# Simple Python script to solve the Four Fours puzzle.
# Namely: express each integer between 1 and 100   
# using standard operations and exactly four fours
#
# Written by: Rich Burridge - December 2006
#
# Based on the C# version by Carl Johansen
# http://www.carljohansen.co.uk/fourfours/fourfours.cs.txt
# Copyright (c) 2005 Carl Johansen
#

import operator
import time

def Operate(lhs, rhs, operation):
    blnAbort = False
    if operation == 0:
        result = lhs + rhs + 0.0
    elif operation == 1:
        result = lhs - rhs - 0.0
    elif operation == 2:
        try:
            result = lhs * rhs * 1.0
        except:
            result = 0.0
            blnAbort = True
    elif operation == 3:
        if rhs < 0.001:
            result = 0.0
            blnAbort = True
        else:
            result = lhs / rhs * 1.0
    elif operation == 4:
        try:
            result = pow(lhs, rhs) * 1.0
        except:
            result = 0.0
            blnAbort = True
    else:
        result = -9999.0

    return [result, blnAbort]

def OperatorSymbol(operation):
    try:
        return ["+", "-", "*", "/", "^"][operation]
    except:
        return "unknown operator!"

def ExpressionForDisplay(arrTermsDisp, termIndex, operations, separators):
    # Combines the expression's operators and operands using the specified 
    # separator characters (white spaces and round brackets) to create a 
    # string for display.
    #
    return separators[0] + str(arrTermsDisp[termIndex[0]]) + \
           separators[1] + OperatorSymbol(operations[0]) + \
           separators[2] + str(arrTermsDisp[termIndex[1]]) + \
           separators[3] + OperatorSymbol(operations[1]) + \
           separators[4] + str(arrTermsDisp[termIndex[2]]) + \
           separators[5] + OperatorSymbol(operations[2]) + \
           separators[6] + str(arrTermsDisp[termIndex[3]]) + \
           separators[7]

def main():
    NUM_OPERATORS = 5
    NUM_TERMS = 6
    intCurrResult = 0
    intCurrResultScore = 0
    intIterations = 0
    datStartTime = time.time()
    decCurrResult = 0.0
    decTempResult = 0.0
    blnAbort = False
    operations = [ 0, 0, 0 ]
    arrTerms = [ 4.0, 2.0, 24.0, 4.0/10.0, 4.0/9.0, 2.0/3.0, 0.0, 0.0 ]
    arrTermsDisp = [ "4", "sqrt(4)", "4!", ".4",     ".4bar",  "sqrt(.4bar)" ]

    # Used to give preference to "simpler" answers.
    #
    arrTermScore = [ 50,  40,        30,   20,     10,       1 ]

    # There are four possible groupings. 
    # { 0, 0, 1 } means apply operator #0 to operand #0 and operand #1 and 
    # call the result "operand #4"
    # { 2, 2, 3 } means apply operator #2 to operand #2 and operand #3 and 
    # call the result "operand #5"
    # { 4, 1, 5 } means apply operator #1 to operand #4 and operand #5.
    # This is the overall result.
    #
    expression = [ [ [ 0, 0, 1 ], [ 2, 2, 3 ], [ 4, 1, 5 ] ],   # ( A x B ) x ( C x D )
                   [ [ 0, 0, 1 ], [ 4, 1, 2 ], [ 5, 2, 3 ] ],   # ( ( A x B ) x C ) x D
                   [ [ 1, 1, 2 ], [ 0, 0, 4 ], [ 5, 2, 3 ] ],   # ( A x ( B x C ) ) x D
                   [ [ 2, 2, 3 ], [ 1, 1, 4 ], [ 0, 0, 5 ] ] ]  # A x ( B x ( C x D ) )

    termIndex = [ 0, 0, 0, 0, NUM_TERMS, NUM_TERMS + 1 ]

    arrAnswer = [0]*101 
    arrBestAnswerScore = [0]*101
    seenResult = [False]*101

    # Go through all possible operator/operand combinations.
    # There are four ways of applying precedence to the operators
    #
    for association in range(0, 4):
        for termIndex[0] in range(0, NUM_TERMS):
            for termIndex[1] in range(0, NUM_TERMS):
                for termIndex[2] in range(0, NUM_TERMS):
                    for termIndex[3] in range(0, NUM_TERMS):
                        for operations[0] in range(0, NUM_OPERATORS):
                            for operations[1] in range(0, NUM_OPERATORS):
                                for operations[2] in range(0, NUM_OPERATORS):
                                    intIterations += 1

                                    blnAbort = False
                                    for step in range(0, 3):
                                        if blnAbort == True:
                                            break
                                        [decTempResult, blnAbort] = Operate(arrTerms[termIndex[expression[association][step][0]]], 
                                                                            arrTerms[termIndex[expression[association][step][2]]],
                                                                            operations[expression[association][step][1]])

                                        if blnAbort == False: 
                                            if step == 0:
                                                arrTerms[NUM_TERMS] = decTempResult
                                            elif step == 1:
                                                arrTerms[NUM_TERMS + 1] = decTempResult
                                            elif step == 2:
                                                decCurrResult = decTempResult

                                    intCurrResult = int(decCurrResult)
                                    if (blnAbort == False) and \
                                       (decCurrResult >= 1) and \
                                       (decCurrResult <= 100) and \
                                       (abs(intCurrResult - float(decCurrResult)) < 0.0000001):
                                        intCurrResultScore = arrTermScore[termIndex[0]] + \
                                                             arrTermScore[termIndex[1]] + \
                                                             arrTermScore[termIndex[2]] + \
                                                             arrTermScore[termIndex[3]];
                                        if intCurrResultScore > arrBestAnswerScore[intCurrResult]:
                                            # This looks like the most attractive answer we have seen so far for intCurrResult.
                                            #
                                            arrBestAnswerScore[intCurrResult] = intCurrResultScore;                                        

                                            if association == 0:
                                                separators = [ "(", " ", " ", ") ", " (", " ", " ", ")" ]
                                                arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, separators)
                                            elif association == 1:
                                                separators = [ "( (", " ", " ", ") ", " ", ") ", " ", "" ]
                                                arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, separators)
                                            elif association == 2:
                                                separators = [ "", " ", " (", " ", " ", ") ", " ", "" ]
                                                arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, separators)
                                            elif association == 3:
                                                separators = [ "", "", " (", "", " (", "", "", ") )" ]
                                                arrAnswer[intCurrResult] = ExpressionForDisplay(arrTermsDisp, termIndex, operations, separators)

                                        if seenResult[intCurrResult] == False:
                                            seenResult[intCurrResult] = True

    for i in range(1, 101):
        print "%d = %s" % (i, arrAnswer[i])

    print "Done. (%d loop iterations)" % intIterations
    print "Elapsed time: ", (time.time() - datStartTime), " seconds"

if __name__ == "__main__":
    main()