Just for fun: Countdown numbers game solver

[Terry Jones]

>>>>> "Arnaud" == Arnaud Delobelle <arnodel at googlemail.com> writes:
Arnaud> In countdown you are not required to use all numbers to reach the
Arnaud> target.  This means you are missing solutions, e.g.  (1, 3, 6,
Arnaud> 'mul', 'add', 7 , 'add', 9, 'mul')

Hi Arnaud.

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

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

Code and output below.

Terry


from operator import *

def countdown(target, nums, numsAvail, value, partialSolution, solutions, ops=(add, mul, sub, div)):
    if value == target or not any(numsAvail):
        # Ran out of available numbers. Add the solution, if we're right.
        if value == target:
            solutions.add(tuple(partialSolution))
    elif value is None:
        # Use each distinct number as a starting value.
        used = set()
        for i, num in enumerate(nums):
            if num not in used:
                numsAvail[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 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