Just for fun: Countdown numbers game solver

Arnaud Delobelle arnodel at googlemail.com
Sat Jan 26 17:13:01 CET 2008


Right, I've cleaned up my efforts a bit:

* tried to improve the efficiency of the 'fold' technique that I  
posted earlier.
* taken on Dan's email about equivalence of expressions
* created a problem random generator
* created a little function test to time and compare various things,  
and a 'random test' function.

In the file there are two methods for combining two expressions: 'ops'  
and 'cleverops'.  Ops is vanilla, cleverops only returns canonical  
expressions (roughly) as defined in Dan's email.

The two strategies for walking the solution tree are 'divide and  
conquer' (divide) and 'origami' (fold).  The code is pretty  
straighforward and is commented!

Then there are some convenience functions for running the algorithms:  
print_countdown, all_countdown and first_countdown.

Here's an example of how it works:

 >>> # print all solutions using the divide method, and cleverops:
 >>> print_countdown([50, 8, 5, 4, 9, 10], 983, method=divide,  
ops=cleverops)
50*5*4-9-8
(50*5+8-10)*4-9
(50+8/4)*(10+9)-5
50*(10-5)*4-9-8
 >>> # Test which method is fastest, divide or fold:
 >>> randtest(10, 'method', method=[divide, fold], ops=cleverops)
       divide         fold
     0.317304     0.366359    ([1, 2, 4, 3, 6, 7], 249)
     0.495667     0.660426    ([75, 100, 50, 25, 9, 3], 289)
     0.443912     0.562409    ([50, 8, 5, 4, 9, 10], 399)
     0.199696     0.231997    ([100, 1, 5, 7, 1, 4], 833)
     0.406256     0.527588    ([50, 25, 10, 9, 3, 8], 123)
     0.263348     0.315722    ([9, 8, 7, 5, 1, 7], 730)
     0.403028     0.517426    ([25, 75, 9, 4, 10, 6], 605)
     0.420140     0.564138    ([10, 6, 10, 9, 5, 4], 900)
     0.278489     0.343525    ([4, 10, 5, 9, 9, 1], 388)
     0.485815     0.643627    ([100, 10, 2, 6, 3, 9], 146)
------------ ------------
     0.371365     0.473322
 >>> # Test which method is best for finding just one solution:
 >>> randtest(10, 'method', method=[divide, fold],  
countdown=first_countdown)
       divide         fold
     0.001674     0.043920    ([50, 75, 25, 9, 5, 8], 333)
     0.164332     0.072060    ([75, 2, 7, 8, 8, 5], 409)
     0.028889     0.212317    ([50, 100, 75, 6, 3, 9], 782)
     0.049070     0.005830    ([75, 4, 3, 2, 1, 6], 471)
     0.014728     0.091845    ([100, 75, 25, 50, 8, 7], 483)
     0.290982     0.367972    ([3, 1, 7, 6, 5, 3], 794)
     0.240363     0.118508    ([50, 100, 75, 3, 1, 10], 537)
     0.001693     0.009519    ([50, 75, 8, 7, 5, 5], 180)
     0.000289     0.037539    ([3, 9, 2, 4, 4, 1], 123)
     0.079161     0.174323    ([50, 75, 100, 25, 4, 10], 723)
------------ ------------
     0.087118     0.113383
 >>> # Test how cleverops improves over ops for the fold method:
 >>> randtest(10, 'ops', method=fold, ops=[ops, cleverops])
          ops    cleverops
     1.689920     0.671041    ([75, 9, 6, 10, 3, 9], 874)
     0.938402     0.338120    ([5, 7, 8, 2, 1, 7], 258)
     0.982800     0.333443    ([25, 50, 9, 4, 8, 1], 309)
     1.152037     0.407845    ([25, 50, 3, 5, 10, 1], 736)
     0.892541     0.323406    ([9, 7, 1, 9, 4, 10], 108)
     1.794778     0.677161    ([25, 50, 10, 8, 2, 6], 357)
     1.534185     0.591878    ([50, 100, 25, 7, 7, 3], 773)
     1.013421     0.350179    ([50, 6, 3, 1, 8, 9], 761)
     0.612838     0.228354    ([25, 1, 4, 3, 1, 4], 148)
     1.213055     0.430611    ([50, 100, 5, 3, 10, 1], 814)
------------ ------------
     1.182398     0.435204

I have found that the 'divide & conquer' strategy is faster than the  
'origami' one.  Moreover cleverops (i.e. clever pruning) improves  
origami by much more than divide&conquer.

Code follows.  Terry: I'm going to look at your code tonight and see  
if I can interface it with my little testing suite.  Thanks for  
posting it!

It was a lot of fun thinking about this, although I am sure that there  
is a lot of room for improvement.  In particular, there must be a  
simple way to avoid the amount of list tinkering in fold().  Any  
feedback greatly appreciated.

-- 
Arnaud

====================== countdown.py =======================
def getop(h): return 'n' if isinstance(h, int) else h[1]

# An ops function takes two numbers with histories and yield all  
suitable
# ways of combining them together.

def ops(a, b):
     if a < b: a, b = b, a
     x, hx = a
     y, hy = b
     yield x + y, (a, '+', b)
     if x != 1 and y != 1:
         yield x * y, (a, '*', b)
     if x != y:
         yield x - y, (a, '-', b)
     if not x % y and y != 1:
         yield x / y, (a, '/', b)

def cleverops(a, b, getop=getop):
     if a < b: a, b = b, a
     x, hx = a
     y, hy = b
     opx, opy = getop(hx), getop(hy)
     # rx is the right operand of hx (or x if no history)
     rx = x if opx == 'n' else hx[2][0]
     if opy not in '+-':
         # Only allow a+b+c-x-y-z if a >= b >= c...
         if (opx == '+' and rx >= y) or (opx not in '+-' and x >= y):
             yield x + y, (a, '+', b)
         # ... and x >= y >= z
         if x > y and (opx != '-' or rx >= y):
             yield x - y, (a, '-', b)
     if y != 1 and opy not in '*/':
         # Only allow a*b*c/x/y/z if a >= b >= c...
         if (opx == '*' and rx >= y) or (opx not in '*/' and x >= y):
             yield x * y, (a, '*', b)
         # ... and x >= y >= z
         if not x % y and (opx != '/' or rx >= y):
             yield x / y, (a, '/', b)

# a method function takes a list of numbers, an action, and and ops
# function.  It should go through all ways of combining the numbers
# together (using ops) and apply action to each.

def fold(nums, action, ops=cleverops):
     "Use the 'origami' approach"
     nums = zip(nums, nums) # Attach a history to each number
     def recfold(start=1):
         for i in xrange(start, len(nums)):
             a, ii = nums[i], i-1     # Pick a number;
             for j in xrange(i):
                 b = nums.pop(j)      # Take out another before it;
                 for x in ops(a, b):  # combine them
                     nums[ii] = x     # into one;
                     action(*x)       # (with side-effect)
                     recfold(ii or 1) # then fold the shorter list.
                 nums.insert(j, b)
             nums[i] = a
     recfold()

def divide(nums, action, ops=cleverops):
     "Use the 'divide and conquer' approach"
     def partitions(l):
         "generate all 2-partitions of l"
         for i in xrange(1, 2**len(l)-1, 2):
             partition = [], []
             for x in l:
                 i, r = divmod(i, 2)
                 partition[r].append(x)
             yield partition
     def recdiv(l):
         if len(l) == 1: # if l in a singleton,
             yield l[0]  # we're done.
         else:
             for l1, l2 in partitions(l):    # Divide l in two;
                 for a in recdiv(l1):        # conquer the two
                     for b in recdiv(l2):    # smaller lists;
                         for x in ops(a, b): # combine results
                             action(*x)      # (with side-effect)
                             yield x         # and yield answer.
     for x in recdiv(zip(nums, nums)): pass

# Countdown functions

def all_countdown(nums, target, method=fold, ops=cleverops):
     "Return all ways of reaching target with nums"
     all = []
     def action(n, h):
         if n == target:
             all.append(h)
     method(nums, action, ops)
     return all

def print_countdown(nums, target, method=fold, ops=cleverops):
     "Print all solutions"
     def action(n, h):
         if n == target:
             print pretty(h)
     method(nums, action, ops)

class FoundSolution(Exception):
     "Helper exception class for first_countdown"
     def __init__(self, sol):
         self.sol = sol

def first_countdown(nums, target, method=fold, ops=cleverops):
     "Return one way of reaching target with nums"
     def action(n, h):
         if n == target:
             raise FoundSolution(h)
     try:
         method(nums, action, ops)
     except FoundSolution, fs:
         return pretty(fs.sol)

# Pretty representation of a number's history

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 = x[1], y[1]
         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))

# This test function times a call to a countdown function, it allows
# comparisons between differents things (methods, ops, ...)

def test(enumkey=None, **kwargs):
     from time import time
     def do_countdown(countdown=all_countdown, target=758,
                       nums=[2, 4, 5, 8, 9, 25], **kwargs):
         return countdown(nums, target, **kwargs)
     enum = kwargs.pop(enumkey) if enumkey else ['time']
     for val in enum:
         if enumkey: kwargs[enumkey] = val
         t0 = time()
         do_countdown(**kwargs)
         t1 = time()
         yield t1-t0

# Tools for generating random countdown problems and doing random
# tests.

bignums, smallnums = [25, 50, 75, 100], range(1, 11)*2
from random import sample, randrange

def randnums(nbig=None):
     if nbig is None:
         nbig = randrange(5)
     return sample(bignums, nbig) + sample(smallnums, 6-nbig)

def randtarget(): return randrange(100, 1000)

# Like test() but generates n tests with a new random problem to solve
# each time, and prints the results.

def randtest(n=1, enumkey=None, col=12, **kwargs):
     if enumkey:
         enums = kwargs[enumkey]
         nenums = len(enums)
         enums = [getattr(obj, '__name__', obj) for obj in enums]
         print ' '.join("%*s" % (col, obj[:col]) for obj in enums)
     else:
         nenums = 1
     acc = [0] * nenums
     for i in xrange(n):
         target, nums = randtarget(), randnums()
         kwargs.update(target=target, nums=nums)
         times = tuple(test(enumkey, **kwargs))
         print ' '.join("%*f" % (col, t) for t in times),
         print '   (%s, %s)' % (nums, target)
         for i, t in enumerate(times): acc[i] += t
     if n > 1:
         print ' '.join(['-'*col]*nenums)
         print ' '.join("%*f" % (col, t/n) for t in acc)




More information about the Python-list mailing list