FAILURE MAP
← Case archive

FA-39801 / Tree accessibility / Open access

Bounded accessible branch expansion eviction: Budget eviction drops user pin or requested branch · case 01

Budget eviction drops user pin or requested 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 `pinned=set(d['pinned'])|path` by replacing it with `pinned=path`.

VERIFIED REPAIR

Restore `pinned=set(d['pinned'])|path` at this fault site while retaining the other tree state decisions.

Unsuccessful approach: The partial repair `pinned=set(d['pinned'])` 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=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[['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 / 70b3115762b25c3e1b978888d9b5f1101604f96e0406fec1c03225e85568c07e

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'])
    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[['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[['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 / 890259bd67464bee88b869ae6312acf393905c3966f9b86596efbc44772809d9

3 / The verified repair

Exit 0
"""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[['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', '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 / 9ec86e719d27d65e90d4357c4f50e2afff03cb5df5f97639180f6daba1698e5a

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:24.897264+00:00.

Case digest / 2e4bede39d41a0750732eae27fa2040f166b0214624a0bd960f7112d18dd6b12