Countdown numbers game solver

While learning Python, I wrote the program attached below to solve the Countdown numbers game. From what I've seen on the web, my program is simpler than any of the other programs with source code out there. Having written it I found this paper which uses a very similar solution to mine (but in Haskell rather than Python).

The source code for the first version is heavily commented with algorithmic details. It takes about 15 seconds to find all solutions on my 2.4GHz laptop.

My ideal (as always with Python) was to write a program you could just look at and understand without comments, but I don't think I achieved that. The first version certainly doesn't, but maybe the second version does. I'd be interested if a more experienced Python programmer could do better in this respect. Let me know.

This snippet is from the second version (slower, 40 seconds to find all solutions) which is supposed to be understandable without comments:

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


countdown-numbers-solver.py.txt8.42 KB
countdown-numbers-solver-2.py.txt2.8 KB
Categories: |