Módulo para combinatoria

[Arnau Sanchez]

Chema Cortes escribió:

 > David Asorey Álvarez escribió:
 >
 >> Lo preguntaba porque estaba tratando de hacer un divertimento del tipo
 >> "Cifras y letras" (para quien no lo conozca, es un programa de la
 >> televisión local de Madrid en el que hay que hacer la palabra más
 >> larga -válida- posible usando nueve letras escogidas al azar).
 >
 > Antes que en TeleMadrid, hace muchos años, fue un programa de TVE2
 > (Televisión Española). Yo llegué a hacer un programa en C para Macintosh
 > para la otra parte del programa, la de las "cifras". Ahora ya no uso ni
 > C ni Macintosh, por lo que a veces me planteo el pasarlo a python. :-P

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 (¿?)

ej: python numbers.py 2 10 7 50 3 9 931

found!! (6.99 secs): 931 = ((((9*3)+50)*(10+2))+7)

saludos
arnau

------

#!/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:
	def __init__(self, value, string=None):
		self.value = value
		self.string = string or str(value)

	def __int__(self):
		return self.value

	def __add__(self, n):
		return self.__class__(self.value+n.value, "(%s+%s)" %(self.string, n.string))

	def __sub__(self, n):
		return self.__class__(self.value-n.value, "(%s-%s)" %(self.string, n.string))

	def __div__(self, n):
		return self.__class__(self.value/n.value, "(%s/%s)" %(self.string, n.string))

	def __mul__(self, n):
		return self.__class__(self.value*n.value, "(%s*%s)" %(self.string, n.string))

	def __repr__(self):
		return self.string

# 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]
		self.nearest = StringInt(0)

	########################
	def process_pair(self, a, b):
		if a < b: a,b = b,a
		values = [a, b, a+b, a*b]
		if int(a-b) > 0: values.append(a-b)
		if not (int(a)%int(b)) and int(b): values.append(a/b)	
		return values
	
	########################
	def check_value(self, val):
		if self.final == int(val):
			return True
		if abs(self.final-int(val)) < abs(self.final-int(self.nearest)):
			self.nearest = val
			print "debug: %d = %s" %(self.nearest, repr(val))

	########################
	def process(self, numbers):
		for index1 in xrange(len(numbers)-1):
			for index2 in xrange(index1+1, len(numbers)):
				number1, number2 = numbers[index1], numbers[index2]
				others = numbers[:index1] + numbers[index1+1:index2] + numbers[index2+1:]
				for num in self.process_pair(number1, number2):
					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

###########################
### MAIN
############

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 = %s" %(elapsed, final, 
str(res))
	else: print "not found (%0.2f secs). best aprox: %d = %s" %(elapsed, int(res), 
str(res))
	
if __name__ == "__main__":
	main()