Implementing and Optimizing a Wordle Solver in Rust

We implement a Wordle solver in Rust based off on the excellent
3blue1brown video on the same topic:

And then we profile and optimize it to improve the runtime from our
initial naive implementation by ~13500x. You can find the code at

0:00:00 Introduction
0:01:00 Wordle intro
0:04:50 What we're doing today
0:11:24 Gathering our datasets
0:27:22 Structure the solver
0:44:04 The correctness of a guess
1:14:28 Testing the play machinery
1:30:16 Outlining the algorithm
1:38:55 Does a word match a pattern?
2:21:12 Reusing correctness computation
2:26:06 Computing a word's "goodness"
2:49:20 Running the naive implementation
2:57:59 Profiling to the rescue
3:04:44 Avoiding allocations
3:22:05 Comparing bytes, not characters
3:31:58 Correctness computing is faster
3:42:23 HashMap iteration is slow
3:47:40 Compare bytes again
3:50:20 Trying to avoid bounds checks
3:54:42 Keep words as length 5 arrays
4:07:36 Only initialize remaining once
4:21:00 Back to length 5 arrays
4:32:14 Where is compute spending time?
4:51:20 Short break
4:55:20 What if we don't set the first word?
5:02:49 What if we start with another word?
5:07:15 Precalculating matches
5:31:20 Prefer more likely words
5:38:05 Prune known-empty patterns
5:56:24 Don't even consider unlikely words
6:07:36 Closing thoughts

[letsgetrusty]

Calling in sick on Monday to watch this 🙏

[avatar]

I was wanting a sort of crash course on Rust and watching you work actually taught me so much more! I love the way you break down problems and it’s not too difficult to follow.

Keep it up man. You have a new follower!

[topdeveloper]

Hello, I am a Korean web developer who is studying while listening to your lecture.
First of all, I want to say thank you. Thanks to you, I am learning a lot about programming itself because I can see the coding process of top programmers as well as the Rust language. Thank you.
Can I ask you a favor?
I want you to turn on YouTube automatic English subtitles so that users of non-English speaking countries, including myself, can easily listen to lectures.
Recent lectures have automatic English subtitles, but the early ones you uploaded do not have automatic English subtitles on YouTube.
Please turn on the YouTube automatic English subtitles for people who are not familiar with English like me or have difficulty hearing.
Thank you always. from your big fan in south korea.

[benedyktjaworski]

Also, I’m not sure if you change that later, but so far (around 3 h in) you seem to be only considering remaining candidates as valid guesses. I believe the original algorithm considered all words accepted by Wordle (even if they’re already eliminated by the masks returned from previous guesses) – obviously you know they won’t be the right answer, but one of them still might be optimal for information gain.

For example you might guess a word which has a letter X repeated in the same place where it already was yellow previously (thus not a correct answer), but it has such a combination of other letters that the rest of the returned mask will further narrow down the candidate list (and would do that better than any of the remaining candidates, as they might eg. give you insight only if they are the right answer, but wouldn’t narrow down anything if they’re not – so you might want to trade off the chance of winning in this step to gain more info for better chance in the next step).

[Vancha]

These are my new favourite streams, not too complex, but really useful for everyday work :)

[lucasa]

I don't know how to explain why, but this video is extremely good, I would want to watch several of them in a row

[kanuos]

I think I learned more from this one video than I learned in my entire first year of college. This was an amazing stream. Would love to see more of these!

[benedyktjaworski]

The insight around 2:21:12 (reusing correctness computation) is that if you plug the guess as the expected answer and it yields a different mask (to the one you actually got previously) against the previous guess – then it *cannot* be the correct answer. If it were the correct answer, it would have to do exactly the same again as it did previously with the previous guess.

So you can reject every remaining word that does not yield the same mask when treated as the target answer. And since you don’t know *anything else* about the answer except for the mask it returns, you cannot reject any word that yields the same mask as the true answer.

That’s why you can just reuse the game logic and plug your candidate as the expected answer and compare the masks returned previously by actual game and now by the guess.

[BrazenNL]

As someone who's just discovered Rust and decided his first project would be the Wordle game, you wouldn't believe how much fun it is to see you make the same assumptions with regards to compute(). It was all so very easy until I wrote tests. 😄

[mageprometheus]

After watching this I'm exhausted! I had almost no grey-outs this episode while previous videos felt like they were in Norwegen. 😀

[avischetlin]

26 minutes into the video (feels like 2) and he says, "...and now this is a good place to start." I've found my perfect video! ❤

[RoughlyUnderstood]

So awesome to watch the process end to end of identifying slow points in the code. Keep up the great work!

[joffreybluthe]

I especially appreciated your impersonation of a grumpy old man ^^
That was pretty hilarious.
And the coding part was of course amazing as well!

[maybenexttime]

Nitpick: I thought the same thing you did at firs but upon some thought I realized that your comment at 3:40:00 is actually wrong. If G gives mask C against A, A doesn't have to give mask C against G. Imagine: G: "awxyz", A: "bacde" -> G|A = "MWWWW", A|G = "WMWWW". However the code is still correct as explained by others here.

[mmdts]

Some more insight relevant to 1:41:21 and 2:23:38:

I ended up implementing the unoptimized algorithm on my own (before watching the relevant part of the video) and comparing that in retrospect. For the functionality of Guess.matches (described on 1:41:21), I simply used Correctness::check (later reached on 2:23:38), then verified that the returned mask is equal to the mask inside &self.

Here's the logic:

I was thinking in the lines of "I cannot possibly retain a word that, had their roles been swapped (answer and guessed word), will not provide the same mask".

It's useful to think of the mask as a bilateral non-directional relation between two words. It does not care which is the answer, and which is the guessed word, but provides information that relates the letters of both words to each other.

[JMW]

During the correctness check: If you loop over the answers you do not need the `let mut used = [false; 5];` array. If answer == guess you can mark it as correct and if it isn't loop over the guess array and mark the first matching one that is still set to Wrong as Misplaced (if I understood the problem correctly).
(At minute 55)

[Starckoo]

Watching this now and tried Wordle, the word was "Rusty"....what a weird coincident 😂

[MasterHigure]

I have tried to come up with a good explanation for my "Use Correctness::calculate() in matches()" idea. The best I've come up with is this (I don't remember the argument order to the functions):

matches(word, guess, pattern) wants to ask the question "Given that guessing guess yielded pattern, could word be the answer?" The line Correctness::calculate(word, guess) == pattern; asks "If word were the answer, would guessing guess yield pattern?" These questions are equivalent, under the assumption that a given answer and guess always yields the same pattern.

Given some guess, the possible patterns partition the (remaining) dictionary into subdictionaries. Each word is in exactly one of these subdictionaries. Our main goal in the loop where we call matches() is basically to filter down to the partition that the current pattern corresponds to.

I had to leave the stream early, and I won't have time to see the rest for a while, so I don't know whether you did what I'm about to suggest now, but here it is:

We want to partition the dictionary. The way it is done (at least at 3:30:00, the time where you use my correctness calculation suggestion), we loop over the patterns, and filter the entire dictionary against each pattern. It seems like it would be faster to go through the entire dictionary once and calculate the correctness against guess, then construct the partitions from there. Something like

let mut parts: HashMap<[Correctness; 5], Vec<Word>> = HashMap::new();
for word in dict {
parts.get_mut(Correctness::calculate(word, guess)).insert(word);
}

Yes, something needs to be done about initialisation here. But apart from that, I think this should be better.

[gabrielmachado]

I guess the biggest impact would be to calculate the probability of a mask in a different way: you could generate a mask for every word against your potential guess, than increment counters on a hashmap in witch the masks are keys. At the end you divide each count by the total number of words, this would eliminate one big loop. I did this and I could run the entire thing on 100ms (including de first guess being calculated).

[horaciomlhh]

Great to see collaboration between channels specially these 2 that are great!