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

N = 1
observations = []
def solve(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = max(acks.get(mb, {}).get(origin, 0) for mb in live)
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = sorted(acks.get(mb, {}).get(origin, 0) for mb in live)[len(live) // 2]
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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:
Tombstones are purged while some replicas have not yet seen the deletion, so those replicas later resurrect the element.

Tombstones are [element, origin, seq]. acks maps replica -> {origin: highest delivered seq}. The live membership is members minus departed. A tombstone is causally stable, and may be purged, when every live member has reported an ack for its origin at or above seq; a live member with no report counts as zero. Other reporters are ignored. Return sorted purged and kept elements.

split: open-access


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

N = 1
observations = []
def solve(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in acks if mb not in departed)
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in set(live) | set(acks))
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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:
A member that has never reported is treated as caught up.

Tombstones are [element, origin, seq]. acks maps replica -> {origin: highest delivered seq}. The live membership is members minus departed. A tombstone is causally stable, and may be purged, when every live member has reported an ack for its origin at or above seq; a live member with no report counts as zero. Other reporters are ignored. Return sorted purged and kept elements.

split: open-access


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

N = 1
observations = []
def solve(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed or mb in acks]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in live)
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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:
After a replica leaves the group, tombstones are never collected.

Tombstones are [element, origin, seq]. acks maps replica -> {origin: highest delivered seq}. The live membership is members minus departed. A tombstone is causally stable, and may be purged, when every live member has reported an ack for its origin at or above seq; a live member with no report counts as zero. Other reporters are ignored. Return sorted purged and kept elements.

split: open-access


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

N = 1
observations = []
def solve(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in live)
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] > seq:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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(tombstones, acks, members, departed):
    live = [mb for mb in members if mb not in departed]
    stable = {}
    for origin in sorted({t[1] for t in tombstones}):
        stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in live)
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq - 1:
            purged.append(elem)
        else:
            kept.append(elem)
    return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
    5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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:
Tombstones that every member has acknowledged are retained one round too long.

Tombstones are [element, origin, seq]. acks maps replica -> {origin: highest delivered seq}. The live membership is members minus departed. A tombstone is causally stable, and may be purged, when every live member has reported an ack for its origin at or above seq; a live member with no report counts as zero. Other reporters are ignored. Return sorted purged and kept elements.

split: open-access


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

N = 1
observations = []
def solve(length, ops):
    best = [None] * length
    for kind, start, end, stamp in ops:
        st = tuple(stamp)
        for i in range(max(start, 0), min(end + 1, length)):
            if best[i] is None or st > best[i][0]:
                best[i] = (st, kind)
    spans = []
    for i, b in enumerate(best):
        if b is not None and b[1] == 'bold':
            if spans and spans[-1][1] == i:
                spans[-1][1] = i + 1
            else:
                spans.append([i, i + 1])
    return spans
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later unbold wins inside a bold range', [9, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [9, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [9, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [9, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [9, [['bold', 6, 9, [1, 'a']]]], [[6, 9]]), ('range end is exclusive', [9, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [9, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [9, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [9, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [9, [['bold', 8, 10, [1, 'a']], ['unbold', -1, 1, [2, 'a']]]], [[8, 9]])],
    2: [('later unbold wins inside a bold range', [10, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [10, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [10, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [10, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [10, [['bold', 7, 10, [1, 'a']]]], [[7, 10]]), ('range end is exclusive', [10, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [10, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [10, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [10, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [10, [['bold', 9, 12, [1, 'a']], ['unbold', -2, 1, [2, 'a']]]], [[9, 10]])],
    3: [('later unbold wins inside a bold range', [11, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [11, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [11, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [11, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [11, [['bold', 8, 11, [1, 'a']]]], [[8, 11]]), ('range end is exclusive', [11, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [11, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [11, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [11, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [11, [['bold', 10, 14, [1, 'a']], ['unbold', -3, 1, [2, 'a']]]], [[10, 11]])],
    4: [('later unbold wins inside a bold range', [12, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [12, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [12, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [12, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [12, [['bold', 9, 12, [1, 'a']]]], [[9, 12]]), ('range end is exclusive', [12, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [12, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [12, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [12, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [12, [['bold', 11, 16, [1, 'a']], ['unbold', -4, 1, [2, 'a']]]], [[11, 12]])],
    5: [('later unbold wins inside a bold range', [13, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [13, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [13, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [13, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [13, [['bold', 10, 13, [1, 'a']]]], [[10, 13]]), ('range end is exclusive', [13, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [13, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [13, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [13, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [13, [['bold', 12, 18, [1, 'a']], ['unbold', -5, 1, [2, 'a']]]], [[12, 13]])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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(length, ops):
    best = [None] * length
    for kind, start, end, stamp in ops:
        st = tuple(stamp)
        for i in range(max(start, 0), min(end, length - 1)):
            if best[i] is None or st > best[i][0]:
                best[i] = (st, kind)
    spans = []
    for i, b in enumerate(best):
        if b is not None and b[1] == 'bold':
            if spans and spans[-1][1] == i:
                spans[-1][1] = i + 1
            else:
                spans.append([i, i + 1])
    return spans
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later unbold wins inside a bold range', [9, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [9, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [9, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [9, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [9, [['bold', 6, 9, [1, 'a']]]], [[6, 9]]), ('range end is exclusive', [9, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [9, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [9, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [9, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [9, [['bold', 8, 10, [1, 'a']], ['unbold', -1, 1, [2, 'a']]]], [[8, 9]])],
    2: [('later unbold wins inside a bold range', [10, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [10, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [10, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [10, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [10, [['bold', 7, 10, [1, 'a']]]], [[7, 10]]), ('range end is exclusive', [10, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [10, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [10, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [10, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [10, [['bold', 9, 12, [1, 'a']], ['unbold', -2, 1, [2, 'a']]]], [[9, 10]])],
    3: [('later unbold wins inside a bold range', [11, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [11, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [11, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [11, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [11, [['bold', 8, 11, [1, 'a']]]], [[8, 11]]), ('range end is exclusive', [11, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [11, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [11, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [11, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [11, [['bold', 10, 14, [1, 'a']], ['unbold', -3, 1, [2, 'a']]]], [[10, 11]])],
    4: [('later unbold wins inside a bold range', [12, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [12, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [12, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [12, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [12, [['bold', 9, 12, [1, 'a']]]], [[9, 12]]), ('range end is exclusive', [12, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [12, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [12, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [12, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [12, [['bold', 11, 16, [1, 'a']], ['unbold', -4, 1, [2, 'a']]]], [[11, 12]])],
    5: [('later unbold wins inside a bold range', [13, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [13, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [13, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [13, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [13, [['bold', 10, 13, [1, 'a']]]], [[10, 13]]), ('range end is exclusive', [13, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [13, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [13, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [13, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [13, [['bold', 12, 18, [1, 'a']], ['unbold', -5, 1, [2, 'a']]]], [[12, 13]])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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:
Formatting bleeds onto the character just after the selected range.

A text of `length` characters receives ["bold"|"unbold", start, end, stamp] operations over half-open ranges clamped to the text. Each character takes the operation with the largest stamp (counter, replica) covering it; it is bold when that operation is "bold". Return maximal bold spans as [start, end) pairs in order.

split: open-access


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

N = 1
observations = []
def solve(length, ops):
    best = [None] * length
    for kind, start, end, stamp in ops:
        st = tuple(stamp)
        for i in range(max(start, 0), min(end, length)):
            best[i] = (st, kind)
    spans = []
    for i, b in enumerate(best):
        if b is not None and b[1] == 'bold':
            if spans and spans[-1][1] == i:
                spans[-1][1] = i + 1
            else:
                spans.append([i, i + 1])
    return spans
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later unbold wins inside a bold range', [9, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [9, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [9, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [9, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [9, [['bold', 6, 9, [1, 'a']]]], [[6, 9]]), ('range end is exclusive', [9, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [9, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [9, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [9, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [9, [['bold', 8, 10, [1, 'a']], ['unbold', -1, 1, [2, 'a']]]], [[8, 9]])],
    2: [('later unbold wins inside a bold range', [10, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [10, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [10, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [10, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [10, [['bold', 7, 10, [1, 'a']]]], [[7, 10]]), ('range end is exclusive', [10, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [10, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [10, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [10, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [10, [['bold', 9, 12, [1, 'a']], ['unbold', -2, 1, [2, 'a']]]], [[9, 10]])],
    3: [('later unbold wins inside a bold range', [11, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [11, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [11, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [11, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [11, [['bold', 8, 11, [1, 'a']]]], [[8, 11]]), ('range end is exclusive', [11, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [11, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [11, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [11, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [11, [['bold', 10, 14, [1, 'a']], ['unbold', -3, 1, [2, 'a']]]], [[10, 11]])],
    4: [('later unbold wins inside a bold range', [12, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [12, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [12, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [12, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [12, [['bold', 9, 12, [1, 'a']]]], [[9, 12]]), ('range end is exclusive', [12, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [12, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [12, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [12, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [12, [['bold', 11, 16, [1, 'a']], ['unbold', -4, 1, [2, 'a']]]], [[11, 12]])],
    5: [('later unbold wins inside a bold range', [13, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [13, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [13, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [13, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [13, [['bold', 10, 13, [1, 'a']]]], [[10, 13]]), ('range end is exclusive', [13, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [13, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [13, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [13, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [13, [['bold', 12, 18, [1, 'a']], ['unbold', -5, 1, [2, 'a']]]], [[12, 13]])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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(length, ops):
    best = [None] * length
    for kind, start, end, stamp in ops:
        st = tuple(stamp)
        for i in range(max(start, 0), min(end, length)):
            if best[i] is None or st[0] > best[i][0][0]:
                best[i] = (st, kind)
    spans = []
    for i, b in enumerate(best):
        if b is not None and b[1] == 'bold':
            if spans and spans[-1][1] == i:
                spans[-1][1] = i + 1
            else:
                spans.append([i, i + 1])
    return spans
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later unbold wins inside a bold range', [9, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [9, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [9, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [9, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [9, [['bold', 6, 9, [1, 'a']]]], [[6, 9]]), ('range end is exclusive', [9, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [9, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [9, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [9, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [9, [['bold', 8, 10, [1, 'a']], ['unbold', -1, 1, [2, 'a']]]], [[8, 9]])],
    2: [('later unbold wins inside a bold range', [10, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [10, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [10, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [10, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [10, [['bold', 7, 10, [1, 'a']]]], [[7, 10]]), ('range end is exclusive', [10, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [10, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [10, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [10, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [10, [['bold', 9, 12, [1, 'a']], ['unbold', -2, 1, [2, 'a']]]], [[9, 10]])],
    3: [('later unbold wins inside a bold range', [11, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [11, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [11, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [11, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [11, [['bold', 8, 11, [1, 'a']]]], [[8, 11]]), ('range end is exclusive', [11, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [11, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [11, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [11, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [11, [['bold', 10, 14, [1, 'a']], ['unbold', -3, 1, [2, 'a']]]], [[10, 11]])],
    4: [('later unbold wins inside a bold range', [12, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [12, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [12, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [12, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [12, [['bold', 9, 12, [1, 'a']]]], [[9, 12]]), ('range end is exclusive', [12, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [12, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [12, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [12, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [12, [['bold', 11, 16, [1, 'a']], ['unbold', -4, 1, [2, 'a']]]], [[11, 12]])],
    5: [('later unbold wins inside a bold range', [13, [['bold', 0, 6, [1, 'a']], ['unbold', 2, 4, [2, 'b']]]], [[0, 2], [4, 6]]), ('arrival order does not matter', [13, [['unbold', 2, 4, [2, 'b']], ['bold', 0, 6, [1, 'a']]]], [[0, 2], [4, 6]]), ('equal counters break by replica', [13, [['bold', 1, 5, [3, 'b']], ['unbold', 3, 7, [3, 'a']]]], [[1, 5]]), ('equal counters other arrival', [13, [['unbold', 3, 7, [3, 'a']], ['bold', 1, 5, [3, 'b']]]], [[1, 5]]), ('mark reaching the end of text', [13, [['bold', 10, 13, [1, 'a']]]], [[10, 13]]), ('range end is exclusive', [13, [['bold', 2, 3, [1, 'a']], ['bold', 5, 6, [2, 'a']]]], [[2, 3], [5, 6]]), ('adjacent ranges join', [13, [['bold', 0, 2, [1, 'a']], ['bold', 2, 4, [1, 'b']]]], [[0, 4]]), ('one-character gap stays split', [13, [['bold', 0, 2, [1, 'a']], ['bold', 3, 5, [1, 'b']]]], [[0, 2], [3, 5]]), ('range starting before the text is clamped', [13, [['bold', -2, 2, [1, 'a']]]], [[0, 2]]), ('range past the end is clamped', [13, [['bold', 12, 18, [1, 'a']], ['unbold', -5, 1, [2, 'a']]]], [[12, 13]])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), 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:
Replicas that receive the same formatting operations in different orders render different bold spans.

A text of `length` characters receives ["bold"|"unbold", start, end, stamp] operations over half-open ranges clamped to the text. Each character takes the operation with the largest stamp (counter, replica) covering it; it is bold when that operation is "bold". Return maximal bold spans as [start, end) pairs in order.

split: open-access