Too Much Spelling Bee!

Content warning: Computer programming and mild combinatorics. May not be suitable for anyone.

Someone is wrong on the internet! I've fallen in a rabbit hole and can't get out! Ahem. Hold on. Let me start over. Do you know the NY Times Spelling Bee puzzle? You are given a honeycomb of seven letters and asked to form as many words as you can. You have to use the center letter and can use any of the letters more than once. Also words are at least four letters long. And if you make a word with all seven letters, that's a pangram. And if you get a pangram, you can sleep.

But I can't sleep. Because I've been trying to solve the Spelling Bee with a computer program. Or rather, with a bunch of programs. I have been trying my hand at learning new programming languages and used Spelling Bee as my exercise. I've written a solver in Python, Haskell, Picat, BQN and C. Since you didn't ask, here is the BQN version. It tastes like liquid nitrogen cooled molecular gastronomic jellybeans.

solution ← (3<≠∧(∧′(ctr??))∧(∧′(ctr?six)???))¨?/(words)        

But the rabbit hole veers sharply here. As I was writing the C version, I discovered that C tastes like a basket of unshorn unpeeled raw carrots. Just reading the dictionary of words into the program required allocating computer memory by hand.1

If I don't allocate enough I will SEGFAULT and live in shame. But if I allocate too much, I'm a newb. And if you're from last century, then every empty byte is too much. I need maybe 20 bytes per word, but how many possible words could be made from a puzzle? What set of letters produces the most words? The most pangrams?

This is easy. I have a solver for a given puzzle, I just have to feed it all the puzzles. But how many is that? Can my laptop do this in a day or will the universe wink out of existence before I finish?

I decided I didn't trust ChatGPT and asked Google, and Google sent me here: Answered: How many NYT Spelling Bee combinations exist? | by Juzer Ali | Medium.

The writer says, "We can get number of unique 7 letter combinations out of 26 English alphabet with function C(26,7). The value of this function can be calculated as (19×20×22×23×24×25×26)/(7×6×5×4×3×2)...Now that we have the unique combinations, we need to multiply it by 7, as for each 7 letter combination, there can be 7 unique games with a different central letter in each game....There are more than 20 billion unique Spelling Bee games."

That's a lot! But this fellow is wrong! His math isn't correct for combinations, you don't multiply by 7 for each center letter, and he forgets the number 21!

The correct way is: The center letter can be any of 26. The six letters are therefore 25 choose 6, which Excel calculates as 177,100. Thus 26 x 177,100 = 4,604,600 possible puzzles. Except Spelling Bee disallows 's' because it makes too many words. Thus 3,364,900 puzzles. Except (!) words have to have at least one vowel.2 So our final answer is: 2,822,260 possible Spelling Bee puzzles.3

My 5-year-old laptop can do that in 7,423 seconds. And the very best puzzle has a center letter c surrounded by e, n, o, r, t, u. It produced 420 words and 128 pangrams.4 5

And now, technical details for, to be honest, me. Technical details for me.

(1) Yes, I was allocating a fixed block. Yes, I could have used a data structure to parsimoniously bag bytes. Yes, ChatGPT offered me a linked list struct like a squeeze bottle of thousand island dressing for my carrots. But we aren't here for data structures!

(2) This is the horrendous line of code that makes sure we have at least one vowel. Honestly, it gives me chills.

if (strchr(VOWELS, CTR) == NULL && strchr(VOWELS, SIX[0]) == NULL && strchr(VOWELS, SIX[1]) == NULL && strchr(VOWELS, SIX[2]) == NULL && strchr(VOWELS, SIX[3]) == NULL && strchr(VOWELS, SIX[4]) == NULL && strchr(VOWELS, SIX[5]) == NULL) {        

(3) Did you see the handwaving? I just subtracted some mystery number. That number is the total number of possible puzzles with all consonants. The center letter is not 's' and not 'aeiou', leaving 20 letters. The six letters are 19 choose 6. Multiply those and it should work. ????

(4) Using Linux's /usr/share/dict/words, which is about 80,000 words. There's lots of other dictionaries out there, some with more than 350,000 words, although I've never been able to find the one used by the NY Times.

And for more fun, at least if you define fun as non-standard compiler optimization options. gcc -Ofast doubled the speed on my code to compute 510 solves per second.

(5) The NY Times always makes sure there is a pangram. If we only include puzzles that have a pangram possible (again, limiting to the dictionary I used), we are down to around 115,000 possible puzzles. A lot less than 20 billion!