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

N = 1
observations = []
def solve(flags, name):
    def ev(key, stack):
        f = flags.get(key)
        if f is None:
            return [None, 'MISSING', key]
        if key in stack:
            return [None, 'CYCLE', key]
        if not f['on']:
            return [f['off'], 'OFF', None]
        for pre, want in f.get('prereqs', []):
            got = ev(pre, stack + [key])
            if got[1] in ('MISSING', 'CYCLE'):
                return got
            if got[0] != want:
                return [f['off'], 'PREREQUISITE_FAILED', pre]
        return [f['serve'], 'ON', None]
    return ev(name, [])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 1',
   [{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 2',
   [{'a': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['d', 'x'], ['c', 'x']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]}},
    'b'],
   [None, 'MISSING', 'z'])],
 [('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 55',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['e', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['a', 'on'], ['z', 'on']]},
     'e': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'b'],
   ['off', 'PREREQUISITE_FAILED', 'e'])],
 [('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 11',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 12',
   [{'a': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['c', 'on'], ['z', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on']]},
     'c': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []}},
    'c'],
   [None, 'CYCLE', 'b'])],
 [('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('prerequisite graph sample 16',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
    'c'],
   ['x', 'ON', None]),
  ('prerequisite graph sample 17',
   [{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 55',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['e', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['a', 'on'], ['z', 'on']]},
     'e': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'b'],
   ['off', 'PREREQUISITE_FAILED', 'e'])],
 [('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 21',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   [None, 'MISSING', 'e']),
  ('prerequisite graph sample 22',
   [{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   ['off', 'OFF', None])]]
for label, args, expected in fixtures[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(flags, name):
    def ev(key, stack):
        f = flags.get(key)
        if f is None:
            return [None, 'MISSING', key]
        if key in stack:
            return [None, 'CYCLE', key]
        if not f['on']:
            return [f['off'], 'OFF', None]
        for pre, want in f.get('prereqs', []):
            got = ev(pre, stack + [key])
            if got[1] in ('MISSING', 'CYCLE'):
                return got
            if got[0] != want or got[1] != 'ON':
                return [f['off'], 'PREREQUISITE_FAILED', pre]
        return [f['serve'], 'ON', None]
    return ev(name, [])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 1',
   [{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 2',
   [{'a': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['d', 'x'], ['c', 'x']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]}},
    'b'],
   [None, 'MISSING', 'z'])],
 [('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 55',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['e', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['a', 'on'], ['z', 'on']]},
     'e': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'b'],
   ['off', 'PREREQUISITE_FAILED', 'e'])],
 [('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 11',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 12',
   [{'a': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['c', 'on'], ['z', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on']]},
     'c': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []}},
    'c'],
   [None, 'CYCLE', 'b'])],
 [('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('prerequisite graph sample 16',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
    'c'],
   ['x', 'ON', None]),
  ('prerequisite graph sample 17',
   [{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 55',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['e', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['a', 'on'], ['z', 'on']]},
     'e': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'b'],
   ['off', 'PREREQUISITE_FAILED', 'e'])],
 [('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 21',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   [None, 'MISSING', 'e']),
  ('prerequisite graph sample 22',
   [{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   ['off', 'OFF', None])]]
for label, args, expected in fixtures[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 dependent flag turns on although its prerequisite flag is switched off.

flags maps key -> {on, off, serve, prereqs:[[key, required variation]]}. Missing flags yield [None, MISSING, key]; revisiting a flag on the current path yields [None, CYCLE, key] (checked before on/off). An off flag serves [off, OFF, None]. Prerequisites are evaluated in order; MISSING/CYCLE results propagate unchanged; the first prerequisite that is OFF or serves a different variation stops evaluation with [off, PREREQUISITE_FAILED, that prerequisite key]. A prerequisite that itself failed counts as serving its off variation. Otherwise [serve, ON, None].

split: open-access


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

N = 1
observations = []
def solve(flags, name):
    def ev(key, stack):
        f = flags.get(key)
        if f is None:
            return [None, 'MISSING', key]
        if key in stack:
            return [None, 'CYCLE', key]
        if not f['on']:
            return [f['off'], 'OFF', None]
        for pre, want in f.get('prereqs', []):
            got = ev(pre, stack + [key])
            if got[1] in ('MISSING', 'CYCLE'):
                return got
            if got[0] != want or got[1] == 'OFF':
                return [f['off'], 'PREREQUISITE_FAILED', key]
        return [f['serve'], 'ON', None]
    return ev(name, [])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('prerequisite graph sample 1',
   [{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 2',
   [{'a': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['d', 'x'], ['c', 'x']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]}},
    'b'],
   [None, 'MISSING', 'z'])],
 [('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('prerequisite graph sample 6',
   [{'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'on'], ['d', 'off'], ['a', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['z', 'off']]}},
    'c'],
   ['off', 'OFF', None]),
  ('prerequisite graph sample 7',
   [{'a': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['z', 'x'], ['a', 'x'], ['a', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'x'], ['d', 'on'], ['b', 'on']]}},
    'c'],
   [None, 'MISSING', 'c']),
  ('prerequisite graph sample 29',
   [{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['e', 'on']]},
     'b': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': [['z', 'on']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['e', 'off'], ['b', 'on'], ['e', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'x']]},
     'e': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['c', 'on'], ['d', 'off'], ['e', 'off']]}},
    'd'],
   ['off', 'PREREQUISITE_FAILED', 'a'])],
 [('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 11',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 12',
   [{'a': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['c', 'on'], ['z', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on']]},
     'c': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []}},
    'c'],
   [None, 'CYCLE', 'b'])],
 [('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('prerequisite graph sample 16',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
    'c'],
   ['x', 'ON', None]),
  ('prerequisite graph sample 17',
   [{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 32',
   [{'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'off'], ['e', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on'], ['a', 'off']]},
     'd': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'on']]}},
    'c'],
   ['x', 'PREREQUISITE_FAILED', 'd'])],
 [('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 21',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   [None, 'MISSING', 'e']),
  ('prerequisite graph sample 22',
   [{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   ['off', 'OFF', None]),
  ('prerequisite graph sample 23',
   [{'a': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'e': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['c', 'on'], ['z', 'on']]}},
    'a'],
   ['x', 'ON', None])]]
for label, args, expected in fixtures[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(flags, name):
    def ev(key, stack):
        f = flags.get(key)
        if f is None:
            return [None, 'MISSING', key]
        if key in stack:
            return [None, 'CYCLE', key]
        if not f['on']:
            return [f['off'], 'OFF', None]
        for pre, want in f.get('prereqs', []):
            got = ev(pre, stack + [key])
            if got[1] in ('MISSING', 'CYCLE'):
                return got
            if got[0] != want or got[1] == 'OFF':
                return [f['off'], 'PREREQUISITE_FAILED', got[2]]
        return [f['serve'], 'ON', None]
    return ev(name, [])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('prerequisite graph sample 1',
   [{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 2',
   [{'a': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'on'], ['d', 'x'], ['c', 'x']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on'], ['c', 'on']]}},
    'b'],
   [None, 'MISSING', 'z'])],
 [('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('prerequisite graph sample 6',
   [{'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'on'], ['d', 'off'], ['a', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['z', 'off']]}},
    'c'],
   ['off', 'OFF', None]),
  ('prerequisite graph sample 7',
   [{'a': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['z', 'x'], ['a', 'x'], ['a', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'x'], ['d', 'on'], ['b', 'on']]}},
    'c'],
   [None, 'MISSING', 'c']),
  ('prerequisite graph sample 29',
   [{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['e', 'on']]},
     'b': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': [['z', 'on']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['e', 'off'], ['b', 'on'], ['e', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'x']]},
     'e': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['c', 'on'], ['d', 'off'], ['e', 'off']]}},
    'd'],
   ['off', 'PREREQUISITE_FAILED', 'a'])],
 [('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 11',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 12',
   [{'a': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['c', 'on'], ['z', 'x']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on']]},
     'c': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []}},
    'c'],
   [None, 'CYCLE', 'b'])],
 [('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('prerequisite graph sample 16',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
    'c'],
   ['x', 'ON', None]),
  ('prerequisite graph sample 17',
   [{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'd'],
   [None, 'MISSING', 'd']),
  ('prerequisite graph sample 32',
   [{'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'off'], ['e', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on'], ['a', 'off']]},
     'd': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'on']]}},
    'c'],
   ['x', 'PREREQUISITE_FAILED', 'd'])],
 [('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 21',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   [None, 'MISSING', 'e']),
  ('prerequisite graph sample 22',
   [{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   ['off', 'OFF', None]),
  ('prerequisite graph sample 23',
   [{'a': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'e': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['c', 'on'], ['z', 'on']]}},
    'a'],
   ['x', 'ON', None])]]
for label, args, expected in fixtures[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:
Debug output says a flag failed its own prerequisite instead of naming the blocking dependency.

flags maps key -> {on, off, serve, prereqs:[[key, required variation]]}. Missing flags yield [None, MISSING, key]; revisiting a flag on the current path yields [None, CYCLE, key] (checked before on/off). An off flag serves [off, OFF, None]. Prerequisites are evaluated in order; MISSING/CYCLE results propagate unchanged; the first prerequisite that is OFF or serves a different variation stops evaluation with [off, PREREQUISITE_FAILED, that prerequisite key]. A prerequisite that itself failed counts as serving its off variation. Otherwise [serve, ON, None].

split: open-access


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

N = 1
observations = []
def solve(flags, name):
    visited = []
    def ev(key, stack):
        f = flags.get(key)
        if f is None:
            return [None, 'MISSING', key]
        if key in visited:
            return [None, 'CYCLE', key]
        visited.append(key)
        if not f['on']:
            return [f['off'], 'OFF', None]
        for pre, want in f.get('prereqs', []):
            got = ev(pre, stack + [key])
            if got[1] in ('MISSING', 'CYCLE'):
                return got
            if got[0] != want or got[1] == 'OFF':
                return [f['off'], 'PREREQUISITE_FAILED', pre]
        return [f['serve'], 'ON', None]
    return ev(name, [])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 1',
   [{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
    'd'],
   [None, 'MISSING', 'd'])],
 [('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 33',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x'], ['a', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['a', 'on'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'off']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'x']]}},
    'b'],
   [None, 'CYCLE', 'b'])],
 [('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 11',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 27',
   [{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'x'], ['e', 'x'], ['d', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['b', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'e': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['z', 'on']]}},
    'd'],
   [None, 'CYCLE', 'd'])],
 [('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 16',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
    'c'],
   ['x', 'ON', None]),
  ('prerequisite graph sample 17',
   [{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'd'],
   [None, 'MISSING', 'd'])],
 [('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 21',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   [None, 'MISSING', 'e']),
  ('prerequisite graph sample 22',
   [{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   ['off', 'OFF', None])]]
for label, args, expected in fixtures[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(flags, name):
    def ev(key, stack):
        f = flags.get(key)
        if f is None:
            return [None, 'MISSING', key]
        if key in stack[1:]:
            return [None, 'CYCLE', key]
        if not f['on']:
            return [f['off'], 'OFF', None]
        for pre, want in f.get('prereqs', []):
            got = ev(pre, stack + [key])
            if got[1] in ('MISSING', 'CYCLE'):
                return got
            if got[0] != want or got[1] == 'OFF':
                return [f['off'], 'PREREQUISITE_FAILED', pre]
        return [f['serve'], 'ON', None]
    return ev(name, [])
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 1',
   [{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
     'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
    'd'],
   [None, 'MISSING', 'd'])],
 [('failure names the unmet prerequisite',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 33',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x'], ['a', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['a', 'on'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'off']]},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'x']]}},
    'b'],
   [None, 'CYCLE', 'b'])],
 [('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 11',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 27',
   [{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'x'], ['e', 'x'], ['d', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['b', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'e': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['z', 'on']]}},
    'd'],
   [None, 'CYCLE', 'd'])],
 [('missing prerequisite propagates MISSING',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
   [None, 'MISSING', 'zz']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 16',
   [{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
     'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
     'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
    'c'],
   ['x', 'ON', None]),
  ('prerequisite graph sample 17',
   [{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'd'],
   [None, 'MISSING', 'd'])],
 [('cycle through an off member reports CYCLE',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('first unmet prerequisite stops evaluation',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
     'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('later missing prerequisite is never reached',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
     'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['off', 'PREREQUISITE_FAILED', 'b']),
  ('nested failure serving required off variation passes',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
     'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
     'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('cycle revisits the root',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   [None, 'CYCLE', 'a']),
  ('diamond dependency is not a cycle',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'a'],
   ['on', 'ON', None]),
  ('prerequisite graph sample 21',
   [{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
     'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
     'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
    'e'],
   [None, 'MISSING', 'e']),
  ('prerequisite graph sample 22',
   [{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
     'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
     'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
     'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
     'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
    'a'],
   ['off', 'OFF', None])]]
for label, args, expected in fixtures[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:
Two flags that both depend on the same base flag report a prerequisite cycle.

flags maps key -> {on, off, serve, prereqs:[[key, required variation]]}. Missing flags yield [None, MISSING, key]; revisiting a flag on the current path yields [None, CYCLE, key] (checked before on/off). An off flag serves [off, OFF, None]. Prerequisites are evaluated in order; MISSING/CYCLE results propagate unchanged; the first prerequisite that is OFF or serves a different variation stops evaluation with [off, PREREQUISITE_FAILED, that prerequisite key]. A prerequisite that itself failed counts as serving its off variation. Otherwise [serve, ON, None].

split: open-access