"""
Python Countdown Numbers Game solver, Dan Goodman Jan 2008

Solves the Countdown Numbers game fairly quickly in a fairly neat way.

Usage:
------

In the following, target is an integer, sources is a list of integers, and
ops is a list of operations (functions taking two values), which if
unspecified is left as +,-,*,/. The aim is to find expressions constructed
from the integer sources and the operations which evaluate to the target.

-- findfirsttarget(target,sources(,ops))
    Finds the first matching expression

-- targetexpressions(target,sources(,ops))
    Generator, returns all the (string) expressions matching the target

-- expressions(sources(,ops))
    Generator, returns all valid expressions (in list format), see its
    docs for more info.

-- strexpression(e)
    Converts a list format expression to a string expression

Examples:
---------

>>> findfirsttarget(234,[100,9,7,6,3,1])
'(100+(9-(1-(7*(3*6)))))'

>>> for x in targetexpressions(33,[100,3,1]):
	print x

	
((100-1)/3)

Detailed notes:
---------------

Raw expressions generated by the expressions() generator are (recursive)
lists of 1 or 3 elements. A list with 1 element contains just an integer,
one of the sources. A list of three elements is of the form: [f,x,y] where
f is an operator and x and y are themselves raw expressions. So, for example
(x+y)*z would be represented as [mul,[add,x,y],z].

The standard operations are just +,-,*,/ but with some special features.
Add and multiply with raise a ValueError exception if their second
argument is bigger than their first argument. This stops the algorithm
from processing both a+b and b+a, which makes it run significantly faster.
The division operation raises the same exception if the result is a noninteger
or division by zero is attempted.

The algorithm is fairly simple minded, it just goes through every possible
expression recursively, evaluating as it goes. For each position in the
expression tree, it first tries each remaining source value, and then for
each operator f it tries f(x,y) for every possible pair of expressions
(x,y). See source code for the expressions() generator for a more detailed
explanation.

"""

__all__ = [ 'expressions', 'findfirsttarget', 'targetexpressions', 'strexpression' ]

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):
    """Convert a raw expression to a string"""
    if len(e)==3:
        return '('+strexpression(e[1])+e[0].disp+strexpression(e[2])+')'
    elif len(e)==1:
        return str(e[0])
    raise ValueError

# The algorithm for the expressions function works as follows:
# 1. Start with an empty expression tree with a single free slot
# 2. When recursively filling in a free slot, first try each
#    of the remaining sources, then for each operation, build
#    an extra branch using that operation and two free slots.
def expressions(sources,ops=standard_ops,minremsources=0):
    """Generates all expressions

    Returns a tuple (e,s,v) where:
    -- e, a raw expression
    -- s, the remaining unused sources
    -- v, the value of the expression

    Example (from findfirsttarget):

    for e,s,v in expressions(sources,ops):
    if v==target:
        return strexpression(e)
        
    The minremsources argument to this generator is only used internally.
    
    See source code comments for algorithmic notes.
    """
    # First try each of the sources, when we try each one we have to remember
    # to remove it from the list of remaining sources that we pass back
    # and pass back the (trivial) evaluation of the subexpression, which is
    # just the value of the source
    for i in range(len(sources)):
        #      expression   remaining sources         value
        yield ([sources[i]],sources[:i]+sources[i+1:],sources[i])
    # Now we have the slightly more complicated recursive job of trying
    # all possible subexpressions formed by an operation with two free
    # slots. The first thing to check is that there are actually enough
    # sources remaining. If you just check len(sources)>=2 you run into a
    # problem. It seems like having 2 remaining sources is enough because
    # you are adding two free slots which would have to be filled by
    # sources. However, because the algorithm proceeds by first recursing
    # on the left hand side, then the right hand side, you might actually
    # need to leave some sources over for the calling function to use to
    # fill in one of its remaining slots. If you don't check for this you
    # get an infinite recursion. Let me illustrate, you have the following
    # sources left [a,b,c] say. The algorithm first tries to generate:
    # +(.,.) where . is a free slot. Now it tries +(+(.,.),.) and
    # +(+(+(.,.),.),.) etc. because until those free slots have a source
    # placed in them, no sources are used up. So, the solution is to
    # keep track of the number of sources we will need to have left over
    # after the operation is finished for all of the calling functions
    # to fill their slots. We do this by incrementing minremsources, the
    # minimum number of remaining sources required after this call yields
    # an expression, for the expressions generated on the left hand side.
    # We don't have to do this when generating expressions for the right
    # hand side because when we get to doing this, the left hand side
    # expressions will already have filled all their free slots. So, in
    # conclusion, the following line checks that we have enough sources
    # to fill the two free slots we'll create, and leave enough left over
    # for the calling function to fill
    if len(sources)>=2+minremsources:
        # e1, rs1, v1 = LHS expression, remaining sources, value, we iterate
        # over all expressions which leave us one extra remaining source to
        # fill the right hand side of the expression we're generating
        for e1, rs1, v1 in expressions(sources,ops,minremsources+1):
            # similar to e1,rs1,v1
            for e2, rs2, v2 in expressions(rs1,ops,minremsources):
                # logically, this loop is outside the previous two, but
                # for speed reasons it makes more sense to put it here.
                # It tries out all the operations on its inputs. The
                # clever thing to note is that if the operation
                # o(v1,v2) raises a ValueError exception, we do not yield the
                # expression (and thereby save on further processing).
                for o in ops:
                    # [o,e1,e2] is the raw expression, rs2 is the sources
                    # remaining after the expressions e1 and e2 have been
                    # generated, and o(v1,v2) is the operation applied to
                    # the values of e1 and e2 (we compute as we go along
                    # to save time).
                    try: yield ([o,e1,e2],rs2,o(v1,v2))
                    except ValueError: pass

def findfirsttarget(target,sources,ops=standard_ops):
    """Find the first matching expression"""
    for e,s,v in expressions(sources,ops):
        if v==target:
            return strexpression(e)
    return []

def targetexpressions(target,sources,ops=standard_ops):
    """Generates all matching expressions"""
    for e,s,v in expressions(sources,ops):
        if v==target:
            yield strexpression(e)

if __name__=='__main__':
    import time
    def demo(target,sources):
        print "Looking for:",target
        print "Given numbers:",sources
        print "Operators:",
        for o in standard_ops:
            print o.disp,
        print
        print
        
        start = time.time()
        s = [e for e in targetexpressions(target,sources)]
        s.sort(lambda x,y:len(x)-len(y))

        print "Found",len(s),"solutions, minimal string length solution:"
        print s[0]
        print
        print "Took", time.time()-start, "seconds."

    print "A sample:"
    print

    demo(234,[100,9,7,6,3,1])    

    print
    print "Now trying one of the most difficult possible problems:"
    print

    demo(923,[7,8,50,8,1,3])