broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(target, hunks, max_offset):
    lines = list(target)
    delta = 0
    applied, rejected = [], []
    for h_i, (old_start, old, new) in enumerate(hunks):
        expect = old_start - 1 + delta
        found = None
        for dist in range(0, max_offset + 1):
            for pos in ((expect - dist, expect + dist) if dist else (expect,)):
                if 0 <= pos and pos + len(old) <= len(lines) and lines[pos:pos + len(old)] == old:
                    found = pos
                    break
            if found is not None:
                break
        if found is None:
            rejected.append(h_i)
            continue
        lines[found:found + len(new)] = new
        applied.append(found + 1)
        delta += (found - expect) + len(new) - len(old)
    return {'lines': lines, 'applied': applied, 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 2], {'lines': ['pre0', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 0], {'lines': ['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 1], {'lines': ['pre0', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [3, 11], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L81']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L81', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    2: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 3], {'lines': ['pre0', 'pre1', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 1], {'lines': ['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 2], {'lines': ['pre0', 'pre1', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [4, 12], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L82']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L82', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    3: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 4], {'lines': ['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [6], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 2], {'lines': ['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 3], {'lines': ['pre0', 'pre1', 'pre2', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L83']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L83', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    4: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 5], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [7], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 3], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 4], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [6, 14], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L84']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L84', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    5: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 6], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [8], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 4], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 5], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [7, 15], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L85']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L85', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(target, hunks, max_offset):
    lines = list(target)
    delta = 0
    applied, rejected = [], []
    for h_i, (old_start, old, new) in enumerate(hunks):
        expect = old_start - 1 + delta
        found = None
        for dist in range(0, max_offset + 1):
            for pos in ((expect - dist, expect + dist) if dist else (expect,)):
                if 0 <= pos and pos + len(old) <= len(lines) and lines[pos:pos + len(old)] == old:
                    found = pos
                    break
            if found is not None:
                break
        if found is None:
            rejected.append(h_i)
            continue
        lines[found:found + max(len(old), len(new))] = new
        applied.append(found + 1)
        delta += (found - expect) + len(new) - len(old)
    return {'lines': lines, 'applied': applied, 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 2], {'lines': ['pre0', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 0], {'lines': ['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 1], {'lines': ['pre0', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [3, 11], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L81']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L81', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    2: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 3], {'lines': ['pre0', 'pre1', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 1], {'lines': ['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 2], {'lines': ['pre0', 'pre1', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [4, 12], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L82']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L82', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    3: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 4], {'lines': ['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [6], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 2], {'lines': ['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'pre2', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 3], {'lines': ['pre0', 'pre1', 'pre2', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L83']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L83', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    4: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 5], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [7], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 3], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 4], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [6, 14], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L84']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L84', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
    5: [('clean apply at the expected line', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X', 'l4']]], 3], {'lines': ['l1', 'l2', 'l3', 'X', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [3], 'rejected': []}), ('offset because lines were added above', [['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 6], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'X', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [8], 'rejected': []}), ('offset beyond the limit is rejected', [['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[3, ['l3', 'l4'], ['l3', 'X']]], 4], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [], 'rejected': [0]}), ("second hunk follows the first hunk's offset", [['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['l2', 'A', 'B']], [8, ['l8', 'l9'], ['Z']]], 5], {'lines': ['pre0', 'pre1', 'pre2', 'pre3', 'pre4', 'l1', 'l2', 'A', 'B', 'l3', 'l4', 'l5', 'l6', 'l7', 'Z', 'l10', 'l11', 'l12'], 'applied': [7, 15], 'rejected': []}), ('equal distances prefer the earlier match', [['a', 'k', 'b', 'k', 'c'], [[3, ['k'], ['K']]], 1], {'lines': ['a', 'K', 'b', 'k', 'c'], 'applied': [2], 'rejected': []}), ('rejected hunk does not shift later hunks', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['nope'], ['x', 'y', 'z']], [5, ['l5'], ['F', 'l5']]], 1], {'lines': ['l1', 'l2', 'l3', 'l4', 'F', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [5], 'rejected': [0]}), ('rejected hunk keeps earlier shifts', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['l1', 'a', 'b']], [3, ['nope'], ['x']], [5, ['l5'], ['F']]], 1], {'lines': ['l1', 'a', 'b', 'l2', 'l3', 'l4', 'F', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [1, 7], 'rejected': [1]}), ('carried offset keeps a far hunk in range', [['pre', 'pre', 'pre', 'l1', 'l2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[2, ['l2'], ['L2']], [8, ['l8'], ['L85']]], 3], {'lines': ['pre', 'pre', 'pre', 'l1', 'L2', 'l3', 'l4', 'l5', 'ins1', 'ins2', 'l6', 'l7', 'L85', 'l9', 'l10', 'l11', 'l12'], 'applied': [5, 13], 'rejected': []}), ('two hunks with size changes', [['l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1', 'l2'], ['l1']], [6, ['l6'], ['l6', 'm', 'm2']], [10, ['l10'], ['T']]], 0], {'lines': ['l1', 'l3', 'l4', 'l5', 'l6', 'm', 'm2', 'l7', 'l8', 'l9', 'T', 'l11', 'l12'], 'applied': [1, 5, 11], 'rejected': []}), ('only a later occurrence matches', [['q', 'r', 's', 'x', 'y', 'x', 'y'], [[4, ['x', 'z'], ['w']], [1, ['r'], ['R']]], 2], {'lines': ['q', 'R', 's', 'x', 'y', 'x', 'y'], 'applied': [2], 'rejected': [0]}), ('match exactly at the offset limit', [['p', 'p', 'z', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], [[1, ['l1'], ['L1']]], 3], {'lines': ['p', 'p', 'z', 'L1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9', 'l10', 'l11', 'l12'], 'applied': [4], 'rejected': []})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Applying a hunk that grows or shrinks the text swallows or duplicates neighbouring lines.

Hunks [old_start, old_lines, new_lines] are applied in order. The expected index is old_start-1 plus the accumulated shift. The search tries distance 0, then 1, 2, ... up to max_offset, at each distance the earlier position before the later one; the first position where old_lines match replaces them with new_lines. After an applied hunk the shift grows by (found-expected) + len(new)-len(old); a hunk that does not match is rejected and changes nothing. Return lines, 1-based applied positions and rejected hunk indices.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import difflib
N = 1
observations = []
def solve(base, ours, theirs):
    def matches(x):
        sm = difflib.SequenceMatcher(None, base, x, autojunk=False)
        mp = {}
        for i, j, size in sm.get_matching_blocks():
            for t in range(size):
                mp[i + t] = j + t
        return mp
    mo, mt = matches(ours), matches(theirs)
    out = []
    conflicts = 0
    i = j = k = 0
    anchors = [bi for bi in range(len(base)) if bi in mo and bi in mt] + [None]
    for bi in anchors:
        if bi is None:
            i1, j1, k1 = len(base), len(ours), len(theirs)
        else:
            i1, j1, k1 = bi, mo[bi], mt[bi]
        B, O, T = base[i:i1], ours[j:j1], theirs[k:k1]
        if O == B:
            out.extend(O)
        elif T == B:
            out.extend(O)
        elif O == T:
            out.extend(O)
        else:
            conflicts += 1
            out.append('<<<<<<< ours')
            out.extend(O)
            out.append('||||||| base')
            out.extend(B)
            out.append('=======')
            out.extend(T)
            out.append('>>>>>>> theirs')
        if bi is not None:
            out.append(base[bi])
            i, j, k = i1 + 1, j1 + 1, k1 + 1
    return {'merged': out, 'conflicts': conflicts}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e']], {'merged': ['a', 'b', 'C1', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    2: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e']], {'merged': ['a', 'b', 'C2', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    3: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e']], {'merged': ['a', 'b', 'C3', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    4: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e']], {'merged': ['a', 'b', 'C4', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    5: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e']], {'merged': ['a', 'b', 'C5', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3', 'o4'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', 'o4', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import difflib
N = 1
observations = []
def solve(base, ours, theirs):
    def matches(x):
        sm = difflib.SequenceMatcher(None, base, x, autojunk=False)
        mp = {}
        for i, j, size in sm.get_matching_blocks():
            for t in range(size):
                mp[i + t] = j + t
        return mp
    mo, mt = matches(ours), matches(theirs)
    out = []
    conflicts = 0
    i = j = k = 0
    anchors = [bi for bi in range(len(base)) if bi in mo and bi in mt] + [None]
    for bi in anchors:
        if bi is None:
            i1, j1, k1 = len(base), len(ours), len(theirs)
        else:
            i1, j1, k1 = bi, mo[bi], mt[bi]
        B, O, T = base[i:i1], ours[j:j1], theirs[k:k1]
        if O == B:
            out.extend(T if T else O)
        elif T == B:
            out.extend(O)
        elif O == T:
            out.extend(O)
        else:
            conflicts += 1
            out.append('<<<<<<< ours')
            out.extend(O)
            out.append('||||||| base')
            out.extend(B)
            out.append('=======')
            out.extend(T)
            out.append('>>>>>>> theirs')
        if bi is not None:
            out.append(base[bi])
            i, j, k = i1 + 1, j1 + 1, k1 + 1
    return {'merged': out, 'conflicts': conflicts}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e']], {'merged': ['a', 'b', 'C1', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    2: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e']], {'merged': ['a', 'b', 'C2', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    3: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e']], {'merged': ['a', 'b', 'C3', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    4: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e']], {'merged': ['a', 'b', 'C4', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    5: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e']], {'merged': ['a', 'b', 'C5', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3', 'o4'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', 'o4', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Edits from the other branch silently vanish when our side left the region untouched.

Match base against ours and against theirs with difflib.SequenceMatcher (autojunk off). Base lines matched on both sides are stable anchors. Between consecutive anchors (and after the last) compare the three regions: unchanged ours takes theirs, unchanged theirs takes ours, identical changes take ours, anything else is a conflict rendered as "<<<<<<< ours", ours, "||||||| base", base, "=======", theirs, ">>>>>>> theirs". Return merged lines and the conflict count.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import difflib
N = 1
observations = []
def solve(base, ours, theirs):
    def matches(x):
        sm = difflib.SequenceMatcher(None, base, x, autojunk=False)
        mp = {}
        for i, j, size in sm.get_matching_blocks():
            for t in range(size):
                mp[i + t] = j + t
        return mp
    mo, mt = matches(ours), matches(theirs)
    out = []
    conflicts = 0
    i = j = k = 0
    anchors = [bi for bi in range(len(base)) if bi in mo and bi in mt] + [None]
    for bi in anchors:
        if bi is None:
            i1, j1, k1 = len(base), len(ours), len(theirs)
        else:
            i1, j1, k1 = bi, mo[bi], mt[bi]
        B, O, T = base[i:i1], ours[j:j1], theirs[k:k1]
        if O == B:
            out.extend(T)
        elif T == B:
            out.extend(O)
        else:
            conflicts += 1
            out.append('<<<<<<< ours')
            out.extend(O)
            out.append('||||||| base')
            out.extend(B)
            out.append('=======')
            out.extend(T)
            out.append('>>>>>>> theirs')
        if bi is not None:
            out.append(base[bi])
            i, j, k = i1 + 1, j1 + 1, k1 + 1
    return {'merged': out, 'conflicts': conflicts}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e']], {'merged': ['a', 'b', 'C1', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    2: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e']], {'merged': ['a', 'b', 'C2', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    3: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e']], {'merged': ['a', 'b', 'C3', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    4: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e']], {'merged': ['a', 'b', 'C4', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    5: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e']], {'merged': ['a', 'b', 'C5', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3', 'o4'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', 'o4', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import difflib
N = 1
observations = []
def solve(base, ours, theirs):
    def matches(x):
        sm = difflib.SequenceMatcher(None, base, x, autojunk=False)
        mp = {}
        for i, j, size in sm.get_matching_blocks():
            for t in range(size):
                mp[i + t] = j + t
        return mp
    mo, mt = matches(ours), matches(theirs)
    out = []
    conflicts = 0
    i = j = k = 0
    anchors = [bi for bi in range(len(base)) if bi in mo and bi in mt] + [None]
    for bi in anchors:
        if bi is None:
            i1, j1, k1 = len(base), len(ours), len(theirs)
        else:
            i1, j1, k1 = bi, mo[bi], mt[bi]
        B, O, T = base[i:i1], ours[j:j1], theirs[k:k1]
        if O == B:
            out.extend(T)
        elif T == B:
            out.extend(O)
        elif O == T and O:
            out.extend(O)
        else:
            conflicts += 1
            out.append('<<<<<<< ours')
            out.extend(O)
            out.append('||||||| base')
            out.extend(B)
            out.append('=======')
            out.extend(T)
            out.append('>>>>>>> theirs')
        if bi is not None:
            out.append(base[bi])
            i, j, k = i1 + 1, j1 + 1, k1 + 1
    return {'merged': out, 'conflicts': conflicts}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e'], ['a', 'b', 'C1', 'd', 'e']], {'merged': ['a', 'b', 'C1', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    2: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e'], ['a', 'b', 'C2', 'd', 'e']], {'merged': ['a', 'b', 'C2', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    3: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e'], ['a', 'b', 'C3', 'd', 'e']], {'merged': ['a', 'b', 'C3', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    4: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e'], ['a', 'b', 'C4', 'd', 'e']], {'merged': ['a', 'b', 'C4', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
    5: [('only ours changed', [['a', 'b', 'c', 'd', 'e'], ['a', 'B', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']], {'merged': ['a', 'B', 'c', 'd', 'e'], 'conflicts': 0}), ('only theirs deleted a line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'd', 'e']], {'merged': ['a', 'b', 'd', 'e'], 'conflicts': 0}), ('both made the same change', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e'], ['a', 'b', 'C5', 'd', 'e']], {'merged': ['a', 'b', 'C5', 'd', 'e'], 'conflicts': 0}), ('both deleted the same line', [['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'd', 'e']], {'merged': ['a', 'c', 'd', 'e'], 'conflicts': 0}), ('conflicting edits', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'X', 'd', 'e'], ['a', 'b', 'Y', 'd', 'e']], {'merged': ['a', 'b', '<<<<<<< ours', 'X', '||||||| base', 'c', '=======', 'Y', '>>>>>>> theirs', 'd', 'e'], 'conflicts': 1}), ('changes after the last stable line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 'o0', 'o1', 'o2', 'o3', 'o4'], ['a', 'b', 'c', 'd', 'e', 'T']], {'merged': ['a', 'b', 'c', 'd', 'e', '<<<<<<< ours', 'o0', 'o1', 'o2', 'o3', 'o4', '||||||| base', '=======', 'T', '>>>>>>> theirs'], 'conflicts': 1}), ('appended by one side only', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4']], {'merged': ['a', 'b', 'c', 'd', 'e', 't0', 't1', 't2', 't3', 't4'], 'conflicts': 0}), ('changes on both sides in different places', [['a', 'b', 'c', 'd', 'e'], ['A', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'D', 'e']], {'merged': ['A', 'b', 'c', 'D', 'e'], 'conflicts': 0}), ('theirs changes the last base line', [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'E']], {'merged': ['a', 'b', 'c', 'd', 'E'], 'conflicts': 0})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Both branches made the same change and the merge still stops with a conflict.

Match base against ours and against theirs with difflib.SequenceMatcher (autojunk off). Base lines matched on both sides are stable anchors. Between consecutive anchors (and after the last) compare the three regions: unchanged ours takes theirs, unchanged theirs takes ours, identical changes take ours, anything else is a conflict rendered as "<<<<<<< ours", ours, "||||||| base", base, "=======", theirs, ">>>>>>> theirs". Return merged lines and the conflict count.

split: open-access