FA-87791 / Collision detection broadphase / Open access

Swap-begin events skip the y overlap check · case 01

Boxes crossing on x far apart in y create contacts.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Every min-over-max swap adds a begin pair.

VERIFIED REPAIR

Begin only when y intervals overlap in the new frame.

Unsuccessful approach: Checking one side of the y interval still admits separated boxes.

Case contract

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

Why this case matters

Broadphase stages decide which object pairs ever reach narrowphase; a wrong boundary, ordering or bookkeeping rule silently drops real contacts or floods the solver with false candidates.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prev, curr):
    old = {b[0]: b for b in prev}
    new = {b[0]: b for b in curr}
    E = []
    for i, b in old.items():
        E.append([b[1], 0, i])
        E.append([b[3], 1, i])
    E.sort()
    for e in E:
        b = new[e[2]]
        e[0] = b[1] if e[1] == 0 else b[3]
    def yover(a, c):
        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]
    begins, ends = set(), set()
    swaps = 0
    for i in range(1, len(E)):
        j = i
        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):
            e, f = E[j], E[j - 1]
            E[j - 1], E[j] = e, f
            swaps += 1
            p = (min(e[2], f[2]), max(e[2], f[2]))
            if e[1] == 0 and f[1] == 1:
                begins.add(p)
            elif e[1] == 1 and f[1] == 0:
                ends.add(p)
            j -= 1
    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[4, -3.0, 4.0, -3.0, 7.0], [12, -2.0, 0.0, -1.0, 0.0], [31, -3.0, -5.0, 0.0, -2.0], [17, 2.0, -3.0, 2.0, -1.0]], [[4, -4.0, 4.0, -4.0, 7.0], [12, 2.0, 0.0, 3.0, 0.0], [31, -3.0, -6.0, 0.0, -3.0], [17, 2.0, -3.0, 2.0, -1.0]]], [[], [[4, 31], [12, 31]], 5]], [[[[8, -3.0, 4.0, 0.0, 6.0], [15, 2.0, -2.0, 4.0, -2.0], [33, -1.0, 2.0, 0.0, 2.0], [10, 2.0, -3.0, 3.0, -1.0]], [[8, -1.0, 5.0, 2.0, 7.0], [15, -1.0, -2.0, 1.0, -2.0], [33, 0.0, 3.0, 1.0, 3.0], [10, -1.0, -4.0, 0.0, -2.0]]], [[], [], 10]], [[[[36, 4.0, -1.0, 5.0, 2.0], [8, 1.0, 3.0, 1.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 1.0, 4.0, 4.0, 5.0], [2, -5.0, -2.0, -4.0, 0.0], [23, 2.0, 1.0, 4.0, 1.0]], [[36, 3.0, -2.0, 4.0, 1.0], [8, 5.0, 3.0, 5.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 0.0, 3.0, 3.0, 4.0], [2, -3.0, -1.0, -2.0, 1.0], [23, 3.0, 1.0, 5.0, 1.0]]], [[[2, 7]], [[8, 28], [8, 36]], 12]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]], [[[[25, 2.0, 0.0, 5.0, 2.0], [26, -4.0, -3.0, -2.0, 0.0], [3, 4.0, 4.0, 6.0, 6.0], [30, 4.0, 0.0, 6.0, 2.0]], [[25, 3.0, 1.0, 6.0, 3.0], [26, -7.0, -4.0, -5.0, -1.0], [3, 4.0, 5.0, 6.0, 7.0], [30, 6.0, 0.0, 8.0, 2.0]]], [[], [], 0]], [[[[12, 2.0, -4.0, 4.0, -4.0], [39, -2.0, -1.0, 1.0, -1.0], [5, -5.0, 5.0, -5.0, 7.0]], [[12, 2.0, -5.0, 4.0, -5.0], [39, -2.0, 0.0, 1.0, 0.0], [5, -1.0, 5.0, -1.0, 7.0]]], [[], [], 2]], [[[[12, -1.0, 3.0, -1.0, 6.0], [1, -1.0, -4.0, 0.0, -3.0], [16, -3.0, -2.0, -2.0, -1.0], [30, 5.0, -4.0, 8.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]], [[12, 3.0, 3.0, 3.0, 6.0], [1, -1.0, -5.0, 0.0, -4.0], [16, 1.0, -2.0, 2.0, -1.0], [30, 9.0, -4.0, 12.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]]], [[], [[1, 12], [1, 16], [6, 12]], 10]], [[[[36, -1.0, -4.0, 1.0, -4.0], [9, -1.0, -2.0, 0.0, 1.0]], [[36, 1.0, -5.0, 3.0, -5.0], [9, 0.0, -1.0, 1.0, 2.0]]], [[], [], 0]]], [[[[[36, 5.0, -4.0, 6.0, -3.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -5.0, -4.0, -4.0, -2.0], [3, 5.0, 4.0, 5.0, 4.0], [7, 0.0, 0.0, 3.0, 2.0], [28, 0.0, 0.0, 2.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]], [[36, 5.0, -3.0, 6.0, -2.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -4.0, -4.0, -3.0, -2.0], [3, 6.0, 4.0, 6.0, 4.0], [7, 0.0, 1.0, 3.0, 3.0], [28, 4.0, 0.0, 6.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]]], [[], [[6, 28], [7, 28]], 7]], [[[[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 2.0, 2.0, 3.0]], [[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 3.0, 2.0, 4.0]]], [[], [], 0]], [[[[30, -1.0, -5.0, 0.0, -5.0], [20, 4.0, -5.0, 5.0, -4.0], [1, -1.0, -2.0, -1.0, -1.0], [12, -2.0, 1.0, -2.0, 2.0], [22, 1.0, 5.0, 2.0, 7.0]], [[30, -1.0, -6.0, 0.0, -6.0], [20, 3.0, -6.0, 4.0, -5.0], [1, -1.0, -1.0, -1.0, 0.0], [12, 0.0, 0.0, 0.0, 1.0], [22, 0.0, 5.0, 1.0, 7.0]]], [[[1, 12]], [[1, 12]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]], [[[[22, -2.0, 0.0, 1.0, 0.0], [8, -1.0, -2.0, 0.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0], [33, 2.0, 4.0, 4.0, 5.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 1.0, -5.0, 2.0, -4.0], [32, -4.0, 0.0, -1.0, 0.0]], [[22, -5.0, 0.0, -2.0, 0.0], [8, -4.0, -3.0, -3.0, -3.0], [2, 0.0, 0.0, 3.0, 1.0], [33, 2.0, 5.0, 4.0, 6.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 2.0, -4.0, 3.0, -3.0], [32, 0.0, 0.0, 3.0, 0.0]]], [[[2, 32], [9, 37]], [[8, 32], [22, 32], [22, 37]], 16]], [[[[17, -3.0, 5.0, 0.0, 7.0], [29, -3.0, 0.0, -3.0, 1.0], [20, 5.0, -3.0, 8.0, -2.0], [4, 3.0, -5.0, 5.0, -2.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 1.0, -4.0, 4.0, -2.0], [24, 2.0, -2.0, 3.0, 0.0]], [[17, 1.0, 5.0, 4.0, 7.0], [29, -6.0, -1.0, -6.0, 0.0], [20, 5.0, -2.0, 8.0, -1.0], [4, 2.0, -6.0, 4.0, -3.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 0.0, -5.0, 3.0, -3.0], [24, 2.0, -3.0, 3.0, -1.0]]], [[], [[2, 17], [2, 29], [4, 20], [17, 29]], 12]], [[[[30, 4.0, 3.0, 4.0, 3.0], [11, -1.0, 4.0, 1.0, 6.0], [29, -3.0, -3.0, -3.0, 0.0], [18, -1.0, -4.0, 0.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, -1.0, 0.0, -1.0, 3.0]], [[30, 3.0, 3.0, 3.0, 3.0], [11, 3.0, 3.0, 5.0, 5.0], [29, -3.0, -2.0, -3.0, 1.0], [18, 0.0, -4.0, 1.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, 0.0, 0.0, 0.0, 3.0]]], [[[11, 30]], [[11, 18], [11, 21], [11, 31]], 11]], [[[[26, -5.0, 4.0, -4.0, 6.0], [30, -2.0, 0.0, 0.0, 3.0], [39, -5.0, -2.0, -2.0, -2.0]], [[26, -1.0, 4.0, 0.0, 6.0], [30, -2.0, -1.0, 0.0, 2.0], [39, -8.0, -1.0, -5.0, -1.0]]], [[], [[26, 39], [30, 39]], 6]]], [[[[[8, -4.0, 4.0, -2.0, 4.0], [32, 2.0, -2.0, 4.0, -1.0], [1, -2.0, -1.0, -1.0, 0.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 4.0, -2.0, 7.0], [11, -4.0, -5.0, -3.0, -2.0], [12, 2.0, -2.0, 4.0, 1.0]], [[8, -3.0, 3.0, -1.0, 3.0], [32, -1.0, -3.0, 1.0, -2.0], [1, -5.0, 0.0, -4.0, 1.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 3.0, -2.0, 6.0], [11, -4.0, -6.0, -3.0, -3.0], [12, 3.0, -3.0, 5.0, 0.0]]], [[], [[1, 8], [12, 32]], 16]], [[[[17, -5.0, 4.0, -2.0, 6.0], [5, -2.0, -5.0, -1.0, -3.0], [22, -1.0, 0.0, 0.0, 2.0], [1, -3.0, 1.0, 0.0, 2.0], [12, -3.0, 1.0, -1.0, 4.0], [33, 3.0, 2.0, 4.0, 5.0], [19, -5.0, 5.0, -2.0, 7.0]], [[17, -3.0, 4.0, 0.0, 6.0], [5, -1.0, -4.0, 0.0, -2.0], [22, -4.0, -1.0, -3.0, 1.0], [1, -2.0, 1.0, 1.0, 2.0], [12, -3.0, 0.0, -1.0, 3.0], [33, 5.0, 3.0, 6.0, 6.0], [19, -5.0, 5.0, -2.0, 7.0]]], [[], [[1, 22], [5, 19], [5, 22]], 19]], [[[[8, 5.0, 2.0, 8.0, 5.0], [13, 2.0, -4.0, 3.0, -1.0]], [[8, 2.0, 3.0, 5.0, 6.0], [13, 1.0, -4.0, 2.0, -1.0]]], [[], [], 1]], [[[[3, -1.0, -1.0, 2.0, 2.0], [10, -5.0, -3.0, -5.0, -1.0]], [[3, -2.0, -1.0, 1.0, 2.0], [10, -4.0, -4.0, -4.0, -2.0]]], [[], [], 0]], [[[[8, 4.0, 5.0, 4.0, 5.0], [25, 2.0, -5.0, 5.0, -3.0], [26, 3.0, 5.0, 6.0, 7.0], [35, -5.0, 2.0, -3.0, 4.0], [22, 4.0, -4.0, 6.0, -3.0], [5, -5.0, -4.0, -3.0, -4.0]], [[8, 4.0, 5.0, 4.0, 5.0], [25, 3.0, -5.0, 6.0, -3.0], [26, 4.0, 6.0, 7.0, 8.0], [35, -5.0, 1.0, -3.0, 3.0], [22, 3.0, -4.0, 5.0, -3.0], [5, -6.0, -4.0, -4.0, -4.0]]], [[], [], 3]], [[[[22, 0.0, 3.0, 1.0, 4.0], [36, 3.0, -5.0, 3.0, -2.0]], [[22, 0.0, 3.0, 1.0, 4.0], [36, 0.0, -5.0, 0.0, -2.0]]], [[], [], 2]], [[[[29, 4.0, 4.0, 6.0, 5.0], [28, 4.0, 5.0, 6.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -2.0, 2.0, -2.0, 3.0], [25, -2.0, 2.0, 0.0, 4.0], [6, -3.0, 1.0, -1.0, 3.0], [35, -4.0, 4.0, -3.0, 7.0]], [[29, 8.0, 4.0, 10.0, 5.0], [28, 5.0, 5.0, 7.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -5.0, 3.0, -5.0, 4.0], [25, -1.0, 2.0, 1.0, 4.0], [6, 1.0, 1.0, 3.0, 3.0], [35, -2.0, 4.0, -1.0, 7.0]]], [[[20, 35], [25, 35]], [[6, 20], [6, 35], [20, 25], [20, 35], [28, 29]], 13]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]]], [[[[[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 5.0, -5.0, 7.0, -3.0]], [[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 6.0, -5.0, 8.0, -3.0]]], [[], [], 0]], [[[[17, 5.0, -3.0, 5.0, -1.0], [13, -5.0, 3.0, -2.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 3.0, 5.0, 6.0, 7.0], [7, -1.0, -2.0, 1.0, 1.0], [10, 4.0, 3.0, 7.0, 6.0], [1, 4.0, -5.0, 5.0, -2.0], [3, -3.0, -5.0, -1.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]], [[17, 6.0, -3.0, 6.0, -1.0], [13, -4.0, 3.0, -1.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 4.0, 4.0, 7.0, 6.0], [7, -2.0, -2.0, 0.0, 1.0], [10, 4.0, 4.0, 7.0, 7.0], [1, 4.0, -6.0, 5.0, -3.0], [3, -4.0, -5.0, -2.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]]], [[], [[1, 17], [13, 28]], 5]], [[[[24, 2.0, -2.0, 3.0, -2.0], [2, 0.0, -4.0, 1.0, -4.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 3.0, -5.0, 5.0, -4.0], [10, 3.0, 3.0, 6.0, 4.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 3.0, -2.0, 6.0, -2.0]], [[24, -1.0, -2.0, 0.0, -2.0], [2, 0.0, -5.0, 1.0, -5.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 4.0, -5.0, 6.0, -4.0], [10, 3.0, 2.0, 6.0, 3.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 0.0, -2.0, 3.0, -2.0]]], [[[22, 24]], [[4, 20], [10, 24], [20, 24]], 9]], [[[[6, 0.0, -2.0, 0.0, -2.0], [11, -2.0, 0.0, -2.0, 3.0], [39, 4.0, 0.0, 7.0, 3.0]], [[6, 1.0, -2.0, 1.0, -2.0], [11, 2.0, 1.0, 2.0, 4.0], [39, 4.0, 0.0, 7.0, 3.0]]], [[], [[6, 11]], 4]], [[[[18, -1.0, 3.0, 0.0, 4.0], [39, 5.0, 0.0, 7.0, 2.0], [2, -1.0, 1.0, -1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, -2.0, 3.0, -1.0, 6.0], [10, -3.0, -2.0, -2.0, -1.0]], [[18, 1.0, 3.0, 2.0, 4.0], [39, 2.0, 0.0, 4.0, 2.0], [2, 1.0, 1.0, 1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, 2.0, 4.0, 3.0, 7.0], [10, -3.0, -3.0, -2.0, -2.0]]], [[], [[2, 27], [10, 27]], 7]], [[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[29, -4.0, -1.0, -3.0, -1.0], [14, 4.0, -5.0, 6.0, -5.0], [20, 2.0, -4.0, 2.0, -3.0]], [[29, -7.0, 0.0, -6.0, 0.0], [14, 4.0, -4.0, 6.0, -4.0], [20, -1.0, -4.0, -1.0, -3.0]]], [[], [], 0]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[37, 0.0, -3.0, 3.0, -3.0], [2, 3.0, -2.0, 5.0, -2.0], [35, 5.0, 2.0, 7.0, 3.0]], [[37, 2.0, -3.0, 5.0, -3.0], [2, 3.0, -3.0, 5.0, -3.0], [35, 5.0, 3.0, 7.0, 4.0]]], [[], [], 1]], [[[[15, 0.0, 0.0, 2.0, 0.0], [18, 3.0, 0.0, 4.0, 1.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -5.0, -4.0, -5.0, -3.0], [32, 5.0, -3.0, 8.0, -2.0]], [[15, 2.0, -1.0, 4.0, -1.0], [18, 7.0, -1.0, 8.0, 0.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -6.0, -3.0, -6.0, -2.0], [32, 7.0, -2.0, 10.0, -1.0]]], [[[18, 32]], [[15, 30]], 3]], [[[[29, 3.0, 3.0, 3.0, 6.0], [20, 4.0, 4.0, 5.0, 7.0], [7, 3.0, 2.0, 4.0, 4.0], [21, 3.0, -1.0, 5.0, 0.0]], [[29, 3.0, 2.0, 3.0, 5.0], [20, 5.0, 5.0, 6.0, 8.0], [7, 4.0, 3.0, 5.0, 5.0], [21, 2.0, -2.0, 4.0, -1.0]]], [[], [[7, 29], [20, 21]], 6]], [[[[25, 0.0, 3.0, 2.0, 3.0], [27, 0.0, 5.0, 0.0, 5.0], [33, -1.0, -5.0, 1.0, -4.0], [9, -5.0, 4.0, -5.0, 6.0], [21, 3.0, 4.0, 6.0, 6.0], [18, -2.0, -2.0, -2.0, -1.0], [39, -2.0, -3.0, 0.0, 0.0], [20, 3.0, -3.0, 3.0, -3.0], [2, -1.0, 0.0, 2.0, 1.0]], [[25, 0.0, 4.0, 2.0, 4.0], [27, 4.0, 6.0, 4.0, 6.0], [33, 1.0, -5.0, 3.0, -4.0], [9, -5.0, 5.0, -5.0, 7.0], [21, 4.0, 5.0, 7.0, 7.0], [18, -1.0, -2.0, -1.0, -1.0], [39, -5.0, -3.0, -3.0, 0.0], [20, 3.0, -2.0, 3.0, -2.0], [2, 3.0, 0.0, 6.0, 1.0]]], [[[21, 27]], [[2, 25], [2, 39], [18, 39], [20, 21], [20, 27], [25, 27], [25, 39], [27, 33], [27, 39], [33, 39]], 29]], [[[[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -3.0, -1.0, -3.0], [27, 3.0, 5.0, 6.0, 8.0], [30, -3.0, 3.0, 0.0, 6.0], [6, -4.0, -4.0, -4.0, -1.0]], [[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -4.0, -1.0, -4.0], [27, 0.0, 6.0, 3.0, 9.0], [30, -1.0, 4.0, 2.0, 7.0], [6, -7.0, -4.0, -7.0, -1.0]]], [[[27, 30]], [], 4]], [[[[22, 2.0, -1.0, 3.0, -1.0], [14, -2.0, -2.0, -1.0, 0.0], [17, 1.0, -2.0, 2.0, 0.0], [1, 0.0, -2.0, 3.0, -1.0], [16, 2.0, 3.0, 3.0, 4.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 0.0, 3.0, 0.0, 6.0], [3, 3.0, -5.0, 4.0, -5.0], [38, 0.0, 3.0, 0.0, 3.0]], [[22, 2.0, -1.0, 3.0, -1.0], [14, -5.0, -2.0, -4.0, 0.0], [17, 3.0, -1.0, 4.0, 1.0], [1, 1.0, -2.0, 4.0, -1.0], [16, 4.0, 4.0, 5.0, 5.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 2.0, 3.0, 2.0, 6.0], [3, 7.0, -4.0, 8.0, -4.0], [38, 2.0, 3.0, 2.0, 3.0]]], [[[24, 33]], [[1, 3], [3, 16], [3, 22], [3, 33], [16, 22], [16, 33]], 21]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, 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)

Boundary fixture	Actual	Expected	Outcome
case 0	`[[[12, 17]], [[4, 31], [12, 31]], 5]`	`[[], [[4, 31], [12, 31]], 5]`	Failed
case 1	`[[[8, 10], [8, 15], [10, 33], [15, 33]], [], 10]`	`[[], [], 10]`	Failed
case 2	`[[[2, 7], [8, 23], [8, 36]], [[8, 28], [8, 36]], 12]`	`[[[2, 7]], [[8, 28], [8, 36]], 12]`	Failed
case 3	`[[], [], 0]`	`[[], [], 0]`	Passed
case 4	`[[], [], 0]`	`[[], [], 0]`	Passed
case 5	`[[[5, 39]], [], 2]`	`[[], [], 2]`	Failed
case 6	`[[[1, 16]], [[1, 12], [1, 16], [6, 12]], 10]`	`[[], [[1, 12], [1, 16], [6, 12]], 10]`	Failed
case 7	`[[], [], 0]`	`[[], [], 0]`	Passed

SHA-256 / 19fd3ac8807f9adf15e4d4b2731615e97b496788c523888462ea5b1cf8545eb2

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prev, curr):
    old = {b[0]: b for b in prev}
    new = {b[0]: b for b in curr}
    E = []
    for i, b in old.items():
        E.append([b[1], 0, i])
        E.append([b[3], 1, i])
    E.sort()
    for e in E:
        b = new[e[2]]
        e[0] = b[1] if e[1] == 0 else b[3]
    def yover(a, c):
        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]
    begins, ends = set(), set()
    swaps = 0
    for i in range(1, len(E)):
        j = i
        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):
            e, f = E[j], E[j - 1]
            E[j - 1], E[j] = e, f
            swaps += 1
            p = (min(e[2], f[2]), max(e[2], f[2]))
            if e[1] == 0 and f[1] == 1:
                if new[e[2]][2] <= new[f[2]][4]:
                    begins.add(p)
            elif e[1] == 1 and f[1] == 0:
                ends.add(p)
            j -= 1
    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[4, -3.0, 4.0, -3.0, 7.0], [12, -2.0, 0.0, -1.0, 0.0], [31, -3.0, -5.0, 0.0, -2.0], [17, 2.0, -3.0, 2.0, -1.0]], [[4, -4.0, 4.0, -4.0, 7.0], [12, 2.0, 0.0, 3.0, 0.0], [31, -3.0, -6.0, 0.0, -3.0], [17, 2.0, -3.0, 2.0, -1.0]]], [[], [[4, 31], [12, 31]], 5]], [[[[8, -3.0, 4.0, 0.0, 6.0], [15, 2.0, -2.0, 4.0, -2.0], [33, -1.0, 2.0, 0.0, 2.0], [10, 2.0, -3.0, 3.0, -1.0]], [[8, -1.0, 5.0, 2.0, 7.0], [15, -1.0, -2.0, 1.0, -2.0], [33, 0.0, 3.0, 1.0, 3.0], [10, -1.0, -4.0, 0.0, -2.0]]], [[], [], 10]], [[[[36, 4.0, -1.0, 5.0, 2.0], [8, 1.0, 3.0, 1.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 1.0, 4.0, 4.0, 5.0], [2, -5.0, -2.0, -4.0, 0.0], [23, 2.0, 1.0, 4.0, 1.0]], [[36, 3.0, -2.0, 4.0, 1.0], [8, 5.0, 3.0, 5.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 0.0, 3.0, 3.0, 4.0], [2, -3.0, -1.0, -2.0, 1.0], [23, 3.0, 1.0, 5.0, 1.0]]], [[[2, 7]], [[8, 28], [8, 36]], 12]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]], [[[[25, 2.0, 0.0, 5.0, 2.0], [26, -4.0, -3.0, -2.0, 0.0], [3, 4.0, 4.0, 6.0, 6.0], [30, 4.0, 0.0, 6.0, 2.0]], [[25, 3.0, 1.0, 6.0, 3.0], [26, -7.0, -4.0, -5.0, -1.0], [3, 4.0, 5.0, 6.0, 7.0], [30, 6.0, 0.0, 8.0, 2.0]]], [[], [], 0]], [[[[12, 2.0, -4.0, 4.0, -4.0], [39, -2.0, -1.0, 1.0, -1.0], [5, -5.0, 5.0, -5.0, 7.0]], [[12, 2.0, -5.0, 4.0, -5.0], [39, -2.0, 0.0, 1.0, 0.0], [5, -1.0, 5.0, -1.0, 7.0]]], [[], [], 2]], [[[[12, -1.0, 3.0, -1.0, 6.0], [1, -1.0, -4.0, 0.0, -3.0], [16, -3.0, -2.0, -2.0, -1.0], [30, 5.0, -4.0, 8.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]], [[12, 3.0, 3.0, 3.0, 6.0], [1, -1.0, -5.0, 0.0, -4.0], [16, 1.0, -2.0, 2.0, -1.0], [30, 9.0, -4.0, 12.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]]], [[], [[1, 12], [1, 16], [6, 12]], 10]], [[[[36, -1.0, -4.0, 1.0, -4.0], [9, -1.0, -2.0, 0.0, 1.0]], [[36, 1.0, -5.0, 3.0, -5.0], [9, 0.0, -1.0, 1.0, 2.0]]], [[], [], 0]]], [[[[[36, 5.0, -4.0, 6.0, -3.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -5.0, -4.0, -4.0, -2.0], [3, 5.0, 4.0, 5.0, 4.0], [7, 0.0, 0.0, 3.0, 2.0], [28, 0.0, 0.0, 2.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]], [[36, 5.0, -3.0, 6.0, -2.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -4.0, -4.0, -3.0, -2.0], [3, 6.0, 4.0, 6.0, 4.0], [7, 0.0, 1.0, 3.0, 3.0], [28, 4.0, 0.0, 6.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]]], [[], [[6, 28], [7, 28]], 7]], [[[[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 2.0, 2.0, 3.0]], [[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 3.0, 2.0, 4.0]]], [[], [], 0]], [[[[30, -1.0, -5.0, 0.0, -5.0], [20, 4.0, -5.0, 5.0, -4.0], [1, -1.0, -2.0, -1.0, -1.0], [12, -2.0, 1.0, -2.0, 2.0], [22, 1.0, 5.0, 2.0, 7.0]], [[30, -1.0, -6.0, 0.0, -6.0], [20, 3.0, -6.0, 4.0, -5.0], [1, -1.0, -1.0, -1.0, 0.0], [12, 0.0, 0.0, 0.0, 1.0], [22, 0.0, 5.0, 1.0, 7.0]]], [[[1, 12]], [[1, 12]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]], [[[[22, -2.0, 0.0, 1.0, 0.0], [8, -1.0, -2.0, 0.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0], [33, 2.0, 4.0, 4.0, 5.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 1.0, -5.0, 2.0, -4.0], [32, -4.0, 0.0, -1.0, 0.0]], [[22, -5.0, 0.0, -2.0, 0.0], [8, -4.0, -3.0, -3.0, -3.0], [2, 0.0, 0.0, 3.0, 1.0], [33, 2.0, 5.0, 4.0, 6.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 2.0, -4.0, 3.0, -3.0], [32, 0.0, 0.0, 3.0, 0.0]]], [[[2, 32], [9, 37]], [[8, 32], [22, 32], [22, 37]], 16]], [[[[17, -3.0, 5.0, 0.0, 7.0], [29, -3.0, 0.0, -3.0, 1.0], [20, 5.0, -3.0, 8.0, -2.0], [4, 3.0, -5.0, 5.0, -2.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 1.0, -4.0, 4.0, -2.0], [24, 2.0, -2.0, 3.0, 0.0]], [[17, 1.0, 5.0, 4.0, 7.0], [29, -6.0, -1.0, -6.0, 0.0], [20, 5.0, -2.0, 8.0, -1.0], [4, 2.0, -6.0, 4.0, -3.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 0.0, -5.0, 3.0, -3.0], [24, 2.0, -3.0, 3.0, -1.0]]], [[], [[2, 17], [2, 29], [4, 20], [17, 29]], 12]], [[[[30, 4.0, 3.0, 4.0, 3.0], [11, -1.0, 4.0, 1.0, 6.0], [29, -3.0, -3.0, -3.0, 0.0], [18, -1.0, -4.0, 0.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, -1.0, 0.0, -1.0, 3.0]], [[30, 3.0, 3.0, 3.0, 3.0], [11, 3.0, 3.0, 5.0, 5.0], [29, -3.0, -2.0, -3.0, 1.0], [18, 0.0, -4.0, 1.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, 0.0, 0.0, 0.0, 3.0]]], [[[11, 30]], [[11, 18], [11, 21], [11, 31]], 11]], [[[[26, -5.0, 4.0, -4.0, 6.0], [30, -2.0, 0.0, 0.0, 3.0], [39, -5.0, -2.0, -2.0, -2.0]], [[26, -1.0, 4.0, 0.0, 6.0], [30, -2.0, -1.0, 0.0, 2.0], [39, -8.0, -1.0, -5.0, -1.0]]], [[], [[26, 39], [30, 39]], 6]]], [[[[[8, -4.0, 4.0, -2.0, 4.0], [32, 2.0, -2.0, 4.0, -1.0], [1, -2.0, -1.0, -1.0, 0.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 4.0, -2.0, 7.0], [11, -4.0, -5.0, -3.0, -2.0], [12, 2.0, -2.0, 4.0, 1.0]], [[8, -3.0, 3.0, -1.0, 3.0], [32, -1.0, -3.0, 1.0, -2.0], [1, -5.0, 0.0, -4.0, 1.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 3.0, -2.0, 6.0], [11, -4.0, -6.0, -3.0, -3.0], [12, 3.0, -3.0, 5.0, 0.0]]], [[], [[1, 8], [12, 32]], 16]], [[[[17, -5.0, 4.0, -2.0, 6.0], [5, -2.0, -5.0, -1.0, -3.0], [22, -1.0, 0.0, 0.0, 2.0], [1, -3.0, 1.0, 0.0, 2.0], [12, -3.0, 1.0, -1.0, 4.0], [33, 3.0, 2.0, 4.0, 5.0], [19, -5.0, 5.0, -2.0, 7.0]], [[17, -3.0, 4.0, 0.0, 6.0], [5, -1.0, -4.0, 0.0, -2.0], [22, -4.0, -1.0, -3.0, 1.0], [1, -2.0, 1.0, 1.0, 2.0], [12, -3.0, 0.0, -1.0, 3.0], [33, 5.0, 3.0, 6.0, 6.0], [19, -5.0, 5.0, -2.0, 7.0]]], [[], [[1, 22], [5, 19], [5, 22]], 19]], [[[[8, 5.0, 2.0, 8.0, 5.0], [13, 2.0, -4.0, 3.0, -1.0]], [[8, 2.0, 3.0, 5.0, 6.0], [13, 1.0, -4.0, 2.0, -1.0]]], [[], [], 1]], [[[[3, -1.0, -1.0, 2.0, 2.0], [10, -5.0, -3.0, -5.0, -1.0]], [[3, -2.0, -1.0, 1.0, 2.0], [10, -4.0, -4.0, -4.0, -2.0]]], [[], [], 0]], [[[[8, 4.0, 5.0, 4.0, 5.0], [25, 2.0, -5.0, 5.0, -3.0], [26, 3.0, 5.0, 6.0, 7.0], [35, -5.0, 2.0, -3.0, 4.0], [22, 4.0, -4.0, 6.0, -3.0], [5, -5.0, -4.0, -3.0, -4.0]], [[8, 4.0, 5.0, 4.0, 5.0], [25, 3.0, -5.0, 6.0, -3.0], [26, 4.0, 6.0, 7.0, 8.0], [35, -5.0, 1.0, -3.0, 3.0], [22, 3.0, -4.0, 5.0, -3.0], [5, -6.0, -4.0, -4.0, -4.0]]], [[], [], 3]], [[[[22, 0.0, 3.0, 1.0, 4.0], [36, 3.0, -5.0, 3.0, -2.0]], [[22, 0.0, 3.0, 1.0, 4.0], [36, 0.0, -5.0, 0.0, -2.0]]], [[], [], 2]], [[[[29, 4.0, 4.0, 6.0, 5.0], [28, 4.0, 5.0, 6.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -2.0, 2.0, -2.0, 3.0], [25, -2.0, 2.0, 0.0, 4.0], [6, -3.0, 1.0, -1.0, 3.0], [35, -4.0, 4.0, -3.0, 7.0]], [[29, 8.0, 4.0, 10.0, 5.0], [28, 5.0, 5.0, 7.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -5.0, 3.0, -5.0, 4.0], [25, -1.0, 2.0, 1.0, 4.0], [6, 1.0, 1.0, 3.0, 3.0], [35, -2.0, 4.0, -1.0, 7.0]]], [[[20, 35], [25, 35]], [[6, 20], [6, 35], [20, 25], [20, 35], [28, 29]], 13]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]]], [[[[[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 5.0, -5.0, 7.0, -3.0]], [[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 6.0, -5.0, 8.0, -3.0]]], [[], [], 0]], [[[[17, 5.0, -3.0, 5.0, -1.0], [13, -5.0, 3.0, -2.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 3.0, 5.0, 6.0, 7.0], [7, -1.0, -2.0, 1.0, 1.0], [10, 4.0, 3.0, 7.0, 6.0], [1, 4.0, -5.0, 5.0, -2.0], [3, -3.0, -5.0, -1.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]], [[17, 6.0, -3.0, 6.0, -1.0], [13, -4.0, 3.0, -1.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 4.0, 4.0, 7.0, 6.0], [7, -2.0, -2.0, 0.0, 1.0], [10, 4.0, 4.0, 7.0, 7.0], [1, 4.0, -6.0, 5.0, -3.0], [3, -4.0, -5.0, -2.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]]], [[], [[1, 17], [13, 28]], 5]], [[[[24, 2.0, -2.0, 3.0, -2.0], [2, 0.0, -4.0, 1.0, -4.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 3.0, -5.0, 5.0, -4.0], [10, 3.0, 3.0, 6.0, 4.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 3.0, -2.0, 6.0, -2.0]], [[24, -1.0, -2.0, 0.0, -2.0], [2, 0.0, -5.0, 1.0, -5.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 4.0, -5.0, 6.0, -4.0], [10, 3.0, 2.0, 6.0, 3.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 0.0, -2.0, 3.0, -2.0]]], [[[22, 24]], [[4, 20], [10, 24], [20, 24]], 9]], [[[[6, 0.0, -2.0, 0.0, -2.0], [11, -2.0, 0.0, -2.0, 3.0], [39, 4.0, 0.0, 7.0, 3.0]], [[6, 1.0, -2.0, 1.0, -2.0], [11, 2.0, 1.0, 2.0, 4.0], [39, 4.0, 0.0, 7.0, 3.0]]], [[], [[6, 11]], 4]], [[[[18, -1.0, 3.0, 0.0, 4.0], [39, 5.0, 0.0, 7.0, 2.0], [2, -1.0, 1.0, -1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, -2.0, 3.0, -1.0, 6.0], [10, -3.0, -2.0, -2.0, -1.0]], [[18, 1.0, 3.0, 2.0, 4.0], [39, 2.0, 0.0, 4.0, 2.0], [2, 1.0, 1.0, 1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, 2.0, 4.0, 3.0, 7.0], [10, -3.0, -3.0, -2.0, -2.0]]], [[], [[2, 27], [10, 27]], 7]], [[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[29, -4.0, -1.0, -3.0, -1.0], [14, 4.0, -5.0, 6.0, -5.0], [20, 2.0, -4.0, 2.0, -3.0]], [[29, -7.0, 0.0, -6.0, 0.0], [14, 4.0, -4.0, 6.0, -4.0], [20, -1.0, -4.0, -1.0, -3.0]]], [[], [], 0]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[37, 0.0, -3.0, 3.0, -3.0], [2, 3.0, -2.0, 5.0, -2.0], [35, 5.0, 2.0, 7.0, 3.0]], [[37, 2.0, -3.0, 5.0, -3.0], [2, 3.0, -3.0, 5.0, -3.0], [35, 5.0, 3.0, 7.0, 4.0]]], [[], [], 1]], [[[[15, 0.0, 0.0, 2.0, 0.0], [18, 3.0, 0.0, 4.0, 1.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -5.0, -4.0, -5.0, -3.0], [32, 5.0, -3.0, 8.0, -2.0]], [[15, 2.0, -1.0, 4.0, -1.0], [18, 7.0, -1.0, 8.0, 0.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -6.0, -3.0, -6.0, -2.0], [32, 7.0, -2.0, 10.0, -1.0]]], [[[18, 32]], [[15, 30]], 3]], [[[[29, 3.0, 3.0, 3.0, 6.0], [20, 4.0, 4.0, 5.0, 7.0], [7, 3.0, 2.0, 4.0, 4.0], [21, 3.0, -1.0, 5.0, 0.0]], [[29, 3.0, 2.0, 3.0, 5.0], [20, 5.0, 5.0, 6.0, 8.0], [7, 4.0, 3.0, 5.0, 5.0], [21, 2.0, -2.0, 4.0, -1.0]]], [[], [[7, 29], [20, 21]], 6]], [[[[25, 0.0, 3.0, 2.0, 3.0], [27, 0.0, 5.0, 0.0, 5.0], [33, -1.0, -5.0, 1.0, -4.0], [9, -5.0, 4.0, -5.0, 6.0], [21, 3.0, 4.0, 6.0, 6.0], [18, -2.0, -2.0, -2.0, -1.0], [39, -2.0, -3.0, 0.0, 0.0], [20, 3.0, -3.0, 3.0, -3.0], [2, -1.0, 0.0, 2.0, 1.0]], [[25, 0.0, 4.0, 2.0, 4.0], [27, 4.0, 6.0, 4.0, 6.0], [33, 1.0, -5.0, 3.0, -4.0], [9, -5.0, 5.0, -5.0, 7.0], [21, 4.0, 5.0, 7.0, 7.0], [18, -1.0, -2.0, -1.0, -1.0], [39, -5.0, -3.0, -3.0, 0.0], [20, 3.0, -2.0, 3.0, -2.0], [2, 3.0, 0.0, 6.0, 1.0]]], [[[21, 27]], [[2, 25], [2, 39], [18, 39], [20, 21], [20, 27], [25, 27], [25, 39], [27, 33], [27, 39], [33, 39]], 29]], [[[[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -3.0, -1.0, -3.0], [27, 3.0, 5.0, 6.0, 8.0], [30, -3.0, 3.0, 0.0, 6.0], [6, -4.0, -4.0, -4.0, -1.0]], [[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -4.0, -1.0, -4.0], [27, 0.0, 6.0, 3.0, 9.0], [30, -1.0, 4.0, 2.0, 7.0], [6, -7.0, -4.0, -7.0, -1.0]]], [[[27, 30]], [], 4]], [[[[22, 2.0, -1.0, 3.0, -1.0], [14, -2.0, -2.0, -1.0, 0.0], [17, 1.0, -2.0, 2.0, 0.0], [1, 0.0, -2.0, 3.0, -1.0], [16, 2.0, 3.0, 3.0, 4.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 0.0, 3.0, 0.0, 6.0], [3, 3.0, -5.0, 4.0, -5.0], [38, 0.0, 3.0, 0.0, 3.0]], [[22, 2.0, -1.0, 3.0, -1.0], [14, -5.0, -2.0, -4.0, 0.0], [17, 3.0, -1.0, 4.0, 1.0], [1, 1.0, -2.0, 4.0, -1.0], [16, 4.0, 4.0, 5.0, 5.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 2.0, 3.0, 2.0, 6.0], [3, 7.0, -4.0, 8.0, -4.0], [38, 2.0, 3.0, 2.0, 3.0]]], [[[24, 33]], [[1, 3], [3, 16], [3, 22], [3, 33], [16, 22], [16, 33]], 21]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, 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)

Boundary fixture	Actual	Expected	Outcome
case 0	`[[[12, 17]], [[4, 31], [12, 31]], 5]`	`[[], [[4, 31], [12, 31]], 5]`	Failed
case 1	`[[[8, 10], [8, 15], [10, 33], [15, 33]], [], 10]`	`[[], [], 10]`	Failed
case 2	`[[[2, 7], [8, 23], [8, 36]], [[8, 28], [8, 36]], 12]`	`[[[2, 7]], [[8, 28], [8, 36]], 12]`	Failed
case 3	`[[], [], 0]`	`[[], [], 0]`	Passed
case 4	`[[], [], 0]`	`[[], [], 0]`	Passed
case 5	`[[[5, 39]], [], 2]`	`[[], [], 2]`	Failed
case 6	`[[[1, 16]], [[1, 12], [1, 16], [6, 12]], 10]`	`[[], [[1, 12], [1, 16], [6, 12]], 10]`	Failed
case 7	`[[], [], 0]`	`[[], [], 0]`	Passed

SHA-256 / c764b74c6f8f3fa71036472c897b4d74435951f66e2c5c4e7b06893cb271248c

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prev, curr):
    old = {b[0]: b for b in prev}
    new = {b[0]: b for b in curr}
    E = []
    for i, b in old.items():
        E.append([b[1], 0, i])
        E.append([b[3], 1, i])
    E.sort()
    for e in E:
        b = new[e[2]]
        e[0] = b[1] if e[1] == 0 else b[3]
    def yover(a, c):
        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]
    begins, ends = set(), set()
    swaps = 0
    for i in range(1, len(E)):
        j = i
        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):
            e, f = E[j], E[j - 1]
            E[j - 1], E[j] = e, f
            swaps += 1
            p = (min(e[2], f[2]), max(e[2], f[2]))
            if e[1] == 0 and f[1] == 1:
                if yover(e[2], f[2]):
                    begins.add(p)
            elif e[1] == 1 and f[1] == 0:
                ends.add(p)
            j -= 1
    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[4, -3.0, 4.0, -3.0, 7.0], [12, -2.0, 0.0, -1.0, 0.0], [31, -3.0, -5.0, 0.0, -2.0], [17, 2.0, -3.0, 2.0, -1.0]], [[4, -4.0, 4.0, -4.0, 7.0], [12, 2.0, 0.0, 3.0, 0.0], [31, -3.0, -6.0, 0.0, -3.0], [17, 2.0, -3.0, 2.0, -1.0]]], [[], [[4, 31], [12, 31]], 5]], [[[[8, -3.0, 4.0, 0.0, 6.0], [15, 2.0, -2.0, 4.0, -2.0], [33, -1.0, 2.0, 0.0, 2.0], [10, 2.0, -3.0, 3.0, -1.0]], [[8, -1.0, 5.0, 2.0, 7.0], [15, -1.0, -2.0, 1.0, -2.0], [33, 0.0, 3.0, 1.0, 3.0], [10, -1.0, -4.0, 0.0, -2.0]]], [[], [], 10]], [[[[36, 4.0, -1.0, 5.0, 2.0], [8, 1.0, 3.0, 1.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 1.0, 4.0, 4.0, 5.0], [2, -5.0, -2.0, -4.0, 0.0], [23, 2.0, 1.0, 4.0, 1.0]], [[36, 3.0, -2.0, 4.0, 1.0], [8, 5.0, 3.0, 5.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 0.0, 3.0, 3.0, 4.0], [2, -3.0, -1.0, -2.0, 1.0], [23, 3.0, 1.0, 5.0, 1.0]]], [[[2, 7]], [[8, 28], [8, 36]], 12]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]], [[[[25, 2.0, 0.0, 5.0, 2.0], [26, -4.0, -3.0, -2.0, 0.0], [3, 4.0, 4.0, 6.0, 6.0], [30, 4.0, 0.0, 6.0, 2.0]], [[25, 3.0, 1.0, 6.0, 3.0], [26, -7.0, -4.0, -5.0, -1.0], [3, 4.0, 5.0, 6.0, 7.0], [30, 6.0, 0.0, 8.0, 2.0]]], [[], [], 0]], [[[[12, 2.0, -4.0, 4.0, -4.0], [39, -2.0, -1.0, 1.0, -1.0], [5, -5.0, 5.0, -5.0, 7.0]], [[12, 2.0, -5.0, 4.0, -5.0], [39, -2.0, 0.0, 1.0, 0.0], [5, -1.0, 5.0, -1.0, 7.0]]], [[], [], 2]], [[[[12, -1.0, 3.0, -1.0, 6.0], [1, -1.0, -4.0, 0.0, -3.0], [16, -3.0, -2.0, -2.0, -1.0], [30, 5.0, -4.0, 8.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]], [[12, 3.0, 3.0, 3.0, 6.0], [1, -1.0, -5.0, 0.0, -4.0], [16, 1.0, -2.0, 2.0, -1.0], [30, 9.0, -4.0, 12.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]]], [[], [[1, 12], [1, 16], [6, 12]], 10]], [[[[36, -1.0, -4.0, 1.0, -4.0], [9, -1.0, -2.0, 0.0, 1.0]], [[36, 1.0, -5.0, 3.0, -5.0], [9, 0.0, -1.0, 1.0, 2.0]]], [[], [], 0]]], [[[[[36, 5.0, -4.0, 6.0, -3.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -5.0, -4.0, -4.0, -2.0], [3, 5.0, 4.0, 5.0, 4.0], [7, 0.0, 0.0, 3.0, 2.0], [28, 0.0, 0.0, 2.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]], [[36, 5.0, -3.0, 6.0, -2.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -4.0, -4.0, -3.0, -2.0], [3, 6.0, 4.0, 6.0, 4.0], [7, 0.0, 1.0, 3.0, 3.0], [28, 4.0, 0.0, 6.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]]], [[], [[6, 28], [7, 28]], 7]], [[[[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 2.0, 2.0, 3.0]], [[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 3.0, 2.0, 4.0]]], [[], [], 0]], [[[[30, -1.0, -5.0, 0.0, -5.0], [20, 4.0, -5.0, 5.0, -4.0], [1, -1.0, -2.0, -1.0, -1.0], [12, -2.0, 1.0, -2.0, 2.0], [22, 1.0, 5.0, 2.0, 7.0]], [[30, -1.0, -6.0, 0.0, -6.0], [20, 3.0, -6.0, 4.0, -5.0], [1, -1.0, -1.0, -1.0, 0.0], [12, 0.0, 0.0, 0.0, 1.0], [22, 0.0, 5.0, 1.0, 7.0]]], [[[1, 12]], [[1, 12]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]], [[[[22, -2.0, 0.0, 1.0, 0.0], [8, -1.0, -2.0, 0.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0], [33, 2.0, 4.0, 4.0, 5.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 1.0, -5.0, 2.0, -4.0], [32, -4.0, 0.0, -1.0, 0.0]], [[22, -5.0, 0.0, -2.0, 0.0], [8, -4.0, -3.0, -3.0, -3.0], [2, 0.0, 0.0, 3.0, 1.0], [33, 2.0, 5.0, 4.0, 6.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 2.0, -4.0, 3.0, -3.0], [32, 0.0, 0.0, 3.0, 0.0]]], [[[2, 32], [9, 37]], [[8, 32], [22, 32], [22, 37]], 16]], [[[[17, -3.0, 5.0, 0.0, 7.0], [29, -3.0, 0.0, -3.0, 1.0], [20, 5.0, -3.0, 8.0, -2.0], [4, 3.0, -5.0, 5.0, -2.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 1.0, -4.0, 4.0, -2.0], [24, 2.0, -2.0, 3.0, 0.0]], [[17, 1.0, 5.0, 4.0, 7.0], [29, -6.0, -1.0, -6.0, 0.0], [20, 5.0, -2.0, 8.0, -1.0], [4, 2.0, -6.0, 4.0, -3.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 0.0, -5.0, 3.0, -3.0], [24, 2.0, -3.0, 3.0, -1.0]]], [[], [[2, 17], [2, 29], [4, 20], [17, 29]], 12]], [[[[30, 4.0, 3.0, 4.0, 3.0], [11, -1.0, 4.0, 1.0, 6.0], [29, -3.0, -3.0, -3.0, 0.0], [18, -1.0, -4.0, 0.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, -1.0, 0.0, -1.0, 3.0]], [[30, 3.0, 3.0, 3.0, 3.0], [11, 3.0, 3.0, 5.0, 5.0], [29, -3.0, -2.0, -3.0, 1.0], [18, 0.0, -4.0, 1.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, 0.0, 0.0, 0.0, 3.0]]], [[[11, 30]], [[11, 18], [11, 21], [11, 31]], 11]], [[[[26, -5.0, 4.0, -4.0, 6.0], [30, -2.0, 0.0, 0.0, 3.0], [39, -5.0, -2.0, -2.0, -2.0]], [[26, -1.0, 4.0, 0.0, 6.0], [30, -2.0, -1.0, 0.0, 2.0], [39, -8.0, -1.0, -5.0, -1.0]]], [[], [[26, 39], [30, 39]], 6]]], [[[[[8, -4.0, 4.0, -2.0, 4.0], [32, 2.0, -2.0, 4.0, -1.0], [1, -2.0, -1.0, -1.0, 0.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 4.0, -2.0, 7.0], [11, -4.0, -5.0, -3.0, -2.0], [12, 2.0, -2.0, 4.0, 1.0]], [[8, -3.0, 3.0, -1.0, 3.0], [32, -1.0, -3.0, 1.0, -2.0], [1, -5.0, 0.0, -4.0, 1.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 3.0, -2.0, 6.0], [11, -4.0, -6.0, -3.0, -3.0], [12, 3.0, -3.0, 5.0, 0.0]]], [[], [[1, 8], [12, 32]], 16]], [[[[17, -5.0, 4.0, -2.0, 6.0], [5, -2.0, -5.0, -1.0, -3.0], [22, -1.0, 0.0, 0.0, 2.0], [1, -3.0, 1.0, 0.0, 2.0], [12, -3.0, 1.0, -1.0, 4.0], [33, 3.0, 2.0, 4.0, 5.0], [19, -5.0, 5.0, -2.0, 7.0]], [[17, -3.0, 4.0, 0.0, 6.0], [5, -1.0, -4.0, 0.0, -2.0], [22, -4.0, -1.0, -3.0, 1.0], [1, -2.0, 1.0, 1.0, 2.0], [12, -3.0, 0.0, -1.0, 3.0], [33, 5.0, 3.0, 6.0, 6.0], [19, -5.0, 5.0, -2.0, 7.0]]], [[], [[1, 22], [5, 19], [5, 22]], 19]], [[[[8, 5.0, 2.0, 8.0, 5.0], [13, 2.0, -4.0, 3.0, -1.0]], [[8, 2.0, 3.0, 5.0, 6.0], [13, 1.0, -4.0, 2.0, -1.0]]], [[], [], 1]], [[[[3, -1.0, -1.0, 2.0, 2.0], [10, -5.0, -3.0, -5.0, -1.0]], [[3, -2.0, -1.0, 1.0, 2.0], [10, -4.0, -4.0, -4.0, -2.0]]], [[], [], 0]], [[[[8, 4.0, 5.0, 4.0, 5.0], [25, 2.0, -5.0, 5.0, -3.0], [26, 3.0, 5.0, 6.0, 7.0], [35, -5.0, 2.0, -3.0, 4.0], [22, 4.0, -4.0, 6.0, -3.0], [5, -5.0, -4.0, -3.0, -4.0]], [[8, 4.0, 5.0, 4.0, 5.0], [25, 3.0, -5.0, 6.0, -3.0], [26, 4.0, 6.0, 7.0, 8.0], [35, -5.0, 1.0, -3.0, 3.0], [22, 3.0, -4.0, 5.0, -3.0], [5, -6.0, -4.0, -4.0, -4.0]]], [[], [], 3]], [[[[22, 0.0, 3.0, 1.0, 4.0], [36, 3.0, -5.0, 3.0, -2.0]], [[22, 0.0, 3.0, 1.0, 4.0], [36, 0.0, -5.0, 0.0, -2.0]]], [[], [], 2]], [[[[29, 4.0, 4.0, 6.0, 5.0], [28, 4.0, 5.0, 6.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -2.0, 2.0, -2.0, 3.0], [25, -2.0, 2.0, 0.0, 4.0], [6, -3.0, 1.0, -1.0, 3.0], [35, -4.0, 4.0, -3.0, 7.0]], [[29, 8.0, 4.0, 10.0, 5.0], [28, 5.0, 5.0, 7.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -5.0, 3.0, -5.0, 4.0], [25, -1.0, 2.0, 1.0, 4.0], [6, 1.0, 1.0, 3.0, 3.0], [35, -2.0, 4.0, -1.0, 7.0]]], [[[20, 35], [25, 35]], [[6, 20], [6, 35], [20, 25], [20, 35], [28, 29]], 13]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]]], [[[[[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 5.0, -5.0, 7.0, -3.0]], [[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 6.0, -5.0, 8.0, -3.0]]], [[], [], 0]], [[[[17, 5.0, -3.0, 5.0, -1.0], [13, -5.0, 3.0, -2.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 3.0, 5.0, 6.0, 7.0], [7, -1.0, -2.0, 1.0, 1.0], [10, 4.0, 3.0, 7.0, 6.0], [1, 4.0, -5.0, 5.0, -2.0], [3, -3.0, -5.0, -1.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]], [[17, 6.0, -3.0, 6.0, -1.0], [13, -4.0, 3.0, -1.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 4.0, 4.0, 7.0, 6.0], [7, -2.0, -2.0, 0.0, 1.0], [10, 4.0, 4.0, 7.0, 7.0], [1, 4.0, -6.0, 5.0, -3.0], [3, -4.0, -5.0, -2.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]]], [[], [[1, 17], [13, 28]], 5]], [[[[24, 2.0, -2.0, 3.0, -2.0], [2, 0.0, -4.0, 1.0, -4.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 3.0, -5.0, 5.0, -4.0], [10, 3.0, 3.0, 6.0, 4.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 3.0, -2.0, 6.0, -2.0]], [[24, -1.0, -2.0, 0.0, -2.0], [2, 0.0, -5.0, 1.0, -5.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 4.0, -5.0, 6.0, -4.0], [10, 3.0, 2.0, 6.0, 3.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 0.0, -2.0, 3.0, -2.0]]], [[[22, 24]], [[4, 20], [10, 24], [20, 24]], 9]], [[[[6, 0.0, -2.0, 0.0, -2.0], [11, -2.0, 0.0, -2.0, 3.0], [39, 4.0, 0.0, 7.0, 3.0]], [[6, 1.0, -2.0, 1.0, -2.0], [11, 2.0, 1.0, 2.0, 4.0], [39, 4.0, 0.0, 7.0, 3.0]]], [[], [[6, 11]], 4]], [[[[18, -1.0, 3.0, 0.0, 4.0], [39, 5.0, 0.0, 7.0, 2.0], [2, -1.0, 1.0, -1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, -2.0, 3.0, -1.0, 6.0], [10, -3.0, -2.0, -2.0, -1.0]], [[18, 1.0, 3.0, 2.0, 4.0], [39, 2.0, 0.0, 4.0, 2.0], [2, 1.0, 1.0, 1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, 2.0, 4.0, 3.0, 7.0], [10, -3.0, -3.0, -2.0, -2.0]]], [[], [[2, 27], [10, 27]], 7]], [[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[29, -4.0, -1.0, -3.0, -1.0], [14, 4.0, -5.0, 6.0, -5.0], [20, 2.0, -4.0, 2.0, -3.0]], [[29, -7.0, 0.0, -6.0, 0.0], [14, 4.0, -4.0, 6.0, -4.0], [20, -1.0, -4.0, -1.0, -3.0]]], [[], [], 0]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[37, 0.0, -3.0, 3.0, -3.0], [2, 3.0, -2.0, 5.0, -2.0], [35, 5.0, 2.0, 7.0, 3.0]], [[37, 2.0, -3.0, 5.0, -3.0], [2, 3.0, -3.0, 5.0, -3.0], [35, 5.0, 3.0, 7.0, 4.0]]], [[], [], 1]], [[[[15, 0.0, 0.0, 2.0, 0.0], [18, 3.0, 0.0, 4.0, 1.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -5.0, -4.0, -5.0, -3.0], [32, 5.0, -3.0, 8.0, -2.0]], [[15, 2.0, -1.0, 4.0, -1.0], [18, 7.0, -1.0, 8.0, 0.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -6.0, -3.0, -6.0, -2.0], [32, 7.0, -2.0, 10.0, -1.0]]], [[[18, 32]], [[15, 30]], 3]], [[[[29, 3.0, 3.0, 3.0, 6.0], [20, 4.0, 4.0, 5.0, 7.0], [7, 3.0, 2.0, 4.0, 4.0], [21, 3.0, -1.0, 5.0, 0.0]], [[29, 3.0, 2.0, 3.0, 5.0], [20, 5.0, 5.0, 6.0, 8.0], [7, 4.0, 3.0, 5.0, 5.0], [21, 2.0, -2.0, 4.0, -1.0]]], [[], [[7, 29], [20, 21]], 6]], [[[[25, 0.0, 3.0, 2.0, 3.0], [27, 0.0, 5.0, 0.0, 5.0], [33, -1.0, -5.0, 1.0, -4.0], [9, -5.0, 4.0, -5.0, 6.0], [21, 3.0, 4.0, 6.0, 6.0], [18, -2.0, -2.0, -2.0, -1.0], [39, -2.0, -3.0, 0.0, 0.0], [20, 3.0, -3.0, 3.0, -3.0], [2, -1.0, 0.0, 2.0, 1.0]], [[25, 0.0, 4.0, 2.0, 4.0], [27, 4.0, 6.0, 4.0, 6.0], [33, 1.0, -5.0, 3.0, -4.0], [9, -5.0, 5.0, -5.0, 7.0], [21, 4.0, 5.0, 7.0, 7.0], [18, -1.0, -2.0, -1.0, -1.0], [39, -5.0, -3.0, -3.0, 0.0], [20, 3.0, -2.0, 3.0, -2.0], [2, 3.0, 0.0, 6.0, 1.0]]], [[[21, 27]], [[2, 25], [2, 39], [18, 39], [20, 21], [20, 27], [25, 27], [25, 39], [27, 33], [27, 39], [33, 39]], 29]], [[[[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -3.0, -1.0, -3.0], [27, 3.0, 5.0, 6.0, 8.0], [30, -3.0, 3.0, 0.0, 6.0], [6, -4.0, -4.0, -4.0, -1.0]], [[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -4.0, -1.0, -4.0], [27, 0.0, 6.0, 3.0, 9.0], [30, -1.0, 4.0, 2.0, 7.0], [6, -7.0, -4.0, -7.0, -1.0]]], [[[27, 30]], [], 4]], [[[[22, 2.0, -1.0, 3.0, -1.0], [14, -2.0, -2.0, -1.0, 0.0], [17, 1.0, -2.0, 2.0, 0.0], [1, 0.0, -2.0, 3.0, -1.0], [16, 2.0, 3.0, 3.0, 4.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 0.0, 3.0, 0.0, 6.0], [3, 3.0, -5.0, 4.0, -5.0], [38, 0.0, 3.0, 0.0, 3.0]], [[22, 2.0, -1.0, 3.0, -1.0], [14, -5.0, -2.0, -4.0, 0.0], [17, 3.0, -1.0, 4.0, 1.0], [1, 1.0, -2.0, 4.0, -1.0], [16, 4.0, 4.0, 5.0, 5.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 2.0, 3.0, 2.0, 6.0], [3, 7.0, -4.0, 8.0, -4.0], [38, 2.0, 3.0, 2.0, 3.0]]], [[[24, 33]], [[1, 3], [3, 16], [3, 22], [3, 33], [16, 22], [16, 33]], 21]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, 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)

Boundary fixture	Actual	Expected	Outcome
case 0	`[[], [[4, 31], [12, 31]], 5]`	`[[], [[4, 31], [12, 31]], 5]`	Passed
case 1	`[[], [], 10]`	`[[], [], 10]`	Passed
case 2	`[[[2, 7]], [[8, 28], [8, 36]], 12]`	`[[[2, 7]], [[8, 28], [8, 36]], 12]`	Passed
case 3	`[[], [], 0]`	`[[], [], 0]`	Passed
case 4	`[[], [], 0]`	`[[], [], 0]`	Passed
case 5	`[[], [], 2]`	`[[], [], 2]`	Passed
case 6	`[[], [[1, 12], [1, 16], [6, 12]], 10]`	`[[], [[1, 12], [1, 16], [6, 12]], 10]`	Passed
case 7	`[[], [], 0]`	`[[], [], 0]`	Passed

SHA-256 / 184d00652fff86c61c613a5b6fd57d22250f13ae8d5a684445034a33a8d88883

Verification & scope

A deterministic bounded teaching model with stipulated toy conventions; not a production physics engine or spatial index. 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.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:02.181387+00:00.

Case digest / 7ddeb8bff1a19b191ff94297a71ff190db76c5addffa6438662f0c4d0ad32446