FAILURE MAP
← Case archive

FA-39806 / Tree accessibility / Open access

Bounded accessible branch expansion eviction: Eviction chooses lexicographic or most-recent branch · case 01

Eviction chooses lexicographic or most-recent branch produces the wrong hierarchical widget state in a regression fixture.

Verified by executionVariant 1 · 9 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The expansion-budget contract is violated at `sorted(opened,key=lambda x:d['ages'].get(x,0))` by replacing it with `sorted(opened,key=lambda x:d['ages'].get(x,0),reverse=True)`.

THE FAILURE

The expansion-budget contract is violated at `sorted(opened,key=lambda x:d['ages'].get(x,0))` by replacing it with `sorted(opened,key=lambda x:d['ages'].get(x,0),reverse=True)`.

Unsuccessful approach: The partial repair `sorted(opened)` still violates a boundary or preservation case.

Case contract

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.

Why this case matters

Offline executable model of a hierarchical accessibility interaction; inputs are bounded and valid as stipulated. No browser, assistive technology, or normative ARIA conformance is claimed.

1 / The failure

Exit 1
"""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),reverse=True):
        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']]=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)
Boundary fixtureActualExpectedOutcome
weighted eviction[['a', 'b', 'r'], ['c', 'q'], True, 6, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'q', 'r'], ['b', 'c'], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Failed
older unrelated root[['a', 'q', 'r'], ['b', 'c'], True, 5, {'a': 11, 'b': 5, 'c': 4, 'leaf': 5, 'q': 0, 'r': 6}][['a', 'b', 'c', 'r'], ['q'], True, 7, {'a': 11, 'b': 5, 'c': 4, 'leaf': 5, 'q': 0, 'r': 6}]Failed
fits exactly[['a', 'b', 'c', 'q', 'r'], [], True, 9, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'b', 'c', 'q', 'r'], [], True, 9, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
path impossible[['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
pinned descendant[['a', 'b', 'c', 'r'], ['q'], True, 7, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'b', 'c', 'r'], ['q'], True, 7, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
disabled request[['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
leaf request[['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
root absent[['a', 'q', 'r'], [], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'q', 'r'], [], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
evict two groups[['a', 'r'], ['c', 'q', 'b'], True, 3, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'r'], ['b', 'c', 'q'], True, 3, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Failed

SHA-256 / bab4281b5fd17b3499c4adc7a0d226a6ee41cbbb482e23685404e4a6095ace54

2 / The unsuccessful fix

Exit 1
"""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):
        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']]=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)
Boundary fixtureActualExpectedOutcome
weighted eviction[['a', 'q', 'r'], ['b', 'c'], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'q', 'r'], ['b', 'c'], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
older unrelated root[['a', 'q', 'r'], ['b', 'c'], True, 5, {'a': 11, 'b': 5, 'c': 4, 'leaf': 5, 'q': 0, 'r': 6}][['a', 'b', 'c', 'r'], ['q'], True, 7, {'a': 11, 'b': 5, 'c': 4, 'leaf': 5, 'q': 0, 'r': 6}]Failed
fits exactly[['a', 'b', 'c', 'q', 'r'], [], True, 9, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'b', 'c', 'q', 'r'], [], True, 9, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
path impossible[['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
pinned descendant[['a', 'b', 'c', 'r'], ['q'], True, 7, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'b', 'c', 'r'], ['q'], True, 7, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
disabled request[['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
leaf request[['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['b', 'c', 'q', 'r'], [], False, 7, {'a': 3, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
root absent[['a', 'q', 'r'], [], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'q', 'r'], [], True, 5, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed
evict two groups[['a', 'r'], ['b', 'c', 'q'], True, 3, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}][['a', 'r'], ['b', 'c', 'q'], True, 3, {'a': 11, 'b': 1, 'c': 4, 'leaf': 5, 'q': 2, 'r': 0}]Passed

SHA-256 / 02c1d3add467b6ce20dd58fb7ff65b6fda53621dbfec216a832a5136139c5d3c

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 9 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

Synthetic deterministic hierarchical-widget data contract; not an implementation of a browser accessibility tree. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:43:25.257035+00:00.

Case digest / cb50608b6cf6bade01e1bfe75e001b435590e3f8d8d7cbcb3005998448ddabe0