Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

varianceexplained.org

Post reply on HN
Print view View original

1–10 of 12 posts

Re: The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

#2

Post by swilliamsio »

You can play the daily New York Times Spelling Bee puzzle online[0]. It's free to play up till you get more than a certain number of points, then you require a subscription.

I made a little clone of the game to get around these restrictions[1].

[0] https://www.nytimes.com/puzzles/spelling-bee

[1] http://www.swilliams.io/fun/hex/

Re: The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

#3

Post by wchargin »

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. :-)

Re: The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

#5

Post by ncmncm »

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.

Re: The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

#6

Post by jim-jim-jim »

wchargin wrote: post #3

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…

Very cool. I also wrote a solver using the NYT magazine's rules back in 2018, and found the bitwise method of matching both 1 and 3 point values incredibly fast. I just precalculated the hashes and ran a parallel loop over the whole array, but I know there are specialized data structures that games like Scrabble use. I wonder if that would have sped things up even more.

Anyway, whenever I see a problem that involves letters now, I reach for bit operators first.

Re: The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

#9

Post by madcaptenor »

madcaptenor wrote: post #8
hoseja wrote: post #7

>it must not contain the letter S (that would be too easy) I don't understand. Why S?

If the puzzle contains S it will be very easy to form plurals and therefore run up the score.

More specifically, if you include S as a possible letter, it appears in the second-most words (53,556, compared to 63,445 for E). But once you have some words it's natural to just stick S on the end of everything (this will work for most nouns and verbs) and this makes the standard spelling bee puzzle uninteresting. (I don't think it makes the meta-puzzle less interesting, though.)

If you run Robinson's code but omit the filtering out of words with S, the best puzzle is E/AINRST (8681 points). The previous winner, R/AEGINT at 3898 points, is now only 442nd-best. (Notation: I put the required center letter before a slash.)

Interestingly, one of the five puzzles that's tied for 15 points, the second-worst possible, includes an S. The puzzle is Q/CIORSU - the words are CROQUIS and SUQS.

Re: The 'Spelling Bee Honeycomb' puzzle: efficient computation in R

#10

Post by ddoran »

I've started playing this puzzle every day. If you get every word that NYT expects, you get a "Queen Bee" award, the trick is that they don't tell you what the Queen Bee target is, and more often than not there is at least one word I've never heard of.

The words are revealed the next day on the puzzle page, or if you're impatient, they are in the source code for the Spelling Bee page each day.

Post reply on HN