Ever since I learnt to program I've always loved writing solvers for the Countdown numbers game problem in different languages, and so now I'm wondering what the most elegant solution in Python is.
If you don't know the game, it's simple: you're given six randomly chosen positive integers, and a target (another randomly chosen positive integer), and you have to make the target using only the numbers you're given, and +,-,* and / (and any number of brackets you like). You're not allowed fractions as intermediate values. So, given 2, 3 and 5 say, and a target of 21, you could do (2+5)*3 = 21. So what's the best algorithm? And, what's the most elegant way to code it in Python? I've posted my most elegant version below (I have a faster version which is slightly less elegant). Can anyone do better? Refs: * This academic paper describes an implementation of an algorithm to solve the problem in Haskell. I found it after I'd written mine but it uses a very similar algorithm. http://www.cs.nott.ac.uk/~gmh/countdown.pdf * My web page where I put both versions of my code: http://thesamovar.net/countdownnumbers * The web page of the TV show the problem is based on: http://www.channel4.com/entertainment/tv/microsites/C/countdown/index.html My version: class InvalidExpressionError(ValueError): pass subtract = lambda x,y: x-y def add(x,y): if x<=y: return x+y raise InvalidExpressionError def multiply(x,y): if x<=y or x==1 or y==1: return x*y raise InvalidExpressionError def divide(x,y): if not y or x%y or y==1: raise InvalidExpressionError return x/y add.display_string = '+' multiply.display_string = '*' subtract.display_string = '-' divide.display_string = '/' standard_operators = [ add, subtract, multiply, divide ] class Expression(object): pass class TerminalExpression(Expression): def __init__(self,value,remaining_sources): self.value = value self.remaining_sources = remaining_sources def __str__(self): return str(self.value) def __repr__(self): return str(self.value) class BranchedExpression(Expression): def __init__(self,operator,lhs,rhs,remaining_sources): self.operator = operator self.lhs = lhs self.rhs = rhs self.value = operator(lhs.value,rhs.value) self.remaining_sources = remaining_sources def __str__(self): return '('+str(self.lhs)+self.operator.display_string +str(self.rhs)+')' def __repr__(self): return self.__str__() def ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0): for value, i in zip(sources,range(len(sources))): yield TerminalExpression(value=value, remaining_sources=sources[:i]+sources[i+1:]) if len(sources)>=2+minimal_remaining_sources: for lhs in ValidExpressions(sources,operators,minimal_remaining_sources+1): for rhs in ValidExpressions(lhs.remaining_sources, operators, minimal_remaining_sources): for f in operators: try: yield BranchedExpression(operator=f, lhs=lhs, rhs=rhs, remaining_sources=rhs.remaining_sources) except InvalidExpressionError: pass def TargetExpressions(target,sources,operators=standard_operators): for expression in ValidExpressions(sources,operators): if expression.value==target: yield expression def FindFirstTarget(target,sources,operators=standard_operators): for expression in ValidExpressions(sources,operators): if expression.value==target: return expression raise IndexError, "No matching expressions found" if __name__=='__main__': import time start_time = time.time() target_expressions = list(TargetExpressions(923,[7,8,50,8,1,3])) target_expressions.sort(lambda x,y:len(str(x))-len(str(y))) print "Found",len(target_expressions),"solutions, minimal string length was:" print target_expressions[0],'=',target_expressions[0].value print print "Took",time.time()-start_time,"seconds." -- http://mail.python.org/mailman/listinfo/python-list
