|
Hey, I wrote one of these, too! Mine generates and solves all possible
puzzles (with my dictionary, there are 54733) in about 1.8 seconds on my
six-year-old laptop, and can also typeset them to LaTeX+TikZ to make
printable puzzle sheets. That’s 0.03 milliseconds per puzzle. It turns
out that you can get this thing to run quite fast once you realize that
you can pack words into bitsets and express the whole algorithm in terms
of bitwise operations on machine words. Of particular interest is that
the running time is output-sensitive: proportional to the number of
solutions to the puzzle but not the total size of the dictionary (after
one-time preprocessing). I used the “hard copy” rule set as used in the printed New York Times,
which is slightly different from the web rule set: words must be at
least five letters long, not four, and are worth 1 point each, or 3 for
a pangram. The hard copy puzzles also include three score thresholds, so
I had a bit of fun trying to reverse-engineer how those thresholds are
chosen. I didn’t get exactly the right function, but I got fairly close,
and most importantly the thresholds feel fair when playing. (The online
version also has score thresholds, but there are many more of them, and
it was easy for me to transcribe thresholds from the archives of the
printed copies.) In my admittedly biased yet assuredly humble opinion, both the algorithm
performance and the rating threshold estimation are interesting:
https://github.com/wchargin/spelling-bee/tree/master#perform... Oh, and a web-based solver, for convenience:
https://wchargin.github.io/spelling-bee/ Lovely to see how the author of this article and I both had a lot of fun
with this by taking it in different directions. :-) |