(NOTE: As of August 18, 2023 the NYT Digits puzzle has been removed the the NYT website. A copy of the game has been reproduced on a new private site: https://engaging-data.com/digitsgame/)
About a month ago, I started playing a new puzzle from the New York Times. The puzzle setup is simple. You are given six numbers and a target number, and you are supposed to reproduce the target number from any combination from the set of six numbers using the operations addition, subtraction, division, and multiplication. In combining numbers, divisions cannot have remainders and subtractions cannot result in negative numbers. But there is also some leeway in reaching the target. You get the maximum three points if you reach the target, two points if you’re at most 10 integer steps from the target, and one point if you’re 25 steps from the target.
There are six such puzzles each day, with target numbers increasing from a number between 50 and 100 to higher than 400. Here is one puzzle from Friday June 2nd.
One solution for this puzzle is
$$ ((23 \times 3) – 20)\times9 = 441. $$
In general finding a solution involves a trial-and-error approach of combining various numbers with the available operations until one reaches the target value. The approach is inherently combinatorial which suggests there is likely a combinatorial algorithm which would allow us to find all solutions to the puzzle.
The current post will walk through the programming (i.e., the incremental programming and the recursion) of building up the algorithm. In a second post, we will discuss the mathematics (i.e., generating functions, Catalan numbers, and computational complexity) that exists at the background.
If you just want the full algorithm for the puzzle, go to the bottom of this page. [Here]
Incremental Solutions
The general approach to finding all solutions to the puzzle is to generate all possible valid combinations of the numbers and then filter for the combinations that lead to the target. All operations consist of combining a pair of numbers at a time, so the final solution would consist of some repeated pairing of numbers through various operations. Thus, the general strategy is to
Find all the ways to combine a pair of numbers
Find all the ways to combine numbers in pairs out of a set of \(N\) numbers (where \(N=6\) for the NYT digits game.)
To start I tried to begin with just two numbers. Starting small is a basic precept of incremental programming. Rather than attempting to build a complete program outright, you start with a small piece that you test, and then later build on top of. For two numbers, there are at most four possible combinations that we can form from the four possible operations. For example, if we have the numbers 9 and 3, the four possible combinations of these numbers are
$$ 9+3, \quad 9-3, \quad 9\times 3, \quad 9/3. $$
To find a solution we would want to generate these combinations and keep track of the operations that led to them. Thus, while we combine various integers, we also want to do parallel combinations of their strings to represent the combinations. We use a dictionary to store this data to separate the integer names from the integers themselves. For example,
value_dict = {'1': 2, '2': 2}
And the function that performs the parallel combinations both in string space and integer space is
def gen_two_combos(value_dict):
# sort dictionary by value to ensure subtractions are not negative
# and divisions are greater than 1
sorted_vals = dict(sorted(value_dict.items(), key=lambda item: item[1], reverse=True))
# access the list of string names and the list of associated integers
name_list, num_list = list(sorted_vals.keys()), list(sorted_vals.values())
# for writing simplicity
elem1, elem2 = num_list
name1, name2 = name_list
# generating all combinations
# internal if conditional yields a small decimal number if the division
# and subtraction constraints are violated
combo_dict = {'('+name1+'+'+name2+')':elem1 + elem2,
'('+name1+'*'+name2+')':elem1 * elem2,
'('+name1+'/'+name2+')': int(elem1/elem2) if elem1%elem2==0 else 1/3001,
'('+name1+'-'+name2+')': elem1- elem2 if elem1- elem2>0 else 1/3001 }
return combo_dict
As an example we can apply this function to the value_dict defined above.
We note that we have included conditions within the the gen_two_combos function that result in one divided by a large prime number when the non-negative or zero-remainder conditions are violated. This is to ensure these results are not chosen as combinations paths for future numbers [1].
Next, we can extend this approach to combining two numbers to a combination of three numbers. In this case, we will use the gen_two_combos function internally both before and after finding various ways to split the two numbers into two groups. This is best seen through example.
Say we have three numbers 1, 2, and 3. What are the various ways we can combine these numbers using our four operations? We know there are four ways to combine two numbers, so to find the various ways to combine three numbers, we can first ask how can we form two numbers from three numbers. If we select two numbers 1 and 2 and add them, then we would have the number 3 in addition to the original unselected 3. In other words, we would have two numbers. We can then combine this new 3 and the old 3 in all the ways that two numbers can be combined.
Thus the various ways to combine three numbers consists of the various ways to select two numbers from three, crossed with the various ways to combine those two selected numbers, and finally crossed with the ways to combine the result of the two-number combinations with the third unselected number. Written in code this is
def gen_three_combos(start_dict):
# empty dictionary to house combo outputs
output_dict = dict()
for key, value in start_dict.items():
# define copy of three number combination
copy_dict = start_dict.copy()
del copy_dict[key] # eliminate one number from the three
# for all combinations of the two remaining numbers
for name, elem in gen_two_combos(copy_dict).items():
# create combinations of the two-number result and the unselected number
new_dict = {name: elem, key:value }
result_dict = gen_two_combos(new_dict)
output_dict.update(result_dict)
return output_dict
Applying this function to the dictionary {'1': 2, '2': 2, '3', 3}, we have
The decimal results arise from invalid number combinations (e.g., 3/2 has a remainder). What we have done in our definition of gen_three_combos is known as recursion in computer science. We wrote a solution in terms of its lower order versions. This approach can be generalized to gen_four_combos in a similar way:
from itertools import combinations
def gen_four_combos(start_dict):
output_dict = dict()
# split four numbers into three numbers and one number
for key, value in start_dict.items():
copy_dict = start_dict.copy()
del copy_dict[key]
for name, elem in gen_three_combos(copy_dict).items():
new_dict = {name: elem, key:value }
result_dict = gen_two_combos(new_dict)
output_dict.update(result_dict)
# split four numbers into two numbers and two numbers
for elem in list(combinations((start_dict.keys()), 2)):
copy_dict = start_dict.copy()
del copy_dict[elem[0]]
del copy_dict[elem[1]]
comp_copy_dict = {elem[0]:start_dict[elem[0]], elem[1]:start_dict[elem[1]]}
for key1, value1 in gen_two_combos(copy_dict).items():
for key2, value2 in gen_two_combos(comp_copy_dict).items():
new_dict = {key1: value1, key2:value2 }
result_dict = gen_two_combos(new_dict)
output_dict.update(result_dict)
return output_dict
The one new addition in gen_four_combos is that in the final code block, we use the combinations function to generate all the ways to select two numbers from four numbers. Listing these selections allows us to systematically go through each one and combine the numbers using the lower order gen_two_combos function. We also combine the two unselected numbers (comprising comp_copy_dict) and finally combine the result of the two combinations [2].
Generating All Combinations
So far we have applied both incremental programming and recursion to build up an algorithm that lists the possible ways to combine sets of numbers using the four standard operations. Specifically, we incrementally extended beyond the gen_two_combos case towards the gen_three_combos and gen_four_combos cases all the while recursively referring to the lower order solutions in order to build the higher order ones.
Our functions have been written to take in dictionaries with a specific number of key-value pairs, but using the general structure of all the functions we can extrapolate to a more general function that takes in a general dictionary. If properly written, such a function would decompose the dictionary into smaller combination chunks and then recursively refer to itself in order to generate combinations for those chunks and so on. Reviewing the structure of all these functions, we find that the more general way to write them (in a dictionary-length agnostic form) is as
from itertools import combinations
from math import comb
# generates all manipulation combinations of a dictionary of elements
def generator_combos(start_dict: dict):
# defining dict_len to determine pathing
dict_len = len(start_dict)
# defining output dictionary
output_dict = dict()
count = 0
# output the dictionary if there is just one element
if dict_len==1:
output_dict = start_dict
# output all ways to add, subtract, multiply, or divide two numbers
elif dict_len==2:
# sort to ensure division is >= 1 and subtraction is >= 0
sorted_vals = dict(sorted(start_dict.items(), key=lambda item: item[1], reverse=True))
# list of names and numbers
name_list, num_list = list(sorted_vals.keys()), list(sorted_vals.values())
# getting elements and there names
elem1, elem2 = num_list
name1, name2 = name_list
# set of all possible operations with keys for operation name
# Note: digits game doesn't allow fractions or negative numbers
# so we set the result to a large
output_dict = {'('+name1+'+'+name2+')':elem1 + elem2,
'('+name1+'*'+name2+')':elem1 * elem2,
'('+name1+'/'+name2+')': int(elem1/elem2) if elem1%elem2==0 else 1/3001,
'('+name1+'-'+name2+')': elem1- elem2 if elem1- elem2>0 else 1/3001 }
# for dict_len >=3, recursively build sub solutions
else:
# only go up to half the number of elements in dict
# to prevent double counting (e.g., n choose k = n choose n-k)
for ix in range(1, dict_len//2+1):
# number of ways to select 'ix' elements from 'dict_len' total
num_comb = comb(dict_len, ix)
# limiting number of combinations considered
# when there is an even split; this prevents double counting
if ix == dict_len/2:
lim = num_comb//2
else:
lim = num_comb
# generating combinations of elements
# '[:lim]' prevents double consideration of combos
for elem in list(combinations(start_dict.keys(), ix))[:lim]:
copy_dict = start_dict.copy()
comp_copy_dict = dict() # complement of copy_dict
for j in range(ix):
del copy_dict[elem[j]]
comp_copy_dict[elem[j]] = start_dict[elem[j]]
# generating set of possible operations for elements
for key1, value1 in generator_combos(copy_dict).items():
for key2, value2 in generator_combos(comp_copy_dict).items():
new_dict = {key1: value1, key2: value2 }
result_dict = generator_combos(new_dict)
output_dict.update(result_dict)
count += len(result_dict)
return output_dict
There are three things we should explain about this function
Avoiding double counting of combinations: To avoid double counting of combinations, the maximum number of elements we select is always half of the total number of elements. This is because selecting, say, four elements from a set of six is identical to selecting the two unselected elements from that set of six.
Avoiding double counting for even split: To further avoid double counting, when the number of elements we select is exactly half the length of the dictionary, we only select the first half of the total generated combinations of those elements. This is for the same reasons as above; selecting two elements from four elements is the same as selecting the two unselected elements from that four.
Recursive appearance of generator_combos: The function generator_combos appears three times within itself. If we have \(N\) numbers in our dictionary, we split those numbers into a set of \(k\) numbers and a set of \(N-k\) numbers. We then use the first generator_combos to find all ways to combine the set of \(k\) numbers and the second generator_combos to find all ways to combine the set of \(N-k\) numbers. Finally, we use the third generator_combos to find all the ways to combine the results of the first two.
The function generator_combos returns all the ways to combine all the elements of the dictionary start_dict using the operations addition, multiplication, subtraction, and division. The output is a dictionary whose keys are the string representations of the operations and whose values are the results of the operations. For example:
Additionally, we can count the total number of combinations that are possible for various numbers of dictionary elements. For dictionaries whose lengths increase by 1 up to 6, we have
This result will be important in the next post when we consider the mathematics (and computational complexity) underlying this algorithm.
NYT Digits Solver
Our goal was to find a way to solve the NYT digits puzzle. Above, we defined the function generator_combos which creates all the ways to combine a list of numbers using the valid operations. To use this function to solve the NYT digits puzzle, we now need to generate all the possible combinations of the original list of numbers and select the combinations which have a result that matches the target number.
Importantly, we want to list the ways to combine various subsets of numbers. This requires us to run generator_combos on collections of the listed numbers all the while updating a master dictionary soln_set_dict with the running list of solutions. After collecting all the solutions, we can then perform value matching to find the valid solutions.
There are often many solutions to a give puzzle, so as to not be overwhelmed by their number, we include a soln_num argument which, when defined, only selects the shortest solutions.
All of these considerations result in the following function
def nyt_digits_solver(num_list: list, target: int, soln_num=None):
# generating full list of combinations of all sizes for the input numbers
soln_set_dict = dict()
for i in range(2, len(num_list) + 1):
for combo in list(combinations(num_list, i)):
dict_conv = {str(num):num for num in list(combo)}
soln_dict = generator_combos(dict_conv)
soln_set_dict.update(soln_dict)
# enumerating all solutions (i.e., combinations that result in target)
solns = [key for key in soln_set_dict if soln_set_dict[key]==target]
# find the `soln_num`-shortest solutions (by char count)
if soln_num:
solns_copy = list()
for k in sorted(solns, key=len)[:soln_num]:
solns_copy.append(k)
solns = solns_copy
return solns
Now, we can apply the function to the example at the start of this post. For a target of 441 and a list of numbers we found one solution. What other solutions are there? Applying the above created algorithm we find that there are 151 possible solutions (specifically 151 different numbers combinations consisting of operation sequences applied to certain numbers) of this puzzle.
Now, selecting out the ten shortest solutions we have
We see that there is some redundancy in our solutions. Specifically, the penultimate three solutions are distinguished by various pairwise associations of multiplying \(20\times 13 \times 5\) but such a product is invariant under such associations. This is one thing to note about these unique solutions: They do represent unique user operations even if a given net operation has some degeneracy due to associative properties of addition and subtraction.
Ending Remarks
Through the above algorithm, we showed how the NYT digits puzzle could be solved using ideas from incremental programming and recursion. Still, there is more left to uncover about this problem by placing it in a more abstract context. In particular, the number of combinations of our set of numbers is associated with the Catalan numbers
We will show why this is the case in the next post.
Footnotes
[1] Having the result of an invalid combination be “1/(large prime number)” helps ensure that multiplications will not eliminate the fraction and so all subsequent combinations of the number would be decimals that cannot equal the target.
[2] This explanation might have been confusing. We’ll explain it another way in the next post.
One comment on “NYT Digits Puzzle – Incremental Programming and Recursion”
One comment on “NYT Digits Puzzle – Incremental Programming and Recursion”