broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import collections
N = 1
observations = []
def solve(deleted, added, threshold):
    cands = []
    for o, ol in deleted.items():
        for a_, al in added.items():
            if not ol or not al:
                continue
            common = sum((collections.Counter(ol) & collections.Counter(al)).values())
            score = common * 100 // max(len(ol), len(al))
            if score >= threshold:
                cands.append((-score, o, a_))
    cands.sort()
    used_o, used_a, pairs = set(), set(), []
    for neg, o, a_ in cands:
        if a_ in used_a:
            continue
        used_o.add(o)
        used_a.add(a_)
        pairs.append([o, a_, -neg])
    return sorted(pairs)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 26], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 26], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    2: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 27], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 27], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    3: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 28], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 28], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    4: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 29], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 29], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    5: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 30], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 30], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 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 collections
N = 1
observations = []
def solve(deleted, added, threshold):
    cands = []
    for o, ol in deleted.items():
        for a_, al in added.items():
            if not ol or not al:
                continue
            common = sum((collections.Counter(ol) & collections.Counter(al)).values())
            score = common * 100 // max(len(ol), len(al))
            if score >= threshold:
                cands.append((-score, o, a_))
    cands.sort()
    used_o, used_a, pairs = set(), set(), []
    for neg, o, a_ in cands:
        if o in used_o:
            continue
        used_o.add(o)
        used_a.add(a_)
        pairs.append([o, a_, -neg])
    return sorted(pairs)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 26], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 26], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    2: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 27], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 27], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    3: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 28], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 28], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    4: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 29], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 29], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    5: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 30], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 30], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 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:
A single deleted file appears as the source of multiple renames.

For deleted and added files (path -> lines), a pair scores floor(100 * multiset-common-lines / max(len_a, len_b)); empty files never pair. Pairs scoring at least the threshold are taken greedily by descending score, ties by (deleted path, added path) ascending, each file used at most once. Return [deleted, added, score] triples sorted by deleted path.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import collections
N = 1
observations = []
def solve(deleted, added, threshold):
    cands = []
    for o, ol in deleted.items():
        for a_, al in added.items():
            if not ol or not al:
                continue
            common = sum((collections.Counter(ol) & collections.Counter(al)).values())
            score = common * 100 // max(len(ol), len(al))
            if score >= threshold:
                cands.append((-score, o, a_))
    cands.sort(key=lambda c: (c[1], c[2]))
    used_o, used_a, pairs = set(), set(), []
    for neg, o, a_ in cands:
        if o in used_o or a_ in used_a:
            continue
        used_o.add(o)
        used_a.add(a_)
        pairs.append([o, a_, -neg])
    return sorted(pairs)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 26], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 26], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    2: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 27], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 27], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    3: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 28], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 28], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    4: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 29], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 29], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    5: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 30], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 30], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 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 collections
N = 1
observations = []
def solve(deleted, added, threshold):
    cands = []
    for o, ol in deleted.items():
        for a_, al in added.items():
            if not ol or not al:
                continue
            common = sum((collections.Counter(ol) & collections.Counter(al)).values())
            score = common * 100 // max(len(ol), len(al))
            if score >= threshold:
                cands.append((-score, o, a_))
    cands.sort(reverse=True)
    used_o, used_a, pairs = set(), set(), []
    for neg, o, a_ in cands:
        if o in used_o or a_ in used_a:
            continue
        used_o.add(o)
        used_a.add(a_)
        pairs.append([o, a_, -neg])
    return sorted(pairs)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 26], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 26], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    2: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 27], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 27], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    3: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 28], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 28], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    4: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 29], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 29], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 0], [])],
    5: [('exact rename', [{'old.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'new.c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['old.c', 'new.c', 100]]), ('edited rename above threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'x', 'y', 'z', 'w']}, 60], [['a.py', 'b.py', 60]]), ('score exactly at the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 50], [['a.py', 'b.py', 50]]), ('small file inside a big one', [{'small': ['l0', 'l1', 'l2']}, {'big': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], []), ('duplicate lines count once per copy', [{'dup': ['}', '}', '}', 'x']}, {'dup2': ['}', 'y', 'z', 'w']}, 30], []), ('duplicate lines on both sides', [{'d1': ['}', '}', '}', 'x']}, {'d2': ['}', '}', 'y', 'z']}, 30], [['d1', 'd2', 50]]), ('score one below the threshold', [{'a.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'b.py': ['l0', 'l1', 'l2', 'l3', 'l4', 'q', 'q', 'q', 'q', 'q']}, 51], []), ('best pairing wins', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'b': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'b1', 'b2', 'b3']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'c1', 'c2']}, 50], [['a', 'c', 80]]), ('each file used once', [{'a': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'c2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a', 'c1', 100]]), ('each destination used once', [{'a1': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'a2': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, {'c': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 50], [['a1', 'c', 100]]), ('lower score pairs after higher ones', [{'x': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9'], 'y': ['l0', 'l1', 'l2', 'l3', 'l4', 'y0', 'y1', 'y2', 'y3', 'y4']}, {'p': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'p'], 'q': ['l0', 'l1', 'l2', 'l3', 'l4', 'l5', 'l6', 'l7', 'l8', 'l9']}, 40], [['x', 'q', 100], ['y', 'p', 50]]), ('empty files never pair', [{'e': []}, {'f': [], 'g': ['z']}, 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:
A weaker pairing claims a file before its best match is considered.

For deleted and added files (path -> lines), a pair scores floor(100 * multiset-common-lines / max(len_a, len_b)); empty files never pair. Pairs scoring at least the threshold are taken greedily by descending score, ties by (deleted path, added path) ascending, each file used at most once. Return [deleted, added, score] triples sorted by deleted path.

split: open-access


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

N = 1
observations = []
def solve(parents, x, y):
    def anc(c):
        seen = set()
        stack = list(parents.get(c, []))
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []))
        return seen
    common = (anc(x) | {x}) & anc(y)
    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]
    return sorted(best)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],
    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],
    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],
    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],
    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],
}[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:
When one branch contains the other, the merge base is reported as an older commit instead of the branch tip.

Given a commit graph (commit -> parent list) and two commits, ancestors include the commit itself and all commits reachable through any parent. The merge bases are the common ancestors that are not ancestors of another common ancestor. Return them sorted.

split: open-access


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

N = 1
observations = []
def solve(parents, x, y):
    def anc(c):
        seen = set()
        stack = [c]
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []) if k == c else parents.get(k, [])[:1])
        return seen
    common = anc(x) & anc(y)
    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]
    return sorted(best)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],
    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],
    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],
    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],
    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],
}[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:
History reachable only through a merge's second parent is ignored and the base is too old or missing.

Given a commit graph (commit -> parent list) and two commits, ancestors include the commit itself and all commits reachable through any parent. The merge bases are the common ancestors that are not ancestors of another common ancestor. Return them sorted.

split: open-access


prompt:
The merge base is the root commit, so merges show every change since the beginning of history.

Given a commit graph (commit -> parent list) and two commits, ancestors include the commit itself and all commits reachable through any parent. The merge bases are the common ancestors that are not ancestors of another common ancestor. Return them sorted.

split: open-access


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

N = 1
observations = []
def solve(parents, x, y):
    def anc(c):
        seen = set()
        stack = [c]
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []))
        return seen
    common = anc(x) & anc(y)
    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]
    return [max(best, key=lambda c: (len(anc(c)), c))] if best else []
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],
    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],
    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],
    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],
    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],
}[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:
Criss-cross merges pick an arbitrary base and can report spurious conflicts or silently revert changes.

Given a commit graph (commit -> parent list) and two commits, ancestors include the commit itself and all commits reachable through any parent. The merge bases are the common ancestors that are not ancestors of another common ancestor. Return them sorted.

split: open-access


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

N = 1
observations = []
def solve(hunks, lines):
    res = []
    for ln in lines:
        shift = 0
        out = ln
        for os_, ol, ns, nl in hunks:
            s = os_
            if ln < s:
                break
            if ln < s + ol:
                out = None
                break
            shift += nl - ol
        res.append(None if out is None else ln + shift)
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 1]], [5, 6, 7]], [5, 7, 8]), ('pure deletion', [[[3, 1, 2, 0]], [2, 3, 3, 4, 10]], [2, None, None, 3, 9]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 1]], [1, 1])],
    2: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 2]], [5, 6, 7]], [5, 8, 9]), ('pure deletion', [[[3, 2, 2, 0]], [2, 3, 4, 5, 10]], [2, None, None, 3, 8]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 2]], [1, 2])],
    3: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 3]], [5, 6, 7]], [5, 9, 10]), ('pure deletion', [[[3, 3, 2, 0]], [2, 3, 5, 6, 10]], [2, None, None, 3, 7]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 3]], [1, 3])],
    4: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 4]], [5, 6, 7]], [5, 10, 11]), ('pure deletion', [[[3, 4, 2, 0]], [2, 3, 6, 7, 10]], [2, None, None, 3, 6]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 4]], [1, 4])],
    5: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 5]], [5, 6, 7]], [5, 11, 12]), ('pure deletion', [[[3, 5, 2, 0]], [2, 3, 7, 8, 10]], [2, None, None, 3, 5]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 5]], [1, 5])],
}[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(hunks, lines):
    res = []
    for ln in lines:
        shift = 0
        out = ln
        for os_, ol, ns, nl in hunks:
            s = os_ - 1 if ol == 0 else os_
            if ln < s:
                break
            if ln < s + ol:
                out = None
                break
            shift += nl - ol
        res.append(None if out is None else ln + shift)
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 1]], [5, 6, 7]], [5, 7, 8]), ('pure deletion', [[[3, 1, 2, 0]], [2, 3, 3, 4, 10]], [2, None, None, 3, 9]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 1]], [1, 1])],
    2: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 2]], [5, 6, 7]], [5, 8, 9]), ('pure deletion', [[[3, 2, 2, 0]], [2, 3, 4, 5, 10]], [2, None, None, 3, 8]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 2]], [1, 2])],
    3: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 3]], [5, 6, 7]], [5, 9, 10]), ('pure deletion', [[[3, 3, 2, 0]], [2, 3, 5, 6, 10]], [2, None, None, 3, 7]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 3]], [1, 3])],
    4: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 4]], [5, 6, 7]], [5, 10, 11]), ('pure deletion', [[[3, 4, 2, 0]], [2, 3, 6, 7, 10]], [2, None, None, 3, 6]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 4]], [1, 4])],
    5: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 5]], [5, 6, 7]], [5, 11, 12]), ('pure deletion', [[[3, 5, 2, 0]], [2, 3, 7, 8, 10]], [2, None, None, 3, 5]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 5]], [1, 5])],
}[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:
A comment on the line just above an insertion jumps down by the inserted count.

Hunks [old_start, old_len, new_start, new_len] use unified conventions (start is the line before when the length is 0) and are sorted. An old line maps to None if it lies in a hunk's old range; otherwise it moves by the sum of new_len - old_len over hunks entirely before it. A zero-length hunk after line s affects lines from s+1 on. Return the mapped line numbers.

split: open-access


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

N = 1
observations = []
def solve(hunks, lines):
    res = []
    for ln in lines:
        shift = 0
        out = ln
        for os_, ol, ns, nl in hunks:
            s = os_ if ol > 0 else os_ + 1
            if ln < s:
                break
            if ln <= s + ol:
                out = None
                break
            shift += nl - ol
        res.append(None if out is None else ln + shift)
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 1]], [5, 6, 7]], [5, 7, 8]), ('pure deletion', [[[3, 1, 2, 0]], [2, 3, 3, 4, 10]], [2, None, None, 3, 9]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 1]], [1, 1])],
    2: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 2]], [5, 6, 7]], [5, 8, 9]), ('pure deletion', [[[3, 2, 2, 0]], [2, 3, 4, 5, 10]], [2, None, None, 3, 8]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 2]], [1, 2])],
    3: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 3]], [5, 6, 7]], [5, 9, 10]), ('pure deletion', [[[3, 3, 2, 0]], [2, 3, 5, 6, 10]], [2, None, None, 3, 7]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 3]], [1, 3])],
    4: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 4]], [5, 6, 7]], [5, 10, 11]), ('pure deletion', [[[3, 4, 2, 0]], [2, 3, 6, 7, 10]], [2, None, None, 3, 6]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 4]], [1, 4])],
    5: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 5]], [5, 6, 7]], [5, 11, 12]), ('pure deletion', [[[3, 5, 2, 0]], [2, 3, 7, 8, 10]], [2, None, None, 3, 5]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 5]], [1, 5])],
}[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:
A comment on the first unchanged line after a hunk is dropped.

Hunks [old_start, old_len, new_start, new_len] use unified conventions (start is the line before when the length is 0) and are sorted. An old line maps to None if it lies in a hunk's old range; otherwise it moves by the sum of new_len - old_len over hunks entirely before it. A zero-length hunk after line s affects lines from s+1 on. Return the mapped line numbers.

split: open-access


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

N = 1
observations = []
def solve(hunks, lines):
    res = []
    for ln in lines:
        shift = 0
        out = ln
        for os_, ol, ns, nl in hunks:
            s = os_ if ol > 0 else os_ + 1
            if ln < s + ol:
                out = None
                break
            shift += nl - ol
        res.append(None if out is None else ln + shift)
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 1]], [5, 6, 7]], [5, 7, 8]), ('pure deletion', [[[3, 1, 2, 0]], [2, 3, 3, 4, 10]], [2, None, None, 3, 9]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 1]], [1, 1])],
    2: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 2]], [5, 6, 7]], [5, 8, 9]), ('pure deletion', [[[3, 2, 2, 0]], [2, 3, 4, 5, 10]], [2, None, None, 3, 8]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 2]], [1, 2])],
    3: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 3]], [5, 6, 7]], [5, 9, 10]), ('pure deletion', [[[3, 3, 2, 0]], [2, 3, 5, 6, 10]], [2, None, None, 3, 7]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 3]], [1, 3])],
    4: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 4]], [5, 6, 7]], [5, 10, 11]), ('pure deletion', [[[3, 4, 2, 0]], [2, 3, 6, 7, 10]], [2, None, None, 3, 6]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 4]], [1, 4])],
    5: [('lines before and after a replacement', [[[5, 2, 5, 3]], [4, 5, 6, 7, 8]], [4, None, None, 8, 9]), ('pure insertion after line five', [[[5, 0, 6, 5]], [5, 6, 7]], [5, 11, 12]), ('pure deletion', [[[3, 5, 2, 0]], [2, 3, 7, 8, 10]], [2, None, None, 3, 5]), ('insertion at the top of the file', [[[0, 0, 1, 2]], [1, 2]], [3, 4]), ('several hunks accumulate', [[[2, 1, 2, 2], [10, 3, 11, 1], [20, 0, 19, 4]], [1, 2, 3, 9, 10, 13, 20, 21]], [1, None, 4, 10, None, 12, 19, 24]), ('line just after a hunk', [[[7, 2, 7, 5]], [8, 9, 10]], [None, 12, 13]), ('last line of a deletion', [[[4, 3, 3, 0]], [6, 7]], [None, 4]), ('no hunks', [[], [1, 5]], [1, 5])],
}[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:
Lines before a later hunk are reported as removed.

Hunks [old_start, old_len, new_start, new_len] use unified conventions (start is the line before when the length is 0) and are sorted. An old line maps to None if it lies in a hunk's old range; otherwise it moves by the sum of new_len - old_len over hunks entirely before it. A zero-length hunk after line s affects lines from s+1 on. Return the mapped line numbers.

split: open-access