Edit Distance

Algorithms & Data

How many single-character edits turn one word into another? The edit distance is answered by dynamic programming: fill a grid where each cell is the cheapest of three moves from its neighbours, and the answer appears in the corner. Then trace backward to recover the actual alignment — the bright path through the cost heat-map. Runs on its own; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

loading core…

Self-running demo — the table and its alignment path cycle through word pairs.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

Dynamic programming solves a big problem by filling a table of smaller ones. For edit distance, cell [i][j] is the distance between the first i letters of one word and the first j of the other:

D[i][j] = min(                        // fill the table cell by cell
  D[i-1][j-1] + (A[i] != B[j]),       //  substitute (or match)
  D[i-1][j]   + 1,                    //  delete
  D[i][j-1]   + 1);                   //  insert
// then walk back from D[m][n] to D[0][0] for the alignment

Fill the whole grid and the answer is the bottom-right corner; walk back from it and you recover exactly which letters were kept, changed, added or dropped — the lit path. It stays bit-exact across every codegen mode.

Compiler stress-test

Item	What it exercises
2-D dynamic programming	A grid of sub-answers is filled in, each cell built from three neighbours it already knows. The edit distance between two whole words falls out of the bottom-right corner. A doubly-indexed table (D[i][j]) with a min recurrence — a loop nest no earlier demo runs.
min recurrence	Each cell takes the cheapest of three moves — substitute, delete, insert. That min-of-three, over the whole grid, is the entire algorithm.
backtracking	Once the table is full, tracing backward from the corner — always to whichever neighbour produced the minimum — recovers the actual sequence of edits: the highlighted path.
cross-checked	The build gate verifies the distance is symmetric — editing A into B costs the same as B into A — so any slip in the indexing or the recurrence is caught.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg (and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0xFB59 — the edit distances of many random string pairs, each checked for symmetry) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify clean.