Arithmetic puzzle solver

digits.py

"""
Arithmetic puzzle solver. 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. E.g. 24 = 1 * 2 * 3 * 4 or 24 = (1 + 2 + 3) * 4.

Some 'hard' problems from https://blog.plover.com/math/17-puzzle.html:
    1. Given 6, 6, 5, 2, get 17.
    2. Given 3, 3, 8, 8, get 24.
"""

import itertools


def apply(f1, op, f2):
    """
    Apply takes two formulas, f1 and f2, each stored as a tuple (value, formula string), and applies op to them,
    returning the result.
    """
    d1, s1 = f1
    d2, s2 = f2
    try:
        return (d1 + d2 if op == '+' else
                d1 - d2 if op == '-' else
                d1 / d2 if op == '/' else
                d1 * d2 if op == '*' else
                None,
                f"({s1} {op} {s2})")
    except (ZeroDivisionError, TypeError):
        return None, None


def combine(formulas):
    """
    Return a list of possible combinations with given formulas.
    """
    return formulas if len(formulas) == 1 else [
        apply(f1, op, f2)
        for op in '+-/*'
        for i in range(1, len(formulas))
        for f1 in combine(formulas[:i])
        for f2 in combine(formulas[i:])
    ]


TOLERANCE = 1e-6


def find(digits, number):
    formula = next(x[1]
                   for scrambled in itertools.permutations(digits, len(digits))
                   for x in combine([(x, str(x)) for x in scrambled])
                   if x[0] is not None and abs(x[0] - number) < TOLERANCE)
    print(f"{number} = {formula}")


find([6, 6, 5, 2], 17)  # 17 = (6 * ((5 / 6) + 2))
find([6, 6, 5, 2], 24)  # 24 = (6 + (6 * (5 - 2)))
find([3, 3, 8, 8], 24)  # 24 = (8 / (3 - (8 / 3)))