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

N = 1
observations = []
def solve(ops, replicas):
    VA = {r: set() for r in replicas}
    VR = {r: set() for r in replicas}
    EA = {r: set() for r in replicas}
    ER = {r: set() for r in replicas}
    rejected = []
    def vlive(r, v):
        return v in VA[r] and v not in VR[r]
    def evis(r, e):
        return e in EA[r] and e not in ER[r] and vlive(r, e[0]) and vlive(r, e[1])
    for i, op in enumerate(ops):
        kind, r = op[0], op[1]
        if kind == 'addv':
            VA[r].add(op[2])
        elif kind == 'remv':
            v = op[2]
            if not vlive(r, v) or any(evis(r, e) and v in e for e in EA[r]):
                rejected.append(i)
            else:
                VR[r].add(v)
        elif kind == 'adde':
            e = (op[2], op[3])
            if vlive(r, e[0]) and vlive(r, e[1]):
                EA[r].add(e)
            else:
                rejected.append(i)
        elif kind == 'reme':
            e = (op[2], op[3])
            if evis(r, e):
                ER[r].add(e)
            else:
                rejected.append(i)
        else:
            d = op[2]
            VA[d] |= VA[r]
            VR[d] |= VR[r]
            EA[d] |= EA[r]
    out = []
    for r in replicas:
        out.append([sorted(v for v in VA[r] if vlive(r, v)), sorted(list(e) for e in EA[r] if evis(r, e))])
    return {'graphs': out, 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w1'], ['adde', 'a', 'w1', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'p', 'q'], []]], 'rejected': []})],
    2: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w2'], ['adde', 'a', 'w2', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'p', 'q'], []]], 'rejected': []})],
    3: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w3'], ['adde', 'a', 'w3', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'p', 'q'], []]], 'rejected': []})],
    4: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w4'], ['adde', 'a', 'w4', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'p', 'q'], []]], 'rejected': []})],
    5: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w5'], ['adde', 'a', 'w5', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3'], ['addv', 'b', 'n4']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'n4', 'p', 'q'], []]], 'rejected': []})],
}[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(ops, replicas):
    VA = {r: set() for r in replicas}
    VR = {r: set() for r in replicas}
    EA = {r: set() for r in replicas}
    ER = {r: set() for r in replicas}
    rejected = []
    def vlive(r, v):
        return v in VA[r] and v not in VR[r]
    def evis(r, e):
        return e in EA[r] and e not in ER[r] and vlive(r, e[0]) and vlive(r, e[1])
    for i, op in enumerate(ops):
        kind, r = op[0], op[1]
        if kind == 'addv':
            VA[r].add(op[2])
        elif kind == 'remv':
            v = op[2]
            if not vlive(r, v) or any(evis(r, e) and v in e for e in EA[r]):
                rejected.append(i)
            else:
                VR[r].add(v)
        elif kind == 'adde':
            e = (op[2], op[3])
            if vlive(r, e[0]) and vlive(r, e[1]):
                EA[r].add(e)
            else:
                rejected.append(i)
        elif kind == 'reme':
            e = (op[2], op[3])
            if evis(r, e):
                ER[r].add(e)
            else:
                rejected.append(i)
        else:
            d = op[2]
            VA[d] |= VA[r]
            VR[d] |= VR[r]
            EA[d] |= EA[r]
            ER[d] &= ER[r]
    out = []
    for r in replicas:
        out.append([sorted(v for v in VA[r] if vlive(r, v)), sorted(list(e) for e in EA[r] if evis(r, e))])
    return {'graphs': out, 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w1'], ['adde', 'a', 'w1', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'p', 'q'], []]], 'rejected': []})],
    2: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w2'], ['adde', 'a', 'w2', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'p', 'q'], []]], 'rejected': []})],
    3: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w3'], ['adde', 'a', 'w3', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'p', 'q'], []]], 'rejected': []})],
    4: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w4'], ['adde', 'a', 'w4', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'p', 'q'], []]], 'rejected': []})],
    5: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w5'], ['adde', 'a', 'w5', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3'], ['addv', 'b', 'n4']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'n4', 'p', 'q'], []]], 'rejected': []})],
}[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:
An edge removed on one replica remains visible on the others.

Vertices and edges each have grow-only add and remove sets. A vertex is live when added and not removed; an edge is visible when added, not removed, and both endpoints are live. At the origin replica, adding an edge requires both endpoints live, removing a vertex requires no visible edge touching it in either direction, and removing an edge requires it visible; failed preconditions record the op index. ["merge", s, d] unions all four sets into d. Return sorted live vertices and visible edges per replica plus rejections.

split: open-access


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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] < nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0][0] > nid[0]:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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:
Two replicas receiving the same concurrent inserts in different orders show different text.

A sequence of [id, char, deleted] where id = (counter, replica). ["ins", id, after, ch] finds the element with id `after` (head when None or unknown), moves one past it, then skips every following element whose id is greater than the new id before inserting. ["del", id] marks the element deleted but keeps it. Return visible text and the number of slots including tombstones.

split: open-access


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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] > nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    seq.remove(e)
                    break
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after) and not e[2]), -1) + 1
            while pos < len(seq) and seq[pos][0] > nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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:
An insert that references a deleted character lands at the head of the document.

A sequence of [id, char, deleted] where id = (counter, replica). ["ins", id, after, ch] finds the element with id `after` (head when None or unknown), moves one past it, then skips every following element whose id is greater than the new id before inserting. ["del", id] marks the element deleted but keeps it. Return visible text and the number of slots including tombstones.

split: open-access


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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                seq.insert(0, [nid, ch, False])
                continue
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] > nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                seq.insert(0 if not seq or seq[0][0] < nid else 1, [nid, ch, False])
                continue
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] > nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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:
Concurrent inserts at the start of the document appear in arrival order.

A sequence of [id, char, deleted] where id = (counter, replica). ["ins", id, after, ch] finds the element with id `after` (head when None or unknown), moves one past it, then skips every following element whose id is greater than the new id before inserting. ["del", id] marks the element deleted but keeps it. Return visible text and the number of slots including tombstones.

split: open-access