## 24 Puzzles

On The Universe of Discourse Mark Dominus discusses the classic 24 Puzzle:

You are given a sequence of four digits, say 1, 2, 3, 4, and your job is to combine them with ordinary arithmetic operations (+, -, ×, and ÷) in any order to make a target number, typically 24. For example, with 1, 2, 3, 4, you can go with

`((1+2)+3)×4=24`

or with`4×((2×3)×1)=24`

.

Here’s a solver for such puzzles. It uses `itertools`

to generate possible expressions, `fractions`

to get the arithmetic right, and `eval`

to evaluate expressions. It’s limited to expressions formed from 4 numbers which means I don’t have to programmatically calculate different ways of parenthesising: there are only 5.

# http://blog.plover.com/math/24-puzzle.html import re import math # Use fractions for exact calculations from fractions import Fraction # Solve for 4 numbers only! N = 4 # So these are the only expression templates # where X is a number and @ is an operation templates = '''\ ((X @ X) @ X) @ X (X @ (X @ X)) @ X X @ ((X @ X) @ X) X @ (X @ (X @ X)) (X @ X) @ (X @ X)'''.splitlines() import itertools as its def defrac(s): return re.compile(r'Fraction\((\d+)\)').sub(r'\1', s) def evaluate(nums, ops, template): fracs = ('Fraction(%s)' % n for n in nums) ops = iter(ops) expr = ''.join(next(fracs) if c == 'X' else next(ops) if c == '@' else c for c in template) try: return expr, eval(expr) except ZeroDivisionError: return expr, None def solve(spec, ops): numbers = re.compile(r'\d+').findall(spec) assert len(numbers) == N + 1 result = Fraction(numbers.pop()) seqs = its.product(its.permutations(numbers), its.product(ops, repeat=N-1), templates) print(defrac(next((e for e, v in its.starmap(evaluate, seqs) if v == result), 'Impossible'))) def main(): solve('2,5,6,6 => 17', '+-/*') solve('3,3,8,8 => 24', '+-/*') main()

Here’s a second attempt, which doesn’t assume there will just be 4 numbers on the left hand side of the equation. Given a sequence of numbers and a set of operators, it repeatedly reduces the sequence length by picking pair of numbers and combining them using one of the operators, iterating over all possible ways of doing this. The first sequence of length 1 which equals the target value gives a solution and terminates the search.

# http://blog.plover.com/math/24-puzzle.html from fractions import Fraction import itertools as its import operator import re def pick2(xs): return ((p[:2], p[2:]) for p in its.permutations(xs)) def allow(op, l, r): return op != '/' or eval(r) != 0 def apply(op, l, r): return '(%s%s%s)'%(l, op, r) def values(xs, ops): L = [xs] while L: xs = L.pop() if len(xs) == 1: yield xs.pop() else: L.extend([apply(op, *lr)] + list(tl) for op, (lr, tl) in its.product(ops, pick2(xs)) if allow(op, *lr)) def solve(spec, ops): numbers = ['Fraction(%s)'%n for n in re.compile(r'\d+').findall(spec)] target = eval(numbers.pop()) print(next((v for v in values(numbers, ops) if eval(v) == target), 'Impossible')) def main(): solve('2,5,6,6 => 17', '+-/*') solve('3,3,8,8 => 24', '+-/*') main()