Game Boy Fiver [Wordle clone]: How to compress 12972 five-letter words to 17871 bytes

Update: You can play an updated version online here in the binjgb Game Boy emulator. This is the version with the frequency-based answer list rather than the official Wordle list, for copyright reasons.

There is a Game Boy version of Wordle, using a bloom filter, a reduced vocabulary and a reduced list of guess words, all fitting on one 32K cartridge. I decided to challenge myself and see if I could fit in the whole 12972 word Wordle vocabulary, with the whole 2315 word answer list. So the challenge is:

• Compress 12972 five-letter words (Vocabulary)

• Compress a distinguished 2315 word subset (Answers).

I managed it (download ROM here), and it works in a Game Boy emulator. There is more than one way, and what I did may be excessively complicated, but I don’t have a good feel for how fast the Game Boy runs, so I did a bit of speed optimization.

Step 0: We start with 12972 × 5 = 64860 bytes of uncompressed data.

Step 1: Divide the 12972 word list into 26 lists, based on the first letter of the word. Since in each list, the first letter is the same, we now need only store four letters per word, along with some overhead for each list. (The overhead in the final analysis will be 108 bytes.) If we stop here,

Step 2: Each four letter “word” (or tail of a word) can be stored with 5 bits per letter, thereby yielding a 20 bit unsigned integer. If we stop here, we can store each word in 2.5 bytes, for a total of 32430. That would fit on the cartridge if there was no code, but it is some progress.

Step 3: Here was my one clever idea. Each of the lists of four letter “words”, is in alphabetical order, and encoded the natural way as 20 bit numbers, the numbers will be in ascending order. Instead of storing these numbers, we need only store their arithmetical differences, starting with an initial (invalid) 0.

Step 4: Since the differences are always at least 1, we can subtract one from each difference to make the numbers slightly smaller. (This is a needless complication, but I had it, and don’t feel like removing it.)

Step 5: Store a stream of bytes encoding the difference-minus-ones. Each number is encoded as one, two or three bytes, seven-bits in each byte, with the high bit of each byte being 1 if it’s the last 7-bit sequence and 0 if it’s not. It turns out that the result is 17763 bytes, plus 108 bytes of overhead, for a total of 17871 bytes, or 28% of the original list, with very, very simple decompression.

Step 6: Now we replace each word in the alphabetically-sorted Answers list with an index into the vocabulary list. Since each index fits into 2 bytes, this would let us store the 2315 words of the Answers as 2315 × 2 = 4630 bytes.

Step 7: However, it turns out that the difference between two successive indexes is never bigger than 62. So we can re-use the trick of storing successive differences, and store the Answers in 2315 bytes. (In fact, since we only need 6 bits for the differences, we could go down to 1737 bytes, but it would complicate the code significantly.)

Result: Vocabulary plus Answers goes down to 108+17763+2315=20186 bytes. This was too big to fit on a 32K cartridge using the existing code. But it turns out that most of the existing code was library support code for gprintf(), and replacing the single gprintf() call, which was just being used to format a string containing a single-digit integer variable, with gprint(), seemed to get everything to fit in 32K.

Example of the Vocabulary compression:

• The first six words are: aahed, aalii, aargh, aarti, abaca, abaci.

• Dropping the initial “a”, we get ahed, alii, argh, arti, baca, baci.

• Encoding as 20-bit integers and adding an initial zero, we get 0, 7299, 11528, 17607, 18024, 32832, 32840.

• The differences-minus-one are 7298, 4228, 6078, 416, 14807, 7.

• Each of these fits in 14-bits (two bytes, given the high-bit usage), with the last one in 7-bits. In practice, there are a lot of differences that fit in 7-bits, so this ends up being more efficient than it looks—the first six words are not representative.

Notes:

• With the code as described above, there are 250 bytes to spare in the cartridge.

• One might wonder whether making up the compression algorithm saves much memory over using a standard general purpose compressor. Yes. gzip run on the 64860 bytes of uncompressed Vocabulary yields 30338 bytes, which is rather worse than my 17871 byte compression of the Vocabulary. Plus the decompression code would, I expect, be quite a bit more complex.

• One could save a little memory by encoding the four-letter “words” in Step 2 in base-26 instead of four 5-bit sequences. But it would save only about 0.5K of memory, and the code would be much nastier (the Game Boy uses library functions for division!).

• The Answers could be stored as a bitmap of length 12972, which would be 1622 bytes. But this would make the code for generating a random word more complicated and slower.