NYT Digits Solver

README.md

About

This is a program that tries to solve the New York Times Digits game

Usage:

usage: digits_solver [-h] number number number number number number number

NYTimes Digits Solver

positional arguments:
  number      target, followed by all 6 candidates

options:
  -h, --help  show this help message and exit

digits_solver

#!/usr/bin/env python3

import argparse

from collections import deque
from typing import List


class Solver(object):
    def __init__(self, target: int, candidates: List[int]) -> None:
        self.target = target
        self.candidates = candidates

        # Each entries in the queue would be a list of tuples in the form of (number, path)
        # `[(3, "1 + 2"), (7, "4 + 3")]` for example,
        self.queue = deque()
        self.seen = set()
        self.solutions = set()

    def solve(self):
        # Generate the starting point for searcing
        # Starting numbers and the number itself as the path
        self._bfs([(num, str(num)) for num in self.candidates])
        while self.queue:
            self._bfs(self.queue.popleft())
    
    def _bfs(self, node: List[tuple[int, str]]):
        # Sort the list by the numbers
        current = sorted(node, key=lambda t: t[0])
        nums = tuple(num for num, _ in current)

        if nums in self.seen:
            return

        self.seen.add(nums)
        for i in range(len(current) - 1):
            num1, path1 = current[i]
            for j in range(i + 1, len(current)):
                num2, path2 = current[j]

                base = [val for index, val in enumerate(current) if index not in (i, j)]

                neighbors = [
                    (num1 + num2, f'({path1}) + ({path2})'),
                    (num1 * num2, f'({path1}) * ({path2})'),
                ]
                
                # Only positive numbers are allowed in the game
                if num2 != num1:
                    neighbors.append((num2 - num1, f'({path2}) - ({path1})'))

                # Only whole numbers are allowe in the game
                if num1 != 0 and num2 % num1 == 0:
                    neighbors.append((int(num2 / num1), f'({path2}) / ({path1})'))
                
                for t in neighbors:
                    num, path = t

                    # Search only if we are not at target
                    if num != self.target:
                        self.queue.append(base + [t])
                        continue

                    # No need to output if we have already seen this solution
                    if path in self.solutions:
                        continue
                    
                    # Print and add the solution to cache if we are seeing it for the first time
                    print(path)
                    self.solutions.add(path)

            
def main():
    parser = argparse.ArgumentParser(description='NYTimes Digits Solver')
    parser.add_argument('numbers', metavar='number', type=int, nargs=7, help='target, followed by all 6 candidates')
    args = parser.parse_args()

    target, *digits = args.numbers
    Solver(target, digits).solve()
        
    
if __name__ == '__main__':
    main()