FA-86631 / Procedural level generation constraints / Open access
Perfect maze validator: Union links cells instead of roots · case 01
Connected mazes are reported as loops or disconnected.
ROOT CAUSE
The union step re-parents the endpoint cell instead of its root.
VERIFIED REPAIR
Restore `parent[a] = b` at the union linkage step.
Unsuccessful approach: Linking the endpoint to the other root still detaches the rest of its tree.
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 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[(x1, y1)] = (x2, y2)
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 = [[('regression union linkage #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'),
('regression union linkage #2',
[3,
3,
[[[2, 1], [2, 0]],
[[2, 0], [1, 0]],
[[0, 1], [0, 0]],
[[0, 1], [1, 1]],
[[1, 0], [1, 1]],
[[0, 0], [1, 0]],
[[0, 1], [0, 2]]]],
'loop'),
('regression union linkage #3',
[4,
2,
[[[1, 0], [0, 0]],
[[1, 0], [1, 1]],
[[3, 0], [2, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[1, 1], [0, 1]],
[[3, 1], [3, 0]]]],
'loop'),
('regression union linkage #4',
[4,
4,
[[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[1, 0], [2, 0]],
[[2, 1], [3, 1]],
[[1, 3], [2, 3]],
[[3, 3], [3, 2]],
[[0, 2], [0, 3]],
[[2, 1], [1, 1]],
[[2, 2], [2, 1]],
[[1, 3], [0, 3]],
[[1, 1], [1, 2]],
[[2, 0], [2, 1]],
[[2, 2], [2, 3]],
[[2, 3], [3, 3]],
[[1, 2], [2, 2]]]],
'loop'),
('diagonal passage #1', [2, 2, [[[0, 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')],
[('regression union linkage #1',
[4,
2,
[[[1, 0], [0, 0]],
[[1, 0], [1, 1]],
[[3, 0], [2, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[1, 1], [0, 1]],
[[3, 1], [3, 0]]]],
'loop'),
('regression union linkage #2',
[4,
4,
[[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[1, 0], [2, 0]],
[[2, 1], [3, 1]],
[[1, 3], [2, 3]],
[[3, 3], [3, 2]],
[[0, 2], [0, 3]],
[[2, 1], [1, 1]],
[[2, 2], [2, 1]],
[[1, 3], [0, 3]],
[[1, 1], [1, 2]],
[[2, 0], [2, 1]],
[[2, 2], [2, 3]],
[[2, 3], [3, 3]],
[[1, 2], [2, 2]]]],
'loop'),
('regression union linkage #3',
[3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
'perfect'),
('regression union linkage #4', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),
('single cell maze #1', [1, 1, []], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge'),
('control #2',
[4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
'duplicate')],
[('regression union linkage #1',
[3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
'perfect'),
('regression union linkage #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),
('regression union linkage #3',
[2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],
'loop'),
('regression union linkage #4',
[4,
3,
[[[1, 2], [0, 2]],
[[1, 1], [2, 1]],
[[3, 0], [2, 0]],
[[3, 1], [3, 0]],
[[3, 2], [3, 1]],
[[1, 1], [1, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[2, 1], [2, 0]],
[[0, 1], [1, 1]],
[[0, 0], [0, 1]],
[[0, 2], [0, 1]],
[[1, 2], [2, 2]]]],
'loop'),
('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'),
('control #2', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],
[('regression union linkage #1',
[2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],
'loop'),
('regression union linkage #2',
[4,
3,
[[[1, 2], [0, 2]],
[[1, 1], [2, 1]],
[[3, 0], [2, 0]],
[[3, 1], [3, 0]],
[[3, 2], [3, 1]],
[[1, 1], [1, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[2, 1], [2, 0]],
[[0, 1], [1, 1]],
[[0, 0], [0, 1]],
[[0, 2], [0, 1]],
[[1, 2], [2, 2]]]],
'loop'),
('regression union linkage #3',
[4,
4,
[[[1, 1], [1, 2]],
[[3, 1], [2, 1]],
[[0, 2], [1, 2]],
[[0, 0], [0, 1]],
[[0, 2], [0, 3]],
[[1, 1], [1, 0]],
[[1, 1], [2, 1]],
[[1, 0], [2, 0]],
[[1, 3], [1, 2]],
[[2, 1], [2, 0]],
[[3, 1], [3, 0]],
[[0, 0], [1, 0]],
[[3, 2], [3, 1]]]],
'loop'),
('regression union linkage #4', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('control #1',
[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'),
('control #2',
[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')],
[('regression union linkage #1',
[4,
4,
[[[1, 1], [1, 2]],
[[3, 1], [2, 1]],
[[0, 2], [1, 2]],
[[0, 0], [0, 1]],
[[0, 2], [0, 3]],
[[1, 1], [1, 0]],
[[1, 1], [2, 1]],
[[1, 0], [2, 0]],
[[1, 3], [1, 2]],
[[2, 1], [2, 0]],
[[3, 1], [3, 0]],
[[0, 0], [1, 0]],
[[3, 2], [3, 1]]]],
'loop'),
('regression union linkage #2', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),
('regression union linkage #3',
[4,
2,
[[[2, 0], [2, 1]],
[[1, 0], [0, 0]],
[[0, 1], [0, 0]],
[[2, 1], [1, 1]],
[[2, 0], [1, 0]],
[[1, 0], [1, 1]]]],
'loop'),
('regression union linkage #4',
[3, 2, [[[1, 1], [2, 1]], [[0, 0], [1, 0]], [[2, 1], [2, 0]], [[0, 0], [0, 1]], [[1, 0], [2, 0]]]],
'perfect'),
('single cell maze #1', [1, 1, []], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('control #1', [2, 1, []], 'disconnected'),
('control #2', [1, 2, [[[0, 0], [0, 1]]]], 'perfect')]]
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 |
|---|---|---|---|
| regression union linkage #1 | disconnected | loop | Failed |
| regression union linkage #2 | disconnected | loop | Failed |
| regression union linkage #3 | disconnected | loop | Failed |
| regression union linkage #4 | disconnected | loop | Failed |
| diagonal passage #1 | 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 / 4eee95538f41e26ac3b97cf47e4ffb6d2c47b0aa9793f224971c35ea3a62f78c
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[(x1, y1)] = 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 = [[('regression union linkage #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'),
('regression union linkage #2',
[3,
3,
[[[2, 1], [2, 0]],
[[2, 0], [1, 0]],
[[0, 1], [0, 0]],
[[0, 1], [1, 1]],
[[1, 0], [1, 1]],
[[0, 0], [1, 0]],
[[0, 1], [0, 2]]]],
'loop'),
('regression union linkage #3',
[4,
2,
[[[1, 0], [0, 0]],
[[1, 0], [1, 1]],
[[3, 0], [2, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[1, 1], [0, 1]],
[[3, 1], [3, 0]]]],
'loop'),
('regression union linkage #4',
[4,
4,
[[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[1, 0], [2, 0]],
[[2, 1], [3, 1]],
[[1, 3], [2, 3]],
[[3, 3], [3, 2]],
[[0, 2], [0, 3]],
[[2, 1], [1, 1]],
[[2, 2], [2, 1]],
[[1, 3], [0, 3]],
[[1, 1], [1, 2]],
[[2, 0], [2, 1]],
[[2, 2], [2, 3]],
[[2, 3], [3, 3]],
[[1, 2], [2, 2]]]],
'loop'),
('diagonal passage #1', [2, 2, [[[0, 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')],
[('regression union linkage #1',
[4,
2,
[[[1, 0], [0, 0]],
[[1, 0], [1, 1]],
[[3, 0], [2, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[1, 1], [0, 1]],
[[3, 1], [3, 0]]]],
'loop'),
('regression union linkage #2',
[4,
4,
[[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[1, 0], [2, 0]],
[[2, 1], [3, 1]],
[[1, 3], [2, 3]],
[[3, 3], [3, 2]],
[[0, 2], [0, 3]],
[[2, 1], [1, 1]],
[[2, 2], [2, 1]],
[[1, 3], [0, 3]],
[[1, 1], [1, 2]],
[[2, 0], [2, 1]],
[[2, 2], [2, 3]],
[[2, 3], [3, 3]],
[[1, 2], [2, 2]]]],
'loop'),
('regression union linkage #3',
[3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
'perfect'),
('regression union linkage #4', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),
('single cell maze #1', [1, 1, []], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge'),
('control #2',
[4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
'duplicate')],
[('regression union linkage #1',
[3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
'perfect'),
('regression union linkage #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),
('regression union linkage #3',
[2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],
'loop'),
('regression union linkage #4',
[4,
3,
[[[1, 2], [0, 2]],
[[1, 1], [2, 1]],
[[3, 0], [2, 0]],
[[3, 1], [3, 0]],
[[3, 2], [3, 1]],
[[1, 1], [1, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[2, 1], [2, 0]],
[[0, 1], [1, 1]],
[[0, 0], [0, 1]],
[[0, 2], [0, 1]],
[[1, 2], [2, 2]]]],
'loop'),
('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'),
('control #2', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],
[('regression union linkage #1',
[2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],
'loop'),
('regression union linkage #2',
[4,
3,
[[[1, 2], [0, 2]],
[[1, 1], [2, 1]],
[[3, 0], [2, 0]],
[[3, 1], [3, 0]],
[[3, 2], [3, 1]],
[[1, 1], [1, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[2, 1], [2, 0]],
[[0, 1], [1, 1]],
[[0, 0], [0, 1]],
[[0, 2], [0, 1]],
[[1, 2], [2, 2]]]],
'loop'),
('regression union linkage #3',
[4,
4,
[[[1, 1], [1, 2]],
[[3, 1], [2, 1]],
[[0, 2], [1, 2]],
[[0, 0], [0, 1]],
[[0, 2], [0, 3]],
[[1, 1], [1, 0]],
[[1, 1], [2, 1]],
[[1, 0], [2, 0]],
[[1, 3], [1, 2]],
[[2, 1], [2, 0]],
[[3, 1], [3, 0]],
[[0, 0], [1, 0]],
[[3, 2], [3, 1]]]],
'loop'),
('regression union linkage #4', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('control #1',
[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'),
('control #2',
[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')],
[('regression union linkage #1',
[4,
4,
[[[1, 1], [1, 2]],
[[3, 1], [2, 1]],
[[0, 2], [1, 2]],
[[0, 0], [0, 1]],
[[0, 2], [0, 3]],
[[1, 1], [1, 0]],
[[1, 1], [2, 1]],
[[1, 0], [2, 0]],
[[1, 3], [1, 2]],
[[2, 1], [2, 0]],
[[3, 1], [3, 0]],
[[0, 0], [1, 0]],
[[3, 2], [3, 1]]]],
'loop'),
('regression union linkage #2', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),
('regression union linkage #3',
[4,
2,
[[[2, 0], [2, 1]],
[[1, 0], [0, 0]],
[[0, 1], [0, 0]],
[[2, 1], [1, 1]],
[[2, 0], [1, 0]],
[[1, 0], [1, 1]]]],
'loop'),
('regression union linkage #4',
[3, 2, [[[1, 1], [2, 1]], [[0, 0], [1, 0]], [[2, 1], [2, 0]], [[0, 0], [0, 1]], [[1, 0], [2, 0]]]],
'perfect'),
('single cell maze #1', [1, 1, []], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('control #1', [2, 1, []], 'disconnected'),
('control #2', [1, 2, [[[0, 0], [0, 1]]]], 'perfect')]]
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 |
|---|---|---|---|
| regression union linkage #1 | disconnected | loop | Failed |
| regression union linkage #2 | disconnected | loop | Failed |
| regression union linkage #3 | disconnected | loop | Failed |
| regression union linkage #4 | disconnected | loop | Failed |
| diagonal passage #1 | 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 / f54249e4f6839867c8ae54adf81b58b9d7f45b506e79e6d2261c772f388527de
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 = [[('regression union linkage #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'),
('regression union linkage #2',
[3,
3,
[[[2, 1], [2, 0]],
[[2, 0], [1, 0]],
[[0, 1], [0, 0]],
[[0, 1], [1, 1]],
[[1, 0], [1, 1]],
[[0, 0], [1, 0]],
[[0, 1], [0, 2]]]],
'loop'),
('regression union linkage #3',
[4,
2,
[[[1, 0], [0, 0]],
[[1, 0], [1, 1]],
[[3, 0], [2, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[1, 1], [0, 1]],
[[3, 1], [3, 0]]]],
'loop'),
('regression union linkage #4',
[4,
4,
[[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[1, 0], [2, 0]],
[[2, 1], [3, 1]],
[[1, 3], [2, 3]],
[[3, 3], [3, 2]],
[[0, 2], [0, 3]],
[[2, 1], [1, 1]],
[[2, 2], [2, 1]],
[[1, 3], [0, 3]],
[[1, 1], [1, 2]],
[[2, 0], [2, 1]],
[[2, 2], [2, 3]],
[[2, 3], [3, 3]],
[[1, 2], [2, 2]]]],
'loop'),
('diagonal passage #1', [2, 2, [[[0, 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')],
[('regression union linkage #1',
[4,
2,
[[[1, 0], [0, 0]],
[[1, 0], [1, 1]],
[[3, 0], [2, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 0]],
[[1, 1], [2, 1]],
[[1, 1], [0, 1]],
[[3, 1], [3, 0]]]],
'loop'),
('regression union linkage #2',
[4,
4,
[[[0, 0], [0, 1]],
[[2, 0], [3, 0]],
[[0, 2], [0, 1]],
[[1, 0], [2, 0]],
[[2, 1], [3, 1]],
[[1, 3], [2, 3]],
[[3, 3], [3, 2]],
[[0, 2], [0, 3]],
[[2, 1], [1, 1]],
[[2, 2], [2, 1]],
[[1, 3], [0, 3]],
[[1, 1], [1, 2]],
[[2, 0], [2, 1]],
[[2, 2], [2, 3]],
[[2, 3], [3, 3]],
[[1, 2], [2, 2]]]],
'loop'),
('regression union linkage #3',
[3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
'perfect'),
('regression union linkage #4', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),
('single cell maze #1', [1, 1, []], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('control #1',
[3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
'invalid-edge'),
('control #2',
[4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
'duplicate')],
[('regression union linkage #1',
[3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
'perfect'),
('regression union linkage #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),
('regression union linkage #3',
[2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],
'loop'),
('regression union linkage #4',
[4,
3,
[[[1, 2], [0, 2]],
[[1, 1], [2, 1]],
[[3, 0], [2, 0]],
[[3, 1], [3, 0]],
[[3, 2], [3, 1]],
[[1, 1], [1, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[2, 1], [2, 0]],
[[0, 1], [1, 1]],
[[0, 0], [0, 1]],
[[0, 2], [0, 1]],
[[1, 2], [2, 2]]]],
'loop'),
('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'),
('control #2', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],
[('regression union linkage #1',
[2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],
'loop'),
('regression union linkage #2',
[4,
3,
[[[1, 2], [0, 2]],
[[1, 1], [2, 1]],
[[3, 0], [2, 0]],
[[3, 1], [3, 0]],
[[3, 2], [3, 1]],
[[1, 1], [1, 0]],
[[2, 1], [3, 1]],
[[2, 1], [2, 2]],
[[2, 1], [2, 0]],
[[0, 1], [1, 1]],
[[0, 0], [0, 1]],
[[0, 2], [0, 1]],
[[1, 2], [2, 2]]]],
'loop'),
('regression union linkage #3',
[4,
4,
[[[1, 1], [1, 2]],
[[3, 1], [2, 1]],
[[0, 2], [1, 2]],
[[0, 0], [0, 1]],
[[0, 2], [0, 3]],
[[1, 1], [1, 0]],
[[1, 1], [2, 1]],
[[1, 0], [2, 0]],
[[1, 3], [1, 2]],
[[2, 1], [2, 0]],
[[3, 1], [3, 0]],
[[0, 0], [1, 0]],
[[3, 2], [3, 1]]]],
'loop'),
('regression union linkage #4', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
('control #1',
[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'),
('control #2',
[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')],
[('regression union linkage #1',
[4,
4,
[[[1, 1], [1, 2]],
[[3, 1], [2, 1]],
[[0, 2], [1, 2]],
[[0, 0], [0, 1]],
[[0, 2], [0, 3]],
[[1, 1], [1, 0]],
[[1, 1], [2, 1]],
[[1, 0], [2, 0]],
[[1, 3], [1, 2]],
[[2, 1], [2, 0]],
[[3, 1], [3, 0]],
[[0, 0], [1, 0]],
[[3, 2], [3, 1]]]],
'loop'),
('regression union linkage #2', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),
('regression union linkage #3',
[4,
2,
[[[2, 0], [2, 1]],
[[1, 0], [0, 0]],
[[0, 1], [0, 0]],
[[2, 1], [1, 1]],
[[2, 0], [1, 0]],
[[1, 0], [1, 1]]]],
'loop'),
('regression union linkage #4',
[3, 2, [[[1, 1], [2, 1]], [[0, 0], [1, 0]], [[2, 1], [2, 0]], [[0, 0], [0, 1]], [[1, 0], [2, 0]]]],
'perfect'),
('single cell maze #1', [1, 1, []], 'perfect'),
('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
('control #1', [2, 1, []], 'disconnected'),
('control #2', [1, 2, [[[0, 0], [0, 1]]]], 'perfect')]]
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 |
|---|---|---|---|
| regression union linkage #1 | loop | loop | Passed |
| regression union linkage #2 | loop | loop | Passed |
| regression union linkage #3 | loop | loop | Passed |
| regression union linkage #4 | loop | loop | Passed |
| diagonal passage #1 | 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 / 39f96ebb059a040b38a5413d51bd38863a0e7f967dac921553106a9419c8f7d9
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.414989+00:00.
Case digest / 89bb088cc63991bb2d37b7bfb4269c87ca76d8bef3c32078124f71305a215b9a