Tiny Tiny Wordle

Introduction

I know, I haven't been very active lately, I started teaching computer science a few months ago and learning this new job took away most of my time, so I have hundreds of unread emails, projects that need to be finished (looking at you OpenLDAT), projects that need updating (did someone say LibreSpeed websockets?), games waiting for me to play them, and a high end PC that asks itself every day what the fuck went wrong in its life when I started using it for making slides and grading tests.

Anyway, that didn't stop me from starting a new mini project when I discovered Wordle (Trigger warning: proprietary software with ads and analytics).

Wordle is a web-based puzzle game where you have to guess a 5 letter word chosen randomly from a dictionary using up to 6 guesses, each guess has to be in the dictionary, and when you enter it, it colors each letter differently: green if the letter is correct, yellow if the letter is present in the word but you put it in the wrong position, gray if the letter is not in the word.

This is what a typical game of Wordle looks like:

There are a bunch of Wordle clones around at this time, but none of them was able to run on something as limited as an Arduino, so I decided to give it a try.

The Wordle algorithm

Finding the dictionaries to use in the game was easy, I adapted them from another clone called Gurgle (with the author's permission of course), but the algorithm behind the coloring of the word is actually a bit more complicated than you may think.

Generally speaking, this algorithm takes 2 strings in input (the solution and the user's guess) and outputs a number for each letter: 0 for gray, 1 for yellow, 2 for green.

A first, naive approach would be something like this pseudocode:

int[] color(String guess, String solution){
    int length=solution.length;
    int colors[length];
    for(int i=0;i<length;i++){
        colors[i]=0;
        for(int j=0;j<length;j++){
            if(guess[i]==solution[j]){
                if(i==j){
                    colors[i]=2;
                }else{
                    if(colors[i]!=2) colors[i]=1;
                }
            }
        }
    }
    return colors;
}

This algorithm compares each letter in guess with each letter in solution: if a match is found at the right position, the color green is assigned, if a match is found at the wrong position and this letter isn't already green, the color yellow is assigned, otherwise the color gray is assigned. A puzzle is solved when all the letters are green.

Example:

Solution:   CHAIR
Guess:      CRUSH
Colors:     21001

This naive solution would be good enough for a small school project, but if we compare it to the actual game, we can see that their algorithm is slightly different.

Example:

Solution:   CHAIR
Guess:      RASTA
Wordle:     11000
Our clone:  11001

With these inputs, the second A in RASTA is yellowed by our clone but is gray in the original game. This means that the original algorithm takes repeated letters into account, so we need to modify our clone to count how many time each letter appears and how many times we've already seen it in the solution.

We could do it this way:

int[] color(String guess, String solution){
    int length=solution.length;
    int colors[length];
    for(int i=0;i<length;i++){
        if(guess[i]==solution[i]){
            colors[i]=2;
        }else{
            colors[i]=0;
        }
    }
    for(int i=0;i<length;i++){
        if(colors[i]==0){
            for(int j=0;j<length;j++){
                if(i==j) continue;
                if(guess[i]==solution[j]){
                    int ctr=0;
                    for(int k=0;k<length;k++){
                        if(solution[k]==solution[j]) ctr++;
                        if(guess[k]==solution[j]&&colors[k]!=0) ctr--;
                    }
                    if(ctr>0) colors[i]=1;
                }
            }
        }
    }
    return colors;
}

This new version works in two passes:

1. Determine which letters in guess should be green and assign them that color
2. Compare each letter in guess that isn't green with each letter in solution. If the letters are the same, determine the difference between how many times the letter appears in solution versus how many times we've already encountered and colored it in guess, if this difference is greater than 0, assign the color yellow to this letter in guess, otherwise leave it as it is

This code would give my students a panic attack, but it does give us the expected output:

Solution:   CHAIR
Guess:      RASTA
Wordle:     11000
Our clone:  11000

Now that we have a working algorithm, it's time to make the rest of the game.

Wordle vs. Arduino

Getting this game running on an Arduino means:

• Adapting the game to make it playable on a black and white display with no keyboard
• Figuring out a way to fit the dictionary in memory
• Building some sort of "game boy" with display and buttons and a library to make input and output to this custom board easy
• Implementing it all in C

Adapting the game

We mainly have 3 restrictions to deal with here:

• No keyboard: making a whole QWERTY keyboard for this thing would be difficult, expensive and pointless, instead I decided to put 4 buttons on it; the input system shows 5 boxes that the user can select using the left and right buttons, the letter in each box can be changed using the up and down buttons. When the user is done entering the word, a confirm button on the right can be selected using the right button and activated by pressing right again. This works quite well, but my friends have rightfully pointed out that with this system they have to keep track of which letters have already been used in previous attempts. Personally, I like the added challenge, but I get their point
• No colors: the display chosen for this project is a 128x64 monochrome display (it looks yellow and cyan in the picture because the manufacturer put a colored filter on it, but it's actually black and white). To get around this problem, I decided that correct letters would be shown with a solid white background, letters in the wrong position would be shown with a white outline, and incorrect letters would have no decoration. I also added a small tutorial at the beginning of the game to instruct the user about this. This also works quite well and we all found it very easy to get used to
• Screen shape and size: the tiny 0.96" display doesn't have enough space to fit the original table-style UI of the game and it has the wrong aspect ratio, so I decided to split it into two columns showing your previous attempts. After inputting a word, the "colored" output will be shown there with a little animation

Compared to the original game, this clone actually has a couple of extra features:

• Play as much as you want: when you guess a word (or run out of guesses), you can continue and try to guess another word
• Combos: if you guess 3 or more words in a row, you get a cool animated screen showing the combo counter

Compressing the dictionary

Fitting the dictionary into the tiny storage of the Arduino was my favorite part of this project.

In case you're not familiar with the Arduino Uno (and all its clones and variants), it's based on the ATmega 328p microcontroller, which means it has a 16MHz CPU, 32kB of flash memory for both program and data, 2kB of RAM for running your program, 1kB of EEPROM to store settings and that's pretty much it. This makes it effectively impossible to use standard compression algorithms like Deflate or LZMA because we simply don't have enough RAM, and even if we did it would be quite slow on that CPU, so we need to come up with a custom, very simple compression algorithm.

In total, I made 2 dictionaries for this project: English (3579 words) and Italian (5984 words). Each word is 5 characters in length, just like the original game. If we just store them as an array of strings, each word would take up 6 bytes (5 characters + 1 terminator), so it would take 3579*6=21474 bytes for the English dictionary and 5984*6=35904 bytes for the Italian dictionary. The first one would fit but it would leave very little space for the game code, the second one wouldn't fit at all.

Since all the words have the same length, a simple way to save memory would be to get rid of the terminators and store the entire dictionary as a single very long string. This would lower the size of the English dictionary to 3579*5=17895 bytes, which is just about manageable, and the Italian dictionary to 5984*5=29920 bytes, which is still too big.

Wordle only uses uppercase latin characters, no numbers, no accents, no symbols, etc., so we don't need the entire 8 bit ASCII charset, we can make our own encoding that can only do the 26 characters A-Z. If you know your binary, you'll know that ⌈log2(26)⌉ is 5, so we can use 5 bits per character instead of 8. With this new encoding, our English dictionary takes ⌈3579*5*(5/8)⌉=11185 bytes, and the Italian dictionary takes ⌈5984*5*(5/8)⌉=18700 bytes. That's a 52% compression ratio! We can still address words individually without decompressing the entire dictionary, but because the encoding is not byte-aligned, some tricky bit manipulation is required to decode the words, and this is slow on the Arduino.

Implementing Wordle requires that we are able to quickly tell whether a word is present or not in the dictionary, and with this system, it would take about 1 second to do a full linear search. This problem can be solved very simply by sorting the dictionary in alphabetical order before compressing it, allowing the Arduino to do a binary search, just like you would do with a physical dictionary, and this only takes a handful of milliseconds.

The compression routine, which is meant to run on a PC, was implemented in C in a tool that takes a text file in input and spits out a compressed file as well as a .h file that can be used in the Arduino IDE.

If you want to know more about how this compression algorithm works, a detailed explanation is included with the project.

The "game boy" board

This board is composed of an SSD1306 OLED monochrome display and 4 normally-open buttons. The display is connected to the Arduino via I2C, while the buttons are just connected to 4 GPIO pins.

The 4 buttons are just regular clicky normally-open buttons, they're connected to pins 2,3,4 and 5 on the Arduino in pullup input mode and their status can be obtained with the digitalRead function. I chose not to use interrupts for these buttons since we don't have enough interrupt capable pins on the Arduino and made a simple getButton function that works similarly to the getCh function in C: it waits for a button to be pressed, returns which button it is, and handles debounce.

The display situation is much more interesting. The SSD1306 display has a resolution of 128x64 at 1 bit per pixel and comes with the Adafruit SSD1306 library for driving it, but I couldn't use it because it took up too much program memory. I ended up making my own super minimal version of this library as a single .h file containing the code required to initialize the display in this particular scenario, overclock the living crap out of the I2C bus, draw characters and lines with some space-optimized routines, clear the display, and that's pretty much it. To further reduce the amount of program memory used, I also removed most of the characters in the Adafruit font, leaving only numbers, uppercase and lowercase latin, and a few symbols.

One not so great thing about this library is that to make things simple and small, I have to keep the entire framebuffer in RAM, which eats up a whole kB out of the 2kB available on the Arduno; it's not a problem for this game, but it's something to remember should you decide to reuse my code for something else.

The first prototype board looked like this, with an Arduino Uno hooked up to a breadboard with the components on it:

Implementation

I implemented the game in C using Arduino IDE. At first I was really worried about speed, but I quickly realized that I had to optimize the code to use as little program memory as possible, especially if I wanted to fit that huge Italian dictionary in it. There are many instances in which I had to write slower code because making it smaller was more important, especially in the graphics library, but in the end it turned out to be a good choice because there is no percievable lag for the user anyway and these optimizations made it possible to fit a larger dictionary, which is definitely important to the user.

The Arduino code is organized in a sort of modular way:

• TinyTinyWordle.ino is the main file, it just imports the other project files and defines some compile-time flags that you can change to toggle various features such as the splash screen, the tutorial, animations, etc. in case you want to free some memory for a larger dictionary
• dictionary.h contains the decompression routines as well as functions to get a random word and determine whether a word is in the dictionary or not
• userInteraction.h contains all the code to handle the input and output with the "game boy" board mentioned before and provides some standard functions used by the game like input, output, splashScreen, etc.
• MiniSSD1306.h is the super lightweight display and graphics library mentioned before, it's only used by userInteraction.h
• game.h is the most important file and contains all the game logic. This code is platform-independent and can be easily used in other projects, provided that all the functions defined in userInteraction.h and dictionary.h are reimplemented for that specific platform
• locale-en.h and locale-it.h contain the English and Italian localization strings, as well as their respective dictionaries. Only one of these is loaded at a time, you can choose which one in TinyTinyWordle.ino (default is English obviously). The compressed dictionaries in these files were generated with the cookDictionary tool in the PC folder (instructions included)

An interesting problem that I had to solve during development was initializing the random number generator. As you probably know, comptuers can't actually generate random numbers, and the pseudo-random number generator provided by the Arduino core libraries needs a "true" random seed to initialize. A common solution is to initialize it using the output of analogRead on a disconnected pin to pick up random-ish RF interference, but this is not good enough for our game because it can only generate 1024 different numbers and they are almost always in the same range, so the first words would almost always be the same. I came up with two solutions:

• Generate a seed by using a temporary variable that is repeatedly shifted to the left by 1 bit and xor-ed with the output of analogRead. This generates fairly good random numbers, definitely good enough for this game, but it takes up a bit of program memory, especially for that analogRead
• A splash screen: games in the 80s and early 90s had the same exact problem, and they solved it by timing how long it took the user to press the start button on the splash screen and using that time as a seed for the RNG. This is the solution I ended up using by default even if it uses a bit more program memory because it makes the game look more polished to the user, but you can disable it and use the previous solution.

Debugging the software was fairly easy because thankfully I had just barely enough free memory to use the Serial library. I left some debug code in the project that can be enabled at compile-time if you want to play around with it.

Making it portable

The final step of this project was to make it into a small battery-powered portable device that would have made you king of the playground in 1991.

Since the Arduino Nano is almost 100% compatible with the Uno, I decided to use it instead of the Uno for this version. The idea was to make a small 3D printed box with a 12V battery holder (A23 type, typically used in door remotes), a toggle switch to turn the game on/off, the Arduino, and a circuitboard with the display and buttons soldered to it.

The battery has a capacity of about 60mAh which translates to little more than a hour of play time with a new decent battery in it. It's not rechargable so it's not exactly eco-friendly.

Overall, this works quite well but I'm not too happy with the case: I like the way it looks, but my 3D modeling skills are pretty crap so everything is held together by hot glue and good wishes, and also access to the USB on the Nano is blocked, meaning that if I find a bug in the game, I have to take the whole thing apart to reflash it, which is almost certainly going to break something because of the glue. Hopefully someone will take pity on me and help me design a better case.

To give you an idea of how tiny this thing is, here it is next to a flash drive.

Code and conclusion

As usual, all my work is free and open source so you can study it, improve it, yada yada. The project is under a GNU GPL v3 license.

• Browse repository on GitHub
• Download source code and schematics from here

To be honest, I haven't had this much fun developing something in years, and considering that most of the work was done in less than a week during the Easter holidays, I'm really happy with how well it works, sometimes when I'm bored I just pick it up and play it and it's absolutely fine, this could have genuinely been a real product 25 or so years ago and people would have rushed to buy it. Sure, it makes no sense now that everyone has a smartphone, but I enjoyed pretending that it was still the 90s and that I was developing some kind of Game Boy knockoff, and the optimized code was fun to write.

Here's a video of me playing Tiny Tiny Wordle with a friend:

Taking pictures (and especially videos) of this thing was a bit of a nightmare because the display has a slight strobing caused by its refresh cycle which causes black lines in pictures similar to old CRTs that have to be removed manually, my phone also has a very hard time autofocusing on it. It's possible that the 1.3" version of this display doesn't have this problem but I wasn't able to find one at a reasonable price.

Needless to say, this is a completely unofficial clone of Wordle, it's in no way endorsed or authorized by the original author or The NY Times.