# Just for fun: Countdown numbers game solver

Paul Rubin http
Mon Jan 21 08:51:41 CET 2008

```Arnaud Delobelle <arnodel at googlemail.com> writes:
> After a quick glance at your code it seems to me that you can only
> have solutions of the type:
>         (num, num, op, num, op, num, op, num, op, num, op)
> this omits many possible solutions (see the one above).

Here's my latest, which I think is exhaustive, but it is very slow.
It prints a progress message now and then just to give the user some
sign of life.  It should print a total of 256-8 = 248 of those
messages and it takes around 20 minutes on my old 1 Ghz Pentium 3.  It
does find plenty of solutions for 234, e.g.

234 mul(9,sub(mul(mul(6,mul(3,1)),7),100))

There are some obvious clunky ways to speed it up through memoizing
and symmetry folding but I can't help thinking there's a concise
elegant way to do that too.

================================================================
from operator import *
from time import time, ctime
start_time = time()

def partition(k):
for i in xrange(1, (1<<k) - 1):
yield tuple(bool(i & (1<<j)) for j in xrange(k))

d = div in ops

if len(nums) == 1:
yield nums[0], str(nums[0])

for p1 in partition(len(nums)):
n0s = list(a for p,a in zip(p1, nums) if p)
n1s = list(a for p,a in zip(p1, nums) if not p)

for f in ops:
if d: print '->', n0s, f, '%.3f'%(time()-start_time)
for r0,t0 in countdown(n0s, trace, ams):
for r1,t1 in countdown(n1s, trace, ams):
if f != div or r1 != 0 and r0 % r1 == 0:
yield f(r0, r1), \
'%s(%s,%s)'% (f.__name__, t0, t1)

def find_repr(target, nums):
for x,t in countdown(nums):
if x == target:
print x,t

print ctime()
find_repr(234, [100,9,7,6,3,1])

```