Python solver for puzzles like the "Four Fours" puzzle.

four-fours.py

# 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 partition(lst):
    """Recursively partition a list into two nonempty sublists."""
    head, tail = lst[:1], lst[1:]
    yield head, tail
    if len(lst) > 2:
      for left, right in partition(tail):
          yield head + left, right
          yield left, head + right


def generate(lst):
    if len(lst) == 1:
        x = lst[0]
        yield Fraction(x), str(x)
    else:
        for A, B in partition(lst):
            for x, sx in generate(A):
                for y, sy in generate(B):
                    yield x + y, f'({sx} + {sy})'
                    yield x - y, f'({sx} - {sy})'
                    if sx != sy:
                        yield y - x, f'({sy} - {sx})'
                    yield x * y, f'({sx} * {sy})'
                    if y != 0:
                        yield x / y, f'({sx} / {sy})'
                    if x != 0 and sx != sy:
                        yield y / x, f'({sy} / {sx})'
                    if abs(y) < 100 and y.denominator == 1 and (x != 0 or y > 0):
                        yield x ** y, f'({sx} ^ {sy})'
                    if sx != sy and abs(x) < 100 and x.denominator == 1 and (y != 0 or x > 0):
                       yield y ** x, f'({sy} ^ {sx})'


if __name__ == '__main__':
    for n, s in generate([2, 3, 5, 7]):
        if n == 10:
            print(f'{n} = {s}')

"""

Expected output:

10 = (2 * (3 - (5 - 7)))
10 = (2 - ((5 - 7) ^ 3))
10 = (2 * (3 + (7 - 5)))
10 = (2 + ((7 - 5) ^ 3))
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 = ((5 * (7 - 3)) / 2)
10 = ((2 + 3) * (7 - 5))
10 = ((2 ^ 3) - (5 - 7))
10 = ((2 ^ 3) + (7 - 5))
10 = ((2 + (3 * 5)) - 7)
10 = (((2 ^ 3) - 5) + 7)
10 = (7 - (5 - (2 ^ 3)))
10 = ((3 - 5) * (2 - 7))
10 = ((5 - 3) * (7 - 2))
10 = ((3 * 5) + (2 - 7))
10 = ((3 * 5) - (7 - 2))
10 = ((7 - 3) / (2 / 5))
10 = ((5 / 2) * (7 - 3))
10 = (5 + ((3 + 7) / 2))
10 = (5 * ((7 - 3) - 2))
10 = (5 / (2 / (7 - 3)))
10 = (5 * ((7 - 3) / 2))
10 = (5 * (7 - (2 + 3)))
10 = (((2 ^ 3) + 7) - 5)
10 = (5 * ((3 ^ 2) - 7))
10 = (5 * ((7 - 2) - 3))
10 = ((3 * (7 - 2)) - 5)
10 = (5 / ((7 / 2) - 3))

"""