Skip to content

Edit graph

One search from three angles: the grid, the note the algorithm keeps, and the diff that comes out. Move one and the others follow.

Give it two texts

Watch it search

The search grid

Each diagonal thread — a small knot when the grid is dense — marks a line that is identical on both sides. Those are the free steps the algorithm will aim for.

A — before →

Nothing has been searched yet. The diagonals already drawn are the lines that are identical on both sides — the free steps, and the search will try to string together as many as it can. Press play below, or step one move at a time, and watch the yellow edge expand: that is every point reachable with d edits.

Legend

  • Match position— the same line on both sides
  • Explored region— tried and left behind
  • Frontier— how far the search has reached
  • Chosen path— the answer

The V array

One cell per diagonal k. The number is x: the furthest point along A that d edits can reach on that diagonal. y is never stored — it can always be recovered as x − k, which is exactly why V needs only one number per diagonal. Hover a k cell to highlight that diagonal in the lattice.