Bitmaps reveal the Queen Bee
I fell into the Wordle craze a few years after everyone else. After indulging in several months of Wordle, I shifted my focus to the NYT Spelling Bee. What better way to enjoy the Queen Bee than to solve it programmatically? Any excuse to play with bitmaps is fine by me.
The rules of the NYT Spelling Bee are:
- Words must contain at least four letters.
- Words must include the center letter.
- The word list excludes obscure words, proper nouns, and hyphenated words.
- No naughty words.
- Letters can be reused.
Sketch¶
I started with the following sketch:
- Build a Go command line app, invoked as
spelling-bee --letters=entivcz
. - The first letter is the center letter.
- Loop through
/usr/share/dict/words
to find matching words. - Display panagrams first, followed by other matching words sorted by descending length.
To match the words, we'll use a bitmap representing the character set of a word.
Since there are 26 letters, and we don't care about frequency, the data fits in
a uint32
. For example, to represent citizen
:
0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 a b c d e f g h i j k l m n o p q r s t u v w x y z _ _ _ _ _ _
When matching a word, we need to verify two conditions:
- The center letter is included.
- The word contains only the letters present in the
target
bitmap.
The challenge lies in ensuring that a word uses only the target letters. In
other words, does the word
bitmap contain only the set bits corresponding to
the target
bitmap? We can encode the logic with two steps:
- Bitwise
and
theword
bitmap with thetarget
bitmap. The result is only the letters present in both bitmaps. - Check that the
word
bitmap is the same as step 1.
(word & target) == word # Equivalently (word & target) ^ word == 0
Go program¶
See full code at the GitHub Gist. The main logic is in the wordMatcher
.
We build the matcher from the target letters and match words from the
dictionary.
package maintype wordMatcherstruct {// center is a bitmap of the single center letter in the target word. centeruint32 // all is a bitmap of all letters in the target word alluint32 }func newWorldMatcher (targetstring ) wordMatcher {return wordMatcher{ center: letterBitmap(target[0]), all: wordBitmap([]byte(target)), } }func (m wordMatcher)isMatch (word []byte )bool {for _, r :=range word {if r <'a' || r >'z' {return false } } other := wordBitmap(word) hasCenter := other&m.center > 0 isExclusive := (other & m.all) == otherreturn hasCenter && isExclusive }func wordBitmap (word []byte )uint32 { bm := uint32(0)for _, ch :=range word { bm |= letterBitmap(ch) }return bm }func letterBitmap (chbyte )uint32 {return 1 << (ch -'a' ) }
Results¶
The program works as advertised. For the target word entivcz
, we find all
matching words in the dictionary. However, there are two problems with the
solver.
- The list includes obscure words like
itcze
andcetene
. - The list doesn't include suffixation, like adding
ed
oring
to the word. This means the solver misses the panagram for the puzzle:incentivize
.
Letters: etnizvc Panagrams: Matches: incentive inventive nineteen ... evict niece ... nine nice