Practice: Comparing Two Versions of a Recipe

Two versions of a recipe share most of their steps; find the steps both keep and the edits between them.

Comparing two versions of a text line by line uses the longest common subsequence and the edit distance with whole lines in place of letters, which is the idea behind a diff tool. This exercise gives you two versions of a recipe and asks which steps survive and how many edits separate them.

The old version has five steps: heat oven; mix flour and sugar; add eggs; add milk; bake 30 minutes. The new version also has five: heat oven; mix flour and sugar; add butter; add eggs; bake 25 minutes. Treat each whole step as one symbol, equal only to an identical step.

Which steps appear in both versions, in the same order, and how many are there at most?
What is the edit distance between the versions, where one edit inserts, deletes or replaces a whole step?
A line-based diff shows a changed line as one deletion and one insertion. How many lines does it mark?

Work out all three answers, then compare.

Three steps: heat oven, mix flour and sugar, add eggs. Add eggs is common to both even though add butter now comes before it, because a subsequence may have gaps. The table has 6 rows and 6 columns, one for each step and one for the empty prefix.
The edit distance is 3. One shortest set of edits is: insert add butter, delete add milk, and replace bake 30 minutes with bake 25 minutes.
Four lines. The diff keeps the three common steps and marks the other two in each version: add milk and bake 30 minutes as deleted, add butter and bake 25 minutes as inserted. With m and n steps and a longest common subsequence of length L, a diff marks (m − L) + (n − L) lines, here 2 + 2. The edit distance is smaller because it lets one replacement stand for a deletion and an insertion together.

The listing below computes both answers with the recurrences from Fill a Longest Common Subsequence Table and Compute the Edit Distance Between Two Words, comparing steps with == exactly as those cards compared letters, and prints the diff.

recipe_code.pypy

old = ["heat oven", "mix flour and sugar", "add eggs", "add milk", "bake 30 minutes"]
new = ["heat oven", "mix flour and sugar", "add butter", "add eggs", "bake 25 minutes"]


def common_steps(a: list[str], b: list[str]) -> list[str]:
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    i, j, kept = len(a), len(b), []
    while i and j:
        if a[i - 1] == b[j - 1]:
            kept.append(a[i - 1])
            i, j = i - 1, j - 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return kept[::-1]


def edit_distance(a: list[str], b: list[str]) -> int:
    dist = [[i + j if i * j == 0 else 0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            same = a[i - 1] == b[j - 1]
            dist[i][j] = dist[i - 1][j - 1] if same else 1 + min(dist[i - 1][j], dist[i][j - 1], dist[i - 1][j - 1])
    return dist[-1][-1]


kept = common_steps(old, new)
print(f"steps kept: {len(kept)}")
for step in kept:
    print(f"  {step}")
print(f"edits between the versions: {edit_distance(old, new)}")
for step in old:
    print(f"{' ' if step in kept else '-'} {step}")
for step in new:
    if step not in kept:
        print(f"+ {step}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

steps kept: 3
  heat oven
  mix flour and sugar
  add eggs
edits between the versions: 3
  heat oven
  mix flour and sugar
  add eggs
- add milk
- bake 30 minutes
+ add butter
+ bake 25 minutes

← → move through sections and cards