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

N = 1
observations = []
def solve(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local[b[0]] = b[1][b[0]]
                    delivered.append(b[2])
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local[b[0]] = b[1][b[0]]
                    delivered.append(b[2])
                    progress = True
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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:
Buffered messages that became deliverable stay pending until another message arrives.

A receiver starts with an empty delivered vector. An arrival [sender, vector, payload] is a duplicate when its sender entry is at or below the delivered entry or the same (sender, entry) is already buffered. Otherwise it is buffered; then, repeatedly, the oldest buffered message whose sender entry is exactly delivered+1 and whose other entries are all <= delivered is delivered, setting only the sender entry. Return delivered payloads, sorted pending payloads, duplicate count and the delivered vector.

split: open-access


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

N = 1
observations = []
def solve(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) < local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local[b[0]] = b[1][b[0]]
                    delivered.append(b[2])
                    progress = True
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local[b[0]] = b[1][b[0]]
                    delivered.append(b[2])
                    progress = True
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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 retransmitted copy of the latest message sits in the buffer forever and is not counted as a duplicate.

A receiver starts with an empty delivered vector. An arrival [sender, vector, payload] is a duplicate when its sender entry is at or below the delivered entry or the same (sender, entry) is already buffered. Otherwise it is buffered; then, repeatedly, the oldest buffered message whose sender entry is exactly delivered+1 and whose other entries are all <= delivered is delivered, setting only the sender entry. Return delivered payloads, sorted pending payloads, duplicate count and the delivered vector.

split: open-access


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

N = 1
observations = []
def solve(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local = dict(b[1])
                    delivered.append(b[2])
                    progress = True
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local.update(b[1])
                    delivered.append(b[2])
                    progress = True
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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:
The delivered vector moves backwards and old messages are accepted again.

A receiver starts with an empty delivered vector. An arrival [sender, vector, payload] is a duplicate when its sender entry is at or below the delivered entry or the same (sender, entry) is already buffered. Otherwise it is buffered; then, repeatedly, the oldest buffered message whose sender entry is exactly delivered+1 and whose other entries are all <= delivered is delivered, setting only the sender entry. Return delivered payloads, sorted pending payloads, duplicate count and the delivered vector.

split: open-access