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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk < last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1] + 1:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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:
Two ranges that meet end to start stay separate, so encodings differ between replicas.

A delete set is a list of [client, clock, length] ranges, possibly unsorted, overlapping or adjacent. Normalize per client in client order: sort by clock and merge ranges that overlap or touch. Queries [client, clock] report whether the clock lies in a merged range (end exclusive). Return merged ranges and query answers.

split: open-access


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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = clk + ln - last[0]
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = last[1] + ln
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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:
Deleted clocks at the end of a long range are forgotten.

A delete set is a list of [client, clock, length] ranges, possibly unsorted, overlapping or adjacent. Normalize per client in client order: sort by clock and merge ranges that overlap or touch. Queries [client, clock] report whether the clock lies in a merged range (end exclusive). Return merged ranges and query answers.

split: open-access


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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = list(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c], key=lambda r: r[0] + r[1])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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:
Unsorted delete sets normalize to overlapping or out-of-order ranges.

A delete set is a list of [client, clock, length] ranges, possibly unsorted, overlapping or adjacent. Normalize per client in client order: sort by clock and merge ranges that overlap or touch. Queries [client, clock] report whether the clock lies in a merged range (end exclusive). Return merged ranges and query answers.

split: open-access


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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] <= a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a < q[1] <= a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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:
The first live clock after a deleted range is reported as deleted.

A delete set is a list of [client, clock, length] ranges, possibly unsorted, overlapping or adjacent. Normalize per client in client order: sort by clock and merge ranges that overlap or touch. Queries [client, clock] report whether the clock lies in a merged range (end exclusive). Return merged ranges and query answers.

split: open-access


prompt:
Diffs contain more insertions and deletions than necessary around repeated lines.

Given old and new line lists, fill a suffix LCS table L[i][j] for a[i:], b[j:], then walk from the start: equal lines are kept, otherwise delete when L[i+1][j] >= L[i][j+1] and insert otherwise; flush remaining old lines as deletions and new lines as insertions. Return [tag, line] ops with tags " ", "-", "+".

split: open-access


prompt:
A replaced line is shown as the new line followed by the removed one.

Given old and new line lists, fill a suffix LCS table L[i][j] for a[i:], b[j:], then walk from the start: equal lines are kept, otherwise delete when L[i+1][j] >= L[i][j+1] and insert otherwise; flush remaining old lines as deletions and new lines as insertions. Return [tag, line] ops with tags " ", "-", "+".

split: open-access


prompt:
The first of several trailing removed lines disappears from the diff.

Given old and new line lists, fill a suffix LCS table L[i][j] for a[i:], b[j:], then walk from the start: equal lines are kept, otherwise delete when L[i+1][j] >= L[i][j+1] and insert otherwise; flush remaining old lines as deletions and new lines as insertions. Return [tag, line] ops with tags " ", "-", "+".

split: open-access


prompt:
Edits near the start of the files are chosen from zeros and the diff is not minimal.

Given old and new line lists, fill a suffix LCS table L[i][j] for a[i:], b[j:], then walk from the start: equal lines are kept, otherwise delete when L[i+1][j] >= L[i][j+1] and insert otherwise; flush remaining old lines as deletions and new lines as insertions. Return [tag, line] ops with tags " ", "-", "+".

split: open-access


prompt:
Reported distances are larger than the true minimum.

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

split: open-access


prompt:
Runs of equal lines count as edits and the distance is overstated.

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

split: open-access


prompt:
The distance omits the remaining insertions or deletions at the end.

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

split: open-access


prompt:
Diagonals that cannot be reached with d edits are used and the reported distance is too small.

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

split: open-access


prompt:
Files whose distance equals max_d are treated as too different.

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

split: open-access


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

N = 1
observations = []
def solve(ops, context):
    changes = [i for i, op in enumerate(ops) if op[0] != ' ']
    if not changes:
        return []
    groups = []
    start = end = changes[0]
    for i in changes[1:]:
        if i - end - 1 <= context:
            end = i
        else:
            groups.append((start, end))
            start = end = i
    groups.append((start, end))
    old_no, new_no = [], []
    o = w = 0
    for tag, _ in ops:
        old_no.append(o)
        new_no.append(w)
        if tag != '+':
            o += 1
        if tag != '-':
            w += 1
    def rng(start0, count):
        first = start0 + 1 if count > 0 else start0
        return str(first) if count == 1 else '%d,%d' % (first, count)
    out = []
    for s, e in groups:
        lo = max(0, s - context)
        hi = min(len(ops) - 1, e + context)
        body = ops[lo:hi + 1]
        ol = sum(1 for t, _ in body if t != '+')
        nl = sum(1 for t, _ in body if t != '-')
        out.append('@@ -%s +%s @@' % (rng(old_no[lo], ol), rng(new_no[lo], nl)))
        out.extend(t + x for t, x in body)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0']], 3], ['@@ -0,0 +1 @@', '+x0']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 1], ['@@ -1,4 +1,4 @@', '-a', ' c0', ' c1', '+b', ' c0']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 1], ['@@ -1,2 +1 @@', '-a', ' c0', '@@ -4,2 +3,3 @@', ' c2', '+b', ' c0']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    2: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1']], 3], ['@@ -0,0 +1,2 @@', '+x0', '+x1']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 2], ['@@ -1,7 +1,7 @@', '-a', ' c0', ' c1', ' c2', ' c3', '+b', ' c0', ' c1']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 2], ['@@ -1,3 +1,2 @@', '-a', ' c0', ' c1', '@@ -5,4 +4,5 @@', ' c3', ' c4', '+b', ' c0', ' c1']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    3: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1'], ['+', 'x2']], 3], ['@@ -0,0 +1,3 @@', '+x0', '+x1', '+x2']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 3], ['@@ -1,10 +1,10 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', ' c5', '+b', ' c0', ' c1', ' c2']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 3], ['@@ -1,4 +1,3 @@', '-a', ' c0', ' c1', ' c2', '@@ -6,6 +5,7 @@', ' c4', ' c5', ' c6', '+b', ' c0', ' c1', ' c2']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    4: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1'], ['+', 'x2'], ['+', 'x3']], 3], ['@@ -0,0 +1,4 @@', '+x0', '+x1', '+x2', '+x3']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 4], ['@@ -1,12 +1,12 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', ' c5', ' c6', ' c7', '+b', ' c0', ' c1', ' c2']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], [' ', 'c8'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 4], ['@@ -1,5 +1,4 @@', '-a', ' c0', ' c1', ' c2', ' c3', '@@ -7,7 +6,8 @@', ' c5', ' c6', ' c7', ' c8', '+b', ' c0', ' c1', ' c2']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    5: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1'], ['+', 'x2'], ['+', 'x3'], ['+', 'x4']], 3], ['@@ -0,0 +1,5 @@', '+x0', '+x1', '+x2', '+x3', '+x4']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], [' ', 'c8'], [' ', 'c9'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 5], ['@@ -1,14 +1,14 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', ' c5', ' c6', ' c7', ' c8', ' c9', '+b', ' c0', ' c1', ' c2']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], [' ', 'c8'], [' ', 'c9'], [' ', 'c10'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 5], ['@@ -1,6 +1,5 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', '@@ -8,8 +7,9 @@', ' c6', ' c7', ' c8', ' c9', ' c10', '+b', ' c0', ' c1', ' c2']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
}[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(ops, context):
    changes = [i for i, op in enumerate(ops) if op[0] != ' ']
    if not changes:
        return []
    groups = []
    start = end = changes[0]
    for i in changes[1:]:
        if i - end - 1 < 2 * context:
            end = i
        else:
            groups.append((start, end))
            start = end = i
    groups.append((start, end))
    old_no, new_no = [], []
    o = w = 0
    for tag, _ in ops:
        old_no.append(o)
        new_no.append(w)
        if tag != '+':
            o += 1
        if tag != '-':
            w += 1
    def rng(start0, count):
        first = start0 + 1 if count > 0 else start0
        return str(first) if count == 1 else '%d,%d' % (first, count)
    out = []
    for s, e in groups:
        lo = max(0, s - context)
        hi = min(len(ops) - 1, e + context)
        body = ops[lo:hi + 1]
        ol = sum(1 for t, _ in body if t != '+')
        nl = sum(1 for t, _ in body if t != '-')
        out.append('@@ -%s +%s @@' % (rng(old_no[lo], ol), rng(new_no[lo], nl)))
        out.extend(t + x for t, x in body)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0']], 3], ['@@ -0,0 +1 @@', '+x0']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 1], ['@@ -1,4 +1,4 @@', '-a', ' c0', ' c1', '+b', ' c0']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 1], ['@@ -1,2 +1 @@', '-a', ' c0', '@@ -4,2 +3,3 @@', ' c2', '+b', ' c0']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    2: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1']], 3], ['@@ -0,0 +1,2 @@', '+x0', '+x1']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 2], ['@@ -1,7 +1,7 @@', '-a', ' c0', ' c1', ' c2', ' c3', '+b', ' c0', ' c1']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 2], ['@@ -1,3 +1,2 @@', '-a', ' c0', ' c1', '@@ -5,4 +4,5 @@', ' c3', ' c4', '+b', ' c0', ' c1']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    3: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1'], ['+', 'x2']], 3], ['@@ -0,0 +1,3 @@', '+x0', '+x1', '+x2']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 3], ['@@ -1,10 +1,10 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', ' c5', '+b', ' c0', ' c1', ' c2']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 3], ['@@ -1,4 +1,3 @@', '-a', ' c0', ' c1', ' c2', '@@ -6,6 +5,7 @@', ' c4', ' c5', ' c6', '+b', ' c0', ' c1', ' c2']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    4: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1'], ['+', 'x2'], ['+', 'x3']], 3], ['@@ -0,0 +1,4 @@', '+x0', '+x1', '+x2', '+x3']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 4], ['@@ -1,12 +1,12 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', ' c5', ' c6', ' c7', '+b', ' c0', ' c1', ' c2']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], [' ', 'c8'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 4], ['@@ -1,5 +1,4 @@', '-a', ' c0', ' c1', ' c2', ' c3', '@@ -7,7 +6,8 @@', ' c5', ' c6', ' c7', ' c8', '+b', ' c0', ' c1', ' c2']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
    5: [('single change in the middle', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], ['-', 'old'], ['+', 'new'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7']], 2], ['@@ -3,5 +3,5 @@', ' c2', ' c3', '-old', '+new', ' c4', ' c5']), ('change at the very start', [[['-', 'first'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4']], 3], ['@@ -1,4 +1,3 @@', '-first', ' c0', ' c1', ' c2']), ('pure insertion into an empty file', [[['+', 'x0'], ['+', 'x1'], ['+', 'x2'], ['+', 'x3'], ['+', 'x4']], 3], ['@@ -0,0 +1,5 @@', '+x0', '+x1', '+x2', '+x3', '+x4']), ('pure deletion of every line', [[['-', 'gone']], 1], ['@@ -1 +0,0 @@', '-gone']), ('two changes separated by exactly twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], [' ', 'c8'], [' ', 'c9'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 5], ['@@ -1,14 +1,14 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', ' c5', ' c6', ' c7', ' c8', ' c9', '+b', ' c0', ' c1', ' c2']), ('two changes separated by more than twice the context', [[['-', 'a'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5'], [' ', 'c6'], [' ', 'c7'], [' ', 'c8'], [' ', 'c9'], [' ', 'c10'], ['+', 'b'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 5], ['@@ -1,6 +1,5 @@', '-a', ' c0', ' c1', ' c2', ' c3', ' c4', '@@ -8,8 +7,9 @@', ' c6', ' c7', ' c8', ' c9', ' c10', '+b', ' c0', ' c1', ' c2']), ('insertion after existing lines', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], ['+', 'tail']], 2], ['@@ -4,2 +4,3 @@', ' c3', ' c4', '+tail']), ('single-line ranges', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], ['-', 'x'], ['+', 'y'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2']], 0], ['@@ -4 +4 @@', '-x', '+y']), ('no changes', [[[' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3']], 3], []), ('deletion and insertion in separate hunks', [[[' ', 'a'], ['-', 'b'], [' ', 'c'], ['+', 'd'], [' ', 'e']], 0], ['@@ -2 +1,0 @@', '-b', '@@ -3,0 +3 @@', '+d']), ('deletion near the start with wide context', [[[' ', 'c0'], ['-', 'd1'], ['-', 'd2'], [' ', 'c0'], [' ', 'c1'], [' ', 'c2'], [' ', 'c3'], [' ', 'c4'], [' ', 'c5']], 3], ['@@ -1,6 +1,4 @@', ' c0', '-d1', '-d2', ' c0', ' c1', ' c2'])],
}[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:
Two nearby changes produce two hunks that repeat the same context lines.

Given a full edit script ([tag, line], tags " ", "-", "+") and a context width C, group changes whose separating equal lines number at most 2C, extend each group by up to C lines on both sides, and emit a header "@@ -a,b +c,d @@" followed by the hunk lines. A range start is the 1-based first line, or the line before when the count is 0; a count of 1 is omitted.

split: open-access