Just for fun: Countdown numbers game solver

[Terry Jones]

>>>>> "cokofreedom" == cokofreedom  <cokofreedom at gmail.com> 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