>>>>> "cokofreedom" == cokofreedom <[EMAIL PROTECTED]> writes:
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
--
http://mail.python.org/mailman/listinfo/python-list
