As of August 8, the New York Times game Digits is no more. Digits was a game where you were given a target number and six smaller numbers. Combining the smaller numbers with the four basic arithmetic operators, you would try to produce the target number. (Read more about it on this Verge article.)
The game is over, so spoilers are moot. Why not write a solver?
First, let’s explore the solution landscape. You have six numbers which can be combined two at a time with addition (+), subtraction (-), multiplication (*), and division (/). Each step reduces the count of remaining numbers by one. The last binary operation would happen when two numbers are left; at that point if you get the target number, you have followed the longest possible solution path.
An example would be handy right about now. Let’s say the target is 9 and you are given 1, 2, 3, 4, 5, 6 to start with. You could follow these steps:
- 6 + 1 = 7; remaining: 2, 3, 4, 5, 7
- 5 * 2 = 10; remaining: 3, 4, 7, 10
- 4 + 3 = 7; remaining: 7, 7, 10
- 7 / 7 = 1; remaining: 1, 10
- 10 – 1 = 9; target achieved!
(There is of course a much shorter solution, 6 + 3 = 9, but where’s the fun in taking the easy path?)
We should also mention some constraints: the game disallows fractions, negative numbers, and division by zero. This means that when we consider pairs of numbers for our operations, we need not care about order. We’ll just always choose the larger number first so that any operator we apply could produce a potentially valid result (noting that division may still steer us wrong — but we’ll handle that later).
To count how many possible paths there are in general, we need to consider all combinations of two operands for every path length. Out of six distinct numbers, there are 6 C 2 = 6!/((6-2)!2!) = 6*5/2 = 15 combinations. Out of five numbers, we have 5*4/2 = 10 combinations. Then 4*3/2 = 6, 3*2/2 = 3, and finally 2*1/2 = 1. This means that there are 15*10*6*3*1 = 2700 operand combinations for the longest solution path. For the operators we have four choices, so we have to quadruple the number of combinations at each step: 2700 * 4^5 = 2,764,800. For a four-step solution, we’d omit the fifth step combinations, 2700 * 4^4 = 691,200. Similarly, three steps have 57,600 possibilities, two steps have 2400, and one step has only 60. Altogether we have 3,516,060 potential solutions!
Clearly that’s way too many possibilities to explore by hand. Programmatically, how could we approach this? We’ll definitely need to generate move combinations, track our number list at each step, and detect if we should move ahead or not.
Let’s start with move generation. We need two indexes and an operator, which sounds like a job for a record type. We also need some sort of enumerator to hand out all the combinations given a path length. This could work in a pinch:
public record Move(int I1, int I2, char Op)
{
public static IEnumerable<Move> Generate(int length)
{
for (int i1 = 0; i1 < length; ++i1)
{
for (int i2 = i1 + 1; i2 < length; ++i2)
{
foreach (char op in Ops.All)
{
yield return new Move(i1, i2, op);
}
}
}
}
}
For quick prototyping, we have defined the operations as characters:
public static class Ops
{
public const char Add = '+';
public const char Subtract = '-';
public const char Multiply = '*';
public const char Divide = '/';
public static readonly IEnumerable<char> All = new[] { Add, Subtract, Multiply, Divide };
}
A board is fairly simple — it’s just a list of numbers with some basic operations:
public sealed class Board
{
private const int InvalidNumber = -1;
private static readonly Board Invalid = new(Enumerable.Empty<int>());
private readonly int[] _numbers;
public Board(IEnumerable<int> numbers)
{
_numbers = numbers.ToArray();
}
public bool IsValid => _numbers.Length > 0;
public int Count => _numbers.Length;
public bool HasTarget(int target) => _numbers.Contains(target);
}
We’ll use -1 as a sentinel for an invalid number (e.g., if we attempt to divide by 0) and an empty list for an invalid board. Now to make a move, we have to calculate the tentative result, remove the operands involved, and generate a new reduced board:
public Board TryMove(Move move)
{
int result = Calculate(move);
if (result == InvalidNumber)
{
return Invalid;
}
var numbers = new List<int> { result };
for (int i = 0; i < _numbers.Length; i++)
{
if (i != move.I1 && i != move.I2)
{
numbers.Add(_numbers[i]);
}
}
numbers.Sort();
return new Board(numbers);
}
private int Calculate(Move move)
{
int n1 = _numbers[move.I1];
int n2 = _numbers[move.I2];
return move.Op switch
{
Ops.Add => n2 + n1,
Ops.Subtract => n2 - n1,
Ops.Multiply => n2 * n1,
Ops.Divide => Divide(n2, n1),
_ => InvalidNumber,
};
}
private int Divide(int n, int d)
{
if (d == 0)
{
return InvalidNumber;
}
(int div, int rem) = Math.DivRem(n, d);
return rem == 0 ? div : InvalidNumber;
}
Good enough. Now the solver just needs to piece these elements together and recursively explore the whole solution space:
public sealed class Solver
{
private readonly int _target;
private readonly Board _board;
public Solver(int target, Board board)
{
_target = target;
_board = board;
}
public void Solve(Action<IList<Move>> found) => Solve(_board, Enumerable.Empty<Move>(), found);
private void Solve(Board current, IEnumerable<Move> previous, Action<IList<Move>> found)
{
if (current.HasTarget(_target))
{
found(previous.ToList());
return;
}
foreach (Move move in Move.Generate(current.Count))
{
Board nextBoard = current.TryMove(move);
if (nextBoard.IsValid)
{
var next = previous.ToList();
next.Add(move);
Solve(nextBoard, next, found);
}
}
}
}
Here we use a callback strategy, passing the current list of moves as we visit each valid solution.
The final integration app boils down to a few dozen lines:
internal sealed class Program
{
private static readonly Stopwatch Time = Stopwatch.StartNew();
public static void Main(string[] args)
{
try
{
var parsed = Args.Parse(args);
var board = new Board(parsed.Numbers);
var solver = new Solver(parsed.Target, board);
Log($"Finding solutions for target={parsed.Target}, board=[{board}]...");
solver.Solve(ms => PrintSolution(board, ms));
Log("Done.");
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
}
private static void Log(string message) => Console.WriteLine("[{0:000.000}] {1}", Time.Elapsed.TotalSeconds, message);
private static void PrintSolution(Board board, IList<Move> moves)
{
foreach (Move move in moves)
{
Console.Write(board.ToString(move) + ". ");
board = board.TryMove(move);
}
Console.WriteLine();
}
}
We can try a board which should have only a few solutions to test the app:
> .\Digits.App.exe 415 1 2 3 4 5 6 [000.000] Finding solutions for target=415, board=[1,2,3,4,5,6]... 6 * 2 = 12. 4 + 3 = 7. 12 * 7 = 84. 84 - 1 = 83. 83 * 5 = 415. 4 + 3 = 7. 6 * 2 = 12. 12 * 7 = 84. 84 - 1 = 83. 83 * 5 = 415. 4 + 3 = 7. 7 * 2 = 14. 14 * 6 = 84. 84 - 1 = 83. 83 * 5 = 415. 4 + 3 = 7. 7 * 6 = 42. 42 * 2 = 84. 84 - 1 = 83. 83 * 5 = 415. 4 * 3 = 12. 12 + 2 = 14. 14 * 6 = 84. 84 - 1 = 83. 83 * 5 = 415. [000.440] Done.
I can’t be certain, but this seems like all the solutions there would be. The whole app including the console output took less than half a second, which is pretty good! But let’s write a benchmark and get some more precise measurements:
[MemoryDiagnoser]
public class SolverBenchmark
{
private readonly Solver _solver;
public SolverBenchmark()
{
_solver = new Solver(415, new Board(Enumerable.Range(1, 6)));
}
[Benchmark]
public int Solve()
{
int n = 0;
_solver.Solve(ms => n += ms.Count);
return n;
}
}
The results raise a few concerns:
| Method | Mean | Error | StdDev | Gen0 | Allocated | |------- |---------:|--------:|--------:|------------:|----------:| | Solve | 296.0 ms | 1.29 ms | 1.21 ms | 175000.0000 | 714.83 MB |
Do we really need 700+ MB of heap allocations to solve this puzzle?! Probably not… but we’ll leave optimization for another time. Until then you can browse the code, including unit tests, on GitHub here: Digits solver
Pingback: Digits: faster in theory – WriteAsync .NET