Just for fun: Countdown numbers game solver

[dg.google.groups]

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.

If you don't know the game, it's simple: you're given six randomly
chosen positive integers, and a target (another randomly chosen
positive integer), and you have to make the target using only the
numbers you're given, and +,-,* and / (and any number of brackets you
like). You're not allowed fractions as intermediate values. So, given
2, 3 and 5 say, and a target of 21, you could do (2+5)*3 = 21.

So what's the best algorithm? And, what's the most elegant way to code
it in Python? I've posted my most elegant version below (I have a
faster version which is slightly less elegant). Can anyone do better?

Refs:

* This academic paper describes an implementation of an algorithm to
solve the problem in Haskell. I found it after I'd written mine but it
uses a very similar algorithm. http://www.cs.nott.ac.uk/~gmh/countdown.pdf
* My web page where I put both versions of my code: http://thesamovar.net/countdownnumbers
* The web page of the TV show the problem is based on:
http://www.channel4.com/entertainment/tv/microsites/C/countdown/index.html

My version:

class InvalidExpressionError(ValueError):
pass

subtract = lambda x,y: x-y
def add(x,y):
if x<=y: return x+y
raise InvalidExpressionError
def multiply(x,y):
if x<=y or x==1 or y==1: return x*y
raise InvalidExpressionError
def divide(x,y):
if not y or x%y or y==1:
raise InvalidExpressionError
return x/y

add.display_string = '+'
multiply.display_string = '*'
subtract.display_string = '-'
divide.display_string = '/'

standard_operators = [ add, subtract, multiply, divide ]

class Expression(object): pass

class TerminalExpression(Expression):
def __init__(self,value,remaining_sources):
self.value = value
self.remaining_sources = remaining_sources
def __str__(self):
return str(self.value)
def __repr__(self):
return str(self.value)

class BranchedExpression(Expression):
def __init__(self,operator,lhs,rhs,remaining_sources):
self.operator = operator
self.lhs = lhs
self.rhs = rhs
self.value = operator(lhs.value,rhs.value)
self.remaining_sources = remaining_sources
def __str__(self):
return '('+str(self.lhs)+self.operator.display_string
+str(self.rhs)+')'
def __repr__(self):
return self.__str__()

def
ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0):
for value, i in zip(sources,range(len(sources))):
yield TerminalExpression(value=value,
remaining_sources=sources[:i]+sources[i+1:])
if len(sources)>=2+minimal_remaining_sources:
for lhs in
ValidExpressions(sources,operators,minimal_remaining_sources+1):
for rhs in ValidExpressions(lhs.remaining_sources,
operators, minimal_remaining_sources):
for f in operators:
try: yield BranchedExpression(operator=f, lhs=lhs,
rhs=rhs, remaining_sources=rhs.remaining_sources)
except InvalidExpressionError: pass

def TargetExpressions(target,sources,operators=standard_operators):
for expression in ValidExpressions(sources,operators):
if expression.value==target:
yield expression

def FindFirstTarget(target,sources,operators=standard_operators):
for expression in ValidExpressions(sources,operators):
if expression.value==target:
return expression
raise IndexError, "No matching expressions found"

if __name__=='__main__':
import time
start_time = time.time()
target_expressions = list(TargetExpressions(923,[7,8,50,8,1,3]))
target_expressions.sort(lambda x,y:len(str(x))-len(str(y)))
print "Found",len(target_expressions),"solutions, minimal string
length was:"
print target_expressions[0],'=',target_expressions[0].value
print
print "Took",time.time()-start_time,"seconds."

 

[marek.rocki]

Nice challenge! I came up with something like this:

def find_repr(target, numbers):
org_reprs = dict((number, str(number)) for number in numbers)
curr_reprs = org_reprs
while target not in curr_reprs:
old_reprs, curr_reprs = curr_reprs, {}
for x in old_reprs:
for y in org_reprs:
repr_x, repr_y = old_reprs[x], old_reprs[y]
curr_reprs[x + y] = '(%s)+(%s)' % (repr_x, repr_y)
curr_reprs[x - y] = '(%s)-(%s)' % (repr_x, repr_y)
curr_reprs[x * y] = '(%s)*(%s)' % (repr_x, repr_y)
if y <> 0 and x % y == 0:
curr_reprs[x // y] = '(%s)/(%s)' % (repr_x, repr_y)
curr_reprs.update(old_reprs)
return curr_reprs[target]

print '21 =', find_repr(21, [2, 3, 5])
print '923 =', find_repr(923, [7, 8, 50, 8, 1, 3])

Unfortunately, this yields solutions that are a bit lispish (as in
'lots of superfluous parentheses' in the result). Nothing a simple
regex or two wouldn't fix ;-) And the solution found would be minimal
not with respect to the string length, but rather to the number of
operations to be performed.

Apart from that, I find it quite elegant. I'd like to know if it has
any flaws.

Regards,
Marek

 

[Gabriel Genellina]

Nice challenge! I came up with something like this:

A nice solution too!

 

[dg.google.groups]

Hi Marek,

That's a really nice solution (and ultrafast).

Unfortunately I realise I stated the problem imprecisely. You're only
allowed to use each number once (otherwise there's a trivial solution
for every problem, i.e. x/x + x/x + x/x + ... + x/x repeated y times
for target y given any source number x). Trying your program on 234
from [100,9,7,6,3,1] gives you 9*9*3-9 using the 9 three times.

Does your solution adjust to deal with this additional requirement? At
first I thought it would be an easy fix, but maybe it's a little more
complicated than I thought...

Dan Goodman

 

[Paul Rubin]

Unfortunately I realise I stated the problem imprecisely. You're only
allowed to use each number once (otherwise there's a trivial solution
for every problem, i.e. x/x + x/x + x/x + ... + x/x repeated y times
for target y given any source number x). Trying your program on 234
from [100,9,7,6,3,1] gives you 9*9*3-9 using the 9 three times.

Here is a pretty inefficient solution. It doesn't find 234 but it
does find 253 twice:

from operator import *

def countdown(nums, ops, trace):
n0 = nums[0]
if len(nums) == 1:
yield n0, str(n0)
return
for i,n in enumerate(nums[1:]):
for f in ops:
for r,t in countdown(nums[1:i] + nums[i+1:], [add, mul, sub], trace):
if f != div or r != 0 and n0 % r == 0:
yield f(n0, r), '%s(%s,%s)'% (f.__name__, n0, t)

def search(nums, target):
for x,t in countdown(nums, [add, mul, sub, div], []):
if x == target:
print x,t

search([100,9,7,6,3,1], 253)

 

[Arnaud Delobelle]

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.

If you don't know the game, it's simple: you're given six randomly
chosen positive integers, and a target (another randomly chosen
positive integer), and you have to make the target using only the
numbers you're given, and +,-,* and / (and any number of brackets you
like). You're not allowed fractions as intermediate values. So, given
2, 3 and 5 say, and a target of 21, you could do (2+5)*3 = 21.

Neat problem! I couldn't help but have a go. I have no idea how
efficient it is, I didn't think too much before I started typing


def partitions(l):
""""split(l) -> an iterator over all partitions of l into two
lists

There is no repetition provided that all elements of l are
distinct."""
# Works only for lists of length < 8*size(int) due to xrange
limitations
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 calc(l, filter=lambda *x:x):
"""calc(l, filter) -> an iterator over all expressions involving
all
numbers in l

filter is a function that returns its two arguments with possible
side-effects. """
if len(l) == 1:
yield l[0], str(l[0])
else:
for l1, l2 in partitions(l):
for v1, s1 in calc(l1, filter):
for v2, s2 in calc(l2, filter):
yield filter(v1 + v2, '(%s+%s)' % (s1, s2))
yield filter(v1 * v2, '(%s*%s)' % (s1, s2))
if v1 > v2:
yield filter(v1 - v2, '(%s-%s)' % (s1, s2))
elif v2 > v1:
yield filter(v2 - v1, '(%s-%s)' % (s2,
s1))
if not v1 % v2:
yield filter(v1 / v2, '(%s/%s)' % (s1, s2))
elif not v2 % v1:
yield filter(v2 / v1, '(%s/%s)' % (s2, s1))


def print_filter(target):
"""print_filter(target) -> filter that prints all expressions that
equal target"""
def filter(v, s):
if v == target: print s
return v, s
return filter

class ShortestFilter(object):
def __init__(self, target):
self.shortest = None
self.target = target
def __call__(self, v, s):
if v == self.target:
if not self.shortest or len(self.shortest) > len(s):
self.shortest = s
return v, s

def countdown(numbers, target):
"""countown(numbers, target) -> None -- print all countdown
solutions"""
for dummy in calc(numbers, print_filter(target)): pass

def best_countdown(numbers, target):
"""best_countdown(numbers, target) -> str -- return shortest
solution"""
filter = ShortestFilter(target)
for dummy in calc(numbers, filter): pass
return filter.shortest

countdown([7,8,50,8,1,3], 923)

(((((50*8)-1)/3)*7)-8)
(((((50*8)-1)*7)/3)-8)
(((((8*50)-1)/3)*7)-8)
(((((8*50)-1)*7)/3)-8)

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

(((1+(3*6))+7)*9)

 

[Mel]

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.

If you don't know the game, it's simple: you're given six randomly
chosen positive integers, and a target (another randomly chosen
positive integer), and you have to make the target using only the
numbers you're given, and +,-,* and / (and any number of brackets you
like). You're not allowed fractions as intermediate values. So, given
2, 3 and 5 say, and a target of 21, you could do (2+5)*3 = 21.

So what's the best algorithm? And, what's the most elegant way to code
it in Python? I've posted my most elegant version below (I have a
faster version which is slightly less elegant). Can anyone do better?

I found that postfix notation made it easy to run up all the possible
expressions based on permutations of the available numbers. Don't
know where my source code is ... have to look.

Mel.

 

[Paul Rubin]

Unfortunately I realise I stated the problem imprecisely. You're only
allowed to use each number once (otherwise there's a trivial solution
for every problem, i.e. x/x + x/x + x/x + ... + x/x repeated y times
for target y given any source number x). Trying your program on 234
from [100,9,7,6,3,1] gives you 9*9*3-9 using the 9 three times.

Here's an inefficient solution, that doesn't find 234 but finds 253.
If you see a double post, it's because I posted something similar a
little while ago but cancelled it since it had a bug. I'm not sure
this one is correct either ;-).

from operator import *

def countdown(nums, trace='', ops=[add,mul,sub,div]):
n0,n1s = nums[0], nums[1:]
if not n1s:
yield n0, str(n0)
return
for f in ops:
for r,t in countdown(n1s, trace, [add, mul, sub]):
if f != div or r != 0 and n0 % r == 0:
yield f(n0, r), '%s(%s,%s)'% (f.__name__, n0, t)

def find_repr(target, nums):
# print all representations of target from nums
for x,t in countdown(nums):
if x == target:
print x,t

find_repr(253, [100,9,7,6,3,1])

 

[Arnaud Delobelle]

Ever since I learnt to program I've always loved writing solvers for
the Countdown numbers game problem in different languages

Ok so here's a challenge I just thought of:

What is (or are) the set of 6 starting numbers which are such that the
smallest target they can't reach is maximal?

E.g for 1, 2, 3, 4, 5, 6 the smallest target they can't reach is 284:

100 = ((5*4)*(3+2))
101 = (5+((4*3)*(6+2)))
102 = (((6*5)+4)*3)
103 = ((5*((6*4)-3))-2)
...
280 = ((5*(4+3))*(6+2))
281 = (((5*(4+3))*(6+2))+1)
282 = ((4+((6*5)*3))*(2+1))
283 = (3+(((5*4)*2)*(6+1)))
284 : can't be done

For 2, 3, 5, 8, 9, 10, the smallest unreachable target is 796 (and
there are five others: 829, 956, 961, 964, 991).

For 2, 4, 5, 8, 9, 10, the smallest is 807 (but there are 23 others)

Time to go to bed

 

[Arnaud Delobelle]

Ok so here's a challenge I just thought of:

What is (or are) the set of 6 starting numbers which are such that the
smallest target they can't reach is maximal?

Update: 2, 4, 5, 8, 9, 25 can reach any target between 100 and 999.

The question remains if we lift the upper limit of 999...

Time to really go to bed

 

[Terry Jones]

Here's a solution that doesn't use any copying of lists in for recursion.
It also eliminates a bunch of trivially equivalent solutions. The countdown
function is 37 lines of non-comment code. Sample (RPN) output below.

Terry


from operator import *

def countdown(target, nums, numsAvail, value, partialSolution, solutions, ops=(add, mul, sub, div)):
if not any(numsAvail):
# Ran out of available numbers. Add the solution, if we're right.
if value == target:
solutions.add(tuple(partialSolution))
elif value is None:
# Use each distinct number as a starting value.
used = set()
for i, num in enumerate(nums):
if num not in used:
numsAvail = False
used.add(num)
partialSolution.append(num)
countdown(target, nums, numsAvail, num, partialSolution, solutions, ops)
numsAvail = True
partialSolution.pop()
else:
for op in ops:
for i, num in enumerate(nums):
if numsAvail:
numsAvail = False
moreAvail = any(numsAvail)
try:
lastNum, lastOp = partialSolution[-2:]
except ValueError:
lastNum, lastOp = partialSolution[-1], None
# Don't allow any of:
if not any((
# Div: after mul, by 1, by 0, producing a fraction.
(op == div and (lastOp == 'mul' or num <= 1 or value % num != 0)),
# If initial mul/add, canonicalize to 2nd operator biggest.
((op == mul or op == add) and lastOp is None and num > lastNum),
# Don't all subtracting 0 (instead allow adding 0).
(op == sub and num == 0),
# Don't allow adding 0 unless it's the very last thing we do.
(op == add and num == 0 and moreAvail),
# Don't allow mult by 1 unless it's the very last thing we do.
(op == mul and num == 1 and moreAvail),
# Don't allow sub after add (allow add after sub).
(op == sub and lastOp == 'add'),
# If same op twice in a row, canonicalize operand order.
(lastOp == op.__name__ and num > lastNum)
)):
partialSolution.extend([num, op.__name__])
countdown(target, nums, numsAvail, op(value, num), partialSolution, solutions, ops)
del partialSolution[-2:]
numsAvail = True

for nums, target in (((100, 9, 7, 6, 3, 1), 253),
((100, 9, 7, 6, 3, 1), 234),
((2, 3, 5), 21),
((7, 8, 50, 8, 1, 3), 923),
((8, 8), 16),
((8, 8, 8), 8),
((8, 0), 8),
((7,), 8),
((), 8),
((8, 8, 8, 8), 32)):
print "Target %d, numbers = %s" % (target, nums)
solutions = set()
countdown(target, nums, [True,] * len(nums), value=None, partialSolution=[], solutions=solutions)
for s in solutions: print '\t', s


This produces:

Target 253, numbers = (100, 9, 7, 6, 3, 1)
(7, 6, 'add', 3, 'add', 1, 'add', 9, 'mul', 100, 'add')
(7, 6, 'mul', 9, 'add', 3, 'mul', 100, 'add', 1, 'mul')
(3, 1, 'add', 6, 'mul', 7, 'sub', 9, 'mul', 100, 'add')
(100, 7, 'sub', 6, 'sub', 3, 'mul', 9, 'sub', 1, 'add')
(7, 1, 'add', 6, 'mul', 3, 'mul', 100, 'add', 9, 'add')
Target 234, numbers = (100, 9, 7, 6, 3, 1)
(6, 1, 'add', 100, 'mul', 7, 'sub', 9, 'add', 3, 'div')
(100, 1, 'sub', 3, 'div', 7, 'mul', 6, 'sub', 9, 'add')
(7, 6, 'mul', 3, 'mul', 100, 'sub', 9, 'mul', 1, 'mul')
(100, 7, 'sub', 3, 'div', 6, 'sub', 1, 'add', 9, 'mul')
(7, 6, 'mul', 3, 'mul', 1, 'sub', 100, 'add', 9, 'add')
(6, 9, 'sub', 7, 'mul', 1, 'sub', 100, 'add', 3, 'mul')
(100, 9, 'sub', 7, 'sub', 6, 'sub', 3, 'mul', 1, 'mul')
(100, 7, 'mul', 3, 'mul', 6, 'add', 9, 'div', 1, 'mul')
(100, 1, 'sub', 7, 'mul', 9, 'sub', 3, 'div', 6, 'add')
(100, 7, 'sub', 3, 'div', 1, 'sub', 9, 'add', 6, 'mul')
(7, 3, 'mul', 6, 'sub', 9, 'mul', 1, 'sub', 100, 'add')
(100, 7, 'mul', 6, 'sub', 1, 'sub', 9, 'add', 3, 'div')
(100, 9, 'add', 7, 'add', 1, 'add', 3, 'div', 6, 'mul')
(100, 9, 'sub', 7, 'div', 6, 'mul', 3, 'mul', 1, 'mul')
Target 21, numbers = (2, 3, 5)
(5, 2, 'add', 3, 'mul')
Target 923, numbers = (7, 8, 50, 8, 1, 3)
(50, 8, 'mul', 1, 'sub', 3, 'div', 7, 'mul', 8, 'sub')
Target 16, numbers = (8, 8)
(8, 8, 'add')
Target 8, numbers = (8, 8, 8)
(8, 8, 'sub', 8, 'add')
(8, 8, 'div', 8, 'mul')
Target 8, numbers = (8, 0)
(8, 0, 'add')
Target 8, numbers = (7,)
Target 8, numbers = ()
Target 32, numbers = (8, 8, 8, 8)
(8, 8, 'add', 8, 'add', 8, 'add')

 

[Paul Rubin]

Here's a solution that doesn't use any copying of lists in for recursion.
It also eliminates a bunch of trivially equivalent solutions. The countdown
function is 37 lines of non-comment code. Sample (RPN) output below.

Nice, I realized after I posted my 2nd solution that it was missing
some cases and it's good to see confirmation that 239 is reachable.
I'll see if I can fix my version. I think the list copying is ok
given that the recursion depth always must be fairly small if the
generator is to complete in any reasonable amount of time.

 

[Arnaud Delobelle]

Here's a solution that doesn't use any copying of lists in for recursion.
It also eliminates a bunch of trivially equivalent solutions. The countdown
function is 37 lines of non-comment code.  Sample (RPN) output below.

Terry

[snip code]

This produces: [...]
Target 234, numbers = (100, 9, 7, 6, 3, 1)
        (6, 1, 'add', 100, 'mul', 7, 'sub', 9, 'add', 3, 'div')
        (100, 1, 'sub', 3, 'div', 7, 'mul', 6, 'sub', 9, 'add')
        (7, 6, 'mul', 3, 'mul', 100, 'sub', 9, 'mul', 1, 'mul')
        (100, 7, 'sub', 3, 'div', 6, 'sub', 1, 'add', 9, 'mul')
        (7, 6, 'mul', 3, 'mul', 1, 'sub', 100, 'add', 9, 'add')
        (6, 9, 'sub', 7, 'mul', 1, 'sub', 100, 'add', 3, 'mul')
        (100, 9, 'sub', 7, 'sub', 6, 'sub', 3, 'mul', 1, 'mul')
        (100, 7, 'mul', 3, 'mul', 6, 'add', 9, 'div', 1, 'mul')
        (100, 1, 'sub', 7, 'mul', 9, 'sub', 3, 'div', 6, 'add')
        (100, 7, 'sub', 3, 'div', 1, 'sub', 9, 'add', 6, 'mul')
        (7, 3, 'mul', 6, 'sub', 9, 'mul', 1, 'sub', 100, 'add')
        (100, 7, 'mul', 6, 'sub', 1, 'sub', 9, 'add', 3, 'div')
        (100, 9, 'add', 7, 'add', 1, 'add', 3, 'div', 6, 'mul')
        (100, 9, 'sub', 7, 'div', 6, 'mul', 3, 'mul', 1, 'mul')

In countdown you are not required to use all numbers to reach the
target. This means you are missing solutions, e.g.
(1, 3, 6, 'mul', 'add', 7 , 'add', 9, 'mul')

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

 

[Paul Rubin]

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

 

[Paul Rubin]

Update: 2, 4, 5, 8, 9, 25 can reach any target between 100 and 999.

Are you sure? What expression do you get for target = 758?

 

[dg.google.groups]

Hi all,

It's great how many different sorts of solutions (or almost solutions)
this puzzle has generated. Speedwise, for reference my solution posted
above takes about 40 seconds on my 1.8GHz laptop, and the less elegant
version (on my webpage linked to in the original post) takes about 15
seconds. It seems to me like surely this problem can be more
efficiently solved than that?

My version isn't very Pythonic (it could almost be written in C++ the
way I've done it) so I liked the idea of the first solution, but I
don't think it can be fixed. I adapted it so that it doesn't use the
same number more than once, but it still has some problems. Firstly,
it only finds solution ((a op b) op c) op d etc. and won't find (for
example (1+2)*(3+4). Secondly, it stores a dictionary value->how to
get to value which is fine if you can re-use numbers because one way
to get to a given value is as good as another, but sometimes you can
get to the same number in two different ways using different numbers,
so it misses solutions.

Paul: 758 = 8+(5*((2+4)*25))

Arnaud: I haven't had time to play with your solution yet - how quick
does it run?

My fantasy is that there is a solution that isn't TOO slow where you
can just look at the code and go 'Oh yes, of course that works!' and
understand it immediately. Maybe that's too much to ask even of
Python! ;-)

 

[Terry Jones]

Arnaud> In countdown you are not required to use all numbers to reach the
Arnaud> target. This means you are missing solutions, e.g. (1, 3, 6,
Arnaud> 'mul', 'add', 7 , 'add', 9, 'mul')

Hi Arnaud.

Thanks, I didn't know that. The fix is a simple change to the first if my
function below.

WRT to the missing solution, note that my code only allowed multiplication
by 1 if it was the last thing done. That was because you can multiply by 1
at any time, and I didn't want to see those trivially equivalent solutions
(same goes for adding 0). Seeing as you're allowed to omit numbers, I've
now gotten rid of those trivial operations altogether in my solution.

Code and output below.

Terry


from operator import *

def countdown(target, nums, numsAvail, value, partialSolution, solutions, ops=(add, mul, sub, div)):
if value == target or not any(numsAvail):
# Ran out of available numbers. Add the solution, if we're right.
if value == target:
solutions.add(tuple(partialSolution))
elif value is None:
# Use each distinct number as a starting value.
used = set()
for i, num in enumerate(nums):
if num not in used:
numsAvail = False
used.add(num)
partialSolution.append(num)
countdown(target, nums, numsAvail, num, partialSolution, solutions, ops)
numsAvail = True
partialSolution.pop()
else:
for op in ops:
for i, num in enumerate(nums):
if numsAvail:
numsAvail = False
moreAvail = any(numsAvail)
try:
lastNum, lastOp = partialSolution[-2:]
except ValueError:
lastNum, lastOp = partialSolution[-1], None
# Don't allow any of:
if not any((
# Div: after mul, by 1, by 0, producing a fraction.
(op == div and (lastOp == 'mul' or num <= 1 or value % num != 0)),
# If initial mul/add, canonicalize to 2nd operator biggest.
((op == mul or op == add) and lastOp is None and num > lastNum),
# Don't allow add or sub of 0.
((op == add or op == sub) and num == 0),
# Don't allow mult by 1.
(op == mul and num == 1),
# Don't allow sub after add (allow add after sub).
(op == sub and lastOp == 'add'),
# If same op twice in a row, canonicalize operand order.
(lastOp == op.__name__ and num > lastNum)
)):
partialSolution.extend([num, op.__name__])
countdown(target, nums, numsAvail, op(value, num), partialSolution, solutions, ops)
del partialSolution[-2:]
numsAvail = True

for nums, target in (((100, 9, 7, 6, 3, 1), 253),
((100, 9, 7, 6, 3, 1), 234),
((2, 3, 5), 21),
((7, 8, 50, 8, 1, 3), 923),
((8, 8), 16),
((8, 8, 8), 8),
((8, 0), 8),
((7,), 8),
((), 8),
((8, 8, 8, 8), 32)):
solutions = set()
countdown(target, nums, [True,] * len(nums), value=None, partialSolution=[], solutions=solutions)
print "%d solutions to: target %d, numbers = %s" % (len(solutions), target, nums)
for s in sorted(solutions, cmp=lambda a, b: cmp(len(a), len(b)) or cmp(a, b)):
print '\t', s


$ time countdown.py
8 solutions to: target 253, numbers = (100, 9, 7, 6, 3, 1)
(6, 3, 'mul', 1, 'sub', 9, 'mul', 100, 'add')
(7, 6, 'mul', 9, 'add', 3, 'mul', 100, 'add')
(9, 3, 'sub', 7, 'mul', 6, 'mul', 1, 'add')
(100, 9, 'sub', 7, 'sub', 3, 'mul', 1, 'add')
(3, 1, 'add', 6, 'mul', 7, 'sub', 9, 'mul', 100, 'add')
(7, 1, 'add', 6, 'mul', 3, 'mul', 100, 'add', 9, 'add')
(7, 6, 'add', 3, 'add', 1, 'add', 9, 'mul', 100, 'add')
(100, 7, 'sub', 6, 'sub', 3, 'mul', 9, 'sub', 1, 'add')
19 solutions to: target 234, numbers = (100, 9, 7, 6, 3, 1)
(6, 3, 'mul', 7, 'add', 1, 'add', 9, 'mul')
(7, 1, 'add', 9, 'mul', 6, 'add', 3, 'mul')
(7, 3, 'mul', 1, 'sub', 6, 'add', 9, 'mul')
(7, 6, 'mul', 3, 'mul', 100, 'sub', 9, 'mul')
(100, 1, 'sub', 3, 'div', 7, 'sub', 9, 'mul')
(100, 1, 'sub', 7, 'mul', 9, 'add', 3, 'div')
(100, 7, 'mul', 3, 'mul', 6, 'add', 9, 'div')
(100, 9, 'sub', 7, 'div', 6, 'mul', 3, 'mul')
(100, 9, 'sub', 7, 'sub', 6, 'sub', 3, 'mul')
(6, 1, 'add', 100, 'mul', 7, 'sub', 9, 'add', 3, 'div')
(6, 9, 'sub', 7, 'mul', 1, 'sub', 100, 'add', 3, 'mul')
(7, 3, 'mul', 6, 'sub', 9, 'mul', 1, 'sub', 100, 'add')
(7, 6, 'mul', 3, 'mul', 1, 'sub', 100, 'add', 9, 'add')
(100, 1, 'sub', 3, 'div', 7, 'mul', 6, 'sub', 9, 'add')
(100, 1, 'sub', 7, 'mul', 9, 'sub', 3, 'div', 6, 'add')
(100, 7, 'mul', 6, 'sub', 1, 'sub', 9, 'add', 3, 'div')
(100, 7, 'sub', 3, 'div', 1, 'sub', 9, 'add', 6, 'mul')
(100, 7, 'sub', 3, 'div', 6, 'sub', 1, 'add', 9, 'mul')
(100, 9, 'add', 7, 'add', 1, 'add', 3, 'div', 6, 'mul')
1 solutions to: target 21, numbers = (2, 3, 5)
(5, 2, 'add', 3, 'mul')
1 solutions to: target 923, numbers = (7, 8, 50, 8, 1, 3)
(50, 8, 'mul', 1, 'sub', 3, 'div', 7, 'mul', 8, 'sub')
1 solutions to: target 16, numbers = (8, 8)
(8, 8, 'add')
1 solutions to: target 8, numbers = (8, 8, 8)
(8,)
1 solutions to: target 8, numbers = (8, 0)
(8,)
0 solutions to: target 8, numbers = (7,)
0 solutions to: target 8, numbers = ()
1 solutions to: target 32, numbers = (8, 8, 8, 8)
(8, 8, 'add', 8, 'add', 8, 'add')

real 0m1.423s
user 0m1.371s
sys 0m0.047s

 

[dg.google.groups]

Decided I may as well post my other solution while I'm at it. The neat
trick here is redefining the add, mul, etc. functions so that they
raise exceptions for example if x>y then add(x,y) raises an exception
which is handled by the search algorithm to mean don't continue that
computation - this stops you from having to evaluate x+y AND y+x, etc.

sub = lambda x,y:x-y
def add(x,y):
if x<=y: return x+y
raise ValueError
def mul(x,y):
if x<=y or x==1 or y==1: return x*y
raise ValueError
def div(x,y):
if not y or x%y or y==1:
raise ValueError
return x/y

add.disp = '+'
mul.disp = '*'
sub.disp = '-'
div.disp = '/'

standard_ops = [ add, sub, mul, div ]

def strexpression(e):
if len(e)==3:
return '('+strexpression(e[1])+e[0].disp+strexpression(e[2])
+')'
elif len(e)==1:
return str(e[0])

# I don't like this function, it's nice and short but is it clear
# what it's doing just from looking at it?
def expressions(sources,ops=standard_ops,minremsources=0):
for i in range(len(sources)):
yield ([sources],sources[:i]+sources[i+1:],sources)
if len(sources)>=2+minremsources:
for e1, rs1, v1 in expressions(sources,ops,minremsources+1):
for e2, rs2, v2 in expressions(rs1,ops,minremsources):
for o in ops:
try: yield ([o,e1,e2],rs2,o(v1,v2))
except ValueError: pass

def findfirsttarget(target,sources,ops=standard_ops):
for e,s,v in expressions(sources,ops):
if v==target:
return strexpression(e)
return None

print findfirsttarget(923,[7,8,50,8,1,3])

gives:

((7*(((8*50)-1)/3))-8)

Dan Goodman

 

[Terry Jones]

Hi Paul

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

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

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

The symmetry folding is important, you can cut off many recursive calls. My
code runs in 0.5 seconds for the 234 problem, but I have a MacBook Pro

Terry

 

[Steven D'Aprano]

Decided I may as well post my other solution while I'm at it. The neat
trick here is redefining the add, mul, etc. functions so that they raise
exceptions for example if x>y then add(x,y) raises an exception which is
handled by the search algorithm to mean don't continue that computation
- this stops you from having to evaluate x+y AND y+x, etc.

Setting up a try...except block is very fast, but actually responding to
an exception is very slow. You _might_ find that it is quicker to
evaluate both expressions than it is to catch the exception.

Better still is to find another way of avoiding both the exception and
the symmetrical calls.