FA-87486 / Collision detection broadphase / Open access
Quadtree allows one level below the maximum depth · case 01
Degenerate clusters create nodes deeper than configured.
ROOT CAUSE
The depth guard is d <= max_depth.
VERIFIED REPAIR
Only nodes with d < max_depth may split.
Unsuccessful approach: Using d+1 < max_depth stops one level early.
Case contract
solve(objs, cap, max_depth, q): quadtree over [0,16]^2. Insert [id,minx,miny,maxx,maxy] in order. A node splits when it holds more than cap objects and depth<max_depth; children are ordered cy*2+cx. An object goes to a child only if it fits entirely: maxx<mid -> left, minx>=mid -> right (same for y); straddlers stay. On split all node objects are re-inserted. Query returns [sorted ids of objects in nodes whose closed bounds overlap q, total node count, max depth].
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(objs, cap, max_depth, q):
def make(x, y, s, d):
return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
def child_index(n, o):
h = n['s'] / 2
mx, my = n['x'] + h, n['y'] + h
if o[3] < mx:
cx = 0
elif o[1] >= mx:
cx = 1
else:
return -1
if o[4] < my:
cy = 0
elif o[2] >= my:
cy = 1
else:
return -1
return cy * 2 + cx
def split(n):
h = n['s'] / 2
n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
old, n['objs'] = n['objs'], []
for o in old:
insert(n, o)
def insert(n, o):
if n['kids'] is not None:
k = child_index(n, o)
if k >= 0:
insert(n['kids'][k], o)
return
n['objs'].append(o)
if n['kids'] is None and len(n['objs']) > cap and n['d'] <= max_depth:
split(n)
root = make(0, 0, 16, 0)
for o in objs:
insert(root, o)
found, count, deep = [], 0, 0
stack = [root]
while stack:
n = stack.pop()
count += 1
deep = max(deep, n['d'])
if n['kids']:
stack.extend(n['kids'])
if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
found.extend(o[0] for o in n['objs'])
return [sorted(found), count, deep]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]], [[[[17, 1, 8, 3, 8], [10, 5, 2, 6, 2], [49, 4, 10, 5, 12], [3, 14, 4, 14, 4], [4, 11, 7, 13, 8], [29, 10, 1, 13, 1]], 1, 1, [12, 11, 16, 16]], [[4], 5, 1]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 13, 10, 14, 12], [22, 15, 13, 16, 13], [29, 6, 6, 8, 6], [35, 4, 3, 7, 4], [20, 6, 0, 6, 0]], 2, 1, [10, 1, 14, 3]], [[29], 5, 1]], [[[[21, 6, 5, 6, 7], [31, 7, 11, 7, 12], [17, 1, 8, 3, 9], [14, 10, 14, 12, 14], [33, 4, 15, 6, 16]], 1, 1, [12, 10, 12, 15]], [[14], 5, 1]], [[[[28, 12, 2, 15, 5], [6, 4, 1, 6, 4], [47, 4, 10, 6, 11], [49, 8, 9, 9, 10], [41, 12, 4, 14, 7]], 1, 3, [2, 10, 5, 10]], [[47], 9, 2]], [[[[32, 9, 1, 11, 3], [9, 7, 15, 7, 16], [44, 9, 8, 10, 8], [45, 9, 10, 12, 12], [21, 6, 0, 9, 1]], 2, 1, [3, 6, 3, 7]], [[21], 5, 1]], [[[[48, 14, 14, 16, 16], [19, 15, 3, 15, 4], [34, 0, 5, 2, 8], [13, 5, 1, 8, 1], [21, 1, 15, 3, 15], [36, 5, 6, 7, 8], [28, 15, 2, 16, 5], [41, 4, 7, 6, 10]], 2, 3, [8, 2, 13, 6]], [[13, 19, 28, 34, 36, 41], 5, 1]]], [[[[[48, 15, 14, 16, 14], [2, 2, 13, 4, 15], [30, 0, 0, 3, 0], [43, 5, 5, 8, 8], [24, 7, 13, 7, 14]], 1, 1, [5, 3, 7, 6]], [[30, 43], 5, 1]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]], [[[[28, 15, 10, 15, 13], [3, 14, 15, 16, 16], [23, 15, 9, 16, 10], [7, 13, 13, 13, 15], [16, 6, 8, 6, 9]], 2, 2, [3, 13, 3, 18]], [[16], 9, 2]], [[[[16, 3, 6, 3, 6], [36, 2, 1, 3, 3], [34, 11, 1, 14, 3], [2, 15, 9, 16, 10], [48, 5, 3, 8, 3], [41, 1, 7, 3, 8], [17, 7, 6, 7, 8]], 1, 1, [2, 10, 4, 10]], [[17, 41, 48], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[49, 11, 10, 11, 10], [12, 1, 6, 1, 8], [45, 15, 11, 16, 11], [8, 13, 12, 14, 14], [47, 10, 8, 10, 9]], 1, 1, [4, 10, 7, 10]], [[12], 5, 1]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]]], [[[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]], [[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[48, 13, 12, 14, 14], [15, 12, 15, 12, 16], [38, 14, 3, 16, 4], [22, 3, 6, 5, 7], [6, 0, 0, 2, 0], [10, 5, 6, 8, 6], [47, 4, 7, 5, 10], [21, 2, 10, 5, 10], [45, 12, 2, 13, 2]], 1, 1, [11, 2, 15, 7]], [[10, 38, 45, 47], 5, 1]], [[[[30, 4, 13, 4, 14], [46, 0, 12, 2, 13], [14, 9, 15, 12, 16], [43, 11, 7, 14, 7], [12, 11, 3, 12, 6], [33, 9, 10, 12, 10], [48, 1, 11, 1, 13], [25, 11, 9, 13, 10], [49, 6, 6, 7, 7]], 2, 1, [14, 2, 19, 5]], [[12, 43], 5, 1]], [[[[46, 5, 8, 5, 9], [8, 1, 13, 2, 15], [38, 8, 6, 9, 8], [14, 1, 15, 3, 16], [36, 10, 8, 11, 9], [4, 12, 5, 12, 8], [48, 1, 10, 1, 11], [42, 10, 7, 12, 9], [26, 11, 14, 12, 16], [17, 10, 9, 10, 12]], 2, 1, [8, 9, 11, 13]], [[4, 8, 14, 17, 26, 36, 38, 42, 46, 48], 5, 1]], [[[[31, 9, 9, 10, 12], [13, 5, 15, 7, 16], [33, 0, 4, 3, 5]], 2, 1, [12, 12, 16, 15]], [[31], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[6, 7, 4, 7, 5], [25, 5, 5, 7, 6], [31, 14, 13, 14, 13], [13, 3, 13, 5, 16]], 2, 3, [14, 8, 19, 8]], [[31], 5, 1]]], [[[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]], [[[[29, 0, 6, 1, 7], [13, 7, 1, 7, 2], [45, 2, 2, 3, 2], [34, 3, 1, 3, 4], [46, 1, 6, 2, 8], [22, 5, 2, 5, 4]], 2, 1, [9, 11, 11, 14]], [[46], 5, 1]], [[[[30, 0, 15, 3, 15], [22, 7, 2, 10, 5], [39, 0, 4, 0, 6], [20, 13, 7, 15, 7], [28, 5, 8, 7, 10], [2, 9, 0, 9, 0], [25, 15, 15, 16, 16], [42, 1, 10, 4, 11], [6, 8, 8, 8, 10], [9, 11, 12, 12, 13]], 1, 2, [11, 5, 11, 6]], [[22], 17, 2]], [[[[35, 2, 3, 3, 6], [39, 15, 10, 15, 11], [1, 13, 12, 14, 15], [45, 5, 9, 8, 12], [48, 8, 14, 8, 14], [38, 8, 2, 11, 2], [37, 2, 11, 2, 12], [7, 12, 14, 15, 15]], 1, 2, [3, 6, 7, 7]], [[35, 45], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[33, 4, 7, 7, 9], [26, 8, 5, 11, 8], [49, 6, 11, 6, 12], [7, 2, 3, 3, 5]], 1, 1, [11, 12, 14, 13]], [[26, 33], 5, 1]]], [[[[[22, 7, 14, 9, 16], [33, 3, 15, 5, 16], [46, 7, 10, 7, 12], [43, 15, 13, 16, 15]], 2, 1, [2, 9, 3, 14]], [[22, 33, 46], 5, 1]], [[[[29, 8, 4, 11, 7], [45, 0, 12, 1, 15], [20, 14, 7, 16, 7], [39, 4, 12, 6, 14], [25, 9, 7, 10, 8], [12, 8, 8, 11, 9], [26, 11, 12, 13, 13], [1, 4, 15, 6, 16], [32, 7, 10, 10, 12], [11, 7, 4, 7, 4]], 3, 2, [8, 0, 13, 2]], [[11, 20, 25, 29, 32], 5, 1]], [[[[28, 10, 12, 10, 12], [22, 9, 7, 12, 7], [4, 14, 4, 14, 5], [2, 7, 14, 9, 15]], 1, 3, [12, 1, 13, 5]], [[2, 4, 22], 9, 2]], [[[[35, 5, 11, 7, 12], [47, 3, 4, 6, 4], [27, 15, 1, 16, 1], [43, 12, 11, 13, 14], [49, 3, 15, 3, 16], [38, 6, 8, 6, 9], [25, 5, 12, 6, 15], [5, 5, 2, 7, 3], [45, 13, 1, 13, 4], [23, 14, 1, 16, 3]], 2, 1, [2, 11, 4, 12]], [[25, 35, 38, 49], 5, 1]], [[[[37, 11, 9, 14, 12], [38, 3, 1, 4, 1], [14, 6, 7, 8, 7], [45, 8, 2, 11, 3], [12, 0, 4, 3, 4]], 1, 1, [7, 12, 9, 13]], [[14, 37], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]]]]
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 | [[11], 13, 3] | [[5, 7, 11], 9, 2] | Failed |
| case 1 | [[4], 13, 2] | [[4], 5, 1] | Failed |
| case 2 | [[13, 29, 33], 21, 3] | [[13, 29, 33], 17, 2] | Failed |
| case 3 | [[29], 5, 1] | [[29], 5, 1] | Passed |
| case 4 | [[14], 9, 2] | [[14], 5, 1] | Failed |
| case 5 | [[47], 9, 2] | [[47], 9, 2] | Passed |
| case 6 | [[21], 5, 1] | [[21], 5, 1] | Passed |
| case 7 | [[13, 19, 28, 34, 36, 41], 5, 1] | [[13, 19, 28, 34, 36, 41], 5, 1] | Passed |
SHA-256 / d1d06bc0ffb32d17328a02752aec1dfd5c9c1f06758ad0cad029bbd5a237bdc1
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
def make(x, y, s, d):
return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
def child_index(n, o):
h = n['s'] / 2
mx, my = n['x'] + h, n['y'] + h
if o[3] < mx:
cx = 0
elif o[1] >= mx:
cx = 1
else:
return -1
if o[4] < my:
cy = 0
elif o[2] >= my:
cy = 1
else:
return -1
return cy * 2 + cx
def split(n):
h = n['s'] / 2
n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
old, n['objs'] = n['objs'], []
for o in old:
insert(n, o)
def insert(n, o):
if n['kids'] is not None:
k = child_index(n, o)
if k >= 0:
insert(n['kids'][k], o)
return
n['objs'].append(o)
if n['kids'] is None and len(n['objs']) > cap and n['d'] + 1 < max_depth:
split(n)
root = make(0, 0, 16, 0)
for o in objs:
insert(root, o)
found, count, deep = [], 0, 0
stack = [root]
while stack:
n = stack.pop()
count += 1
deep = max(deep, n['d'])
if n['kids']:
stack.extend(n['kids'])
if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
found.extend(o[0] for o in n['objs'])
return [sorted(found), count, deep]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]], [[[[17, 1, 8, 3, 8], [10, 5, 2, 6, 2], [49, 4, 10, 5, 12], [3, 14, 4, 14, 4], [4, 11, 7, 13, 8], [29, 10, 1, 13, 1]], 1, 1, [12, 11, 16, 16]], [[4], 5, 1]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 13, 10, 14, 12], [22, 15, 13, 16, 13], [29, 6, 6, 8, 6], [35, 4, 3, 7, 4], [20, 6, 0, 6, 0]], 2, 1, [10, 1, 14, 3]], [[29], 5, 1]], [[[[21, 6, 5, 6, 7], [31, 7, 11, 7, 12], [17, 1, 8, 3, 9], [14, 10, 14, 12, 14], [33, 4, 15, 6, 16]], 1, 1, [12, 10, 12, 15]], [[14], 5, 1]], [[[[28, 12, 2, 15, 5], [6, 4, 1, 6, 4], [47, 4, 10, 6, 11], [49, 8, 9, 9, 10], [41, 12, 4, 14, 7]], 1, 3, [2, 10, 5, 10]], [[47], 9, 2]], [[[[32, 9, 1, 11, 3], [9, 7, 15, 7, 16], [44, 9, 8, 10, 8], [45, 9, 10, 12, 12], [21, 6, 0, 9, 1]], 2, 1, [3, 6, 3, 7]], [[21], 5, 1]], [[[[48, 14, 14, 16, 16], [19, 15, 3, 15, 4], [34, 0, 5, 2, 8], [13, 5, 1, 8, 1], [21, 1, 15, 3, 15], [36, 5, 6, 7, 8], [28, 15, 2, 16, 5], [41, 4, 7, 6, 10]], 2, 3, [8, 2, 13, 6]], [[13, 19, 28, 34, 36, 41], 5, 1]]], [[[[[48, 15, 14, 16, 14], [2, 2, 13, 4, 15], [30, 0, 0, 3, 0], [43, 5, 5, 8, 8], [24, 7, 13, 7, 14]], 1, 1, [5, 3, 7, 6]], [[30, 43], 5, 1]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]], [[[[28, 15, 10, 15, 13], [3, 14, 15, 16, 16], [23, 15, 9, 16, 10], [7, 13, 13, 13, 15], [16, 6, 8, 6, 9]], 2, 2, [3, 13, 3, 18]], [[16], 9, 2]], [[[[16, 3, 6, 3, 6], [36, 2, 1, 3, 3], [34, 11, 1, 14, 3], [2, 15, 9, 16, 10], [48, 5, 3, 8, 3], [41, 1, 7, 3, 8], [17, 7, 6, 7, 8]], 1, 1, [2, 10, 4, 10]], [[17, 41, 48], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[49, 11, 10, 11, 10], [12, 1, 6, 1, 8], [45, 15, 11, 16, 11], [8, 13, 12, 14, 14], [47, 10, 8, 10, 9]], 1, 1, [4, 10, 7, 10]], [[12], 5, 1]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]]], [[[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]], [[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[48, 13, 12, 14, 14], [15, 12, 15, 12, 16], [38, 14, 3, 16, 4], [22, 3, 6, 5, 7], [6, 0, 0, 2, 0], [10, 5, 6, 8, 6], [47, 4, 7, 5, 10], [21, 2, 10, 5, 10], [45, 12, 2, 13, 2]], 1, 1, [11, 2, 15, 7]], [[10, 38, 45, 47], 5, 1]], [[[[30, 4, 13, 4, 14], [46, 0, 12, 2, 13], [14, 9, 15, 12, 16], [43, 11, 7, 14, 7], [12, 11, 3, 12, 6], [33, 9, 10, 12, 10], [48, 1, 11, 1, 13], [25, 11, 9, 13, 10], [49, 6, 6, 7, 7]], 2, 1, [14, 2, 19, 5]], [[12, 43], 5, 1]], [[[[46, 5, 8, 5, 9], [8, 1, 13, 2, 15], [38, 8, 6, 9, 8], [14, 1, 15, 3, 16], [36, 10, 8, 11, 9], [4, 12, 5, 12, 8], [48, 1, 10, 1, 11], [42, 10, 7, 12, 9], [26, 11, 14, 12, 16], [17, 10, 9, 10, 12]], 2, 1, [8, 9, 11, 13]], [[4, 8, 14, 17, 26, 36, 38, 42, 46, 48], 5, 1]], [[[[31, 9, 9, 10, 12], [13, 5, 15, 7, 16], [33, 0, 4, 3, 5]], 2, 1, [12, 12, 16, 15]], [[31], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[6, 7, 4, 7, 5], [25, 5, 5, 7, 6], [31, 14, 13, 14, 13], [13, 3, 13, 5, 16]], 2, 3, [14, 8, 19, 8]], [[31], 5, 1]]], [[[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]], [[[[29, 0, 6, 1, 7], [13, 7, 1, 7, 2], [45, 2, 2, 3, 2], [34, 3, 1, 3, 4], [46, 1, 6, 2, 8], [22, 5, 2, 5, 4]], 2, 1, [9, 11, 11, 14]], [[46], 5, 1]], [[[[30, 0, 15, 3, 15], [22, 7, 2, 10, 5], [39, 0, 4, 0, 6], [20, 13, 7, 15, 7], [28, 5, 8, 7, 10], [2, 9, 0, 9, 0], [25, 15, 15, 16, 16], [42, 1, 10, 4, 11], [6, 8, 8, 8, 10], [9, 11, 12, 12, 13]], 1, 2, [11, 5, 11, 6]], [[22], 17, 2]], [[[[35, 2, 3, 3, 6], [39, 15, 10, 15, 11], [1, 13, 12, 14, 15], [45, 5, 9, 8, 12], [48, 8, 14, 8, 14], [38, 8, 2, 11, 2], [37, 2, 11, 2, 12], [7, 12, 14, 15, 15]], 1, 2, [3, 6, 7, 7]], [[35, 45], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[33, 4, 7, 7, 9], [26, 8, 5, 11, 8], [49, 6, 11, 6, 12], [7, 2, 3, 3, 5]], 1, 1, [11, 12, 14, 13]], [[26, 33], 5, 1]]], [[[[[22, 7, 14, 9, 16], [33, 3, 15, 5, 16], [46, 7, 10, 7, 12], [43, 15, 13, 16, 15]], 2, 1, [2, 9, 3, 14]], [[22, 33, 46], 5, 1]], [[[[29, 8, 4, 11, 7], [45, 0, 12, 1, 15], [20, 14, 7, 16, 7], [39, 4, 12, 6, 14], [25, 9, 7, 10, 8], [12, 8, 8, 11, 9], [26, 11, 12, 13, 13], [1, 4, 15, 6, 16], [32, 7, 10, 10, 12], [11, 7, 4, 7, 4]], 3, 2, [8, 0, 13, 2]], [[11, 20, 25, 29, 32], 5, 1]], [[[[28, 10, 12, 10, 12], [22, 9, 7, 12, 7], [4, 14, 4, 14, 5], [2, 7, 14, 9, 15]], 1, 3, [12, 1, 13, 5]], [[2, 4, 22], 9, 2]], [[[[35, 5, 11, 7, 12], [47, 3, 4, 6, 4], [27, 15, 1, 16, 1], [43, 12, 11, 13, 14], [49, 3, 15, 3, 16], [38, 6, 8, 6, 9], [25, 5, 12, 6, 15], [5, 5, 2, 7, 3], [45, 13, 1, 13, 4], [23, 14, 1, 16, 3]], 2, 1, [2, 11, 4, 12]], [[25, 35, 38, 49], 5, 1]], [[[[37, 11, 9, 14, 12], [38, 3, 1, 4, 1], [14, 6, 7, 8, 7], [45, 8, 2, 11, 3], [12, 0, 4, 3, 4]], 1, 1, [7, 12, 9, 13]], [[14, 37], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]]]]
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 | [[5, 7, 11], 5, 1] | [[5, 7, 11], 9, 2] | Failed |
| case 1 | [[3, 4, 10, 17, 29, 49], 1, 0] | [[4], 5, 1] | Failed |
| case 2 | [[13, 29, 33], 5, 1] | [[13, 29, 33], 17, 2] | Failed |
| case 3 | [[20, 22, 29, 30, 35], 1, 0] | [[29], 5, 1] | Failed |
| case 4 | [[14, 17, 21, 31, 33], 1, 0] | [[14], 5, 1] | Failed |
| case 5 | [[47], 9, 2] | [[47], 9, 2] | Passed |
| case 6 | [[9, 21, 32, 44, 45], 1, 0] | [[21], 5, 1] | Failed |
| case 7 | [[13, 19, 28, 34, 36, 41], 5, 1] | [[13, 19, 28, 34, 36, 41], 5, 1] | Passed |
SHA-256 / f06cb32ded958b48829b1eb114c850679b6ead504c47390bbe55d6aaf80be812
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
def make(x, y, s, d):
return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
def child_index(n, o):
h = n['s'] / 2
mx, my = n['x'] + h, n['y'] + h
if o[3] < mx:
cx = 0
elif o[1] >= mx:
cx = 1
else:
return -1
if o[4] < my:
cy = 0
elif o[2] >= my:
cy = 1
else:
return -1
return cy * 2 + cx
def split(n):
h = n['s'] / 2
n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
old, n['objs'] = n['objs'], []
for o in old:
insert(n, o)
def insert(n, o):
if n['kids'] is not None:
k = child_index(n, o)
if k >= 0:
insert(n['kids'][k], o)
return
n['objs'].append(o)
if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
split(n)
root = make(0, 0, 16, 0)
for o in objs:
insert(root, o)
found, count, deep = [], 0, 0
stack = [root]
while stack:
n = stack.pop()
count += 1
deep = max(deep, n['d'])
if n['kids']:
stack.extend(n['kids'])
if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
found.extend(o[0] for o in n['objs'])
return [sorted(found), count, deep]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]], [[[[17, 1, 8, 3, 8], [10, 5, 2, 6, 2], [49, 4, 10, 5, 12], [3, 14, 4, 14, 4], [4, 11, 7, 13, 8], [29, 10, 1, 13, 1]], 1, 1, [12, 11, 16, 16]], [[4], 5, 1]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 13, 10, 14, 12], [22, 15, 13, 16, 13], [29, 6, 6, 8, 6], [35, 4, 3, 7, 4], [20, 6, 0, 6, 0]], 2, 1, [10, 1, 14, 3]], [[29], 5, 1]], [[[[21, 6, 5, 6, 7], [31, 7, 11, 7, 12], [17, 1, 8, 3, 9], [14, 10, 14, 12, 14], [33, 4, 15, 6, 16]], 1, 1, [12, 10, 12, 15]], [[14], 5, 1]], [[[[28, 12, 2, 15, 5], [6, 4, 1, 6, 4], [47, 4, 10, 6, 11], [49, 8, 9, 9, 10], [41, 12, 4, 14, 7]], 1, 3, [2, 10, 5, 10]], [[47], 9, 2]], [[[[32, 9, 1, 11, 3], [9, 7, 15, 7, 16], [44, 9, 8, 10, 8], [45, 9, 10, 12, 12], [21, 6, 0, 9, 1]], 2, 1, [3, 6, 3, 7]], [[21], 5, 1]], [[[[48, 14, 14, 16, 16], [19, 15, 3, 15, 4], [34, 0, 5, 2, 8], [13, 5, 1, 8, 1], [21, 1, 15, 3, 15], [36, 5, 6, 7, 8], [28, 15, 2, 16, 5], [41, 4, 7, 6, 10]], 2, 3, [8, 2, 13, 6]], [[13, 19, 28, 34, 36, 41], 5, 1]]], [[[[[48, 15, 14, 16, 14], [2, 2, 13, 4, 15], [30, 0, 0, 3, 0], [43, 5, 5, 8, 8], [24, 7, 13, 7, 14]], 1, 1, [5, 3, 7, 6]], [[30, 43], 5, 1]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]], [[[[28, 15, 10, 15, 13], [3, 14, 15, 16, 16], [23, 15, 9, 16, 10], [7, 13, 13, 13, 15], [16, 6, 8, 6, 9]], 2, 2, [3, 13, 3, 18]], [[16], 9, 2]], [[[[16, 3, 6, 3, 6], [36, 2, 1, 3, 3], [34, 11, 1, 14, 3], [2, 15, 9, 16, 10], [48, 5, 3, 8, 3], [41, 1, 7, 3, 8], [17, 7, 6, 7, 8]], 1, 1, [2, 10, 4, 10]], [[17, 41, 48], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[49, 11, 10, 11, 10], [12, 1, 6, 1, 8], [45, 15, 11, 16, 11], [8, 13, 12, 14, 14], [47, 10, 8, 10, 9]], 1, 1, [4, 10, 7, 10]], [[12], 5, 1]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]]], [[[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]], [[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[48, 13, 12, 14, 14], [15, 12, 15, 12, 16], [38, 14, 3, 16, 4], [22, 3, 6, 5, 7], [6, 0, 0, 2, 0], [10, 5, 6, 8, 6], [47, 4, 7, 5, 10], [21, 2, 10, 5, 10], [45, 12, 2, 13, 2]], 1, 1, [11, 2, 15, 7]], [[10, 38, 45, 47], 5, 1]], [[[[30, 4, 13, 4, 14], [46, 0, 12, 2, 13], [14, 9, 15, 12, 16], [43, 11, 7, 14, 7], [12, 11, 3, 12, 6], [33, 9, 10, 12, 10], [48, 1, 11, 1, 13], [25, 11, 9, 13, 10], [49, 6, 6, 7, 7]], 2, 1, [14, 2, 19, 5]], [[12, 43], 5, 1]], [[[[46, 5, 8, 5, 9], [8, 1, 13, 2, 15], [38, 8, 6, 9, 8], [14, 1, 15, 3, 16], [36, 10, 8, 11, 9], [4, 12, 5, 12, 8], [48, 1, 10, 1, 11], [42, 10, 7, 12, 9], [26, 11, 14, 12, 16], [17, 10, 9, 10, 12]], 2, 1, [8, 9, 11, 13]], [[4, 8, 14, 17, 26, 36, 38, 42, 46, 48], 5, 1]], [[[[31, 9, 9, 10, 12], [13, 5, 15, 7, 16], [33, 0, 4, 3, 5]], 2, 1, [12, 12, 16, 15]], [[31], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[6, 7, 4, 7, 5], [25, 5, 5, 7, 6], [31, 14, 13, 14, 13], [13, 3, 13, 5, 16]], 2, 3, [14, 8, 19, 8]], [[31], 5, 1]]], [[[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]], [[[[29, 0, 6, 1, 7], [13, 7, 1, 7, 2], [45, 2, 2, 3, 2], [34, 3, 1, 3, 4], [46, 1, 6, 2, 8], [22, 5, 2, 5, 4]], 2, 1, [9, 11, 11, 14]], [[46], 5, 1]], [[[[30, 0, 15, 3, 15], [22, 7, 2, 10, 5], [39, 0, 4, 0, 6], [20, 13, 7, 15, 7], [28, 5, 8, 7, 10], [2, 9, 0, 9, 0], [25, 15, 15, 16, 16], [42, 1, 10, 4, 11], [6, 8, 8, 8, 10], [9, 11, 12, 12, 13]], 1, 2, [11, 5, 11, 6]], [[22], 17, 2]], [[[[35, 2, 3, 3, 6], [39, 15, 10, 15, 11], [1, 13, 12, 14, 15], [45, 5, 9, 8, 12], [48, 8, 14, 8, 14], [38, 8, 2, 11, 2], [37, 2, 11, 2, 12], [7, 12, 14, 15, 15]], 1, 2, [3, 6, 7, 7]], [[35, 45], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[33, 4, 7, 7, 9], [26, 8, 5, 11, 8], [49, 6, 11, 6, 12], [7, 2, 3, 3, 5]], 1, 1, [11, 12, 14, 13]], [[26, 33], 5, 1]]], [[[[[22, 7, 14, 9, 16], [33, 3, 15, 5, 16], [46, 7, 10, 7, 12], [43, 15, 13, 16, 15]], 2, 1, [2, 9, 3, 14]], [[22, 33, 46], 5, 1]], [[[[29, 8, 4, 11, 7], [45, 0, 12, 1, 15], [20, 14, 7, 16, 7], [39, 4, 12, 6, 14], [25, 9, 7, 10, 8], [12, 8, 8, 11, 9], [26, 11, 12, 13, 13], [1, 4, 15, 6, 16], [32, 7, 10, 10, 12], [11, 7, 4, 7, 4]], 3, 2, [8, 0, 13, 2]], [[11, 20, 25, 29, 32], 5, 1]], [[[[28, 10, 12, 10, 12], [22, 9, 7, 12, 7], [4, 14, 4, 14, 5], [2, 7, 14, 9, 15]], 1, 3, [12, 1, 13, 5]], [[2, 4, 22], 9, 2]], [[[[35, 5, 11, 7, 12], [47, 3, 4, 6, 4], [27, 15, 1, 16, 1], [43, 12, 11, 13, 14], [49, 3, 15, 3, 16], [38, 6, 8, 6, 9], [25, 5, 12, 6, 15], [5, 5, 2, 7, 3], [45, 13, 1, 13, 4], [23, 14, 1, 16, 3]], 2, 1, [2, 11, 4, 12]], [[25, 35, 38, 49], 5, 1]], [[[[37, 11, 9, 14, 12], [38, 3, 1, 4, 1], [14, 6, 7, 8, 7], [45, 8, 2, 11, 3], [12, 0, 4, 3, 4]], 1, 1, [7, 12, 9, 13]], [[14, 37], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]]]]
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 | [[5, 7, 11], 9, 2] | [[5, 7, 11], 9, 2] | Passed |
| case 1 | [[4], 5, 1] | [[4], 5, 1] | Passed |
| case 2 | [[13, 29, 33], 17, 2] | [[13, 29, 33], 17, 2] | Passed |
| case 3 | [[29], 5, 1] | [[29], 5, 1] | Passed |
| case 4 | [[14], 5, 1] | [[14], 5, 1] | Passed |
| case 5 | [[47], 9, 2] | [[47], 9, 2] | Passed |
| case 6 | [[21], 5, 1] | [[21], 5, 1] | Passed |
| case 7 | [[13, 19, 28, 34, 36, 41], 5, 1] | [[13, 19, 28, 34, 36, 41], 5, 1] | Passed |
SHA-256 / e3f63063b7f9ed651b35875deae86aa2f08ace8003076a7f4e8bcc75c4772419
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:50:59.260306+00:00.
Case digest / e8d5742cb4b11d8ebb675b736ebe37e490a61caf256b864188ab2d8ba9283825