FA-86416 / Procedural level generation constraints / Open access
Key and lock solvability: Search stops after one sweep · case 01
Rooms whose doors appear earlier in the edge list are never explored.
ROOT CAUSE
Opening a new room does not trigger another pass over the doors.
VERIFIED REPAIR
Restore `seen.add(v) changed = True` at the fixpoint after traversal step.
Unsuccessful approach: Re-sweeping only after locked doors misses chains of plain doors listed out of order.
Case contract
rooms maps room -> keys lying there; edges [a, b, lock] are two-way doors, lock None or a key colour. Keys are never consumed. Starting in start, repeatedly pick up keys in visited rooms and walk through doors that are open or whose key is held, until nothing changes. Returns {solvable: goal visited, keys: sorted keys held, visited: count}.
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(rooms, edges, start, goal):
have = set()
seen = {start}
changed = True
while changed:
changed = False
for r in list(seen):
for k in rooms.get(r, []):
if k not in have:
have.add(k)
changed = True
for a, b, lock in edges:
for u, v in ((a, b), (b, a)):
if u in seen and v not in seen and (lock is None or lock in have):
seen.add(v)
return {'solvable': goal in seen, 'keys': sorted(have), 'visited': len(seen)}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r0': ['gold'], 'r2': ['blue']},
[['r2', 'r1', 'gold'],
['r3', 'r1', 'blue'],
['r1', 'r3', None],
['r1', 'r0', None],
['r2', 'r3', 'blue']],
'r0',
'r3'],
{'solvable': True, 'keys': ['blue', 'gold'], 'visited': 4}),
('regression fixpoint after traversal #2',
[{'r4': ['red']},
[['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
'r0',
'r3'],
{'solvable': False, 'keys': [], 'visited': 3}),
('partial repair boundary #1',
[{'r0': ['red'], 'r3': ['gold']},
[['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
'r0',
'r4'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('partial repair boundary #2',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r4': ['red']},
[['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
'r0',
'r3'],
{'solvable': False, 'keys': [], 'visited': 3}),
('regression fixpoint after traversal #2',
[{'r3': ['blue'], 'r4': ['gold']},
[['r4', 'r1', 'blue'],
['r5', 'r3', None],
['r5', 'r4', 'red'],
['r1', 'r0', 'gold'],
['r0', 'r2', 'blue'],
['r4', 'r0', None],
['r3', 'r2', None]],
'r0',
'r4'],
{'solvable': True, 'keys': ['gold'], 'visited': 3}),
('partial repair boundary #1',
[{'r0': ['red'], 'r3': ['gold']},
[['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
'r0',
'r4'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('partial repair boundary #2',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red']},
[['r3', 'r2', 'gold'], ['r1', 'r3', 'red'], ['r1', 'r0', 'gold'], ['r2', 'r0', None], ['r1', 'r2', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 4}),
('regression fixpoint after traversal #2',
[{'r4': ['blue']},
[['r6', 'r1', None],
['r1', 'r0', None],
['r1', 'r5', 'blue'],
['r2', 'r1', 'gold'],
['r4', 'r0', 'blue'],
['r3', 'r6', None],
['r4', 'r5', None],
['r3', 'r1', 'gold']],
'r0',
'r2'],
{'solvable': False, 'keys': [], 'visited': 4}),
('partial repair boundary #1',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('regression fixpoint after traversal #3',
[{'r3': ['blue'], 'r4': ['gold']},
[['r4', 'r1', 'blue'],
['r5', 'r3', None],
['r5', 'r4', 'red'],
['r1', 'r0', 'gold'],
['r0', 'r2', 'blue'],
['r4', 'r0', None],
['r3', 'r2', None]],
'r0',
'r4'],
{'solvable': True, 'keys': ['gold'], 'visited': 3}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red'], 'r4': ['blue'], 'r6': ['gold']},
[['r1', 'r0', 'blue'],
['r2', 'r6', 'blue'],
['r5', 'r4', None],
['r0', 'r2', 'gold'],
['r1', 'r3', None],
['r0', 'r4', None]],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('regression fixpoint after traversal #2',
[{'r2': ['gold'], 'r3': ['red']},
[['r2', 'r0', None], ['r2', 'r4', 'gold'], ['r5', 'r4', None], ['r3', 'r2', None], ['r0', 'r1', 'gold']],
'r0',
'r1'],
{'solvable': True, 'keys': ['gold', 'red'], 'visited': 6}),
('partial repair boundary #1',
[{'r0': ['blue'], 'r3': ['red']},
[['r1', 'r0', None],
['r5', 'r3', None],
['r1', 'r2', 'red'],
['r3', 'r2', 'red'],
['r0', 'r4', 'gold'],
['r3', 'r1', None],
['r0', 'r5', 'gold']],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('regression fixpoint after traversal #3',
[{'r1': ['red']},
[['r3', 'r2', 'gold'], ['r1', 'r3', 'red'], ['r1', 'r0', 'gold'], ['r2', 'r0', None], ['r1', 'r2', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 4}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red']},
[['r0', 'r1', None], ['r2', 'r3', 'blue'], ['r2', 'r1', 'gold'], ['r3', 'r1', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #2',
[{'r1': ['blue'], 'r2': ['gold'], 'r4': ['red']},
[['r2', 'r0', None], ['r1', 'r0', None], ['r1', 'r4', None], ['r1', 'r3', None], ['r3', 'r5', 'gold']],
'r0',
'r1'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 6}),
('regression fixpoint after traversal #3',
[{'r4': ['blue']},
[['r6', 'r1', None],
['r1', 'r0', None],
['r1', 'r5', 'blue'],
['r2', 'r1', 'gold'],
['r4', 'r0', 'blue'],
['r3', 'r6', None],
['r4', 'r5', None],
['r3', 'r1', 'gold']],
'r0',
'r2'],
{'solvable': False, 'keys': [], 'visited': 4}),
('regression fixpoint after traversal #4',
[{'r1': ['red'], 'r4': ['blue'], 'r6': ['gold']},
[['r1', 'r0', 'blue'],
['r2', 'r6', 'blue'],
['r5', 'r4', None],
['r0', 'r2', 'gold'],
['r1', 'r3', None],
['r0', 'r4', None]],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['red']}, [['r0', 'r1', None]], 'r0', 'r1'],
{'solvable': True, 'keys': ['red'], 'visited': 2})]]
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 |
|---|---|---|---|
| key behind first door #1 | {'keys': [], 'solvable': False, 'visited': 2} | {'keys': ['red'], 'solvable': True, 'visited': 3} | Failed |
| regression fixpoint after traversal #1 | {'keys': ['gold'], 'solvable': True, 'visited': 4} | {'keys': ['blue', 'gold'], 'solvable': True, 'visited': 4} | Failed |
| regression fixpoint after traversal #2 | {'keys': [], 'solvable': False, 'visited': 2} | {'keys': [], 'solvable': False, 'visited': 3} | Failed |
| partial repair boundary #1 | {'keys': ['red'], 'solvable': True, 'visited': 3} | {'keys': ['red'], 'solvable': True, 'visited': 3} | Passed |
| partial repair boundary #2 | {'keys': ['blue', 'gold', 'red'], 'solvable': True, 'visited': 7} | {'keys': ['blue', 'gold', 'red'], 'solvable': True, 'visited': 7} | Passed |
| reverse listed door #1 | {'keys': [], 'solvable': True, 'visited': 2} | {'keys': [], 'solvable': True, 'visited': 2} | Passed |
| wrong colour #1 | {'keys': ['blue'], 'solvable': False, 'visited': 1} | {'keys': ['blue'], 'solvable': False, 'visited': 1} | Passed |
| control #1 | {'keys': ['gold'], 'solvable': True, 'visited': 2} | {'keys': ['gold'], 'solvable': True, 'visited': 2} | Passed |
SHA-256 / f36c42c26d5bdf7f7dbd5b28989002d3901fb6fd51ca79694357b4aae0d44efd
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(rooms, edges, start, goal):
have = set()
seen = {start}
changed = True
while changed:
changed = False
for r in list(seen):
for k in rooms.get(r, []):
if k not in have:
have.add(k)
changed = True
for a, b, lock in edges:
for u, v in ((a, b), (b, a)):
if u in seen and v not in seen and (lock is None or lock in have):
seen.add(v)
changed = lock is not None
return {'solvable': goal in seen, 'keys': sorted(have), 'visited': len(seen)}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r0': ['gold'], 'r2': ['blue']},
[['r2', 'r1', 'gold'],
['r3', 'r1', 'blue'],
['r1', 'r3', None],
['r1', 'r0', None],
['r2', 'r3', 'blue']],
'r0',
'r3'],
{'solvable': True, 'keys': ['blue', 'gold'], 'visited': 4}),
('regression fixpoint after traversal #2',
[{'r4': ['red']},
[['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
'r0',
'r3'],
{'solvable': False, 'keys': [], 'visited': 3}),
('partial repair boundary #1',
[{'r0': ['red'], 'r3': ['gold']},
[['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
'r0',
'r4'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('partial repair boundary #2',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r4': ['red']},
[['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
'r0',
'r3'],
{'solvable': False, 'keys': [], 'visited': 3}),
('regression fixpoint after traversal #2',
[{'r3': ['blue'], 'r4': ['gold']},
[['r4', 'r1', 'blue'],
['r5', 'r3', None],
['r5', 'r4', 'red'],
['r1', 'r0', 'gold'],
['r0', 'r2', 'blue'],
['r4', 'r0', None],
['r3', 'r2', None]],
'r0',
'r4'],
{'solvable': True, 'keys': ['gold'], 'visited': 3}),
('partial repair boundary #1',
[{'r0': ['red'], 'r3': ['gold']},
[['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
'r0',
'r4'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('partial repair boundary #2',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red']},
[['r3', 'r2', 'gold'], ['r1', 'r3', 'red'], ['r1', 'r0', 'gold'], ['r2', 'r0', None], ['r1', 'r2', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 4}),
('regression fixpoint after traversal #2',
[{'r4': ['blue']},
[['r6', 'r1', None],
['r1', 'r0', None],
['r1', 'r5', 'blue'],
['r2', 'r1', 'gold'],
['r4', 'r0', 'blue'],
['r3', 'r6', None],
['r4', 'r5', None],
['r3', 'r1', 'gold']],
'r0',
'r2'],
{'solvable': False, 'keys': [], 'visited': 4}),
('partial repair boundary #1',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('regression fixpoint after traversal #3',
[{'r3': ['blue'], 'r4': ['gold']},
[['r4', 'r1', 'blue'],
['r5', 'r3', None],
['r5', 'r4', 'red'],
['r1', 'r0', 'gold'],
['r0', 'r2', 'blue'],
['r4', 'r0', None],
['r3', 'r2', None]],
'r0',
'r4'],
{'solvable': True, 'keys': ['gold'], 'visited': 3}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red'], 'r4': ['blue'], 'r6': ['gold']},
[['r1', 'r0', 'blue'],
['r2', 'r6', 'blue'],
['r5', 'r4', None],
['r0', 'r2', 'gold'],
['r1', 'r3', None],
['r0', 'r4', None]],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('regression fixpoint after traversal #2',
[{'r2': ['gold'], 'r3': ['red']},
[['r2', 'r0', None], ['r2', 'r4', 'gold'], ['r5', 'r4', None], ['r3', 'r2', None], ['r0', 'r1', 'gold']],
'r0',
'r1'],
{'solvable': True, 'keys': ['gold', 'red'], 'visited': 6}),
('partial repair boundary #1',
[{'r0': ['blue'], 'r3': ['red']},
[['r1', 'r0', None],
['r5', 'r3', None],
['r1', 'r2', 'red'],
['r3', 'r2', 'red'],
['r0', 'r4', 'gold'],
['r3', 'r1', None],
['r0', 'r5', 'gold']],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('regression fixpoint after traversal #3',
[{'r1': ['red']},
[['r3', 'r2', 'gold'], ['r1', 'r3', 'red'], ['r1', 'r0', 'gold'], ['r2', 'r0', None], ['r1', 'r2', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 4}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red']},
[['r0', 'r1', None], ['r2', 'r3', 'blue'], ['r2', 'r1', 'gold'], ['r3', 'r1', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #2',
[{'r1': ['blue'], 'r2': ['gold'], 'r4': ['red']},
[['r2', 'r0', None], ['r1', 'r0', None], ['r1', 'r4', None], ['r1', 'r3', None], ['r3', 'r5', 'gold']],
'r0',
'r1'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 6}),
('regression fixpoint after traversal #3',
[{'r4': ['blue']},
[['r6', 'r1', None],
['r1', 'r0', None],
['r1', 'r5', 'blue'],
['r2', 'r1', 'gold'],
['r4', 'r0', 'blue'],
['r3', 'r6', None],
['r4', 'r5', None],
['r3', 'r1', 'gold']],
'r0',
'r2'],
{'solvable': False, 'keys': [], 'visited': 4}),
('regression fixpoint after traversal #4',
[{'r1': ['red'], 'r4': ['blue'], 'r6': ['gold']},
[['r1', 'r0', 'blue'],
['r2', 'r6', 'blue'],
['r5', 'r4', None],
['r0', 'r2', 'gold'],
['r1', 'r3', None],
['r0', 'r4', None]],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['red']}, [['r0', 'r1', None]], 'r0', 'r1'],
{'solvable': True, 'keys': ['red'], 'visited': 2})]]
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 |
|---|---|---|---|
| key behind first door #1 | {'keys': [], 'solvable': False, 'visited': 2} | {'keys': ['red'], 'solvable': True, 'visited': 3} | Failed |
| regression fixpoint after traversal #1 | {'keys': ['gold'], 'solvable': False, 'visited': 2} | {'keys': ['blue', 'gold'], 'solvable': True, 'visited': 4} | Failed |
| regression fixpoint after traversal #2 | {'keys': [], 'solvable': False, 'visited': 2} | {'keys': [], 'solvable': False, 'visited': 3} | Failed |
| partial repair boundary #1 | {'keys': ['red'], 'solvable': False, 'visited': 2} | {'keys': ['red'], 'solvable': True, 'visited': 3} | Failed |
| partial repair boundary #2 | {'keys': ['red'], 'solvable': False, 'visited': 4} | {'keys': ['blue', 'gold', 'red'], 'solvable': True, 'visited': 7} | Failed |
| reverse listed door #1 | {'keys': [], 'solvable': True, 'visited': 2} | {'keys': [], 'solvable': True, 'visited': 2} | Passed |
| wrong colour #1 | {'keys': ['blue'], 'solvable': False, 'visited': 1} | {'keys': ['blue'], 'solvable': False, 'visited': 1} | Passed |
| control #1 | {'keys': ['gold'], 'solvable': True, 'visited': 2} | {'keys': ['gold'], 'solvable': True, 'visited': 2} | Passed |
SHA-256 / 1307d25c80abd492d13bf96bcea0bcfdb5bbaba752644be467298fdc03e1492c
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(rooms, edges, start, goal):
have = set()
seen = {start}
changed = True
while changed:
changed = False
for r in list(seen):
for k in rooms.get(r, []):
if k not in have:
have.add(k)
changed = True
for a, b, lock in edges:
for u, v in ((a, b), (b, a)):
if u in seen and v not in seen and (lock is None or lock in have):
seen.add(v)
changed = True
return {'solvable': goal in seen, 'keys': sorted(have), 'visited': len(seen)}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r0': ['gold'], 'r2': ['blue']},
[['r2', 'r1', 'gold'],
['r3', 'r1', 'blue'],
['r1', 'r3', None],
['r1', 'r0', None],
['r2', 'r3', 'blue']],
'r0',
'r3'],
{'solvable': True, 'keys': ['blue', 'gold'], 'visited': 4}),
('regression fixpoint after traversal #2',
[{'r4': ['red']},
[['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
'r0',
'r3'],
{'solvable': False, 'keys': [], 'visited': 3}),
('partial repair boundary #1',
[{'r0': ['red'], 'r3': ['gold']},
[['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
'r0',
'r4'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('partial repair boundary #2',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r4': ['red']},
[['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
'r0',
'r3'],
{'solvable': False, 'keys': [], 'visited': 3}),
('regression fixpoint after traversal #2',
[{'r3': ['blue'], 'r4': ['gold']},
[['r4', 'r1', 'blue'],
['r5', 'r3', None],
['r5', 'r4', 'red'],
['r1', 'r0', 'gold'],
['r0', 'r2', 'blue'],
['r4', 'r0', None],
['r3', 'r2', None]],
'r0',
'r4'],
{'solvable': True, 'keys': ['gold'], 'visited': 3}),
('partial repair boundary #1',
[{'r0': ['red'], 'r3': ['gold']},
[['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
'r0',
'r4'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('partial repair boundary #2',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red']},
[['r3', 'r2', 'gold'], ['r1', 'r3', 'red'], ['r1', 'r0', 'gold'], ['r2', 'r0', None], ['r1', 'r2', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 4}),
('regression fixpoint after traversal #2',
[{'r4': ['blue']},
[['r6', 'r1', None],
['r1', 'r0', None],
['r1', 'r5', 'blue'],
['r2', 'r1', 'gold'],
['r4', 'r0', 'blue'],
['r3', 'r6', None],
['r4', 'r5', None],
['r3', 'r1', 'gold']],
'r0',
'r2'],
{'solvable': False, 'keys': [], 'visited': 4}),
('partial repair boundary #1',
[{'r0': ['red'], 'r1': ['gold'], 'r4': ['gold'], 'r5': ['blue'], 'r6': ['red']},
[['r1', 'r2', 'blue'],
['r0', 'r2', 'red'],
['r0', 'r1', 'blue'],
['r3', 'r6', 'gold'],
['r4', 'r0', None],
['r3', 'r2', 'blue'],
['r2', 'r5', None]],
'r0',
'r6'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
('regression fixpoint after traversal #3',
[{'r3': ['blue'], 'r4': ['gold']},
[['r4', 'r1', 'blue'],
['r5', 'r3', None],
['r5', 'r4', 'red'],
['r1', 'r0', 'gold'],
['r0', 'r2', 'blue'],
['r4', 'r0', None],
['r3', 'r2', None]],
'r0',
'r4'],
{'solvable': True, 'keys': ['gold'], 'visited': 3}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
[['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
'r0',
'r2'],
{'solvable': True, 'keys': ['gold'], 'visited': 2})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red'], 'r4': ['blue'], 'r6': ['gold']},
[['r1', 'r0', 'blue'],
['r2', 'r6', 'blue'],
['r5', 'r4', None],
['r0', 'r2', 'gold'],
['r1', 'r3', None],
['r0', 'r4', None]],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('regression fixpoint after traversal #2',
[{'r2': ['gold'], 'r3': ['red']},
[['r2', 'r0', None], ['r2', 'r4', 'gold'], ['r5', 'r4', None], ['r3', 'r2', None], ['r0', 'r1', 'gold']],
'r0',
'r1'],
{'solvable': True, 'keys': ['gold', 'red'], 'visited': 6}),
('partial repair boundary #1',
[{'r0': ['blue'], 'r3': ['red']},
[['r1', 'r0', None],
['r5', 'r3', None],
['r1', 'r2', 'red'],
['r3', 'r2', 'red'],
['r0', 'r4', 'gold'],
['r3', 'r1', None],
['r0', 'r5', 'gold']],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('regression fixpoint after traversal #3',
[{'r1': ['red']},
[['r3', 'r2', 'gold'], ['r1', 'r3', 'red'], ['r1', 'r0', 'gold'], ['r2', 'r0', None], ['r1', 'r2', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 4}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
[('key behind first door #1',
[{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #1',
[{'r1': ['red']},
[['r0', 'r1', None], ['r2', 'r3', 'blue'], ['r2', 'r1', 'gold'], ['r3', 'r1', None]],
'r0',
'r3'],
{'solvable': True, 'keys': ['red'], 'visited': 3}),
('regression fixpoint after traversal #2',
[{'r1': ['blue'], 'r2': ['gold'], 'r4': ['red']},
[['r2', 'r0', None], ['r1', 'r0', None], ['r1', 'r4', None], ['r1', 'r3', None], ['r3', 'r5', 'gold']],
'r0',
'r1'],
{'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 6}),
('regression fixpoint after traversal #3',
[{'r4': ['blue']},
[['r6', 'r1', None],
['r1', 'r0', None],
['r1', 'r5', 'blue'],
['r2', 'r1', 'gold'],
['r4', 'r0', 'blue'],
['r3', 'r6', None],
['r4', 'r5', None],
['r3', 'r1', 'gold']],
'r0',
'r2'],
{'solvable': False, 'keys': [], 'visited': 4}),
('regression fixpoint after traversal #4',
[{'r1': ['red'], 'r4': ['blue'], 'r6': ['gold']},
[['r1', 'r0', 'blue'],
['r2', 'r6', 'blue'],
['r5', 'r4', None],
['r0', 'r2', 'gold'],
['r1', 'r3', None],
['r0', 'r4', None]],
'r0',
'r5'],
{'solvable': True, 'keys': ['blue', 'red'], 'visited': 5}),
('reverse listed door #1',
[{}, [['r1', 'r0', None]], 'r0', 'r1'],
{'solvable': True, 'keys': [], 'visited': 2}),
('wrong colour #1',
[{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
{'solvable': False, 'keys': ['blue'], 'visited': 1}),
('control #1',
[{'r0': ['red']}, [['r0', 'r1', None]], 'r0', 'r1'],
{'solvable': True, 'keys': ['red'], 'visited': 2})]]
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 |
|---|---|---|---|
| key behind first door #1 | {'keys': ['red'], 'solvable': True, 'visited': 3} | {'keys': ['red'], 'solvable': True, 'visited': 3} | Passed |
| regression fixpoint after traversal #1 | {'keys': ['blue', 'gold'], 'solvable': True, 'visited': 4} | {'keys': ['blue', 'gold'], 'solvable': True, 'visited': 4} | Passed |
| regression fixpoint after traversal #2 | {'keys': [], 'solvable': False, 'visited': 3} | {'keys': [], 'solvable': False, 'visited': 3} | Passed |
| partial repair boundary #1 | {'keys': ['red'], 'solvable': True, 'visited': 3} | {'keys': ['red'], 'solvable': True, 'visited': 3} | Passed |
| partial repair boundary #2 | {'keys': ['blue', 'gold', 'red'], 'solvable': True, 'visited': 7} | {'keys': ['blue', 'gold', 'red'], 'solvable': True, 'visited': 7} | Passed |
| reverse listed door #1 | {'keys': [], 'solvable': True, 'visited': 2} | {'keys': [], 'solvable': True, 'visited': 2} | Passed |
| wrong colour #1 | {'keys': ['blue'], 'solvable': False, 'visited': 1} | {'keys': ['blue'], 'solvable': False, 'visited': 1} | Passed |
| control #1 | {'keys': ['gold'], 'solvable': True, 'visited': 2} | {'keys': ['gold'], 'solvable': True, 'visited': 2} | Passed |
SHA-256 / 4c45a74fa9e1e0333980cdc72cac6a4c083a118f44affbc8ef7233ee9355869a
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:49.330536+00:00.
Case digest / 0e9edb24e02c26833cb41156727fe7de01bbb4c843fa35560784020e85ba72ba