24 Puzzles

2017-03-08 • , • Comments

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()