Just for fun: Countdown numbers game solver

[Arnaud Delobelle]

On Jan 20, 5:41 pm, dg.google.gro... at thesamovar.net wrote:
> 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.

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