Just for fun: Countdown numbers game solver
dg.googl...@thesamovar.net
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...@wp.pl
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!
--
Gabriel Genellina
dg.googl...@thesamovar.net
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)
--
Arnaud
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
> 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
PS: apologies if I got the results wrong...
Arnaud Delobelle
> On Jan 20, 5:41 pm, dg.google.gro...@thesamovar.net wrote:
>
> > 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?
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 :)
--
Arnaud
Terry Jones
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[i] = False
used.add(num)
partialSolution.append(num)
countdown(target, nums, numsAvail, num, partialSolution, solutions, ops)
numsAvail[i] = True
partialSolution.pop()
else:
for op in ops:
for i, num in enumerate(nums):
if numsAvail[i]:
numsAvail[i] = 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[i] = 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).
--
Arnaud
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.googl...@thesamovar.net
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):
# 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[i] = 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.googl...@thesamovar.net
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[i]],sources[:i]+sources[i+1:],sources[i])
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.
--
Steven
Terry Jones
dg> It's great how many different sorts of solutions (or almost solutions)
dg> this puzzle has generated. Speedwise, for reference my solution posted
dg> above takes about 40 seconds on my 1.8GHz laptop, and the less elegant
dg> version (on my webpage linked to in the original post) takes about 15
dg> seconds. It seems to me like surely this problem can be more
dg> efficiently solved than that?
dg> Paul: 758 = 8+(5*((2+4)*25))
For this I get:
2 solutions to: target 758, numbers = (2, 4, 5, 8, 25)
(4, 2, 'add', 25, 'mul', 5, 'mul', 8, 'add')
(25, 4, 'mul', 5, 'sub', 8, 'mul', 2, 'sub')
real 0m0.118s
user 0m0.074s
sys 0m0.044s
Terry
Arnaud Delobelle
> 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?
I haven't had the time to look at your solution yet. I wanted to have
a go without being influenced.
> Arnaud: I haven't had time to play with your solution yet - how quick
> does it run?
I can't run test from here (work) but last night it seemed of the
order of a second on my 2GHz MacBook Pro (it was late and I was quite
tired so I didn't have the energy to time anything...). It depends if
you stop when you hit the first solution or you want to go through all
of them. I guess it will run quicker if I don't build a string
representation of each calculation.
You should run a test on your own machine though to make comparisons
meaningful.
> 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! ;-)
It's a laudable goal. We might get there :)
--
Arnaud
cokof...@gmail.com
Terry, your technique is efficient and pretty readable! All that could
be added now is a way to output the data in a more user-friendly
print. (it currently reminds me of Lisp operands done backwards :) )
Also perhaps the creation of a random generator for the 6 numbers and
the target :)
I do not remember if countdown enforced that it must be possible to
actually get the target, you could also get close to it. (I believe
you would get different points depending on this)
Will have to read up on how many large numbers you can have, as well
as small. Currently I think it is you can take up to 4 large numbers,
and up to 6 small numbers to a total of 6. (you must always have 6
numbers to work with)
Arnaud Delobelle
[...]
> Hi Arnaud.
Hi Terry
[...]
> 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.
Sorry I gave an incorrect example to illustrate my question last night
(I blame this on baby-induced sleep deprivation ;), so I'll have
another go:
Say I have 2, 3, 4, 100 and I want to make 406. AFAICS there is only
one way: (2*3)+(4*100), i.e. in postfix notation:
2 3 * 4 100 * +
It seemed to me that your function wouldn't generate that sort of
solution (as you always extend partialSolution by [num, op] making the
subsequence [mul, add] impossible). Am I wrong?
--
Arnaud
Terry Jones
cokofreedom> Terry, your technique is efficient and pretty readable! All
cokofreedom> that could be added now is a way to output the data in a more
cokofreedom> user-friendly print.
Yes, and a fix for the bug Arnaud just pointed out :-)
Below is code to print things more nicely for you.
Terry
from operator import *
from itertools import izip
def countdown(target, nums, numsAvail, value, partialSolution, solutions, ops=(add, mul, sub, div)):
if value == target or not any(numsAvail):
# 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[i] = False
used.add(num)
partialSolution.append(num)
countdown(target, nums, numsAvail, num, partialSolution, solutions, ops)
numsAvail[i] = True
partialSolution.pop()
else:
for op in ops:
for i, num in enumerate(nums):
if numsAvail[i]:
numsAvail[i] = False
moreAvail = any(numsAvail)
try:
lastNum, lastOp = partialSolution[-2:]
except ValueError:
lastNum, lastOp = partialSolution[-1], None
# Don't allow any of:
if not (
# Div: after mul, by 1, by 0, producing a fraction.
(op == div and (lastOp == 'mul' or num <= 1 or value % num != 0)) or
# If initial mul/add, canonicalize to 2nd operator biggest.
((op == mul or op == add) and lastOp is None and num > lastNum) or
# Don't allow add or sub of 0.
((op == add or op == sub) and num == 0) or
# Don't allow mult by 1.
(op == mul and num == 1) or
# Don't allow sub after add (allow add after sub).
(op == sub and lastOp == 'add') or
# 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[i] = True
op2sym = { 'add' : '+', 'sub' : '-', 'mul' : '*', 'div': '/', }
def pretty(s):
out = [str(s[0])]
lastOp = None
for value, op in izip(*(iter(s[1:]),) * 2):
if (op == 'mul' or op == 'div') and (lastOp == 'add' or lastOp == 'sub'):
out.insert(0, '(')
out.append(')')
out.append(op2sym[op])
out.append(str(value))
lastOp = op
return ''.join(out)
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),
((2, 4, 5, 8, 25), 758),
((2, 3, 4, 100), 406),
):
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', pretty(s)
Sample output:
8 solutions to: target 253, numbers = (100, 9, 7, 6, 3, 1)
(6*3-1)*9+100
(7*6+9)*3+100
(9-3)*7*6+1
(100-9-7)*3+1
((3+1)*6-7)*9+100
(7+1)*6*3+100+9
(7+6+3+1)*9+100
(100-7-6)*3-9+1
19 solutions to: target 234, numbers = (100, 9, 7, 6, 3, 1)
(6*3+7+1)*9
((7+1)*9+6)*3
(7*3-1+6)*9
(7*6*3-100)*9
((100-1)/3-7)*9
((100-1)*7+9)/3
(100*7*3+6)/9
(100-9)/7*6*3
(100-9-7-6)*3
((6+1)*100-7+9)/3
((6-9)*7-1+100)*3
(7*3-6)*9-1+100
7*6*3-1+100+9
(100-1)/3*7-6+9
((100-1)*7-9)/3+6
(100*7-6-1+9)/3
((100-7)/3-1+9)*6
((100-7)/3-6+1)*9
(100+9+7+1)/3*6
Terry Jones
Arnaud> Sorry I gave an incorrect example to illustrate my question last
Arnaud> night (I blame this on baby-induced sleep deprivation ;), so I'll
Arnaud> have another go:
Arnaud> Say I have 2, 3, 4, 100 and I want to make 406. AFAICS there is only
Arnaud> one way: (2*3)+(4*100), i.e. in postfix notation:
Arnaud> 2 3 * 4 100 * +
Arnaud> It seemed to me that your function wouldn't generate that sort of
Arnaud> solution (as you always extend partialSolution by [num, op] making
Arnaud> the subsequence [mul, add] impossible). Am I wrong?
No, you're right. I actually started out with a stack solution, and then
switched to something simpler (too simple). I'm going to redo it, but maybe
not right now...
Thanks!
Terry
Arnaud Delobelle
> Arnaud: I haven't had time to play with your solution yet - how quick
> does it run?
Ok I've done some quick timings, it's faster than I remembered it:
numbers = [2, 4, 5, 8, 25]
target = 758
Average time to find
(1) best solution (in terms of length of repr): 0.0418s
(2) first solution: 0.00421s
(2.2GHz MacBook Pro, done with the timeit module)
(1) involves working out all possible calculations with the 6 numbers.
--
Arnaud
Arnaud Delobelle
> Ever since I learnt to program I've always loved writing solvers for
> I'm wondering what the most elegant solution in Python is.
I've tried a completely different approach, that I imagine as
'folding'. I thought it would improve performance over my previous
effort but extremely limited and crude benchmarking seems to indicate
disappointingly comparable performance...
def ops(a, b):
"Generate all possible ops on two numbers with histories"
x, hx = a
y, hy = b
if x < y:
x, y, hx, hy = y, x, hy, hx
yield x + y, (hx, '+', hy)
if x != 1 and y != 1:
yield x * y, (hx, '*', hy)
if x != y:
yield x - y, (hx, '-', hy)
if not x % y and y != 1:
yield x / y, (hx, '/', hy)
def fold(nums, action, ops=ops):
"""Perform all possible ways of folding nums using ops.
Side-effect action triggered for every fold."""
nums = zip(nums, nums) # Attach a history to each number
def recfold():
for i in xrange(1, len(nums)):
a = nums.pop(i) # Take out a number;
for j in xrange(i):
b = nums[j] # choose another before it;
for x in ops(a, b): # combine them
nums[j] = x # into one;
action(x) # (with side-effect)
recfold() # then fold the shorter list.
nums[j] = b
nums.insert(i, a)
recfold()
def all_countdown(nums, target):
"Return all ways of reaching target with nums"
all = set()
def action(nh):
if nh[0] == target:
all.add(pretty(nh[1]))
fold(nums, action)
return all
def print_countdown(nums, target):
"Print all solutions"
print '\n'.join(all_countdown(nums, target))
class FoundSolution(Exception):
def __init__(self, sol):
self.sol = sol
def first_countdown(nums, target):
"Return one way of reaching target with nums"
def action(nh):
if nh[0] == target:
raise FoundSolution(nh[1])
try:
fold(nums, action)
except FoundSolution, fs:
return pretty(fs.sol)
# pretty helpers
def getop(h): return 'n' if isinstance(h, int) else h[1]
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, 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))
--
Arnaud
Terry Jones
> I've tried a completely different approach, that I imagine as 'folding'. I
> thought it would improve performance over my previous effort but extremely
> limited and crude benchmarking seems to indicate disappointingly comparable
> performance...
I wrote a stack-based version yesterday and it's also slow. It keeps track
of the stack computation and allows you to backtrack. I'll post it
sometime, but it's too slow for my liking and I need to put in some more
optimizations. I'm trying not to think about this problem.
What was wrong with the very fast(?) code you sent earlier?
Terry
dg.googl...@thesamovar.net
Great solutions both of you! Much nicer than mine. I particularly like
Arnaud's latest one based on folding because it's so neat and
conceptually simple. For me, it's the closest so far to my goal of the
most elegant solution.
So anyone got an answer to which set of numbers gives the most targets
from 100 onwards say (or from 0 onwards)? Is Python up to the task?
A thought on that last one. Two ways to improve speed. First of all,
you don't need to rerun from scratch for each target. Secondly, you
can try multiple different sets of numbers at the same time by passing
numpy arrays instead of single values (although you have to give up
the commutativity and division by zero optimisations).
Dan Goodman
Arnaud Delobelle
I thought it was a bit convoluted, wanted to try something I thought
had more potential. I think the problem with the second one is that I
repeat the same 'fold' too many times. I'll take a closer look at the
weekend.
--
Arnaud
Arnaud Delobelle
> Arnaud and Terry,
>
> Great solutions both of you! Much nicer than mine. I particularly like
> Arnaud's latest one based on folding because it's so neat and
> conceptually simple. For me, it's the closest so far to my goal of the
> most elegant solution.
Thanks! It's a great little problem to think of and it helps bring
more fun to this list. Sadly work takes over fun during the week, but
I will try to improve it at the weekend.
> So anyone got an answer to which set of numbers gives the most targets
> from 100 onwards say (or from 0 onwards)? Is Python up to the task?
I bet it is :)
> A thought on that last one. Two ways to improve speed. First of all,
> you don't need to rerun from scratch for each target
Yes, I've been doing this by writing an 'action' (see my code) that
takes note of all reached results.
> Secondly, you
> can try multiple different sets of numbers at the same time by passing
> numpy arrays instead of single values (although you have to give up
> the commutativity and division by zero optimisations).
Have to think about this.
--
Arnaud
Terry Jones
>>>>> "Arnaud" == Arnaud Delobelle <arn...@googlemail.com> writes:
>> What was wrong with the very fast(?) code you sent earlier?
Arnaud> I thought it was a bit convoluted, wanted to try something I
Arnaud> thought had more potential. I think the problem with the second
Arnaud> one is that I repeat the same 'fold' too many times.
and later:
Arnaud> Yes, I've been doing this by writing an 'action' (see my code) that
Arnaud> takes note of all reached results.
These are both comments about pruning, if I understand you. In the first
you weren't pruning enough and in the second you're planning to prune more.
I'm giving up thinking about this problem because I've realized that the
pruning solution is fundamentally subjective. I.e., whether or not you
consider two solutions to be the "same" depends on how hard you're willing
to think about them (and argue that they're the same), or how smart you
are.
I have a new version that does some things nicely, but in trying to do
efficient pruning, I've realized that you can't satisfy everyone.
Some examples for the problem with target 253, numbers = 100, 9, 7, 6, 3, 1
Firstly, there are nice solutions that go way negative, like:
1 7 6 3 9 sub mul mul sub or 1 - 7 * 6 * (3 - 9)
Here's a pruning example. Are these the "same"?
1 3 7 100 9 sub sub mul sub or 1 - 3 * (7 - 100 - 9)
1 3 7 9 100 sub add mul sub or 1 - 3 * (7 - 9 - 100)
I think many people would argue that that's really the "same" and that one
of the two should not appear in the output. The same goes for your earlier
example for 406. It's 4 * 100 + 2 x 3, and 2 x 3 + 100 * 4, and so on.
My latest program does all these prunings.
But you can argue that you should push even further into eliminating things
that are the same. You could probably make a pretty fast program that
stores globally all the states it has passed through (what's on the stack,
what numbers are yet to be used, what's the proposed op) and never does
them again. But if you push that, you'll wind up saying that any two
solutions that look like this:
....... 1 add
e.g.
6 9 3 sub mul 7 mul 1 add or 6 * (9 - 3) * 7 + 1
7 6 mul 9 3 sub mul 1 add or 7 * 6 * (9 - 3) + 1
are the same. And if we go that far, then a really smart person might argue
that this
100 7 sub 9 sub 3 mul 1 add or (100 - 7 - 9) * 3 + 1
is also the "same" (because all these solutions get to 252 and then add 1,
so they're clearly the "same", right?):
Once you've gone that far, you might even argue that on a particular
problem of a particular difficulty (subjectively matching what your brain
is capable of) all solutions that start out by pushing 1 onto the stack are
actually the "same".
And if you're even smarter than that, you might just look at any problem
and say "Hey, that's easy! The answer is X" or "There's clearly no
solution" because you'd immediately just see the answer (if any) and that
all others were just obvious variants.
E.g., if I said to you: "make 20 out of (20, 10, 10, 3)", I imagine you
could immediately list the answer(s?)
20 = 20
20 = 10 + 10
20 = 20 + 10 - 10
20 = 20 - 10 + 10
etc., and explain that those are all really the same. You'd prune on the
spot, and consider it obvious that the pruning was fully justified.
But my 6-year-old son couldn't tell you that, and I doubt he'd agree with
your prunings.
OK, enough examples. I'm just trying to illustrate that the (difficult)
problem of efficiently pruning doesn't have an objective solution. Pruning
is subjective. OTOH, the decision problem "does this puzzle have any
solutions or not (and if so, produce one)" does.
That's why I'm going to stop working on this. My stack solution code is
fun, but working on making it prune better is a black hole. And to make
matters worse, the more I push it (i.e., the more advanced its prunings
get), the less likely (some) people are to agree that its output is still
correct. You can't win.
If anyone wants the stack simulation code, send me an email.
Terry
Arnaud Delobelle
> Hi Arnaud and Dan
Hi Terry
> >>>>> "Arnaud" == Arnaud Delobelle <arno...@googlemail.com> writes:
> >> What was wrong with the very fast(?) code you sent earlier?
>
> Arnaud> I thought it was a bit convoluted, wanted to try something I
> Arnaud> thought had more potential. I think the problem with the second
> Arnaud> one is that I repeat the same 'fold' too many times.
>
> and later:
>
> Arnaud> Yes, I've been doing this by writing an 'action' (see my code) that
> Arnaud> takes note of all reached results.
>
> These are both comments about pruning, if I understand you. In the first
> you weren't pruning enough and in the second you're planning to prune more.
Yes I think the first one is about pruning, I couldn't think of the
english word.
> I'm giving up thinking about this problem because I've realized that the
> pruning solution is fundamentally subjective. I.e., whether or not you
> consider two solutions to be the "same" depends on how hard you're willing
> to think about them (and argue that they're the same), or how smart you
> are.
FWIW, I have a clear idea of what the space of solutions is, and which
solutions I consider to be equivalent. I'll explain it below. I'm
not saying it's the right model, but it's the one within which I'm
thinking.
> I have a new version that does some things nicely, but in trying to do
> efficient pruning, I've realized that you can't satisfy everyone.
>
> Some examples for the problem with target 253, numbers = 100, 9, 7, 6, 3, 1
>
> Firstly, there are nice solutions that go way negative, like:
>
> 1 7 6 3 9 sub mul mul sub or 1 - 7 * 6 * (3 - 9)
I think it's best to forbid negatives. Solutions always be written
without any negative intermediate answer. E.g. 1-7*6*(3-9) can be
done as 1+7*6*(9-3).
>
> Here's a pruning example. Are these the "same"?
>
> 1 3 7 100 9 sub sub mul sub or 1 - 3 * (7 - 100 - 9)
rather 1 - 3*(7 - (100 - 9))
> 1 3 7 9 100 sub add mul sub or 1 - 3 * (7 - 9 - 100)
rather 1 - 3*(7 + (9 - 100))
Not allowing negatives means these are
3*(100 - 9 - 7) + 1
or 3*(100 - (9 + 7)) + 1
or 3*(100 - 7 - 9) + 1
I don't consider these to be equivalent, because their equivalence
depends on understanding the meaning of subtraction and addition.
(I've also applied the 'big then small' rule explained below)
>
> I think many people would argue that that's really the "same" and that one
> of the two should not appear in the output. The same goes for your earlier
> example for 406. It's 4 * 100 + 2 x 3, and 2 x 3 + 100 * 4, and so on.
There is a simple rule that goes a long way: "big then small", i.e.
only allow a <op> b when a > b.
So the above is canonically written as 100*4 + 2*3.
>
> My latest program does all these prunings.
>
> But you can argue that you should push even further into eliminating things
> that are the same. You could probably make a pretty fast program that
> stores globally all the states it has passed through (what's on the stack,
> what numbers are yet to be used, what's the proposed op) and never does
> them again. But if you push that, you'll wind up saying that any two
> solutions that look like this:
>
> ....... 1 add
>
> e.g.
>
> 6 9 3 sub mul 7 mul 1 add or 6 * (9 - 3) * 7 + 1
> 7 6 mul 9 3 sub mul 1 add or 7 * 6 * (9 - 3) + 1
>
> are the same.
I honestly think this is outside the scope of this problem, which must
remain simple. I'm not trying to convince you of anything, but I'll
just explain briefly what solutions I don't want to repeat.
I see a solution as a full ordered binary tree. Each node has a
weight (which is the result of the calculation it represents) and the
left child of a node has to be at least as heavy as the right child.
Each parent node can be labeled + - * or /.
If a node x has two children y and z and is labeled <op>, let me write
x = (y <op> z)
so 6 9 3 sub mul 7 mul 1 add -> (((6 * (9 - 3)) * 7) + 1)
and 7 6 mul 9 3 sub mul 1 add -> (((7 * 6) * (9 - 3)) + 1)
are two distinct solutions according to my criterion.
But
9 3 sub 6 mul 7 mul 1 add -> ((((9 - 3) * 6) * 7) + 1)
is not a solution because 9-3 < 6
To be perfectly honest (and expose my approach a little to your
argument) I added a three additional rules:
* Don't allow x - x
* Don't allow x * 1
* Don't allow x / 1
My aim was find and efficient way to generate all solutions exactly
once if there is no repeat in the list of starting numbers. This is a
clearly defined problem and I wanted to find a nice way of solving
it. I realised that the folding method was redundant in that respect
and this is what I wanted to fix (I have a fix, I think, but the
'proof' of it is only in my head and might be flawed).
If there are repeats in the list of starting numbers, I don't worry
about repeating solutions.
> If anyone wants the stack simulation code, send me an email.
I'd like to see it :)
--
Arnaud
Terry Jones
Arnaud> FWIW, I have a clear idea of what the space of solutions is, and
Arnaud> which solutions I consider to be equivalent. I'll explain it
Arnaud> below. I'm not saying it's the right model, but it's the one
Arnaud> within which I'm thinking.
OK. This reinforces why I'm not going to work on it anymore, the solution
is subjective (once you start pruning).
Arnaud> I think it's best to forbid negatives. Solutions always be written
Arnaud> without any negative intermediate answer. E.g. 1-7*6*(3-9) can be
Arnaud> done as 1+7*6*(9-3).
That's a good optimization, and I think it's easy to prove that it's
correct supposing the target is positive and the inputs are all positive.
If you consider the intermediate results in a solution, then if you ever go
negative it's because of an operation X (must be a sub or a div) and when
you next become positive it's due to an operation Y (must be add or
mul). So you can "reflect" that part of the computation by doing the
opposite operations for that formerly sub-zero intermediate sequence.
Arnaud> I don't consider these to be equivalent, because their equivalence
Arnaud> depends on understanding the meaning of subtraction and addition.
Ha - you can't have it both ways Arnaud! You don't want the computation to
go negative... doesn't that (and my "proof") have something to do with the
inverse nature of add and sub? :-)
Arnaud> (I've also applied the 'big then small' rule explained below)
And now you're taking advantage of your knowledge of > and < ...
My original code did this big then small canonicalization too.
That's my point exactly - pruning depends on who you are, how smart you
are, how hard you work, your personal taste, etc.
Arnaud> I see a solution as a full ordered binary tree. Each node has a
Arnaud> weight (which is the result of the calculation it represents) and
Arnaud> the left child of a node has to be at least as heavy as the right
Arnaud> child. Each parent node can be labeled + - * or /. If a node x
Arnaud> has two children y and z and is labeled <op>, let me write x = (y
Arnaud> <op> z)
Where does the sequence of numbers enter into this? You have a tree of
operations - is it acting on a stack? What's on the stack?
It sounds similar to what I've done. I walk up and down the tree, keeping
the stack and the stack history, doing operations (including pushing onto
the stack) and undoing them.
There are several more prunings I could be doing, but these require looking
further back in the stack. E.g., I force div before mul and sub before
add, and I also apply the "big then small" rule to the intermediate stack
results if there are series of identical operations (not just to a single
operation). E.g. X / Y / Z can be re-ordered so that Y >= Z, and A + B + C
can be reordered so A >= B >= C. Doing it on the stack results is different
(but similar) to doing it on the raw input numbers.
There are lots of other little and more complex things you can do to prune.
You want to prune early, of course. The stack model of computation make
this hard because it's always legitimate to push all the numbers onto the
stack, by which point you're already deep in the tree.
And this approach only lets you do local pruning - i.e., that affect the
branch of the tree you're on. If you stored the state of the stack, the
operation you're about to do, and the (sorted) numbers remaining to be
input, then if you ever hit that configuration elsewhere in the massive
tree, you could know that you'd been that way before. But are you justified
in pruning at that point? The identical state of the computation could have
been arrived at via a very different method.
But that's where the big speed-up in this approach is.
At this realization I decided to give up :-)
Arnaud> To be perfectly honest (and expose my approach a little to your
Arnaud> argument) I added a three additional rules:
Arnaud> * Don't allow x - x
Arnaud> * Don't allow x * 1
Arnaud> * Don't allow x / 1
Yes, I do these too, including not allowing a zero intermediate (which is a
useless calculation that simply could not have been done - see, I have deep
knowledge of zero!).
Arnaud> If there are repeats in the list of starting numbers, I don't worry
Arnaud> about repeating solutions.
I handle most of those cases, but I didn't push all the way. With target 32
and input 8, 8, 8, 8 my code still gives 2 answers:
8 8 add 8 8 add add
8 8 add 8 add 8 add
>> If anyone wants the stack simulation code, send me an email.
Arnaud> I'd like to see it :)
I'll send it.
Terry
dg.googl...@thesamovar.net
parallelise the problem, and there were some difficulties with it.
Firstly, the pruning makes a really big difference to the speed, and
you don't get that if you're trying to parallelise the problem because
what is an equivalent calculation for one set of numbers is obviously
not for another set. I think this problem disappears when you consider
very large sets of numbers though (where the cost of doing equivalent
computations vanishes in comparison to the alternative cost of
starting up the whole recursive computation from scratch many times).
The second problem is that you can't weed out division by zero and
intermediate fractions. I haven't looked at the internals of how NumPy
deals with these though, so this might be fixable or it might not.
For my part, I'd consider the following equivalences to be right for
defining equivalent expressions (where here a, b and c are any
subexpression, and 1 and 0 means any subexpression that evaluates to 1
and 0).
Commutativity:
a*b <-> b*a
a+b <-> b+a
Associativity:
(a+b)+c <-> a+(b+c)
(a+b)-c <-> a+(b-c)
(a-b)+c <-> a-(b-c)
(a-b)-c <-> a-(b+c)
(a*b)*c <-> a*(b*c)
(a*b)/c <-> a*(b/c)
(a/b)*c <-> a/(b/c)
(a/b)/c <-> a/(b*c)
Units (1 is multiplicative unit, 0 is additive unit):
a*1 <-> a
a/1 <-> a
a+0 <-> a
a-0 <-> a
Substitution (swapping equal starting numbers is equivalent):
expr(a,b,c,...,z) <-> expr(s(a,b,c,...,z)) where a,b,c,...,z are the
original numbers given and s is a permutation of (a,b,c...,z) so that
(a,b,c,...z) evaluates to the same thing as s(a,b,c,...,z)
or equivalently, expr1 <-> expr2 if str(expr1)==str(expr2)
Then, any two expressions which can be transformed into one another by
the equivalences above are equivalent. Commutativity and units can be
easily implemented as you go and most of the programs suggested so far
do this, by for example only allowing a*b or a+b if a>=b, and not
allowing a*1 or 1*a, etc. Substitution can be implemented by just
taking set(map(str,expressions)) at the end. The associativity ones
are a little more tricky to implement, but Arnaud's idea of the fully
ordered binary tree seems to do it. Another way of saying it is that
any subexpression consisting only of + and - operations should be
reduced to a+b+c+...-z-y-x-.... where a>b>c>... and z>y>x>... (and
similarly for an expression involving only * and /).
Terry, I'd also be interested in a copy of your stack simulation code,
btw.
Arnaud Delobelle
> >>>>> "Arnaud" == Arnaud Delobelle <arno...@googlemail.com> writes:
>
> Arnaud> FWIW, I have a clear idea of what the space of solutions is, and
> Arnaud> which solutions I consider to be equivalent. I'll explain it
> Arnaud> below. I'm not saying it's the right model, but it's the one
> Arnaud> within which I'm thinking.
>
> OK. This reinforces why I'm not going to work on it anymore, the solution
> is subjective (once you start pruning).
>
> Arnaud> I think it's best to forbid negatives. Solutions always be written
> Arnaud> without any negative intermediate answer. E.g. 1-7*6*(3-9) can be
> Arnaud> done as 1+7*6*(9-3).
>
> That's a good optimization, and I think it's easy to prove that it's
> correct supposing the target is positive and the inputs are all positive.
>
> If you consider the intermediate results in a solution, then if you ever go
> negative it's because of an operation X (must be a sub or a div) and when
> you next become positive it's due to an operation Y (must be add or
> mul). So you can "reflect" that part of the computation by doing the
> opposite operations for that formerly sub-zero intermediate sequence.
>
> Arnaud> I don't consider these to be equivalent, because their equivalence
> Arnaud> depends on understanding the meaning of subtraction and addition.
>
> Ha - you can't have it both ways Arnaud! You don't want the computation to
> go negative... doesn't that (and my "proof") have something to do with the
> inverse nature of add and sub? :-)
I think I can have it both ways, here's why: the "big then small" and
"no negatives" rules are applied indiscriminately by the algorithm:
it doesn't need to know about the history of operations in order to
make a decision depending on their nature. OTOH, identifying (a + b)
- c and a + (b - c) for example, requires inspection of the stack/tree/
calculation history. It is an *informed* decision made by the
algorithm
> Arnaud> (I've also applied the 'big then small' rule explained below)
>
> And now you're taking advantage of your knowledge of > and < ...
Again, *I* have the knowledge, the algorithm does it
indiscriminately...
[...]
> Arnaud> To be perfectly honest (and expose my approach a little to your
> Arnaud> argument) I added a three additional rules:
>
> Arnaud> * Don't allow x - x
> Arnaud> * Don't allow x * 1
> Arnaud> * Don't allow x / 1
>
> Yes, I do these too, including not allowing a zero intermediate (which is a
> useless calculation that simply could not have been done - see, I have deep
> knowledge of zero!).
Note that disallowing 0 and disallowing x - x are equivalent, as the
only way to get your first 0 is by doing x - x.
Thanks for the discussion, it's made me realise more clearly what I
was doing.
--
Arnaud
Terry Jones
>> go negative... doesn't that (and my "proof") have something to do with the
>> inverse nature of add and sub? :-)
Arnaud> I think I can have it both ways, here's why: the "big then small"
Arnaud> and "no negatives" rules are applied indiscriminately by the
Arnaud> algorithm: it doesn't need to know about the history of operations
Arnaud> in order to make a decision depending on their nature. OTOH,
Arnaud> identifying (a + b) - c and a + (b - c) for example, requires
Arnaud> inspection of the stack/tree/ calculation history. It is an
Arnaud> *informed* decision made by the algorithm
But this is having it both ways too :-)
The reason the algorithm can do it indiscriminately is because *you* know
that it always applies, and *you* figure out and implement the algorithm
that way. The algorithm doesn't have a mind of its own, after all.
BTW, there are some very important issues here. One is about representation
(thinking about representation is one of my pet vices). When you try to
solve some real-world problem with a computer, you must choose a
representation. What many people seem to fail to recognize is that in so
doing you've already begun to solve the problem. If you pick a better
representation, your algorithm can potentially be much dumber and still be
hugely faster than a brilliant algorithm on a terrible representation.
In maintaining an A > B invariant in operations A + B and A * B, you're
using insight into the problem to influence representation. With that
better representation, your algorithm doesn't have to do so much work.
I wrote some more about this a while ago at
Arnaud> Note that disallowing 0 and disallowing x - x are equivalent, as
Arnaud> the only way to get your first 0 is by doing x - x.
That depends. I allow negative numbers in the input, and also 0 (I just
don't let you use it :-))
Arnaud> Thanks for the discussion, it's made me realise more clearly what I
Arnaud> was doing.
Me too! Thanks.
Terry
Arnaud Delobelle
* 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)
david....@blueyonder.co.uk
months ago. I tried a few optimizations and my experience was that
with only 6 seeds, a hash table was very effective. So effective, in
fact, that it made all other optimizations more or less pointless.
Code below. Arguments are seeds first, then targets. Like this:
C:\utils>countdown.py 7 8 50 8 1 3 923
made target!
50 * 8 = 400
400 - 1 = 399
399 / 3 = 133
133 * 7 = 931
931 - 8 = 923
Took 0.421 seconds
from time import time
from bisect import insort
from sys import argv
#------------------------------------------------------------------------------
# Hash table is a global variable
#------------------------------------------------------------------------------
global hash_table
#------------------------------------------------------------------------------
# countdown.py
#
# Python script to solve the Countdown numbers game
#
# Remarks on optimization:
#
# - Without the hash table, the following all proved beneficial:
# - Keep a list of numbers used so far, and never create a number
that
# you've already used
# - Make sure only to return unique pairs from the generate_pairs
function
# - Don't ever perform two consecutive substractions
# - (Don't ever perform two consecutive divisions would also be
valid,
# though it's not something that happens a lot so the benefit is
small)
#
# - These tricks work by avoiding performing the same search more
than once
#
# - With only six seeds, it's possible to implement a perfect hash
table that
# remembers every list that we try to solve (and indeed this is
what the
# implementation here does)
#
# - With that hash table, the optimizations above become largely
redundant, so
# for the sake of simplicity I've removed them
#
# - Solving for larger numbers of seeds would require a smarter
approach, as
# it would soon become infeasible to maintain a complete hash
table. Then
# the tricks above might be useful again.
#
#------------------------------------------------------------------------------
#------------------------------------------------------------------------------
# Returns all useful combinations of two numbers, and a string
representing
# the operation used to get there.
#------------------------------------------------------------------------------
def generate_combinations(higher_number, lower_number):
#--------------------------------------------------------------------------
# Useful operations are:
# - addition (always)
# - subtraction (of the lower number from the higher number, so
long as
# they are not equal)
# - multiplication (so long as not multiplying by one)
# - division (if it's exact, and not by one)
#--------------------------------------------------------------------------
yield "+", higher_number + lower_number
if (higher_number != lower_number):
yield "-", higher_number - lower_number
if (lower_number != 1):
yield "*", higher_number * lower_number
if ((higher_number % lower_number) == 0):
yield "/", higher_number / lower_number
#------------------------------------------------------------------------------
# Returns all pairs from a list of seeds.
#
# Pairs always have the first number lower than or equal to the second
number,
# provided that the list is ordered on entry (as it should be).
#------------------------------------------------------------------------------
def generate_pairs(seeds):
for ii in xrange(len(seeds)):
for higher_num in seeds[ii+1:]:
yield seeds[ii], higher_num
#------------------------------------------------------------------------------
# Solves a seed list. Takes pairs, combines them, and recursively
calls
# solve_list again with the new shorter list.
#
# Seeds should be sorted on entry.
#------------------------------------------------------------------------------
def solve_list(seeds, target, depth, solution_so_far):
#--------------------------------------------------------------------------
# Loop through possible pairs.
#--------------------------------------------------------------------------
for lower_num, higher_num in generate_pairs(seeds):
#----------------------------------------------------------------------
# Make a copy of the list, and remove this pair.
#
# Taking a copy appears to be quicker than using the original
list and
# then reinstating the chosen pair later.
#----------------------------------------------------------------------
new_seeds = seeds[:]
new_seeds.remove(lower_num)
new_seeds.remove(higher_num)
#----------------------------------------------------------------------
# Try out all possible combinations of our pair.
#----------------------------------------------------------------------
for operation, combination in
generate_combinations(higher_num,
lower_num):
#------------------------------------------------------------------
# If we hit our target, we're happy.
#
# Else if the list has gotten too short already, move on.
#
# Else make a new, shorter, list containing our new value.
#
# If we've already tried to solve the new list, there's no
point in
# trying again.
#
# Else try to solve the shorter list.
#------------------------------------------------------------------
if combination == target:
print "made target!"
print "%s%d %s %d = %d\n" % (solution_so_far,
higher_num,
operation,
lower_num,
combination)
return(0)
elif (depth > 0):
insort(new_seeds, combination)
seeds_tuple = tuple(new_seeds)
if (seeds_tuple in hash_table):
pass
else:
hash_table[seeds_tuple] = 1
new_soln_so_far = ("%s%d %s %d = %d\n" %
(solution_so_far,
higher_num,
operation,
lower_num,
combination))
if (solve_list(new_seeds,
target,
depth - 1,
new_soln_so_far) == 0):
#------------------------------------------------------
# Success!
#------------------------------------------------------
return(0)
#--------------------------------------------------------------
# Remove the value that we made out of our number
pair, in
# preparation for the next try.
#--------------------------------------------------------------
new_seeds.remove(combination)
#--------------------------------------------------------------------------
# Didn't solve it.
#--------------------------------------------------------------------------
return(1)
#------------------------------------------------------------------------------
# OK, let's go. Get the puzzle, and solve it. The last argument is
the target
# and the others are the seeds.
#------------------------------------------------------------------------------
original_seeds = map(int, argv[1:-1])
target = int(argv[-1])
start_time = time()
failed = 1;
if target in original_seeds:
print "Target is amongst seeds!"
else:
original_seeds.sort()
#--------------------------------------------------------------------------
# First look for one-step solutions, then for two-step solutions,
etc.
# That way we always get a shortest solution first.
#--------------------------------------------------------------------------
for depth in xrange(len(original_seeds)):
hash_table = {}
failed = solve_list(original_seeds, target, depth, "")
if (failed == 0):
break
if (failed != 0):
print "No solution!"
print "Took %.3f seconds" % (time() - start_time)
david....@blueyonder.co.uk
reformatted listing.
from time import time
from bisect import insort
from sys import argv
#---------------------------------------------------------------------
# Hash table is a global variable
#---------------------------------------------------------------------
global hash_table
#---------------------------------------------------------------------
# countdown.py
#
# Python script to solve the Countdown numbers game
#
# Remarks on optimization:
#
# - Without the hash table, the following all proved beneficial:
# - Keep a list of numbers used so far, and never create a number
# that you've already used
# - Make sure only to return unique pairs from the generate_pairs
# function
# - Don't ever perform two consecutive substractions
# - (Don't ever perform two consecutive divisions would also be
# valid, though it's not something that happens a lot so the
# benefit is small)
#
# - These tricks work by avoiding performing the same search more
# than once
#
# - With only six seeds, it's possible to implement a perfect hash
# table that remembers every list that we try to solve (and indeed
# this is what the implementation here does)
#
# - With that hash table, the optimizations above become largely
# redundant, so for the sake of simplicity I've removed them
#
# - Solving for larger numbers of seeds would require a smarter
# approach, as it would soon become infeasible to maintain a
# complete hash table. Then the tricks above might be useful
# again.
#
#---------------------------------------------------------------------
#---------------------------------------------------------------------
# Returns all useful combinations of two numbers, and a string
# representing the operation used to get there.
#---------------------------------------------------------------------
def generate_combinations(higher_number, lower_number):
#-----------------------------------------------------------------
# Useful operations are:
# - addition (always)
# - subtraction (of the lower number from the higher number, so
# long as they are not equal)
# - multiplication (so long as not multiplying by one)
# - division (if it's exact, and not by one)
#-----------------------------------------------------------------
yield "+", higher_number + lower_number
if (higher_number != lower_number):
yield "-", higher_number - lower_number
if (lower_number != 1):
yield "*", higher_number * lower_number
if ((higher_number % lower_number) == 0):
yield "/", higher_number / lower_number
#---------------------------------------------------------------------
# Returns all pairs from a list of seeds.
#
# Pairs always have the first number lower than or equal to the second
# number, provided that the list is ordered on entry (as it should
# be).
#---------------------------------------------------------------------
def generate_pairs(seeds):
for ii in xrange(len(seeds)):
for higher_num in seeds[ii+1:]:
yield seeds[ii], higher_num
#---------------------------------------------------------------------
# Solves a seed list. Takes pairs, combines them, and recursively
# calls solve_list again with the new shorter list.
#
# Seeds should be sorted on entry.
#---------------------------------------------------------------------
def solve_list(seeds, target, depth, solution_so_far):
#-----------------------------------------------------------------
# Loop through possible pairs.
#-----------------------------------------------------------------
for lower_num, higher_num in generate_pairs(seeds):
#-------------------------------------------------------------
# Make a copy of the list, and remove this pair.
#
# Taking a copy appears to be quicker than using the original
# list and then reinstating the chosen pair later.
#-------------------------------------------------------------
new_seeds = seeds[:]
new_seeds.remove(lower_num)
new_seeds.remove(higher_num)
#-------------------------------------------------------------
# Try out all possible combinations of our pair.
#-------------------------------------------------------------
for operation, combination in generate_combinations(
higher_num,
lower_num):
#---------------------------------------------------------
# If we hit our target, we're happy.
#
# Else if the list has gotten too short already, move on.
#
# Else make a new, shorter, list containing our new value.
#
# If we've already tried to solve the new list, there's no
# point in trying again.
#
# Else try to solve the shorter list.
#----------------------------------------------------------
# Success!
#---------------------------------------------
return(0)
#-----------------------------------------------------
# Remove the value that we made out of our number
# pair, in preparation for the next try.
#-----------------------------------------------------
new_seeds.remove(combination)
#-----------------------------------------------------------------
# Didn't solve it.
#-----------------------------------------------------------------
return(1)
#---------------------------------------------------------------------
# OK, let's go. Get the puzzle, and solve it. The last argument is
# the target and the others are the seeds.
#---------------------------------------------------------------------
original_seeds = map(int, argv[1:-1])
target = int(argv[-1])
start_time = time()
failed = 1;
if target in original_seeds:
print "Target is amongst seeds!"
else:
original_seeds.sort()
#-----------------------------------------------------------------
# First look for one-step solutions, then for two-step solutions,
# etc. That way we always get a shortest solution first.
#-----------------------------------------------------------------
Arnaud Delobelle
> I also had a go at this problem for a bit of python practice, about 6
> months ago. I tried a few optimizations and my experience was that
> with only 6 seeds, a hash table was very effective. So effective, in
> fact, that it made all other optimizations more or less pointless.
My strategy was to walk through each solution "only once" (for a
certain definition of "only once :), thus I was hoping not to need a
hashtable.
> Code below. Arguments are seeds first, then targets. Like this:
>
> C:\utils>countdown.py 7 8 50 8 1 3 923
> made target!
> 50 * 8 = 400
> 400 - 1 = 399
> 399 / 3 = 133
> 133 * 7 = 931
> 931 - 8 = 923
>
> Took 0.421 seconds
Did you pick these numbers at random? Interestingly, the solution is
unique:
[0.27424502372741699]
>>> list(test(nums=[7, 8, 50, 8, 1, 3], target=923, method=divide, countdown=print_countdown)) (50*8-1)*7/3-8
(50*8-1)*7/3-8
[0.2748568058013916]
To find just one solution:
>>> list(test(nums=[7, 8, 50, 8, 1, 3], target=923, countdown=first_countdown)) [0.11860203742980957]
(list returned contains time taken to reach solution. By comparison
your code takes 0.264s on my machine. Mine is faster on this example,
but one example is not representative!)
--
Arnaud
david....@blueyonder.co.uk
> My strategy was to walk through each solution "only once" (for a
> certain definition of "only once :), thus I was hoping not to need a
> hashtable.
Yes, that seems like it should be preferable (and indeed necessary for
a more general problem with larger numbers of seeds). But I wasn't
smart enough to figure out how to do it ;-)
> Did you pick these numbers at random? Interestingly, the solution is
> unique:
Not at random - this particular puzzle came out of the first post in
this thread.
> Mine is faster on this example, but one example is not representative!
If you've found an efficient way to walk through the possible
solutions only once, then
- I expect that yours will be faster
- and well done!
I guess I should try to understand your code...
> --
> Arnaud
Arnaud Delobelle
> If you've found an efficient way to walk through the possible
> solutions only once
As discussed earlier in this thread, the definition of 'only once' is
not as clear cut as one would first think (see Terry's thoughts on
this).
--
Arnaud
Arnaud Delobelle
Oops I sent too quickly...
> If you've found an efficient way to walk through the possible
> solutions only once, then
> - I expect that yours will be faster
> - and well done!
>
> I guess I should try to understand your code...
My code is quite naive and I suspect that combining your caching and
the tree pruning discussed in this thread would yield faster results.
Not sure if I'll have time to try this though...
--
Arnaud
wolfram....@googlemail.com
> So anyone got an answer to which set of numbers gives the most targets
> from 100 onwards say (or from 0 onwards)? IsPythonupto the task?
It's (5, 8, 9, 50, 75, 100): 47561 targets altogether (including
negative ones), 25814 targets >= 100.
(BTW, 1226 sets of numbers give all 900 3-digit targets, but the above
one doesn't; 954 and 981 are missing.)
The following (mostly) straightforward program needed about 30 min for
the calculation. I tried to keep all (intermediate) results in a dict
(which turned out later to need too much memory). I wanted to use the
same dict for memoization. So I let the dict fill itself on access.
The disadvantage of this method is that the function needs to know
that it's being memoized. The advantage is that it's easier (I think)
to manipulate/control the dict.
class AutoFillDict(dict):
""" Values for missing keys are computed on-the-fly """
def __init__(self, func, *args, **kwargs):
self.func = func
super(AutoFillDict, self).__init__(*args, **kwargs)
def __missing__(self, key):
self[key] = self.func(self, key)
return self[key]
def subs_k(dic, (nums, k)):
""" Return k-subsets of tuple nums, using dic as cache """
if k == 1:
return [(i,) for i in nums]
if k == len(nums):
return [nums]
a = nums[:1]
b = nums[1:]
return [a + i for i in dic[b, k-1]] + dic[b, k]
def subs_and_complements(dic, nums):
""" Return subsets and complements of tuple nums, using dic as
cache """
if not nums:
return set([((), ())])
a = nums[:1]
b = nums[1:]
res = set([(s, a + c) for s, c in dic[b]])
res.update([(a + s, c) for s, c in dic[b]])
return res
subs_and_comps = AutoFillDict(subs_and_complements)
def countdown(dic, nums, sac_dict=subs_and_comps):
"""Return all possible goals for input nums, using dic as cache
All numbers in nums must be used.
"""
if len(nums) == 1:
return nums
ret = set()
for s, c in sac_dict[nums]:
if s and c:
xs = dic[s]
ys = dic[c]
ret.update([x + y for x in xs for y in ys])
ret.update([x - y for x in xs for y in ys])
ret.update([x * y for x in xs for y in ys])
ret.update([x // y for x in xs for y in ys if y != 0 and x
% y == 0])
return ret
def print_max(results):
max_goals = max(results.values())
max_nums = [n for (n, g) in results.items() if g == max_goals]
max_nums.sort()
print "Maximal number of reachable goals: %d" % max_goals
print "Number of tuples: %d" % len(max_nums)
for n in max_nums:
print n
if __name__ == "__main__":
all_nums = range(1, 11)*2 + [25, 50, 75, 100]
all_nums = tuple(sorted(all_nums))
subsets_k = AutoFillDict(subs_k)
d = AutoFillDict(countdown)
results = {}
results100 = {}
for i, nums in enumerate(sorted(set(subsets_k[all_nums, 6]))):
# result is the union of reachable goals for all subsets
result = set()
for s, c in subs_and_comps[nums]:
result.update(d[s])
results[nums] = len(result)
results100[nums] = len([x for x in result if x >= 100])
# Prevent MemoryError
if i % 200 == 0:
d.clear()
print "Goals: all integers"
print_max(results)
print
print "Goals: integers >= 100"
print_max(results100)
--
Wolfram