w-31-dp-table-fill.yml · YAML
YAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAML
# DP Table Fill (four-way shared widget)
#
# One spec, four panels. Each panel animates a different DP recurrence on the
# same visual chassis (a row-major grid fill with predecessor arrows and a
# status line). The shared chassis lets the reader carry intuition from one
# chapter to the next:
#
# panel-a (9.0): recursion-with-memo, Fibonacci's call-tree collapse
# (scaffold; owned by 9.0 chapter author)
# panel-b (9.1): iterative tabulation, Fibonacci, bottom-up
# (scaffold; owned by 9.1 chapter author)
# panel-c (9.6): LCS, 2D fill, no replace branch
# (scaffold; owned by 9.6 chapter author)
# panel-d (9.7): Edit distance, 2D fill with three-way recurrence and
# per-cell op labels (insert / delete / replace / match)
#
# Status: scaffold, panel-d (9.7) is keyframe-complete; panels a/b/c are
# stubbed pending their chapter authors.
id: w-31-dp-table-fill
title: "DP table fill"
type: four-way-shared
level: 1
modes: [preset]
caps:
source_length: { min: 0, max: 12 }
target_length: { min: 0, max: 12 }
fib_n: { min: 0, max: 12 }
commands:
- name: initCell
payload: { i: 'integer', j: 'integer', value: 'integer' }
description: "Write a base-case value at (i, j). Used for row 0 and column 0."
- name: compareChars
payload: { i: 'integer', j: 'integer', a: 'string', b: 'string', match: 'boolean' }
description: "Highlight word1[i-1] and word2[j-1]; flash green on match, amber on mismatch."
- name: fillCell
payload:
i: 'integer'
j: 'integer'
op: 'string' # match | replace | delete | insert
predecessor: '[integer, integer]'
value: 'integer'
description: "Animate the chosen predecessor arrow into (i, j); stamp value."
- name: highlightAnswer
payload: { i: 'integer', j: 'integer', value: 'integer' }
description: "Frame dp[m][n] as the final answer."
# Panel-a (9.0) recursion-tree commands. Drive three synchronized
# sub-views from one trace: recursion tree (left), call sequence (middle),
# memo dict (right). Decoupled from the table-fill commands above; panel-a
# renders a tree, not a grid.
- name: enterCall
payload: { k: 'integer', tree_node: 'string', tree_parent: 'string | null' }
description: "Push a recursion-tree node and add it to the call-sequence list (panel-a)."
- name: memoHit
payload: { k: 'integer', tree_node: 'string', value: 'integer' }
description: "Highlight the tree node sky blue, link to the memo node already populated for k, return without recursing (panel-a)."
- name: memoWrite
payload: { k: 'integer', tree_node: 'string', value: 'integer' }
description: "Pop the tree node, mark the corresponding memo entry bluish green, append k:value to the dict view (panel-a)."
static_fallback:
generator: jsdom
output: site/static/widgets/w-31-dp-table-fill-fallback.svg
keyframes_used: [0, 8, 13, 24] # panel-d: init / base done / 'o'='o' match / answer
panels:
panel-a:
chapter: "9.0"
label: "Recursion + memo (Fib)"
canonical_input: |
n = 6
fib(n) = fib(n-1) + fib(n-2); base fib(0) = 0, fib(1) = 1
presets:
- id: fib_6
label: "fib(6) = 8"
input: { n: 6 }
n_steps: 24
expected_answer: 8
keyframes:
- step: 0
kind: init
state:
n: 6
memo: { 0: 0, 1: 1 }
tree: []
call_sequence: []
narration: |
Initial state. Compute fib(6). Memo seeded with the two base cases
F(0) = 0 and F(1) = 1. Tree and call sequence empty.
- step: 1
kind: enterCall
payload: { k: 6, tree_node: "c0", tree_parent: null }
state: { active: "c0", k: 6 }
narration: "Call F(6). Not in memo; recurse on F(5) then F(4)."
- step: 2
kind: enterCall
payload: { k: 5, tree_node: "c1", tree_parent: "c0" }
state: { active: "c1", k: 5 }
narration: "Call F(5). Not in memo; recurse on F(4) then F(3)."
- step: 3
kind: enterCall
payload: { k: 4, tree_node: "c2", tree_parent: "c1" }
state: { active: "c2", k: 4 }
narration: "Call F(4). Not in memo; recurse on F(3) then F(2)."
- step: 4
kind: enterCall
payload: { k: 3, tree_node: "c3", tree_parent: "c2" }
state: { active: "c3", k: 3 }
narration: "Call F(3). Not in memo; recurse on F(2) then F(1)."
- step: 5
kind: enterCall
payload: { k: 2, tree_node: "c4", tree_parent: "c3" }
state: { active: "c4", k: 2 }
narration: "Call F(2). The first call that needs both base cases."
- step: 6
kind: enterCall
payload: { k: 1, tree_node: "c5", tree_parent: "c4" }
state: { active: "c5", k: 1 }
narration: "Call F(1). About to hit the base."
- step: 7
kind: memoHit
payload: { k: 1, tree_node: "c5", value: 1 }
state: { active: "c5", k: 1, value: 1 }
narration: "F(1) is in memo as 1. Return 1; no recursion below."
- step: 8
kind: enterCall
payload: { k: 0, tree_node: "c6", tree_parent: "c4" }
state: { active: "c6", k: 0 }
narration: "Call F(0). About to hit the base."
- step: 9
kind: memoHit
payload: { k: 0, tree_node: "c6", value: 0 }
state: { active: "c6", k: 0, value: 0 }
narration: "F(0) is in memo as 0. Return 0; no recursion below."
- step: 10
kind: memoWrite
payload: { k: 2, tree_node: "c4", value: 1 }
state: { active: "c4", k: 2, value: 1, memo_added: { 2: 1 } }
narration: "F(2) = F(1) + F(0) = 1 + 0 = 1. Write F(2) = 1."
- step: 11
kind: enterCall
payload: { k: 1, tree_node: "c7", tree_parent: "c3" }
state: { active: "c7", k: 1 }
narration: "Call F(1) again, now from F(3)'s right child."
- step: 12
kind: memoHit
payload: { k: 1, tree_node: "c7", value: 1 }
state: { active: "c7", k: 1, value: 1 }
narration: "F(1) hits the memo. Return 1 in O(1); no recursion under this node."
- step: 13
kind: memoWrite
payload: { k: 3, tree_node: "c3", value: 2 }
state: { active: "c3", k: 3, value: 2, memo_added: { 3: 2 } }
narration: "F(3) = F(2) + F(1) = 1 + 1 = 2. Write F(3) = 2."
- step: 14
kind: enterCall
payload: { k: 2, tree_node: "c8", tree_parent: "c2" }
state: { active: "c8", k: 2 }
narration: "Call F(2) again, now from F(4)'s right child. The memo is about to do its job."
- step: 15
kind: memoHit
payload: { k: 2, tree_node: "c8", value: 1 }
state: { active: "c8", k: 2, value: 1 }
narration: |
F(2) hits the memo. Return 1 in O(1). The whole subtree under c8
is skipped. This is the first non-trivial cache save.
- step: 16
kind: memoWrite
payload: { k: 4, tree_node: "c2", value: 3 }
state: { active: "c2", k: 4, value: 3, memo_added: { 4: 3 } }
narration: "F(4) = F(3) + F(2) = 2 + 1 = 3. Write F(4) = 3."
- step: 17
kind: enterCall
payload: { k: 3, tree_node: "c9", tree_parent: "c1" }
state: { active: "c9", k: 3 }
narration: "Call F(3) again, now from F(5)'s right child."
- step: 18
kind: memoHit
payload: { k: 3, tree_node: "c9", value: 2 }
state: { active: "c9", k: 3, value: 2 }
narration: "F(3) hits the memo. Return 2 in O(1). Another whole subtree saved."
- step: 19
kind: memoWrite
payload: { k: 5, tree_node: "c1", value: 5 }
state: { active: "c1", k: 5, value: 5, memo_added: { 5: 5 } }
narration: "F(5) = F(4) + F(3) = 3 + 2 = 5. Write F(5) = 5."
- step: 20
kind: enterCall
payload: { k: 4, tree_node: "c10", tree_parent: "c0" }
state: { active: "c10", k: 4 }
narration: "Call F(4) again, now from F(6)'s right child."
- step: 21
kind: memoHit
payload: { k: 4, tree_node: "c10", value: 3 }
state: { active: "c10", k: 4, value: 3 }
narration: "F(4) hits the memo. Return 3 in O(1). The largest subtree the memo skips."
- step: 22
kind: memoWrite
payload: { k: 6, tree_node: "c0", value: 8 }
state: { active: "c0", k: 6, value: 8, memo_added: { 6: 8 } }
narration: "F(6) = F(5) + F(4) = 5 + 3 = 8. Write F(6) = 8."
- step: 23
kind: highlightAnswer
payload: { i: 6, j: 0, value: 8 }
state:
result: 8
total_calls: 11
memo_hits: 5
memo_writes: 5
narration: |
Done. F(6) = 8. Eleven tree nodes total. Five cache hits saved
five subtrees; five new memo entries (F(2) through F(6)).
notes: |
24-step trace of memoized recursion on F(6). Commands enterCall /
memoHit / memoWrite drive three synchronized sub-views: recursion
tree (left), call sequence (middle), memo dict (right). The
didactic moment is step 15: the first time the cache skips a
non-trivial subtree (F(2) hits from F(4)'s right child). Trace is
deterministic (left-then-right argument evaluation) and verified
byte-for-byte / the §2.2 Python reference;
replays produce identical buffers.
panel-b:
chapter: "9.1"
label: "Iterative tabulation (Fib n=8) with rolling-pair view"
canonical_input: |
n = 8
dp[0] = 0, dp[1] = 1, dp[i] = dp[i-1] + dp[i-2]
dp = [_, _, _, _, _, _, _, _, _] # length n+1 = 9
presets:
- id: fib_8
label: "fib(8) = 21"
input: { n: 8 }
- id: fib_6
label: "fib(6) = 8 (smaller, same recurrence)"
input: { n: 6 }
n_steps: 12
# Trace: initial null array of 9 cells; base cases dp[0]=0 and
# dp[1]=1; sweep dp[2..8] left-to-right with each cell reading the
# two cells immediately to its left. Final dp[8]=21. Static fallback
# frames land on init / base-cases-set / mid-sweep / final.
keyframes:
- step: 0
kind: init
state:
dp: [null, null, null, null, null, null, null, null, null]
phase: "init"
rolling_pair: [null, null]
narration: "Empty dp array of length n+1 = 9. dp[i] will hold fib(i). The two-cell rolling pair below tracks (prev2, prev1): the only state the O(1)-space form actually needs."
- step: 1
kind: initCell
payload: { i: 0, j: 0, value: 0 }
state:
dp: [0, null, null, null, null, null, null, null, null]
phase: "base-case"
current: [0, 0]
rolling_pair: [0, null]
narration: "Base case: dp[0] = 0. fib(0) is defined as 0. prev2 = 0."
- step: 2
kind: initCell
payload: { i: 0, j: 1, value: 1 }
state:
dp: [0, 1, null, null, null, null, null, null, null]
phase: "base-case"
current: [0, 1]
rolling_pair: [0, 1]
narration: "Base case: dp[1] = 1. fib(1) = 1. The rolling pair is now (0, 1): both base cases captured. The for-loop body will sweep i = 2..8."
- step: 3
kind: fillCell
payload: { i: 0, j: 2, op: "sum", predecessor: [0, 1], value: 1 }
state:
dp: [0, 1, 1, null, null, null, null, null, null]
phase: "sweep"
current: [0, 2]
rolling_pair: [1, 1]
narration: "dp[2] = dp[1] + dp[0] = 1 + 0 = 1. The two predecessors sit immediately to the left of the write cell: pure 'read the two recent cells, write one' shape. Rolling pair shifts: (1, 1)."
- step: 4
kind: fillCell
payload: { i: 0, j: 3, op: "sum", predecessor: [0, 2], value: 2 }
state:
dp: [0, 1, 1, 2, null, null, null, null, null]
phase: "sweep"
current: [0, 3]
rolling_pair: [1, 2]
narration: "dp[3] = dp[2] + dp[1] = 1 + 1 = 2. Rolling pair: (1, 2)."
- step: 5
kind: fillCell
payload: { i: 0, j: 4, op: "sum", predecessor: [0, 3], value: 3 }
state:
dp: [0, 1, 1, 2, 3, null, null, null, null]
phase: "sweep"
current: [0, 4]
rolling_pair: [2, 3]
dead_cells: [0]
narration: "dp[4] = dp[3] + dp[2] = 2 + 1 = 3. Notice: dp[0] will never be read again. The full array stores it; the rolling pair has already dropped it. That cell behind the read frontier is dead memory."
- step: 6
kind: fillCell
payload: { i: 0, j: 5, op: "sum", predecessor: [0, 4], value: 5 }
state:
dp: [0, 1, 1, 2, 3, 5, null, null, null]
phase: "sweep"
current: [0, 5]
rolling_pair: [3, 5]
dead_cells: [0, 1]
narration: "dp[5] = dp[4] + dp[3] = 3 + 2 = 5. Two dead cells now (dp[0], dp[1])."
- step: 7
kind: fillCell
payload: { i: 0, j: 6, op: "sum", predecessor: [0, 5], value: 8 }
state:
dp: [0, 1, 1, 2, 3, 5, 8, null, null]
phase: "sweep"
current: [0, 6]
rolling_pair: [5, 8]
dead_cells: [0, 1, 2]
narration: "dp[6] = dp[5] + dp[4] = 5 + 3 = 8."
- step: 8
kind: fillCell
payload: { i: 0, j: 7, op: "sum", predecessor: [0, 6], value: 13 }
state:
dp: [0, 1, 1, 2, 3, 5, 8, 13, null]
phase: "sweep"
current: [0, 7]
rolling_pair: [8, 13]
dead_cells: [0, 1, 2, 3]
narration: "dp[7] = dp[6] + dp[5] = 8 + 5 = 13."
- step: 9
kind: fillCell
payload: { i: 0, j: 8, op: "sum", predecessor: [0, 7], value: 21 }
state:
dp: [0, 1, 1, 2, 3, 5, 8, 13, 21]
phase: "sweep"
current: [0, 8]
rolling_pair: [13, 21]
dead_cells: [0, 1, 2, 3, 4]
narration: "dp[8] = dp[7] + dp[6] = 13 + 8 = 21. Loop done. By the time we wrote dp[8], cells dp[0..4] had been dead for several iterations: five cells of memory the O(n)-space form keeps for nothing, and the O(1)-space form drops."
- step: 10
kind: highlightAnswer
payload: { i: 0, j: 8, value: 21 }
state:
dp: [0, 1, 1, 2, 3, 5, 8, 13, 21]
phase: "answer"
current: [0, 8]
rolling_pair: [13, 21]
result: 21
narration: "Answer: dp[8] = 21 = fib(8). O(n) time, O(n) space for the array form."
- step: 11
kind: highlightAnswer
payload: { i: 0, j: 8, value: 21 }
state:
dp: [0, 1, 1, 2, 3, 5, 8, 13, 21]
phase: "compress"
rolling_pair: [13, 21]
result: 21
narration: "Same answer from the rolling pair: prev1 = 21. The two scalars carried the complete state needed for every dp[i+1] write. O(n) time stays; space drops from O(n) to O(1). That space cut is the chapter."
panel-c:
chapter: "9.6"
label: "LCS 2D table fill (LC 1143 ABCBDAB / BDCAB)"
canonical_input: |
text1 = "ABCBDAB"
text2 = "BDCAB"
LCS length = 4 (e.g. "BCAB")
presets:
- id: abcbdab_bdcab
label: "LCS('ABCBDAB', 'BDCAB') = 4 (CLRS Figure 14.8)"
input: { text1: "ABCBDAB", text2: "BDCAB" }
- id: abcde_ace
label: "LCS('abcde', 'ace') = 3 (LC 1143 example)"
input: { text1: "abcde", text2: "ace" }
n_steps: 12
# Trace transcribed from the chapter prose at lines 116-126 plus
# CLRS Figure 14.8. Compressed: one frame per row completion plus
# the corner-cell match plus answer. The cell-by-cell fill is
# implicit between snapshots; the row-snapshot frames carry the
# full state.dp 2D so the renderer paints the entire row at once.
keyframes:
- step: 0
kind: init
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
phase: "init"
narration: "Initial 8 x 6 grid. Row 0 (empty text1 prefix) and column 0 (empty text2 prefix) are all 0: LCS with an empty string is 0. Row labels: 0, A, B, C, B, D, A, B (the 7 chars of text1 plus the 0-row). Column labels: 0, B, D, C, A, B."
- step: 1
kind: fillCell
payload: { i: 1, j: 4, op: "match", predecessor: [0, 3], value: 1 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
phase: "row-1"
current: [1, 4]
narration: "Row 1 done. text1[0]='A' compared against text2. Match at j=4 ('A'='A'): dp[1][4] = dp[0][3] + 1 = 1. Mismatches inherit max-of-neighbors. dp[1] = [0, 0, 0, 0, 1, 1]."
- step: 2
kind: fillCell
payload: { i: 2, j: 5, op: "match", predecessor: [1, 4], value: 2 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
phase: "row-2"
current: [2, 5]
narration: "Row 2 done. text1[1]='B'. Two matches: dp[2][1] = 1 ('B'='B' first time) and dp[2][5] = dp[1][4] + 1 = 2 ('B'='B' again, consuming the diagonal we just wrote in row 1). The algorithm has found 'AB' as a length-2 LCS of the two prefixes 'AB' and 'BDCAB'."
- step: 3
kind: fillCell
payload: { i: 3, j: 3, op: "match", predecessor: [2, 2], value: 2 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
phase: "row-3"
current: [3, 3]
narration: "Row 3 done. text1[2]='C'. One match: dp[3][3] = dp[2][2] + 1 = 1 + 1 = 2. The diagonal predecessor was 1 ('B' against 'BD'), so we have 'BC' against 'BDC' with LCS length 2."
- step: 4
kind: fillCell
payload: { i: 4, j: 5, op: "match", predecessor: [3, 4], value: 3 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
phase: "row-4"
current: [4, 5]
narration: "Row 4 done. text1[3]='B' (the second 'B'). Matches at dp[4][1] = 1 and dp[4][5] = dp[3][4] + 1 = 2 + 1 = 3. The table is now finding length-3 subsequences: 'ABCB' against 'BDCAB' has LCS 'BCB' or 'BAB', length 3."
- step: 5
kind: fillCell
payload: { i: 5, j: 2, op: "match", predecessor: [4, 1], value: 2 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 0, 0]
phase: "row-5"
current: [5, 2]
narration: "Row 5 done. text1[4]='D'. Match at dp[5][2] = dp[4][1] + 1 = 1 + 1 = 2. dp[5][5] = 3 inherits up from dp[4][5] (the up wins on ties)."
- step: 6
kind: fillCell
payload: { i: 6, j: 4, op: "match", predecessor: [5, 3], value: 3 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 1, 2, 2, 3, 3]
- [0, 0, 0, 0, 0, 0]
phase: "row-6"
current: [6, 4]
narration: "Row 6 done. text1[5]='A'. Match at dp[6][4] = dp[5][3] + 1 = 2 + 1 = 3. Building 'BCA' from a length-2 prefix at dp[5][3]."
- step: 7
kind: fillCell
payload: { i: 7, j: 1, op: "match", predecessor: [6, 0], value: 1 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 1, 2, 2, 3, 3]
- [0, 1, 2, 2, 3, 3]
phase: "row-7-partial"
current: [7, 1]
narration: "Row 7 in progress. text1[6]='B'. Match at dp[7][1] = 1 ('B'='B'). Cells dp[7][2..4] all inherit from up-or-left: 2, 2, 3. The corner is one cell away."
- step: 8
kind: fillCell
payload: { i: 7, j: 5, op: "match", predecessor: [6, 4], value: 4 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 1, 2, 2, 3, 3]
- [0, 1, 2, 2, 3, 4]
phase: "row-7-corner"
current: [7, 5]
narration: "The dramatic moment. text1[6]='B', text2[4]='B'. Match. dp[7][5] = dp[6][4] + 1 = 3 + 1 = 4. The corner holds the answer."
- step: 9
kind: highlightAnswer
payload: { i: 7, j: 5, value: 4 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 1, 2, 2, 3, 3]
- [0, 1, 2, 2, 3, 4]
phase: "answer"
current: [7, 5]
result: 4
narration: "Answer: LCS length = dp[7][5] = 4. 35 interior cell writes; each cell touched three already-computed neighbors; no cell revisited. O(m * n) time, O(m * n) space: the textbook canonical form."
- step: 10
kind: highlightAnswer
payload: { i: 7, j: 5, value: 4 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 1, 2, 2, 3, 3]
- [0, 1, 2, 2, 3, 4]
phase: "backtrack"
backtrack_path: [[7, 5], [6, 4], [5, 3], [4, 3], [3, 2], [2, 2], [1, 1], [0, 1]]
result: 4
narration: "Reconstruction pass: walk from corner (7,5) to (0,0). Match at (7,5): take diagonal to (6,4). Match at (6,4): diagonal to (5,3). Mismatch at (5,3) with up dp[4][3]=2 >= left dp[5][2]=2: up. Match at (4,3): diagonal to (3,2). And so on. Four matches collected: B, A, C, B."
- step: 11
kind: highlightAnswer
payload: { i: 7, j: 5, value: 4 }
state:
dp:
- [0, 0, 0, 0, 0, 0]
- [0, 0, 0, 0, 1, 1]
- [0, 1, 1, 1, 1, 2]
- [0, 1, 1, 2, 2, 2]
- [0, 1, 1, 2, 2, 3]
- [0, 1, 2, 2, 2, 3]
- [0, 1, 2, 2, 3, 3]
- [0, 1, 2, 2, 3, 4]
phase: "done"
result: 4
recovered: "BCAB"
narration: "Reverse the collected characters: 'BCAB'. CLRS Figure 14.8 displays exactly this 8 x 6 table with the same recovered string. Strict-> tie-break would have given 'BDAB' instead: both are valid LCSs of length 4."
panel-d:
chapter: "9.7"
label: "Edit distance"
canonical_input: |
word1 = "horse"
word2 = "ros"
edit distance = 3
presets:
- id: horse_ros
label: "horse -> ros = 3"
input: { word1: "horse", word2: "ros" }
- id: intention_execution
label: "intention -> execution = 5"
input: { word1: "intention", word2: "execution" }
- id: kitten_sitting
label: "kitten -> sitting = 3"
input: { word1: "kitten", word2: "sitting" }
n_steps: 25
keyframes:
- step: 0
kind: init
state: { grid_dims: [6, 4], cell: [0, 0], value: 0 }
narration: "dp[0][0] = 0. Empty word1 to empty word2 needs 0 operations."
- step: 1
kind: initCell
payload: { i: 0, j: 1, value: 1 }
state: { phase: "base-row", current: [0, 1] }
narration: "dp[0][1] = 1. One insert turns '' into 'r'."
- step: 2
kind: initCell
payload: { i: 0, j: 2, value: 2 }
state: { phase: "base-row", current: [0, 2] }
narration: "dp[0][2] = 2. Two inserts turn '' into 'ro'."
- step: 3
kind: initCell
payload: { i: 0, j: 3, value: 3 }
state: { phase: "base-row", current: [0, 3] }
narration: "dp[0][3] = 3. Three inserts turn '' into 'ros'."
- step: 4
kind: initCell
payload: { i: 1, j: 0, value: 1 }
state: { phase: "base-col", current: [1, 0] }
narration: "dp[1][0] = 1. One delete turns 'h' into ''."
- step: 5
kind: initCell
payload: { i: 2, j: 0, value: 2 }
state: { phase: "base-col", current: [2, 0] }
narration: "dp[2][0] = 2. Two deletes turn 'ho' into ''."
- step: 6
kind: initCell
payload: { i: 3, j: 0, value: 3 }
state: { phase: "base-col", current: [3, 0] }
narration: "dp[3][0] = 3. Three deletes turn 'hor' into ''."
- step: 7
kind: initCell
payload: { i: 4, j: 0, value: 4 }
state: { phase: "base-col", current: [4, 0] }
narration: "dp[4][0] = 4. Four deletes turn 'hors' into ''."
- step: 8
kind: initCell
payload: { i: 5, j: 0, value: 5 }
state: { phase: "base-col", current: [5, 0] }
narration: "dp[5][0] = 5. Five deletes turn 'horse' into ''."
- step: 9
kind: fillCell
payload: { i: 1, j: 1, op: replace, predecessor: [0, 0], value: 1 }
state: { compare: ["h", "r"], match: false, mins: { diag: 0, top: 1, left: 1 } }
narration: "'h' != 'r'. Cheapest predecessor is dp[0][0] = 0 (replace). dp[1][1] = 1 + 0 = 1."
- step: 10
kind: fillCell
payload: { i: 1, j: 2, op: replace, predecessor: [1, 1], value: 2 }
state: { compare: ["h", "o"], match: false, mins: { diag: 1, top: 2, left: 1 } }
narration: "'h' != 'o'. Tie between diag and left at value 1; replace wins by tie-break. dp[1][2] = 2."
- step: 11
kind: fillCell
payload: { i: 1, j: 3, op: replace, predecessor: [1, 2], value: 3 }
state: { compare: ["h", "s"], match: false, mins: { diag: 2, top: 3, left: 2 } }
narration: "'h' != 's'. dp[1][3] = 1 + min(2, 3, 2) = 3."
- step: 12
kind: fillCell
payload: { i: 2, j: 1, op: replace, predecessor: [1, 0], value: 2 }
state: { compare: ["o", "r"], match: false, mins: { diag: 1, top: 1, left: 2 } }
narration: "'o' != 'r'. dp[2][1] = 1 + min(1, 1, 2) = 2."
- step: 13
kind: fillCell
payload: { i: 2, j: 2, op: match, predecessor: [1, 1], value: 1 }
state: { compare: ["o", "o"], match: true }
narration: "'o' == 'o'. Free diagonal: dp[2][2] = dp[1][1] = 1. No operation."
- step: 14
kind: fillCell
payload: { i: 2, j: 3, op: insert, predecessor: [2, 2], value: 2 }
state: { compare: ["o", "s"], match: false, mins: { diag: 2, top: 3, left: 1 } }
narration: "'o' != 's'. Cheapest predecessor is dp[2][2] = 1 (insert). dp[2][3] = 2."
- step: 15
kind: fillCell
payload: { i: 3, j: 1, op: match, predecessor: [2, 0], value: 2 }
state: { compare: ["r", "r"], match: true }
narration: "'r' == 'r'. Free diagonal: dp[3][1] = dp[2][0] = 2."
- step: 16
kind: fillCell
payload: { i: 3, j: 2, op: replace, predecessor: [2, 1], value: 2 }
state: { compare: ["r", "o"], match: false, mins: { diag: 1, top: 2, left: 2 } }
narration: "'r' != 'o'. dp[3][2] = 1 + min(1, 2, 2) = 2."
- step: 17
kind: fillCell
payload: { i: 3, j: 3, op: replace, predecessor: [2, 2], value: 2 }
state: { compare: ["r", "s"], match: false, mins: { diag: 1, top: 2, left: 2 } }
narration: "'r' != 's'. dp[3][3] = 1 + min(1, 2, 2) = 2."
- step: 18
kind: fillCell
payload: { i: 4, j: 1, op: replace, predecessor: [3, 0], value: 3 }
state: { compare: ["s", "r"], match: false, mins: { diag: 2, top: 2, left: 3 } }
narration: "'s' != 'r'. dp[4][1] = 1 + min(2, 2, 3) = 3."
- step: 19
kind: fillCell
payload: { i: 4, j: 2, op: replace, predecessor: [3, 1], value: 3 }
state: { compare: ["s", "o"], match: false, mins: { diag: 2, top: 2, left: 3 } }
narration: "'s' != 'o'. dp[4][2] = 1 + min(2, 2, 3) = 3."
- step: 20
kind: fillCell
payload: { i: 4, j: 3, op: match, predecessor: [3, 2], value: 2 }
state: { compare: ["s", "s"], match: true }
narration: "'s' == 's'. Free diagonal: dp[4][3] = dp[3][2] = 2."
- step: 21
kind: fillCell
payload: { i: 5, j: 1, op: replace, predecessor: [4, 0], value: 4 }
state: { compare: ["e", "r"], match: false, mins: { diag: 3, top: 3, left: 4 } }
narration: "'e' != 'r'. dp[5][1] = 1 + min(3, 3, 4) = 4."
- step: 22
kind: fillCell
payload: { i: 5, j: 2, op: replace, predecessor: [4, 1], value: 4 }
state: { compare: ["e", "o"], match: false, mins: { diag: 3, top: 3, left: 4 } }
narration: "'e' != 'o'. dp[5][2] = 1 + min(3, 3, 4) = 4."
- step: 23
kind: fillCell
payload: { i: 5, j: 3, op: delete, predecessor: [4, 3], value: 3 }
state: { compare: ["e", "s"], match: false, mins: { diag: 3, top: 2, left: 4 } }
narration: "'e' != 's'. Cheapest predecessor is dp[4][3] = 2 (delete the trailing 'e'). dp[5][3] = 3."
- step: 24
kind: highlightAnswer
payload: { i: 5, j: 3, value: 3 }
state: { phase: "answer", current: [5, 3] }
narration: |
Answer = dp[5][3] = 3. Edit distance from 'horse' to 'ros' is 3:
one replace ('h' -> 'r'), one delete ('e' at the end), and one
delete in the middle (the 'r' or the 'e' depending on tie-break).
The cost is unique; the alignment is not.
selector_default: panel-d
notes: |
Color palette (Wong, per style-guide.md):
match = #009E73 (bluish green)
replace = #E69F00 (orange)
delete = #D55E00 (vermilion)
insert = #56B4E9 (sky blue)
current = #CC79A7 (reddish purple, outline)
Tie-break order for predecessor selection (so the renderer's arrow is
deterministic): diag (replace) > top (delete) > left (insert). Matches
the evaluation order of `min({diag, top, left})` in the §2 reference
implementations across all four languages.
Trace for panel-d generated by instrumenting the verified Python
reference at part-9-dynamic-programming/07-edit-distance/lc-72/sol.py
to emit one record per cell write. Reproducible: re-running yields a
byte-identical 25-step buffer.
Reduced-motion fallback uses keyframes [0, 8, 13, 24]:
init / base row+col complete / first 'o'='o' match / answer.
Panels a/b/c are scaffolded (n_steps: 0, keyframes: []) pending their
chapter authors. Status flips from `scaffold` to `complete` once all
four panels carry full keyframe traces.From The Engineering Handbook (source), CC BY-SA 4.0.