Re: Módulo para combinatoria

[Chema Cortes]

El 8/08/06, Arnau Sanchez<arnau en ehas.org> escribió:

> Repasando el archivo de la lista me encontré con este hilo de abril pasado... me
> ha hecho gracia, porque precisamente hice ese algoritmo (el de buscar la
> solución de "Cifras") para practicar clases y recursividad cuando empecé con
> Python (así que no espereis ninguna maravilla). Ahí va por si le interesara a
> alguien (¿?)

Para ser de un ejercicio de iniciación está muy completo.

Si admites una sugerencia, yo habría derivado la clase StringInt del
tipo int. Te evitarías tener que andar transformando a entero antes de
operar. También se puede aprovechar mejor la "representación" con el
fomato "%r" en lugar del "%s". A parte de ésto, tenías una redundancia
ya que volvías a añadir los dos operandos a la lista en el método
"process_pair". A ver qué te parece esta reescritura, es algo más
rápido que el que tenías:



#!/usr/bin/python

# Solves a simple math game: given an arbitray list of numbers, and using
# the 4 basic rules (+, -, /, *)  between them, find (or be close to) another
# given number. Spanish readers will probably know it for the old "Cifras y
# Letras" quiz show.
#
# Comments: arnau en ehas.org

# Standard Python modules
import sys, time

class StringInt(int):
    def __new__(cls,n=0,base=10,_repr=None):
        self=super(StringInt,cls).__new__(cls,n)
        self._repr = _repr or str(n)
        return self

    def __add__(self, n):
        return StringInt( super(StringInt,self).__add__(n),
                _repr="(%r+%r)"%(self,n) )

    def __mul__(self, n):
        return StringInt( super(StringInt,self).__mul__(n),
                _repr="(%r*%r)"%(self,n) )

    def __div__(self, n):
        return StringInt( super(StringInt,self).__div__(n),
                _repr="(%r/%r)"%(self,n) )

    def __sub__(self, n):
        return StringInt( super(StringInt,self).__sub__(n),
                _repr="(%r-%r)"%(self,n) )

    def __repr__(self):
        return self._repr

# Uncomment to use integers instead of StringInt objects
#StringInt = int


class SeekNumber:

    def __init__(self, final, numbers):
        self.final = final
        self.numbers = [StringInt(x) for x in numbers if x>0]
        self.nearest = StringInt(0)

    def process_pair(self, a, b):
        values = [a+b, a*b]
        if a>b: values.append(a-b)
        if a<b: values.append(b-a)
        if a%b==0: values.append(a/b)
        return values

    def check_value(self, val):

        if abs(self.final-val) < abs(self.final-self.nearest):
            self.nearest = val
            print "debug: %d = %r  delta=%d" %(self.nearest, val,
abs(self.final-val))

        return self.final==val

    def process(self, numbers):
        for num in numbers:
            if self.check_value(num): return num

        for i1,n1 in enumerate(numbers[:-1]):
            for i2,n2 in enumerate(numbers[i1+1:]):
                others = numbers[:]
                del others[i1+i2+1]
                del others[i1]
                for num in self.process_pair(n1, n2):
                    if self.check_value(num):
                        return num
                    values=self.process([num] + others)
                    if values:
                        return values

    def run(self):
        retval = self.process(self.numbers)
        return retval or self.nearest


def main():
    args = sys.argv[1:]
    if len(args) < 3:
        print "usage: numbers.py n1 n2 [n3] [n4] ... [nN] final"
        sys.exit(1)
    final, numbers = int(args[-1]), [int(x) for x in args[:-1]]
    sn = SeekNumber(final, numbers)
    t0 = time.time()
    res = sn.run()
    elapsed = time.time() - t0
    if int(res) == final:
        print "found!! (%0.2f secs): %d = %r" %(elapsed, final, res)
    else:
        print "not found (%0.2f secs). best aprox: %d = %r" %(elapsed, res, res)

if __name__ == "__main__":
    main()