git diff needs a MINIMAL edit script between two versions of a file -- not just "these lines differ," but the smallest possible set of deletions from a and insertions from b that turns one into the other. This matters in practice: a naive position-by-position comparison turns one inserted line near the top of a file into a wall of spurious changes for every line below it, since everything shifted down by one. Myers' algorithm finds the true shortest edit script in O(ND) time (N = len(a) + len(b), D = the edit distance) and is what Git's xdiff library actually implements.

Model the edit as a path through an (N+1) x (M+1) grid from (0, 0) to (N, M): a move right is "delete a[x]", a move down is "insert b[y]", and a diagonal move -- only available where a[x] == b[y] -- is "keep this line for free" (it doesn't count toward the edit distance). The shortest edit script is the corner-to-corner path using the fewest non-diagonal moves.

The algorithm has two passes:

1. Forward pass. For increasing edit distance d = 0, 1, 2, ..., track the FURTHEST x reachable on every diagonal k = x - y using exactly d non-diagonal moves, snapping forward along any free diagonal moves available from each point. Stop at the first d where some diagonal reaches (N, M) -- that d is the true minimum edit distance. Save the full per-diagonal state at every d (the "trace") for the next pass.
2. Backward pass. Starting from (N, M) at the final d, walk the trace backward, at each step determining which diagonal (k - 1 or k + 1) the point came from and whether that step was an insert or a delete -- reconstructing the edit script in reverse, then reversing it to get forward order.

Implement myers_diff(a, b) returning a list of (op, line) tuples where op is "equal", "delete", or "insert". The pairs with op != "insert", taken in order, must reconstruct a exactly; the pairs with op != "delete", taken in order, must reconstruct b exactly.

Example

myers_diff(["a", "b"], ["a", "b", "c", "d"])
# -> [("equal", "a"), ("equal", "b"), ("insert", "c"), ("insert", "d")]

Constraints

• The returned edit script must be of MINIMAL length -- not just any script that reconstructs both sequences (a script that deletes and reinserts every line would technically "work" but is wrong here).
• Ties in the forward pass (deciding whether to come from diagonal k - 1 or k + 1) follow the standard rule: prefer whichever neighbor has the larger x so far, defaulting to k + 1 when k == -d and to k - 1 when k == d (the boundary diagonals only have one neighbor to come from at all).

Real-world grounding

• Git's actual Myers-diff implementation (the same greedy forward-pass algorithm this exercise implements, in C, operating on line hashes instead of Python strings): xdiff/xdiffi.c

Real xdiff additionally applies heuristics on top of the base algorithm (like "indent heuristic" hunk-boundary shifting, to produce diffs that align with human-meaningful boundaries like blank lines or matching braces) -- this exercise implements the core shortest-edit- script algorithm underneath all of that.