Dynamic Programming II: Keystrokes, DNA, and the Notebook in the Trees

Last week ended with a promise. The likeness grid asked "what do these two words share?" — and we said it had a sibling that asks the sharper question: "how many keystrokes turn one word into the other?" That number is called edit distance, it is what your autocorrect computes on every letter you type, and scaled up it is how biologists line up DNA. Then the notebook does something new: it climbs out of flatland entirely, onto trees, where the "smaller version" of a problem isn't a smaller number — it's a smaller branch. Same accountant, two new neighborhoods.

Session planHow we will spend the two sessions

Section 1The promised sibling

You type SATURDAY. Your phone calmly suggests SUNDAY. Somewhere in that half-second, the phone answered a question: how close are these two words, really? Last week we measured closeness one way — the likeness grid found the longest skeleton two words share (SUNDAY and SATURDAY share SUDAY, five letters). Tonight's question is the same coin, flipped: not what the words share, but what it costs to fix the difference.

"Fix" means keystrokes, and we allow exactly three kinds — the three things you can do to a letter on any keyboard:

The edit distance between two words is the fewest moves that turn one into the other. Small number: practically the same word, probably a typo. Big number: genuinely different words. That's the whole definition — no formulas required.

Try one by hand before any machinery. The classic pair is KITTEN and SITTING. Stare for a moment and you can find a three-move repair:

And there's the familiar trap. Three moves is what we found. Is it the fewest? Maybe some devious ordering of deletes and inserts does it in two? Checking every possible repair plan by brute force explodes even faster than the cross-outs did last week. You know this story. You know who to call.

Section 2Same grid, different receipts

The notebook, again — and it's the same grid as last week. One row per letter of the first word, one column per letter of the second, and the cell at row i, column j answers a plain-words question:

The edges of the grid come for free. Turning nothing into SIT costs 3 inserts, so the top row reads 0, 1, 2, 3, … Turning KIT into nothing costs 3 deletes, so the left column counts down the same way. Every other cell follows one rule, and it's take-it-or-don't wearing a new coat. Look at the last letter of each piece:

• The last letters match (…KITT vs …SITT): that letter needs no fixing. It's free — the answer is just the diagonal neighbor, the cell with both letters peeled off.
• They don't match: you must pay one keystroke, and there are exactly three ways to spend it — the three moves. Each one hands you a smaller cell that's already in the notebook. Pay 1, take the cheapest of the three.

Run that rule over the whole KITTEN/SITTING grid — 7 × 8 = 56 tiny cells — and then walk the trail back from the bottom-right corner, exactly like the heist's walk-back (the official name is traceback). Every diagonal step on the trail through matching letters was free; every paid step is one of the keystrokes:

One honest sentence on the sibling rivalry: same grid, different receipts — last week's grid counted the letters you get to keep, this week's counts the keystrokes you have to spend, and that's the entire difference between them.

The code is last week's with the two lines changed that the new receipts demand:

def keystrokes(a, b):
    """grid[i][j] = fewest keystrokes to turn a's first i letters
    into b's first j letters."""
    grid = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1): grid[i][0] = i   # fix i letters into nothing: i deletes
    for j in range(len(b) + 1): grid[0][j] = j   # nothing into j letters: j inserts
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:                  # last letters match:
                grid[i][j] = grid[i - 1][j - 1]      # free — copy the diagonal
            else:                                     # pay 1, cheapest door wins:
                grid[i][j] = 1 + min(grid[i - 1][j - 1],  # replace
                                     grid[i - 1][j],      # delete
                                     grid[i][j - 1])      # insert
    return grid[len(a)][len(b)]

print(keystrokes("KITTEN", "SITTING"))   # 3

Now drive it yourself. Type any two words, watch the fill, then read the keystrokes off the walk-back — the grid doesn't just know the number, it remembers the repair, for free, exactly like the heist remembered which loot to take:

Some things to try:

1. Fill KITTEN → SITTING and check the machine against the figure above — same 56 cells, same trail, same three keystrokes.
2. Run SUNDAY → SATURDAY. Last week these two shared a 5-letter skeleton; this week they're 3 keystrokes apart. Two grids, two views of the same closeness.
3. Press DNA strands and notice that nothing about the machine changes — only your reading of it. That's §4 arriving early.
4. Type a word against itself. Zero keystrokes, one long free diagonal — the notebook shrugging.

Section 3Your phone, every keystroke

So what does autocorrect actually do? Nothing exotic: you type a non-word, and the phone measures the edit distance from your typo to the dictionary words near it, then offers the closest ones. GRAPE is one replace from GRADE, two moves from DRAPES — and the suggestion list is largely that ranking, printed. (One honest footnote: real phones also weigh which keys sit next to each other — hitting R for T is a likelier slip than Q for T — so the moves get prices based on keyboard geography. Weighted receipts, same notebook.)

Section 4The grid puts on a lab coat

Here's the twist that turns a spellchecker into a science instrument. DNA is a string — four letters, A, C, G, T, millions of them in a row. And evolution, it turns out, types with our keyboard: a mutation swaps one letter for another (that's a replace), and letters get dropped or added over generations (deletes and inserts — biologists call the result a gap). So "how related are these two gene sequences?" is literally "what's the edit distance?" — and lining the two strands up against each other, gap dashes and all, is called sequence alignment. It is the walk-back, printed sideways:

Real genomics labs dress the receipts up a little: a biologist's grid gives matches a positive score and charges gaps and mutations different negative prices (some mutations are chemically likelier than others, and one long gap is more plausible than five scattered ones). But read that again and notice what it is — the same grid, different prices on the moves. The method, with scoring, is called Needleman–Wunsch, it dates to 1970, and it runs in essentially every genomics lab on Earth. When you hear that two species' genomes are "96% similar," a scaled-up cousin of the grid you just filled by hand is where the number came from.

Section 5The notebook leaves flatland

Every notebook so far lived on a line or a grid: the "smaller version" was always a smaller number (amounts, pounds) or a shorter prefix (first i letters). Time to cash last week's final promise: the smaller version can be a smaller branch.

Here's the problem, and it's a party. A company is throwing one. Everyone in the company has a fun score — how much better the party is if they come. One ironclad rule: nobody parties next to their own boss. If a person is invited, their direct boss and their direct reports stay home (boss's boss is fine — the awkwardness is strictly one level deep). Your job: pick the guest list with the highest total fun.

The org chart is a tree: one person at the top, everyone else reporting to exactly one boss, no loops — nobody is their own grandboss. And a tree has a gift for us: every person sits on top of a branch — themselves plus everyone under them — and each branch is a complete, self-contained copy of the party problem, just smaller. Take-it-or-don't, one more time, now per person:

Play first. Build your best legal guest list — the machine will squawk if you seat someone next to their boss — then open the notebook:

Some things to try:

1. Greedy instinct says grab Fran (7) and Dev (6) first. Take Dev and watch what it costs you: Hana and Iggy — together worth 9 — are now barred. The best-looking grab poisons its own branch. Where have you heard that before?
2. Try to seat Dev and Iggy together. The edge turns red: Iggy reports to Dev, and the rule is the rule.
3. When you're convinced of your best, press Show the notebook and watch the two numbers appear at the leaves first, then flow upward. Gold pairs: comes · stays.

Here's the walkthrough of what the reveal computes, bottom to top. An intern with no reports is easy: come = own score, stay home = 0. Dev is the first interesting case: if Dev comes, Hana and Iggy stay — 6 + 0 + 0 = 6; if Dev stays, both interns do whatever's best for themselves — 4 + 5 = 9. So Dev's branch is worth 9, without Dev. One level up, Blake: coming is worth 5 + (Dev's branch with Dev home: 9) + (Eli home: 0) = 14; staying is worth (Dev's best: 9) + (Eli's best: 3) = 12. And so on to the top:

The code is almost rude in how short it is — the tree does the bookkeeping for us:

def best_party(person):
    """Two answers about this person's branch:
    (best fun if they come, best fun if they stay home)."""
    comes, stays = person.fun, 0
    for kid in person.reports:
        kid_comes, kid_stays = best_party(kid)
        comes += kid_stays                   # rule: their reports sit it out
        stays += max(kid_comes, kid_stays)   # reports free to choose
    return comes, stays

# best possible party = max(best_party(ceo))  →  24 for our chart

Section 6The recipe box, updated

Last week's recipe card said: reach for the notebook when the problem asks for a best over a pile of choices, when one choice leaves a smaller version of the same problem, and when the distinct smaller questions are few. All three held tonight — twice. The new card is about what "smaller" is allowed to mean:

One sentence of fair warning, because it's next week's whole story: everything the notebook touched tonight shrank cleanly — peel a letter and it's gone, cut a branch and it never reaches back. Next week we walk into structures where that's no longer true: graphs, where connections can loop back around, and "smaller" stops being obvious.

Section 7Before next session