42.1K subscribers

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

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