Terry Jones
1/21/2008 3:20:00 AM
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[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')