Projectsdiff
A command-line tool, like the Unix diff, that compares two text files and prints the lines removed from the first and the lines added in the second. Building it teaches the longest common subsequence and the dynamic programming table behind it, how a diff is derived from it, and why real tools switch to faster algorithms when files get large.
From Coding Challenges #13 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 6 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Steps 1 and 2 ask for the LCS, first of two strings and then of two lists of lines, and every later step is built on it.
Covers: subsequence versus substring · the common part as what didn't change · why the answer is often not unique
Longest common subsequence (Wikipedia) ↗ · diff (Wikipedia) ↗
The table is the standard way to compute the LCS in steps 1 and 2, and step 1 asks you to think about its time and memory cost.
Covers: optimal substructure and overlapping subproblems · the table of prefixes · tracing back to recover the answer · time and memory as the inputs grow
Dynamic programming (Wikipedia) ↗ · Jeff Erickson, Algorithms, chapter 3: Dynamic Programming ↗
Step 3 turns the LCS into the list of removed and added lines, and step 4 prints that list for real files.
Covers: deletions and insertions · the shortest edit script and its link to the LCS · why many valid diffs exist · checking a diff by applying it
Edit distance (Wikipedia) ↗ · The Myers diff algorithm, part 1 (James Coglan) ↗
Step 2 moves from characters to lines, and step 4 reads real files and has to split them into lines.
Covers: choosing the unit, from characters to words to lines · comparing lines by hash · line endings and a missing final newline · white space and what counts as equal
GNU diffutils manual: Suppressing differences in blank and tab spacing ↗ · Newline (Wikipedia) ↗
The page names it as the algorithm behind git's default diff, and it's the main answer to the optional step's question about large files.
Covers: the edit graph · cost that grows with the number of differences · why GNU diff and git use it · patience and histogram, tuned for readability
Eugene W. Myers, An O(ND) Difference Algorithm and Its Variations (1986) ↗ · How different are different diff algorithms in Git? (Nugroho, Hata and Matsumoto) ↗
The optional step asks how your tool copes with very large files and what you would change to make it cope better.
Covers: the full table at scale · trimming the common start and end · recovering the LCS in linear memory · matching only lines that occur in both files · the worst case, and giving up the shortest diff
Hirschberg's algorithm (Wikipedia) ↗ · The Hunt-Szymanski algorithm for LCS (Rolf Fagerberg, University of Southern Denmark) ↗ · GNU diffutils manual: diff performance tradeoffs ↗
What you'll build · 5 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project and download the challenge's sample files, two versions of the same short text.
Works whenBoth sample files open, and you can point to the lines that differ between them.
Find a longest common subsequence of two strings, comparing them character by character. Cover identical strings, strings with nothing in common and empty strings, add edge cases of your own, and think about how the time and memory grow with the length of the strings.
Works whenIdentical strings give the whole string back. Strings with no character in common, or an empty string, give an empty result. Strings that share some characters give those characters in order, and a string whose characters all appear in order inside a longer one comes back whole. Your own edge cases pass too.
Concepts: longest common subsequence · dynamic programming
Extend the same algorithm to two lists of lines, treating each whole line as one item.
Works whenFor two short texts that share some lines, the result is exactly the shared lines in their order. A line that differs by a single character is not shared.
Concepts: longest common subsequence · dynamic programming · lines as the unit of comparison
From two lists of lines, produce the list of changes: each line found only in the original is marked with a < sign, and each line found only in the new version with a > sign. Lines in the LCS are left out.
Works whenOn the sample paragraphs the result has two removed lines and two added lines. The removed lines are exactly the original's lines outside the LCS, and the added lines are exactly the new version's lines outside it.
Concepts: edit scripts · longest common subsequence
A command that takes two file paths, reads both files, splits them into lines and prints the differences. Identical files print nothing.
Works whenRunning it on the two sample files prints the same four lines as step 3, and running it on a file against itself prints nothing.
Concepts: lines as the unit of comparison · edit scripts
Find out how your tool behaves as the files grow, then change it so it handles very large files in reasonable time and memory.
Works whenOn two generated files of many thousands of lines that differ in a few places, the tool finishes quickly without running out of memory, and the lines it reports as removed and added are still exactly the lines that changed.
Concepts: large inputs · myers' algorithm · dynamic programming