Solve digits puzzle

solve_digits_puzzle.py

""" Solve a digits puzzle from https://www.nytimes.com/games/digits

TODO: don't duplicate calculations of equivalent commutative operations

Usage example (make 495 from [5, 6, 10, 11, 18, 12]):

python solve_digits_puzzle.py 495 5 6 10 11 18 12

Example of solving a difficult Countdown numbers problem (
https://youtu.be/pfa3MHLLSWI ):

python solve_digits_puzzle.py 952 25 50 75 100 3 6

"""

import argparse
from jutility import util

class DigitsPuzzle:
    def __init__(self, number_list, target):
        self._number_list = number_list
        self._target = target
        self._op_list = [
            lambda x, y: x + y,
            lambda x, y: x - y,
            lambda x, y: x * y,
            lambda x, y: x / y,
        ]
        self._history = []
        self._max_history_len = len(number_list) - 1

    def _too_long(self):
        return (len(self._history) >= self._max_history_len)

    def solve(self):
        if self._too_long():
            return
        for i0 in range(len(self._number_list)):
            n0 = self._number_list[i0]
            self._number_list.remove(n0)
            for i1 in range(len(self._number_list)):
                n1 = self._number_list[i1]
                self._number_list.remove(n1)
                for op in self._op_list:
                    try:
                        n2 = op(n0, n1)
                    except ZeroDivisionError:
                        continue
                    if (n2 <= 0) or (n2 != int(n2)) or self._too_long():
                        continue
                    n2 = int(n2)
                    self._number_list.append(n2)
                    self._history.append([n0, n1, n2])
                    if n2 == self._target:
                        print(self._history)
                        self._max_history_len = len(self._history) - 1
                    self.solve()
                    self._history.pop()
                    self._number_list.remove(n2)
                self._number_list.insert(i1, n1)
            self._number_list.insert(i0, n0)

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("target",       type=int)
    parser.add_argument("number_list",  type=int, nargs="+")
    args = parser.parse_args()
    with util.Timer("DigitsPuzzle.solve"):
        DigitsPuzzle(args.number_list, args.target).solve()