Experiment № 062 · The story
Three Ways to Be Wrong
Why I picked it
Sixty-one experiments of things that flow, grow, vote and search, and I still hadn't built the one piece of computer science I rely on every single day without ever seeing it. Every git diff, every spellchecker's “did you mean”, every DNA alignment and fuzzy address match is this grid. Vladimir Levenshtein defined the distance in 1965; Wagner and Fischer published the way to actually compute it in 1974. The recursion underneath is the obvious one — at each end, either the letters match or you paid for one of three ways to be wrong: substitute, delete, insert. Written as plain recursion it re-solves the same prefixes over and over and dies exponentially. Written as this grid, every prefix pair is priced exactly once. That's the whole of dynamic programming, in a rectangle you can watch fill.
What I enjoy about it
How local it is. Hover any cell and you'll see it consults three neighbours and nothing else — it has no idea what the words are, or that words exist. Yet the corner ends up holding a true global minimum over every possible sequence of edits, and nobody ever enumerated them. I also love that the number alone is nearly useless: the interesting thing arrives on the walk back, when the path reconstructs which edits, and the word visibly turns into the other one below the grid. Watch how the path hugs the diagonal for similar words — matching letters are free, so the cheap route is to keep going straight — and how it lurches sideways the moment a word gains a letter. And the counter I couldn't resist: for intention → execution the grid does a hundred cells where the naive recursion would make tens of millions of calls.
Something you might take away
Two things. First, the distance is a policy, not a fact — flip substitutions to cost 2 and the machine stops swapping letters entirely, because a delete plus an insert is then never worse. That single number is the difference between a spellchecker and diff, and both are “correct”. Second, and more useful: whenever a problem feels exponential, check whether it's actually the same small question asked repeatedly. Write down what you'd have recomputed, in a grid, in the order the answers become available — and keep the arrows, because the reason is usually worth more than the score.