Just for fun: Countdown numbers game solver

[dg.google.groups at thesamovar.net]

Decided I may as well post my other solution while I'm at it. The neat
trick here is redefining the add, mul, etc. functions so that they
raise exceptions for example if x>y then add(x,y) raises an exception
which is handled by the search algorithm to mean don't continue that
computation - this stops you from having to evaluate x+y AND y+x, etc.

sub = lambda x,y:x-y
def add(x,y):
    if x<=y: return x+y
    raise ValueError
def mul(x,y):
    if x<=y or x==1 or y==1: return x*y
    raise ValueError
def div(x,y):
    if not y or x%y or y==1:
        raise ValueError
    return x/y

add.disp = '+'
mul.disp = '*'
sub.disp = '-'
div.disp = '/'

standard_ops = [ add, sub, mul, div ]

def strexpression(e):
    if len(e)==3:
        return '('+strexpression(e[1])+e[0].disp+strexpression(e[2])
+')'
    elif len(e)==1:
        return str(e[0])

# I don't like this function, it's nice and short but is it clear
# what it's doing just from looking at it?
def expressions(sources,ops=standard_ops,minremsources=0):
    for i in range(len(sources)):
        yield ([sources[i]],sources[:i]+sources[i+1:],sources[i])
    if len(sources)>=2+minremsources:
        for e1, rs1, v1 in expressions(sources,ops,minremsources+1):
            for e2, rs2, v2 in expressions(rs1,ops,minremsources):
                for o in ops:
                    try: yield ([o,e1,e2],rs2,o(v1,v2))
                    except ValueError: pass

def findfirsttarget(target,sources,ops=standard_ops):
    for e,s,v in expressions(sources,ops):
        if v==target:
            return strexpression(e)
    return None

print findfirsttarget(923,[7,8,50,8,1,3])

gives:

((7*(((8*50)-1)/3))-8)

Dan Goodman