Just for fun: Countdown numbers game solver
Arnaud Delobelle
arnodel at googlemail.com
Sat Jan 26 11:13:01 EST 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