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

N = 1
observations = []
def solve(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - D[r].get(r, 0)
        incoming = 0
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[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(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - D[r].get(r, 0)
        incoming = sum(T[r].values())
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[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 replica that was given rights still cannot decrement.

Replicas share maps P (increments by replica), D (decrements by replica) and T ("from>to" transferred rights). A replica's rights are its own P minus its own D plus transfers to it minus transfers from it, all read from its local view. ["inc", r, k] grows P[r]; ["dec", r, k] and ["move", r, to, k] are rejected (event index recorded) unless rights >= k. ["sync", s, d] folds s's maps into d by maximum. Return values (sum P - sum D), rights, and rejected indices.

split: open-access


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

N = 1
observations = []
def solve(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - D[r].get(r, 0)
        incoming = sum(v for k, v in T[r].items() if k.split('>')[1] == r)
        outgoing = 0
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[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(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - D[r].get(r, 0)
        incoming = sum(v for k, v in T[r].items() if k.split('>')[1] == r)
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - (outgoing if incoming else 0)
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
After transferring rights a replica can decrement them again, and the global value goes negative.

Replicas share maps P (increments by replica), D (decrements by replica) and T ("from>to" transferred rights). A replica's rights are its own P minus its own D plus transfers to it minus transfers from it, all read from its local view. ["inc", r, k] grows P[r]; ["dec", r, k] and ["move", r, to, k] are rejected (event index recorded) unless rights >= k. ["sync", s, d] folds s's maps into d by maximum. Return values (sum P - sum D), rights, and rejected indices.

split: open-access


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

N = 1
observations = []
def solve(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = sum(P[r].values()) - sum(D[r].values())
        incoming = sum(v for k, v in T[r].items() if k.split('>')[1] == r)
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[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(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - sum(D[r].values())
        incoming = sum(v for k, v in T[r].items() if k.split('>')[1] == r)
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Two replicas both spend the whole observed balance and the merged counter drops below zero.

Replicas share maps P (increments by replica), D (decrements by replica) and T ("from>to" transferred rights). A replica's rights are its own P minus its own D plus transfers to it minus transfers from it, all read from its local view. ["inc", r, k] grows P[r]; ["dec", r, k] and ["move", r, to, k] are rejected (event index recorded) unless rights >= k. ["sync", s, d] folds s's maps into d by maximum. Return values (sum P - sum D), rights, and rejected indices.

split: open-access


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

N = 1
observations = []
def solve(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - D[r].get(r, 0)
        incoming = sum(v for k, v in T[r].items() if k.split('>')[1] == r)
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = to + '>' + r
                T[r][key] = T[r].get(key, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[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(events, replicas):
    P = {r: {} for r in replicas}
    D = {r: {} for r in replicas}
    T = {r: {} for r in replicas}
    rejected = []
    def rights(r):
        own = P[r].get(r, 0) - D[r].get(r, 0)
        incoming = sum(v for k, v in T[r].items() if k.split('>')[1] == r)
        outgoing = sum(v for k, v in T[r].items() if k.split('>')[0] == r)
        return own + incoming - outgoing
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for src, dst in ((P[s], P[d]), (D[s], D[d]), (T[s], T[d])):
                for k, v in src.items():
                    dst[k] = max(dst.get(k, 0), v)
        elif kind == 'inc':
            P[ev[1]][ev[1]] = P[ev[1]].get(ev[1], 0) + ev[2]
        elif kind == 'dec':
            r, k = ev[1], ev[2]
            if rights(r) < k:
                rejected.append(i)
            else:
                D[r][r] = D[r].get(r, 0) + k
        else:
            r, to, k = ev[1], ev[2], ev[3]
            if rights(r) < k:
                rejected.append(i)
            else:
                key = r + '>' + to
                T[r][key] = T[r].get(key, 0) + k
                P[r][to] = P[r].get(to, 0) + k
    return {'values': [sum(P[r].values()) - sum(D[r].values()) for r in replicas], 'rights': [rights(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('each replica spends only its own rights', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 4], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [2, 2, 0], 'rights': [2, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 2], ['move', 'a', 'c', 1], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 1], ['dec', 'c', 1], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [1, 0, 1], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 1], ['dec', 'b', 1], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 3], 'rights': [1, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [2, 5, 2], 'rights': [2, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 1], ['dec', 'c', 4], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    2: [('each replica spends only its own rights', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 3, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 5], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [3, 3, 0], 'rights': [3, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 4], ['move', 'a', 'c', 2], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 2], ['dec', 'c', 2], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [2, 0, 2], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 2], ['dec', 'b', 2], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 2], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 3], 'rights': [2, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [3, 6, 3], 'rights': [3, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 2], ['dec', 'c', 5], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    3: [('each replica spends only its own rights', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 4, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 6], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [4, 4, 0], 'rights': [4, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 6], ['move', 'a', 'c', 3], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 3], ['dec', 'c', 3], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [3, 0, 3], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 3], ['dec', 'b', 3], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 3], 'rights': [3, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [4, 7, 4], 'rights': [4, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 3], ['dec', 'c', 6], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    4: [('each replica spends only its own rights', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 5, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 7], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [5, 5, 0], 'rights': [5, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 8], ['move', 'a', 'c', 4], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 4], ['dec', 'c', 4], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [4, 0, 4], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 4], ['dec', 'b', 4], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 4], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [7, 7, 3], 'rights': [4, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [5, 8, 5], 'rights': [5, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 4], ['dec', 'c', 7], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
    5: [('each replica spends only its own rights', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [0, 6, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('transferred rights can be spent', [[['inc', 'a', 8], ['move', 'a', 'b', 2], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c']], {'values': [6, 6, 0], 'rights': [6, 0, 0], 'rejected': []}), ('outgoing transfers reduce rights', [[['inc', 'a', 3], ['move', 'a', 'b', 2], ['dec', 'a', 2], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rights': [0, 0, 0], 'rejected': [2]}), ('concurrent spending cannot go negative', [[['inc', 'a', 10], ['move', 'a', 'c', 5], ['sync', 'a', 'b'], ['sync', 'a', 'c'], ['dec', 'a', 5], ['dec', 'c', 5], ['dec', 'b', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b']], ['a', 'b', 'c']], {'values': [5, 0, 5], 'rights': [0, 0, 0], 'rejected': [6]}), ('rights exhausted exactly', [[['inc', 'b', 5], ['dec', 'b', 5], ['dec', 'b', 1], ['move', 'b', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rights': [0, 0, 0], 'rejected': [2, 3]}), ('decrements propagate by sync', [[['inc', 'c', 5], ['sync', 'c', 'a'], ['dec', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 5], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [8, 8, 3], 'rights': [5, 0, 3], 'rejected': []}), ('stale peer does not undo local decrements', [[['inc', 'a', 9], ['sync', 'a', 'b'], ['dec', 'a', 3], ['sync', 'b', 'a'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [6, 9, 6], 'rights': [6, 0, 0], 'rejected': []}), ('transfer received before own increments', [[['inc', 'a', 4], ['move', 'a', 'c', 3], ['sync', 'a', 'c'], ['inc', 'c', 5], ['dec', 'c', 8], ['move', 'c', 'b', 1]], ['a', 'b', 'c']], {'values': [4, 0, 1], 'rights': [1, 0, 0], 'rejected': [5]})],
}[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 donor gains rights and the recipient loses them.

Replicas share maps P (increments by replica), D (decrements by replica) and T ("from>to" transferred rights). A replica's rights are its own P minus its own D plus transfers to it minus transfers from it, all read from its local view. ["inc", r, k] grows P[r]; ["dec", r, k] and ["move", r, to, k] are rejected (event index recorded) unless rights >= k. ["sync", s, d] folds s's maps into d by maximum. Return values (sum P - sum D), rights, and rejected indices.

split: open-access