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 [start]:
            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}),
  ('fault site key pickup scope #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 key pickup scope #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}),
  ('regression key pickup scope #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 key pickup scope #2',
   [{'r0': ['blue'], 'r1': ['gold']},
    [['r0', 'r1', 'red'], ['r1', 'r0', 'blue'], ['r0', 'r1', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 2}),
  ('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}),
  ('fault site key pickup scope #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 key pickup scope #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 key pickup scope #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 key pickup scope #3',
   [{'r1': ['blue']}, [['r0', 'r1', 'blue'], ['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 2}),
  ('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 key pickup scope #1',
   [{'r0': ['blue'], 'r1': ['gold']},
    [['r0', 'r1', 'red'], ['r1', 'r0', 'blue'], ['r0', 'r1', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 2}),
  ('fault site key pickup scope #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 key pickup scope #2',
   [{'r0': ['blue'], 'r3': ['gold'], 'r4': ['red']},
    [['r0', 'r1', 'red'],
     ['r4', 'r1', None],
     ['r3', 'r5', 'blue'],
     ['r0', 'r2', None],
     ['r0', 'r1', 'blue'],
     ['r3', 'r0', None],
     ['r3', 'r6', None]],
    'r0',
    'r3'],
   {'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
  ('regression key pickup scope #3',
   [{'r0': ['red'], 'r1': ['gold']}, [['r0', 'r1', None], ['r0', 'r1', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['gold', 'red'], 'visited': 2}),
  ('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}),
  ('fault site key pickup scope #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 key pickup scope #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}),
  ('regression key pickup scope #1',
   [{'r0': ['red'], 'r1': ['gold'], 'r2': ['blue']},
    [['r0', 'r1', 'gold'], ['r0', 'r2', None], ['r1', 'r0', None]],
    'r0',
    'r2'],
   {'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 3}),
  ('regression key pickup scope #2',
   [{'r0': ['blue'], 'r1': ['gold'], 'r2': ['red']},
    [['r2', 'r1', 'gold'],
     ['r2', 'r4', 'gold'],
     ['r2', 'r5', 'gold'],
     ['r1', 'r0', None],
     ['r0', 'r3', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 6}),
  ('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'], 'r3': ['gold']},
    [['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
    'r0',
    'r4'],
   {'solvable': True, 'keys': ['red'], 'visited': 3})],
 [('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site key pickup scope #1',
   [{'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}),
  ('fault site key pickup scope #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}),
  ('regression key pickup scope #1',
   [{'r1': ['blue']}, [['r1', 'r0', None], ['r1', 'r0', None], ['r0', 'r1', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 2}),
  ('regression key pickup scope #2',
   [{'r1': ['red']},
    [['r0', 'r1', 'gold'], ['r0', 'r1', None], ['r2', 'r1', 'red'], ['r2', 'r1', None]],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['red'], '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', 'r1', 'blue']], '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 - {goal}):
            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}),
  ('fault site key pickup scope #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 key pickup scope #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}),
  ('regression key pickup scope #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 key pickup scope #2',
   [{'r0': ['blue'], 'r1': ['gold']},
    [['r0', 'r1', 'red'], ['r1', 'r0', 'blue'], ['r0', 'r1', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 2}),
  ('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}),
  ('fault site key pickup scope #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 key pickup scope #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 key pickup scope #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 key pickup scope #3',
   [{'r1': ['blue']}, [['r0', 'r1', 'blue'], ['r1', 'r0', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 2}),
  ('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 key pickup scope #1',
   [{'r0': ['blue'], 'r1': ['gold']},
    [['r0', 'r1', 'red'], ['r1', 'r0', 'blue'], ['r0', 'r1', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold'], 'visited': 2}),
  ('fault site key pickup scope #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 key pickup scope #2',
   [{'r0': ['blue'], 'r3': ['gold'], 'r4': ['red']},
    [['r0', 'r1', 'red'],
     ['r4', 'r1', None],
     ['r3', 'r5', 'blue'],
     ['r0', 'r2', None],
     ['r0', 'r1', 'blue'],
     ['r3', 'r0', None],
     ['r3', 'r6', None]],
    'r0',
    'r3'],
   {'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 7}),
  ('regression key pickup scope #3',
   [{'r0': ['red'], 'r1': ['gold']}, [['r0', 'r1', None], ['r0', 'r1', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['gold', 'red'], 'visited': 2}),
  ('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}),
  ('fault site key pickup scope #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 key pickup scope #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}),
  ('regression key pickup scope #1',
   [{'r0': ['red'], 'r1': ['gold'], 'r2': ['blue']},
    [['r0', 'r1', 'gold'], ['r0', 'r2', None], ['r1', 'r0', None]],
    'r0',
    'r2'],
   {'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 3}),
  ('regression key pickup scope #2',
   [{'r0': ['blue'], 'r1': ['gold'], 'r2': ['red']},
    [['r2', 'r1', 'gold'],
     ['r2', 'r4', 'gold'],
     ['r2', 'r5', 'gold'],
     ['r1', 'r0', None],
     ['r0', 'r3', 'red']],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['blue', 'gold', 'red'], 'visited': 6}),
  ('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'], 'r3': ['gold']},
    [['r4', 'r2', None], ['r0', 'r1', 'blue'], ['r2', 'r0', None], ['r2', 'r3', 'gold']],
    'r0',
    'r4'],
   {'solvable': True, 'keys': ['red'], 'visited': 3})],
 [('key behind first door #1',
   [{'r1': ['red']}, [['r1', 'r2', 'red'], ['r0', 'r1', None]], 'r0', 'r2'],
   {'solvable': True, 'keys': ['red'], 'visited': 3}),
  ('fault site key pickup scope #1',
   [{'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}),
  ('fault site key pickup scope #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}),
  ('regression key pickup scope #1',
   [{'r1': ['blue']}, [['r1', 'r0', None], ['r1', 'r0', None], ['r0', 'r1', None]], 'r0', 'r1'],
   {'solvable': True, 'keys': ['blue'], 'visited': 2}),
  ('regression key pickup scope #2',
   [{'r1': ['red']},
    [['r0', 'r1', 'gold'], ['r0', 'r1', None], ['r2', 'r1', 'red'], ['r2', 'r1', None]],
    'r0',
    'r1'],
   {'solvable': True, 'keys': ['red'], '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', 'r1', 'blue']], '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:
Keys placed deeper in the dungeon are ignored.

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


meaning: Fixture-count band, not measured model difficulty

deps: stdlib

prompt:
Enemies spawn diagonally next to the player.

Candidates [row, col] are tried in order until count spawns are chosen. A spawn must be in bounds on a '.' tile, at Chebyshev distance >= min_dist from the player and at Chebyshev distance >= 2 from every chosen spawn (no touching spawns, diagonals included). Returns chosen cells.

split: open-access


prompt:
Small arenas end up with no valid spawns.

Candidates [row, col] are tried in order until count spawns are chosen. A spawn must be in bounds on a '.' tile, at Chebyshev distance >= min_dist from the player and at Chebyshev distance >= 2 from every chosen spawn (no touching spawns, diagonals included). Returns chosen cells.

split: open-access


prompt:
Enemy packs spawn stacked on adjacent tiles.

Candidates [row, col] are tried in order until count spawns are chosen. A spawn must be in bounds on a '.' tile, at Chebyshev distance >= min_dist from the player and at Chebyshev distance >= 2 from every chosen spawn (no touching spawns, diagonals included). Returns chosen cells.

split: open-access


prompt:
Land enemies appear on water tiles.

Candidates [row, col] are tried in order until count spawns are chosen. A spawn must be in bounds on a '.' tile, at Chebyshev distance >= min_dist from the player and at Chebyshev distance >= 2 from every chosen spawn (no touching spawns, diagonals included). Returns chosen cells.

split: open-access


prompt:
Encounters contain an extra enemy.

Candidates [row, col] are tried in order until count spawns are chosen. A spawn must be in bounds on a '.' tile, at Chebyshev distance >= min_dist from the player and at Chebyshev distance >= 2 from every chosen spawn (no touching spawns, diagonals included). Returns chosen cells.

split: open-access


prompt:
Off-map candidates spawn on the opposite edge.

Candidates [row, col] are tried in order until count spawns are chosen. A spawn must be in bounds on a '.' tile, at Chebyshev distance >= min_dist from the player and at Chebyshev distance >= 2 from every chosen spawn (no touching spawns, diagonals included). Returns chosen cells.

split: open-access


prompt:
Players cannot drop down to lower platforms.

platforms [x1, x2, y] (y grows upward); the player starts on platform 0. From A the player reaches B when rise = yB-yA <= jump_h (any drop is allowed) and the horizontal gap max(0, xB1-xA2, xA1-xB2) <= jump_d - max(0, rise)//2. Reachability is transitive. Returns sorted reachable indices.

split: open-access


prompt:
Wide platforms appear far apart even when overlapping.

platforms [x1, x2, y] (y grows upward); the player starts on platform 0. From A the player reaches B when rise = yB-yA <= jump_h (any drop is allowed) and the horizontal gap max(0, xB1-xA2, xA1-xB2) <= jump_d - max(0, rise)//2. Reachability is transitive. Returns sorted reachable indices.

split: open-access


prompt:
Falling platforms become reachable from absurd distances.

platforms [x1, x2, y] (y grows upward); the player starts on platform 0. From A the player reaches B when rise = yB-yA <= jump_h (any drop is allowed) and the horizontal gap max(0, xB1-xA2, xA1-xB2) <= jump_d - max(0, rise)//2. Reachability is transitive. Returns sorted reachable indices.

split: open-access


prompt:
A gap exactly equal to jump distance is unreachable.

platforms [x1, x2, y] (y grows upward); the player starts on platform 0. From A the player reaches B when rise = yB-yA <= jump_h (any drop is allowed) and the horizontal gap max(0, xB1-xA2, xA1-xB2) <= jump_d - max(0, rise)//2. Reachability is transitive. Returns sorted reachable indices.

split: open-access


prompt:
Platforms two hops away are reported unreachable.

platforms [x1, x2, y] (y grows upward); the player starts on platform 0. From A the player reaches B when rise = yB-yA <= jump_h (any drop is allowed) and the horizontal gap max(0, xB1-xA2, xA1-xB2) <= jump_d - max(0, rise)//2. Reachability is transitive. Returns sorted reachable indices.

split: open-access


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

N = 1
observations = []
def solve(domains, rules):
    dom = [sorted(set(d)) for d in domains]
    changed = True
    while changed:
        changed = False
        for i in range(len(dom)):
            keep = []
            for t in dom[i]:
                ok_left = i == 0 or any(l in rules.get(t, []) for l in dom[i - 1])
                ok_right = i == len(dom) - 1 or any(r in rules.get(t, []) for r in dom[i + 1])
                if ok_left and ok_right:
                    keep.append(t)
            if keep != dom[i]:
                dom[i] = keep
                changed = True
    return {'domains': dom, 'contradiction': any(not d for d in dom)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill'], ['sand', 'hill'], ['sea'], ['grass', 'sand', 'sea', 'hill'], ['sea']],
    {'sea': ['hill', 'sea'],
     'sand': ['grass', 'hill', 'sea'],
     'grass': ['hill', 'sea'],
     'hill': ['sand', 'sea']}],
   {'domains': [['hill'], ['sand'], ['sea'], ['hill', 'sea'], ['sea']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'sea', 'grass', 'sea'],
     ['sea', 'sand', 'grass', 'hill'],
     ['sand', 'sea'],
     ['sand', 'hill', 'sea', 'grass']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand'], 'grass': ['sea'], 'hill': ['sand']}],
   {'domains': [['hill', 'sea'], ['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass', 'hill', 'sand']],
    'contradiction': False}),
  ('regression left support direction #3',
   [[['hill', 'grass', 'sand', 'sea'],
     ['sea', 'sand', 'hill', 'grass'],
     ['sand', 'sea', 'grass', 'hill', 'sea']],
    {'sea': ['sand'], 'sand': ['hill', 'sand'], 'grass': ['sand', 'sea'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'], ['hill', 'sand', 'sea'], ['hill', 'sand']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['hill', 'sand', 'sea'], ['grass', 'sand', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand', 'sea'], ['grass', 'sand']], 'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill', 'sea', 'grass', 'sea'],
     ['sea', 'sand', 'grass', 'hill'],
     ['sand', 'sea'],
     ['sand', 'hill', 'sea', 'grass']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand'], 'grass': ['sea'], 'hill': ['sand']}],
   {'domains': [['hill', 'sea'], ['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass', 'hill', 'sand']],
    'contradiction': False}),
  ('fault site left support direction #1',
   [[['grass'], ['grass', 'sea', 'sand', 'hill']],
    {'sea': ['grass', 'sand', 'sea'],
     'sand': ['grass', 'sand'],
     'grass': ['grass', 'hill'],
     'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass'], ['grass', 'hill']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'grass', 'sand', 'sea'],
     ['sea', 'sand', 'hill', 'grass'],
     ['sand', 'sea', 'grass', 'hill', 'sea']],
    {'sea': ['sand'], 'sand': ['hill', 'sand'], 'grass': ['sand', 'sea'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'], ['hill', 'sand', 'sea'], ['hill', 'sand']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['hill', 'sand', 'sea'], ['grass', 'sand', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand', 'sea'], ['grass', 'sand']], 'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('fault site left support direction #1',
   [[['sea', 'hill'], ['sea', 'hill', 'grass'], ['sea', 'sand', 'grass', 'hill']],
    {'sea': ['sand'],
     'sand': ['grass', 'sand', 'sea'],
     'grass': ['hill', 'sand', 'sea'],
     'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['hill'], ['grass', 'hill', 'sea'], ['grass', 'hill', 'sand', 'sea']],
    'contradiction': False}),
  ('regression left support direction #1',
   [[['hill', 'grass', 'sand', 'sea'],
     ['sea', 'sand', 'hill', 'grass'],
     ['sand', 'sea', 'grass', 'hill', 'sea']],
    {'sea': ['sand'], 'sand': ['hill', 'sand'], 'grass': ['sand', 'sea'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'], ['hill', 'sand', 'sea'], ['hill', 'sand']],
    'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'grass', 'sand'],
     ['sand', 'sea'],
     ['sand', 'sea', 'grass', 'hill'],
     ['sea'],
     ['grass', 'sea', 'hill']],
    {'sea': ['grass'], 'sand': ['grass', 'sand'], 'grass': ['grass', 'hill', 'sea'], 'hill': ['sea']}],
   {'domains': [['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass'], ['sea'], ['grass']],
    'contradiction': False}),
  ('regression left support direction #3',
   [[['hill'],
     ['hill', 'sand', 'grass'],
     ['sand', 'hill', 'sea'],
     ['hill', 'grass', 'sea', 'sand'],
     ['sand', 'grass']],
    {'sea': ['hill', 'sea'],
     'sand': ['hill', 'sand', 'sea'],
     'grass': ['grass', 'hill', 'sand'],
     'hill': ['sand']}],
   {'domains': [['hill'], ['sand'], ['hill', 'sand', 'sea'], ['hill', 'sand'], ['sand']],
    'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill', 'grass', 'sand'],
     ['sand', 'sea'],
     ['sand', 'sea', 'grass', 'hill'],
     ['sea'],
     ['grass', 'sea', 'hill']],
    {'sea': ['grass'], 'sand': ['grass', 'sand'], 'grass': ['grass', 'hill', 'sea'], 'hill': ['sea']}],
   {'domains': [['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass'], ['sea'], ['grass']],
    'contradiction': False}),
  ('fault site left support direction #1',
   [[['grass', 'hill', 'sand'], ['sand', 'grass', 'hill', 'sea']],
    {'sea': ['grass', 'hill', 'sea'], 'sand': ['hill'], 'grass': ['grass', 'sand'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand'], ['grass', 'hill', 'sand']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'sand', 'grass', 'sea'],
     ['sand', 'hill', 'sea', 'grass'],
     ['sand', 'hill'],
     ['grass', 'sand', 'hill']],
    {'sea': ['grass'], 'sand': ['hill'], 'grass': ['hill', 'sand', 'sea'], 'hill': ['grass', 'hill']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'],
                ['grass', 'hill', 'sand'],
                ['hill', 'sand'],
                ['grass', 'hill']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['hill', 'hill'], ['grass', 'sea', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill'], ['grass']], 'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('fault site left support direction #1',
   [[['hill', 'sea', 'grass'], ['hill', 'sand'], ['grass', 'hill', 'sea']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand', 'sea'], 'grass': ['hill'], 'hill': ['hill', 'sea']}],
   {'domains': [['grass', 'hill', 'sea'], ['hill'], ['hill', 'sea']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill'],
     ['hill', 'sand', 'grass'],
     ['sand', 'hill', 'sea'],
     ['hill', 'grass', 'sea', 'sand'],
     ['sand', 'grass']],
    {'sea': ['hill', 'sea'],
     'sand': ['hill', 'sand', 'sea'],
     'grass': ['grass', 'hill', 'sand'],
     'hill': ['sand']}],
   {'domains': [['hill'], ['sand'], ['hill', 'sand', 'sea'], ['hill', 'sand'], ['sand']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['sand', 'hill', 'sand'], ['hill', 'grass', 'sea'], ['grass']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand'], ['grass'], ['grass']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['sea', 'sand', 'hill'],
     ['sand', 'hill', 'grass', 'sea'],
     ['sea', 'grass'],
     ['hill', 'grass', 'sea', 'sand'],
     ['sea']],
    {'sea': ['sand', 'sea'],
     'sand': ['grass', 'sand', 'sea'],
     'grass': ['grass', 'hill', 'sand'],
     'hill': ['sea']}],
   {'domains': [['hill', 'sand', 'sea'],
                ['grass', 'sand', 'sea'],
                ['grass', 'sea'],
                ['hill', 'sand', 'sea'],
                ['sea']],
    'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['hill', 'grass', 'sand', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'hill', 'sand', 'sea']], 'contradiction': False})]]
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(domains, rules):
    dom = [sorted(set(d)) for d in domains]
    changed = True
    while changed:
        changed = False
        for i in range(len(dom)):
            keep = []
            for t in dom[i]:
                ok_left = i == 0 or any(t in rules.get(l, []) or l == t for l in dom[i - 1])
                ok_right = i == len(dom) - 1 or any(r in rules.get(t, []) for r in dom[i + 1])
                if ok_left and ok_right:
                    keep.append(t)
            if keep != dom[i]:
                dom[i] = keep
                changed = True
    return {'domains': dom, 'contradiction': any(not d for d in dom)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill'], ['sand', 'hill'], ['sea'], ['grass', 'sand', 'sea', 'hill'], ['sea']],
    {'sea': ['hill', 'sea'],
     'sand': ['grass', 'hill', 'sea'],
     'grass': ['hill', 'sea'],
     'hill': ['sand', 'sea']}],
   {'domains': [['hill'], ['sand'], ['sea'], ['hill', 'sea'], ['sea']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'sea', 'grass', 'sea'],
     ['sea', 'sand', 'grass', 'hill'],
     ['sand', 'sea'],
     ['sand', 'hill', 'sea', 'grass']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand'], 'grass': ['sea'], 'hill': ['sand']}],
   {'domains': [['hill', 'sea'], ['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass', 'hill', 'sand']],
    'contradiction': False}),
  ('regression left support direction #3',
   [[['hill', 'grass', 'sand', 'sea'],
     ['sea', 'sand', 'hill', 'grass'],
     ['sand', 'sea', 'grass', 'hill', 'sea']],
    {'sea': ['sand'], 'sand': ['hill', 'sand'], 'grass': ['sand', 'sea'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'], ['hill', 'sand', 'sea'], ['hill', 'sand']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['hill', 'sand', 'sea'], ['grass', 'sand', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand', 'sea'], ['grass', 'sand']], 'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill', 'sea', 'grass', 'sea'],
     ['sea', 'sand', 'grass', 'hill'],
     ['sand', 'sea'],
     ['sand', 'hill', 'sea', 'grass']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand'], 'grass': ['sea'], 'hill': ['sand']}],
   {'domains': [['hill', 'sea'], ['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass', 'hill', 'sand']],
    'contradiction': False}),
  ('fault site left support direction #1',
   [[['grass'], ['grass', 'sea', 'sand', 'hill']],
    {'sea': ['grass', 'sand', 'sea'],
     'sand': ['grass', 'sand'],
     'grass': ['grass', 'hill'],
     'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass'], ['grass', 'hill']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'grass', 'sand', 'sea'],
     ['sea', 'sand', 'hill', 'grass'],
     ['sand', 'sea', 'grass', 'hill', 'sea']],
    {'sea': ['sand'], 'sand': ['hill', 'sand'], 'grass': ['sand', 'sea'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'], ['hill', 'sand', 'sea'], ['hill', 'sand']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['hill', 'sand', 'sea'], ['grass', 'sand', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand', 'sea'], ['grass', 'sand']], 'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('fault site left support direction #1',
   [[['sea', 'hill'], ['sea', 'hill', 'grass'], ['sea', 'sand', 'grass', 'hill']],
    {'sea': ['sand'],
     'sand': ['grass', 'sand', 'sea'],
     'grass': ['hill', 'sand', 'sea'],
     'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['hill'], ['grass', 'hill', 'sea'], ['grass', 'hill', 'sand', 'sea']],
    'contradiction': False}),
  ('regression left support direction #1',
   [[['hill', 'grass', 'sand', 'sea'],
     ['sea', 'sand', 'hill', 'grass'],
     ['sand', 'sea', 'grass', 'hill', 'sea']],
    {'sea': ['sand'], 'sand': ['hill', 'sand'], 'grass': ['sand', 'sea'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'], ['hill', 'sand', 'sea'], ['hill', 'sand']],
    'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'grass', 'sand'],
     ['sand', 'sea'],
     ['sand', 'sea', 'grass', 'hill'],
     ['sea'],
     ['grass', 'sea', 'hill']],
    {'sea': ['grass'], 'sand': ['grass', 'sand'], 'grass': ['grass', 'hill', 'sea'], 'hill': ['sea']}],
   {'domains': [['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass'], ['sea'], ['grass']],
    'contradiction': False}),
  ('regression left support direction #3',
   [[['hill'],
     ['hill', 'sand', 'grass'],
     ['sand', 'hill', 'sea'],
     ['hill', 'grass', 'sea', 'sand'],
     ['sand', 'grass']],
    {'sea': ['hill', 'sea'],
     'sand': ['hill', 'sand', 'sea'],
     'grass': ['grass', 'hill', 'sand'],
     'hill': ['sand']}],
   {'domains': [['hill'], ['sand'], ['hill', 'sand', 'sea'], ['hill', 'sand'], ['sand']],
    'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill', 'grass', 'sand'],
     ['sand', 'sea'],
     ['sand', 'sea', 'grass', 'hill'],
     ['sea'],
     ['grass', 'sea', 'hill']],
    {'sea': ['grass'], 'sand': ['grass', 'sand'], 'grass': ['grass', 'hill', 'sea'], 'hill': ['sea']}],
   {'domains': [['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass'], ['sea'], ['grass']],
    'contradiction': False}),
  ('fault site left support direction #1',
   [[['grass', 'hill', 'sand'], ['sand', 'grass', 'hill', 'sea']],
    {'sea': ['grass', 'hill', 'sea'], 'sand': ['hill'], 'grass': ['grass', 'sand'], 'hill': ['sand']}],
   {'domains': [['grass', 'hill', 'sand'], ['grass', 'hill', 'sand']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['hill', 'sand', 'grass', 'sea'],
     ['sand', 'hill', 'sea', 'grass'],
     ['sand', 'hill'],
     ['grass', 'sand', 'hill']],
    {'sea': ['grass'], 'sand': ['hill'], 'grass': ['hill', 'sand', 'sea'], 'hill': ['grass', 'hill']}],
   {'domains': [['grass', 'hill', 'sand', 'sea'],
                ['grass', 'hill', 'sand'],
                ['hill', 'sand'],
                ['grass', 'hill']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['hill', 'hill'], ['grass', 'sea', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill'], ['grass']], 'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'sea']], 'contradiction': False})],
 [('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('fault site left support direction #1',
   [[['hill', 'sea', 'grass'], ['hill', 'sand'], ['grass', 'hill', 'sea']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand', 'sea'], 'grass': ['hill'], 'hill': ['hill', 'sea']}],
   {'domains': [['grass', 'hill', 'sea'], ['hill'], ['hill', 'sea']], 'contradiction': False}),
  ('regression left support direction #1',
   [[['hill'],
     ['hill', 'sand', 'grass'],
     ['sand', 'hill', 'sea'],
     ['hill', 'grass', 'sea', 'sand'],
     ['sand', 'grass']],
    {'sea': ['hill', 'sea'],
     'sand': ['hill', 'sand', 'sea'],
     'grass': ['grass', 'hill', 'sand'],
     'hill': ['sand']}],
   {'domains': [['hill'], ['sand'], ['hill', 'sand', 'sea'], ['hill', 'sand'], ['sand']],
    'contradiction': False}),
  ('partial repair boundary #1',
   [[['sand', 'hill', 'sand'], ['hill', 'grass', 'sea'], ['grass']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand'], ['grass'], ['grass']], 'contradiction': False}),
  ('regression left support direction #2',
   [[['sea', 'sand', 'hill'],
     ['sand', 'hill', 'grass', 'sea'],
     ['sea', 'grass'],
     ['hill', 'grass', 'sea', 'sand'],
     ['sea']],
    {'sea': ['sand', 'sea'],
     'sand': ['grass', 'sand', 'sea'],
     'grass': ['grass', 'hill', 'sand'],
     'hill': ['sea']}],
   {'domains': [['hill', 'sand', 'sea'],
                ['grass', 'sand', 'sea'],
                ['grass', 'sea'],
                ['hill', 'sand', 'sea'],
                ['sea']],
    'contradiction': False}),
  ('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['hill', 'grass', 'sand', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'hill', 'sand', 'sea']], 'contradiction': False})]]
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:
Asymmetric tile rules produce illegal left neighbours.

A 1D strip of cells, each with a domain of tiles; rules[t] lists tiles allowed immediately to the right of t. Repeatedly remove tile t from cell i unless (i is first or some tile l in cell i-1 allows t on its right) and (i is last or t allows some tile in cell i+1), until stable. Domains are returned as sorted unique lists with a contradiction flag (any empty domain).

split: open-access


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

N = 1
observations = []
def solve(domains, rules):
    dom = [sorted(set(d)) for d in domains]
    changed = True
    while changed:
        changed = False
        for i in range(len(dom)):
            keep = []
            for t in dom[i]:
                ok_left = i == 0 or any(t in rules.get(l, []) for l in dom[i - 1])
                ok_right = i == len(dom) - 1 or any(r in rules.get(t, []) for r in dom[i + 1])
                if ok_left and ok_right:
                    keep.append(t)
            if keep != dom[i]:
                dom[i] = keep
    return {'domains': dom, 'contradiction': any(not d for d in dom)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'sea', 'grass', 'sea'],
     ['sea', 'sand', 'grass', 'hill'],
     ['sand', 'sea'],
     ['sand', 'hill', 'sea', 'grass']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand'], 'grass': ['sea'], 'hill': ['sand']}],
   {'domains': [['hill', 'sea'], ['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass', 'hill', 'sand']],
    'contradiction': False}),
  ('fault site propagation fixpoint #1',
   [[['sea', 'hill', 'grass', 'sand'],
     ['grass', 'sand', 'hill', 'sea'],
     ['hill'],
     ['sea', 'sand', 'sand'],
     ['hill', 'grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #2',
   [[['sand', 'hill', 'grass'], ['sea', 'hill', 'sand', 'grass'], ['sea', 'hill', 'grass', 'sea']],
    {'sea': ['hill', 'sand', 'sea'], 'sand': ['hill', 'sand', 'sea'], 'grass': ['sand'], 'hill': ['grass']}],
   {'domains': [['grass', 'sand'], ['hill', 'sand', 'sea'], ['grass', 'hill', 'sea']],
    'contradiction': False}),
  ('regression propagation fixpoint #3',
   [[['hill', 'grass', 'sand'], ['sand', 'sea'], ['grass']],
    {'sea': ['grass'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sand', 'sea']}],
   {'domains': [['hill'], ['sea'], ['grass']], 'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['sea', 'hill', 'grass', 'sand'],
     ['grass', 'sand', 'hill', 'sea'],
     ['hill'],
     ['sea', 'sand', 'sand'],
     ['hill', 'grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #2',
   [[['sand', 'sea', 'hill', 'grass'],
     ['hill', 'sea', 'grass', 'sand'],
     ['grass', 'sand', 'sea'],
     ['grass', 'sea', 'grass'],
     ['grass', 'hill', 'sea']],
    {'sea': ['hill'], 'sand': ['hill', 'sand'], 'grass': ['hill'], 'hill': ['hill']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'grass', 'sand'], ['sand', 'sea'], ['grass']],
    {'sea': ['grass'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sand', 'sea']}],
   {'domains': [['hill'], ['sea'], ['grass']], 'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sea', 'grass', 'hill', 'sand'],
     ['hill', 'sand', 'grass', 'sea'],
     ['hill'],
     ['sea', 'hill', 'grass'],
     ['sand', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'hill', 'sand'], ['grass'], ['hill'], ['grass'], ['hill', 'sand']],
    'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['hill'], ['sea', 'hill', 'grass', 'sand', 'hill'], ['sand', 'sea'], ['grass', 'sea', 'hill']],
    {'sea': ['grass', 'sand'], 'sand': ['hill', 'sea'], 'grass': ['sand', 'sea'], 'hill': ['hill']}],
   {'domains': [[], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['sand', 'hill', 'grass'], ['sea', 'hill', 'sand', 'grass'], ['sea', 'hill', 'grass', 'sea']],
    {'sea': ['hill', 'sand', 'sea'], 'sand': ['hill', 'sand', 'sea'], 'grass': ['sand'], 'hill': ['grass']}],
   {'domains': [['grass', 'sand'], ['hill', 'sand', 'sea'], ['grass', 'hill', 'sea']],
    'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sea', 'grass', 'grass'],
     ['sea', 'sand', 'grass'],
     ['sand', 'grass', 'hill'],
     ['grass', 'hill', 'sea', 'sand'],
     ['sea', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'sea'], ['grass', 'sand', 'sea'], ['grass', 'sand'], ['sand', 'sea'], ['sea']],
    'contradiction': False}),
  ('regression propagation fixpoint #3',
   [[['sea', 'sand', 'hill'], ['sea', 'hill', 'sand', 'grass'], ['hill', 'sea', 'grass'], ['hill', 'grass']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand', 'sea'], ['grass', 'sand'], ['grass', 'hill'], ['grass', 'hill']],
    'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['grass', 'sand', 'hill', 'sea'], ['hill', 'sand', 'sea', 'hill'], ['hill']],
    {'sea': ['grass', 'sand'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sea']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #2',
   [[['grass', 'sand', 'hill', 'hill'], ['sand', 'sea'], ['grass'], ['sea'], ['grass', 'hill', 'sand']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'sand', 'sea', 'grass'], ['hill', 'sea', 'grass', 'sand'], ['grass'], ['grass', 'hill']],
    {'sea': ['hill'], 'sand': ['hill'], 'grass': ['grass', 'sea'], 'hill': ['hill', 'sea']}],
   {'domains': [['grass'], ['grass'], ['grass'], ['grass']], 'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sand', 'hill', 'sea'], ['sea', 'sand', 'grass'], ['grass'], ['sand', 'hill', 'grass', 'sea', 'hill']],
    {'sea': ['grass'], 'sand': ['grass'], 'grass': ['hill', 'sea'], 'hill': ['hill', 'sand']}],
   {'domains': [['hill'], ['sand'], ['grass'], ['hill', 'sea']], 'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['sea'], ['sea', 'grass', 'hill'], ['grass'], ['sand', 'grass']],
    {'sea': ['grass', 'hill', 'sand'],
     'sand': ['hill', 'sand', 'sea'],
     'grass': ['hill', 'sand'],
     'hill': ['sand']}],
   {'domains': [[], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'grass', 'sand'], ['sand', 'sea'], ['grass']],
    {'sea': ['grass'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sand', 'sea']}],
   {'domains': [['hill'], ['sea'], ['grass']], 'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sand', 'hill', 'sea', 'grass'],
     ['sea', 'grass', 'sand', 'hill', 'sand'],
     ['grass'],
     ['sand', 'sea', 'hill', 'grass', 'sand']],
    {'sea': ['sand'], 'sand': ['grass', 'sea'], 'grass': ['hill', 'sand'], 'hill': ['hill', 'sand', 'sea']}],
   {'domains': [['grass', 'hill', 'sea'], ['sand'], ['grass'], ['hill', 'sand']], 'contradiction': False}),
  ('regression propagation fixpoint #3',
   [[['hill', 'sand', 'sea', 'grass', 'sea'],
     ['grass', 'sea', 'sand', 'hill'],
     ['sea', 'grass', 'sand'],
     ['grass'],
     ['sand', 'sea', 'hill', 'grass']],
    {'sea': ['hill', 'sea'],
     'sand': ['grass', 'hill', 'sand'],
     'grass': ['hill', 'sand', 'sea'],
     'hill': ['hill']}],
   {'domains': [['grass', 'sand'], ['grass', 'sand'], ['sand'], ['grass'], ['hill', 'sand', 'sea']],
    'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['hill', 'grass', 'sand', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'hill', 'sand', 'sea']], 'contradiction': False})]]
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(domains, rules):
    dom = [sorted(set(d)) for d in domains]
    changed = True
    while changed:
        changed = False
        for i in range(len(dom)):
            keep = []
            for t in dom[i]:
                ok_left = i == 0 or any(t in rules.get(l, []) for l in dom[i - 1])
                ok_right = i == len(dom) - 1 or any(r in rules.get(t, []) for r in dom[i + 1])
                if ok_left and ok_right:
                    keep.append(t)
            if keep != dom[i]:
                dom[i] = keep
                changed = keep == []
    return {'domains': dom, 'contradiction': any(not d for d in dom)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'sea', 'grass', 'sea'],
     ['sea', 'sand', 'grass', 'hill'],
     ['sand', 'sea'],
     ['sand', 'hill', 'sea', 'grass']],
    {'sea': ['grass', 'hill'], 'sand': ['hill', 'sand'], 'grass': ['sea'], 'hill': ['sand']}],
   {'domains': [['hill', 'sea'], ['grass', 'hill', 'sand'], ['sand', 'sea'], ['grass', 'hill', 'sand']],
    'contradiction': False}),
  ('fault site propagation fixpoint #1',
   [[['sea', 'hill', 'grass', 'sand'],
     ['grass', 'sand', 'hill', 'sea'],
     ['hill'],
     ['sea', 'sand', 'sand'],
     ['hill', 'grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #2',
   [[['sand', 'hill', 'grass'], ['sea', 'hill', 'sand', 'grass'], ['sea', 'hill', 'grass', 'sea']],
    {'sea': ['hill', 'sand', 'sea'], 'sand': ['hill', 'sand', 'sea'], 'grass': ['sand'], 'hill': ['grass']}],
   {'domains': [['grass', 'sand'], ['hill', 'sand', 'sea'], ['grass', 'hill', 'sea']],
    'contradiction': False}),
  ('regression propagation fixpoint #3',
   [[['hill', 'grass', 'sand'], ['sand', 'sea'], ['grass']],
    {'sea': ['grass'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sand', 'sea']}],
   {'domains': [['hill'], ['sea'], ['grass']], 'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['sea', 'hill', 'grass', 'sand'],
     ['grass', 'sand', 'hill', 'sea'],
     ['hill'],
     ['sea', 'sand', 'sand'],
     ['hill', 'grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #2',
   [[['sand', 'sea', 'hill', 'grass'],
     ['hill', 'sea', 'grass', 'sand'],
     ['grass', 'sand', 'sea'],
     ['grass', 'sea', 'grass'],
     ['grass', 'hill', 'sea']],
    {'sea': ['hill'], 'sand': ['hill', 'sand'], 'grass': ['hill'], 'hill': ['hill']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'grass', 'sand'], ['sand', 'sea'], ['grass']],
    {'sea': ['grass'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sand', 'sea']}],
   {'domains': [['hill'], ['sea'], ['grass']], 'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sea', 'grass', 'hill', 'sand'],
     ['hill', 'sand', 'grass', 'sea'],
     ['hill'],
     ['sea', 'hill', 'grass'],
     ['sand', 'hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'hill', 'sand'], ['grass'], ['hill'], ['grass'], ['hill', 'sand']],
    'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['hill'], ['sea', 'hill', 'grass', 'sand', 'hill'], ['sand', 'sea'], ['grass', 'sea', 'hill']],
    {'sea': ['grass', 'sand'], 'sand': ['hill', 'sea'], 'grass': ['sand', 'sea'], 'hill': ['hill']}],
   {'domains': [[], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['sand', 'hill', 'grass'], ['sea', 'hill', 'sand', 'grass'], ['sea', 'hill', 'grass', 'sea']],
    {'sea': ['hill', 'sand', 'sea'], 'sand': ['hill', 'sand', 'sea'], 'grass': ['sand'], 'hill': ['grass']}],
   {'domains': [['grass', 'sand'], ['hill', 'sand', 'sea'], ['grass', 'hill', 'sea']],
    'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sea', 'grass', 'grass'],
     ['sea', 'sand', 'grass'],
     ['sand', 'grass', 'hill'],
     ['grass', 'hill', 'sea', 'sand'],
     ['sea', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'sea'], ['grass', 'sand', 'sea'], ['grass', 'sand'], ['sand', 'sea'], ['sea']],
    'contradiction': False}),
  ('regression propagation fixpoint #3',
   [[['sea', 'sand', 'hill'], ['sea', 'hill', 'sand', 'grass'], ['hill', 'sea', 'grass'], ['hill', 'grass']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['hill', 'sand', 'sea'], ['grass', 'sand'], ['grass', 'hill'], ['grass', 'hill']],
    'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sand', 'sea']],
    {'sea': ['grass', 'sand'], 'sand': ['hill'], 'grass': ['hill'], 'hill': ['grass', 'hill', 'sea']}],
   {'domains': [['grass', 'sand', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['grass', 'sand', 'hill', 'sea'], ['hill', 'sand', 'sea', 'hill'], ['hill']],
    {'sea': ['grass', 'sand'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sea']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #2',
   [[['grass', 'sand', 'hill', 'hill'], ['sand', 'sea'], ['grass'], ['sea'], ['grass', 'hill', 'sand']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'sand', 'sea', 'grass'], ['hill', 'sea', 'grass', 'sand'], ['grass'], ['grass', 'hill']],
    {'sea': ['hill'], 'sand': ['hill'], 'grass': ['grass', 'sea'], 'hill': ['hill', 'sea']}],
   {'domains': [['grass'], ['grass'], ['grass'], ['grass']], 'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sand', 'hill', 'sea'], ['sea', 'sand', 'grass'], ['grass'], ['sand', 'hill', 'grass', 'sea', 'hill']],
    {'sea': ['grass'], 'sand': ['grass'], 'grass': ['hill', 'sea'], 'hill': ['hill', 'sand']}],
   {'domains': [['hill'], ['sand'], ['grass'], ['hill', 'sea']], 'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['grass', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'sea']], 'contradiction': False})],
 [('coast gradient #1',
   [[['sea'], ['sea', 'sand', 'grass', 'hill'], ['hill']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [[], [], []], 'contradiction': True}),
  ('fault site propagation fixpoint #1',
   [[['sea'], ['sea', 'grass', 'hill'], ['grass'], ['sand', 'grass']],
    {'sea': ['grass', 'hill', 'sand'],
     'sand': ['hill', 'sand', 'sea'],
     'grass': ['hill', 'sand'],
     'hill': ['sand']}],
   {'domains': [[], [], [], []], 'contradiction': True}),
  ('regression propagation fixpoint #1',
   [[['hill', 'grass', 'sand'], ['sand', 'sea'], ['grass']],
    {'sea': ['grass'], 'sand': ['sand'], 'grass': ['hill'], 'hill': ['grass', 'sand', 'sea']}],
   {'domains': [['hill'], ['sea'], ['grass']], 'contradiction': False}),
  ('regression propagation fixpoint #2',
   [[['sand', 'hill', 'sea', 'grass'],
     ['sea', 'grass', 'sand', 'hill', 'sand'],
     ['grass'],
     ['sand', 'sea', 'hill', 'grass', 'sand']],
    {'sea': ['sand'], 'sand': ['grass', 'sea'], 'grass': ['hill', 'sand'], 'hill': ['hill', 'sand', 'sea']}],
   {'domains': [['grass', 'hill', 'sea'], ['sand'], ['grass'], ['hill', 'sand']], 'contradiction': False}),
  ('regression propagation fixpoint #3',
   [[['hill', 'sand', 'sea', 'grass', 'sea'],
     ['grass', 'sea', 'sand', 'hill'],
     ['sea', 'grass', 'sand'],
     ['grass'],
     ['sand', 'sea', 'hill', 'grass']],
    {'sea': ['hill', 'sea'],
     'sand': ['grass', 'hill', 'sand'],
     'grass': ['hill', 'sand', 'sea'],
     'hill': ['hill']}],
   {'domains': [['grass', 'sand'], ['grass', 'sand'], ['sand'], ['grass'], ['hill', 'sand', 'sea']],
    'contradiction': False}),
  ('asymmetric rule #1',
   [[['sand'], ['hill', 'grass']], {'sand': ['grass'], 'grass': ['sand'], 'hill': ['sand']}],
   {'domains': [['sand'], ['grass']], 'contradiction': False}),
  ('duplicate domain entries #1',
   [[['grass', 'grass', 'sand']], {'grass': []}],
   {'domains': [['grass', 'sand']], 'contradiction': False}),
  ('control #1',
   [[['hill', 'grass', 'sand', 'sea']],
    {'sea': ['sea', 'sand'],
     'sand': ['sea', 'sand', 'grass'],
     'grass': ['sand', 'grass', 'hill'],
     'hill': ['grass']}],
   {'domains': [['grass', 'hill', 'sand', 'sea']], 'contradiction': False})]]
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:
Removals on the right never propagate back to the left.

A 1D strip of cells, each with a domain of tiles; rules[t] lists tiles allowed immediately to the right of t. Repeatedly remove tile t from cell i unless (i is first or some tile l in cell i-1 allows t on its right) and (i is last or t allows some tile in cell i+1), until stable. Domains are returned as sorted unique lists with a contradiction flag (any empty domain).

split: open-access