Build a diff: the table

Recursion and Dynamic Programming · Open board

Is the board this build leans on. It says dynamic programming is “just recursion that remembers”: answer each small question once, write it down, and build the big answer from answers already written. This lesson writes those answers into a grid for two whole files, turns the grid into a real diff, and then measures how much writing everything down costs.

Before you start. Dynamic Programming, Worked (filling the table) filled a grid for two protein chains: each cell answered “how much do these two beginnings share, in order?”, and the answer for the whole chains waited in the bottom-right cell. Clinic #22 - Longest Common Subsequence solved the same grid as an interview problem, and Git's diff (Myers' algorithm) - the case study, later in this track, tells git’s side; here you build the tool yourself, one file of Python, and watch it run out of room.

The idea in 30 seconds

A diff finds the longest common subsequence of two files: the most lines that appear in both, in the same order. Every other line was removed or added.
The table has one cell per pair of lines, and each cell is filled from the cell up-left (if the two lines match) or the bigger of the cells above and to the left (if not).
Walking back from the bottom-right cell recovers the edit script: keep, remove and add instructions that turn the old file into the new one with the fewest edits.
diff -u prints only the changes, grouped into hunks with three unchanged context lines on each side and an @@ -old +new @@ address.
The table’s memory is quadratic: twice the lines, four times the cells. Measured in Python, 16,000 lines took 2.2 GB, and 50,000 lines would need more than a 16 GB laptop has.

Read the story · Skip to the numbers