{"abstract":"Unsorted delete sets normalize to overlapping or out-of-order ranges.","category":"CRDT convergence","checks":8,"contract":"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.","evaluation_group":"w2-crdt-convergence-delete-set-normalization","failed_approach":"Sorting by end clock still places a long early range after short ranges it contains.","family":"w2-crdt-convergence-delete-set-normalization-clock-sort","id":"FA-75331","implementations":{"attempt":{"sha256":"2ac787ee9009ba9b0462f60194f4b53cef7155a277f97dd763a39a7e6b3f0c7a","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ranges, queries):\n    by = {}\n    for c, clk, ln in ranges:\n        by.setdefault(c, []).append([clk, ln])\n    out = []\n    for c in sorted(by):\n        rs = sorted(by[c], key=lambda r: r[0] + r[1])\n        merged = [rs[0][:]]\n        for clk, ln in rs[1:]:\n            last = merged[-1]\n            if clk <= last[0] + last[1]:\n                last[1] = max(last[1], clk + ln - last[0])\n            else:\n                merged.append([clk, ln])\n        out.extend([c, a, b] for a, b in merged)\n    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]\n    return {'ranges': out, 'hits': hits}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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]})],\n    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]})],\n    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]})],\n    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]})],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"318b2b99fa716ea1b0bb22e2ddddc9e5436740fb4363a52b08a7df3b8fde5b3d","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ranges, queries):\n    by = {}\n    for c, clk, ln in ranges:\n        by.setdefault(c, []).append([clk, ln])\n    out = []\n    for c in sorted(by):\n        rs = list(by[c])\n        merged = [rs[0][:]]\n        for clk, ln in rs[1:]:\n            last = merged[-1]\n            if clk <= last[0] + last[1]:\n                last[1] = max(last[1], clk + ln - last[0])\n            else:\n                merged.append([clk, ln])\n        out.extend([c, a, b] for a, b in merged)\n    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]\n    return {'ranges': out, 'hits': hits}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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]})],\n    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]})],\n    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]})],\n    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]})],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"d56fbc60856d774d390799787a14c39164ac12816ab600995fab894f7065f355","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ranges, queries):\n    by = {}\n    for c, clk, ln in ranges:\n        by.setdefault(c, []).append([clk, ln])\n    out = []\n    for c in sorted(by):\n        rs = sorted(by[c])\n        merged = [rs[0][:]]\n        for clk, ln in rs[1:]:\n            last = merged[-1]\n            if clk <= last[0] + last[1]:\n                last[1] = max(last[1], clk + ln - last[0])\n            else:\n                merged.append([clk, ln])\n        out.extend([c, a, b] for a, b in merged)\n    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]\n    return {'ranges': out, 'hits': hits}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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]})],\n    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]})],\n    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]})],\n    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]})],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-crdt-convergence-delete-set-normalization-clock-sort","generated_at":"2026-09-29T14:49:05.410732+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Sequence CRDTs ship deletions as compact range sets that every replica must normalize identically.","repair":"Sort each client's ranges by start clock before merging.","root_cause":"The per-client ranges are not sorted by clock before the linear merge.","sha256":"f1c0bd7364a06c17475a0b92e1931f01ea865b83dfd90deb531a08175dc5d948","title":"Delete set normalization: ranges are merged in arrival order · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":42.581,"exit_code":1,"observations":[{"actual":{"hits":[true,false],"ranges":[[1,0,5]]},"check":"adjacent ranges merge","expected":{"hits":[true,false],"ranges":[[1,0,5]]},"passed":true},{"actual":{"hits":[false,true],"ranges":[[1,0,2],[1,3,1]]},"check":"one-clock gap stays split","expected":{"hits":[false,true],"ranges":[[1,0,2],[1,3,1]]},"passed":true},{"actual":{"hits":[true,false],"ranges":[[2,3,7]]},"check":"contained range does not shrink","expected":{"hits":[true,false],"ranges":[[2,0,10]]},"passed":false},{"actual":{"hits":[true,true,false],"ranges":[[3,5,6]]},"check":"overlap extends","expected":{"hits":[true,true,false],"ranges":[[3,5,6]]},"passed":true},{"actual":{"hits":[true,false],"ranges":[[4,0,11]]},"check":"unsorted input","expected":{"hits":[true,false],"ranges":[[4,0,11]]},"passed":true},{"actual":{"hits":[true,false,true],"ranges":[[5,0,2],[6,1,3]]},"check":"several clients","expected":{"hits":[true,false,true],"ranges":[[5,0,2],[6,1,3]]},"passed":true},{"actual":{"hits":[false,true],"ranges":[[8,5,15],[8,21,2]]},"check":"long range earlier start sorted after by end","expected":{"hits":[false,true],"ranges":[[8,0,20],[8,21,2]]},"passed":false},{"actual":{"hits":[false],"ranges":[]},"check":"empty input","expected":{"hits":[false],"ranges":[]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"adjacent ranges merge\", \"actual\": {\"ranges\": [[1, 0, 5]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[1, 0, 5]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"one-clock gap stays split\", \"actual\": {\"ranges\": [[1, 0, 2], [1, 3, 1]], \"hits\": [false, true]}, \"expected\": {\"ranges\": [[1, 0, 2], [1, 3, 1]], \"hits\": [false, true]}, \"passed\": true}, {\"check\": \"contained range does not shrink\", \"actual\": {\"ranges\": [[2, 3, 7]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[2, 0, 10]], \"hits\": [true, false]}, \"passed\": false}, {\"check\": \"overlap extends\", \"actual\": {\"ranges\": [[3, 5, 6]], \"hits\": [true, true, false]}, \"expected\": {\"ranges\": [[3, 5, 6]], \"hits\": [true, true, false]}, \"passed\": true}, {\"check\": \"unsorted input\", \"actual\": {\"ranges\": [[4, 0, 11]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[4, 0, 11]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"several clients\", \"actual\": {\"ranges\": [[5, 0, 2], [6, 1, 3]], \"hits\": [true, false, true]}, \"expected\": {\"ranges\": [[5, 0, 2], [6, 1, 3]], \"hits\": [true, false, true]}, \"passed\": true}, {\"check\": \"long range earlier start sorted after by end\", \"actual\": {\"ranges\": [[8, 5, 15], [8, 21, 2]], \"hits\": [false, true]}, \"expected\": {\"ranges\": [[8, 0, 20], [8, 21, 2]], \"hits\": [false, true]}, \"passed\": false}, {\"check\": \"empty input\", \"actual\": {\"ranges\": [], \"hits\": [false]}, \"expected\": {\"ranges\": [], \"hits\": [false]}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.895,"exit_code":1,"observations":[{"actual":{"hits":[true,false],"ranges":[[1,0,5]]},"check":"adjacent ranges merge","expected":{"hits":[true,false],"ranges":[[1,0,5]]},"passed":true},{"actual":{"hits":[false,true],"ranges":[[1,0,2],[1,3,1]]},"check":"one-clock gap stays split","expected":{"hits":[false,true],"ranges":[[1,0,2],[1,3,1]]},"passed":true},{"actual":{"hits":[true,false],"ranges":[[2,0,10]]},"check":"contained range does not shrink","expected":{"hits":[true,false],"ranges":[[2,0,10]]},"passed":true},{"actual":{"hits":[true,true,false],"ranges":[[3,5,6]]},"check":"overlap extends","expected":{"hits":[true,true,false],"ranges":[[3,5,6]]},"passed":true},{"actual":{"hits":[true,false],"ranges":[[4,9,2]]},"check":"unsorted input","expected":{"hits":[true,false],"ranges":[[4,0,11]]},"passed":false},{"actual":{"hits":[true,false,true],"ranges":[[5,0,2],[6,1,3]]},"check":"several clients","expected":{"hits":[true,false,true],"ranges":[[5,0,2],[6,1,3]]},"passed":true},{"actual":{"hits":[false,true],"ranges":[[8,0,20],[8,21,2]]},"check":"long range earlier start sorted after by end","expected":{"hits":[false,true],"ranges":[[8,0,20],[8,21,2]]},"passed":true},{"actual":{"hits":[false],"ranges":[]},"check":"empty input","expected":{"hits":[false],"ranges":[]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"adjacent ranges merge\", \"actual\": {\"ranges\": [[1, 0, 5]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[1, 0, 5]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"one-clock gap stays split\", \"actual\": {\"ranges\": [[1, 0, 2], [1, 3, 1]], \"hits\": [false, true]}, \"expected\": {\"ranges\": [[1, 0, 2], [1, 3, 1]], \"hits\": [false, true]}, \"passed\": true}, {\"check\": \"contained range does not shrink\", \"actual\": {\"ranges\": [[2, 0, 10]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[2, 0, 10]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"overlap extends\", \"actual\": {\"ranges\": [[3, 5, 6]], \"hits\": [true, true, false]}, \"expected\": {\"ranges\": [[3, 5, 6]], \"hits\": [true, true, false]}, \"passed\": true}, {\"check\": \"unsorted input\", \"actual\": {\"ranges\": [[4, 9, 2]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[4, 0, 11]], \"hits\": [true, false]}, \"passed\": false}, {\"check\": \"several clients\", \"actual\": {\"ranges\": [[5, 0, 2], [6, 1, 3]], \"hits\": [true, false, true]}, \"expected\": {\"ranges\": [[5, 0, 2], [6, 1, 3]], \"hits\": [true, false, true]}, \"passed\": true}, {\"check\": \"long range earlier start sorted after by end\", \"actual\": {\"ranges\": [[8, 0, 20], [8, 21, 2]], \"hits\": [false, true]}, \"expected\": {\"ranges\": [[8, 0, 20], [8, 21, 2]], \"hits\": [false, true]}, \"passed\": true}, {\"check\": \"empty input\", \"actual\": {\"ranges\": [], \"hits\": [false]}, \"expected\": {\"ranges\": [], \"hits\": [false]}, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":49.014,"exit_code":0,"observations":[{"actual":{"hits":[true,false],"ranges":[[1,0,5]]},"check":"adjacent ranges merge","expected":{"hits":[true,false],"ranges":[[1,0,5]]},"passed":true},{"actual":{"hits":[false,true],"ranges":[[1,0,2],[1,3,1]]},"check":"one-clock gap stays split","expected":{"hits":[false,true],"ranges":[[1,0,2],[1,3,1]]},"passed":true},{"actual":{"hits":[true,false],"ranges":[[2,0,10]]},"check":"contained range does not shrink","expected":{"hits":[true,false],"ranges":[[2,0,10]]},"passed":true},{"actual":{"hits":[true,true,false],"ranges":[[3,5,6]]},"check":"overlap extends","expected":{"hits":[true,true,false],"ranges":[[3,5,6]]},"passed":true},{"actual":{"hits":[true,false],"ranges":[[4,0,11]]},"check":"unsorted input","expected":{"hits":[true,false],"ranges":[[4,0,11]]},"passed":true},{"actual":{"hits":[true,false,true],"ranges":[[5,0,2],[6,1,3]]},"check":"several clients","expected":{"hits":[true,false,true],"ranges":[[5,0,2],[6,1,3]]},"passed":true},{"actual":{"hits":[false,true],"ranges":[[8,0,20],[8,21,2]]},"check":"long range earlier start sorted after by end","expected":{"hits":[false,true],"ranges":[[8,0,20],[8,21,2]]},"passed":true},{"actual":{"hits":[false],"ranges":[]},"check":"empty input","expected":{"hits":[false],"ranges":[]},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"adjacent ranges merge\", \"actual\": {\"ranges\": [[1, 0, 5]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[1, 0, 5]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"one-clock gap stays split\", \"actual\": {\"ranges\": [[1, 0, 2], [1, 3, 1]], \"hits\": [false, true]}, \"expected\": {\"ranges\": [[1, 0, 2], [1, 3, 1]], \"hits\": [false, true]}, \"passed\": true}, {\"check\": \"contained range does not shrink\", \"actual\": {\"ranges\": [[2, 0, 10]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[2, 0, 10]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"overlap extends\", \"actual\": {\"ranges\": [[3, 5, 6]], \"hits\": [true, true, false]}, \"expected\": {\"ranges\": [[3, 5, 6]], \"hits\": [true, true, false]}, \"passed\": true}, {\"check\": \"unsorted input\", \"actual\": {\"ranges\": [[4, 0, 11]], \"hits\": [true, false]}, \"expected\": {\"ranges\": [[4, 0, 11]], \"hits\": [true, false]}, \"passed\": true}, {\"check\": \"several clients\", \"actual\": {\"ranges\": [[5, 0, 2], [6, 1, 3]], \"hits\": [true, false, true]}, \"expected\": {\"ranges\": [[5, 0, 2], [6, 1, 3]], \"hits\": [true, false, true]}, \"passed\": true}, {\"check\": \"long range earlier start sorted after by end\", \"actual\": {\"ranges\": [[8, 0, 20], [8, 21, 2]], \"hits\": [false, true]}, \"expected\": {\"ranges\": [[8, 0, 20], [8, 21, 2]], \"hits\": [false, true]}, \"passed\": true}, {\"check\": \"empty input\", \"actual\": {\"ranges\": [], \"hits\": [false]}, \"expected\": {\"ranges\": [], \"hits\": [false]}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}