Skip to content

Instantly share code, notes, and snippets.

@Radcliffe Radcliffe/four-fours.py
Last active Aug 23, 2016

Embed
What would you like to do?
Python solver for puzzles like the "Four Fours" puzzle.
# 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))
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.