News for hackers. Stuff that matters.
Re:The 'Spelling Bee Honeycomb' puzzle: efficient computatio... by ncmncm on Friday January 17, 2020 @03:17AM (#22072842)
I wrote one to generate all possible versions of the weekly puzzle (minimum 5-letter words) that score between 26 and 32 points, that runs in under 70 ms. It finds about 4.8k puzzles, for 14us per. (Nowadays they run puzzles that score as low as 20 (pfft).)

https://github.com/ncm/nytm-spelling-bee/

I did both C++ and Rust versions. They run in the same time. My goal was the fastest single-threaded program that would fit on exactly one printed page. My first version ran in about a second, and I spent months shaving off milliseconds. Rust in 2016 was much more sensitive to arbitrary details of the source code. Maybe it's better now.

The final version does enough setup to enable most of the time to be spent in a four-instruction loop that a modern core can do in a single cycle per iteration, with occasional detours.

Compilers (clang is especially insistent) prefer to arrange the loop to take two cycles, and save a cycle on the long detours instead. I filed a bug on Gcc over it preferring the slow loop, but they decided the slow version was better:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=67153

I absolutely recommend spending months optimizing a little but complicated program. I learned so much. Most things you think will make it faster make it slower.

The solution to any such puzzle is an easy one-line shellscript, also on the github page.

There are no comments on this comment yet.