FA-75379 / Text diff and three-way merge / Member archive

Myers greedy edit distance: diagonals of the wrong parity are explored · case 04

Diagonals that cannot be reached with d edits are used and the reported distance is too small.

Member previewVariant 4 · 3 implementations · 10 checks per implementation

Case contract

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

Why this case matters

Diff engines use Myers' O(ND) algorithm with a cap on D to bound work on very different files.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
classic example	`3`	`5`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.