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

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk >= cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1) if c in table else -1
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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 client removed by timeout reappears when an old update is redelivered.

Presence updates ["update", client, clock, state|None, now] are accepted when clock exceeds the last accepted clock for that client, or when it equals it, the state is None and the client is present. Accepted updates record the clock; a None state removes the client (logging a removal only if it was present); otherwise [state, now] is stored. ["tick", now] removes, in client order, every client other than self_id whose last update is at least timeout old. Return present [client, state] pairs and the removal log.

split: open-access


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

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur:
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk >= cur:
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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 client that announces it is leaving stays visible until it times out.

Presence updates ["update", client, clock, state|None, now] are accepted when clock exceeds the last accepted clock for that client, or when it equals it, the state is None and the client is present. Accepted updates record the clock; a None state removes the client (logging a removal only if it was present); otherwise [state, now] is stored. ["tick", now] removes, in client order, every client other than self_id whose last update is at least timeout old. Return present [client, state] pairs and the removal log.

split: open-access


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

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] > timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - clocks[c] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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 peer silent for exactly the timeout remains visible one tick too long.

Presence updates ["update", client, clock, state|None, now] are accepted when clock exceeds the last accepted clock for that client, or when it equals it, the state is None and the client is present. Accepted updates record the clock; a None state removes the client (logging a removal only if it was present); otherwise [state, now] is stored. ["tick", now] removes, in client order, every client other than self_id whose last update is at least timeout old. Return present [client, state] pairs and the removal log.

split: open-access


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

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != 'me' and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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 local user disappears from presence after a quiet period.

Presence updates ["update", client, clock, state|None, now] are accepted when clock exceeds the last accepted clock for that client, or when it equals it, the state is None and the client is present. Accepted updates record the clock; a None state removes the client (logging a removal only if it was present); otherwise [state, now] is stored. ["tick", now] removes, in client order, every client other than self_id whose last update is at least timeout old. Return present [client, state] pairs and the removal log.

split: open-access


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

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    table.pop(c, None)
                    removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    table.pop(c, None)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[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:
Removal events are emitted for clients that were never present.

Presence updates ["update", client, clock, state|None, now] are accepted when clock exceeds the last accepted clock for that client, or when it equals it, the state is None and the client is present. Accepted updates record the clock; a None state removes the client (logging a removal only if it was present); otherwise [state, now] is stored. ["tick", now] removes, in client order, every client other than self_id whose last update is at least timeout old. Return present [client, state] pairs and the removal log.

split: open-access


prompt:
Zero-length updates are sent for structs the peer already has.

The local store holds structs [client, clock, length] covering clocks clock..clock+length-1. The remote state vector maps client ids (decimal strings, as decoded from JSON) to the next clock it expects; absent clients expect 0. Send, sorted by client then clock, every struct part the remote lacks, slicing a partly known struct to start at the expected clock. Also return the local state vector.

split: open-access


prompt:
Peers receive clocks they already integrated.

The local store holds structs [client, clock, length] covering clocks clock..clock+length-1. The remote state vector maps client ids (decimal strings, as decoded from JSON) to the next clock it expects; absent clients expect 0. Send, sorted by client then clock, every struct part the remote lacks, slicing a partly known struct to start at the expected clock. Also return the local state vector.

split: open-access


prompt:
A peer that has never heard from a client never receives its structs.

The local store holds structs [client, clock, length] covering clocks clock..clock+length-1. The remote state vector maps client ids (decimal strings, as decoded from JSON) to the next clock it expects; absent clients expect 0. Send, sorted by client then clock, every struct part the remote lacks, slicing a partly known struct to start at the expected clock. Also return the local state vector.

split: open-access


prompt:
The advertised state vector is one behind, so peers resend the last clock of every client.

The local store holds structs [client, clock, length] covering clocks clock..clock+length-1. The remote state vector maps client ids (decimal strings, as decoded from JSON) to the next clock it expects; absent clients expect 0. Send, sorted by client then clock, every struct part the remote lacks, slicing a partly known struct to start at the expected clock. Also return the local state vector.

split: open-access


prompt:
Every sync resends the whole store.

The local store holds structs [client, clock, length] covering clocks clock..clock+length-1. The remote state vector maps client ids (decimal strings, as decoded from JSON) to the next clock it expects; absent clients expect 0. Send, sorted by client then clock, every struct part the remote lacks, slicing a partly known struct to start at the expected clock. Also return the local state vector.

split: open-access