"""
Ever had people present a set of numerical terms and said "How can you get this
specific result when you construct an expression out of these given numerical
terms?". This program is to hard-compute all possible solutions derived from all
possible combinations of a set of terms and a set of binary operators that are
equal to the given target result.
 
Coded for educational and hobbyist purposes only.
"""
 
__author__ = "doug@neverfear.org"
 
import sys, getopt
 
 
available_operators = {
    "s": "-", # Subtraction
    "a": "+", # Addition
    "m": "*", # Multiplication
    "d": "/", # Division
    "e": "**" # Exponentiation
}
 
 
 
def usage(name):
	print "Usage: %s [OPTIONS] TERMS" % name
	print "Options:"
	print "-h  --help              Show this help."
	print "-t  --target TARGET     Set the target result."
	print "-s  --subtraction       Use subtraction."
	print "-a  --addition          Use addition."
	print "-m  --multiplication    Use multiplication."
	print "-d  --division          Use division."
	print "-e  --exponentiation    Use exponentiation."
	print "If no arithmetic operations are specified then -samde is assumed"
	print
 
 
def test(expr, target):
    try:
        return eval(expr) == target
    except: # Protect against things like ZeroDivisionError
        return False
 
def solve(terms, target, operators, expr = None):
    count = 0
    solutions = []
 
    if not expr:
        # Generate the first operation
        for i, a in enumerate(terms):
            for j, b in enumerate(terms):
                    if i != j:
                        newterms = list(terms)
                        newterms.remove(a)
                        newterms.remove(b)
 
                        for operator in operators:
                                newexpr = "%.1f %s %.1f" % (a, operator, b)
                                if newterms:
                                    s, n = solve(newterms, target, operators, newexpr)
                                    count += n
                                    solutions += s
                                else:
                                    count += 1
                                    if test(newexpr, target):
                                        solutions.append(newexpr)
 
    else:
        # Combine another term into the existing expression
        for a in terms:
            newterms = list(terms)
            newterms.remove(a)
 
            for operator in operators:
 
                expressions = ["(%s) %s %.1f" % (expr, operator, a),
                               "%.1f %s (%s)" % (a, operator, expr)]
 
                if newterms:
                    for expression in expressions:
                        s, n = solve(newterms, target, operators, expression)
                        count += n
                        solutions += s
                else:
                    for expression in expressions:
                        count += 1
                        if test(expression, target):
                            solutions.append(expression)
 
    return (solutions, count)
 
 
 
 
operators = []
 
terms  = []
target = None
try:
    opts, args = getopt.getopt(sys.argv[1:], "ht:samde",
                                            ["help",
                                             "target=",
                                             "subtraction",
                                             "addition",
                                             "multiplication",
                                             "division",
                                             "exponentiation"])
except getopt.GetoptError, err:
    print str(err)
    usage(sys.argv[0])
    sys.exit(2)
 
for name, value in opts:
    if   name == "-h":
        usage(sys.argv[0])
        sys.exit(0)
 
    elif name in ["-s", "-a", "-m", "-d", "-e"]:
        operators.append(available_operators[name[1]])
 
    elif name in ["--subtraction", "--addition", "--multiplication",
                  "--division", "--exponentiation"]:
        operators.append(available_operators[name[2]])
 
    elif name in ("-t", "--target"):
        try:
            target = float(value)
        except:
            print "Invalid target", value
            sys.exit(3)
 
 
if target is None:
    print "No target given"
    usage(sys.argv[0])
    sys.exit(4)
 
 
for arg in args:
    try:
        terms.append(float(arg))
    except:
        print "Invalid term", arg
        sys.exit(5)
 
 
if not terms:
    print "No terms given"
    usage(sys.argv[0])
    sys.exit(6)
 
if not operators:
    operators = available_operators.values()
 
 
(solutions, count) = solve(terms, target, operators)
 
print count, "combinations tested and found", len(solutions), "solutions"
print "Solutions:"
format = "Solution #%%-%dd: %%s" % (len(str(len(solutions))))
for i, solution in enumerate(solutions):
    print format % (i + 1, solution)