A dart into the net came back holding the little grid that every spell-checker, DNA aligner and diff tool secretly runs: the fewest single-character insert / delete / substitute moves to turn one string into another — found by filling a table where each cell is the best of its three neighbors. We show the method live, credit who actually built it, and stack it against two I-13 walls. Three prongs, one dart.
THE TECHNIQUE fill the grid · walk the min path
Cell d[i][j] = cheapest way to edit the first i letters of A into the first j letters of B. It is the smallest of three moves from its neighbors: delete (cell above +1), insert (cell left +1), or match / substitute (cell up-left, +0 if the letters agree else +1). The answer sits in the bottom-right corner; walk backward to recover the alignment. live demo
rows = A (down = delete) · cols = B (right = insert) · diagonal = match / sub · gold path = one optimal edit script
HISTORY & CREDIT credit where it is due
The name honors one man, but the metric and the algorithm that computes it are two different inventions by different people — and the fast table method was invented once re-discovered independently at least four times, in coding theory, speech, and biology, within a decade. cited
1965 · Vladimir I. Levenshtein (Keldysh Institute, USSR) — defines the metric in a coding-theory paper on codes that correct deletions, insertions and reversals. Russian 1965; English translation 1966. He defined what the distance is — not the efficient way to compute it. 1968 · Taras K. Vintsyuk — the same dynamic-programming alignment, independently, for speech recognition. 1970 · Saul Needleman & Christian Wunsch — the same DP grid, independently, for global sequence alignment in molecular biology. 1974 · Robert A. Wagner & Michael J. Fischer — “The String-to-String Correction Problem” (Journal of the ACM). This is the clean O(mn) table method taught today — the how behind Levenshtein’s what.
The common miscredit: people say “the Levenshtein algorithm” as if Levenshtein handed us the matrix. He handed us the definition; the matrix is Wagner–Fischer’s (and Vintsyuk’s, and Needleman–Wunsch’s). Still open: there is no single “first” inventor of the edit-distance DP — it is a textbook case of independent multiple discovery, so any single-name credit for the algorithm is a simplification. open
RECOMMEND FOR I-13 two walls, stacked
This technique leans on two things I-13 does not have, so it stacks two walls at once. I proved both on the live compiler — measured, not asserted.
Wall 1 — there is no string or char.Constant is f64 only; a string or char literal never even lexes:
$ i13 check str.i13 # I s <- "cat"
str.i13:1:8 E0001 unexpected character `"`
$ i13 check char.i13 # I c <- 'a'
char.i13:1:8 E0001 unexpected character `'` (exit 1)
Wall 2 — there is no aggregate / 2-D array. The DP needs a matrix; I-13 has no array literal and no subscript — the [ and ] are not in the alphabet at all:
$ i13 check arr.i13 # I a <- [1, 2, 3]
arr.i13:1:8 E0001 unexpected character `[`
$ i13 check idx.i13 # I v <- a[1]
idx.i13:2:9 E0001 unexpected character `[` (exit 1)
What it does have — f64 arithmetic over declared scalars — runs clean, which is the whole point of the boundary:
$ i13 run ok.i13 # d <- n - m ; dd <- d * d
RUN OK · 12 step(s) · peak stack 2 · call depth 0
n = 7 · m = 3 · d = 4 · dd = 16 (exit 0)
Recommend: a string/char type and a real array (aggregate + subscript) would unlock this whole family — edit distance, diff, search, DNA alignment. But flag it honestly: this is expensive, not a cheap add. Unlike the bit-op darts (a new BinOp discriminant costs zero new alphabet symbols), strings and arrays each demand a new value kind plus new AST node kinds — a string literal, an aggregate literal, and a subscript operator. The 13-symbol alphabet was counted, and the census deliberately excluded exactly these container/index nodes. So adding them is real alphabet growth against the counting identity. Verdict (honest): the string+array gap is most likely a deliberate scope boundary, not an oversight to patch. The cheapest in-scope path that keeps the alphabet fixed is the one examples/core.i13 already uses on purpose — pass the values explicitly as scalar parameters rather than indexing an array (its own comment: “No arrays/records are assumed”). Keep I-13 numeric; let the host hold the strings.