Skip to content

Instantly share code, notes, and snippets.

@hickford hickford/numbers-game.py
Last active Aug 29, 2015

Embed
What would you like to do?
How to make 21 from the numbers 1,5,6,7?
#!python
import operator
import itertools
from fractions import Fraction
operations = dict()
operations['+'] = operator.add
operations['-'] = operator.sub
operations['/'] = operator.truediv
operations['*'] = operator.mul
def solve(target, numbers):
"""List ways to make target from numbers."""
numbers = [Fraction(x) for x in numbers]
return solve_inner(target, numbers)
def solve_inner(target, numbers):
if len(numbers) == 1:
if numbers[0] == target:
yield str(target)
return
# combine a pair of numbers with an operation, then recurse
for a,b in itertools.permutations(numbers, 2):
for symbol, operation in operations.items():
try:
product = operation(a,b)
except ZeroDivisionError:
continue
subnumbers = list(numbers)
subnumbers.remove(a)
subnumbers.remove(b)
subnumbers.append(product)
for solution in solve_inner(target, subnumbers):
# expand product (but only once)
yield solution.replace(str(product), "({0}{1}{2})".format(a, symbol, b), 1)
if __name__ == "__main__":
numbers = [1, 5, 6, 7]
target = 21
solutions = solve(target, numbers)
for solution in solutions:
print("{0}={1}".format(target, solution))
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.