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)
            delta += len(new) - len(old)
            continue
        lines[found:found + len(old)] = 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)
            delta = 0
            continue
        lines[found:found + len(old)] = 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:
After one hunk fails, the following hunks are searched at displaced positions.

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

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):
            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(old)] = 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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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(1, 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(old)] = 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:
Hunks displaced by exactly max_offset lines fail to apply.

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