Solver for NYTimes Digits games. Use with my puzzlesolver gist. EDIT: also handles chain mode now.

nytdigits.py

# MIT License
#
# Copyright (c) 2023 Neil Webber
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included
# in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

# For use with puzzlesolver.py, this models the NYT Digits puzzle

import operator
import itertools


class DigitsPuzzle:

    CHAINMODE = object()                       # sentinel for forced_operand

    def __init__(self, target, *sources, forced_operand=None):
        """Initialize a NYT Digits Puzzle.

        target: the puzzle's ending/target value
        *sources: N integers, the starting numbers for the puzzle
        forced_operand: generalized version of the NYT "chain mode" rule.
           It can take on three different meanings:
             None (default): All source operands are available.

             DigitsPuzzle.CHAINMODE: This is the NYT "chain" mode indicator.
                 All source operands are available for the first move; after
                 that the forced_operand will be the output of the prior move.

             any value f, where "f in sources" is true.
                 f will be forced to be the first operand. This is a
                 generalization of NYT chain mode and also used by clone()
        """

        self.target = target
        self.forced_operand = forced_operand

        # sub and div rely on the sources being in descending order
        self.sources = sorted(sources, reverse=True)

    @property
    def endstate(self):
        return self.target in self.sources

    def clone(self):
        return self.__class__(self.target, *self.sources,
                              forced_operand=self.forced_operand)

    def _sourcecombos(self):
        """Generate potential pairs, taking chain mode into account."""

        if self.forced_operand in self.sources:
            # Because forced_operand is being, ummm, forced, it's important
            # not to double-use it from sources. But there's a catch: there
            # might be more than one entry in sources equal to this value.
            # Therefore, take ONE forced_operand value out of the sources
            # and use the result to pair up against it.

            sminus = list(self.sources)
            sminus.remove(self.forced_operand)
            return ((self.forced_operand, b) for b in sminus)
        else:
            return itertools.combinations(self.sources, 2)

    def legalmoves(self):
        # all add/multiply operations are legal
        yield from itertools.product(
            (operator.add, operator.mul), self._sourcecombos())

        # For subtract, the result must be non-negative.
        # NOTE: Don't allow zero to get into sources, because it is
        # pointless but, more importantly, is a problem for later divs.
        for a, b in self._sourcecombos():
            if a > b:
                yield (operator.sub, (a, b))

        # for division, it's only legal if no remainder.
        for a, b in self._sourcecombos():
            if a % b == 0:
                yield (operator.floordiv, (a, b))

    def move(self, m):
        op = m[0]
        a, b = m[1]
        self.sources.remove(a)
        self.sources.remove(b)
        rslt = op(a, b)

        # the code prevents this but here's a sanity check
        assert rslt != 0

        # in chain mode, this must be the next first operand
        if self.forced_operand:
            self.forced_operand = rslt
        self.sources.append(rslt)
        self.sources = sorted(self.sources, reverse=True)

    def canonicalstate(self):
        return tuple(list(self.sources) + [self.forced_operand])


if __name__ == "__main__":
    import unittest

    class TestMethods(unittest.TestCase):
        # these are simpler tests than the typical NYT puzzle
        def test1(self):
            d = DigitsPuzzle(10, 3, 7)
            # there should be three legal moves from this
            # (not four; division doesn't work for 7/3).
            moves = list(d.legalmoves())
            self.assertEqual(len(moves), 3)

        def test2(self):
            d = DigitsPuzzle(10, 3, 7)
            moves = list(d.legalmoves())
            # there should be a subtract move in the legal moves
            # and it has to be (7, 3) not (3, 7)
            self.assertTrue((operator.sub, (7, 3)) in moves)

        def test3(self):
            d = DigitsPuzzle(10, 3, 7)
            moves = list(d.legalmoves())
            # check for the legal add and multiply moves without
            # enforcing that the operands are sorted (because
            # that's an implementation detail not a behavior)

            for op, rands in d.legalmoves():
                if op == operator.add:
                    self.assertTrue(rands in ((3, 7), (7, 3)))
                    break
            else:
                self.assertTrue(False, "didn't find operator.add")

            for op, rands in d.legalmoves():
                if op == operator.mul:
                    self.assertTrue(rands in ((3, 7), (7, 3)))
                    break
            else:
                self.assertTrue(False, "didn't find operator.mul")

        def test4(self):
            d = DigitsPuzzle(10, 3, 14, 2)
            moves = list(d.legalmoves())
            # by inspection there should be 10 moves; there are three
            # combinations each for add/mul/sub plus div is legal 14/2
            self.assertEqual(len(moves), 10)

            # check to see if the div is in there since no prev test was div
            for op, rands in moves:
                if op == operator.floordiv:
                    self.assertEqual(rands, (14, 2))
                    break
            else:
                self.assertTrue(False, "didn't find operator.floordiv")

        def test5(self):
            # chain mode test
            d = DigitsPuzzle(10, 3, 14, 2, 13,
                             forced_operand=DigitsPuzzle.CHAINMODE)

            moves = list(d.legalmoves())
            # there are 19 moves, by inspection (6 add/mul/sub, 1 div)
            self.assertEqual(len(moves), 19)

            # do the 1 division move
            d.move((operator.floordiv, (14, 2)))

            # now every legal move should have the (new) 7 as
            # its first operand, making the legal moves:
            #   add (7, 3)
            #   add (7, 13)
            #   mul (7, 3)
            #   mul (7, 13)
            #   sub (7, 3)
            moves = list(d.legalmoves())
            self.assertEqual(len(moves), 5)
            for m in (
                    (operator.add, (7, 3)),
                    (operator.add, (7, 13)),
                    (operator.mul, (7, 3)),
                    (operator.mul, (7, 13)),
                    (operator.sub, (7, 3))):
                with self.subTest(m=m):
                    self.assertTrue(m in moves)

        def test6(self):
            # another chain mode test verifying the thing where
            # duplicated forced operand values work

            d = DigitsPuzzle(10, 3, 14, 2, 7,
                             forced_operand=DigitsPuzzle.CHAINMODE)

            moves = list(d.legalmoves())
            # there are 20 moves, by inspection (6 add/mul/sub, 2 div)
            self.assertEqual(len(moves), 20)

            # do the division move that makes a 7, which will be
            # a duplicate (i.e., there will be two 7's in sources)
            d.move((operator.floordiv, (14, 2)))

            # now every legal move should have the (new) 7 as
            # its first operand, making the legal moves:
            #   add (7, 3)
            #   add (7, 7)
            #   mul (7, 3)
            #   mul (7, 7)
            #   sub (7, 3)
            #   div (7, 7)
            moves = list(d.legalmoves())
            self.assertEqual(len(moves), 6)
            for m in (
                    (operator.add, (7, 3)),
                    (operator.add, (7, 7)),
                    (operator.mul, (7, 3)),
                    (operator.mul, (7, 7)),
                    (operator.sub, (7, 3)),
                    (operator.floordiv, (7, 7))):
                with self.subTest(m=m):
                    self.assertTrue(m in moves)

    unittest.main()