Alignment — workshop

Edit distance as a grid you walk rather than a number you compute — two words on the axes, every cell drawing the three arrows it chose between with the winner solid and the losers ghosted, the corner number arriving early and boring, and the payoff a traceback that spells out the actual edits. Then a two-row toggle that keeps the number, computes it just as fast, and loses the path — the space optimization rendered as a real loss.

Edit Distance (LC 72) filled one cell at a time. word1 runs down the rows, word2 across the columns, and dp[i][j] is the fewest edits that turn the first i letters of one into the first j of the other. The base row and column are derived on screen, not pre-filled — dp[i][0] = i because turning i letters into nothing is i deletes — because most wrong solutions to this problem are a correct recurrence attached to a state definition the author never pinned down.

Every interior cell draws its three choices as arrows: diagonal (keep, free, when the letters match; replace, +1, when they don’t), up (delete the row’s letter, +1), left (insert the column’s letter, +1). The winner is solid in its operation’s colour; the losers are ghosted. When the letters match the diagonal is free and the other two can at best tie it, which is the on-screen answer to “is it ever right to pay for a substitution when the characters are already equal?”

The corner value arrives and is boring. The payoff is the traceback: the solid arrows are walked from (m, n) back to (0, 0), and the edit script fills in on the right — h → r replace · o keep · r delete · s keep · e delete — the diff, which is the thing anyone ever actually wanted from this algorithm.

Then the table switch. “Two rows” is the O(min(m, n))-space version every tutorial mentions and none shows: the fill runs at the same speed and lands on the same corner number, but as each row completes, the row two above it is visibly overwritten — and when the fill ends, the trace has nothing to walk. The script panel says gone. You optimized away the answer and kept the score. The narration names the way back — Hirschberg’s divide-and-conquer, one forward pass and one backward pass to find where the optimal path crosses the middle row, recursing on both halves, the path in linear space for about twice the time — but the viz stops at the loss; it is the trade itself that is worth seeing.

Reuse

src/alignment.js is a framework-free ES module:

editDistance(a, b) — the full (m+1)×(n+1) table with a back-pointer per cell (from[i][j]: match | sub | del | ins), the distance, the path walked corner-to-origin, and ops, the edit script in reading order. Ties go diagonal, then up, then left — one of several optimal scripts, chosen deterministically.
editDistanceTwoRow(a, b) — the space optimization: same distance, two rows, no path.
candidates(dp, a, b, i, j) — the three terms one cell weighs, for narrating a fill step.
simulate(a, b, mode) — the fill as frames, one cell per tick in row-major order (base cases included), then the traceback one arrow per tick — or, in two-row mode, a single “lost” frame. Same trace-per-tick shape as change, rho, sift and window.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

Words are lowercased, stripped to a–z, and capped at 12 characters, purely so the grid stays readable as cells; the algorithm has no such limit.
The demo bundles its own copy of alignment.js (self-contained by contract); re-copy after editing src/.
Switching the table shape mid-fill keeps the frame position, so you can watch the same cell being computed both ways.