"le compte est bon" (documented version)

readme.txt

This is a solver for  the "le compte est bon" game ("the total is right") http://bit.ly/Lxvowq

Its main file is game.py. It needs arguments on the command line. This is a usage example : 

python game.py 18 29 30 17 40 29

The engine will try different combinations of algebric operations on the first numbers to get to the last one

For example : 

python game.py 35 22 4 7 16 100 

will find all possible combinations of 35,22,4,7,16 to get 100. The program prints 20 solutions for this problem :

((35+(22*4))-16)-7 = 100
(35-(16-(4*22)))-7 = 100
(35+((4*22)-16))-7 = 100
(35-(7-(4*22)))-16 = 100
(35+((4*22)-7))-16 = 100
((35+(22*4))-7)-16 = 100
4+(16*(35-(22+7))) = 100
4-(16*((22+7)-35)) = 100
4-(16*(22+(7-35))) = 100
4-(16*(22-(35-7))) = 100
4+(16*((35-7)-22)) = 100
4-(16*(7-(35-22))) = 100
4+(16*((35-22)-7)) = 100
4-(16*(7+(22-35))) = 100
35-(7+(16-(4*22))) = 100
35-(7-((4*22)-16)) = 100
35+(((4*22)-16)-7) = 100
35-(16+(7-(4*22))) = 100
35-(16-((4*22)-7)) = 100
35+(((4*22)-7)-16) = 100
found 20 solutions to this problem amongst a total of 77.760 possible combinations (5 numbers)

Some solutions are discarded, for example if 4*22 is a solution then 22*4 is discarded, same for 4+22 and 22+4, 
because they are considered the same. This also works for expressions, if (4*22) + 55 is a solution 
then 55 + (4*22) is discarded. The engine is stupid enough to not notice that 25+(2-1) is really the same as 25-(1-2). 

How it works
============

game.py asks the generator's (generator.py) "combo" function to generate all possible algebric combinations for the N-1
numebers given as argument, and passes each one of them to the calculator's (calculator.py) evaluate function. 
The result is compared to the last number.

The combinatoric part is extensively documented inside the source code of generator.py

caculator.py

## Yassine chaouche
## yacinechaouche@yahoo.com
## http://ychaouche.informatick.net
## Jun 16 2012 - 02:42

"""
This file contains the evaluate function that computes expressions like (4+3)/(2*(5+4)).
game.py feeds this function with expressions generated by the generator.combo function
(file generator.py). Its main function is evaluate. It takes an expression as a parameter,
which is simply a string, and returns the result of the computation of that expression.
For example : evaluate ("(4+(2*(6-1)))") -> 14

== FORMAT == 

The format of the expression is highly restricted : every expression must contain one
operation at a time, So you must be careful to put all you operands in parentheses.
For example : 5+6*(3+1) is wrong, because there's more than one operation
at a time (+ then *). the correct form is : 5+(6*(3+1)) which is evaluated like this :
  o There's one big operation 5 + (X).
  o X has one big operation inside which is 6 * (Y)
  o and Y is a simple operation that is 3+1.

== EXCEPTIONS ==
It may return None when any part of the expression divides by 0.
"""

def evaluate(expression):
    """
    evaluate("6+(3*2)") => 12
    Where : first = 6; second = +; and third = (3*2).

    Symmetrically, evaluate("(8*2) - 10") => 6
    where first = (8*2); second = -; and third = 10.

    First and third are either numbers or expressions.
    Second is always an operator, otherwise the application may crash (not tested)

    The function is not defensive at all, it does not check the validity of its input.
    If the format is not respected, it may simply crash.

    Here's how it works :
    
    First thing, we tokenize the expression into tokens : first, second, and third 
    for example :                                                                      
    tokenize("6+(3*2)") => first = 6; second = +; and third = (3*2).

    Then, we simply retun the result of applying the operation on the evaluation of left
    and the evaluation of right recursively.

    The evalution of left or right is again the result of applying the operation contained
    within on the evaluation of their left and right parts respectively and so on.

    The recursion ends when the expression to evaluate is a simple number, in which case
    it evaluates to itself.
    """
    if is_number(expression):
        return int(expression)
    left,operation,right = tokenize(expression)
    if left != None and right != None and operation != None and is_operation(operation):
        return do_op(evaluate(remove_parens(left)),operation,evaluate(remove_parens(right)))

    # for a total of 5 lines of code, but you may prefere the longer, documented and  boring version.
    # see bleow
    
## def evaluate_boring_long_version(expression)
##     #print 'expression is "%s"' % expression

##     # If the expression to evaluate is a number, return that number.
##     if is_number(expression):
##         return int(expression)
    
##     # Else, we decompose the expression into tokens...(1)
##     left,operation,right = tokenize(expression)
##     left, right = map(remove_parens,[left,right])
##     #print "tokens '%s', '%s', '%s' " %(left,operation,right)

##     if left != None and right != None and operation != None and is_operation(operation):
##         # (1)...and evaluate each of them recurively, until they become simple numbers (the recursion ends there).
##         result = do_op(evaluate(left),operation,evaluate(right))
##         #print "we return the value of %s %s %s which is %s" % (left,operation,right,result)
##         return result

def tokenize(s):
    """
    This function cuts s into two parts with a left operand and a right operand.
    Both parts can be expressions or numbers.
    
    tokenize("(13*8)+(5-3)") -> (13*8),+,(5-3)
    tokenize("(13*(8+5))-3") -> (13*(8+5)),-,3
    """
    #print "tokenize",s
    s = remove_spaces(s)
    if s[0] not in ('(',')') :
        # we're reading a number
        # XXX : it can't be an operand otherwise the expression is malformed -> crash
        first  = read_number(s)        
        second = s[len(first)]
        third  = s[len(first)+1:]
    else:
        # we're reading an expression
        pos    = next_token(s)
        first  = s[0:pos+1]
        second = s[pos+1]
        third  = s[pos+2:]
    #print "tokenization : %s, %s , %s" % (first,second,third)
    return first,second,third

def next_token(s):
    """
    This is a helper function used by the tokenize function.
    By counting the number of parentheses, it can know where an expression ends and where the next begins.
    Here's how it works :
    the function has a counter n. 
    It parses the string s and increments n whenever it encounters an opening parenthesis.
    It decerements n whenever it encounters a closing parenthesis.
    If n reaches zero, that means that all opened parentheses are matched, so we're at the end
    of an expression contained between parentheses.

    (5+(3*(2+1)))-(1+4) -> returns the position of the "-" operation.

    that way, the tokenize function can, well... "tokenize" s into :
      o (5+(3*(2+1))); which is s[0:pos+1]
      o -; which is s[pos+1]
      o (1+4) which is s[pos+2:]
    """
    n   = 0
    pos = 0
    for x in s:
        if x == '(':
            n += 1
        elif x == ')':
            n -= 1
        if n == 0:
            # function should always exit here
            return pos
        pos += 1
    # this should only happen when parentheses are unablanced
    return pos

def read_number(s):
    """
    Simply reads a number from a stream of characters s. 
    157+(3*8) -> 157
    """
    c = ""
    while s[0].isdigit():
        c += s[0]
        s = s[1:] # s++;
    return c

def do_op(left,operation,right):
    """
    do_op("10","+","30") -> 40 
    do_op("2","/","4") -> None # fraction
    do_op("7","/","5") -> None # fraction
    do_op("38","/","0") -> None # divide by 0
    """
    # TODO :  Can we optimise thise function a little bit and get rid of all those ifs ?
    # print "do_op(%s,%s,%s)" % (left,operation,right)
    
    if left == None or right == None: # Left or Right might be None in a case of a previous 
        return                        # impossible operation, like division by zero.
    
    if operation == "+" :
        return left + right
    
    elif operation == "*" :
        return left * right
    
    elif operation == "/" :
        if right != 0 : 
            result =  left / right
            if not left % right : # we don't allow fractions
                return result
    
    elif operation == "-" :
        return left - right
    
def is_number(s):
    """ self exp """
    return s.isdigit()

def is_operation(s):
    """ self exp """
    return s in ["+","/","*","-"]

def remove_spaces(s):
    return "".join(s.split(" "))

def is_parenthized(s):
    return s.startswith("(")

def remove_parens(s):
    # defensive programming
    if is_parenthized(s) :
        return s[1:-1]
    return s

def main():
    """ self exp """
    import sys
    print evaluate(sys.argv[1])

def test_tokenize():
    """ self exp """
    import sys
    print tokenize(sys.argv[1])

if __name__ == "__main__":
    #test_tokenize()
    main()

game.py

## Yassine chaouche
## yacinechaouche@yahoo.com
## http://ychaouche.informatick.net
## Jun 16 2012 - 19:08

"""
This is the main file containing the main function.
It reads a series of number from standard input and
tries to combine the N-1th numbers to get the Nth number

For example :

python game.py 10 29 39 48 19 40

Will try to combine 10 29 39 48 19 to get 40.

It will print all the possible results.

chaouche@karabeela ~/CODE/TEST/PYTHON/MATHS $ python game.py 10 29 39 48 19 40
found one solution after 5.482 tries (39-(19*(29-48)))/10  =  40
found one solution after 6.340 tries (39+(19*(48-29)))/10  =  40
found one solution after 9.221 tries (48+((39+19)/29))-10  =  40
found one solution after 50.695 tries 48-(10-((39+19)/29))  =  40
found one solution after 50.718 tries 48+(((39+19)/29)-10)  =  40
(39-(19*(29-48)))/10 = 40
(39+(19*(48-29)))/10 = 40
(48+((39+19)/29))-10 = 40
48-(10-((39+19)/29)) = 40
48+(((39+19)/29)-10) = 40
found 5 solutions to this problem amongst a total of 77.760 possible combinations (5 numbers)
chaouche@karabeela ~/CODE/TEST/PYTHON/MATHS $

The main function simply asks the genrator.combo function to give all possible
combinations for the numbers given as parameters. For each combination, it asks
the calculator how much that expression is and compares it to the last number of
the command line arguments. If the numbers are the same, then that combination is
a solution.

The algorithme is simple :

for combo in generator.combo(numbers):
   if calculator.evalute(combo) == result :
      that's one solution.

As simple as that.

All the complexity is hidden in generator.combo and calculator.evalute.
"""

import sys
import generator
import calculator
from number_pprint import number_pprint

def main():
    numbers = sys.argv[1:-1]
    result  = sys.argv[-1]
    # A little optimisation : if there are two identical numbers in the input, there
    # may be some identical expressions in the output, so we may sweep them to make
    # things a little faster.
    # THIS OPTIMISATION CANNOT BE DONE
    # because now we're using generators to avoid memory consumption.
    # using sets will make a list out of the generator, a very big list (2Gb+ for a combo of 7 numbers)
    # S         = set(L)
    solutions  = []
    iterations = 0
    found      = False
    for possibility in generator.combo(numbers):
        #print "l",l
        #sys.stdin.readline()
        possibility = possibility[1:-1] # removes protecting parentheses
        evaluation  = calculator.evaluate(possibility)
        #print "c",c
        if evaluation !=None and int(evaluation) == int(result):
            print "found one solution after %s tries" % (number_pprint(iterations)),possibility," = ",result
            found = True
            #break
            solutions.append(possibility)
        iterations += 1
        ## if not iterations % 10000:
        ##     print "%s iterations so far" % number_pprint(iterations)

    if not found:
        string =  "there seems to be no solution to this problem. I've exhausted all %s combinations (for %s numbers)"
        print string % (iterations,len(sys.argv[1:-1]))
        return
    
    for s in solutions :
        print s, "=", result
    
    string = "found %s solutions to this problem amongst a total of %s possible combinations (%s numbers)"
    print string % (number_pprint(len(solutions)),number_pprint(iterations),len(sys.argv[1:-1]))

if __name__ == "__main__":
    main()

generator.py

## Yassine chaouche
## yacinechaouche@yahoo.com
## http://ychaouche.informatick.net
## Jun 16 2012 - 16:53

"""
This file contains the combo function : a generator that takes numbers
as parameter (any number of numbers), and generates every possible combination
of simple algebric expressions with these numbers.

For example combo([2,4,9]) -> : (108 combinations)

(2+(4-9)) (2+(4+9)) (2+(4*9)) (2+(4/9)) (2+(9/4)) (2+(9-4)) (4+(9+2)) (4+(9-2)) (4+(9*2))
(2-(4-9)) (2-(4+9)) (2-(4*9)) (2-(4/9)) (2-(9/4)) (2-(9-4)) (4-(9+2)) (4-(9-2)) (4-(9*2))
(2*(4-9)) (2*(4+9)) (2*(4*9)) (2*(4/9)) (2*(9/4)) (2*(9-4)) (4*(9+2)) (4*(9-2)) (4*(9*2))
(2/(4-9)) (2/(4+9)) (2/(4*9)) (2/(4/9)) (2/(9/4)) (2/(9-4)) (4/(9+2)) (4/(9-2)) (4/(9*2))
((4-9)/2) ((4+9)/2) ((4*9)/2) ((4/9)/2) ((9/4)/2) ((9-4)/2) ((9+2)/4) ((9-2)/4) ((9*2)/4)
((4-9)-2) ((4+9)-2) ((4*9)-2) ((4/9)-2) ((9/4)-2) ((9-4)-2) ((9+2)-4) ((9-2)-4) ((9*2)-4)

(4+(9/2)) (4+(2/9)) (4+(2-9)) (9+(2+4)) (9+(2-4)) (9+(2*4)) (9+(2/4)) (9+(4/2)) (9+(4-2))
(4-(9/2)) (4-(2/9)) (4-(2-9)) (9-(2+4)) (9-(2-4)) (9-(2*4)) (9-(2/4)) (9-(4/2)) (9-(4-2))
(4*(9/2)) (4*(2/9)) (4*(2-9)) (9*(2+4)) (9*(2-4)) (9*(2*4)) (9*(2/4)) (9*(4/2)) (9*(4-2))
(4/(9/2)) (4/(2/9)) (4/(2-9)) (9/(2+4)) (9/(2-4)) (9/(2*4)) (9/(2/4)) (9/(4/2)) (9/(4-2))
((9/2)/4) ((2/9)/4) ((2-9)/4) ((2+4)/9) ((2-4)/9) ((2*4)/9) ((2/4)/9) ((4/2)/9) ((4-2)/9)
((9/2)-4) ((2/9)-4) ((2-9)-4) ((2+4)-9) ((2-4)-9) ((2*4)-9) ((2/4)-9) ((4/2)-9) ((4-2)-9)

The abelian operations are not doubled, this means that for the + and for the *
operations, only a+b and a*b are generated (b*a and b+a are considered duplicates).
This is not true however for non abelian operations like - and / .

You can verify that all these combinations are unique, if that sounds amusing to you.
Some of them may have the same value, but they're not obtained the same way, so they're
not considered the same. This may seem more obvious to you in large combinations (6 to 9 numbers)
where one problem may have tens of solutions.
"""

def combo(S):
    """
    How it works :

    S is a Serie of numbers (okay, it's just a list...). But for the purposes of our function,
    it's treated like a Stack (hence the S).

    If S contains just two numbers, for example 9 and 8, then combo will generate all possible
    algebric operations with these two numbers, with the help of the _combo function (notice the
    leading underscore). So for example combo([9,8]) is a list of six items, returned
    by the helper funciton _combo(9,8) : 
    
    (9+8)
    (9-8)
    (9*8)
    (9/8)
    (8/9)
    (8-9)

    If S has more than just two numbers, for example :

    S = [4,5,8,9,12]

    then take the first number (4) out of the stack...

    S = [5,8,9,12]

    ...and combine it with every combination c of the remaining numbers, which are obtained by simply
    calling combo recursively on the Stack. These recursive calls will end when there are just
    two numbers remaining in the stack, because in each call to Combo, one number is removed as we
    did earlier.
    
    So for example (recursive calls) :

    -> combo([4,5,8,9,12]) is _combo(4,X) for every X in combo([5,8,9,12]) #removes 4 from the stack
     -> combo([5,8,9,12]) is _combo(5,Y) for every Y in combo([8,9,12]) #removes 5 from the stack
      -> combo([8,9,12]) is _combo(8,Z) for every Z in combo([9,12]) #removes 8 from the stack
       -> combo([9,12]) -> _combo(9,12) (all 6 algebric operations).
       -> the recursion ends here, return all the combinations of 9 and 12
      -> return all the combinations of [8,9,12]
     -> return all the combinations [5,8,9,12]
    -> combine 4 with every combination of [5,8,9,12]
    
    Let's take an example with just three numbers : 4,5, and 8.
    We decide to execute combo([4,5,8])

    We remove 4 from the stack, and combine it with every combinations of the remaining numbers
    8 and 5 :
    
    combo([4,5,8]) is _combo(4,c) for every c in combo([5,8]).

    combo([5,8]) : the stack has only two numbers, so its combinations are simply _combo(5,8),
    a list of 6 combos : (5+8),(5-8),(5*8),(5/8),(8-5),(8/5).
    (remember that (8*5) and (8+5) are the same as (5*8) and (5+8) so they're not generated.)
    
    What we'll do is take every one of these combinations, let's call them c, and make
    a combination out of 4, the number we took from S earlier, and c. That's what the line
    
    _combo(4,c) for every c in combo([5,8])

    does.

    _combo(4,c) has also six possibilities (4+c, 4-c, 4*c, 4/c, c-4,c/4), so for each
    value of c we have 6 possible combinations with 4, and there are 6 values of c,
    so the total possibilities of _combo(4,c) is 6 * 6 = 36 possible combos : 

    (4+(5+8)) (4+(5-8)) (4+(5*8)) (4+(5/8)) (4+(8/5)) (4+(8-5))
    (4-(5+8)) (4-(5-8)) (4-(5*8)) (4-(5/8)) (4-(8/5)) (4-(8-5))
    (4*(5+8)) (4*(5-8)) (4*(5*8)) (4*(5/8)) (4*(8/5)) (4*(8-5))
    (4/(5+8)) (4/(5-8)) (4/(5*8)) (4/(5/8)) (4/(8/5)) (4/(8-5))
    ((5+8)/4) ((5-8)/4) ((5*8)/4) ((5/8)/4) ((8/5)/4) ((8-5)/4)
    ((5+8)-4) ((5-8)-4) ((5*8)-4) ((5/8)-4) ((8/5)-4) ((8-5)-4)

    Notice how 4 is always in one side of the operation and (8,5) is on the other side ?
    There are still many combinations left where 4 is "in the middle" of the expression,
    not just on its sides. And so does for 5 and 8. 

    We can simply acheive this by putting 4 back in the stack...
    
    S = [4,5,8]

    take 5 out of it...

    S = [4,8]

    and make every combinations of 5 with every combinations of 4 and 8. We get this : 

    (5+(8+4)) (5+(8-4)) (5+(8*4)) (5+(8/4)) (5+(4/8)) (5+(4-8))
    (5-(8+4)) (5-(8-4)) (5-(8*4)) (5-(8/4)) (5-(4/8)) (5-(4-8))
    (5*(8+4)) (5*(8-4)) (5*(8*4)) (5*(8/4)) (5*(4/8)) (5*(4-8))
    (5/(8+4)) (5/(8-4)) (5/(8*4)) (5/(8/4)) (5/(4/8)) (5/(4-8))
    ((8+4)/5) ((8-4)/5) ((8*4)/5) ((8/4)/5) ((4/8)/5) ((4-8)/5)
    ((8+4)-5) ((8-4)-5) ((8*4)-5) ((8/4)-5) ((4/8)-5) ((4-8)-5)
    
    Now we put back five in the stack...

    S = [4,5,8]

    and remove 8...

    S = [4,5]

    Then generate all combinations of 8 with all combinations of 4 and 5.

    (8+(4+5)) (8+(4-5)) (8+(4*5)) (8+(4/5)) (8+(5/4)) (8+(5-4))
    (8-(4+5)) (8-(4-5)) (8-(4*5)) (8-(4/5)) (8-(5/4)) (8-(5-4))
    (8*(4+5)) (8*(4-5)) (8*(4*5)) (8*(4/5)) (8*(5/4)) (8*(5-4))
    (8/(4+5)) (8/(4-5)) (8/(4*5)) (8/(4/5)) (8/(5/4)) (8/(5-4))
    ((4+5)/8) ((4-5)/8) ((4*5)/8) ((4/5)/8) ((5/4)/8) ((5-4)/8)
    ((4+5)-8) ((4-5)-8) ((4*5)-8) ((4/5)-8) ((5/4)-8) ((5-4)-8)

    Done ! you have cycled through all elements of your stack, and so you have all
    108 possible combinations of 4,5 and 8 taken in any possible order. If all the
    numbers are different, all the combinations are unique.
    
    Let's analyze this algorithme and see if we're going to explode the memory for
    high numbers of stack size. Here's how our algorithme looks like
    
    combo([4,5,8,12,9]) is :     _combo(4,X) for every X in combo([5,8,12,9])
                                                       +                     
                                 _combo(5,Y) for every Y in combo([4,8,12,9])
                                                       +                     
                                 _combo(8,Z) for every Z in combo([4,5,12,9])
                                                       +                     
                                 _combo(12,W) for every W in combo([4,5,8,9])
                                                       +                     
                                 _combo(9,V) for every V in combo([4,8,5,12])

    You can figure out from this demonstration that the total number of combinations
    for a stack of n numbers, for n > 2 is : 
    F(2) = 6           
    F(3) = 6*(F(2))*3  
    F(4) = 6*(F(3))*4  
    ...
    F(n) = 6*(F(n-1))*n

    (Is this is a geometrical serie ?)

    Now you'll understand why we don't put the results in a list before returning them :
    For 3 numbers, the number of possibilities is 108.
    For 4 numbers, 2.592.
    5 -> 77.760
    6 -> 2.799.360
    7 -> 117.573.120. That's a lot of memory :

    Each character is one byte and for 7 numbers you may have expressions like (5+(3*(8+2))/((4-2)*6)
    which are 22 characters long.

    22 characters are 22 bytes, which multiplies 117.573.120 is 2,586,608,640.
    That's approximatively 2.5 Gb of RAM, and that's why I got a memory error when I tried the
    list version of combo. So I rewrote it in a generative way (combo is a generator).

    The code to do this is 11 lines :
    """

    if len(S) == 2: # If there's only two numbers remaining in the stack
        for c in _combo(S[0],S[1]):
            yield ("("+c+")")
        return
    
    original = list(S)
    
    for e in original:
        S.remove(e)
        # don't throw away the yields ! use the generator
        #s = combo(S)
        for es in combo(S) :
            for c in _combo(e,es):
                yield ("("+c+")")
        S.append(e)

def _combo(a,b):
    """
    a and b mustn't be lists
    """
    L = []
    L.append(a+"+"+b)
    L.append(a+"-"+b)
    L.append(a+"*"+b)
    L.append(a+"/"+b)
    
    L.append(b+"/"+a)
    L.append(b+"-"+a)
    #L.append( b+"+"+a) # addition and multiplication are abelian,
    #L.append( b+"*"+a) # no need to repeat them
    return L    

def test5():
    import sys
    from number_pprint import number_pprint
    L = sys.argv[1:]
    i = 0
    for c in combo(L):
        print c
        i+=1
    print number_pprint(i),"possibilities for",len(L),"numbers"
        
if __name__ == "__main__":
    test5()

number_pprint.py

def number_pprint(number):
    string_number = list(str(number))
    i             = 0
    result        = []
    while string_number:
        if i and not (i % 3):
            result+="."
        n = string_number.pop()
        result+=n
        i += 1
        
    result.reverse()
    return "".join(result)

def main():
    import sys
    print number_pprint(sys.argv[1])
    
if __name__ == "__main__":
    main()