Just for fun: Countdown numbers game solver

[dg.google.groups at thesamovar.net]

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.

If you don't know the game, it's simple: you're given six randomly
chosen positive integers, and a target (another randomly chosen
positive integer), and you have to make the target using only the
numbers you're given, and +,-,* and / (and any number of brackets you
like). You're not allowed fractions as intermediate values. So, given
2, 3 and 5 say, and a target of 21, you could do (2+5)*3 = 21.

So what's the best algorithm? And, what's the most elegant way to code
it in Python? I've posted my most elegant version below (I have a
faster version which is slightly less elegant). Can anyone do better?

Refs:

* This academic paper describes an implementation of an algorithm to
solve the problem in Haskell. I found it after I'd written mine but it
uses a very similar algorithm. http://www.cs.nott.ac.uk/~gmh/countdown.pdf
* My web page where I put both versions of my code: http://thesamovar.net/countdownnumbers
* The web page of the TV show the problem is based on:
http://www.channel4.com/entertainment/tv/microsites/C/countdown/index.html

My version:

class InvalidExpressionError(ValueError):
    pass

subtract = lambda x,y: x-y
def add(x,y):
    if x<=y: return x+y
    raise InvalidExpressionError
def multiply(x,y):
    if x<=y or x==1 or y==1: return x*y
    raise InvalidExpressionError
def divide(x,y):
    if not y or x%y or y==1:
        raise InvalidExpressionError
    return x/y

add.display_string = '+'
multiply.display_string = '*'
subtract.display_string = '-'
divide.display_string = '/'

standard_operators = [ add, subtract, multiply, divide ]

class Expression(object): pass

class TerminalExpression(Expression):
    def __init__(self,value,remaining_sources):
        self.value = value
        self.remaining_sources = remaining_sources
    def __str__(self):
        return str(self.value)
    def __repr__(self):
        return str(self.value)

class BranchedExpression(Expression):
    def __init__(self,operator,lhs,rhs,remaining_sources):
        self.operator = operator
        self.lhs = lhs
        self.rhs = rhs
        self.value = operator(lhs.value,rhs.value)
        self.remaining_sources = remaining_sources
    def __str__(self):
        return '('+str(self.lhs)+self.operator.display_string
+str(self.rhs)+')'
    def __repr__(self):
        return self.__str__()

def
ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0):
    for value, i in zip(sources,range(len(sources))):
        yield TerminalExpression(value=value,
remaining_sources=sources[:i]+sources[i+1:])
    if len(sources)>=2+minimal_remaining_sources:
        for lhs in
ValidExpressions(sources,operators,minimal_remaining_sources+1):
            for rhs in ValidExpressions(lhs.remaining_sources,
operators, minimal_remaining_sources):
                for f in operators:
                    try: yield BranchedExpression(operator=f, lhs=lhs,
rhs=rhs, remaining_sources=rhs.remaining_sources)
                    except InvalidExpressionError: pass

def TargetExpressions(target,sources,operators=standard_operators):
    for expression in ValidExpressions(sources,operators):
        if expression.value==target:
            yield expression

def FindFirstTarget(target,sources,operators=standard_operators):
    for expression in ValidExpressions(sources,operators):
        if expression.value==target:
            return expression
    raise IndexError, "No matching expressions found"

if __name__=='__main__':
    import time
    start_time = time.time()
    target_expressions = list(TargetExpressions(923,[7,8,50,8,1,3]))
    target_expressions.sort(lambda x,y:len(str(x))-len(str(y)))
    print "Found",len(target_expressions),"solutions, minimal string
length was:"
    print target_expressions[0],'=',target_expressions[0].value
    print
    print "Took",time.time()-start_time,"seconds."