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

N = 1
observations = []
def solve(d):
    owned=d['transaction']==d['current_transaction'] and d['written_version']==d['current_version']
    rollback=owned and not d['success']
    parent=d['old_parent'] if rollback else d['new_parent']
    source=list(d['source'])
    if rollback: source=source[:d['old_index']]+[d['root']]+source[d['old_index']:]
    target=[x for x in d['target'] if not(rollback and x==d['root'])]
    levels={x:v-d['delta'] if rollback and x in d['closure'] else v for x,v in d['levels'].items()}
    focus=d['old_focus'] if rollback and d['focus']==d['owned_focus'] else d['focus']
    selection=d['selected']
    status='rolled-back' if rollback else 'committed'
    return [parent,source,target,levels,focus,selection,status]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 3, 'c': 4, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 3, 'c': 4, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 3, 'c': 4, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 2: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 4, 'c': 5, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 4, 'c': 5, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 4, 'c': 5, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 3: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 5, 'c': 6, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 5, 'c': 6, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 5, 'c': 6, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 4: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 6, 'c': 7, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 6, 'c': 7, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 6, 'c': 7, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 5: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 7, 'c': 8, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 7, 'c': 8, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 6, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 7, 'c': 8, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])]}
for label, data, expected in cases[N]:
    check(label, solve(data), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    owned=d['transaction']==d['current_transaction'] and d['written_version']==d['current_version']
    rollback=owned and not d['success']
    parent=d['old_parent'] if rollback else d['new_parent']
    source=list(d['source'])
    if rollback: source=source[:d['old_index']]+[d['root']]+source[d['old_index']:]
    target=[x for x in d['target'] if not(rollback and x==d['root'])]
    levels={x:v-d['delta'] if rollback and x in d['closure'] else v for x,v in d['levels'].items()}
    focus=d['old_focus'] if rollback and d['focus']==d['owned_focus'] else d['focus']
    selection=d['selected']
    status='rolled-back' if not d['success'] else 'committed'
    return [parent,source,target,levels,focus,selection,status]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 3, 'c': 4, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 3, 'c': 4, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 3, 'c': 4, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 1, 'current_version': 1, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 2, 'closure': ['b', 'c'], 'levels': {'b': 3, 'c': 4, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 2: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 4, 'c': 5, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 4, 'c': 5, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 4, 'c': 5, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 2, 'current_version': 2, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 3, 'closure': ['b', 'c'], 'levels': {'b': 4, 'c': 5, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 3: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 5, 'c': 6, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 5, 'c': 6, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 5, 'c': 6, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 3, 'current_version': 3, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 4, 'closure': ['b', 'c'], 'levels': {'b': 5, 'c': 6, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 4: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 6, 'c': 7, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 6, 'c': 7, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 6, 'c': 7, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 4, 'current_version': 4, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 5, 'closure': ['b', 'c'], 'levels': {'b': 6, 'c': 7, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])], 5: [('owned failure', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('success', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': True, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 7, 'c': 8, 'outside': 0}, 'b', ['c', 'outside'], 'committed']), ('new transaction', {'transaction': 't', 'current_transaction': 'new', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 7, 'c': 8, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('new parent version', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 6, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['q', ['a', 'z'], ['x', 'b', 'y'], {'b': 7, 'c': 8, 'outside': 0}, 'b', ['c', 'outside'], 'superseded']), ('outside focus', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 1, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'outside', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'b', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'outside', ['c', 'outside'], 'rolled-back']), ('original first', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 0, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['b', 'a', 'z'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back']), ('original last', {'transaction': 't', 'current_transaction': 't', 'written_version': 5, 'current_version': 5, 'success': False, 'old_parent': 'r', 'new_parent': 'q', 'source': ['a', 'z'], 'target': ['x', 'b', 'y'], 'root': 'b', 'old_index': 2, 'delta': 6, 'closure': ['b', 'c'], 'levels': {'b': 7, 'c': 8, 'outside': 0}, 'old_focus': 'c', 'focus': 'b', 'owned_focus': 'b', 'selected': ['c', 'outside'], 'old_selected': ['b']}, ['r', ['a', 'z', 'b'], ['x', 'y'], {'b': 1, 'c': 2, 'outside': 0}, 'c', ['c', 'outside'], 'rolled-back'])]}
for label, data, expected in cases[N]:
    check(label, solve(data), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Superseded operation is reported as committed or rolled back produces the wrong hierarchical widget state in a regression fixture.

A failed optimistic move may roll back only while the current parent version and transaction ID match its write. Restore the subtree root at its original sibling position, restore descendant levels by inverse delta, preserve later unrelated selection, and recover focus only if the optimistic move owned it.

split: open-access


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

N = 1
observations = []
def solve(d):
    valid=d['target'] in d['branches']
    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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(d):
    valid=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)

prompt:
Expansion budget admits disabled or nonbranch target produces the wrong hierarchical widget state in a regression fixture.

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

split: open-access