# This Python 3 script solves the "Four Fours" problem and similar problems.

# The example at the end of the script generates all combinations of [2,3,5,7]
# that equal 10, using the operations of addition, subtraction, multiplication,
# and division.

# Exact arithmetic is used. Only integer exponents between -99 and 99 are allowed.

from fractions import Fraction

def partitions(lst):
    def part(lst):
        if len(lst) == 1:
            yield (lst, [])
        else:
            first = lst[:-1]
            last = lst[-1:]
            for A, B in part(first):
                yield (A + last, B)
                yield (A, B + last)

    for A, B in part(lst):
        if len(A) > 0 and len(B) > 0:
            yield A, B


def generate(lst):
    if len(lst) == 1:
        x = lst[0]
        yield Fraction(x), str(x)
    else:
        for A, B in partitions(lst):
            for x, sx in generate(A):
                for y, sy in generate(B):
                    yield x+y, "(%s + %s)" % (sx, sy)
                    yield x-y, "(%s - %s)" % (sx, sy)
                    yield y-x, "(%s - %s)" % (sy, sx)
                    yield x*y, "(%s * %s)" % (sx, sy)
                    if y != 0:
                        yield x/y, "(%s / %s)" % (sx, sy)
                    if x != 0:
                        yield y/x, "(%s / %s)" % (sy, sx)
                    if abs(y) < 100 and y == int(y) and (x != 0 or y > 0):
                        yield x**y, "(%s ^ %s)" % (sx, sy)
                    if abs(x) < 100 and x == int(x) and (y != 0 or x > 0):
                       yield y**x, "(%s ^ %s)" % (sy, sx)


if __name__ == "__main__":
    for n, s in generate([2,3,5,7]):
        if n == 10:
            print ("%s = %s" % (n, s))

""" Expected output:

10 = (((2 ^ 3) - 5) + 7)
10 = (7 - (5 - (2 ^ 3)))
10 = ((2 + (3 * 5)) - 7)
10 = ((7 - (2 + 3)) * 5)
10 = (((2 ^ 3) + 7) - 5)
10 = (((3 ^ 2) - 7) * 5)
10 = (((7 - 2) - 3) * 5)
10 = (((7 - 2) * 3) - 5)
10 = (5 / ((7 / 2) - 3))
10 = (((3 + 7) / 2) + 5)
10 = (((7 - 3) - 2) * 5)
10 = (5 / (2 / (7 - 3)))
10 = (((7 - 3) / 2) * 5)
10 = ((2 + 3) * (7 - 5))
10 = ((2 ^ 3) - (5 - 7))
10 = ((2 ^ 3) + (7 - 5))
10 = ((7 - 3) / (2 / 5))
10 = ((5 / 2) * (7 - 3))
10 = ((2 - 7) * (3 - 5))
10 = ((2 - 7) + (3 * 5))
10 = ((7 - 2) * (5 - 3))
10 = ((3 * 5) - (7 - 2))
10 = (2 * ((3 - 5) + 7))
10 = (2 * (7 - (5 - 3)))
10 = (2 + ((3 * 5) - 7))
10 = (2 - (7 - (3 * 5)))
10 = (2 * ((3 + 7) - 5))
10 = (((7 - 3) * 5) / 2)
10 = (2 * (3 - (5 - 7)))
10 = (2 - ((5 - 7) ^ 3))
10 = (2 * (3 + (7 - 5)))
10 = (2 + ((7 - 5) ^ 3))
"""