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

N = 1
observations = []
def solve(d):
    valid=d['target'] in d['branches'] and d['target'] not in d['disabled']
    path=set(d['ancestors'].get(d['target'],[]))|{d['target']}
    pinned=set(d['pinned'])|path
    opened=set(d['open'])|path if valid else set(d['open'])
    evicted=[]
    for victim in sorted(opened,key=lambda x:d['ages'].get(x,0)):
        if sum(d['weights'][x] for x in opened)<=d['budget']: break
        if victim not in opened: continue
        closure={x for x in opened if x==victim or victim in d['ancestors'].get(x,[])}
        if closure&pinned: continue
        opened-=closure
        evicted.extend(sorted(closure))
    accepted=valid and sum(d['weights'][x] for x in opened)<=d['budget']
    result=opened if accepted else set(d['open'])
    ages=dict(d['ages'])
    ages[d['target']]=d['now']
    return [sorted(result),evicted if accepted else [],accepted,sum(d['weights'][x] for x in result),ages]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 11, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 11}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 11}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 11}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 11}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}])], 2: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 12, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 12}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 12}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 12}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 12}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}])], 3: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 13, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 13}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 13}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 13}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 13}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}])], 4: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 14, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 14}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 14}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 14}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 14}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}])], 5: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 15, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 15}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 15}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 15}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 15}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}])]}
for label, data, expected in cases[N]:
    check(label, solve(data), 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(d):
    valid=d['target'] in d['branches'] and d['target'] not in d['disabled']
    path=set(d['ancestors'].get(d['target'],[]))|{d['target']}
    pinned=set(d['pinned'])|path
    opened=set(d['open'])|path if valid else set(d['open'])
    evicted=[]
    for victim in sorted(opened,key=lambda x:d['ages'].get(x,0)):
        if sum(d['weights'][x] for x in opened)<=d['budget']: break
        if victim not in opened: continue
        closure={x for x in opened if x==victim or victim in d['ancestors'].get(x,[])}
        if closure&pinned: continue
        opened-=closure
        evicted.extend(sorted(closure))
    accepted=valid and sum(d['weights'][x] for x in opened)<=d['budget']
    result=opened if accepted else set(d['open'])
    ages=dict(d['ages'])
    if accepted: ages[d['target']]=0
    return [sorted(result),evicted if accepted else [],accepted,sum(d['weights'][x] for x in result),ages]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 11, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 11}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 11}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 11}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 11}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 11}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 11, 'c': 4, 'leaf': 5}])], 2: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 12, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 12}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 12}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 12}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 12}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 12}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 12, 'c': 4, 'leaf': 5}])], 3: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 13, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 13}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 13}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 13}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 13}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 13}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 13, 'c': 4, 'leaf': 5}])], 4: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 14, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 14}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 14}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 14}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 14}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 14}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 14, 'c': 4, 'leaf': 5}])], 5: [('weighted eviction', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['a', 'q', 'r'], ['b', 'c'], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('older unrelated root', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 6, 'b': 5, 'q': 0, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 6, 'b': 5, 'q': 0, 'a': 15, 'c': 4, 'leaf': 5}]), ('fits exactly', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 9, 'now': 15}, [['a', 'b', 'c', 'q', 'r'], [], True, 9, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('path impossible', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 2, 'now': 15}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('pinned descendant', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': ['c'], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['a', 'b', 'c', 'r'], ['q'], True, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('disabled request', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': ['a'], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('leaf request', {'target': 'leaf', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 7, 'now': 15}, [['b', 'c', 'q', 'r'], [], False, 7, {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}]), ('root absent', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 6, 'now': 15}, [['a', 'q', 'r'], [], True, 5, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}]), ('evict two groups', {'target': 'a', 'branches': ['r', 'a', 'b', 'c', 'q'], 'disabled': [], 'ancestors': {'a': ['r'], 'b': ['r'], 'c': ['r', 'b'], 'leaf': ['r', 'a']}, 'pinned': [], 'open': ['r', 'b', 'c', 'q'], 'ages': {'r': 0, 'b': 1, 'q': 2, 'a': 3, 'c': 4, 'leaf': 5}, 'weights': {'r': 1, 'a': 2, 'b': 3, 'c': 1, 'q': 2, 'leaf': 1}, 'budget': 3, 'now': 15}, [['a', 'r'], ['b', 'c', 'q'], True, 3, {'r': 0, 'b': 1, 'q': 2, 'a': 15, 'c': 4, 'leaf': 5}])]}
for label, data, expected in cases[N]:
    check(label, solve(data), 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:
Rejected request or wrong timestamp corrupts branch recency produces the wrong hierarchical widget state in a regression fixture.

Expanded branches have positive weights, distinct recency ages, and a positive budget. Opening a target requires its entire ancestor path. Evict oldest expandable subtrees atomically until within budget, never evicting a subtree containing a pinned branch or requested path. If the required path cannot fit, reject without changing expansion or recency.

split: open-access


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

N = 1
observations = []
def solve(d):
    r = d['roots']
    return {'canonical': [x[0] for x in sorted(r,key=lambda x:x[1])],
    'collisions': sorted({x[0] for x in r if sum(y[0]==x[0] for y in r)>1}),
    'minimum': min([x[1] for x in r],default=None),
    'population': sum(x[2] for x in r),
    'cardinality': [i for i,x in enumerate(r) if x[2] != 2**x[0]],
    'children': [i for i,x in enumerate(r) if x[3] != list(range(x[0]-1,-1,-1))]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 8, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 9, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 10, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 11, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 12, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    r = d['roots']
    return {'canonical': sorted(set(x[0] for x in r)),
    'collisions': sorted({x[0] for x in r if sum(y[0]==x[0] for y in r)>1}),
    'minimum': min([x[1] for x in r],default=None),
    'population': sum(x[2] for x in r),
    'cardinality': [i for i,x in enumerate(r) if x[2] != 2**x[0]],
    'children': [i for i,x in enumerate(r) if x[3] != list(range(x[0]-1,-1,-1))]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 8, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 9, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 10, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 11, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 12, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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:
The bounded binomial forest certificate reports an incorrect canonical.

For a binomial-forest certificate, roots is a list of [rank,key,node_count,child_ranks]. Report canonical rank order, duplicate ranks, root minimum, size, tree-cardinality failures, and descending child-rank failures. No implicit tree nodes are present.

split: open-access


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

N = 1
observations = []
def solve(d):
    r = d['roots']
    return {'canonical': sorted([x[0] for x in r]),
    'collisions': sorted({r[i][0] for i in range(1,len(r)) if r[i][0]==r[i-1][0]}),
    'minimum': min([x[1] for x in r],default=None),
    'population': sum(x[2] for x in r),
    'cardinality': [i for i,x in enumerate(r) if x[2] != 2**x[0]],
    'children': [i for i,x in enumerate(r) if x[3] != list(range(x[0]-1,-1,-1))]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 8, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 9, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 10, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 11, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 12, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    r = d['roots']
    return {'canonical': sorted([x[0] for x in r]),
    'collisions': sorted({x[0] for x in r if sum(y[0]==x[0] for y in r)>2}),
    'minimum': min([x[1] for x in r],default=None),
    'population': sum(x[2] for x in r),
    'cardinality': [i for i,x in enumerate(r) if x[2] != 2**x[0]],
    'children': [i for i,x in enumerate(r) if x[3] != list(range(x[0]-1,-1,-1))]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 8, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 9, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 10, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 11, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 12, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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:
The bounded binomial forest certificate reports an incorrect collisions.

For a binomial-forest certificate, roots is a list of [rank,key,node_count,child_ranks]. Report canonical rank order, duplicate ranks, root minimum, size, tree-cardinality failures, and descending child-rank failures. No implicit tree nodes are present.

split: open-access


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

N = 1
observations = []
def solve(d):
    r = d['roots']
    return {'canonical': sorted([x[0] for x in r]),
    'collisions': sorted({x[0] for x in r if sum(y[0]==x[0] for y in r)>1}),
    'minimum': min(r,default=[0,None],key=lambda x:x[0])[1],
    'population': sum(x[2] for x in r),
    'cardinality': [i for i,x in enumerate(r) if x[2] != 2**x[0]],
    'children': [i for i,x in enumerate(r) if x[3] != list(range(x[0]-1,-1,-1))]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 8, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 9, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 10, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 11, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 12, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    r = d['roots']
    return {'canonical': sorted([x[0] for x in r]),
    'collisions': sorted({x[0] for x in r if sum(y[0]==x[0] for y in r)>1}),
    'minimum': r[0][1] if r else None,
    'population': sum(x[2] for x in r),
    'cardinality': [i for i,x in enumerate(r) if x[2] != 2**x[0]],
    'children': [i for i,x in enumerate(r) if x[3] != list(range(x[0]-1,-1,-1))]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 8, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 9, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 10, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 11, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})], [({'roots': []}, {'canonical': [], 'collisions': [], 'minimum': None, 'population': 0, 'cardinality': [], 'children': []}), ({'roots': [[0, 8, 1, []]]}, {'canonical': [0], 'collisions': [], 'minimum': 8, 'population': 1, 'cardinality': [], 'children': []}), ({'roots': [[2, 9, 4, [1, 0]], [0, 3, 1, []], [2, 2, 4, [1, 0]]]}, {'canonical': [0, 2, 2], 'collisions': [2], 'minimum': 2, 'population': 9, 'cardinality': [], 'children': []}), ({'roots': [[3, 1, 8, [2, 1, 0]], [1, 5, 2, [0]]]}, {'canonical': [1, 3], 'collisions': [], 'minimum': 1, 'population': 10, 'cardinality': [], 'children': []}), ({'roots': [[2, 4, 5, [0, 1]], [1, 4, 1, [0]]]}, {'canonical': [1, 2], 'collisions': [], 'minimum': 4, 'population': 6, 'cardinality': [0, 1], 'children': [0]}), ({'roots': [[1, 7, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]}), ({'roots': [[1, 12, 2, []], [3, 0, 7, [2, 0, 1]], [1, 2, 2, [0]]]}, {'canonical': [1, 1, 3], 'collisions': [1], 'minimum': 0, 'population': 11, 'cardinality': [1], 'children': [0, 1]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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:
The bounded binomial forest certificate reports an incorrect minimum.

For a binomial-forest certificate, roots is a list of [rank,key,node_count,child_ranks]. Report canonical rank order, duplicate ranks, root minimum, size, tree-cardinality failures, and descending child-rank failures. No implicit tree nodes are present.

split: open-access