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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
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(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and k in roots and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
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:
Weak-keyed tables keep every value alive, leaking entries whose keys died.

Ephemeron entries [table, key, value]: the value is traced only when both the table and the key are reachable; values may make further keys reachable, so iterate to a fixpoint. Keys and tables are never retained by an entry. Return the sorted live set and the [table, key] entries of live tables whose key died (to be cleared).

split: open-access


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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in heap and k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A discarded WeakMap still retains values for keys that are alive elsewhere.

Ephemeron entries [table, key, value]: the value is traced only when both the table and the key are reachable; values may make further keys reachable, so iterate to a fixpoint. Keys and tables are never retained by an entry. Return the sorted live set and the [table, key] entries of live tables whose key died (to be cleared).

split: open-access


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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
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(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and v not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
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:
Clearing work is scheduled for tables that are themselves garbage.

Ephemeron entries [table, key, value]: the value is traced only when both the table and the key are reachable; values may make further keys reachable, so iterate to a fixpoint. Keys and tables are never retained by an entry. Return the sorted live set and the [table, key] entries of live tables whose key died (to be cleared).

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior and a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w & ~1
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior and a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Exact references never match an object start, so objects referenced from the stack are not pinned.

Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior and a <= s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior and a < hi):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A pointer just beyond an object in a gap keeps that object pinned.

Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.

split: open-access