While everyone loves theoretical performance improvements, we need to check back in with reality from time to time. To review, we had proposed a near-zero allocation strategy to help improve the speed of a Digits game solver. After all, heap…
Digits: faster in theory
Previously, we gave a send-off to the New York Times “Digits” game with a custom solver app. Unfortunately, the solver took quite some time (several hundred milliseconds) and even more space (several hundred megabytes) to analyze the solutions for one…
Goodbye Digits
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…
Letter Boxed: out with the old
Software rot is inevitable if projects are not maintained with care. It is nice to think that in today’s write once, run anywhere world, a rock-solid application with no planned changes can continue to work perhaps without even recompiling; of…
An even faster hash table
Last week, in my continuing exploration of a C++ Letter Boxed solver, I had to build a faster hash table to improve performance. Today we’ll make it even faster, hoping to catch up to the performance of my .NET Core…
A faster hash table
Last time, I wrote about a native C++ implementation of the Letter Boxed solver. Vexingly, this native implementation was actually slower than the corresponding .NET Core app. Today we’ll try to fix that. As I mentioned, some basic profiling revealed…
Native code: always faster?
Last month, I explored some performance optimizations for a C# Letter Boxed solver. It was a fair bit of effort but in the end I could solve a typical puzzle in ~80 ms. Success! However, you might rightly point out…
Letter Boxed: perf gains and losses
After successfully optimizing the trie loading path, we apparently “pessimized” the solution path. Let’s see if we can find out why. I’ll start by building a benchmark for the word finding algorithm: FindWords benchmark Note that this benchmark eliminates all…
Letter Boxed: optimizing the trie
Last time, I demonstrated a relatively fast Letter Boxed solver. It took about 15 ms to solve the puzzle, but that was after a delay of over 200 ms while loading the trie. Surely we can squeeze some more performance…
Letter Boxed: an algorithmic solution
Previously, I introduced the Letter Boxed puzzle and a StringTrie data structure to help determine valid moves. Today, I will go over one possible algorithm to solve it. We first consider the Letter Box as a graph with numbered vertices…