Skip to content

Instantly share code, notes, and snippets.

@Radcliffe
Last active Sep 28, 2021
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 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))
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment