FA-39666 / Tree accessibility / Open access
Hierarchical sibling sort and stable identity: Sort replacement closure duplicates descendants or deletes unrelated roots · case 01
Sort replacement closure duplicates descendants or deletes unrelated roots produces the wrong hierarchical widget state in a regression fixture.
ROOT CAUSE
The sibling-sort contract is violated at `{x for block in blocks.values() for x in block}` by replacing it with `set(roots)`.
VERIFIED REPAIR
Restore `{x for block in blocks.values() for x in block}` at this fault site while retaining the other tree state decisions.
Unsuccessful approach: The partial repair `set(d['order'])` still violates a boundary or preservation case.
Case contract
Only direct children of the target parent are sorted by casefolded display label, with original order retained on ties; each child subtree moves as one block. Missing labels sort last in ascending order; descending reverses the complete comparison order. Focus, selection and expansion remain ID-based; sibling positions are recomputed from sorted roots.
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):
roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
key=lambda x:(d['labels'].get(x) is None,(d['labels'].get(x) or '').casefold())
ordered=sorted(roots,key=key,reverse=d['descending'])
blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
closure=set(roots)
first=min((d['order'].index(x) for x in closure),default=len(d['order']))
prefix=[x for x in d['order'][:first] if x not in closure]
suffix=[x for x in d['order'][first:] if x not in closure]
result=prefix+[x for r in ordered for x in blocks[r]]+suffix
positions={x:i+1 for i,x in enumerate(ordered)}
return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| ascending | [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'zz', 'zzz', 'q'], {'a': 1, 'b': 3, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'b': 3, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| descending | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'zz', 'zzz', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| stable tie | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'zz', 'zzz', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| case fold | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'zz', 'zzz', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| empty siblings | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']] | Passed |
| empty label | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'zz', 'zzz', 'q'], {'a': 2, 'b': 3, 'z': 1}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'a': 2, 'b': 3, 'z': 1}, 'z', ['zzz'], ['r', 'z']] | Failed |
SHA-256 / 8b6f0ef346cf61deaf315b48bca33dc175fb79c7894394b608082e01f87a3d23
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
key=lambda x:(d['labels'].get(x) is None,(d['labels'].get(x) or '').casefold())
ordered=sorted(roots,key=key,reverse=d['descending'])
blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
closure=set(d['order'])
first=min((d['order'].index(x) for x in closure),default=len(d['order']))
prefix=[x for x in d['order'][:first] if x not in closure]
suffix=[x for x in d['order'][first:] if x not in closure]
result=prefix+[x for r in ordered for x in blocks[r]]+suffix
positions={x:i+1 for i,x in enumerate(ordered)}
return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| ascending | [['a', 'z', 'zz', 'zzz', 'b'], {'a': 1, 'b': 3, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'b': 3, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| descending | [['b', 'z', 'zz', 'zzz', 'a'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| stable tie | [['b', 'z', 'zz', 'zzz', 'a'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| case fold | [['b', 'z', 'zz', 'zzz', 'a'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Failed |
| empty siblings | [[], {}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']] | Failed |
| empty label | [['z', 'zz', 'zzz', 'a', 'b'], {'a': 2, 'b': 3, 'z': 1}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'a': 2, 'b': 3, 'z': 1}, 'z', ['zzz'], ['r', 'z']] | Failed |
SHA-256 / a8264ed335dfc8bed33f75f1ba9557c238f95f298a82c97d70f6387e61069eb3
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
roots=[x for x in d['order'] if d['parents'].get(x)==d['parent']]
key=lambda x:(d['labels'].get(x) is None,(d['labels'].get(x) or '').casefold())
ordered=sorted(roots,key=key,reverse=d['descending'])
blocks={r:[x for x in d['order'] if x==r or r in d['ancestors'].get(x,[])] for r in roots}
closure={x for block in blocks.values() for x in block}
first=min((d['order'].index(x) for x in closure),default=len(d['order']))
prefix=[x for x in d['order'][:first] if x not in closure]
suffix=[x for x in d['order'][first:] if x not in closure]
result=prefix+[x for r in ordered for x in blocks[r]]+suffix
positions={x:i+1 for i,x in enumerate(ordered)}
return [result,positions,d['focus'],d['selected'],d['expanded']]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {1: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X1', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 2: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X2', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 3: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X3', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 4: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X4', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])], 5: [('ascending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'z': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']]), ('descending', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': True, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('stable tie', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'SAME', 'a': 'same', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('case fold', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'Straße', 'a': 'STRASSE', 'b': 'other'}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'b': 1, 'z': 2, 'a': 3}, 'z', ['zzz'], ['r', 'z']]), ('empty siblings', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'absent', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': 'beta', 'a': 'Alpha', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']]), ('empty label', {'order': ['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], 'parents': {'outside': None, 'r': None, 'z': 'r', 'zz': 'z', 'zzz': 'zz', 'a': 'r', 'b': 'r', 'q': None}, 'parent': 'r', 'ancestors': {'z': ['r'], 'zz': ['r', 'z'], 'zzz': ['r', 'z', 'zz'], 'a': ['r'], 'b': ['r']}, 'labels': {'z': '', 'a': 'X5', 'b': None}, 'descending': False, 'focus': 'z', 'selected': ['zzz'], 'expanded': ['r', 'z']}, [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'z': 1, 'a': 2, 'b': 3}, 'z', ['zzz'], ['r', 'z']])]}
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| ascending | [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'b': 3, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'a', 'z', 'zz', 'zzz', 'b', 'q'], {'a': 1, 'b': 3, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Passed |
| descending | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Passed |
| stable tie | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Passed |
| case fold | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'b', 'z', 'zz', 'zzz', 'a', 'q'], {'a': 3, 'b': 1, 'z': 2}, 'z', ['zzz'], ['r', 'z']] | Passed |
| empty siblings | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {}, 'z', ['zzz'], ['r', 'z']] | Passed |
| empty label | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'a': 2, 'b': 3, 'z': 1}, 'z', ['zzz'], ['r', 'z']] | [['outside', 'r', 'z', 'zz', 'zzz', 'a', 'b', 'q'], {'a': 2, 'b': 3, 'z': 1}, 'z', ['zzz'], ['r', 'z']] | Passed |
SHA-256 / 1dcdf2de62849b93bfda5672dd139b165cddae17971fcd35a9b4914b8146c5f4
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:23.483156+00:00.
Case digest / e119a03a6277dc56ec4c240b10cbbe5b4bfdd855d4c6badc857a041b67a8b94d