# Just for fun: Countdown numbers game solver

Tue Jan 22 02:20:54 CET 2008

```On Jan 20, 5:41 pm, dg.google.gro... at thesamovar.net wrote:
> 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.

I've tried a completely different approach, that I imagine as
'folding'.  I thought it would improve performance over my previous
effort but extremely limited and crude benchmarking seems to indicate
disappointingly comparable performance...

def ops(a, b):
"Generate all possible ops on two numbers with histories"
x, hx = a
y, hy = b
if x < y:
x, y, hx, hy = y, x, hy, hx
yield x + y, (hx, '+', hy)
if x != 1 and y != 1:
yield x * y, (hx, '*', hy)
if x != y:
yield x - y, (hx, '-', hy)
if not x % y and y != 1:
yield x / y, (hx, '/', hy)

def fold(nums, action, ops=ops):
"""Perform all possible ways of folding nums using ops.
Side-effect action triggered for every fold."""
nums = zip(nums, nums) # Attach a history to each number
def recfold():
for i in xrange(1, len(nums)):
a = nums.pop(i)         # Take out a number;
for j in xrange(i):
b = nums[j]         # choose another before it;
for x in ops(a, b): # combine them
nums[j] = x     # into one;
action(x)       # (with side-effect)
recfold()       # then fold the shorter list.
nums[j] = b
nums.insert(i, a)
recfold()

def all_countdown(nums, target):
"Return all ways of reaching target with nums"
all = set()
def action(nh):
if nh[0] == target:
fold(nums, action)
return all

def print_countdown(nums, target):
"Print all solutions"
print '\n'.join(all_countdown(nums, target))

class FoundSolution(Exception):
def __init__(self, sol):
self.sol = sol

def first_countdown(nums, target):
"Return one way of reaching target with nums"
def action(nh):
if nh[0] == target:
raise FoundSolution(nh[1])
try:
fold(nums, action)
except FoundSolution, fs:
return pretty(fs.sol)

# pretty helpers
def getop(h): return 'n' if isinstance(h, int) else h[1]
lbracket = ['+*', '-*', '+/', '-/', '/*', '//']
rbracket = ['*+', '*-', '/+', '/-', '/*', '//', '-+', '--']

def pretty(h):
"Print a readable form of a number's history"
if isinstance(h, int):
return str(h)
else:
x, op, y = h
x, y, xop, yop = pretty(x), pretty(y), getop(x), getop(y)
if xop + op in lbracket: x = "(%s)" % x
if op + yop in rbracket: y = "(%s)" % y
return ''.join((x, op, y))

--
Arnaud

```