{"id":5881,"date":"2023-08-11T07:00:46","date_gmt":"2023-08-11T14:00:46","guid":{"rendered":"http:\/\/writeasync.net\/?p=5881"},"modified":"2023-08-10T20:01:34","modified_gmt":"2023-08-11T03:01:34","slug":"goodbye-digits","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5881","title":{"rendered":"Goodbye Digits"},"content":{"rendered":"<p>As of August 8, the <a href=\"https:\/\/www.nytimes.com\/games\/digits\">New York Times game Digits<\/a> 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 <a href=\"https:\/\/www.theverge.com\/2023\/7\/18\/23798932\/the-new-york-times-digits-math-based-puzzle-game-shut-down\">this Verge article<\/a>.)<\/p>\n<p>The game is over, so spoilers are moot. Why not write a solver?<\/p>\n<p>First, let&#8217;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.<\/p>\n<p><a href=\"http:\/\/www.exampler.com\/propaganda\/\">An example would be handy right about now.<\/a> Let&#8217;s say the target is 9 and you are given 1, 2, 3, 4, 5, 6 to start with. You could follow these steps:<\/p>\n<ul>\n<li>6 + 1 = 7; remaining: 2, 3, 4, 5, 7<\/li>\n<li>5 * 2 = 10; remaining: 3, 4, 7, 10<\/li>\n<li>4 + 3 = 7; remaining: 7, 7, 10<\/li>\n<li>7 \/ 7 = 1; remaining: 1, 10<\/li>\n<li>10 &#8211; 1 = 9; target achieved!<\/li>\n<\/ul>\n<p>(There is of course a much shorter solution, 6 + 3 = 9, but where&#8217;s the fun in taking the easy path?)<\/p>\n<p>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&#8217;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 &#8212; but we&#8217;ll handle that later).<\/p>\n<p>To count how many possible paths there are in general, we need to consider all <a href=\"https:\/\/en.wikipedia.org\/wiki\/Combination\">combinations<\/a> 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&#8217;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!<\/p>\n<p>Clearly that&#8217;s way too many possibilities to explore by hand. Programmatically, how could we approach this? We&#8217;ll definitely need to generate move combinations, track our number list at each step, and detect if we should move ahead or not.<\/p>\n<p>Let&#8217;s start with move generation. We need two indexes and an operator, which sounds like a job for a <a href=\"https:\/\/learn.microsoft.com\/en-us\/dotnet\/csharp\/language-reference\/builtin-types\/record\">record type<\/a>. We also need some sort of enumerator to hand out all the combinations given a path length. This could work in a pinch:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\npublic record Move(int I1, int I2, char Op)\r\n{\r\n    public static IEnumerable&lt;Move&gt; Generate(int length)\r\n    {\r\n        for (int i1 = 0; i1 &lt; length; ++i1)\r\n        {\r\n            for (int i2 = i1 + 1; i2 &lt; length; ++i2)\r\n            {\r\n                foreach (char op in Ops.All)\r\n                {\r\n                    yield return new Move(i1, i2, op);\r\n                }\r\n            }\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p>For quick prototyping, we have defined the operations as characters:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\npublic static class Ops\r\n{\r\n    public const char Add = '+';\r\n    public const char Subtract = '-';\r\n    public const char Multiply = '*';\r\n    public const char Divide = '\/';\r\n\r\n    public static readonly IEnumerable&lt;char&gt; All = new&#x5B;] { Add, Subtract, Multiply, Divide };\r\n}\r\n<\/pre>\n<p>A board is fairly simple &#8212; it&#8217;s just a list of numbers with some basic operations:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\npublic sealed class Board\r\n{\r\n    private const int InvalidNumber = -1;\r\n\r\n    private static readonly Board Invalid = new(Enumerable.Empty&lt;int&gt;());\r\n\r\n    private readonly int&#x5B;] _numbers;\r\n\r\n    public Board(IEnumerable&lt;int&gt; numbers)\r\n    {\r\n        _numbers = numbers.ToArray();\r\n    }\r\n\r\n    public bool IsValid =&gt; _numbers.Length &gt; 0;\r\n\r\n    public int Count =&gt; _numbers.Length;\r\n\r\n    public bool HasTarget(int target) =&gt; _numbers.Contains(target);\r\n}\r\n<\/pre>\n<p>We&#8217;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:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\n    public Board TryMove(Move move)\r\n    {\r\n        int result = Calculate(move);\r\n        if (result == InvalidNumber)\r\n        {\r\n            return Invalid;\r\n        }\r\n\r\n        var numbers = new List&lt;int&gt; { result };\r\n        for (int i = 0; i &lt; _numbers.Length; i++)\r\n        {\r\n            if (i != move.I1 &amp;&amp; i != move.I2)\r\n            {\r\n                numbers.Add(_numbers&#x5B;i]);\r\n            }\r\n        }\r\n\r\n        numbers.Sort();\r\n\r\n        return new Board(numbers);\r\n    }\r\n\r\n    private int Calculate(Move move)\r\n    {\r\n        int n1 = _numbers&#x5B;move.I1];\r\n        int n2 = _numbers&#x5B;move.I2];\r\n        return move.Op switch\r\n        {\r\n            Ops.Add =&gt; n2 + n1,\r\n            Ops.Subtract =&gt; n2 - n1,\r\n            Ops.Multiply =&gt; n2 * n1,\r\n            Ops.Divide =&gt; Divide(n2, n1),\r\n            _ =&gt; InvalidNumber,\r\n        };\r\n    }\r\n\r\n    private int Divide(int n, int d)\r\n    {\r\n        if (d == 0)\r\n        {\r\n            return InvalidNumber;\r\n        }\r\n\r\n        (int div, int rem) = Math.DivRem(n, d);\r\n        return rem == 0 ? div : InvalidNumber;\r\n    }\r\n<\/pre>\n<p>Good enough. Now the solver just needs to piece these elements together and recursively explore the whole solution space:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\npublic sealed class Solver\r\n{\r\n    private readonly int _target;\r\n    private readonly Board _board;\r\n\r\n    public Solver(int target, Board board)\r\n    {\r\n        _target = target;\r\n        _board = board;\r\n    }\r\n\r\n    public void Solve(Action&lt;IList&lt;Move&gt;&gt; found) =&gt; Solve(_board, Enumerable.Empty&lt;Move&gt;(), found);\r\n\r\n    private void Solve(Board current, IEnumerable&lt;Move&gt; previous, Action&lt;IList&lt;Move&gt;&gt; found)\r\n    {\r\n        if (current.HasTarget(_target))\r\n        {\r\n            found(previous.ToList());\r\n            return;\r\n        }\r\n\r\n        foreach (Move move in Move.Generate(current.Count))\r\n        {\r\n            Board nextBoard = current.TryMove(move);\r\n            if (nextBoard.IsValid)\r\n            {\r\n                var next = previous.ToList();\r\n                next.Add(move);\r\n                Solve(nextBoard, next, found);\r\n            }\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p>Here we use a callback strategy, passing the current list of moves as we visit each valid solution.<\/p>\n<p>The final integration app boils down to a few dozen lines:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\ninternal sealed class Program\r\n{\r\n    private static readonly Stopwatch Time = Stopwatch.StartNew();\r\n\r\n    public static void Main(string&#x5B;] args)\r\n    {\r\n        try\r\n        {\r\n            var parsed = Args.Parse(args);\r\n            var board = new Board(parsed.Numbers);\r\n            var solver = new Solver(parsed.Target, board);\r\n            Log($&quot;Finding solutions for target={parsed.Target}, board=&#x5B;{board}]...&quot;);\r\n            solver.Solve(ms =&gt; PrintSolution(board, ms));\r\n            Log(&quot;Done.&quot;);\r\n        }\r\n        catch (Exception e)\r\n        {\r\n            Console.WriteLine(e.Message);\r\n        }\r\n    }\r\n\r\n    private static void Log(string message) =&gt; Console.WriteLine(&quot;&#x5B;{0:000.000}] {1}&quot;, Time.Elapsed.TotalSeconds, message);\r\n\r\n    private static void PrintSolution(Board board, IList&lt;Move&gt; moves)\r\n    {\r\n        foreach (Move move in moves)\r\n        {\r\n            Console.Write(board.ToString(move) + &quot;. &quot;);\r\n            board = board.TryMove(move);\r\n        }\r\n\r\n        Console.WriteLine();\r\n    }\r\n}\r\n<\/pre>\n<p>We can try a board which should have only a few solutions to test the app:<\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\n&gt; .\\Digits.App.exe 415 1 2 3 4 5 6\r\n&#x5B;000.000] Finding solutions for target=415, board=&#x5B;1,2,3,4,5,6]...\r\n6 * 2 = 12. 4 + 3 = 7. 12 * 7 = 84. 84 - 1 = 83. 83 * 5 = 415.\r\n4 + 3 = 7. 6 * 2 = 12. 12 * 7 = 84. 84 - 1 = 83. 83 * 5 = 415.\r\n4 + 3 = 7. 7 * 2 = 14. 14 * 6 = 84. 84 - 1 = 83. 83 * 5 = 415.\r\n4 + 3 = 7. 7 * 6 = 42. 42 * 2 = 84. 84 - 1 = 83. 83 * 5 = 415.\r\n4 * 3 = 12. 12 + 2 = 14. 14 * 6 = 84. 84 - 1 = 83. 83 * 5 = 415.\r\n&#x5B;000.440] Done.\r\n<\/pre>\n<p>I can&#8217;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&#8217;s write a <a href=\"https:\/\/benchmarkdotnet.org\/\">benchmark<\/a> and get some more precise measurements:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\n&#x5B;MemoryDiagnoser]\r\npublic class SolverBenchmark\r\n{\r\n    private readonly Solver _solver;\r\n\r\n    public SolverBenchmark()\r\n    {\r\n        _solver = new Solver(415, new Board(Enumerable.Range(1, 6)));\r\n    }\r\n\r\n    &#x5B;Benchmark]\r\n    public int Solve()\r\n    {\r\n        int n = 0;\r\n        _solver.Solve(ms =&gt; n += ms.Count);\r\n        return n;\r\n    }\r\n}\r\n<\/pre>\n<p>The results raise a few concerns:<\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\n| Method |     Mean |   Error |  StdDev |        Gen0 | Allocated |\r\n|------- |---------:|--------:|--------:|------------:|----------:|\r\n|  Solve | 296.0 ms | 1.29 ms | 1.21 ms | 175000.0000 | 714.83 MB |\r\n<\/pre>\n<p>Do we really need 700+ MB of heap allocations to solve this puzzle?! Probably not&#8230; but we&#8217;ll leave optimization for another time. Until then you can browse the code, including unit tests, on GitHub here: <a href=\"https:\/\/github.com\/brian-dot-net\/writeasync2\/tree\/main\/cs\/Digits\">Digits solver<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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&hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[105,104],"tags":[],"class_list":["post-5881","post","type-post","status-publish","format-standard","hentry","category-games","category-performance"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5881","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5881"}],"version-history":[{"count":2,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5881\/revisions"}],"predecessor-version":[{"id":5883,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5881\/revisions\/5883"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5881"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5881"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5881"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}