FA-87811 / Collision detection broadphase / Open access

Swap events record pairs in swap orientation · case 01

The same pair appears as both (a,b) and (b,a).

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

ROOT CAUSE

p = (e id, f id).

VERIFIED REPAIR

Normalize to (min,max).

Unsuccessful approach: Using (f id, e id) is equally orientation dependent.

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 = (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 = [[[[[[27, 0.0, -1.0, 1.0, 1.0], [2, -2.0, 3.0, 1.0, 3.0], [10, -3.0, 0.0, 0.0, 0.0], [32, 2.0, -2.0, 2.0, 1.0], [14, -4.0, 4.0, -3.0, 4.0], [21, 5.0, 5.0, 6.0, 6.0]], [[27, 0.0, -1.0, 1.0, 1.0], [2, 2.0, 3.0, 5.0, 3.0], [10, 1.0, 0.0, 4.0, 0.0], [32, 2.0, -3.0, 2.0, 0.0], [14, -3.0, 5.0, -2.0, 5.0], [21, 2.0, 6.0, 3.0, 7.0]]], [[[10, 32]], [[2, 27], [10, 14]], 15]], [[[[20, -5.0, 5.0, -2.0, 6.0], [5, 0.0, 5.0, 3.0, 7.0]], [[20, -1.0, 6.0, 2.0, 7.0], [5, 2.0, 5.0, 5.0, 7.0]]], [[[5, 20]], [], 1]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[5, -2.0, -3.0, -1.0, -3.0], [22, 4.0, -1.0, 6.0, 2.0], [14, -2.0, 3.0, 1.0, 4.0], [8, -4.0, 1.0, -1.0, 3.0], [21, 4.0, 0.0, 4.0, 2.0]], [[5, -2.0, -3.0, -1.0, -3.0], [22, 8.0, -2.0, 10.0, 1.0], [14, -1.0, 3.0, 2.0, 4.0], [8, 0.0, 2.0, 3.0, 4.0], [21, 5.0, 1.0, 5.0, 3.0]]], [[], [[5, 8], [21, 22]], 5]], [[[[30, 2.0, 2.0, 3.0, 2.0], [11, 4.0, -1.0, 4.0, 1.0], [13, 5.0, 4.0, 6.0, 7.0], [4, 3.0, -1.0, 4.0, 1.0]], [[30, 6.0, 1.0, 7.0, 1.0], [11, 8.0, 0.0, 8.0, 2.0], [13, 9.0, 4.0, 10.0, 7.0], [4, 3.0, -2.0, 4.0, 0.0]]], [[], [[4, 11], [4, 30]], 4]], [[[[29, -1.0, -2.0, 2.0, 1.0], [38, 5.0, 1.0, 5.0, 3.0], [28, 3.0, -3.0, 3.0, -2.0], [17, 5.0, 1.0, 8.0, 3.0], [9, -5.0, -2.0, -4.0, 0.0]], [[29, 1.0, -1.0, 4.0, 2.0], [38, 9.0, 1.0, 9.0, 3.0], [28, 2.0, -2.0, 2.0, -1.0], [17, 2.0, 1.0, 5.0, 3.0], [9, -1.0, -1.0, 0.0, 1.0]]], [[[17, 29], [28, 29]], [[17, 38]], 6]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[2, 0.0, 5.0, 3.0, 8.0], [38, 5.0, -5.0, 5.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -4.0, 1.0, -1.0], [29, 3.0, -5.0, 3.0, -3.0]], [[2, -1.0, 4.0, 2.0, 7.0], [38, 4.0, -5.0, 4.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -5.0, 1.0, -2.0], [29, 7.0, -4.0, 7.0, -2.0]]], [[[29, 38]], [[2, 29], [29, 38]], 5]]], [[[[[10, 1.0, -3.0, 3.0, -3.0], [33, 1.0, 0.0, 4.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -3.0, 1.0, -2.0, 3.0]], [[10, 1.0, -3.0, 3.0, -3.0], [33, 2.0, 0.0, 5.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -1.0, 1.0, 0.0, 3.0]]], [[], [[16, 38]], 2]], [[[[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]], [[[[1, -3.0, 0.0, -1.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -5.0, 0.0, -5.0, 0.0], [36, 0.0, 3.0, 0.0, 3.0], [33, -1.0, -4.0, 1.0, -2.0], [32, 4.0, -1.0, 5.0, 1.0]], [[1, -6.0, 0.0, -4.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -1.0, 0.0, -1.0, 0.0], [36, 4.0, 2.0, 4.0, 2.0], [33, -2.0, -3.0, 0.0, -1.0], [32, 4.0, 0.0, 5.0, 2.0]]], [[[1, 23], [32, 36]], [[1, 23], [1, 27], [1, 33], [33, 36]], 13]], [[[[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]], [[[[12, -2.0, 0.0, 0.0, 2.0], [19, 0.0, -5.0, 3.0, -5.0], [10, -1.0, -4.0, 0.0, -2.0], [39, 4.0, -3.0, 7.0, -1.0], [17, -4.0, 1.0, -2.0, 4.0], [28, -2.0, -5.0, -1.0, -3.0], [35, 0.0, 5.0, 3.0, 6.0]], [[12, -1.0, -1.0, 1.0, 1.0], [19, 4.0, -5.0, 7.0, -5.0], [10, 1.0, -3.0, 2.0, -1.0], [39, 3.0, -2.0, 6.0, 0.0], [17, -3.0, 1.0, -1.0, 4.0], [28, -3.0, -5.0, -2.0, -3.0], [35, -3.0, 5.0, 0.0, 6.0]]], [[], [[10, 19], [10, 28], [10, 35], [12, 19], [12, 28], [19, 35]], 20]], [[[[32, 1.0, 5.0, 2.0, 6.0], [6, 0.0, 5.0, 2.0, 5.0], [9, 0.0, -2.0, 3.0, 1.0], [24, -5.0, 0.0, -3.0, 3.0]], [[32, -2.0, 6.0, -1.0, 7.0], [6, 1.0, 4.0, 3.0, 4.0], [9, 4.0, -1.0, 7.0, 2.0], [24, -5.0, 1.0, -3.0, 4.0]]], [[], [[6, 9], [6, 32], [9, 32]], 6]], [[[[23, -4.0, 0.0, -1.0, 1.0], [13, -4.0, -2.0, -4.0, 1.0], [6, -2.0, -5.0, 0.0, -3.0], [8, 5.0, 2.0, 5.0, 3.0], [9, -5.0, 0.0, -4.0, 2.0]], [[23, -7.0, 0.0, -4.0, 1.0], [13, -5.0, -1.0, -5.0, 2.0], [6, 0.0, -5.0, 2.0, -3.0], [8, 5.0, 3.0, 5.0, 4.0], [9, -8.0, 1.0, -7.0, 3.0]]], [[], [[6, 23], [9, 13]], 3]], [[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]]], [[[[[39, 3.0, 1.0, 6.0, 4.0], [22, -5.0, 4.0, -4.0, 7.0], [27, 2.0, -5.0, 5.0, -5.0]], [[39, 3.0, 2.0, 6.0, 5.0], [22, -5.0, 3.0, -4.0, 6.0], [27, 6.0, -4.0, 9.0, -4.0]]], [[], [], 2]], [[[[2, 3.0, -2.0, 4.0, 1.0], [32, 3.0, 5.0, 6.0, 7.0], [14, 1.0, -3.0, 2.0, -3.0], [25, -1.0, -2.0, 2.0, 1.0], [24, -1.0, -2.0, 0.0, 0.0], [29, 5.0, -2.0, 5.0, 0.0]], [[2, 0.0, -2.0, 1.0, 1.0], [32, 4.0, 4.0, 7.0, 6.0], [14, 2.0, -4.0, 3.0, -4.0], [25, 3.0, -2.0, 6.0, 1.0], [24, 1.0, -1.0, 2.0, 1.0], [29, 9.0, -2.0, 9.0, 0.0]]], [[[2, 24], [2, 25]], [[2, 14], [2, 25], [2, 32], [24, 25], [29, 32]], 18]], [[[[26, -5.0, -4.0, -2.0, -2.0], [6, 4.0, 1.0, 5.0, 2.0], [18, -2.0, 2.0, -2.0, 2.0], [24, -4.0, -5.0, -2.0, -3.0], [19, -5.0, -2.0, -4.0, -1.0]], [[26, -6.0, -4.0, -3.0, -2.0], [6, 1.0, 1.0, 2.0, 2.0], [18, -5.0, 2.0, -5.0, 2.0], [24, -5.0, -5.0, -3.0, -3.0], [19, -3.0, -2.0, -2.0, -1.0]]], [[], [[18, 19]], 8]], [[[[18, -4.0, -5.0, -3.0, -4.0], [26, 4.0, -4.0, 6.0, -1.0], [8, -4.0, -4.0, -2.0, -3.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 1.0, -2.0, 4.0, 0.0], [23, 2.0, -5.0, 2.0, -2.0]], [[18, -2.0, -6.0, -1.0, -5.0], [26, 5.0, -4.0, 7.0, -1.0], [8, -2.0, -5.0, 0.0, -4.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 5.0, -3.0, 8.0, -1.0], [23, 1.0, -4.0, 1.0, -1.0]]], [[], [[3, 23]], 5]], [[[[13, 5.0, -2.0, 6.0, 0.0], [39, 4.0, 5.0, 7.0, 7.0], [11, 0.0, 5.0, 3.0, 5.0], [10, 3.0, -4.0, 4.0, -3.0], [18, -2.0, -4.0, -1.0, -2.0], [30, -3.0, -4.0, -1.0, -1.0], [36, 1.0, 1.0, 3.0, 3.0]], [[13, 2.0, -3.0, 3.0, -1.0], [39, 1.0, 5.0, 4.0, 7.0], [11, -3.0, 6.0, 0.0, 6.0], [10, 5.0, -5.0, 6.0, -4.0], [18, -2.0, -3.0, -1.0, -1.0], [30, 1.0, -5.0, 3.0, -2.0], [36, 2.0, 0.0, 4.0, 2.0]]], [[[13, 30]], [[10, 11], [10, 13], [10, 36], [10, 39], [11, 30], [11, 36], [18, 30]], 25]], [[[[20, -2.0, -4.0, 0.0, -4.0], [8, 0.0, -2.0, 0.0, 0.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 1.0, 5.0, 2.0, 7.0], [39, -4.0, 3.0, -4.0, 5.0], [18, -3.0, -5.0, -3.0, -3.0]], [[20, -2.0, -4.0, 0.0, -4.0], [8, -3.0, -1.0, -3.0, 1.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 2.0, 4.0, 3.0, 6.0], [39, -4.0, 4.0, -4.0, 6.0], [18, 1.0, -4.0, 1.0, -2.0]]], [[[2, 18], [18, 20]], [[2, 8], [8, 18], [8, 20], [18, 20]], 14]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -2.0, 0.0, 1.0], [31, 0.0, 1.0, 3.0, 3.0]], [[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -1.0, 0.0, 2.0], [31, 0.0, 2.0, 3.0, 4.0]]], [[], [], 0]]], [[[[[39, 5.0, 0.0, 5.0, 3.0], [11, -4.0, 0.0, -4.0, 1.0], [18, -4.0, 1.0, -3.0, 3.0], [12, -2.0, 5.0, 1.0, 8.0], [36, 3.0, 0.0, 5.0, 0.0]], [[39, 7.0, 0.0, 7.0, 3.0], [11, -3.0, -1.0, -3.0, 0.0], [18, -2.0, 0.0, -1.0, 2.0], [12, -5.0, 5.0, -2.0, 8.0], [36, 5.0, 0.0, 7.0, 0.0]]], [[], [[11, 18]], 6]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[19, -5.0, 4.0, -3.0, 6.0], [29, 2.0, 0.0, 4.0, 0.0], [7, -5.0, 3.0, -4.0, 5.0], [11, 2.0, 3.0, 5.0, 3.0]], [[19, -3.0, 4.0, -1.0, 6.0], [29, -1.0, 1.0, 1.0, 1.0], [7, -1.0, 3.0, 0.0, 5.0], [11, 1.0, 3.0, 4.0, 3.0]]], [[], [], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]], [[[[1, 5.0, -4.0, 6.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]], [[1, 2.0, -4.0, 3.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]]], [[], [], 1]], [[[[38, 1.0, 3.0, 4.0, 6.0], [31, -2.0, -3.0, 1.0, -3.0], [37, 0.0, 1.0, 0.0, 3.0], [9, -5.0, 3.0, -5.0, 4.0], [4, -5.0, 4.0, -4.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 5.0, -2.0, 5.0]], [[38, 1.0, 2.0, 4.0, 5.0], [31, -3.0, -3.0, 0.0, -3.0], [37, 4.0, 2.0, 4.0, 4.0], [9, -6.0, 2.0, -6.0, 3.0], [4, -3.0, 4.0, -2.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 6.0, -2.0, 6.0]]], [[[4, 35], [37, 38]], [[4, 9], [14, 37], [31, 37], [31, 38]], 10]], [[[[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]], [[[[38, 0.0, 0.0, 1.0, 2.0], [20, -3.0, 5.0, -2.0, 7.0], [35, 2.0, 0.0, 5.0, 0.0], [39, 0.0, 1.0, 3.0, 1.0], [7, -4.0, -1.0, -2.0, 1.0], [19, 5.0, -3.0, 5.0, -1.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -5.0, 3.0, -4.0, 4.0]], [[38, 4.0, 0.0, 5.0, 2.0], [20, -6.0, 6.0, -5.0, 8.0], [35, -1.0, 1.0, 2.0, 1.0], [39, 0.0, 2.0, 3.0, 2.0], [7, -7.0, -1.0, -5.0, 1.0], [19, 4.0, -4.0, 4.0, -2.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -3.0, 4.0, -2.0, 5.0]]], [[[35, 38]], [[7, 21], [7, 26], [19, 35], [20, 21], [20, 26], [35, 38], [38, 39]], 24]]], [[[[[7, -2.0, 5.0, -2.0, 5.0], [15, 0.0, 1.0, 1.0, 1.0], [5, 4.0, -5.0, 5.0, -4.0], [2, 0.0, -2.0, 0.0, -1.0], [11, 4.0, 3.0, 6.0, 3.0], [34, -1.0, 5.0, -1.0, 6.0], [20, -1.0, -1.0, 2.0, 0.0]], [[7, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 1.0, 0.0, 1.0], [5, 6.0, -6.0, 7.0, -5.0], [2, 2.0, -2.0, 2.0, -1.0], [11, 1.0, 2.0, 3.0, 2.0], [34, -4.0, 6.0, -4.0, 7.0], [20, -1.0, 0.0, 2.0, 1.0]]], [[], [[2, 15], [5, 11], [7, 34], [20, 34]], 15]], [[[[37, -1.0, 5.0, 0.0, 5.0], [38, -1.0, 4.0, 1.0, 7.0], [32, 4.0, -4.0, 5.0, -2.0], [31, -5.0, -2.0, -4.0, -1.0], [13, 4.0, 1.0, 5.0, 3.0]], [[37, -1.0, 5.0, 0.0, 5.0], [38, 0.0, 3.0, 2.0, 6.0], [32, 8.0, -3.0, 9.0, -1.0], [31, -1.0, -3.0, 0.0, -2.0], [13, 4.0, 2.0, 5.0, 4.0]]], [[], [[13, 32]], 3]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[34, 4.0, -3.0, 5.0, -2.0], [39, -5.0, 2.0, -5.0, 5.0]], [[34, 1.0, -3.0, 2.0, -2.0], [39, -5.0, 1.0, -5.0, 4.0]]], [[], [], 0]], [[[[15, -1.0, -1.0, 2.0, 0.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 5.0, 3.0, 7.0, 5.0], [30, 1.0, 1.0, 2.0, 3.0], [26, -3.0, -3.0, -2.0, -1.0], [21, -1.0, 3.0, 0.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]], [[15, 1.0, -2.0, 4.0, -1.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 4.0, 3.0, 6.0, 5.0], [30, 3.0, 1.0, 4.0, 3.0], [26, -3.0, -4.0, -2.0, -2.0], [21, 1.0, 3.0, 2.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]]], [[[4, 30], [13, 15], [13, 30]], [[6, 30]], 7]], [[[[13, 2.0, 3.0, 5.0, 3.0], [8, 0.0, 5.0, 0.0, 8.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 2.0, 1.0, 2.0, 3.0]], [[13, 2.0, 2.0, 5.0, 2.0], [8, 1.0, 4.0, 1.0, 7.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 6.0, 2.0, 6.0, 4.0]]], [[], [[13, 15]], 3]], [[[[15, 4.0, 1.0, 5.0, 1.0], [23, 0.0, 5.0, 2.0, 5.0], [18, -5.0, 4.0, -2.0, 5.0], [39, -3.0, 0.0, -2.0, 2.0], [4, -1.0, 4.0, 2.0, 5.0], [7, 3.0, 1.0, 4.0, 2.0], [16, -3.0, -3.0, -2.0, 0.0]], [[15, 4.0, 0.0, 5.0, 0.0], [23, 2.0, 5.0, 4.0, 5.0], [18, -6.0, 4.0, -3.0, 5.0], [39, 1.0, -1.0, 2.0, 1.0], [4, -1.0, 3.0, 2.0, 4.0], [7, 0.0, 1.0, 1.0, 2.0], [16, -6.0, -3.0, -5.0, 0.0]]], [[[7, 39]], [[7, 15], [7, 23], [16, 39], [18, 39]], 16]], [[[[15, -4.0, 0.0, -4.0, 1.0], [38, 5.0, 5.0, 6.0, 8.0], [35, -5.0, 1.0, -2.0, 2.0], [22, -3.0, 4.0, 0.0, 7.0], [3, 2.0, 0.0, 2.0, 0.0], [32, 3.0, 5.0, 4.0, 8.0], [11, 0.0, 0.0, 3.0, 1.0], [24, 4.0, 0.0, 4.0, 2.0]], [[15, 0.0, 0.0, 0.0, 1.0], [38, 5.0, 6.0, 6.0, 9.0], [35, -3.0, 1.0, 0.0, 2.0], [22, 1.0, 4.0, 4.0, 7.0], [3, 3.0, 0.0, 3.0, 0.0], [32, 2.0, 5.0, 3.0, 8.0], [11, 0.0, -1.0, 3.0, 0.0], [24, 1.0, 0.0, 1.0, 2.0]]], [[[3, 24], [11, 15], [11, 24], [22, 32]], [[3, 24], [22, 35], [24, 32]], 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	`[[[32, 10]], [[14, 10], [27, 2]], 15]`	`[[[10, 32]], [[2, 27], [10, 14]], 15]`	Failed
case 1	`[[[5, 20]], [], 1]`	`[[[5, 20]], [], 1]`	Passed
case 2	`[[], [[35, 4]], 3]`	`[[], [[4, 35]], 3]`	Failed
case 3	`[[], [[5, 8], [21, 22]], 5]`	`[[], [[5, 8], [21, 22]], 5]`	Passed
case 4	`[[], [[4, 11], [4, 30]], 4]`	`[[], [[4, 11], [4, 30]], 4]`	Passed
case 5	`[[[17, 29], [28, 29]], [[17, 38]], 6]`	`[[[17, 29], [28, 29]], [[17, 38]], 6]`	Passed
case 6	`[[], [[5, 12], [5, 33]], 5]`	`[[], [[5, 12], [5, 33]], 5]`	Passed
case 7	`[[[38, 29]], [[2, 29], [38, 29]], 5]`	`[[[29, 38]], [[2, 29], [29, 38]], 5]`	Failed

SHA-256 / 3dfe65eef419b8e9570569e1bf46b858d9810384e500c2b4f5ea758bb0a550c0

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 = (f[2], e[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 = [[[[[[27, 0.0, -1.0, 1.0, 1.0], [2, -2.0, 3.0, 1.0, 3.0], [10, -3.0, 0.0, 0.0, 0.0], [32, 2.0, -2.0, 2.0, 1.0], [14, -4.0, 4.0, -3.0, 4.0], [21, 5.0, 5.0, 6.0, 6.0]], [[27, 0.0, -1.0, 1.0, 1.0], [2, 2.0, 3.0, 5.0, 3.0], [10, 1.0, 0.0, 4.0, 0.0], [32, 2.0, -3.0, 2.0, 0.0], [14, -3.0, 5.0, -2.0, 5.0], [21, 2.0, 6.0, 3.0, 7.0]]], [[[10, 32]], [[2, 27], [10, 14]], 15]], [[[[20, -5.0, 5.0, -2.0, 6.0], [5, 0.0, 5.0, 3.0, 7.0]], [[20, -1.0, 6.0, 2.0, 7.0], [5, 2.0, 5.0, 5.0, 7.0]]], [[[5, 20]], [], 1]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[5, -2.0, -3.0, -1.0, -3.0], [22, 4.0, -1.0, 6.0, 2.0], [14, -2.0, 3.0, 1.0, 4.0], [8, -4.0, 1.0, -1.0, 3.0], [21, 4.0, 0.0, 4.0, 2.0]], [[5, -2.0, -3.0, -1.0, -3.0], [22, 8.0, -2.0, 10.0, 1.0], [14, -1.0, 3.0, 2.0, 4.0], [8, 0.0, 2.0, 3.0, 4.0], [21, 5.0, 1.0, 5.0, 3.0]]], [[], [[5, 8], [21, 22]], 5]], [[[[30, 2.0, 2.0, 3.0, 2.0], [11, 4.0, -1.0, 4.0, 1.0], [13, 5.0, 4.0, 6.0, 7.0], [4, 3.0, -1.0, 4.0, 1.0]], [[30, 6.0, 1.0, 7.0, 1.0], [11, 8.0, 0.0, 8.0, 2.0], [13, 9.0, 4.0, 10.0, 7.0], [4, 3.0, -2.0, 4.0, 0.0]]], [[], [[4, 11], [4, 30]], 4]], [[[[29, -1.0, -2.0, 2.0, 1.0], [38, 5.0, 1.0, 5.0, 3.0], [28, 3.0, -3.0, 3.0, -2.0], [17, 5.0, 1.0, 8.0, 3.0], [9, -5.0, -2.0, -4.0, 0.0]], [[29, 1.0, -1.0, 4.0, 2.0], [38, 9.0, 1.0, 9.0, 3.0], [28, 2.0, -2.0, 2.0, -1.0], [17, 2.0, 1.0, 5.0, 3.0], [9, -1.0, -1.0, 0.0, 1.0]]], [[[17, 29], [28, 29]], [[17, 38]], 6]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[2, 0.0, 5.0, 3.0, 8.0], [38, 5.0, -5.0, 5.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -4.0, 1.0, -1.0], [29, 3.0, -5.0, 3.0, -3.0]], [[2, -1.0, 4.0, 2.0, 7.0], [38, 4.0, -5.0, 4.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -5.0, 1.0, -2.0], [29, 7.0, -4.0, 7.0, -2.0]]], [[[29, 38]], [[2, 29], [29, 38]], 5]]], [[[[[10, 1.0, -3.0, 3.0, -3.0], [33, 1.0, 0.0, 4.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -3.0, 1.0, -2.0, 3.0]], [[10, 1.0, -3.0, 3.0, -3.0], [33, 2.0, 0.0, 5.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -1.0, 1.0, 0.0, 3.0]]], [[], [[16, 38]], 2]], [[[[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]], [[[[1, -3.0, 0.0, -1.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -5.0, 0.0, -5.0, 0.0], [36, 0.0, 3.0, 0.0, 3.0], [33, -1.0, -4.0, 1.0, -2.0], [32, 4.0, -1.0, 5.0, 1.0]], [[1, -6.0, 0.0, -4.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -1.0, 0.0, -1.0, 0.0], [36, 4.0, 2.0, 4.0, 2.0], [33, -2.0, -3.0, 0.0, -1.0], [32, 4.0, 0.0, 5.0, 2.0]]], [[[1, 23], [32, 36]], [[1, 23], [1, 27], [1, 33], [33, 36]], 13]], [[[[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]], [[[[12, -2.0, 0.0, 0.0, 2.0], [19, 0.0, -5.0, 3.0, -5.0], [10, -1.0, -4.0, 0.0, -2.0], [39, 4.0, -3.0, 7.0, -1.0], [17, -4.0, 1.0, -2.0, 4.0], [28, -2.0, -5.0, -1.0, -3.0], [35, 0.0, 5.0, 3.0, 6.0]], [[12, -1.0, -1.0, 1.0, 1.0], [19, 4.0, -5.0, 7.0, -5.0], [10, 1.0, -3.0, 2.0, -1.0], [39, 3.0, -2.0, 6.0, 0.0], [17, -3.0, 1.0, -1.0, 4.0], [28, -3.0, -5.0, -2.0, -3.0], [35, -3.0, 5.0, 0.0, 6.0]]], [[], [[10, 19], [10, 28], [10, 35], [12, 19], [12, 28], [19, 35]], 20]], [[[[32, 1.0, 5.0, 2.0, 6.0], [6, 0.0, 5.0, 2.0, 5.0], [9, 0.0, -2.0, 3.0, 1.0], [24, -5.0, 0.0, -3.0, 3.0]], [[32, -2.0, 6.0, -1.0, 7.0], [6, 1.0, 4.0, 3.0, 4.0], [9, 4.0, -1.0, 7.0, 2.0], [24, -5.0, 1.0, -3.0, 4.0]]], [[], [[6, 9], [6, 32], [9, 32]], 6]], [[[[23, -4.0, 0.0, -1.0, 1.0], [13, -4.0, -2.0, -4.0, 1.0], [6, -2.0, -5.0, 0.0, -3.0], [8, 5.0, 2.0, 5.0, 3.0], [9, -5.0, 0.0, -4.0, 2.0]], [[23, -7.0, 0.0, -4.0, 1.0], [13, -5.0, -1.0, -5.0, 2.0], [6, 0.0, -5.0, 2.0, -3.0], [8, 5.0, 3.0, 5.0, 4.0], [9, -8.0, 1.0, -7.0, 3.0]]], [[], [[6, 23], [9, 13]], 3]], [[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]]], [[[[[39, 3.0, 1.0, 6.0, 4.0], [22, -5.0, 4.0, -4.0, 7.0], [27, 2.0, -5.0, 5.0, -5.0]], [[39, 3.0, 2.0, 6.0, 5.0], [22, -5.0, 3.0, -4.0, 6.0], [27, 6.0, -4.0, 9.0, -4.0]]], [[], [], 2]], [[[[2, 3.0, -2.0, 4.0, 1.0], [32, 3.0, 5.0, 6.0, 7.0], [14, 1.0, -3.0, 2.0, -3.0], [25, -1.0, -2.0, 2.0, 1.0], [24, -1.0, -2.0, 0.0, 0.0], [29, 5.0, -2.0, 5.0, 0.0]], [[2, 0.0, -2.0, 1.0, 1.0], [32, 4.0, 4.0, 7.0, 6.0], [14, 2.0, -4.0, 3.0, -4.0], [25, 3.0, -2.0, 6.0, 1.0], [24, 1.0, -1.0, 2.0, 1.0], [29, 9.0, -2.0, 9.0, 0.0]]], [[[2, 24], [2, 25]], [[2, 14], [2, 25], [2, 32], [24, 25], [29, 32]], 18]], [[[[26, -5.0, -4.0, -2.0, -2.0], [6, 4.0, 1.0, 5.0, 2.0], [18, -2.0, 2.0, -2.0, 2.0], [24, -4.0, -5.0, -2.0, -3.0], [19, -5.0, -2.0, -4.0, -1.0]], [[26, -6.0, -4.0, -3.0, -2.0], [6, 1.0, 1.0, 2.0, 2.0], [18, -5.0, 2.0, -5.0, 2.0], [24, -5.0, -5.0, -3.0, -3.0], [19, -3.0, -2.0, -2.0, -1.0]]], [[], [[18, 19]], 8]], [[[[18, -4.0, -5.0, -3.0, -4.0], [26, 4.0, -4.0, 6.0, -1.0], [8, -4.0, -4.0, -2.0, -3.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 1.0, -2.0, 4.0, 0.0], [23, 2.0, -5.0, 2.0, -2.0]], [[18, -2.0, -6.0, -1.0, -5.0], [26, 5.0, -4.0, 7.0, -1.0], [8, -2.0, -5.0, 0.0, -4.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 5.0, -3.0, 8.0, -1.0], [23, 1.0, -4.0, 1.0, -1.0]]], [[], [[3, 23]], 5]], [[[[13, 5.0, -2.0, 6.0, 0.0], [39, 4.0, 5.0, 7.0, 7.0], [11, 0.0, 5.0, 3.0, 5.0], [10, 3.0, -4.0, 4.0, -3.0], [18, -2.0, -4.0, -1.0, -2.0], [30, -3.0, -4.0, -1.0, -1.0], [36, 1.0, 1.0, 3.0, 3.0]], [[13, 2.0, -3.0, 3.0, -1.0], [39, 1.0, 5.0, 4.0, 7.0], [11, -3.0, 6.0, 0.0, 6.0], [10, 5.0, -5.0, 6.0, -4.0], [18, -2.0, -3.0, -1.0, -1.0], [30, 1.0, -5.0, 3.0, -2.0], [36, 2.0, 0.0, 4.0, 2.0]]], [[[13, 30]], [[10, 11], [10, 13], [10, 36], [10, 39], [11, 30], [11, 36], [18, 30]], 25]], [[[[20, -2.0, -4.0, 0.0, -4.0], [8, 0.0, -2.0, 0.0, 0.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 1.0, 5.0, 2.0, 7.0], [39, -4.0, 3.0, -4.0, 5.0], [18, -3.0, -5.0, -3.0, -3.0]], [[20, -2.0, -4.0, 0.0, -4.0], [8, -3.0, -1.0, -3.0, 1.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 2.0, 4.0, 3.0, 6.0], [39, -4.0, 4.0, -4.0, 6.0], [18, 1.0, -4.0, 1.0, -2.0]]], [[[2, 18], [18, 20]], [[2, 8], [8, 18], [8, 20], [18, 20]], 14]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -2.0, 0.0, 1.0], [31, 0.0, 1.0, 3.0, 3.0]], [[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -1.0, 0.0, 2.0], [31, 0.0, 2.0, 3.0, 4.0]]], [[], [], 0]]], [[[[[39, 5.0, 0.0, 5.0, 3.0], [11, -4.0, 0.0, -4.0, 1.0], [18, -4.0, 1.0, -3.0, 3.0], [12, -2.0, 5.0, 1.0, 8.0], [36, 3.0, 0.0, 5.0, 0.0]], [[39, 7.0, 0.0, 7.0, 3.0], [11, -3.0, -1.0, -3.0, 0.0], [18, -2.0, 0.0, -1.0, 2.0], [12, -5.0, 5.0, -2.0, 8.0], [36, 5.0, 0.0, 7.0, 0.0]]], [[], [[11, 18]], 6]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[19, -5.0, 4.0, -3.0, 6.0], [29, 2.0, 0.0, 4.0, 0.0], [7, -5.0, 3.0, -4.0, 5.0], [11, 2.0, 3.0, 5.0, 3.0]], [[19, -3.0, 4.0, -1.0, 6.0], [29, -1.0, 1.0, 1.0, 1.0], [7, -1.0, 3.0, 0.0, 5.0], [11, 1.0, 3.0, 4.0, 3.0]]], [[], [], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]], [[[[1, 5.0, -4.0, 6.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]], [[1, 2.0, -4.0, 3.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]]], [[], [], 1]], [[[[38, 1.0, 3.0, 4.0, 6.0], [31, -2.0, -3.0, 1.0, -3.0], [37, 0.0, 1.0, 0.0, 3.0], [9, -5.0, 3.0, -5.0, 4.0], [4, -5.0, 4.0, -4.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 5.0, -2.0, 5.0]], [[38, 1.0, 2.0, 4.0, 5.0], [31, -3.0, -3.0, 0.0, -3.0], [37, 4.0, 2.0, 4.0, 4.0], [9, -6.0, 2.0, -6.0, 3.0], [4, -3.0, 4.0, -2.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 6.0, -2.0, 6.0]]], [[[4, 35], [37, 38]], [[4, 9], [14, 37], [31, 37], [31, 38]], 10]], [[[[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]], [[[[38, 0.0, 0.0, 1.0, 2.0], [20, -3.0, 5.0, -2.0, 7.0], [35, 2.0, 0.0, 5.0, 0.0], [39, 0.0, 1.0, 3.0, 1.0], [7, -4.0, -1.0, -2.0, 1.0], [19, 5.0, -3.0, 5.0, -1.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -5.0, 3.0, -4.0, 4.0]], [[38, 4.0, 0.0, 5.0, 2.0], [20, -6.0, 6.0, -5.0, 8.0], [35, -1.0, 1.0, 2.0, 1.0], [39, 0.0, 2.0, 3.0, 2.0], [7, -7.0, -1.0, -5.0, 1.0], [19, 4.0, -4.0, 4.0, -2.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -3.0, 4.0, -2.0, 5.0]]], [[[35, 38]], [[7, 21], [7, 26], [19, 35], [20, 21], [20, 26], [35, 38], [38, 39]], 24]]], [[[[[7, -2.0, 5.0, -2.0, 5.0], [15, 0.0, 1.0, 1.0, 1.0], [5, 4.0, -5.0, 5.0, -4.0], [2, 0.0, -2.0, 0.0, -1.0], [11, 4.0, 3.0, 6.0, 3.0], [34, -1.0, 5.0, -1.0, 6.0], [20, -1.0, -1.0, 2.0, 0.0]], [[7, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 1.0, 0.0, 1.0], [5, 6.0, -6.0, 7.0, -5.0], [2, 2.0, -2.0, 2.0, -1.0], [11, 1.0, 2.0, 3.0, 2.0], [34, -4.0, 6.0, -4.0, 7.0], [20, -1.0, 0.0, 2.0, 1.0]]], [[], [[2, 15], [5, 11], [7, 34], [20, 34]], 15]], [[[[37, -1.0, 5.0, 0.0, 5.0], [38, -1.0, 4.0, 1.0, 7.0], [32, 4.0, -4.0, 5.0, -2.0], [31, -5.0, -2.0, -4.0, -1.0], [13, 4.0, 1.0, 5.0, 3.0]], [[37, -1.0, 5.0, 0.0, 5.0], [38, 0.0, 3.0, 2.0, 6.0], [32, 8.0, -3.0, 9.0, -1.0], [31, -1.0, -3.0, 0.0, -2.0], [13, 4.0, 2.0, 5.0, 4.0]]], [[], [[13, 32]], 3]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[34, 4.0, -3.0, 5.0, -2.0], [39, -5.0, 2.0, -5.0, 5.0]], [[34, 1.0, -3.0, 2.0, -2.0], [39, -5.0, 1.0, -5.0, 4.0]]], [[], [], 0]], [[[[15, -1.0, -1.0, 2.0, 0.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 5.0, 3.0, 7.0, 5.0], [30, 1.0, 1.0, 2.0, 3.0], [26, -3.0, -3.0, -2.0, -1.0], [21, -1.0, 3.0, 0.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]], [[15, 1.0, -2.0, 4.0, -1.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 4.0, 3.0, 6.0, 5.0], [30, 3.0, 1.0, 4.0, 3.0], [26, -3.0, -4.0, -2.0, -2.0], [21, 1.0, 3.0, 2.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]]], [[[4, 30], [13, 15], [13, 30]], [[6, 30]], 7]], [[[[13, 2.0, 3.0, 5.0, 3.0], [8, 0.0, 5.0, 0.0, 8.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 2.0, 1.0, 2.0, 3.0]], [[13, 2.0, 2.0, 5.0, 2.0], [8, 1.0, 4.0, 1.0, 7.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 6.0, 2.0, 6.0, 4.0]]], [[], [[13, 15]], 3]], [[[[15, 4.0, 1.0, 5.0, 1.0], [23, 0.0, 5.0, 2.0, 5.0], [18, -5.0, 4.0, -2.0, 5.0], [39, -3.0, 0.0, -2.0, 2.0], [4, -1.0, 4.0, 2.0, 5.0], [7, 3.0, 1.0, 4.0, 2.0], [16, -3.0, -3.0, -2.0, 0.0]], [[15, 4.0, 0.0, 5.0, 0.0], [23, 2.0, 5.0, 4.0, 5.0], [18, -6.0, 4.0, -3.0, 5.0], [39, 1.0, -1.0, 2.0, 1.0], [4, -1.0, 3.0, 2.0, 4.0], [7, 0.0, 1.0, 1.0, 2.0], [16, -6.0, -3.0, -5.0, 0.0]]], [[[7, 39]], [[7, 15], [7, 23], [16, 39], [18, 39]], 16]], [[[[15, -4.0, 0.0, -4.0, 1.0], [38, 5.0, 5.0, 6.0, 8.0], [35, -5.0, 1.0, -2.0, 2.0], [22, -3.0, 4.0, 0.0, 7.0], [3, 2.0, 0.0, 2.0, 0.0], [32, 3.0, 5.0, 4.0, 8.0], [11, 0.0, 0.0, 3.0, 1.0], [24, 4.0, 0.0, 4.0, 2.0]], [[15, 0.0, 0.0, 0.0, 1.0], [38, 5.0, 6.0, 6.0, 9.0], [35, -3.0, 1.0, 0.0, 2.0], [22, 1.0, 4.0, 4.0, 7.0], [3, 3.0, 0.0, 3.0, 0.0], [32, 2.0, 5.0, 3.0, 8.0], [11, 0.0, -1.0, 3.0, 0.0], [24, 1.0, 0.0, 1.0, 2.0]]], [[[3, 24], [11, 15], [11, 24], [22, 32]], [[3, 24], [22, 35], [24, 32]], 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	`[[[10, 32]], [[2, 27], [10, 14]], 15]`	`[[[10, 32]], [[2, 27], [10, 14]], 15]`	Passed
case 1	`[[[20, 5]], [], 1]`	`[[[5, 20]], [], 1]`	Failed
case 2	`[[], [[4, 35]], 3]`	`[[], [[4, 35]], 3]`	Passed
case 3	`[[], [[8, 5], [22, 21]], 5]`	`[[], [[5, 8], [21, 22]], 5]`	Failed
case 4	`[[], [[11, 4], [30, 4]], 4]`	`[[], [[4, 11], [4, 30]], 4]`	Failed
case 5	`[[[29, 17], [29, 28]], [[38, 17]], 6]`	`[[[17, 29], [28, 29]], [[17, 38]], 6]`	Failed
case 6	`[[], [[12, 5], [33, 5]], 5]`	`[[], [[5, 12], [5, 33]], 5]`	Failed
case 7	`[[[29, 38]], [[29, 2], [29, 38]], 5]`	`[[[29, 38]], [[2, 29], [29, 38]], 5]`	Failed

SHA-256 / c04bdb571d8c42cb9ccb8ad496bee7dcb3169031cb6ed6792c6d5b9d7ad59d72

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 = [[[[[[27, 0.0, -1.0, 1.0, 1.0], [2, -2.0, 3.0, 1.0, 3.0], [10, -3.0, 0.0, 0.0, 0.0], [32, 2.0, -2.0, 2.0, 1.0], [14, -4.0, 4.0, -3.0, 4.0], [21, 5.0, 5.0, 6.0, 6.0]], [[27, 0.0, -1.0, 1.0, 1.0], [2, 2.0, 3.0, 5.0, 3.0], [10, 1.0, 0.0, 4.0, 0.0], [32, 2.0, -3.0, 2.0, 0.0], [14, -3.0, 5.0, -2.0, 5.0], [21, 2.0, 6.0, 3.0, 7.0]]], [[[10, 32]], [[2, 27], [10, 14]], 15]], [[[[20, -5.0, 5.0, -2.0, 6.0], [5, 0.0, 5.0, 3.0, 7.0]], [[20, -1.0, 6.0, 2.0, 7.0], [5, 2.0, 5.0, 5.0, 7.0]]], [[[5, 20]], [], 1]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[5, -2.0, -3.0, -1.0, -3.0], [22, 4.0, -1.0, 6.0, 2.0], [14, -2.0, 3.0, 1.0, 4.0], [8, -4.0, 1.0, -1.0, 3.0], [21, 4.0, 0.0, 4.0, 2.0]], [[5, -2.0, -3.0, -1.0, -3.0], [22, 8.0, -2.0, 10.0, 1.0], [14, -1.0, 3.0, 2.0, 4.0], [8, 0.0, 2.0, 3.0, 4.0], [21, 5.0, 1.0, 5.0, 3.0]]], [[], [[5, 8], [21, 22]], 5]], [[[[30, 2.0, 2.0, 3.0, 2.0], [11, 4.0, -1.0, 4.0, 1.0], [13, 5.0, 4.0, 6.0, 7.0], [4, 3.0, -1.0, 4.0, 1.0]], [[30, 6.0, 1.0, 7.0, 1.0], [11, 8.0, 0.0, 8.0, 2.0], [13, 9.0, 4.0, 10.0, 7.0], [4, 3.0, -2.0, 4.0, 0.0]]], [[], [[4, 11], [4, 30]], 4]], [[[[29, -1.0, -2.0, 2.0, 1.0], [38, 5.0, 1.0, 5.0, 3.0], [28, 3.0, -3.0, 3.0, -2.0], [17, 5.0, 1.0, 8.0, 3.0], [9, -5.0, -2.0, -4.0, 0.0]], [[29, 1.0, -1.0, 4.0, 2.0], [38, 9.0, 1.0, 9.0, 3.0], [28, 2.0, -2.0, 2.0, -1.0], [17, 2.0, 1.0, 5.0, 3.0], [9, -1.0, -1.0, 0.0, 1.0]]], [[[17, 29], [28, 29]], [[17, 38]], 6]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[2, 0.0, 5.0, 3.0, 8.0], [38, 5.0, -5.0, 5.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -4.0, 1.0, -1.0], [29, 3.0, -5.0, 3.0, -3.0]], [[2, -1.0, 4.0, 2.0, 7.0], [38, 4.0, -5.0, 4.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -5.0, 1.0, -2.0], [29, 7.0, -4.0, 7.0, -2.0]]], [[[29, 38]], [[2, 29], [29, 38]], 5]]], [[[[[10, 1.0, -3.0, 3.0, -3.0], [33, 1.0, 0.0, 4.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -3.0, 1.0, -2.0, 3.0]], [[10, 1.0, -3.0, 3.0, -3.0], [33, 2.0, 0.0, 5.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -1.0, 1.0, 0.0, 3.0]]], [[], [[16, 38]], 2]], [[[[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]], [[[[1, -3.0, 0.0, -1.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -5.0, 0.0, -5.0, 0.0], [36, 0.0, 3.0, 0.0, 3.0], [33, -1.0, -4.0, 1.0, -2.0], [32, 4.0, -1.0, 5.0, 1.0]], [[1, -6.0, 0.0, -4.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -1.0, 0.0, -1.0, 0.0], [36, 4.0, 2.0, 4.0, 2.0], [33, -2.0, -3.0, 0.0, -1.0], [32, 4.0, 0.0, 5.0, 2.0]]], [[[1, 23], [32, 36]], [[1, 23], [1, 27], [1, 33], [33, 36]], 13]], [[[[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]], [[[[12, -2.0, 0.0, 0.0, 2.0], [19, 0.0, -5.0, 3.0, -5.0], [10, -1.0, -4.0, 0.0, -2.0], [39, 4.0, -3.0, 7.0, -1.0], [17, -4.0, 1.0, -2.0, 4.0], [28, -2.0, -5.0, -1.0, -3.0], [35, 0.0, 5.0, 3.0, 6.0]], [[12, -1.0, -1.0, 1.0, 1.0], [19, 4.0, -5.0, 7.0, -5.0], [10, 1.0, -3.0, 2.0, -1.0], [39, 3.0, -2.0, 6.0, 0.0], [17, -3.0, 1.0, -1.0, 4.0], [28, -3.0, -5.0, -2.0, -3.0], [35, -3.0, 5.0, 0.0, 6.0]]], [[], [[10, 19], [10, 28], [10, 35], [12, 19], [12, 28], [19, 35]], 20]], [[[[32, 1.0, 5.0, 2.0, 6.0], [6, 0.0, 5.0, 2.0, 5.0], [9, 0.0, -2.0, 3.0, 1.0], [24, -5.0, 0.0, -3.0, 3.0]], [[32, -2.0, 6.0, -1.0, 7.0], [6, 1.0, 4.0, 3.0, 4.0], [9, 4.0, -1.0, 7.0, 2.0], [24, -5.0, 1.0, -3.0, 4.0]]], [[], [[6, 9], [6, 32], [9, 32]], 6]], [[[[23, -4.0, 0.0, -1.0, 1.0], [13, -4.0, -2.0, -4.0, 1.0], [6, -2.0, -5.0, 0.0, -3.0], [8, 5.0, 2.0, 5.0, 3.0], [9, -5.0, 0.0, -4.0, 2.0]], [[23, -7.0, 0.0, -4.0, 1.0], [13, -5.0, -1.0, -5.0, 2.0], [6, 0.0, -5.0, 2.0, -3.0], [8, 5.0, 3.0, 5.0, 4.0], [9, -8.0, 1.0, -7.0, 3.0]]], [[], [[6, 23], [9, 13]], 3]], [[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]]], [[[[[39, 3.0, 1.0, 6.0, 4.0], [22, -5.0, 4.0, -4.0, 7.0], [27, 2.0, -5.0, 5.0, -5.0]], [[39, 3.0, 2.0, 6.0, 5.0], [22, -5.0, 3.0, -4.0, 6.0], [27, 6.0, -4.0, 9.0, -4.0]]], [[], [], 2]], [[[[2, 3.0, -2.0, 4.0, 1.0], [32, 3.0, 5.0, 6.0, 7.0], [14, 1.0, -3.0, 2.0, -3.0], [25, -1.0, -2.0, 2.0, 1.0], [24, -1.0, -2.0, 0.0, 0.0], [29, 5.0, -2.0, 5.0, 0.0]], [[2, 0.0, -2.0, 1.0, 1.0], [32, 4.0, 4.0, 7.0, 6.0], [14, 2.0, -4.0, 3.0, -4.0], [25, 3.0, -2.0, 6.0, 1.0], [24, 1.0, -1.0, 2.0, 1.0], [29, 9.0, -2.0, 9.0, 0.0]]], [[[2, 24], [2, 25]], [[2, 14], [2, 25], [2, 32], [24, 25], [29, 32]], 18]], [[[[26, -5.0, -4.0, -2.0, -2.0], [6, 4.0, 1.0, 5.0, 2.0], [18, -2.0, 2.0, -2.0, 2.0], [24, -4.0, -5.0, -2.0, -3.0], [19, -5.0, -2.0, -4.0, -1.0]], [[26, -6.0, -4.0, -3.0, -2.0], [6, 1.0, 1.0, 2.0, 2.0], [18, -5.0, 2.0, -5.0, 2.0], [24, -5.0, -5.0, -3.0, -3.0], [19, -3.0, -2.0, -2.0, -1.0]]], [[], [[18, 19]], 8]], [[[[18, -4.0, -5.0, -3.0, -4.0], [26, 4.0, -4.0, 6.0, -1.0], [8, -4.0, -4.0, -2.0, -3.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 1.0, -2.0, 4.0, 0.0], [23, 2.0, -5.0, 2.0, -2.0]], [[18, -2.0, -6.0, -1.0, -5.0], [26, 5.0, -4.0, 7.0, -1.0], [8, -2.0, -5.0, 0.0, -4.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 5.0, -3.0, 8.0, -1.0], [23, 1.0, -4.0, 1.0, -1.0]]], [[], [[3, 23]], 5]], [[[[13, 5.0, -2.0, 6.0, 0.0], [39, 4.0, 5.0, 7.0, 7.0], [11, 0.0, 5.0, 3.0, 5.0], [10, 3.0, -4.0, 4.0, -3.0], [18, -2.0, -4.0, -1.0, -2.0], [30, -3.0, -4.0, -1.0, -1.0], [36, 1.0, 1.0, 3.0, 3.0]], [[13, 2.0, -3.0, 3.0, -1.0], [39, 1.0, 5.0, 4.0, 7.0], [11, -3.0, 6.0, 0.0, 6.0], [10, 5.0, -5.0, 6.0, -4.0], [18, -2.0, -3.0, -1.0, -1.0], [30, 1.0, -5.0, 3.0, -2.0], [36, 2.0, 0.0, 4.0, 2.0]]], [[[13, 30]], [[10, 11], [10, 13], [10, 36], [10, 39], [11, 30], [11, 36], [18, 30]], 25]], [[[[20, -2.0, -4.0, 0.0, -4.0], [8, 0.0, -2.0, 0.0, 0.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 1.0, 5.0, 2.0, 7.0], [39, -4.0, 3.0, -4.0, 5.0], [18, -3.0, -5.0, -3.0, -3.0]], [[20, -2.0, -4.0, 0.0, -4.0], [8, -3.0, -1.0, -3.0, 1.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 2.0, 4.0, 3.0, 6.0], [39, -4.0, 4.0, -4.0, 6.0], [18, 1.0, -4.0, 1.0, -2.0]]], [[[2, 18], [18, 20]], [[2, 8], [8, 18], [8, 20], [18, 20]], 14]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -2.0, 0.0, 1.0], [31, 0.0, 1.0, 3.0, 3.0]], [[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -1.0, 0.0, 2.0], [31, 0.0, 2.0, 3.0, 4.0]]], [[], [], 0]]], [[[[[39, 5.0, 0.0, 5.0, 3.0], [11, -4.0, 0.0, -4.0, 1.0], [18, -4.0, 1.0, -3.0, 3.0], [12, -2.0, 5.0, 1.0, 8.0], [36, 3.0, 0.0, 5.0, 0.0]], [[39, 7.0, 0.0, 7.0, 3.0], [11, -3.0, -1.0, -3.0, 0.0], [18, -2.0, 0.0, -1.0, 2.0], [12, -5.0, 5.0, -2.0, 8.0], [36, 5.0, 0.0, 7.0, 0.0]]], [[], [[11, 18]], 6]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[19, -5.0, 4.0, -3.0, 6.0], [29, 2.0, 0.0, 4.0, 0.0], [7, -5.0, 3.0, -4.0, 5.0], [11, 2.0, 3.0, 5.0, 3.0]], [[19, -3.0, 4.0, -1.0, 6.0], [29, -1.0, 1.0, 1.0, 1.0], [7, -1.0, 3.0, 0.0, 5.0], [11, 1.0, 3.0, 4.0, 3.0]]], [[], [], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]], [[[[1, 5.0, -4.0, 6.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]], [[1, 2.0, -4.0, 3.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]]], [[], [], 1]], [[[[38, 1.0, 3.0, 4.0, 6.0], [31, -2.0, -3.0, 1.0, -3.0], [37, 0.0, 1.0, 0.0, 3.0], [9, -5.0, 3.0, -5.0, 4.0], [4, -5.0, 4.0, -4.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 5.0, -2.0, 5.0]], [[38, 1.0, 2.0, 4.0, 5.0], [31, -3.0, -3.0, 0.0, -3.0], [37, 4.0, 2.0, 4.0, 4.0], [9, -6.0, 2.0, -6.0, 3.0], [4, -3.0, 4.0, -2.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 6.0, -2.0, 6.0]]], [[[4, 35], [37, 38]], [[4, 9], [14, 37], [31, 37], [31, 38]], 10]], [[[[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]], [[[[38, 0.0, 0.0, 1.0, 2.0], [20, -3.0, 5.0, -2.0, 7.0], [35, 2.0, 0.0, 5.0, 0.0], [39, 0.0, 1.0, 3.0, 1.0], [7, -4.0, -1.0, -2.0, 1.0], [19, 5.0, -3.0, 5.0, -1.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -5.0, 3.0, -4.0, 4.0]], [[38, 4.0, 0.0, 5.0, 2.0], [20, -6.0, 6.0, -5.0, 8.0], [35, -1.0, 1.0, 2.0, 1.0], [39, 0.0, 2.0, 3.0, 2.0], [7, -7.0, -1.0, -5.0, 1.0], [19, 4.0, -4.0, 4.0, -2.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -3.0, 4.0, -2.0, 5.0]]], [[[35, 38]], [[7, 21], [7, 26], [19, 35], [20, 21], [20, 26], [35, 38], [38, 39]], 24]]], [[[[[7, -2.0, 5.0, -2.0, 5.0], [15, 0.0, 1.0, 1.0, 1.0], [5, 4.0, -5.0, 5.0, -4.0], [2, 0.0, -2.0, 0.0, -1.0], [11, 4.0, 3.0, 6.0, 3.0], [34, -1.0, 5.0, -1.0, 6.0], [20, -1.0, -1.0, 2.0, 0.0]], [[7, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 1.0, 0.0, 1.0], [5, 6.0, -6.0, 7.0, -5.0], [2, 2.0, -2.0, 2.0, -1.0], [11, 1.0, 2.0, 3.0, 2.0], [34, -4.0, 6.0, -4.0, 7.0], [20, -1.0, 0.0, 2.0, 1.0]]], [[], [[2, 15], [5, 11], [7, 34], [20, 34]], 15]], [[[[37, -1.0, 5.0, 0.0, 5.0], [38, -1.0, 4.0, 1.0, 7.0], [32, 4.0, -4.0, 5.0, -2.0], [31, -5.0, -2.0, -4.0, -1.0], [13, 4.0, 1.0, 5.0, 3.0]], [[37, -1.0, 5.0, 0.0, 5.0], [38, 0.0, 3.0, 2.0, 6.0], [32, 8.0, -3.0, 9.0, -1.0], [31, -1.0, -3.0, 0.0, -2.0], [13, 4.0, 2.0, 5.0, 4.0]]], [[], [[13, 32]], 3]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[34, 4.0, -3.0, 5.0, -2.0], [39, -5.0, 2.0, -5.0, 5.0]], [[34, 1.0, -3.0, 2.0, -2.0], [39, -5.0, 1.0, -5.0, 4.0]]], [[], [], 0]], [[[[15, -1.0, -1.0, 2.0, 0.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 5.0, 3.0, 7.0, 5.0], [30, 1.0, 1.0, 2.0, 3.0], [26, -3.0, -3.0, -2.0, -1.0], [21, -1.0, 3.0, 0.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]], [[15, 1.0, -2.0, 4.0, -1.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 4.0, 3.0, 6.0, 5.0], [30, 3.0, 1.0, 4.0, 3.0], [26, -3.0, -4.0, -2.0, -2.0], [21, 1.0, 3.0, 2.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]]], [[[4, 30], [13, 15], [13, 30]], [[6, 30]], 7]], [[[[13, 2.0, 3.0, 5.0, 3.0], [8, 0.0, 5.0, 0.0, 8.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 2.0, 1.0, 2.0, 3.0]], [[13, 2.0, 2.0, 5.0, 2.0], [8, 1.0, 4.0, 1.0, 7.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 6.0, 2.0, 6.0, 4.0]]], [[], [[13, 15]], 3]], [[[[15, 4.0, 1.0, 5.0, 1.0], [23, 0.0, 5.0, 2.0, 5.0], [18, -5.0, 4.0, -2.0, 5.0], [39, -3.0, 0.0, -2.0, 2.0], [4, -1.0, 4.0, 2.0, 5.0], [7, 3.0, 1.0, 4.0, 2.0], [16, -3.0, -3.0, -2.0, 0.0]], [[15, 4.0, 0.0, 5.0, 0.0], [23, 2.0, 5.0, 4.0, 5.0], [18, -6.0, 4.0, -3.0, 5.0], [39, 1.0, -1.0, 2.0, 1.0], [4, -1.0, 3.0, 2.0, 4.0], [7, 0.0, 1.0, 1.0, 2.0], [16, -6.0, -3.0, -5.0, 0.0]]], [[[7, 39]], [[7, 15], [7, 23], [16, 39], [18, 39]], 16]], [[[[15, -4.0, 0.0, -4.0, 1.0], [38, 5.0, 5.0, 6.0, 8.0], [35, -5.0, 1.0, -2.0, 2.0], [22, -3.0, 4.0, 0.0, 7.0], [3, 2.0, 0.0, 2.0, 0.0], [32, 3.0, 5.0, 4.0, 8.0], [11, 0.0, 0.0, 3.0, 1.0], [24, 4.0, 0.0, 4.0, 2.0]], [[15, 0.0, 0.0, 0.0, 1.0], [38, 5.0, 6.0, 6.0, 9.0], [35, -3.0, 1.0, 0.0, 2.0], [22, 1.0, 4.0, 4.0, 7.0], [3, 3.0, 0.0, 3.0, 0.0], [32, 2.0, 5.0, 3.0, 8.0], [11, 0.0, -1.0, 3.0, 0.0], [24, 1.0, 0.0, 1.0, 2.0]]], [[[3, 24], [11, 15], [11, 24], [22, 32]], [[3, 24], [22, 35], [24, 32]], 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	`[[[10, 32]], [[2, 27], [10, 14]], 15]`	`[[[10, 32]], [[2, 27], [10, 14]], 15]`	Passed
case 1	`[[[5, 20]], [], 1]`	`[[[5, 20]], [], 1]`	Passed
case 2	`[[], [[4, 35]], 3]`	`[[], [[4, 35]], 3]`	Passed
case 3	`[[], [[5, 8], [21, 22]], 5]`	`[[], [[5, 8], [21, 22]], 5]`	Passed
case 4	`[[], [[4, 11], [4, 30]], 4]`	`[[], [[4, 11], [4, 30]], 4]`	Passed
case 5	`[[[17, 29], [28, 29]], [[17, 38]], 6]`	`[[[17, 29], [28, 29]], [[17, 38]], 6]`	Passed
case 6	`[[], [[5, 12], [5, 33]], 5]`	`[[], [[5, 12], [5, 33]], 5]`	Passed
case 7	`[[[29, 38]], [[2, 29], [29, 38]], 5]`	`[[[29, 38]], [[2, 29], [29, 38]], 5]`	Passed

SHA-256 / 4318783a4bf03ecc528ad40706f2ac3ce3c3b1f40ffb0d4fb661617c5a70b6c1

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.370411+00:00.

Case digest / 82a7e69e8583203741a23eafd54b993c525581ca4a44c8bc395e5be2d577091b