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

Myers greedy edit distance: the furthest-reaching predecessor comparison is inverted · case 02

Reported distances are larger than the true minimum.

Member previewVariant 2 · 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	`7`	`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.