New York Times' Digits Game Solver

Question

I wrote an algorithm to solve the New York Times' Puzzle: Digits.
You could play the game here.

The rules of the game are as follow:
You were given 6 numbers and you could use simple operations (plus, minus, multiply, and divide) to reach a specific number given by the problem.
You DO NOT need to use all 6 number and you can not create negative and non-integer number.
Everything else is fair game.

The code I implemented uses Python to test all possibilities and compare it to the answer. I uses threading to branch out for all the possibilities and store the thread in a deque and only actually compute them when there's computing space.

Perhaps there's better way to do it?

Please help see if there's thing I could do to make it faster, easier to read, or more pythonic.

from itertools import combinations
import threading
import time
from collections import deque


class DigitSolver():
  def __init__(self,starting_digits:list,target_digit:int):
    """
    starting_digits is a list of integers that are given in the start position
    target_digit is the target integer for the game.
    """
    self.starting_digits = starting_digits
    self.target_digit = target_digit
    self.que = deque()

        
  def __simplify__(self,l:list, target:int, step:list):
    """
    l is a list of all integer at a postion of the game. the list could be of any length
    step are the step must take to a position. the init state should be empty.
    """
    def make_thread_n_que(base_list:list, new_num:int, target_num:int
                         , step:list, op:str,old_n1:int,old_n2:int):
      t = threading.Thread(target=self.__simplify__, args = (base_list + [new_num], 
                              target_num,
                              step + ["{}{}{}".format(old_n1,op,old_n2)]),
                              daemon=True)
      self.que.append(t)
      return
  
    
    def pretty_print( step:list,op:str,n1:int,n2:int):
      print("solution found:",*step + ["{}+{}".format(n1, n2)],sep="\n")
      return
  
    
    if len(l) == 1:
      return
    for index1, index2 in combinations(range(len(l)), 2):
      templist = l[:]
  
      # pop the number in the back first to prevent incorrect index.
      if index1 > index2:
        n1, n2 = templist.pop(index1), templist.pop(index2)
      else:
        n2, n1 = templist.pop(index2), templist.pop(index1)
  
      # switch order so n1 > n2.
      if n2 > n1:
        n1, n2 = n2, n1
  
      # case1 (addition)
      add = n1 + n2
      if add == target:
        pretty_print(step,"+",n1,n2)
        return
      else:
        make_thread_n_que(templist,add,target,step,"+",n1,n2)
  
      # case 2 (multiplication)
      multiply = n1 * n2
      if multiply == target:
        pretty_print(step,"×",n1,n2)
        return
      else:
        make_thread_n_que(templist,multiply,target,step,"×",n1,n2)
  
      # case 3 (subtraction)
      subtract = n1 - n2
      if subtract == target:
        pretty_print(step,"−",n1,n2)
        return
      else:
        make_thread_n_que(templist,subtract,target,step,"−",n1,n2)
      
      # case 4 (full division) (ignore non full division)
      divide, reminder = divmod(n1, n2) if n2 != 0 else (1,1)
      if reminder:
        continue
      if divide == target:
        pretty_print(step,"÷",n1,n2)
        return
      else:
        make_thread_n_que(templist,divide,target,step,"÷",n1,n2)

  
  def solve(self):
    """
    call the function to start solving the puzzle
    """
    self.__simplify__(self.starting_digits, self.target_digit, [])
    while self.que:
      if threading.active_count() < 900:
        self.que.popleft().start()
      else:
        time.sleep(0.1)


if __name__ == "__main__":
    # this is a demo of the code
    # feel free to try with different numbers.
    solver = DigitSolver([8,11,13,18,23,24],407)
    solver.solve()

Answer 1

Is threading necessary? If my math is correct, there are only 946680 possible expressions. Processing that many relatively simple things is a small job for Python (my guess is less than 5 sec on my old computer). That's plenty fast for me on a problem like this, but perhaps your goals are higher than that.

Does threading help? In the abstract, my guess is not too much and it might hurt, because this is entirely a compute-bound problem. In the specific case of your current implementation, threading is definitely hurting, because you've implemented threading in an unusual way. It looks like you're creating lots of threads (maybe a thread per candidate expression), storing the threads in a deque, and starting threads whenever the thread-count is less than 900. That's not a standard approach to threading, at least in my experience, and it seems likely to generate a lot of cost in thread-management overhead. Here's a place to start learning more about how to use threading effectively.

The algorithm is too complex. I confess to not figuring out every detail in the current code. When I ran your example, the program seems to be printing out solutions, but they also seem to be endlessly repeating, so I suspect there is a bug. As best I can tell, you are generating combinations of index numbers and using those to get the needed expression terms. You also have four blocks of nearly-equivalent code to handle each of the arithmetic operations. My suggestion is that you start from scratch -- it happens to everyone!

A simpler approach: define the operations as data. If we put the arithmetic operations in a data structure, we will have all of the expression terms (numbers and operators) in the form of data that we should be able to crank through the functions provided by itertools to produce every possible expression.

import operator

OPERATIONS = {
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    '/': operator.truediv,
}

A simpler approach: combine every number ordering with all possible arrangements of the operators. The itertools library will do the work over five nested, but simple, for-loops:

from itertools import combinations, permutations, product

def generate_expressions(xs):
    for size in range(2, len(xs) + 1):
        for combo in combinations(xs, size):
            for xs_tup in permutations(combo):
                for ops_tup in product(OPERATIONS, repeat = size - 1):
                    yield build_expression(xs_tup, ops_tup)

def build_expression(xs, ops):
    # Temporary implementation.
    return (xs, ops)

A more flexible approach: print only at the outer layer. At this point, we already have a working program that we can assess. Because the algorithm contains no side effects, it's easy for us to take the data emitted by the code and count the number of items. Since the number is less an a million, my advice is to proceed with brute force, not worrying yet (or maybe ever) about either micro-optimizing or the complexities of parallelism.

import sys

def main(args):
    xs = [8, 11, 13, 18, 23, 24]
    target = 407
    exprs = tuple(generate_expressions(xs))
    print(len(exprs))   # 946680

if __name__ == '__main__':
    main(sys.argv[1:])

Consider a data object. What should build_expression() return? It could give us the numbers and operators woven together as a sequence of expression terms: (1, '+', 2, '*', 3, ...). But we also want to know the arithmetic result. And in other contexts, we might want to see the expression terms as a formatted string. That's a good use case for a simple data object.

from dataclasses import dataclass

@dataclass(frozen = True)
class Expression:
    terms: tuple
    val: int

    def __str__(self):
        return ' '.join(str(t) for t in self.terms)

Retaining only the expressions that equal the target. That's an easy filtering function sitting between main() and generate_expressions().

def main(args):
    ...
    exprs = tuple(generate_solutions(xs, target))
    ...

def generate_solutions(xs, target):
    for e in generate_expressions(xs):
        if e.val == target:
            yield e

What's left: building an expression. The function should take the numbers and ops, weave them together into a sequence of terms, compute the value, and return an Expression instance.

def build_expression(xs, ops):
    terms = tuple(...)  # Take a look at itertools.zip_longest().
    return Expression(terms, calculate(terms))

def calculate(terms):
    val = None
    func = None
    for t in terms:
        ...
    return val

Answer 2

This puzzle is very similar to problems such as the Knight's Tour and the n-queens problem. Backtracking is a popular algorithm to solve these sorts of combinatorial puzzles. I would look into this algorithm which may make your code "faster, easier to read, or more pythonic", although I have done little work in Python.

Your code also does not account for potentially multiple solutions for a set of integers and target number. Perhaps you may want to have this feature for your specific needs.

Relying on an arbitrary number like 900 for the active thread count and timing out each thread for 0.1 seconds depending on certain conditions is like a band-aid trying to compensate for confusing logic. I would consider a different algorithm.

Nonetheless, your program's entry point makes it very obvious what the program is doing:

solver = DigitSolver([8,11,13,18,23,24],407)
solver.solve()

is very nice to read.