0 reported it broke · the ▶ count is distinct visitors who ran it, counted once each, anonymously
Edit distance is the smallest number of one-letter changes that turn one word into another, and the classic way to find it is a grid where every square answers the same small question: what did it cost to get here? This demo fills that grid one square at a time — showing the three neighbours each cell compares and which one wins — then reads the answer backwards out of the bottom-right corner as a real list of edits: substitute k→s, keep i, add g. It starts filling the moment you open it, so let kitten become sitting in three moves, then drag the scrubber back to any point and click a square to see exactly how that number was worked out. Type your own pair of words and the whole table rebuilds instantly.
Source — the code you see is the code that just ran 1016 lines 44.2 KB index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Edit Distance Matrix</title>
<style>
/* sloprun design tokens — inline this block into every demo (self-contained rule).
Identity: instrument-panel. Machine facts in mono; human words in sans.
Green is EARNED: only for "it ran / it worked" states, never decoration. */
:root {
--bg: #F6F6F3; /* neutral paper, not cream */
--surface: #FFFFFF;
--ink: #1A1D21;
--muted: #5A6068;
--line: #E3E2DC;
--accent: #C05600; /* phosphor amber, darkened for light bg */
--accent-soft: #FFF3E6;
--run: #1A7F37; /* earned green */
--run-soft: #E7F4EA;
--danger: #C93C37;
--radius: 10px;
--font-sans: system-ui, -apple-system, "Segoe UI", sans-serif;
--font-mono: ui-monospace, "SF Mono", "Cascadia Code", Menlo, Consolas, monospace;
}
@media (prefers-color-scheme: dark) {
:root:not([data-theme="light"]) {
--bg: #14161A; --surface: #1C1F26; --ink: #E8E6E1; --muted: #9AA0A8;
--line: #2A2E36; --accent: #FFB454; --accent-soft: #2A2118;
--run: #3FB950; --run-soft: #16281B; --danger: #F47067;
}
}
:root[data-theme="dark"] {
--bg: #14161A; --surface: #1C1F26; --ink: #E8E6E1; --muted: #9AA0A8;
--line: #2A2E36; --accent: #FFB454; --accent-soft: #2A2118;
--run: #3FB950; --run-soft: #16281B; --danger: #F47067;
}
body { background: var(--bg); color: var(--ink); font-family: var(--font-sans); }
/* ---- demo-local supplements: derived shades, defined for all three theme states ---- */
:root {
color-scheme: light;
--canvas: #FBFAF7; --sunk: #F0EFEA; --line-soft: #EEEDE7;
--on-accent: #FFFFFF; --danger-soft: #FBECEB;
--shadow: 0 1px 2px rgba(20,22,26,.06), 0 8px 22px -18px rgba(20,22,26,.4);
--cs: 40px; --gap: 3px;
}
@media (prefers-color-scheme: dark) {
:root:not([data-theme="light"]) {
color-scheme: dark;
--canvas: #171A20; --sunk: #21252C; --line-soft: #242830;
--on-accent: #14161A; --danger-soft: #2C1B1A;
--shadow: 0 1px 2px rgba(0,0,0,.4), 0 8px 22px -18px rgba(0,0,0,.9);
}
}
:root[data-theme="dark"] {
color-scheme: dark;
--canvas: #171A20; --sunk: #21252C; --line-soft: #242830;
--on-accent: #14161A; --danger-soft: #2C1B1A;
--shadow: 0 1px 2px rgba(0,0,0,.4), 0 8px 22px -18px rgba(0,0,0,.9);
}
:root[data-theme="light"] { color-scheme: light; }
* { box-sizing: border-box; }
html, body { margin: 0; padding: 0; }
/* Reserve the scrollbar so the grid does not have to re-measure when the
answer panel appears and makes the page tall enough to scroll. */
html { scrollbar-gutter: stable; }
body { line-height: 1.45; overflow-x: hidden; -webkit-text-size-adjust: 100%; }
.wrap { max-width: 1120px; margin: 0 auto; padding: 22px 14px 28px; }
/* ---------- header ---------- */
.chip {
display: inline-block; font-family: var(--font-mono); font-size: 10.5px;
letter-spacing: .08em; text-transform: uppercase; color: var(--accent);
background: var(--accent-soft); border: 1px solid var(--line);
border-radius: 999px; padding: 3px 9px; margin-bottom: 9px;
}
h1 { font-size: clamp(20px, 4.6vw, 25px); margin: 0 0 5px; letter-spacing: -.018em; }
.lede { margin: 0; color: var(--muted); font-size: 14.5px; max-width: 70ch; }
/* ---------- panels ---------- */
.panel {
background: var(--surface); border: 1px solid var(--line);
border-radius: var(--radius); box-shadow: var(--shadow); overflow: hidden;
}
.phead {
display: flex; align-items: center; gap: 9px; flex-wrap: wrap;
padding: 8px 12px; border-bottom: 1px solid var(--line); background: var(--canvas);
}
.phead h2 {
margin: 0; font-family: var(--font-mono); font-size: 11px; font-weight: 600;
letter-spacing: .1em; text-transform: uppercase; color: var(--muted);
}
.spacer { flex: 1 1 auto; }
.pill {
font-family: var(--font-mono); font-size: 10.5px; letter-spacing: .05em;
border: 1px solid var(--line); border-radius: 999px; padding: 2px 9px;
color: var(--muted); background: var(--surface); white-space: nowrap;
}
.pill.on { color: var(--accent); border-color: var(--accent); background: var(--accent-soft); }
.pill.ok { color: var(--run); border-color: var(--run); background: var(--run-soft); }
/* ---------- controls ---------- */
.bar { display: flex; align-items: flex-end; gap: 10px; flex-wrap: wrap; padding: 12px; }
.bar + .bar { border-top: 1px solid var(--line-soft); align-items: center; }
.field { display: flex; flex-direction: column; gap: 4px; min-width: 0; }
.field > label {
font-family: var(--font-mono); font-size: 10px; letter-spacing: .1em;
text-transform: uppercase; color: var(--muted);
}
input[type=text] {
font-family: var(--font-mono); font-size: 16px; letter-spacing: .06em;
color: var(--ink); background: var(--canvas); border: 1px solid var(--line);
border-radius: 8px; padding: 7px 10px; width: 9.4em; max-width: 42vw;
}
input[type=text]:hover { border-color: var(--muted); }
select {
font-family: var(--font-mono); font-size: 12px; color: var(--ink);
background: var(--canvas); border: 1px solid var(--line);
border-radius: 8px; padding: 6px 8px;
}
button {
font-family: var(--font-sans); font-size: 13px; color: var(--ink);
background: var(--surface); border: 1px solid var(--line);
border-radius: 8px; padding: 7px 12px; cursor: pointer; white-space: nowrap;
}
button:hover:not(:disabled) { border-color: var(--muted); background: var(--canvas); }
button:disabled { opacity: .42; cursor: default; }
button.primary {
background: var(--accent); border-color: var(--accent); color: var(--on-accent);
font-weight: 600; min-width: 82px;
}
button.primary:hover:not(:disabled) { filter: brightness(1.07); background: var(--accent); }
button.icon { padding: 7px 10px; min-height: 34px; font-family: var(--font-mono); font-size: 15px; line-height: 1; }
button.tiny {
font-family: var(--font-mono); font-size: 11px; padding: 5px 10px; min-height: 28px;
color: var(--muted); border-radius: 999px;
}
button.tiny[aria-pressed="true"] { color: var(--accent); border-color: var(--accent); background: var(--accent-soft); }
:focus-visible { outline: 2px solid var(--accent); outline-offset: 2px; }
/* scrubber */
.scrub { display: flex; align-items: center; gap: 10px; padding: 0 12px 12px; }
.scrub .tick { font-family: var(--font-mono); font-size: 11px; color: var(--muted); white-space: nowrap; }
input[type=range] { -webkit-appearance: none; appearance: none; flex: 1 1 auto; min-width: 90px; height: 20px; background: transparent; }
input[type=range]::-webkit-slider-runnable-track { height: 4px; border-radius: 4px; background: var(--sunk); border: 1px solid var(--line); }
input[type=range]::-moz-range-track { height: 4px; border-radius: 4px; background: var(--sunk); border: 1px solid var(--line); }
input[type=range]::-webkit-slider-thumb {
-webkit-appearance: none; appearance: none; width: 15px; height: 15px; margin-top: -6px;
border-radius: 50%; background: var(--accent); border: 2px solid var(--surface); cursor: pointer;
}
input[type=range]::-moz-range-thumb {
width: 13px; height: 13px; border-radius: 50%; background: var(--accent);
border: 2px solid var(--surface); cursor: pointer;
}
/* ---------- stats ---------- */
.stats {
display: grid; grid-template-columns: repeat(auto-fit, minmax(74px, 1fr));
gap: 1px; background: var(--line-soft); border-top: 1px solid var(--line-soft);
}
.stat { padding: 8px 10px; background: var(--surface); }
.stat .lab { font-family: var(--font-mono); font-size: 9.5px; letter-spacing: .09em; text-transform: uppercase; color: var(--muted); }
.stat .val { font-family: var(--font-mono); font-size: 17px; font-variant-numeric: tabular-nums; margin-top: 1px; }
.stat .val.dim { color: var(--muted); }
/* ---------- layout ---------- */
.cols { display: grid; grid-template-columns: 1fr; gap: 14px; margin-top: 14px; align-items: start; }
@media (min-width: 900px) { .cols { grid-template-columns: minmax(0, 1.32fr) minmax(300px, 1fr); } }
/* ---------- matrix ---------- */
#mwrap { overflow-x: auto; overflow-y: hidden; padding: 14px 12px; background: var(--canvas); }
.matrix { display: grid; gap: var(--gap); width: max-content; margin: 0 auto; }
.mrow { display: contents; }
.hd {
display: flex; align-items: center; justify-content: center;
font-family: var(--font-mono); font-size: calc(var(--cs) * .38); color: var(--muted);
border-radius: 6px;
}
.hd.hot { color: var(--accent); background: var(--accent-soft); }
.hd.eps { font-size: calc(var(--cs) * .32); opacity: .75; }
.cell {
position: relative; display: flex; align-items: center; justify-content: center;
border: 1px solid var(--line); border-radius: 6px; background: var(--surface);
font-family: var(--font-mono); font-variant-numeric: tabular-nums;
font-size: calc(var(--cs) * .40); color: var(--ink);
cursor: pointer; user-select: none; transition: background-color .16s, border-color .16s, color .16s, transform .16s;
}
.cell .v { line-height: 1; }
.cell .ar {
position: absolute; top: 1px; left: 3px; font-size: calc(var(--cs) * .27);
line-height: 1; color: var(--muted); opacity: .5; letter-spacing: -.06em; pointer-events: none;
}
.matrix.tight .cell:not(.path) .ar { display: none; }
.matrix.tight .ar { top: 0; left: 2px; font-size: calc(var(--cs) * .30); }
.cell.todo { background: var(--sunk); border-color: transparent; color: transparent; }
.cell.todo .ar { display: none; }
.cell.base { background: var(--surface); color: var(--muted); border-style: dashed; }
.cell.path { background: var(--accent-soft); border-color: var(--accent); color: var(--ink); font-weight: 600; }
.cell.path .ar { color: var(--accent); opacity: 1; }
.cell.src { border-color: var(--muted); }
.cell.src::after {
content: ""; position: absolute; inset: -3px; border-radius: 8px;
border: 1px dashed var(--muted); opacity: .65;
}
.cell.active {
background: var(--accent); border-color: var(--accent); color: var(--on-accent);
font-weight: 700; z-index: 2; transform: scale(1.06);
}
.cell.active .ar { color: var(--on-accent); opacity: .8; }
.cell.goal.done { box-shadow: inset 0 0 0 2px var(--run); }
.cell.sel { box-shadow: 0 0 0 2px var(--ink); z-index: 3; }
.cell:hover:not(.todo) { border-color: var(--accent); }
/* ---------- narration ---------- */
.narr { padding: 11px 12px; border-top: 1px solid var(--line-soft); }
.say { margin: 0; font-size: 14px; min-height: 2.9em; }
.say b { color: var(--accent); font-family: var(--font-mono); font-weight: 700; }
.say .lit { font-family: var(--font-mono); background: var(--sunk); border-radius: 4px; padding: 0 4px; }
.calc {
margin-top: 8px; font-family: var(--font-mono); font-size: 12px; color: var(--muted);
background: var(--sunk); border: 1px solid var(--line); border-radius: 7px;
padding: 7px 9px; overflow-x: auto; white-space: nowrap;
}
.calc em { font-style: normal; color: var(--accent); font-weight: 700; }
.legend { display: flex; flex-wrap: wrap; gap: 10px; padding: 9px 12px; border-top: 1px solid var(--line-soft); }
.lg { display: inline-flex; align-items: center; gap: 5px; font-family: var(--font-mono); font-size: 10px; color: var(--muted); }
.sw { width: 12px; height: 12px; border-radius: 3px; border: 1px solid var(--line); display: inline-block; }
.sw.w-todo { background: var(--sunk); border-color: transparent; }
.sw.w-base { background: var(--surface); border-style: dashed; }
.sw.w-act { background: var(--accent); border-color: var(--accent); }
.sw.w-path { background: var(--accent-soft); border-color: var(--accent); }
/* ---------- answer ---------- */
.big { display: flex; align-items: baseline; gap: 11px; padding: 14px 14px 10px; }
.num {
font-family: var(--font-mono); font-size: 58px; line-height: .9; font-weight: 700;
letter-spacing: -.03em; font-variant-numeric: tabular-nums; color: var(--muted);
}
.num.final { color: var(--run); }
.cap { font-size: 13px; color: var(--muted); }
.cap b { color: var(--ink); font-family: var(--font-mono); }
.align { padding: 2px 14px 12px; overflow-x: auto; }
.aligrid { display: flex; gap: 3px; width: max-content; }
.acol { display: flex; flex-direction: column; align-items: center; gap: 2px; min-width: 24px; }
.acol .ch {
font-family: var(--font-mono); font-size: 15px; line-height: 1.35; width: 100%; text-align: center;
border-radius: 4px; background: var(--sunk); color: var(--ink);
}
.acol .ch.gap { color: var(--muted); background: transparent; border: 1px dashed var(--line); }
.acol .mk { font-family: var(--font-mono); font-size: 10px; color: var(--muted); line-height: 1; }
.acol.op-sub .ch { background: var(--accent); color: var(--on-accent); }
.acol.op-sub .mk { color: var(--accent); }
.acol.op-ins .ch:not(.gap) { background: var(--accent-soft); color: var(--accent); box-shadow: inset 0 0 0 1px var(--accent); }
.acol.op-ins .mk { color: var(--accent); }
.acol.op-del .ch:not(.gap) { background: var(--danger-soft); color: var(--danger); box-shadow: inset 0 0 0 1px var(--danger); }
.acol.op-del .mk { color: var(--danger); }
.acol.hot { outline: 2px solid var(--ink); outline-offset: 2px; border-radius: 5px; }
.script { border-top: 1px solid var(--line-soft); }
.script .row {
display: flex; align-items: center; gap: 9px; padding: 7px 14px;
border-bottom: 1px solid var(--line-soft); font-size: 13px; cursor: pointer;
background: none; border-left: 0; border-right: 0; border-top: 0; width: 100%; text-align: left;
border-radius: 0;
}
.script .row:last-child { border-bottom: 0; }
.script .row:hover, .script .row.hot { background: var(--canvas); }
.script .row .tag {
font-family: var(--font-mono); font-size: 10px; letter-spacing: .06em; text-transform: uppercase;
padding: 2px 7px; border-radius: 999px; border: 1px solid var(--line); color: var(--muted);
white-space: nowrap; min-width: 84px; text-align: center;
}
.script .row.t-sub .tag { background: var(--accent); border-color: var(--accent); color: var(--on-accent); }
.script .row.t-ins .tag { background: var(--accent-soft); border-color: var(--accent); color: var(--accent); }
.script .row.t-del .tag { background: var(--danger-soft); border-color: var(--danger); color: var(--danger); }
.script .row .txt { flex: 1 1 auto; min-width: 0; }
.script .row .txt code { font-family: var(--font-mono); font-weight: 700; }
.script .row .at { font-family: var(--font-mono); font-size: 10.5px; color: var(--muted); }
.script .row.free { color: var(--muted); }
.script .empty { padding: 12px 14px; color: var(--muted); font-size: 13px; }
.script.fresh .row { animation: pop .3s ease-out both; }
@keyframes pop { from { opacity: .25; transform: translateY(-3px); } to { opacity: 1; transform: none; } }
.hint { margin: 12px 2px 0; font-size: 12px; color: var(--muted); }
kbd {
font-family: var(--font-mono); font-size: 10.5px; border: 1px solid var(--line);
border-bottom-width: 2px; border-radius: 4px; padding: 1px 5px; background: var(--surface); color: var(--ink);
}
footer { margin-top: 16px; font-family: var(--font-mono); font-size: 11px; color: var(--muted); letter-spacing: .05em; }
.sr { position: absolute; width: 1px; height: 1px; overflow: hidden; clip: rect(0 0 0 0); white-space: nowrap; }
@media (prefers-reduced-motion: reduce) {
* { transition: none !important; animation: none !important; }
.cell.active { transform: none; }
}
</style>
</head>
<body>
<div class="wrap">
<header>
<span class="chip">dynamic programming</span>
<h1>Edit Distance Matrix</h1>
<p class="lede">The smallest number of one-letter changes that turn the first word into the second. Every square in
the grid answers the same small question — and the answer walks back out of the bottom-right corner.</p>
</header>
<section class="panel" style="margin-top:14px">
<div class="phead">
<h2>words</h2>
<span class="spacer"></span>
<span class="pill" id="status">ready</span>
</div>
<div class="bar">
<div class="field">
<label for="wa">from</label>
<input id="wa" type="text" value="kitten" maxlength="12" autocomplete="off" autocapitalize="off" autocorrect="off" spellcheck="false">
</div>
<button class="icon" id="swap" title="Swap the two words" aria-label="Swap the two words">⇆</button>
<div class="field">
<label for="wb">into</label>
<input id="wb" type="text" value="sitting" maxlength="12" autocomplete="off" autocapitalize="off" autocorrect="off" spellcheck="false">
</div>
<span class="spacer"></span>
<div class="field" style="flex-direction:row;gap:6px;flex-wrap:wrap">
<button class="tiny" data-pair="kitten|sitting">kitten→sitting</button>
<button class="tiny" data-pair="recieve|receive">recieve→receive</button>
<button class="tiny" data-pair="flaw|lawn">flaw→lawn</button>
<button class="tiny" data-pair="sunday|saturday">sunday→saturday</button>
</div>
</div>
<div class="bar">
<button class="primary" id="play">Play</button>
<button id="back">◀︎ Back</button>
<button id="fwd">Step ▶︎</button>
<button id="reset">Reset</button>
<span class="spacer"></span>
<div class="field" style="flex-direction:row;align-items:center;gap:6px">
<label for="speed" style="margin:0">speed</label>
<select id="speed">
<option value="460">slow</option>
<option value="190" selected>normal</option>
<option value="70">fast</option>
</select>
</div>
</div>
<div class="scrub">
<span class="tick" id="tick">0 / 0</span>
<input id="range" type="range" min="0" max="0" value="0" step="1" aria-label="Scrub through the fill steps">
</div>
<div class="stats">
<div class="stat"><div class="lab">distance</div><div class="val dim" id="sDist">–</div></div>
<div class="stat"><div class="lab">keep</div><div class="val dim" id="sKeep">–</div></div>
<div class="stat"><div class="lab">substitute</div><div class="val dim" id="sSub">–</div></div>
<div class="stat"><div class="lab">insert</div><div class="val dim" id="sIns">–</div></div>
<div class="stat"><div class="lab">delete</div><div class="val dim" id="sDel">–</div></div>
<div class="stat"><div class="lab">solved</div><div class="val" id="sCells">0 / 0</div></div>
</div>
</section>
<div class="cols">
<section class="panel">
<div class="phead">
<h2>the grid</h2>
<span class="spacer"></span>
<span class="pill" id="dims">0 × 0</span>
</div>
<div id="mwrap">
<div class="matrix" id="matrix" role="grid" aria-label="Edit distance grid"></div>
</div>
<div class="narr">
<p class="say" id="say"></p>
<div class="calc" id="calc"></div>
</div>
<div class="legend">
<span class="lg"><span class="sw w-todo"></span>not filled yet</span>
<span class="lg"><span class="sw w-base"></span>free edge</span>
<span class="lg"><span class="sw w-act"></span>solving now</span>
<span class="lg"><span class="sw w-path"></span>cheapest trail</span>
<span class="lg"><span style="font-family:var(--font-mono)">↖↑←</span>where the value came from</span>
</div>
</section>
<section class="panel">
<div class="phead">
<h2>the answer</h2>
<span class="spacer"></span>
<span class="pill" id="rpill">filling…</span>
</div>
<div class="big">
<div class="num" id="bignum">–</div>
<div class="cap" id="bigcap">edits to turn <b id="capA">kitten</b> into <b id="capB">sitting</b></div>
</div>
<div class="align" id="align"></div>
<div class="script" id="script"></div>
</section>
</div>
<p class="hint"><kbd>Space</kbd> play / pause · <kbd>←</kbd><kbd>→</kbd> one square at a time ·
arrow keys inside the grid walk the squares, <kbd>Esc</kbd> stops inspecting.
<span style="font-family:var(--font-mono)">ε</span> is the empty word — nothing at all.</p>
<p class="sr" id="live" role="status" aria-live="polite"></p>
<footer>demo · sloprun.dev</footer>
</div>
<script>
(function () {
"use strict";
/* ---------- theme: platform postMessage + standalone prefers-color-scheme ---------- */
window.addEventListener("message", function (e) {
var d = e && e.data;
if (d && d.type === "sloprun:theme" && (d.theme === "light" || d.theme === "dark")) {
document.documentElement.setAttribute("data-theme", d.theme);
}
});
var $ = function (id) { return document.getElementById(id); };
var mqm = window.matchMedia ? window.matchMedia("(prefers-reduced-motion: reduce)") : null;
function reduced() { return !!(mqm && mqm.matches); }
var EPS = "ε", ARR = { d: "↖", u: "↑", l: "←" };
var el = {
wa: $("wa"), wb: $("wb"), swap: $("swap"), play: $("play"), back: $("back"), fwd: $("fwd"),
reset: $("reset"), speed: $("speed"), range: $("range"), tick: $("tick"), status: $("status"),
matrix: $("matrix"), mwrap: $("mwrap"), dims: $("dims"), say: $("say"), calc: $("calc"),
bignum: $("bignum"), bigcap: $("bigcap"), capA: $("capA"), capB: $("capB"),
align: $("align"), script: $("script"), rpill: $("rpill"), live: $("live"),
sDist: $("sDist"), sKeep: $("sKeep"), sSub: $("sSub"), sIns: $("sIns"), sDel: $("sDel"), sCells: $("sCells")
};
var S = {
A: "kitten", B: "sitting", D: null, dirs: null, m: 0, n: 0,
total: 0, step: 0, playing: false, timer: 0, announced: false, cs: 0,
ops: [], onPath: null, sel: null, cur: null, cells: [], rowH: [], colH: []
};
function esc(s) {
return String(s).replace(/[&<>"]/g, function (c) {
return { "&": "&", "<": "<", ">": ">", '"': """ }[c];
});
}
function show(ch) { return ch === " " ? "␣" : esc(ch); }
/* ---------- 1. the computation ---------- */
function compute() {
var A = S.A, B = S.B, m = A.length, n = B.length, i, j;
var D = [], dirs = [];
for (i = 0; i <= m; i++) { D.push(new Array(n + 1)); dirs.push(new Array(n + 1)); }
for (i = 0; i <= m; i++) { D[i][0] = i; dirs[i][0] = i ? "u" : ""; }
for (j = 0; j <= n; j++) { D[0][j] = j; dirs[0][j] = j ? "l" : ""; }
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
var same = A.charAt(i - 1) === B.charAt(j - 1);
var dv = D[i - 1][j - 1] + (same ? 0 : 1);
var uv = D[i - 1][j] + 1;
var lv = D[i][j - 1] + 1;
var best = Math.min(dv, uv, lv);
D[i][j] = best;
var w = "";
if (dv === best) w += "d";
if (uv === best) w += "u";
if (lv === best) w += "l";
dirs[i][j] = w;
}
}
S.D = D; S.dirs = dirs; S.m = m; S.n = n; S.total = m * n;
/* traceback: prefer diagonal (keep, then substitute), then delete, then insert */
var ops = [], path = {};
i = m; j = n;
path[i + "," + j] = true;
while (i > 0 || j > 0) {
var a = i > 0 ? A.charAt(i - 1) : "", b = j > 0 ? B.charAt(j - 1) : "";
if (i > 0 && j > 0 && a === b && D[i][j] === D[i - 1][j - 1]) {
ops.push({ k: "keep", a: a, b: b, i: i, j: j }); i--; j--;
} else if (i > 0 && j > 0 && D[i][j] === D[i - 1][j - 1] + 1) {
ops.push({ k: "sub", a: a, b: b, i: i, j: j }); i--; j--;
} else if (i > 0 && D[i][j] === D[i - 1][j] + 1) {
ops.push({ k: "del", a: a, b: "", i: i, j: j }); i--;
} else {
ops.push({ k: "ins", a: "", b: b, i: i, j: j }); j--;
}
path[i + "," + j] = true;
}
ops.reverse();
S.ops = ops; S.onPath = path;
}
function cellOfStep(k) { /* step k (1-based) -> [i,j] filled at that step */
if (k < 1 || k > S.total) return null;
var z = k - 1;
return [Math.floor(z / S.n) + 1, (z % S.n) + 1];
}
function isFilled(i, j) {
if (i === 0 || j === 0) return true;
return ((i - 1) * S.n + j) <= S.step;
}
function done() { return S.step >= S.total; }
/* ---------- 2. build the grid DOM ---------- */
function build() {
var m = S.m, n = S.n, i, j;
el.matrix.textContent = "";
S.cells = []; S.rowH = []; S.colH = []; S.cs = 0; /* column count changed: re-measure */
el.matrix.style.gridTemplateColumns = "repeat(" + (n + 2) + ", var(--cs))";
el.matrix.style.gridAutoRows = "var(--cs)";
function mkRow() {
var r = document.createElement("div");
r.className = "mrow"; r.setAttribute("role", "row");
el.matrix.appendChild(r);
return r;
}
var head = mkRow();
var corner = document.createElement("div");
corner.className = "hd";
corner.setAttribute("role", "columnheader");
corner.appendChild(document.createTextNode(""));
head.appendChild(corner);
for (j = 0; j <= n; j++) {
var ch = document.createElement("div");
ch.className = "hd" + (j === 0 ? " eps" : "");
ch.setAttribute("role", "columnheader");
ch.textContent = j === 0 ? EPS : (S.B.charAt(j - 1) === " " ? "␣" : S.B.charAt(j - 1));
head.appendChild(ch);
S.colH.push(ch);
}
for (i = 0; i <= m; i++) {
var row = mkRow();
var rh = document.createElement("div");
rh.className = "hd" + (i === 0 ? " eps" : "");
rh.setAttribute("role", "rowheader");
rh.textContent = i === 0 ? EPS : (S.A.charAt(i - 1) === " " ? "␣" : S.A.charAt(i - 1));
row.appendChild(rh);
S.rowH.push(rh);
S.cells.push([]);
for (j = 0; j <= n; j++) {
var c = document.createElement("div");
c.className = "cell";
c.setAttribute("role", "gridcell");
c.setAttribute("tabindex", "-1");
c.dataset.i = i; c.dataset.j = j;
var ar = document.createElement("span"); ar.className = "ar";
var v = document.createElement("span"); v.className = "v";
c.appendChild(ar); c.appendChild(v);
row.appendChild(c);
S.cells[i].push(c);
}
}
sizeGrid();
}
function sizeGrid() {
var cols = S.n + 2;
var avail = (el.mwrap.clientWidth || 320) - 24; /* minus the wrapper's own padding */
var cs = Math.floor((avail - 3 * (cols - 1)) / cols);
cs = Math.max(26, Math.min(46, cs));
if (cs === S.cs) return;
S.cs = cs;
document.documentElement.style.setProperty("--cs", cs + "px");
el.matrix.classList.toggle("tight", cs < 32);
}
/* ---------- 3. paint a step ---------- */
function paint() {
var m = S.m, n = S.n, i, j;
var fin = done();
S.cur = fin ? null : cellOfStep(S.step);
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
var c = S.cells[i][j], cls = "cell";
var filled = isFilled(i, j);
if (!filled) cls += " todo";
else if (i === 0 || j === 0) cls += " base";
if (fin && S.onPath[i + "," + j]) cls += " path";
if (S.cur && S.cur[0] === i && S.cur[1] === j) cls += " active";
if (S.cur && !fin) {
var ci = S.cur[0], cj = S.cur[1];
if ((i === ci - 1 && j === cj - 1) || (i === ci - 1 && j === cj) || (i === ci && j === cj - 1)) cls += " src";
}
if (i === m && j === n) cls += " goal";
if (fin) cls += " done";
if (S.sel && S.sel[0] === i && S.sel[1] === j) cls += " sel";
c.className = cls;
c.children[1].textContent = filled ? S.D[i][j] : "";
c.children[0].textContent = filled ? dirGlyphs(i, j) : "";
c.setAttribute("aria-label", cellLabel(i, j, filled));
}
}
for (i = 0; i <= m; i++) S.rowH[i].classList.toggle("hot", !!(S.cur && S.cur[0] === i));
for (j = 0; j <= n; j++) S.colH[j].classList.toggle("hot", !!(S.cur && S.cur[1] === j));
var focusCell = S.sel || S.cur || (fin ? [m, n] : [0, 0]);
for (i = 0; i <= m; i++) for (j = 0; j <= n; j++)
S.cells[i][j].setAttribute("tabindex", (i === focusCell[0] && j === focusCell[1]) ? "0" : "-1");
el.range.value = S.step;
el.tick.textContent = S.step + " / " + S.total;
el.sCells.textContent = S.step + " / " + S.total;
el.dims.textContent = (m + 1) + " × " + (n + 1) + " grid";
el.back.disabled = S.step === 0;
el.fwd.disabled = fin;
el.play.disabled = S.total === 0;
el.range.disabled = S.total === 0;
el.reset.disabled = S.step === 0;
el.play.textContent = S.playing ? "Pause" : (fin ? "Replay" : "Play");
el.status.className = "pill" + (fin ? " ok" : (S.playing ? " on" : ""));
el.status.textContent = fin ? "solved" : (S.playing ? "filling" : (S.step ? "paused" : "ready"));
paintAnswer(fin);
narrate();
}
function dirGlyphs(i, j) {
if (i === 0 && j === 0) return "";
var w = S.dirs[i][j] || "", out = "";
if (done() && S.onPath[i + "," + j]) {
/* on the final trail, show only the arrow the traceback actually took */
var t = takenDir(i, j);
return t ? ARR[t] : "";
}
if (w.indexOf("d") >= 0) out += ARR.d;
if (w.indexOf("u") >= 0) out += ARR.u;
if (w.indexOf("l") >= 0) out += ARR.l;
return out;
}
function takenDir(i, j) {
for (var k = 0; k < S.ops.length; k++) {
var o = S.ops[k];
if (o.i === i && o.j === j) return (o.k === "keep" || o.k === "sub") ? "d" : (o.k === "del" ? "u" : "l");
}
return "";
}
function cellLabel(i, j, filled) {
var ra = i === 0 ? "empty word" : S.A.charAt(i - 1);
var cb = j === 0 ? "empty word" : S.B.charAt(j - 1);
var where = "row " + i + " " + ra + ", column " + j + " " + cb;
if (!filled) return where + ", not filled yet";
return where + ", value " + S.D[i][j];
}
/* ---------- 4. narration ---------- */
function narrate() {
var t = S.sel || S.cur;
if (!t) {
if (S.total > 0 && done()) {
var dd = S.D[S.m][S.n];
el.say.innerHTML = "The grid is full. The bottom-right square is the answer: <b>" + dd + "</b> edit" +
(dd === 1 ? "" : "s") + ". Follow its arrows back out — each hop is one line of the edit list. " +
"Click any square to see how it was worked out.";
el.calc.innerHTML = "D[" + S.m + "][" + S.n + "] = <em>" + dd + "</em> ← the answer";
return;
}
if (S.total === 0) {
el.say.innerHTML = S.m === 0 && S.n === 0
? "Both words are empty, so there is nothing to do."
: "One word is empty, so the whole answer sits in the free edge: every letter of the other word is a single edit.";
el.calc.textContent = "D[" + S.m + "][" + S.n + "] = " + S.D[S.m][S.n];
return;
}
el.say.innerHTML = "The top row and left column are free. Turning a word into <span class=\"lit\">" + EPS +
"</span> costs one delete per letter, and building it up from <span class=\"lit\">" + EPS +
"</span> costs one insert per letter. Everything else gets filled in from its three neighbours. Press <b>Play</b>.";
el.calc.textContent = "D[i][0] = i D[0][j] = j";
return;
}
var i = t[0], j = t[1];
if (!isFilled(i, j)) {
el.say.innerHTML = "Square <span class=\"lit\">[" + i + "][" + j + "]</span> has not been filled in yet — step forward to reach it.";
el.calc.textContent = "—";
return;
}
if (i === 0 && j === 0) {
el.say.innerHTML = "The corner: empty word into empty word. Nothing to change, so it costs <b>0</b>.";
el.calc.textContent = "D[0][0] = 0";
return;
}
if (i === 0) {
el.say.innerHTML = "Free edge: starting from nothing, spelling out <span class=\"lit\">" +
esc(S.B.slice(0, j)) + "</span> takes <b>" + j + "</b> insert" + (j === 1 ? "" : "s") + ".";
el.calc.textContent = "D[0][" + j + "] = " + j + " (insert every letter)";
return;
}
if (j === 0) {
el.say.innerHTML = "Free edge: reducing <span class=\"lit\">" + esc(S.A.slice(0, i)) +
"</span> to nothing takes <b>" + i + "</b> delete" + (i === 1 ? "" : "s") + ".";
el.calc.textContent = "D[" + i + "][0] = " + i + " (delete every letter)";
return;
}
var a = S.A.charAt(i - 1), b = S.B.charAt(j - 1), same = a === b;
var dv = S.D[i - 1][j - 1] + (same ? 0 : 1), uv = S.D[i - 1][j] + 1, lv = S.D[i][j - 1] + 1;
var best = S.D[i][j], w = S.dirs[i][j];
var names = [];
if (w.indexOf("d") >= 0) names.push(same ? "keep" : "substitute");
if (w.indexOf("u") >= 0) names.push("delete");
if (w.indexOf("l") >= 0) names.push("insert");
var lead = same
? "<span class=\"lit\">" + show(a) + "</span> matches <span class=\"lit\">" + show(b) +
"</span>, so the diagonal comes through for free."
: "<span class=\"lit\">" + show(a) + "</span> against <span class=\"lit\">" + show(b) +
"</span> — no match, so whichever neighbour is cheapest costs one more.";
el.say.innerHTML = lead + " Best move here: <b>" + names.join(" or ") + "</b>, total <b>" + best + "</b>.";
el.calc.innerHTML =
"D[" + i + "][" + j + "] = min( " +
(w.indexOf("d") >= 0 ? "<em>" : "") + dv + (w.indexOf("d") >= 0 ? "</em>" : "") + " ↖ , " +
(w.indexOf("u") >= 0 ? "<em>" : "") + uv + (w.indexOf("u") >= 0 ? "</em>" : "") + " ↑ , " +
(w.indexOf("l") >= 0 ? "<em>" : "") + lv + (w.indexOf("l") >= 0 ? "</em>" : "") +
" ← ) = <em>" + best + "</em>";
}
/* ---------- 5. the answer panel ---------- */
var LABEL = { keep: "keep", sub: "substitute", del: "delete", ins: "insert" };
var MARK = { keep: "=", sub: "✖", del: "−", ins: "+" };
function paintAnswer(fin) {
el.capA.textContent = S.A.length ? S.A : EPS;
el.capB.textContent = S.B.length ? S.B : EPS;
if (!fin) {
S.announced = false;
el.bignum.textContent = "–";
el.bignum.className = "num";
el.rpill.className = "pill" + (S.playing ? " on" : "");
el.rpill.textContent = S.total ? "filling…" : "no work to do";
["sDist", "sKeep", "sSub", "sIns", "sDel"].forEach(function (k) {
el[k].textContent = "–"; el[k].className = "val dim";
});
el.align.textContent = "";
el.script.className = "script";
el.script.innerHTML = '<p class="empty">The list of edits appears once the grid is full — it is read backwards out of the bottom-right square.</p>';
return;
}
var d = S.D[S.m][S.n];
el.bignum.textContent = d;
el.bignum.className = "num final";
el.rpill.className = "pill ok";
el.rpill.textContent = "solved";
var cnt = { keep: 0, sub: 0, del: 0, ins: 0 };
S.ops.forEach(function (o) { cnt[o.k]++; });
el.sDist.textContent = d; el.sDist.className = "val";
el.sKeep.textContent = cnt.keep; el.sKeep.className = "val" + (cnt.keep ? "" : " dim");
el.sSub.textContent = cnt.sub; el.sSub.className = "val" + (cnt.sub ? "" : " dim");
el.sIns.textContent = cnt.ins; el.sIns.className = "val" + (cnt.ins ? "" : " dim");
el.sDel.textContent = cnt.del; el.sDel.className = "val" + (cnt.del ? "" : " dim");
/* alignment strip */
var g = document.createElement("div");
g.className = "aligrid";
S.ops.forEach(function (o, idx) {
var col = document.createElement("div");
col.className = "acol op-" + o.k;
col.dataset.idx = idx;
var top = document.createElement("div");
top.className = "ch" + (o.a ? "" : " gap");
top.textContent = o.a ? show(o.a) : "·";
var mk = document.createElement("div");
mk.className = "mk"; mk.textContent = MARK[o.k];
var bot = document.createElement("div");
bot.className = "ch" + (o.b ? "" : " gap");
bot.textContent = o.b ? show(o.b) : "·";
col.appendChild(top); col.appendChild(mk); col.appendChild(bot);
g.appendChild(col);
});
el.align.textContent = "";
if (S.ops.length) el.align.appendChild(g);
/* edit script */
el.script.textContent = "";
el.script.className = "script" + (reduced() ? "" : " fresh");
if (!S.ops.length) {
el.script.innerHTML = '<p class="empty">Nothing to change — the two words are already the same.</p>';
} else {
S.ops.forEach(function (o, idx) {
var r = document.createElement("button");
r.type = "button";
r.className = "row t-" + o.k + (o.k === "keep" ? " free" : "");
if (!reduced()) r.style.animationDelay = Math.min(idx * 30, 240) + "ms";
r.dataset.idx = idx;
r.dataset.i = o.i; r.dataset.j = o.j;
var tag = document.createElement("span");
tag.className = "tag"; tag.textContent = LABEL[o.k];
var txt = document.createElement("span");
txt.className = "txt";
if (o.k === "keep") txt.innerHTML = "<code>" + show(o.a) + "</code> stays as it is";
else if (o.k === "sub") txt.innerHTML = "<code>" + show(o.a) + "</code> → <code>" + show(o.b) + "</code>";
else if (o.k === "del") txt.innerHTML = "drop <code>" + show(o.a) + "</code>";
else txt.innerHTML = "add <code>" + show(o.b) + "</code>";
var at = document.createElement("span");
at.className = "at"; at.textContent = "[" + o.i + "][" + o.j + "]";
r.appendChild(tag); r.appendChild(txt); r.appendChild(at);
el.script.appendChild(r);
});
}
/* announce the result once per entry into the solved state, so that
inspecting squares afterwards does not re-read the whole summary */
if (!S.announced) {
S.announced = true;
say(d === 0
? "Solved. The words are identical — zero edits."
: "Solved in " + d + " edit" + (d === 1 ? "" : "s") + ": " + S.ops.filter(function (o) { return o.k !== "keep"; })
.map(function (o) { return LABEL[o.k] + " " + (o.a || "") + (o.k === "sub" ? " to " + o.b : o.b); }).join(", ") + ".");
}
}
function say(msg) { el.live.textContent = msg; }
/* ---------- 6. transport ---------- */
function reset(keepStep) {
stop();
S.step = keepStep ? Math.min(S.step, S.total) : 0;
S.sel = null;
el.range.max = S.total;
paint();
}
function stepTo(k) {
S.step = Math.max(0, Math.min(S.total, k));
S.sel = null;
paint();
}
function stop() {
S.playing = false;
if (S.timer) { clearTimeout(S.timer); S.timer = 0; }
}
function tickOnce() {
if (!S.playing) return;
if (done()) { stop(); paint(); return; }
S.step++;
S.sel = null;
paint();
if (done()) { stop(); paint(); return; }
S.timer = setTimeout(tickOnce, +el.speed.value);
}
function togglePlay() {
if (S.playing) { stop(); paint(); return; }
if (S.total === 0) { paint(); return; }
if (done()) S.step = 0;
S.sel = null;
S.playing = true;
paint();
S.timer = setTimeout(tickOnce, +el.speed.value);
}
/* ---------- 7. words ---------- */
function clean(v) { return String(v).replace(/\s+/g, "").slice(0, 12); }
function load(a, b) {
el.wa.value = a; el.wb.value = b;
apply();
kickoff();
}
/* Never sit on a blank grid: the fill runs itself on load and on any
one-click word change. With reduced motion we jump straight to solved. */
function kickoff() {
if (S.total === 0) { paint(); return; }
if (reduced()) { S.step = S.total; S.sel = null; paint(); return; }
togglePlay();
}
function apply() {
stop();
S.A = clean(el.wa.value);
S.B = clean(el.wb.value);
if (el.wa.value !== S.A) el.wa.value = S.A;
if (el.wb.value !== S.B) el.wb.value = S.B;
compute();
S.step = 0; S.sel = null; S.announced = false;
el.range.max = S.total;
el.range.value = 0;
build();
markPresets();
paint();
}
function markPresets() {
var key = S.A + "|" + S.B;
Array.prototype.forEach.call(document.querySelectorAll("button.tiny[data-pair]"), function (b) {
b.setAttribute("aria-pressed", b.dataset.pair === key ? "true" : "false");
});
}
/* ---------- 8. wiring ---------- */
el.play.addEventListener("click", togglePlay);
el.fwd.addEventListener("click", function () { stop(); stepTo(S.step + 1); });
el.back.addEventListener("click", function () { stop(); stepTo(S.step - 1); });
el.reset.addEventListener("click", function () { reset(false); });
el.range.addEventListener("input", function () { stop(); stepTo(+el.range.value); });
el.speed.addEventListener("change", function () {
if (S.playing) { clearTimeout(S.timer); S.timer = setTimeout(tickOnce, +el.speed.value); }
});
el.wa.addEventListener("input", apply);
el.wb.addEventListener("input", apply);
el.swap.addEventListener("click", function () {
var a = el.wa.value; el.wa.value = el.wb.value; el.wb.value = a;
apply(); kickoff();
});
Array.prototype.forEach.call(document.querySelectorAll("button.tiny[data-pair]"), function (b) {
b.addEventListener("click", function () {
var p = b.dataset.pair.split("|");
load(p[0], p[1]);
});
});
/* grid interaction */
el.matrix.addEventListener("click", function (e) {
var c = e.target.closest ? e.target.closest(".cell") : null;
if (!c) return;
stop(); /* inspecting a square pauses the fill */
select(+c.dataset.i, +c.dataset.j);
c.focus();
});
el.matrix.addEventListener("focusin", function (e) {
var c = e.target.closest ? e.target.closest(".cell") : null;
if (!c) return;
select(+c.dataset.i, +c.dataset.j);
});
el.matrix.addEventListener("keydown", function (e) {
var c = e.target.closest ? e.target.closest(".cell") : null;
if (!c) return;
var i = +c.dataset.i, j = +c.dataset.j, moved = true;
if (e.key === "ArrowRight") j = Math.min(S.n, j + 1);
else if (e.key === "ArrowLeft") j = Math.max(0, j - 1);
else if (e.key === "ArrowDown") i = Math.min(S.m, i + 1);
else if (e.key === "ArrowUp") i = Math.max(0, i - 1);
else if (e.key === "Home") { j = 0; }
else if (e.key === "End") { j = S.n; }
else if (e.key === "Escape") { S.sel = null; paint(); return; }
else moved = false;
if (!moved) return;
e.preventDefault();
stop();
select(i, j);
S.cells[i][j].focus();
});
function select(i, j) {
S.sel = [i, j];
paint();
var c = S.cells[i][j];
say(c.getAttribute("aria-label") + ". " + el.say.textContent);
}
/* edit-script rows highlight their square */
el.script.addEventListener("mouseover", hotFromRow);
el.script.addEventListener("focusin", hotFromRow);
el.script.addEventListener("mouseout", clearHot);
el.script.addEventListener("focusout", clearHot);
el.script.addEventListener("click", function (e) {
var r = e.target.closest ? e.target.closest(".row") : null;
if (!r || !S.cells.length) return;
var i = +r.dataset.i, j = +r.dataset.j;
if (S.cells[i] && S.cells[i][j]) { select(i, j); S.cells[i][j].focus(); }
});
function hotFromRow(e) {
var r = e.target.closest ? e.target.closest(".row") : null;
if (!r) return;
clearHot();
r.classList.add("hot");
var col = el.align.querySelector('.acol[data-idx="' + r.dataset.idx + '"]');
if (col) col.classList.add("hot");
var i = +r.dataset.i, j = +r.dataset.j;
if (S.cells[i] && S.cells[i][j]) S.cells[i][j].classList.add("sel");
}
function clearHot() {
Array.prototype.forEach.call(el.script.querySelectorAll(".row.hot"), function (x) { x.classList.remove("hot"); });
Array.prototype.forEach.call(el.align.querySelectorAll(".acol.hot"), function (x) { x.classList.remove("hot"); });
Array.prototype.forEach.call(el.matrix.querySelectorAll(".cell.sel"), function (x) { x.classList.remove("sel"); });
if (S.sel && S.cells[S.sel[0]] && S.cells[S.sel[0]][S.sel[1]]) S.cells[S.sel[0]][S.sel[1]].classList.add("sel");
}
/* global keys */
document.addEventListener("keydown", function (e) {
var t = e.target, tag = t && t.tagName;
var typing = tag === "INPUT" || tag === "SELECT" || tag === "TEXTAREA";
if (e.key === " " || e.key === "Spacebar") {
if (typing || tag === "BUTTON") return;
e.preventDefault(); togglePlay(); return;
}
if (typing || (t && t.closest && t.closest("#matrix"))) return;
if (e.key === "ArrowRight") { e.preventDefault(); stop(); stepTo(S.step + 1); }
else if (e.key === "ArrowLeft") { e.preventDefault(); stop(); stepTo(S.step - 1); }
else if (e.key === "Escape") { S.sel = null; paint(); }
});
/* The wrapper's width can change without a window resize — a scrollbar
appearing, the column layout flipping — so watch the box itself. */
if (window.ResizeObserver) {
/* Resize on the NEXT frame: resizing inside the callback (the grid's own
scrollbar appearing) would otherwise trip the "undelivered
notifications" loop warning. */
var roQueued = 0;
new ResizeObserver(function () {
if (roQueued) return;
roQueued = setTimeout(function () { roQueued = 0; sizeGrid(); }, 0);
}).observe(el.mwrap);
} else {
var rt = 0;
window.addEventListener("resize", function () {
clearTimeout(rt);
rt = setTimeout(function () { sizeGrid(); }, 90);
});
}
/* ---------- go ---------- */
apply();
kickoff();
})();
</script>
</body>
</html>
source-visible by construction · nothing is published here without its code
Comments
0 totalNo comments yet. If you ran it, say what happened.