FA-87796 / Collision detection broadphase / Open access

Same-kind endpoint swaps end pairs · case 01

Boxes sliding past each other while overlapping lose their contact.

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

ROOT CAUSE

Any non-begin swap emits an end event.

VERIFIED REPAIR

Only a max passing a min ends a pair.

Unsuccessful approach: Treating any max swap as an end still ends on max-over-max swaps.

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

SHA-256 / 6d297d01b964cdb696859ff2eb8675afd5150a3d8e4b45b12071b5a2dded2e58

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

SHA-256 / f9b2311becf541de14c90bd9fa0ce6d448f0ad11786fa88751a841ed40206aa7

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

SHA-256 / bee683ca79e2e0f80679209bd824b278c065e36c9d1aff2976c32b62e57cd2b1

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

Case digest / 904b41e7737ac78d614e69308fc113632a234d2a744ae919a935d55519b0e1b1