Implementing and Optimizing a Wordle Solver in Rust
Channel: Jon Gjengset
Date: 2022-03-06

We implement a Wordle solver in Rust based off on the excellent
3blue1brown video on the same topic:
https://www.youtube.com/watch?v=v68zYyaEmEA

And then we profile and optimize it to improve the runtime from our
initial naive implementation by ~13500x. You can find the code at
https://github.com/jonhoo/roget.

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

Live version with chat: https://youtu.be/cfjQw4ZjAiI