FA-86621 / Procedural level generation constraints / Open access
Perfect maze validator: Diagonal passages validate · case 01
Mazes with diagonal openings pass validation.
ROOT CAUSE
Adjacency uses Chebyshev distance, accepting diagonals.
VERIFIED REPAIR
Restore `abs(x1 - x2) + abs(y1 - y2) != 1` at the adjacency test step.
Unsuccessful approach: Only rejecting distances above one lets self-loops through as loops rather than invalid edges.
Case contract
Cells (x, y) with 0 <= x < w, 0 <= y < h. First pass over passages [[x1, y1], [x2, y2]]: out-of-bounds or non-orthogonally-adjacent pairs -> 'invalid-edge'; the same passage twice in either orientation -> 'duplicate'. Then union passages in order: joining already connected cells -> 'loop'. Finally 'perfect' if all cells are connected, else 'disconnected'.
Why this case matters
Procedural generators silently emit unplayable or unfair levels when a single constraint check uses the wrong boundary, axis, neighborhood or update order; the defect is visible in exact generated geometry.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(w, h, passages):
seen = set()
parent = {(x, y): (x, y) for x in range(w) for y in range(h)}
def find(p):
while parent[p] != p:
parent[p] = parent[parent[p]]
p = parent[p]
return p
for (x1, y1), (x2, y2) in passages:
if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):
return 'invalid-edge'
if max(abs(x1 - x2), abs(y1 - y2)) != 1:
return 'invalid-edge'
key = tuple(sorted([(x1, y1), (x2, y2)]))
if key in seen:
return 'duplicate'
seen.add(key)
for (x1, y1), (x2, y2) in passages:
a, b = find((x1, y1)), find((x2, y2))
if a == b:
return 'loop'
parent[a] = b
roots = {find(p) for p in parent}
return 'perfect' if len(roots) == 1 else 'disconnected'
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[3,
4,
[[[1, 3], [1, 2]],
[[2, 1], [2, 2]],
[[2, 1], [1, 1]],
[[1, 2], [0, 2]],
[[0, 0], [1, 0]],
[[1, 2], [2, 3]],
[[1, 3], [0, 3]],
[[0, 2], [0, 3]],
[[0, 1], [1, 1]],
[[1, 1], [1, 0]],
[[2, 1], [2, 0]],
[[2, 3], [1, 3]],
[[2, 2], [1, 2]],
[[0, 0], [0, 1]]]],
'invalid-edge'),
('fault site adjacency test #2',
[4,
3,
[[[1, 2], [1, 1]],
[[0, 0], [1, 0]],
[[2, 0], [3, 1]],
[[1, 0], [2, 0]],
[[0, 2], [1, 2]],
[[3, 0], [3, 1]],
[[3, 0], [2, 0]],
[[0, 1], [0, 2]],
[[3, 2], [2, 2]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[0, 1], [0, 0]],
[[1, 0], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('partial repair boundary #1',
[4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]],
'invalid-edge'),
('partial repair boundary #2',
[3,
3,
[[[1, 0], [1, 0]],
[[1, 0], [2, 0]],
[[0, 2], [0, 1]],
[[2, 2], [2, 1]],
[[0, 2], [1, 2]],
[[1, 0], [0, 0]],
[[0, 1], [1, 1]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
3,
[[[1, 2], [1, 1]],
[[0, 0], [1, 0]],
[[2, 0], [3, 1]],
[[1, 0], [2, 0]],
[[0, 2], [1, 2]],
[[3, 0], [3, 1]],
[[3, 0], [2, 0]],
[[0, 1], [0, 2]],
[[3, 2], [2, 2]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[0, 1], [0, 0]],
[[1, 0], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('fault site adjacency test #2',
[2,
4,
[[[0, 1], [1, 2]],
[[1, 2], [1, 3]],
[[0, 1], [0, 2]],
[[0, 2], [0, 3]],
[[0, 1], [0, 0]],
[[0, 3], [1, 3]],
[[0, 1], [1, 1]]]],
'invalid-edge'),
('partial repair boundary #1',
[3,
4,
[[[1, 1], [1, 1]],
[[1, 3], [2, 3]],
[[2, 2], [2, 1]],
[[2, 0], [1, 0]],
[[1, 2], [2, 2]],
[[1, 2], [1, 3]],
[[1, 2], [0, 2]],
[[1, 2], [1, 1]],
[[0, 1], [1, 1]],
[[2, 2], [2, 3]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]]]],
'invalid-edge'),
('partial repair boundary #2',
[1, 3, [[[0, 0], [0, 0]], [[0, 0], [0, 1]], [[0, 1], [0, 2]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1', [2, 2, [[[1, 0], [0, 0]], [[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #2',
[4,
4,
[[[1, 1], [1, 0]],
[[3, 1], [3, 0]],
[[3, 1], [3, 2]],
[[0, 2], [1, 3]],
[[1, 1], [0, 1]],
[[1, 3], [0, 3]],
[[0, 1], [0, 2]],
[[0, 2], [0, 3]],
[[2, 3], [2, 2]],
[[1, 0], [2, 0]],
[[2, 1], [2, 0]],
[[0, 0], [0, 1]],
[[2, 2], [3, 2]],
[[1, 2], [0, 2]],
[[2, 3], [3, 3]]]],
'invalid-edge'),
('partial repair boundary #1',
[3,
3,
[[[1, 2], [0, 2]],
[[1, 0], [2, 0]],
[[0, 0], [0, 1]],
[[1, 1], [1, 0]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[0, 2], [0, 2]]]],
'invalid-edge'),
('partial repair boundary #2',
[2,
3,
[[[1, 1], [1, 0]],
[[0, 2], [0, 1]],
[[1, 1], [1, 2]],
[[1, 2], [1, 2]],
[[1, 1], [0, 1]],
[[0, 1], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
4,
[[[3, 3], [3, 2]],
[[2, 1], [1, 1]],
[[0, 1], [1, 1]],
[[0, 3], [0, 2]],
[[3, 3], [2, 3]],
[[0, 1], [0, 0]],
[[1, 1], [1, 0]],
[[3, 0], [3, 1]],
[[2, 2], [2, 1]],
[[1, 2], [1, 1]],
[[2, 0], [1, 0]],
[[3, 1], [3, 2]],
[[3, 1], [2, 1]],
[[2, 2], [3, 2]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[0, 2], [1, 3]]]],
'invalid-edge'),
('fault site adjacency test #2',
[4, 2, [[[2, 0], [2, 1]], [[2, 0], [3, 1]], [[0, 1], [0, 0]], [[1, 0], [0, 0]], [[1, 0], [2, 0]]]],
'invalid-edge'),
('partial repair boundary #1',
[3, 2, [[[0, 0], [0, 1]], [[1, 0], [1, 0]], [[1, 1], [2, 1]], [[1, 0], [2, 0]]]],
'invalid-edge'),
('partial repair boundary #2', [1, 4, [[[0, 1], [0, 1]]]], 'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[4,
3,
[[[1, 0], [1, 1]],
[[0, 1], [0, 0]],
[[0, 1], [0, 2]],
[[2, 0], [2, 1]],
[[1, 0], [0, 0]],
[[1, 0], [2, 0]],
[[2, 1], [2, 2]],
[[2, 2], [3, 2]],
[[2, 1], [3, 1]],
[[2, 2], [1, 2]],
[[1, 1], [0, 1]],
[[0, 2], [1, 2]]]],
'loop')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
2,
[[[1, 0], [2, 0]],
[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[2, 0], [2, 1]],
[[1, 0], [2, 1]],
[[2, 1], [1, 1]]]],
'invalid-edge'),
('fault site adjacency test #2', [2, 3, [[[0, 2], [0, 1]], [[0, 1], [1, 2]]]], 'invalid-edge'),
('partial repair boundary #1',
[4,
4,
[[[1, 1], [2, 1]],
[[2, 2], [3, 2]],
[[2, 1], [2, 0]],
[[2, 2], [1, 2]],
[[2, 0], [1, 0]],
[[0, 3], [0, 2]],
[[2, 2], [2, 1]],
[[1, 2], [0, 2]],
[[1, 3], [0, 3]],
[[2, 3], [1, 3]],
[[0, 0], [1, 0]],
[[2, 0], [2, 0]],
[[3, 2], [3, 3]],
[[3, 2], [3, 1]],
[[3, 0], [2, 0]],
[[2, 2], [2, 3]],
[[1, 1], [1, 0]],
[[0, 2], [0, 1]],
[[1, 2], [1, 3]]]],
'invalid-edge'),
('partial repair boundary #2',
[4, 2, [[[0, 0], [1, 0]], [[3, 0], [3, 0]], [[2, 0], [3, 0]], [[1, 1], [0, 1]], [[2, 0], [1, 0]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
'duplicate')]]
for label, args, expected in cases[N-1]:
check(label, 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 |
|---|---|---|---|
| diagonal passage #1 | disconnected | invalid-edge | Failed |
| fault site adjacency test #1 | loop | invalid-edge | Failed |
| fault site adjacency test #2 | duplicate | invalid-edge | Failed |
| partial repair boundary #1 | invalid-edge | invalid-edge | Passed |
| partial repair boundary #2 | invalid-edge | invalid-edge | Passed |
| reversed duplicate #1 | duplicate | duplicate | Passed |
| single cell maze #1 | perfect | perfect | Passed |
| control #1 | invalid-edge | invalid-edge | Passed |
SHA-256 / d2e565fb8864369df43b03dd4b3f8467815b81755db68151f2621eabe5f23305
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(w, h, passages):
seen = set()
parent = {(x, y): (x, y) for x in range(w) for y in range(h)}
def find(p):
while parent[p] != p:
parent[p] = parent[parent[p]]
p = parent[p]
return p
for (x1, y1), (x2, y2) in passages:
if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):
return 'invalid-edge'
if abs(x1 - x2) + abs(y1 - y2) > 1:
return 'invalid-edge'
key = tuple(sorted([(x1, y1), (x2, y2)]))
if key in seen:
return 'duplicate'
seen.add(key)
for (x1, y1), (x2, y2) in passages:
a, b = find((x1, y1)), find((x2, y2))
if a == b:
return 'loop'
parent[a] = b
roots = {find(p) for p in parent}
return 'perfect' if len(roots) == 1 else 'disconnected'
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[3,
4,
[[[1, 3], [1, 2]],
[[2, 1], [2, 2]],
[[2, 1], [1, 1]],
[[1, 2], [0, 2]],
[[0, 0], [1, 0]],
[[1, 2], [2, 3]],
[[1, 3], [0, 3]],
[[0, 2], [0, 3]],
[[0, 1], [1, 1]],
[[1, 1], [1, 0]],
[[2, 1], [2, 0]],
[[2, 3], [1, 3]],
[[2, 2], [1, 2]],
[[0, 0], [0, 1]]]],
'invalid-edge'),
('fault site adjacency test #2',
[4,
3,
[[[1, 2], [1, 1]],
[[0, 0], [1, 0]],
[[2, 0], [3, 1]],
[[1, 0], [2, 0]],
[[0, 2], [1, 2]],
[[3, 0], [3, 1]],
[[3, 0], [2, 0]],
[[0, 1], [0, 2]],
[[3, 2], [2, 2]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[0, 1], [0, 0]],
[[1, 0], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('partial repair boundary #1',
[4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]],
'invalid-edge'),
('partial repair boundary #2',
[3,
3,
[[[1, 0], [1, 0]],
[[1, 0], [2, 0]],
[[0, 2], [0, 1]],
[[2, 2], [2, 1]],
[[0, 2], [1, 2]],
[[1, 0], [0, 0]],
[[0, 1], [1, 1]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
3,
[[[1, 2], [1, 1]],
[[0, 0], [1, 0]],
[[2, 0], [3, 1]],
[[1, 0], [2, 0]],
[[0, 2], [1, 2]],
[[3, 0], [3, 1]],
[[3, 0], [2, 0]],
[[0, 1], [0, 2]],
[[3, 2], [2, 2]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[0, 1], [0, 0]],
[[1, 0], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('fault site adjacency test #2',
[2,
4,
[[[0, 1], [1, 2]],
[[1, 2], [1, 3]],
[[0, 1], [0, 2]],
[[0, 2], [0, 3]],
[[0, 1], [0, 0]],
[[0, 3], [1, 3]],
[[0, 1], [1, 1]]]],
'invalid-edge'),
('partial repair boundary #1',
[3,
4,
[[[1, 1], [1, 1]],
[[1, 3], [2, 3]],
[[2, 2], [2, 1]],
[[2, 0], [1, 0]],
[[1, 2], [2, 2]],
[[1, 2], [1, 3]],
[[1, 2], [0, 2]],
[[1, 2], [1, 1]],
[[0, 1], [1, 1]],
[[2, 2], [2, 3]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]]]],
'invalid-edge'),
('partial repair boundary #2',
[1, 3, [[[0, 0], [0, 0]], [[0, 0], [0, 1]], [[0, 1], [0, 2]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1', [2, 2, [[[1, 0], [0, 0]], [[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #2',
[4,
4,
[[[1, 1], [1, 0]],
[[3, 1], [3, 0]],
[[3, 1], [3, 2]],
[[0, 2], [1, 3]],
[[1, 1], [0, 1]],
[[1, 3], [0, 3]],
[[0, 1], [0, 2]],
[[0, 2], [0, 3]],
[[2, 3], [2, 2]],
[[1, 0], [2, 0]],
[[2, 1], [2, 0]],
[[0, 0], [0, 1]],
[[2, 2], [3, 2]],
[[1, 2], [0, 2]],
[[2, 3], [3, 3]]]],
'invalid-edge'),
('partial repair boundary #1',
[3,
3,
[[[1, 2], [0, 2]],
[[1, 0], [2, 0]],
[[0, 0], [0, 1]],
[[1, 1], [1, 0]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[0, 2], [0, 2]]]],
'invalid-edge'),
('partial repair boundary #2',
[2,
3,
[[[1, 1], [1, 0]],
[[0, 2], [0, 1]],
[[1, 1], [1, 2]],
[[1, 2], [1, 2]],
[[1, 1], [0, 1]],
[[0, 1], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
4,
[[[3, 3], [3, 2]],
[[2, 1], [1, 1]],
[[0, 1], [1, 1]],
[[0, 3], [0, 2]],
[[3, 3], [2, 3]],
[[0, 1], [0, 0]],
[[1, 1], [1, 0]],
[[3, 0], [3, 1]],
[[2, 2], [2, 1]],
[[1, 2], [1, 1]],
[[2, 0], [1, 0]],
[[3, 1], [3, 2]],
[[3, 1], [2, 1]],
[[2, 2], [3, 2]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[0, 2], [1, 3]]]],
'invalid-edge'),
('fault site adjacency test #2',
[4, 2, [[[2, 0], [2, 1]], [[2, 0], [3, 1]], [[0, 1], [0, 0]], [[1, 0], [0, 0]], [[1, 0], [2, 0]]]],
'invalid-edge'),
('partial repair boundary #1',
[3, 2, [[[0, 0], [0, 1]], [[1, 0], [1, 0]], [[1, 1], [2, 1]], [[1, 0], [2, 0]]]],
'invalid-edge'),
('partial repair boundary #2', [1, 4, [[[0, 1], [0, 1]]]], 'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[4,
3,
[[[1, 0], [1, 1]],
[[0, 1], [0, 0]],
[[0, 1], [0, 2]],
[[2, 0], [2, 1]],
[[1, 0], [0, 0]],
[[1, 0], [2, 0]],
[[2, 1], [2, 2]],
[[2, 2], [3, 2]],
[[2, 1], [3, 1]],
[[2, 2], [1, 2]],
[[1, 1], [0, 1]],
[[0, 2], [1, 2]]]],
'loop')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
2,
[[[1, 0], [2, 0]],
[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[2, 0], [2, 1]],
[[1, 0], [2, 1]],
[[2, 1], [1, 1]]]],
'invalid-edge'),
('fault site adjacency test #2', [2, 3, [[[0, 2], [0, 1]], [[0, 1], [1, 2]]]], 'invalid-edge'),
('partial repair boundary #1',
[4,
4,
[[[1, 1], [2, 1]],
[[2, 2], [3, 2]],
[[2, 1], [2, 0]],
[[2, 2], [1, 2]],
[[2, 0], [1, 0]],
[[0, 3], [0, 2]],
[[2, 2], [2, 1]],
[[1, 2], [0, 2]],
[[1, 3], [0, 3]],
[[2, 3], [1, 3]],
[[0, 0], [1, 0]],
[[2, 0], [2, 0]],
[[3, 2], [3, 3]],
[[3, 2], [3, 1]],
[[3, 0], [2, 0]],
[[2, 2], [2, 3]],
[[1, 1], [1, 0]],
[[0, 2], [0, 1]],
[[1, 2], [1, 3]]]],
'invalid-edge'),
('partial repair boundary #2',
[4, 2, [[[0, 0], [1, 0]], [[3, 0], [3, 0]], [[2, 0], [3, 0]], [[1, 1], [0, 1]], [[2, 0], [1, 0]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
'duplicate')]]
for label, args, expected in cases[N-1]:
check(label, 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 |
|---|---|---|---|
| diagonal passage #1 | invalid-edge | invalid-edge | Passed |
| fault site adjacency test #1 | invalid-edge | invalid-edge | Passed |
| fault site adjacency test #2 | invalid-edge | invalid-edge | Passed |
| partial repair boundary #1 | loop | invalid-edge | Failed |
| partial repair boundary #2 | loop | invalid-edge | Failed |
| reversed duplicate #1 | duplicate | duplicate | Passed |
| single cell maze #1 | perfect | perfect | Passed |
| control #1 | invalid-edge | invalid-edge | Passed |
SHA-256 / 27f34b96b2911766c10af56ab8254992cd36edb12224d0a737a31560df35c691
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(w, h, passages):
seen = set()
parent = {(x, y): (x, y) for x in range(w) for y in range(h)}
def find(p):
while parent[p] != p:
parent[p] = parent[parent[p]]
p = parent[p]
return p
for (x1, y1), (x2, y2) in passages:
if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):
return 'invalid-edge'
if abs(x1 - x2) + abs(y1 - y2) != 1:
return 'invalid-edge'
key = tuple(sorted([(x1, y1), (x2, y2)]))
if key in seen:
return 'duplicate'
seen.add(key)
for (x1, y1), (x2, y2) in passages:
a, b = find((x1, y1)), find((x2, y2))
if a == b:
return 'loop'
parent[a] = b
roots = {find(p) for p in parent}
return 'perfect' if len(roots) == 1 else 'disconnected'
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[3,
4,
[[[1, 3], [1, 2]],
[[2, 1], [2, 2]],
[[2, 1], [1, 1]],
[[1, 2], [0, 2]],
[[0, 0], [1, 0]],
[[1, 2], [2, 3]],
[[1, 3], [0, 3]],
[[0, 2], [0, 3]],
[[0, 1], [1, 1]],
[[1, 1], [1, 0]],
[[2, 1], [2, 0]],
[[2, 3], [1, 3]],
[[2, 2], [1, 2]],
[[0, 0], [0, 1]]]],
'invalid-edge'),
('fault site adjacency test #2',
[4,
3,
[[[1, 2], [1, 1]],
[[0, 0], [1, 0]],
[[2, 0], [3, 1]],
[[1, 0], [2, 0]],
[[0, 2], [1, 2]],
[[3, 0], [3, 1]],
[[3, 0], [2, 0]],
[[0, 1], [0, 2]],
[[3, 2], [2, 2]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[0, 1], [0, 0]],
[[1, 0], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('partial repair boundary #1',
[4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]],
'invalid-edge'),
('partial repair boundary #2',
[3,
3,
[[[1, 0], [1, 0]],
[[1, 0], [2, 0]],
[[0, 2], [0, 1]],
[[2, 2], [2, 1]],
[[0, 2], [1, 2]],
[[1, 0], [0, 0]],
[[0, 1], [1, 1]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
3,
[[[1, 2], [1, 1]],
[[0, 0], [1, 0]],
[[2, 0], [3, 1]],
[[1, 0], [2, 0]],
[[0, 2], [1, 2]],
[[3, 0], [3, 1]],
[[3, 0], [2, 0]],
[[0, 1], [0, 2]],
[[3, 2], [2, 2]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[0, 1], [0, 0]],
[[1, 0], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('fault site adjacency test #2',
[2,
4,
[[[0, 1], [1, 2]],
[[1, 2], [1, 3]],
[[0, 1], [0, 2]],
[[0, 2], [0, 3]],
[[0, 1], [0, 0]],
[[0, 3], [1, 3]],
[[0, 1], [1, 1]]]],
'invalid-edge'),
('partial repair boundary #1',
[3,
4,
[[[1, 1], [1, 1]],
[[1, 3], [2, 3]],
[[2, 2], [2, 1]],
[[2, 0], [1, 0]],
[[1, 2], [2, 2]],
[[1, 2], [1, 3]],
[[1, 2], [0, 2]],
[[1, 2], [1, 1]],
[[0, 1], [1, 1]],
[[2, 2], [2, 3]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]]]],
'invalid-edge'),
('partial repair boundary #2',
[1, 3, [[[0, 0], [0, 0]], [[0, 0], [0, 1]], [[0, 1], [0, 2]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1', [2, 2, [[[1, 0], [0, 0]], [[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #2',
[4,
4,
[[[1, 1], [1, 0]],
[[3, 1], [3, 0]],
[[3, 1], [3, 2]],
[[0, 2], [1, 3]],
[[1, 1], [0, 1]],
[[1, 3], [0, 3]],
[[0, 1], [0, 2]],
[[0, 2], [0, 3]],
[[2, 3], [2, 2]],
[[1, 0], [2, 0]],
[[2, 1], [2, 0]],
[[0, 0], [0, 1]],
[[2, 2], [3, 2]],
[[1, 2], [0, 2]],
[[2, 3], [3, 3]]]],
'invalid-edge'),
('partial repair boundary #1',
[3,
3,
[[[1, 2], [0, 2]],
[[1, 0], [2, 0]],
[[0, 0], [0, 1]],
[[1, 1], [1, 0]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[0, 2], [0, 2]]]],
'invalid-edge'),
('partial repair boundary #2',
[2,
3,
[[[1, 1], [1, 0]],
[[0, 2], [0, 1]],
[[1, 1], [1, 2]],
[[1, 2], [1, 2]],
[[1, 1], [0, 1]],
[[0, 1], [0, 0]],
[[1, 0], [1, 1]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
4,
[[[3, 3], [3, 2]],
[[2, 1], [1, 1]],
[[0, 1], [1, 1]],
[[0, 3], [0, 2]],
[[3, 3], [2, 3]],
[[0, 1], [0, 0]],
[[1, 1], [1, 0]],
[[3, 0], [3, 1]],
[[2, 2], [2, 1]],
[[1, 2], [1, 1]],
[[2, 0], [1, 0]],
[[3, 1], [3, 2]],
[[3, 1], [2, 1]],
[[2, 2], [3, 2]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[0, 2], [1, 3]]]],
'invalid-edge'),
('fault site adjacency test #2',
[4, 2, [[[2, 0], [2, 1]], [[2, 0], [3, 1]], [[0, 1], [0, 0]], [[1, 0], [0, 0]], [[1, 0], [2, 0]]]],
'invalid-edge'),
('partial repair boundary #1',
[3, 2, [[[0, 0], [0, 1]], [[1, 0], [1, 0]], [[1, 1], [2, 1]], [[1, 0], [2, 0]]]],
'invalid-edge'),
('partial repair boundary #2', [1, 4, [[[0, 1], [0, 1]]]], 'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[4,
3,
[[[1, 0], [1, 1]],
[[0, 1], [0, 0]],
[[0, 1], [0, 2]],
[[2, 0], [2, 1]],
[[1, 0], [0, 0]],
[[1, 0], [2, 0]],
[[2, 1], [2, 2]],
[[2, 2], [3, 2]],
[[2, 1], [3, 1]],
[[2, 2], [1, 2]],
[[1, 1], [0, 1]],
[[0, 2], [1, 2]]]],
'loop')],
[('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('fault site adjacency test #1',
[4,
2,
[[[1, 0], [2, 0]],
[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[2, 0], [2, 1]],
[[1, 0], [2, 1]],
[[2, 1], [1, 1]]]],
'invalid-edge'),
('fault site adjacency test #2', [2, 3, [[[0, 2], [0, 1]], [[0, 1], [1, 2]]]], 'invalid-edge'),
('partial repair boundary #1',
[4,
4,
[[[1, 1], [2, 1]],
[[2, 2], [3, 2]],
[[2, 1], [2, 0]],
[[2, 2], [1, 2]],
[[2, 0], [1, 0]],
[[0, 3], [0, 2]],
[[2, 2], [2, 1]],
[[1, 2], [0, 2]],
[[1, 3], [0, 3]],
[[2, 3], [1, 3]],
[[0, 0], [1, 0]],
[[2, 0], [2, 0]],
[[3, 2], [3, 3]],
[[3, 2], [3, 1]],
[[3, 0], [2, 0]],
[[2, 2], [2, 3]],
[[1, 1], [1, 0]],
[[0, 2], [0, 1]],
[[1, 2], [1, 3]]]],
'invalid-edge'),
('partial repair boundary #2',
[4, 2, [[[0, 0], [1, 0]], [[3, 0], [3, 0]], [[2, 0], [3, 0]], [[1, 1], [0, 1]], [[2, 0], [1, 0]]]],
'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('single cell maze #1', [1, 1, []], 'perfect'),
('control #1',
[4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
'duplicate')]]
for label, args, expected in cases[N-1]:
check(label, 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 |
|---|---|---|---|
| diagonal passage #1 | invalid-edge | invalid-edge | Passed |
| fault site adjacency test #1 | invalid-edge | invalid-edge | Passed |
| fault site adjacency test #2 | invalid-edge | invalid-edge | Passed |
| partial repair boundary #1 | invalid-edge | invalid-edge | Passed |
| partial repair boundary #2 | invalid-edge | invalid-edge | Passed |
| reversed duplicate #1 | duplicate | duplicate | Passed |
| single cell maze #1 | perfect | perfect | Passed |
| control #1 | invalid-edge | invalid-edge | Passed |
SHA-256 / d8a8499abb4b43f828d72efffd55b50cd3f18a4cb3a153bf5a973f825512509f
Verification & scope
Deterministic toy contract stipulated for this model; integer or exact arithmetic only, not a reproduction of any specific game engine. 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:51.241376+00:00.
Case digest / 4fc94e47569c288b0920e37722bcf7d49c4d412aa9f8c12306b8fab1a122375e