Solving Wordle

It all started on Discord. I was on a call with my friends and it was clear that they were doing much better than me at this new viral game called Wordle. For those who don’t know, it’s a game where you try to guess a 5-letter word using the hints given to you. When you make a guess, you are given back a “feedback”:

• Green if you guessed the correct letter in the correct position¹
• Yellow if the letter is in the word but in a different position
• Gray if the letter doesn’t exist in the word

It’s a pretty simple and fun game, so of course it went viral. So much so, it was acquired by The New York Times². But I digress. On that Discord call I remembered that while I might not be good at the game, I’m not too bad at making computers do certain things – and this game looked like something that a computer would be much better at than humans. So on that call, I started thinking out loud, annoying my friends, to quickly come up with an algorithm. Since my memory is really bad (why do you think I’m bad at Wordle?), I quickly wrote the algorithm down on a google sheet:

1. Pick a random word
2. Based on the feedback do position elimination.
3. Based on the possible positions, eliminate words.
4. If you have only one word left, that’s your guess
5. If not, pick a new word from the filtered list. Go to 2

Now, it’s obvious how we do the elimination is the most important part of the algorithm. Step 2 and 3 are both crucial to get the right answer and get it fast. My idea was simple. I wanted to create an index with each (letter, position) tuple pointing to a list of possible words. For example, here we have the list of words starting with S followed by T (S, 0) = (T, 1) = ["STEAL", "STOLE", ...]. After building this index it’s trivial to filter the words based on the feedback we get. We just need to do an intersection of each list based on our “green” letters. However, the careful reader will notice that this approach makes it really inefficient and difficult to take advantage of the “gray” letters. Therefore, we need to come up with a better way to eliminate the words.

Let’s take a step back here and think about what exactly each color means³:

• Gray: No position can have this letter and this letter can be in no position
• Yellow: This position can’t have this letter and this letter can’t be in this position
• Green: This position can only have this letter, but the letter can be in other positions as well (duplicates)

These definitions reveal the need for two indexes instead: one for letters and one for positions. Keeping the same general algorithm above, we write the algorithm for the elimination itself (steps 2 and 3):

1. Create an index letters_to_positions, where initially each letter points to a set of all positions, ie, {0, 1, 2, 3, 4}
2. Create an index positions_to_letters, where initially each position points to a set of all letters, ie, {a, b, ..., z}
3. Go through the feedback:
    1. If it's green, positions_to_letters[position] = {letter}
    2. If it's yellow, remove letter from positions_to_letters[position] and remove position from letters_to_positions[letter]
    3. If it's gray, remove all from letters_to_positions[letter] and remove letter from positions_to_letters[position]

With this elimination algorithm, we can make full use of the feedback we get! Consider the example board below.

Pay closer attention to the letter L. We technically don’t get a green for L after our first two guesses, but we can easily infer its exact position. After two guesses, our algorithm eliminates positions “1” and “4” from the letter L because of the yellows. And the greens let us eliminate “L” from position 0 and 3. When we combine these, we can conclude that our target word has an “L” at position 2! The algorithm intuitively feels correct, but I’ll leave the proof as an exercise for the reader.

OK, we now know our algorithm is correct, but how does it perform? There are no tricks, no fancy algorithms nor data structures we use, so is our “naive” algorithm too slow to be practical? Well, not at all! It actually performs pretty well in practice, because of how small the search space is. But to make things more interesting, let’s analyze how it performs in theory. For this analysis, we assume we have N words in our dictionary and each word has M letters, not 5.

• For each guess we need to go through all N words to perform elimination.
• For each word, we have to check each letter against our two indexes: letter_to_position and position_to_letter. We use set data structure as values here instead of lists to have constant lookup and deletion. (although in practice lists might perform faster because they have a small max size)
• English alphabet has 26 letters, so letter_to_position check takes constant time.
• Each word has M letters, so position_to_letter check grows linear to number of letters in each word.
• We need to do this elimination at most M times, assuming we can make at most M guesses.

All in all, with my implementation this adds up to O(M² * N + M) for each guess. For Wordle specifically, since M = 5, our runtime is basically linear to the number of words we have, which is theoretically the best we can do. Of course, in practice we can improve the algorithm by making smarter guesses. One obvious improvement is assigning a score to each “possible” word based on the frequency of the letter in the English language or making more tactical guesses to eliminate more words. Basically we can use statistics and information theory to make better guesses. It wouldn’t improve the worst-case performance, but it’d increase our chances of finding the answer in fewer tries.

I went ahead and implemented this algorithm and some more. For the curious, it is available on Github, with full history⁴. It supports multiple game modes, so you can do more than just using it as a solver. It allows you to play against the computer or watch the computer play against itself. If you have git and python3 installed, should be easy to try it yourself. README should have the most recent instructions on how.

I know I’ve missed the initial hype train, but I had a lot of fun solving Wordle. It beautifully shows that you don’t always need fancy data structures or algorithms to beat your native speaker friends!