Solver for the game 24

twentyfour.py

#!/usr/bin/env python
#
# Plays the game 24: Given 4 numbers that must each be used exactly once, and
# the four basic arithmetic operators (addition, subtraction, multiplication,
# division) than may be used any number of times, finds an expression that
# evaluates to 24.
#
# Copyright 2012 Chris Hiszpanski. All rights reserved.
#
# History:
# Feb 26 2022  Chris Hiszpanski  Fix precision issue.

def solve(numbers, target=24):
    """Find expression of numbers and arithmetic operators which equal target

    Arguments:
        numbers : 4-tuple of numbers to solve
        target : the number to solve for

    Returns:
        String express using 4-tuple which evaluates to 24; None if no solution.

    """
    from itertools import permutations, product
    import operator

    assert 4 == len(numbers)

    # Define a decimal division operator which raises no exceptions
    add = lambda x,y: operator.add(x,y) if (None != x and None != y) else None
    sub = lambda x,y: operator.sub(x,y) if (None != x and None != y) else None
    mul = lambda x,y: operator.mul(x,y) if (None != x and None != y) else None
    div = lambda x,y: operator.truediv(x,y) if (None != x and y) else None

    sgn = lambda z: "+" if add==z else "-" if sub==z else "*" if mul==z else "/"

    operators = ( add, sub, mul, div )

    # Iterate through permutations of four numbers
    for (a, b, c, d) in permutations(numbers):

        # Iterate through left, center, and right operator combinations
        for (lop, cop, rop) in product(operators, repeat=3):

            # Test five possible groupings
            params = (a, sgn(lop), b, sgn(cop), c, sgn(rop), d)
            if abs(target - rop(cop(lop(a, b), c), d)) < 0.0000001:
                return ("((%i %s %i) %s %i) %s %i" % params)
            elif abs(target - rop(lop(a, cop(b, c)), d)) < 0.0000001:
                return ("(%i %s (%i %s %i)) %s %i" % params)
            elif abs(target - cop(lop(a, b), rop(c, d))) < 0.0000001:
                return ("(%i %s %i) %s (%i %s %i)" % params)
            elif abs(target - lop(a, rop(cop(b, c), d))) < 0.0000001:
                return ("%i %s ((%i %s %i) %s %i)" % params)
            elif abs(target - lop(a, cop(b, rop(c, d)))) < 0.0000001:
                return ("%i %s (%i %s (%i %s %i))" % params)

    return None

if __name__ == '__main__':
    from sys import argv, exit

    if (len(argv) is not 5):
        print 'usage: twentyfour a b c d'
        exit(-1)

    print solve([ int(i) for i in argv[1:] ])