broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(grid, start, swim):
    h = len(grid)
    w = len(grid[0])
    sr, sc = start
    seen = set()
    stack = [(sr, sc)]
    found = False
    while stack:
        r, c = stack.pop()
        if grid[r][c] == 'E':
            found = True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
                t = grid[nr][nc]
                if t == '#' or (t == '~' and not swim):
                    continue
                seen.add((nr, nc))
                stack.append((nr, nc))
    return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
  ('partial repair boundary #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('partial repair boundary #2',
   [['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
   {'reachable': 8, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['E', '#', '~', '.'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2', [['E'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True}),
  ('partial repair boundary #2',
   [['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E', '#'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
  ('partial repair boundary #2',
   [['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
   {'reachable': 30, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['.~~~D', 'E....', '.~.#D', '~.~#~', '~~D~D', '.#~#.'], [5, 0], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2',
   [['D', '#', 'E', '#', '.', '.', '.'], [2, 0], True],
   {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['.', '.', '~', 'E', '.', '~'], [4, 0], True],
   {'reachable': 6, 'exit': True}),
  ('partial repair boundary #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True})]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(grid, start, swim):
    h = len(grid)
    w = len(grid[0])
    sr, sc = start
    seen = {(sc, sr)}
    stack = [(sr, sc)]
    found = False
    while stack:
        r, c = stack.pop()
        if grid[r][c] == 'E':
            found = True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
                t = grid[nr][nc]
                if t == '#' or (t == '~' and not swim):
                    continue
                seen.add((nr, nc))
                stack.append((nr, nc))
    return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('partial repair boundary #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True}),
  ('partial repair boundary #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['DD~.', '.#.#', '~.E.', '#.~~', 'D.~.'], [4, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('partial repair boundary #2',
   [['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
   {'reachable': 8, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1', [['E', '#', '~', '.'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('fault site start seeding #2', [['E'], [0, 0], True], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True}),
  ('partial repair boundary #2',
   [['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
   {'reachable': 12, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['#D~.##', '.D.~E#', '.~...~', '....#.', '#.....'], [0, 3], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2', [['E', '#'], [0, 0], False], {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1', [['~D.E..~', '.......'], [1, 5], False], {'reachable': 12, 'exit': True}),
  ('partial repair boundary #2',
   [['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
   {'reachable': 30, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True})],
 [('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('fault site start seeding #1',
   [['.~~~D', 'E....', '.~.#D', '~.~#~', '~~D~D', '.#~#.'], [5, 0], False],
   {'reachable': 1, 'exit': False}),
  ('fault site start seeding #2',
   [['D', '#', 'E', '#', '.', '.', '.'], [2, 0], True],
   {'reachable': 1, 'exit': True}),
  ('partial repair boundary #1',
   [['.', '.', '~', 'E', '.', '~'], [4, 0], True],
   {'reachable': 6, 'exit': True}),
  ('partial repair boundary #2', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('control #1', [['.E', '.D', 'D.'], [0, 0], True], {'reachable': 6, 'exit': True})]]
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)

prompt:
An enclosed start reports zero reachable cells.

grid rows of '#' wall, '.' floor, 'D' door (passable), '~' water (passable only when swim) and 'E' exit. From start [row, col], 4-neighbour flood fill. Returns {reachable: number of reached cells including start, exit: whether an E cell was reached}.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(grid, start, swim):
    h = len(grid)
    w = len(grid[0])
    sr, sc = start
    seen = {(sr, sc)}
    stack = [(sr, sc)]
    found = False
    while stack:
        r, c = stack.pop()
        if grid[r][c] == 'E':
            found = True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
                t = grid[nr][nc]
                if t in '#D' or (t == '~' and not swim):
                    continue
                seen.add((nr, nc))
                stack.append((nr, nc))
    return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True}),
  ('fault site door passability #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #1',
   [['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
   {'reachable': 8, 'exit': True}),
  ('regression door passability #2',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #1',
   [['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
   {'reachable': 8, 'exit': True}),
  ('regression door passability #2',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True}),
  ('regression door passability #3',
   [['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
   {'reachable': 12, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True}),
  ('regression door passability #1',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True}),
  ('regression door passability #2',
   [['~D.E..~', '.......'], [1, 5], False],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #3', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('regression door passability #1',
   [['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #2',
   [['~D.E..~', '.......'], [1, 5], False],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #3',
   [['.', 'E', 'D', '~', '~'], [1, 0], False],
   {'reachable': 3, 'exit': True}),
  ('regression door passability #4', [['....D', 'D...E'], [1, 4], False], {'reachable': 10, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1',
   [['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
   {'reachable': 30, 'exit': True}),
  ('regression door passability #1', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('regression door passability #2',
   [['.D.~', 'E~.D', '~D..'], [0, 0], False],
   {'reachable': 9, 'exit': True}),
  ('regression door passability #3', [['.E...#', '...~.D'], [0, 0], False], {'reachable': 10, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})]]
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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(grid, start, swim):
    h = len(grid)
    w = len(grid[0])
    sr, sc = start
    seen = {(sr, sc)}
    stack = [(sr, sc)]
    found = False
    while stack:
        r, c = stack.pop()
        if grid[r][c] == 'E':
            found = True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen:
                t = grid[nr][nc]
                if t == '#' or t == 'D' and not swim or (t == '~' and not swim):
                    continue
                seen.add((nr, nc))
                stack.append((nr, nc))
    return {'reachable': len(seen), 'exit': found}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1', [['.E..', '.D..'], [0, 1], True], {'reachable': 8, 'exit': True}),
  ('fault site door passability #2',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #1',
   [['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
   {'reachable': 8, 'exit': True}),
  ('regression door passability #2',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1',
   [['~.D#.', 'D....', '#.D#E'], [1, 4], True],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #1',
   [['D.~E.', '#~~.#', 'DD...'], [2, 3], False],
   {'reachable': 8, 'exit': True}),
  ('regression door passability #2',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True}),
  ('regression door passability #3',
   [['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
   {'reachable': 12, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1', [['E.D.', '...D'], [1, 0], True], {'reachable': 8, 'exit': True}),
  ('regression door passability #1',
   [['.##.', '.D#D', 'D...', '.D~.', '.#DE', '.~#.', '.~DD'], [3, 0], False],
   {'reachable': 20, 'exit': True}),
  ('regression door passability #2',
   [['~D.E..~', '.......'], [1, 5], False],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #3', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.'], [1, 0], False], {'reachable': 2, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('regression door passability #1',
   [['..', '.E', 'DD', '.#', '..', '.~', '..'], [6, 0], False],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #2',
   [['~D.E..~', '.......'], [1, 5], False],
   {'reachable': 12, 'exit': True}),
  ('regression door passability #3',
   [['.', 'E', 'D', '~', '~'], [1, 0], False],
   {'reachable': 3, 'exit': True}),
  ('regression door passability #4', [['....D', 'D...E'], [1, 4], False], {'reachable': 10, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['E', '.', '.', '.', '~'], [2, 0], True], {'reachable': 5, 'exit': True})],
 [('door corridor #1', [['.DE'], [0, 0], False], {'reachable': 3, 'exit': True}),
  ('fault site door passability #1',
   [['#D~..', '.#D.~', '.#...', '....D', 'DD#..', '.D.~#', '~~E.D'], [0, 3], True],
   {'reachable': 30, 'exit': True}),
  ('regression door passability #1', [['E.D..'], [0, 3], False], {'reachable': 5, 'exit': True}),
  ('regression door passability #2',
   [['.D.~', 'E~.D', '~D..'], [0, 0], False],
   {'reachable': 9, 'exit': True}),
  ('regression door passability #3', [['.E...#', '...~.D'], [0, 0], False], {'reachable': 10, 'exit': True}),
  ('diagonal gap only #1', [['.#', '#E'], [0, 0], False], {'reachable': 1, 'exit': False}),
  ('walled-in start #1', [['#.#', '#E#'], [0, 1], True], {'reachable': 2, 'exit': True}),
  ('control #1', [['~.#D##E'], [0, 6], False], {'reachable': 1, 'exit': True})]]
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)

prompt:
Rooms behind doors are reported unreachable.

grid rows of '#' wall, '.' floor, 'D' door (passable), '~' water (passable only when swim) and 'E' exit. From start [row, col], 4-neighbour flood fill. Returns {reachable: number of reached cells including start, exit: whether an E cell was reached}.

split: open-access


prompt:
Caves smooth into diagonal checkerboards.

One synchronous step over '#'/'.' rows. For each cell count wall cells among its 8 neighbours (the cell itself excluded); out-of-bounds neighbours count as walls when border_wall. A wall stays a wall when the count is in survive; a floor becomes a wall when the count is in birth. All counts use the input grid.

split: open-access


prompt:
Open-edge maps grow walls along the boundary.

One synchronous step over '#'/'.' rows. For each cell count wall cells among its 8 neighbours (the cell itself excluded); out-of-bounds neighbours count as walls when border_wall. A wall stays a wall when the count is in survive; a floor becomes a wall when the count is in birth. All counts use the input grid.

split: open-access


prompt:
Cave shape depends on scan direction.

One synchronous step over '#'/'.' rows. For each cell count wall cells among its 8 neighbours (the cell itself excluded); out-of-bounds neighbours count as walls when border_wall. A wall stays a wall when the count is in survive; a floor becomes a wall when the count is in birth. All counts use the input grid.

split: open-access


prompt:
Walls erode and floors fill in with the wrong thresholds.

One synchronous step over '#'/'.' rows. For each cell count wall cells among its 8 neighbours (the cell itself excluded); out-of-bounds neighbours count as walls when border_wall. A wall stays a wall when the count is in survive; a floor becomes a wall when the count is in birth. All counts use the input grid.

split: open-access


broken_source:
"""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),):
                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 = [[('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site door direction #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}),
  ('fault site door direction #2',
   [{'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 #1',
   [{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
    [['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
    'r0',
    'r2'],
   {'solvable': True, 'keys': ['gold'], 'visited': 2}),
  ('regression door direction #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}),
  ('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})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site door direction #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}),
  ('fault site door direction #2',
   [{'r4': ['red']},
    [['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': [], 'visited': 3}),
  ('regression door direction #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}),
  ('partial repair boundary #1',
   [{'r0': ['red']}, [['r0', 'r1', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['red'], '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})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('regression door direction #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}),
  ('fault site door direction #1',
   [{'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}),
  ('regression door direction #2',
   [{'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 door direction #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}),
  ('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('control #1',
   [{'r1': ['red'], 'r2': ['gold']},
    [['r1', 'r2', 'blue'], ['r1', 'r0', 'red'], ['r4', 'r2', 'blue'], ['r1', 'r3', None]],
    'r0',
    'r2'],
   {'solvable': False, 'keys': [], 'visited': 1})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site door direction #1',
   [{'r0': ['blue'], 'r1': ['gold']},
    [['r0', 'r1', 'red'], ['r1', 'r0', 'blue'], ['r0', 'r1', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 2}),
  ('regression door direction #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}),
  ('partial repair boundary #1',
   [{'r3': ['red'], 'r5': ['red']},
    [['r1', 'r3', 'gold'],
     ['r2', 'r3', 'blue'],
     ['r2', 'r1', 'blue'],
     ['r0', 'r1', None],
     ['r2', 'r4', 'gold'],
     ['r5', 'r4', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('regression door direction #2',
   [{'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}),
  ('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('control #1',
   [{'r2': ['red']},
    [['r1', 'r0', 'blue'], ['r1', 'r2', None], ['r1', 'r2', 'blue'], ['r1', 'r2', 'blue']],
    'r0',
    'r2'],
   {'solvable': False, 'keys': [], 'visited': 1})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('regression door direction #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}),
  ('fault site door direction #1',
   [{'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 door direction #2',
   [{'r0': ['gold'], 'r2': ['gold'], 'r3': ['red'], 'r4': ['red']},
    [['r0', 'r1', None],
     ['r1', 'r2', 'blue'],
     ['r6', 'r1', None],
     ['r5', 'r0', 'blue'],
     ['r3', 'r2', 'gold'],
     ['r4', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': ['gold', 'red'], 'visited': 4}),
  ('partial repair boundary #1',
   [{'r0': ['red']}, [['r0', 'r1', 'red'], ['r0', 'r1', None], ['r1', 'r0', 'blue']], 'r0', 'r1'],
   {'solvable': True, 'keys': ['red'], 'visited': 2}),
  ('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('control #1',
   [{}, [['r1', 'r0', 'red'], ['r2', 'r1', None]], 'r0', 'r1'],
   {'solvable': False, 'keys': [], 'visited': 1})]]
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)

source:
"""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 ((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 = [[('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site door direction #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}),
  ('fault site door direction #2',
   [{'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 #1',
   [{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
    [['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
    'r0',
    'r2'],
   {'solvable': True, 'keys': ['gold'], 'visited': 2}),
  ('regression door direction #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}),
  ('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})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site door direction #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}),
  ('fault site door direction #2',
   [{'r4': ['red']},
    [['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': [], 'visited': 3}),
  ('regression door direction #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}),
  ('partial repair boundary #1',
   [{'r0': ['red']}, [['r0', 'r1', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['red'], '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})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('regression door direction #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}),
  ('fault site door direction #1',
   [{'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}),
  ('regression door direction #2',
   [{'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 door direction #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}),
  ('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('control #1',
   [{'r1': ['red'], 'r2': ['gold']},
    [['r1', 'r2', 'blue'], ['r1', 'r0', 'red'], ['r4', 'r2', 'blue'], ['r1', 'r3', None]],
    'r0',
    'r2'],
   {'solvable': False, 'keys': [], 'visited': 1})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site door direction #1',
   [{'r0': ['blue'], 'r1': ['gold']},
    [['r0', 'r1', 'red'], ['r1', 'r0', 'blue'], ['r0', 'r1', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 2}),
  ('regression door direction #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}),
  ('partial repair boundary #1',
   [{'r3': ['red'], 'r5': ['red']},
    [['r1', 'r3', 'gold'],
     ['r2', 'r3', 'blue'],
     ['r2', 'r1', 'blue'],
     ['r0', 'r1', None],
     ['r2', 'r4', 'gold'],
     ['r5', 'r4', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('regression door direction #2',
   [{'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}),
  ('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('control #1',
   [{'r2': ['red']},
    [['r1', 'r0', 'blue'], ['r1', 'r2', None], ['r1', 'r2', 'blue'], ['r1', 'r2', 'blue']],
    'r0',
    'r2'],
   {'solvable': False, 'keys': [], 'visited': 1})],
 [('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('regression door direction #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}),
  ('fault site door direction #1',
   [{'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 door direction #2',
   [{'r0': ['gold'], 'r2': ['gold'], 'r3': ['red'], 'r4': ['red']},
    [['r0', 'r1', None],
     ['r1', 'r2', 'blue'],
     ['r6', 'r1', None],
     ['r5', 'r0', 'blue'],
     ['r3', 'r2', 'gold'],
     ['r4', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': ['gold', 'red'], 'visited': 4}),
  ('partial repair boundary #1',
   [{'r0': ['red']}, [['r0', 'r1', 'red'], ['r0', 'r1', None], ['r1', 'r0', 'blue']], 'r0', 'r1'],
   {'solvable': True, 'keys': ['red'], 'visited': 2}),
  ('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('control #1',
   [{}, [['r1', 'r0', 'red'], ['r2', 'r1', None]], 'r0', 'r1'],
   {'solvable': False, 'keys': [], 'visited': 1})]]
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)

prompt:
Rooms listed on the far side of a door are unreachable.

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}.

split: open-access


broken_source:
"""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 bool(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 = [[('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #1',
   [{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
    [['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
    'r0',
    'r2'],
   {'solvable': True, 'keys': ['gold'], 'visited': 2}),
  ('fault site lock matching #2',
   [{'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 #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}),
  ('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}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #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}),
  ('regression lock matching #1',
   [{'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}),
  ('regression lock matching #2',
   [{'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}),
  ('partial repair boundary #1',
   [{'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}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #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 lock matching #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}),
  ('partial repair boundary #1',
   [{'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 #2',
   [{'r0': ['red'], 'r1': ['gold'], 'r2': ['red']},
    [['r0', 'r3', 'gold'],
     ['r2', 'r0', 'red'],
     ['r0', 'r1', 'gold'],
     ['r0', 'r4', None],
     ['r0', 'r1', 'red']],
    'r0',
    'r3'],
   {'solvable': True, 'keys': ['gold', 'red'], 'visited': 5}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #1',
   [{'r0': ['blue'], 'r1': ['red']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #2',
   [{'r0': ['gold'], 'r2': ['gold'], 'r3': ['red'], 'r4': ['red']},
    [['r0', 'r1', None],
     ['r1', 'r2', 'blue'],
     ['r6', 'r1', None],
     ['r5', 'r0', 'blue'],
     ['r3', 'r2', 'gold'],
     ['r4', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': ['gold', 'red'], 'visited': 4}),
  ('regression lock matching #1',
   [{'r0': ['blue'], 'r3': ['blue']},
    [['r3', 'r4', None],
     ['r1', 'r2', 'gold'],
     ['r1', 'r0', 'blue'],
     ['r1', 'r5', 'gold'],
     ['r3', 'r4', 'red'],
     ['r1', 'r3', 'blue']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 4}),
  ('partial repair boundary #1',
   [{'r0': ['blue']},
    [['r2', 'r0', 'red'], ['r1', 'r0', 'red'], ['r0', 'r1', 'blue'], ['r1', 'r2', 'blue']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 3}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1',
   [{'r4': ['red']},
    [['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': [], 'visited': 3})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #1',
   [{'r0': ['blue'], 'r2': ['red'], 'r3': ['blue'], 'r4': ['blue']},
    [['r3', 'r2', 'red'], ['r4', 'r0', None], ['r1', 'r2', 'red'], ['r1', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': ['blue'], 'visited': 3}),
  ('regression lock matching #1',
   [{'r0': ['blue'], 'r3': ['blue']},
    [['r3', 'r4', None],
     ['r1', 'r2', 'gold'],
     ['r1', 'r0', 'blue'],
     ['r1', 'r5', 'gold'],
     ['r3', 'r4', 'red'],
     ['r1', 'r3', 'blue']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 4}),
  ('partial repair boundary #1',
   [{'r0': ['blue'], 'r2': ['blue'], 'r3': ['gold'], 'r4': ['gold']},
    [['r2', 'r0', None],
     ['r1', 'r0', 'blue'],
     ['r2', 'r4', 'blue'],
     ['r0', 'r3', None],
     ['r5', 'r1', 'gold']],
    'r0',
    'r4'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 6}),
  ('partial repair boundary #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}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('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)

source:
"""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 rooms.get(u, [])):
                    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 = [[('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #1',
   [{'r0': ['gold'], 'r1': ['red'], 'r2': ['gold']},
    [['r0', 'r1', 'red'], ['r2', 'r1', 'red'], ['r0', 'r2', None]],
    'r0',
    'r2'],
   {'solvable': True, 'keys': ['gold'], 'visited': 2}),
  ('fault site lock matching #2',
   [{'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 #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}),
  ('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}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #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}),
  ('regression lock matching #1',
   [{'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}),
  ('regression lock matching #2',
   [{'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}),
  ('partial repair boundary #1',
   [{'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}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #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 lock matching #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}),
  ('partial repair boundary #1',
   [{'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 #2',
   [{'r0': ['red'], 'r1': ['gold'], 'r2': ['red']},
    [['r0', 'r3', 'gold'],
     ['r2', 'r0', 'red'],
     ['r0', 'r1', 'gold'],
     ['r0', 'r4', None],
     ['r0', 'r1', 'red']],
    'r0',
    'r3'],
   {'solvable': True, 'keys': ['gold', 'red'], 'visited': 5}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1', [{}, [['r0', 'r1', 'blue']], 'r0', 'r1'], {'solvable': False, 'keys': [], 'visited': 1})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #1',
   [{'r0': ['blue'], 'r1': ['red']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #2',
   [{'r0': ['gold'], 'r2': ['gold'], 'r3': ['red'], 'r4': ['red']},
    [['r0', 'r1', None],
     ['r1', 'r2', 'blue'],
     ['r6', 'r1', None],
     ['r5', 'r0', 'blue'],
     ['r3', 'r2', 'gold'],
     ['r4', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': ['gold', 'red'], 'visited': 4}),
  ('regression lock matching #1',
   [{'r0': ['blue'], 'r3': ['blue']},
    [['r3', 'r4', None],
     ['r1', 'r2', 'gold'],
     ['r1', 'r0', 'blue'],
     ['r1', 'r5', 'gold'],
     ['r3', 'r4', 'red'],
     ['r1', 'r3', 'blue']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 4}),
  ('partial repair boundary #1',
   [{'r0': ['blue']},
    [['r2', 'r0', 'red'], ['r1', 'r0', 'red'], ['r0', 'r1', 'blue'], ['r1', 'r2', 'blue']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 3}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('control #1',
   [{'r4': ['red']},
    [['r3', 'r1', 'gold'], ['r3', 'r4', 'blue'], ['r2', 'r1', None], ['r1', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': [], 'visited': 3})],
 [('wrong colour #1',
   [{'r0': ['blue']}, [['r0', 'r1', 'red']], 'r0', 'r1'],
   {'solvable': False, 'keys': ['blue'], 'visited': 1}),
  ('fault site lock matching #1',
   [{'r0': ['blue'], 'r2': ['red'], 'r3': ['blue'], 'r4': ['blue']},
    [['r3', 'r2', 'red'], ['r4', 'r0', None], ['r1', 'r2', 'red'], ['r1', 'r0', None]],
    'r0',
    'r3'],
   {'solvable': False, 'keys': ['blue'], 'visited': 3}),
  ('regression lock matching #1',
   [{'r0': ['blue'], 'r3': ['blue']},
    [['r3', 'r4', None],
     ['r1', 'r2', 'gold'],
     ['r1', 'r0', 'blue'],
     ['r1', 'r5', 'gold'],
     ['r3', 'r4', 'red'],
     ['r1', 'r3', 'blue']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 4}),
  ('partial repair boundary #1',
   [{'r0': ['blue'], 'r2': ['blue'], 'r3': ['gold'], 'r4': ['gold']},
    [['r2', 'r0', None],
     ['r1', 'r0', 'blue'],
     ['r2', 'r4', 'blue'],
     ['r0', 'r3', None],
     ['r5', 'r1', 'gold']],
    'r0',
    'r4'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 6}),
  ('partial repair boundary #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}),
  ('reverse listed door #1',
   [{}, [['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': [], 'visited': 2}),
  ('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('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)

prompt:
A blue key opens red doors, validating unsolvable dungeons.

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}.

split: open-access


broken_source:
"""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)

source:
"""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)

prompt:
Rooms whose doors appear earlier in the edge list are never explored.

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}.

split: open-access