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

N = 1
observations = []
def solve(diffs):
    res = []
    diffs = [list(d) for d in diffs if d[1] != '']
    i = 0
    while i < len(diffs):
        if diffs[i][0] == 0:
            if res and res[-1][0] == 0:
                res[-1][1] += diffs[i][1]
            else:
                res.append([0, diffs[i][1]])
            i += 1
            continue
        dl = ins = ''
        while i < len(diffs) and diffs[i][0] != 0:
            if diffs[i][0] == -1:
                dl += diffs[i][1]
            else:
                ins += diffs[i][1]
            i += 1
        suffix = ''
        if dl and ins:
            p = 0
            while p < min(len(dl), len(ins)) and dl[p] == ins[p]:
                p += 1
            if p:
                if res and res[-1][0] == 0:
                    res[-1][1] += dl[:p]
                else:
                    res.append([0, dl[:p]])
                dl, ins = dl[p:], ins[p:]
            s = 0
            while s < min(len(dl), len(ins)) and dl[-1 - s] == ins[-1 - s]:
                s += 1
            suffix = dl[len(dl) - s:]
            dl, ins = dl[:len(dl) - s], ins[:len(ins) - s]
        if dl:
            res.append([-1, dl])
        if ins:
            res.append([1, ins])
        if suffix:
            if i < len(diffs) and diffs[i][0] == 0:
                diffs[i] = [0, suffix + diffs[i][1]]
            else:
                pass
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz1'], [1, 'uvz1']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]), ('prefix at the start of the text', [[[-1, 'prea'], [1, 'preb'], [0, 'tail']]], [[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']])],
    2: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz2'], [1, 'uvz2']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z2']]), ('prefix at the start of the text', [[[-1, 'preprea'], [1, 'prepreb'], [0, 'tail']]], [[0, 'prepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab2'], [0, ''], [1, 'ac2']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '2']])],
    3: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz3'], [1, 'uvz3']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z3']]), ('prefix at the start of the text', [[[-1, 'prepreprea'], [1, 'preprepreb'], [0, 'tail']]], [[0, 'preprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab3'], [0, ''], [1, 'ac3']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '3']])],
    4: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz4'], [1, 'uvz4']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z4']]), ('prefix at the start of the text', [[[-1, 'preprepreprea'], [1, 'prepreprepreb'], [0, 'tail']]], [[0, 'prepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab4'], [0, ''], [1, 'ac4']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '4']])],
    5: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz5'], [1, 'uvz5']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z5']]), ('prefix at the start of the text', [[[-1, 'prepreprepreprea'], [1, 'preprepreprepreb'], [0, 'tail']]], [[0, 'preprepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab5'], [0, ''], [1, 'ac5']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '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(diffs):
    res = []
    diffs = [list(d) for d in diffs if d[1] != '']
    i = 0
    while i < len(diffs):
        if diffs[i][0] == 0:
            if res and res[-1][0] == 0:
                res[-1][1] += diffs[i][1]
            else:
                res.append([0, diffs[i][1]])
            i += 1
            continue
        dl = ins = ''
        while i < len(diffs) and diffs[i][0] != 0:
            if diffs[i][0] == -1:
                dl += diffs[i][1]
            else:
                ins += diffs[i][1]
            i += 1
        suffix = ''
        if dl and ins:
            p = 0
            while p < min(len(dl), len(ins)) and dl[p] == ins[p]:
                p += 1
            if p:
                if res and res[-1][0] == 0:
                    res[-1][1] += dl[:p]
                else:
                    res.append([0, dl[:p]])
                dl, ins = dl[p:], ins[p:]
            s = 0
            while s < min(len(dl), len(ins)) and dl[-1 - s] == ins[-1 - s]:
                s += 1
            suffix = dl[len(dl) - s:]
            dl, ins = dl[:len(dl) - s], ins[:len(ins) - s]
        if dl:
            res.append([-1, dl])
        if ins:
            res.append([1, ins])
        if suffix:
            if i < len(diffs) and diffs[i][0] == 0:
                diffs[i] = [0, suffix + diffs[i][1]]
            elif res:
                res[-1][1] += suffix
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz1'], [1, 'uvz1']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]), ('prefix at the start of the text', [[[-1, 'prea'], [1, 'preb'], [0, 'tail']]], [[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']])],
    2: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz2'], [1, 'uvz2']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z2']]), ('prefix at the start of the text', [[[-1, 'preprea'], [1, 'prepreb'], [0, 'tail']]], [[0, 'prepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab2'], [0, ''], [1, 'ac2']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '2']])],
    3: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz3'], [1, 'uvz3']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z3']]), ('prefix at the start of the text', [[[-1, 'prepreprea'], [1, 'preprepreb'], [0, 'tail']]], [[0, 'preprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab3'], [0, ''], [1, 'ac3']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '3']])],
    4: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz4'], [1, 'uvz4']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z4']]), ('prefix at the start of the text', [[[-1, 'preprepreprea'], [1, 'prepreprepreb'], [0, 'tail']]], [[0, 'prepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab4'], [0, ''], [1, 'ac4']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '4']])],
    5: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz5'], [1, 'uvz5']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z5']]), ('prefix at the start of the text', [[[-1, 'prepreprepreprea'], [1, 'preprepreprepreb'], [0, 'tail']]], [[0, 'preprepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab5'], [0, ''], [1, 'ac5']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '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:
Characters shared by the final deletion and insertion disappear from the output.

Normalize a character diff of [op, text] (op -1 delete, 0 equal, 1 insert): drop empty texts, merge adjacent equalities, collect each run of edits into one deletion and one insertion (deletion first), move their common prefix into the preceding equality (creating one at the start if needed) and their common suffix into the following equality (appending one at the end if needed).

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 = len(set(ol) & set(al))
            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 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(min(ol.count(x), al.count(x)) for x in ol)
            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 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:
Files full of repeated lines (braces, blank lines) score too low to be detected as 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 // min(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 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)

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 // ((len(ol) + len(al)) // 2)
            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 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 three-line file is reported as renamed to a large file that merely contains it.

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()
    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)

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 - 1:
                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 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:
Files exactly at the configured similarity are shown as delete plus add.

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