Just for fun: Countdown numbers game solver

[Paul Rubin]

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))

    ams = [add,mul,sub]

    def countdown(nums, trace='', ops=[add,mul,sub,div]):
        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])