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

N = 1
observations = []
def solve(ops, replicas):
    sib = {r: [] for r in replicas}
    def dominates(x, y):
        keys = set(x) | set(y)
        return all(x.get(k, 0) >= y.get(k, 0) for k in keys) and x != y
    for op in ops:
        if op[0] == 'write':
            r, v = op[1], op[2]
            vv = {}
            for _, c in sib[r]:
                for k, cnt in c.items():
                    vv[k] = max(vv.get(k, 0), cnt)
            vv[r] = vv.get(r, 0) + 1
            sib[r] = [[v, vv]]
        else:
            s, d = op[1], op[2]
            pool = sib[d] + [[v, dict(c)] for v, c in sib[s]]
            kept = []
            for v, c in pool:
                if any(dominates(c2, c) for _, c2 in pool):
                    continue
                if False:
                    continue
                kept.append([v, c])
            sib[d] = kept
    return [sorted(v for v, _ in sib[r]) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y1'], ['x', 'y1'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z1'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z1'], ['z1'], ['z1']]), ('merging identical state keeps the value', [[['write', 'a', 'v1'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v1'], ['v1'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new1'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new1'], ['new1'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c1', 'q'], ['q'], ['c1']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    2: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y2'], ['x', 'y2'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z2'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z2'], ['z2'], ['z2']]), ('merging identical state keeps the value', [[['write', 'a', 'v2'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v2'], ['v2'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new2'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new2'], ['new2'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c2', 'q'], ['q'], ['c2']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    3: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y3'], ['x', 'y3'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z3'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z3'], ['z3'], ['z3']]), ('merging identical state keeps the value', [[['write', 'a', 'v3'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v3'], ['v3'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new3'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new3'], ['new3'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['write', 'c', 'c3'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c3', 'q'], ['q'], ['c3']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    4: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y4'], ['x', 'y4'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z4'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z4'], ['z4'], ['z4']]), ('merging identical state keeps the value', [[['write', 'a', 'v4'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v4'], ['v4'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new4'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new4'], ['new4'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['write', 'c', 'c3'], ['write', 'c', 'c4'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c4', 'q'], ['q'], ['c4']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    5: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y5'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y5'], ['x', 'y5'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z5'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z5'], ['z5'], ['z5']]), ('merging identical state keeps the value', [[['write', 'a', 'v5'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v5'], ['v5'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new5'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new5'], ['new5'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['write', 'c', 'c3'], ['write', 'c', 'c4'], ['write', 'c', 'c5'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c5', 'q'], ['q'], ['c5']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
}[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):
    sib = {r: [] for r in replicas}
    def dominates(x, y):
        keys = set(x) | set(y)
        return all(x.get(k, 0) >= y.get(k, 0) for k in keys) and x != y
    for op in ops:
        if op[0] == 'write':
            r, v = op[1], op[2]
            vv = {}
            for _, c in sib[r]:
                for k, cnt in c.items():
                    vv[k] = max(vv.get(k, 0), cnt)
            vv[r] = vv.get(r, 0) + 1
            sib[r] = [[v, vv]]
        else:
            s, d = op[1], op[2]
            pool = sib[d] + [[v, dict(c)] for v, c in sib[s]]
            kept = []
            for v, c in pool:
                if any(dominates(c2, c) for _, c2 in pool):
                    continue
                if any(v == v3 for v3, _ in kept):
                    continue
                kept.append([v, c])
            sib[d] = kept
    return [sorted(v for v, _ in sib[r]) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y1'], ['x', 'y1'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z1'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z1'], ['z1'], ['z1']]), ('merging identical state keeps the value', [[['write', 'a', 'v1'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v1'], ['v1'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new1'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new1'], ['new1'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c1', 'q'], ['q'], ['c1']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    2: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y2'], ['x', 'y2'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z2'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z2'], ['z2'], ['z2']]), ('merging identical state keeps the value', [[['write', 'a', 'v2'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v2'], ['v2'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new2'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new2'], ['new2'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c2', 'q'], ['q'], ['c2']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    3: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y3'], ['x', 'y3'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z3'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z3'], ['z3'], ['z3']]), ('merging identical state keeps the value', [[['write', 'a', 'v3'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v3'], ['v3'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new3'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new3'], ['new3'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['write', 'c', 'c3'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c3', 'q'], ['q'], ['c3']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    4: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y4'], ['x', 'y4'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z4'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z4'], ['z4'], ['z4']]), ('merging identical state keeps the value', [[['write', 'a', 'v4'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v4'], ['v4'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new4'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new4'], ['new4'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['write', 'c', 'c3'], ['write', 'c', 'c4'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c4', 'q'], ['q'], ['c4']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
    5: [('concurrent writes become siblings', [[['write', 'a', 'x'], ['write', 'b', 'y5'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['x', 'y5'], ['x', 'y5'], []]), ('a write after merge supersedes all siblings', [[['write', 'a', 'x'], ['write', 'b', 'y'], ['merge', 'a', 'b'], ['write', 'b', 'z5'], ['merge', 'b', 'a'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['z5'], ['z5'], ['z5']]), ('merging identical state keeps the value', [[['write', 'a', 'v5'], ['merge', 'a', 'b'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['v5'], ['v5'], []]), ('stale incoming sibling is discarded', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'b', 'new'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['old'], ['new'], []]), ('stale local sibling is replaced', [[['write', 'a', 'old'], ['merge', 'a', 'b'], ['write', 'a', 'new5'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['new5'], ['new5'], []]), ('same value written concurrently stays twice', [[['write', 'a', 'same'], ['write', 'b', 'same'], ['merge', 'a', 'c'], ['merge', 'b', 'c']], ['a', 'b', 'c']], [['same'], ['same'], ['same', 'same']]), ('overwrite by the same replica', [[['write', 'c', 'c0'], ['write', 'c', 'c1'], ['write', 'c', 'c2'], ['write', 'c', 'c3'], ['write', 'c', 'c4'], ['write', 'c', 'c5'], ['merge', 'c', 'a'], ['write', 'b', 'q'], ['merge', 'b', 'a']], ['a', 'b', 'c']], [['c5', 'q'], ['q'], ['c5']]), ('three-way concurrency then resolve', [[['write', 'a', 'p'], ['write', 'b', 'q'], ['write', 'c', 'r'], ['merge', 'a', 'c'], ['merge', 'b', 'c'], ['write', 'c', 'resolved'], ['merge', 'c', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['resolved'], ['resolved'], ['resolved']]), ('repeat merge after own rewrite', [[['write', 'a', 'x1'], ['merge', 'a', 'b'], ['write', 'a', 'x2'], ['write', 'b', 'y'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b', 'c']], [['x2', 'y'], ['x2', 'y'], []])],
}[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:
Every re-merge of already known state adds another copy of the same value.

Each replica holds siblings [value, version vector]. ["write", r, v] builds the pointwise maximum of all current sibling vectors, increments r's entry, and replaces all siblings with [v, vector]. ["merge", s, d] pools both sibling lists, drops siblings strictly dominated by another pooled sibling, and keeps one copy per identical vector. Return sorted values per replica.

split: open-access


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

N = 1
observations = []
def solve(a, b):
    def covered(c, rep, n):
        return n <= c['vv'].get(rep, 0) or [rep, n] in c['cloud']
    da = {tuple(x) for x in a['dots']}
    db = {tuple(x) for x in b['dots']}
    dots = (da & db) | {x for x in da if not covered(a, x[1], x[2])} | {x for x in db if not covered(b, x[1], x[2])}
    vv = dict(a['vv'])
    for rep, n in b['vv'].items():
        vv[rep] = max(vv.get(rep, 0), n)
    cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
    changed = True
    while changed:
        changed = False
        for rep, n in sorted(cloud):
            if n == vv.get(rep, 0) + 1:
                vv[rep] = n
                cloud.discard((rep, n))
                changed = True
            elif n <= vv.get(rep, 0):
                cloud.discard((rep, n))
                changed = True
    return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
    2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
    3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
    4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
    5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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(a, b):
    def covered(c, rep, n):
        return n <= c['vv'].get(rep, 0) or [rep, n] in c['cloud']
    da = {tuple(x) for x in a['dots']}
    db = {tuple(x) for x in b['dots']}
    dots = da | db
    vv = dict(a['vv'])
    for rep, n in b['vv'].items():
        vv[rep] = max(vv.get(rep, 0), n)
    cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
    changed = True
    while changed:
        changed = False
        for rep, n in sorted(cloud):
            if n == vv.get(rep, 0) + 1:
                vv[rep] = n
                cloud.discard((rep, n))
                changed = True
            elif n <= vv.get(rep, 0):
                cloud.discard((rep, n))
                changed = True
    return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
    2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
    3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
    4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
    5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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:
New additions known to only one replica disappear on join.

A state is {"dots": [[element, replica, n]], "vv": {replica: n}, "cloud": [[replica, n]]}. A context covers (r, n) when n <= vv[r] or [r, n] is in the cloud. Join keeps dots present in both states plus dots of one state not covered by the other's context; contexts join by vector maximum and cloud union, then the cloud is compacted: an entry equal to vv[r]+1 advances vv[r], entries at or below vv[r] are pruned. Return elements, dots, vector and cloud, all sorted.

split: open-access


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

N = 1
observations = []
def solve(a, b):
    def covered(c, rep, n):
        return n <= c['vv'].get(rep, 0)
    da = {tuple(x) for x in a['dots']}
    db = {tuple(x) for x in b['dots']}
    dots = (da & db) | {x for x in da if not covered(b, x[1], x[2])} | {x for x in db if not covered(a, x[1], x[2])}
    vv = dict(a['vv'])
    for rep, n in b['vv'].items():
        vv[rep] = max(vv.get(rep, 0), n)
    cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
    changed = True
    while changed:
        changed = False
        for rep, n in sorted(cloud):
            if n == vv.get(rep, 0) + 1:
                vv[rep] = n
                cloud.discard((rep, n))
                changed = True
            elif n <= vv.get(rep, 0):
                cloud.discard((rep, n))
                changed = True
    return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
    2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
    3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
    4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
    5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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(a, b):
    def covered(c, rep, n):
        return n <= c['vv'].get(rep, 0) or (rep, n) in c['cloud']
    da = {tuple(x) for x in a['dots']}
    db = {tuple(x) for x in b['dots']}
    dots = (da & db) | {x for x in da if not covered(b, x[1], x[2])} | {x for x in db if not covered(a, x[1], x[2])}
    vv = dict(a['vv'])
    for rep, n in b['vv'].items():
        vv[rep] = max(vv.get(rep, 0), n)
    cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
    changed = True
    while changed:
        changed = False
        for rep, n in sorted(cloud):
            if n == vv.get(rep, 0) + 1:
                vv[rep] = n
                cloud.discard((rep, n))
                changed = True
            elif n <= vv.get(rep, 0):
                cloud.discard((rep, n))
                changed = True
    return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
    2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
    3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
    4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
    5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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 dot removed after out-of-order delivery comes back on join.

A state is {"dots": [[element, replica, n]], "vv": {replica: n}, "cloud": [[replica, n]]}. A context covers (r, n) when n <= vv[r] or [r, n] is in the cloud. Join keeps dots present in both states plus dots of one state not covered by the other's context; contexts join by vector maximum and cloud union, then the cloud is compacted: an entry equal to vv[r]+1 advances vv[r], entries at or below vv[r] are pruned. Return elements, dots, vector and cloud, all sorted.

split: open-access