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

N = 1
observations = []
def solve(elements, edits):
    seq = [list(e) for e in elements]
    out = []
    k = 0
    for ed in edits:
        vis = [i for i, e in enumerate(seq) if not e[2]]
        idx = ed[1]
        if ed[0] == 'insert':
            if idx < 0 or idx > len(vis):
                out.append(['reject', idx])
                continue
            if idx == 0:
                after, pos = None, 0
            else:
                p = vis[idx - 1]
                after, pos = seq[p][0], p + 1
            nid = 'L%d' % k
            seq.insert(pos, [nid, ed[2], False])
            out.append(['ins', nid, after])
        else:
            if idx < 0 or idx >= len(vis):
                out.append(['reject', idx])
                continue
            p = vis[idx]
            seq[p][2] = True
            out.append(['del', seq[p][0]])
    return {'ops': out, 'text': ''.join(e[1] for e in seq if not e[2])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 4, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 4], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2']], 'text': 'hi!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    2: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 5, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 5], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3']], 'text': 'hi!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    3: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 6, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 6], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4']], 'text': 'hi!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    4: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 7, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 7], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5']], 'text': 'hi!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    5: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 8, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 8], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!'], ['insert', 6, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5'], ['ins', 'L7', 'L6']], 'text': 'hi!!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
}[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(elements, edits):
    seq = [list(e) for e in elements]
    out = []
    k = 0
    for ed in edits:
        vis = [i for i, e in enumerate(seq) if not e[2]]
        idx = ed[1]
        if ed[0] == 'insert':
            if idx < 0 or idx > len(vis):
                out.append(['reject', idx])
                continue
            if idx == 0:
                after, pos = None, 0
            else:
                p = vis[idx - 1]
                after, pos = seq[p][0], p + 1
            nid = 'L%d' % (k + 1)
            seq.insert(pos, [nid, ed[2], False])
            out.append(['ins', nid, after])
        else:
            if idx < 0 or idx >= len(vis):
                out.append(['reject', idx])
                continue
            p = vis[idx]
            seq[p][2] = True
            out.append(['del', seq[p][0]])
    return {'ops': out, 'text': ''.join(e[1] for e in seq if not e[2])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 4, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 4], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2']], 'text': 'hi!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    2: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 5, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 5], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3']], 'text': 'hi!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    3: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 6, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 6], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4']], 'text': 'hi!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    4: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 7, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 7], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5']], 'text': 'hi!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    5: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 8, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 8], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!'], ['insert', 6, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5'], ['ins', 'L7', 'L6']], 'text': 'hi!!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
}[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:
Several inserts in one batch receive the same element id.

A sequence CRDT holds [id, char, deleted]. Local edits use visible indices: ["insert", i, ch] (0 <= i <= visible length) references the visible element at i-1 (None at 0), is placed immediately after it, and gets id "L<k>" from a counter advanced only by accepted inserts; ["delete", i] (0 <= i < visible length) tombstones the visible element at i. Out-of-range edits yield ["reject", i]. Return the emitted ops and visible text.

split: open-access


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

N = 1
observations = []
def solve(elements, edits):
    seq = [list(e) for e in elements]
    out = []
    k = 0
    for ed in edits:
        vis = [i for i, e in enumerate(seq) if not e[2]]
        idx = ed[1]
        if ed[0] == 'insert':
            if idx < 0 or idx > len(vis):
                out.append(['reject', idx])
                continue
            if idx == 0:
                after, pos = None, 0
            else:
                p = vis[idx - 1]
                after, pos = seq[p][0], p + 1
            k += 1
            nid = 'L%d' % k
            seq.insert(pos, [nid, ed[2], False])
            out.append(['ins', nid, after])
        else:
            if idx >= len(vis):
                out.append(['reject', idx])
                continue
            p = vis[idx]
            seq[p][2] = True
            out.append(['del', seq[p][0]])
    return {'ops': out, 'text': ''.join(e[1] for e in seq if not e[2])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 4, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 4], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2']], 'text': 'hi!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    2: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 5, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 5], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3']], 'text': 'hi!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    3: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 6, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 6], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4']], 'text': 'hi!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    4: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 7, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 7], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5']], 'text': 'hi!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    5: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 8, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 8], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!'], ['insert', 6, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5'], ['ins', 'L7', 'L6']], 'text': 'hi!!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
}[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(elements, edits):
    seq = [list(e) for e in elements]
    out = []
    k = 0
    for ed in edits:
        vis = [i for i, e in enumerate(seq) if not e[2]]
        idx = ed[1]
        if ed[0] == 'insert':
            if idx < 0 or idx > len(vis):
                out.append(['reject', idx])
                continue
            if idx == 0:
                after, pos = None, 0
            else:
                p = vis[idx - 1]
                after, pos = seq[p][0], p + 1
            k += 1
            nid = 'L%d' % k
            seq.insert(pos, [nid, ed[2], False])
            out.append(['ins', nid, after])
        else:
            if idx < -len(vis) or idx >= len(vis):
                out.append(['reject', idx])
                continue
            p = vis[idx]
            seq[p][2] = True
            out.append(['del', seq[p][0]])
    return {'ops': out, 'text': ''.join(e[1] for e in seq if not e[2])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 4, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 4], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2']], 'text': 'hi!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    2: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 5, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 5], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3']], 'text': 'hi!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    3: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 6, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 6], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4']], 'text': 'hi!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    4: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 7, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 7], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5']], 'text': 'hi!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
    5: [('insert after tombstones uses the visible neighbour', [[['e0', 'a', False], ['e1', 'b', True], ['e2', 'c', True], ['e3', 'd', False], ['e4', 'e', False]], [['insert', 2, 'X']]], {'ops': [['ins', 'L1', 'e3']], 'text': 'adXe'}), ('insert at the visible end', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', True]], [['insert', 2, 'Z'], ['insert', 3, 'W']]], {'ops': [['ins', 'L1', 'e1'], ['ins', 'L2', 'L1']], 'text': 'abZW'}), ('insert at the start', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False]], [['insert', 0, 'S']]], {'ops': [['ins', 'L1', None]], 'text': 'Sbc'}), ('delete by visible index', [[['e0', 'a', True], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True], ['e4', 'e', False], ['e5', 'f', False]], [['delete', 0], ['delete', 2]]], {'ops': [['del', 'e1'], ['del', 'e5']], 'text': 'ce'}), ('delete last visible character', [[['e0', 'a', False], ['e1', 'b', False], ['e2', 'c', False], ['e3', 'd', True]], [['delete', 2]]], {'ops': [['del', 'e2']], 'text': 'ab'}), ('out-of-range edits are rejected', [[['e0', 'a', False], ['e1', 'b', False]], [['insert', 8, 'q'], ['delete', 2], ['delete', -1], ['insert', -1, 'r'], ['insert', 1, 'k']]], {'ops': [['reject', 8], ['reject', 2], ['reject', -1], ['reject', -1], ['ins', 'L1', 'e0']], 'text': 'akb'}), ('ids stay dense after a rejection', [[['e0', 'x', False], ['e1', 'y', False]], [['insert', 5, 'p'], ['insert', 1, 'm'], ['insert', 0, 'n']]], {'ops': [['reject', 5], ['ins', 'L1', 'e0'], ['ins', 'L2', None]], 'text': 'nxmy'}), ('typing into an empty document', [[], [['insert', 0, 'h'], ['insert', 1, 'i'], ['insert', 2, '!'], ['insert', 3, '!'], ['insert', 4, '!'], ['insert', 5, '!'], ['insert', 6, '!']]], {'ops': [['ins', 'L1', None], ['ins', 'L2', 'L1'], ['ins', 'L3', 'L2'], ['ins', 'L4', 'L3'], ['ins', 'L5', 'L4'], ['ins', 'L6', 'L5'], ['ins', 'L7', 'L6']], 'text': 'hi!!!!!'}), ('mixed edits', [[['e0', 'h', False], ['e1', 'e', True], ['e2', 'l', False], ['e3', 'l', False], ['e4', 'o', False]], [['delete', 1], ['insert', 1, 'E'], ['insert', 4, '?']]], {'ops': [['del', 'e2'], ['ins', 'L1', 'e0'], ['ins', 'L2', 'e4']], 'text': 'hElo?'})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A delete at index minus one silently removes the last visible character.

A sequence CRDT holds [id, char, deleted]. Local edits use visible indices: ["insert", i, ch] (0 <= i <= visible length) references the visible element at i-1 (None at 0), is placed immediately after it, and gets id "L<k>" from a counter advanced only by accepted inserts; ["delete", i] (0 <= i < visible length) tombstones the visible element at i. Out-of-range edits yield ["reject", i]. Return the emitted ops and visible text.

split: open-access


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

N = 1
observations = []
def solve(ops, replicas):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            M[r].pop(key, None)
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[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):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, 1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                if entry[2] == 0:
                    offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A stale put arriving by merge brings a deleted key back.

Each key holds [value, ts, kind, writer] with kind 1 for a delete tombstone and 0 for a put. An incoming entry (local op or merge) replaces the stored one only if (ts, kind, writer) is lexicographically larger, so deletes win timestamp ties and writers break the rest. Tombstones are kept. ["merge", s, d] offers each of s's entries to d. Return sorted visible [key, value] pairs per replica.

split: open-access


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

N = 1
observations = []
def solve(ops, replicas):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if True:
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, 1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[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):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or cur[2] == 1 or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, 1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[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:
Delivery order, not timestamps, decides the final value of a key.

Each key holds [value, ts, kind, writer] with kind 1 for a delete tombstone and 0 for a put. An incoming entry (local op or merge) replaces the stored one only if (ts, kind, writer) is lexicographically larger, so deletes win timestamp ties and writers break the rest. Tombstones are kept. ["merge", s, d] offers each of s's entries to d. Return sorted visible [key, value] pairs per replica.

split: open-access