This is a program that tries to solve the New York Times Digits game
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
| #!/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() |