FA-87616 / Collision detection broadphase / Open access
First y boundary ignores the ray origin · case 01
Rays that do not start at y=0 cross rows at wrong times.
ROOT CAUSE
tMaxY = (iy+1)*cs/d[1] drops the origin term.
VERIFIED REPAIR
Subtract the origin: ((iy+1)*cs - o[1])/d[1].
Unsuccessful approach: Subtracting the x origin uses the wrong axis.
Case contract
solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].
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(o, d, cs, max_t):
ix, iy = math.floor(o[0] / cs), math.floor(o[1] / cs)
sx = 1 if d[0] > 0 else (-1 if d[0] < 0 else 0)
sy = 1 if d[1] > 0 else (-1 if d[1] < 0 else 0)
inf = float('inf')
if sx > 0:
tmx = ((ix + 1) * cs - o[0]) / d[0]
elif sx < 0:
tmx = (ix * cs - o[0]) / d[0]
else:
tmx = inf
if sy > 0:
tmy = ((iy + 1) * cs) / d[1]
elif sy < 0:
tmy = (iy * cs - o[1]) / d[1]
else:
tmy = inf
tdx = cs / abs(d[0]) if sx else inf
tdy = cs / abs(d[1]) if sy else inf
cells = [[ix, iy]]
while len(cells) < 64:
if tmx <= tmy:
t, ax = tmx, 0
else:
t, ax = tmy, 1
if t > max_t:
break
if ax == 0:
ix += sx
tmx += tdx
else:
iy += sy
tmy += tdy
cells.append([ix, iy])
return cells
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[-1.25, -0.75], [1, 1], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1]]], [[[0.0, 1.0], [1, 2], 1.0, 3.0], [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]]], [[[-1.5, 0.0], [-4, 0], 1.0, 2.0], [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]]], [[[-2.0, 1.75], [-1, -2], 1.0, 1.0], [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]]], [[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[-1.25, 1.5], [-4, 2], 0.5, 3.0], [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]]], [[[-1.75, 1.75], [-2, 4], 1.0, 0.5], [[-2, 1], [-2, 2], [-3, 2], [-3, 3]]], [[[0.0, 1.25], [1, 2], 0.5, 3.0], [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]]]], [[[[0.0, 0.25], [2, 4], 2.0, 3.0], [[0, 0], [0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6]]], [[[-0.25, -0.5], [-2, 2], 0.5, 2.0], [[-1, -1], [-2, -1], [-2, 0], [-3, 0], [-3, 1], [-4, 1], [-4, 2], [-5, 2], [-5, 3], [-6, 3], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-8, 6], [-9, 6], [-9, 7]]], [[[-0.75, 0.0], [-2, 0], 2.0, 0.5], [[-1, 0]]], [[[1.25, 1.25], [0, 1], 1.0, 2.0], [[1, 1], [1, 2], [1, 3]]], [[[-1.25, -1.25], [-1, 1], 1.0, 2.0], [[-2, -2], [-2, -1], [-3, -1], [-3, 0], [-4, 0]]], [[[-1.75, 1.5], [4, 0], 0.5, 3.0], [[-4, 3], [-3, 3], [-2, 3], [-1, 3], [0, 3], [1, 3], [2, 3], [3, 3], [4, 3], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [10, 3], [11, 3], [12, 3], [13, 3], [14, 3], [15, 3], [16, 3], [17, 3], [18, 3], [19, 3], [20, 3]]], [[[-1.5, 0.5], [-4, 2], 1.0, 1.0], [[-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-5, 2], [-6, 2]]], [[[1.75, 0.25], [2, 2], 1.0, 3.0], [[1, 0], [2, 0], [2, 1], [3, 1], [3, 2], [4, 2], [4, 3], [5, 3], [5, 4], [6, 4], [6, 5], [7, 5], [7, 6]]]], [[[[1.25, 0.5], [-2, -2], 1.0, 1.0], [[1, 0], [0, 0], [0, -1], [-1, -1], [-1, -2]]], [[[-0.25, 1.0], [1, 4], 2.0, 2.0], [[-1, 0], [0, 0], [0, 1], [0, 2], [0, 3], [0, 4]]], [[[1.0, -2.0], [-1, 1], 2.0, 2.0], [[0, -1], [-1, -1], [-1, 0]]], [[[-0.25, -0.75], [-2, 1], 2.0, 2.0], [[-1, -1], [-1, 0], [-2, 0], [-3, 0]]], [[[1.75, 0.75], [-1, 2], 1.0, 0.5], [[1, 0], [1, 1]]], [[[-1.75, 0.0], [-2, 1], 2.0, 3.0], [[-1, 0], [-2, 0], [-3, 0], [-3, 1], [-4, 1]]], [[[1.75, -1.5], [4, 2], 2.0, 2.0], [[0, -1], [1, -1], [2, -1], [2, 0], [3, 0], [4, 0], [4, 1]]], [[[-0.75, -0.5], [2, 1], 2.0, 0.5], [[-1, -1], [0, -1], [0, 0]]]], [[[[0.75, 0.25], [0, 1], 0.5, 3.0], [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]], [[[1.25, -2.0], [4, 4], 1.0, 0.5], [[1, -2], [2, -2], [2, -1], [3, -1], [3, 0]]], [[[-1.0, 0.75], [2, 4], 2.0, 1.0], [[-1, 0], [-1, 1], [0, 1], [0, 2]]], [[[-1.0, -0.75], [-2, 2], 1.0, 1.0], [[-1, -1], [-2, -1], [-2, 0], [-3, 0], [-3, 1], [-4, 1]]], [[[-0.75, -1.0], [2, -2], 1.0, 2.0], [[-1, -1], [-1, -2], [0, -2], [0, -3], [1, -3], [1, -4], [2, -4], [2, -5], [3, -5], [3, -6]]], [[[2.0, -1.75], [0, 1], 1.0, 3.0], [[2, -2], [2, -1], [2, 0], [2, 1]]], [[[-1.0, 0.75], [2, 0], 0.5, 1.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[0.75, -1.5], [-1, -2], 1.0, 3.0], [[0, -2], [0, -3], [-1, -3], [-1, -4], [-1, -5], [-2, -5], [-2, -6], [-2, -7], [-3, -7], [-3, -8]]]], [[[[1.5, 0.25], [2, -1], 0.5, 2.0], [[3, 0], [4, 0], [4, -1], [5, -1], [6, -1], [6, -2], [7, -2], [8, -2], [8, -3], [9, -3], [10, -3], [10, -4], [11, -4]]], [[[-0.75, -1.0], [-4, 1], 1.0, 1.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1], [-5, -1], [-5, 0]]], [[[2.0, 0.0], [-2, -2], 0.5, 1.0], [[4, 0], [3, 0], [3, -1], [2, -1], [2, -2], [1, -2], [1, -3], [0, -3], [0, -4], [-1, -4], [-1, -5]]], [[[-0.25, -0.75], [0, 1], 1.0, 3.0], [[-1, -1], [-1, 0], [-1, 1], [-1, 2]]], [[[1.25, 2.0], [2, -2], 2.0, 2.0], [[0, 1], [0, 0], [1, 0], [1, -1], [2, -1], [2, -2]]], [[[-1.75, -0.25], [2, 2], 2.0, 0.5], [[-1, -1], [-1, 0]]], [[[-2.0, -2.0], [0, 2], 0.5, 0.5], [[-4, -4], [-4, -3], [-4, -2]]], [[[-1.25, -0.25], [4, 4], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1], [1, 1], [1, 2], [2, 2], [2, 3], [3, 3], [3, 4], [4, 4], [4, 5], [5, 5]]]]]
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 | [[-1, -1], [-1, 0], [0, 0], [0, 1]] | [[-1, -1], [-1, 0], [0, 0], [0, 1]] | Passed |
| case 1 | [[0, 1], [1, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [3, 6]] | [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]] | Failed |
| case 2 | [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]] | [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]] | Passed |
| case 3 | [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]] | [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]] | Passed |
| case 4 | [[-1, -3], [-1, -2], [-1, -1], [-1, 0], [-2, 0], [-2, 1], [-2, 2]] | [[-1, -3], [-1, -2], [-2, -2], [-2, -1]] | Failed |
| case 5 | [[-3, 3], [-4, 3], [-5, 3], [-6, 3], [-7, 3], [-8, 3], [-9, 3], [-10, 3], [-11, 3], [-11, 4], [-12, 4], [-13, 4], [-13, 5], [-14, 5], [-15, 5], [-15, 6], [-16, 6], [-17, 6], [-17, 7], [-18, 7], [-19, 7], [-19, 8], [-20, 8], [-21, 8], [-21, 9], [-22, 9], [-23, 9], [-23, 10], [-24, 10], [-25, 10], [-25, 11], [-26, 11], [-27, 11], [-27, 12]] | [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]] | Failed |
| case 6 | [[-2, 1], [-3, 1], [-3, 2]] | [[-2, 1], [-2, 2], [-3, 2], [-3, 3]] | Failed |
| case 7 | [[0, 2], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [3, 6], [3, 7], [4, 7], [4, 8], [4, 9], [5, 9], [5, 10], [5, 11], [6, 11], [6, 12]] | [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]] | Failed |
SHA-256 / d132196393bdff6fc43a212d62b236775d4f5cdf3c5001c3b85c1890c34f0862
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(o, d, cs, max_t):
ix, iy = math.floor(o[0] / cs), math.floor(o[1] / cs)
sx = 1 if d[0] > 0 else (-1 if d[0] < 0 else 0)
sy = 1 if d[1] > 0 else (-1 if d[1] < 0 else 0)
inf = float('inf')
if sx > 0:
tmx = ((ix + 1) * cs - o[0]) / d[0]
elif sx < 0:
tmx = (ix * cs - o[0]) / d[0]
else:
tmx = inf
if sy > 0:
tmy = ((iy + 1) * cs - o[0]) / d[1]
elif sy < 0:
tmy = (iy * cs - o[1]) / d[1]
else:
tmy = inf
tdx = cs / abs(d[0]) if sx else inf
tdy = cs / abs(d[1]) if sy else inf
cells = [[ix, iy]]
while len(cells) < 64:
if tmx <= tmy:
t, ax = tmx, 0
else:
t, ax = tmy, 1
if t > max_t:
break
if ax == 0:
ix += sx
tmx += tdx
else:
iy += sy
tmy += tdy
cells.append([ix, iy])
return cells
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[-1.25, -0.75], [1, 1], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1]]], [[[0.0, 1.0], [1, 2], 1.0, 3.0], [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]]], [[[-1.5, 0.0], [-4, 0], 1.0, 2.0], [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]]], [[[-2.0, 1.75], [-1, -2], 1.0, 1.0], [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]]], [[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[-1.25, 1.5], [-4, 2], 0.5, 3.0], [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]]], [[[-1.75, 1.75], [-2, 4], 1.0, 0.5], [[-2, 1], [-2, 2], [-3, 2], [-3, 3]]], [[[0.0, 1.25], [1, 2], 0.5, 3.0], [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]]]], [[[[0.0, 0.25], [2, 4], 2.0, 3.0], [[0, 0], [0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6]]], [[[-0.25, -0.5], [-2, 2], 0.5, 2.0], [[-1, -1], [-2, -1], [-2, 0], [-3, 0], [-3, 1], [-4, 1], [-4, 2], [-5, 2], [-5, 3], [-6, 3], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-8, 6], [-9, 6], [-9, 7]]], [[[-0.75, 0.0], [-2, 0], 2.0, 0.5], [[-1, 0]]], [[[1.25, 1.25], [0, 1], 1.0, 2.0], [[1, 1], [1, 2], [1, 3]]], [[[-1.25, -1.25], [-1, 1], 1.0, 2.0], [[-2, -2], [-2, -1], [-3, -1], [-3, 0], [-4, 0]]], [[[-1.75, 1.5], [4, 0], 0.5, 3.0], [[-4, 3], [-3, 3], [-2, 3], [-1, 3], [0, 3], [1, 3], [2, 3], [3, 3], [4, 3], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [10, 3], [11, 3], [12, 3], [13, 3], [14, 3], [15, 3], [16, 3], [17, 3], [18, 3], [19, 3], [20, 3]]], [[[-1.5, 0.5], [-4, 2], 1.0, 1.0], [[-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-5, 2], [-6, 2]]], [[[1.75, 0.25], [2, 2], 1.0, 3.0], [[1, 0], [2, 0], [2, 1], [3, 1], [3, 2], [4, 2], [4, 3], [5, 3], [5, 4], [6, 4], [6, 5], [7, 5], [7, 6]]]], [[[[1.25, 0.5], [-2, -2], 1.0, 1.0], [[1, 0], [0, 0], [0, -1], [-1, -1], [-1, -2]]], [[[-0.25, 1.0], [1, 4], 2.0, 2.0], [[-1, 0], [0, 0], [0, 1], [0, 2], [0, 3], [0, 4]]], [[[1.0, -2.0], [-1, 1], 2.0, 2.0], [[0, -1], [-1, -1], [-1, 0]]], [[[-0.25, -0.75], [-2, 1], 2.0, 2.0], [[-1, -1], [-1, 0], [-2, 0], [-3, 0]]], [[[1.75, 0.75], [-1, 2], 1.0, 0.5], [[1, 0], [1, 1]]], [[[-1.75, 0.0], [-2, 1], 2.0, 3.0], [[-1, 0], [-2, 0], [-3, 0], [-3, 1], [-4, 1]]], [[[1.75, -1.5], [4, 2], 2.0, 2.0], [[0, -1], [1, -1], [2, -1], [2, 0], [3, 0], [4, 0], [4, 1]]], [[[-0.75, -0.5], [2, 1], 2.0, 0.5], [[-1, -1], [0, -1], [0, 0]]]], [[[[0.75, 0.25], [0, 1], 0.5, 3.0], [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]], [[[1.25, -2.0], [4, 4], 1.0, 0.5], [[1, -2], [2, -2], [2, -1], [3, -1], [3, 0]]], [[[-1.0, 0.75], [2, 4], 2.0, 1.0], [[-1, 0], [-1, 1], [0, 1], [0, 2]]], [[[-1.0, -0.75], [-2, 2], 1.0, 1.0], [[-1, -1], [-2, -1], [-2, 0], [-3, 0], [-3, 1], [-4, 1]]], [[[-0.75, -1.0], [2, -2], 1.0, 2.0], [[-1, -1], [-1, -2], [0, -2], [0, -3], [1, -3], [1, -4], [2, -4], [2, -5], [3, -5], [3, -6]]], [[[2.0, -1.75], [0, 1], 1.0, 3.0], [[2, -2], [2, -1], [2, 0], [2, 1]]], [[[-1.0, 0.75], [2, 0], 0.5, 1.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[0.75, -1.5], [-1, -2], 1.0, 3.0], [[0, -2], [0, -3], [-1, -3], [-1, -4], [-1, -5], [-2, -5], [-2, -6], [-2, -7], [-3, -7], [-3, -8]]]], [[[[1.5, 0.25], [2, -1], 0.5, 2.0], [[3, 0], [4, 0], [4, -1], [5, -1], [6, -1], [6, -2], [7, -2], [8, -2], [8, -3], [9, -3], [10, -3], [10, -4], [11, -4]]], [[[-0.75, -1.0], [-4, 1], 1.0, 1.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1], [-5, -1], [-5, 0]]], [[[2.0, 0.0], [-2, -2], 0.5, 1.0], [[4, 0], [3, 0], [3, -1], [2, -1], [2, -2], [1, -2], [1, -3], [0, -3], [0, -4], [-1, -4], [-1, -5]]], [[[-0.25, -0.75], [0, 1], 1.0, 3.0], [[-1, -1], [-1, 0], [-1, 1], [-1, 2]]], [[[1.25, 2.0], [2, -2], 2.0, 2.0], [[0, 1], [0, 0], [1, 0], [1, -1], [2, -1], [2, -2]]], [[[-1.75, -0.25], [2, 2], 2.0, 0.5], [[-1, -1], [-1, 0]]], [[[-2.0, -2.0], [0, 2], 0.5, 0.5], [[-4, -4], [-4, -3], [-4, -2]]], [[[-1.25, -0.25], [4, 4], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1], [1, 1], [1, 2], [2, 2], [2, 3], [3, 3], [3, 4], [4, 4], [4, 5], [5, 5]]]]]
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 | [[-1, -1], [0, -1], [0, 0]] | [[-1, -1], [-1, 0], [0, 0], [0, 1]] | Failed |
| case 1 | [[0, 1], [1, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [3, 6]] | [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]] | Failed |
| case 2 | [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]] | [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]] | Passed |
| case 3 | [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]] | [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]] | Passed |
| case 4 | [[-1, -3], [-1, -2], [-1, -1], [-1, 0], [-2, 0], [-2, 1]] | [[-1, -3], [-1, -2], [-2, -2], [-2, -1]] | Failed |
| case 5 | [[-3, 3], [-4, 3], [-5, 3], [-6, 3], [-7, 3], [-8, 3], [-9, 3], [-10, 3], [-11, 3], [-12, 3], [-13, 3], [-14, 3], [-15, 3], [-16, 3], [-16, 4], [-17, 4], [-18, 4], [-18, 5], [-19, 5], [-20, 5], [-20, 6], [-21, 6], [-22, 6], [-22, 7], [-23, 7], [-24, 7], [-24, 8], [-25, 8], [-26, 8], [-26, 9], [-27, 9]] | [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]] | Failed |
| case 6 | [[-2, 1], [-3, 1]] | [[-2, 1], [-2, 2], [-3, 2], [-3, 3]] | Failed |
| case 7 | [[0, 2], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [3, 6], [3, 7], [4, 7], [4, 8], [4, 9], [5, 9], [5, 10], [5, 11], [6, 11], [6, 12]] | [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]] | Failed |
SHA-256 / 1c9b80206d3309ed8cfcaecdda9658fb34b610c116368ff1568e2eb6ac0da03f
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(o, d, cs, max_t):
ix, iy = math.floor(o[0] / cs), math.floor(o[1] / cs)
sx = 1 if d[0] > 0 else (-1 if d[0] < 0 else 0)
sy = 1 if d[1] > 0 else (-1 if d[1] < 0 else 0)
inf = float('inf')
if sx > 0:
tmx = ((ix + 1) * cs - o[0]) / d[0]
elif sx < 0:
tmx = (ix * cs - o[0]) / d[0]
else:
tmx = inf
if sy > 0:
tmy = ((iy + 1) * cs - o[1]) / d[1]
elif sy < 0:
tmy = (iy * cs - o[1]) / d[1]
else:
tmy = inf
tdx = cs / abs(d[0]) if sx else inf
tdy = cs / abs(d[1]) if sy else inf
cells = [[ix, iy]]
while len(cells) < 64:
if tmx <= tmy:
t, ax = tmx, 0
else:
t, ax = tmy, 1
if t > max_t:
break
if ax == 0:
ix += sx
tmx += tdx
else:
iy += sy
tmy += tdy
cells.append([ix, iy])
return cells
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[-1.25, -0.75], [1, 1], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1]]], [[[0.0, 1.0], [1, 2], 1.0, 3.0], [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]]], [[[-1.5, 0.0], [-4, 0], 1.0, 2.0], [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]]], [[[-2.0, 1.75], [-1, -2], 1.0, 1.0], [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]]], [[[-0.25, -1.25], [-1, 2], 0.5, 0.5], [[-1, -3], [-1, -2], [-2, -2], [-2, -1]]], [[[-1.25, 1.5], [-4, 2], 0.5, 3.0], [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]]], [[[-1.75, 1.75], [-2, 4], 1.0, 0.5], [[-2, 1], [-2, 2], [-3, 2], [-3, 3]]], [[[0.0, 1.25], [1, 2], 0.5, 3.0], [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]]]], [[[[0.0, 0.25], [2, 4], 2.0, 3.0], [[0, 0], [0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6]]], [[[-0.25, -0.5], [-2, 2], 0.5, 2.0], [[-1, -1], [-2, -1], [-2, 0], [-3, 0], [-3, 1], [-4, 1], [-4, 2], [-5, 2], [-5, 3], [-6, 3], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-8, 6], [-9, 6], [-9, 7]]], [[[-0.75, 0.0], [-2, 0], 2.0, 0.5], [[-1, 0]]], [[[1.25, 1.25], [0, 1], 1.0, 2.0], [[1, 1], [1, 2], [1, 3]]], [[[-1.25, -1.25], [-1, 1], 1.0, 2.0], [[-2, -2], [-2, -1], [-3, -1], [-3, 0], [-4, 0]]], [[[-1.75, 1.5], [4, 0], 0.5, 3.0], [[-4, 3], [-3, 3], [-2, 3], [-1, 3], [0, 3], [1, 3], [2, 3], [3, 3], [4, 3], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [10, 3], [11, 3], [12, 3], [13, 3], [14, 3], [15, 3], [16, 3], [17, 3], [18, 3], [19, 3], [20, 3]]], [[[-1.5, 0.5], [-4, 2], 1.0, 1.0], [[-2, 0], [-3, 0], [-3, 1], [-4, 1], [-5, 1], [-5, 2], [-6, 2]]], [[[1.75, 0.25], [2, 2], 1.0, 3.0], [[1, 0], [2, 0], [2, 1], [3, 1], [3, 2], [4, 2], [4, 3], [5, 3], [5, 4], [6, 4], [6, 5], [7, 5], [7, 6]]]], [[[[1.25, 0.5], [-2, -2], 1.0, 1.0], [[1, 0], [0, 0], [0, -1], [-1, -1], [-1, -2]]], [[[-0.25, 1.0], [1, 4], 2.0, 2.0], [[-1, 0], [0, 0], [0, 1], [0, 2], [0, 3], [0, 4]]], [[[1.0, -2.0], [-1, 1], 2.0, 2.0], [[0, -1], [-1, -1], [-1, 0]]], [[[-0.25, -0.75], [-2, 1], 2.0, 2.0], [[-1, -1], [-1, 0], [-2, 0], [-3, 0]]], [[[1.75, 0.75], [-1, 2], 1.0, 0.5], [[1, 0], [1, 1]]], [[[-1.75, 0.0], [-2, 1], 2.0, 3.0], [[-1, 0], [-2, 0], [-3, 0], [-3, 1], [-4, 1]]], [[[1.75, -1.5], [4, 2], 2.0, 2.0], [[0, -1], [1, -1], [2, -1], [2, 0], [3, 0], [4, 0], [4, 1]]], [[[-0.75, -0.5], [2, 1], 2.0, 0.5], [[-1, -1], [0, -1], [0, 0]]]], [[[[0.75, 0.25], [0, 1], 0.5, 3.0], [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]], [[[1.25, -2.0], [4, 4], 1.0, 0.5], [[1, -2], [2, -2], [2, -1], [3, -1], [3, 0]]], [[[-1.0, 0.75], [2, 4], 2.0, 1.0], [[-1, 0], [-1, 1], [0, 1], [0, 2]]], [[[-1.0, -0.75], [-2, 2], 1.0, 1.0], [[-1, -1], [-2, -1], [-2, 0], [-3, 0], [-3, 1], [-4, 1]]], [[[-0.75, -1.0], [2, -2], 1.0, 2.0], [[-1, -1], [-1, -2], [0, -2], [0, -3], [1, -3], [1, -4], [2, -4], [2, -5], [3, -5], [3, -6]]], [[[2.0, -1.75], [0, 1], 1.0, 3.0], [[2, -2], [2, -1], [2, 0], [2, 1]]], [[[-1.0, 0.75], [2, 0], 0.5, 1.0], [[-2, 1], [-1, 1], [0, 1], [1, 1], [2, 1]]], [[[0.75, -1.5], [-1, -2], 1.0, 3.0], [[0, -2], [0, -3], [-1, -3], [-1, -4], [-1, -5], [-2, -5], [-2, -6], [-2, -7], [-3, -7], [-3, -8]]]], [[[[1.5, 0.25], [2, -1], 0.5, 2.0], [[3, 0], [4, 0], [4, -1], [5, -1], [6, -1], [6, -2], [7, -2], [8, -2], [8, -3], [9, -3], [10, -3], [10, -4], [11, -4]]], [[[-0.75, -1.0], [-4, 1], 1.0, 1.0], [[-1, -1], [-2, -1], [-3, -1], [-4, -1], [-5, -1], [-5, 0]]], [[[2.0, 0.0], [-2, -2], 0.5, 1.0], [[4, 0], [3, 0], [3, -1], [2, -1], [2, -2], [1, -2], [1, -3], [0, -3], [0, -4], [-1, -4], [-1, -5]]], [[[-0.25, -0.75], [0, 1], 1.0, 3.0], [[-1, -1], [-1, 0], [-1, 1], [-1, 2]]], [[[1.25, 2.0], [2, -2], 2.0, 2.0], [[0, 1], [0, 0], [1, 0], [1, -1], [2, -1], [2, -2]]], [[[-1.75, -0.25], [2, 2], 2.0, 0.5], [[-1, -1], [-1, 0]]], [[[-2.0, -2.0], [0, 2], 0.5, 0.5], [[-4, -4], [-4, -3], [-4, -2]]], [[[-1.25, -0.25], [4, 4], 2.0, 3.0], [[-1, -1], [-1, 0], [0, 0], [0, 1], [1, 1], [1, 2], [2, 2], [2, 3], [3, 3], [3, 4], [4, 4], [4, 5], [5, 5]]]]]
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 | [[-1, -1], [-1, 0], [0, 0], [0, 1]] | [[-1, -1], [-1, 0], [0, 0], [0, 1]] | Passed |
| case 1 | [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]] | [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [2, 6], [3, 6], [3, 7]] | Passed |
| case 2 | [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]] | [[-2, 0], [-3, 0], [-4, 0], [-5, 0], [-6, 0], [-7, 0], [-8, 0], [-9, 0], [-10, 0]] | Passed |
| case 3 | [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]] | [[-2, 1], [-3, 1], [-3, 0], [-3, -1], [-4, -1]] | Passed |
| case 4 | [[-1, -3], [-1, -2], [-2, -2], [-2, -1]] | [[-1, -3], [-1, -2], [-2, -2], [-2, -1]] | Passed |
| case 5 | [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]] | [[-3, 3], [-4, 3], [-5, 3], [-5, 4], [-6, 4], [-7, 4], [-7, 5], [-8, 5], [-9, 5], [-9, 6], [-10, 6], [-11, 6], [-11, 7], [-12, 7], [-13, 7], [-13, 8], [-14, 8], [-15, 8], [-15, 9], [-16, 9], [-17, 9], [-17, 10], [-18, 10], [-19, 10], [-19, 11], [-20, 11], [-21, 11], [-21, 12], [-22, 12], [-23, 12], [-23, 13], [-24, 13], [-25, 13], [-25, 14], [-26, 14], [-27, 14], [-27, 15]] | Passed |
| case 6 | [[-2, 1], [-2, 2], [-3, 2], [-3, 3]] | [[-2, 1], [-2, 2], [-3, 2], [-3, 3]] | Passed |
| case 7 | [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]] | [[0, 2], [0, 3], [0, 4], [1, 4], [1, 5], [1, 6], [2, 6], [2, 7], [2, 8], [3, 8], [3, 9], [3, 10], [4, 10], [4, 11], [4, 12], [5, 12], [5, 13], [5, 14], [6, 14]] | Passed |
SHA-256 / faff8f74cb6f924a075625723cf844470acf39ee54a61eab7ebd4ab1734cd946
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:00.494742+00:00.
Case digest / a3cedad19378f031c0f8a9faed3770f4b35642a51f153d6800797321947e60aa