FAILURE MAP
← Case archive

FA-39821 / Tree accessibility / Open access

Bounded accessible branch expansion eviction: Eviction ignores pinned descendant inside candidate subtree · case 01

Eviction ignores pinned descendant inside candidate subtree 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 `if closure&pinned: continue` by replacing it with `if victim in pinned: continue`.

THE FAILURE

The expansion-budget contract is violated at `if closure&pinned: continue` by replacing it with `if victim in pinned: continue`.

Unsuccessful approach: The partial repair `if closure<=pinned: continue` 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)):
        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 victim in 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', 'b', 'c', 'r'], ['q'], True, 7, {'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}]Passed
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', 'q', 'r'], ['b', 'c'], True, 5, {'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}]Failed
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 / 5bd4e7fcb967b7f8a1629e7cd7681b03a887362a1f410a08ec7d8a183a6d3b51

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,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']]=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[['q'], ['a', 'b', 'c', 'r'], True, 2, {'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', 'b', 'c', 'r'], ['q'], True, 7, {'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}]Passed
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[['q'], ['a', 'b', 'c', 'r'], True, 2, {'a': 11, '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}]Failed
pinned descendant[['q'], ['a', 'b', 'c', 'r'], True, 2, {'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}]Failed
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[['q'], ['a', 'b', 'c', 'r'], True, 2, {'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 / 92fae02b577adc9bdce488f19a2a19760cd00efe71b7f3b2686e156dfa26a521

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 / 40f817c5ae2e4516bb7daf6d0002885f34973a007ed2429ca4f194531087ae03