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

N = 1
observations = []
def solve(viewer, readers, settings, chat_kind, admins):
    enabled = lambda u: settings.get(u, True)
    out = []
    for u in readers:
        if u == viewer and chat_kind == 'direct':
            continue
        if chat_kind == 'channel':
            ok = viewer in admins
        elif chat_kind == 'direct':
            ok = enabled(u) and enabled(viewer)
        else:
            ok = enabled(u)
        if ok:
            out.append(u)
    return sorted(out)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('missing settings default on', ('v', ['r1'], {}, 'direct', []), ['r1']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r1'], {}, 'group', []), ['r1']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 2: [('missing settings default on', ('v', ['r2'], {}, 'direct', []), ['r2']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r2'], {}, 'group', []), ['r2']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 3: [('missing settings default on', ('v', ['r3'], {}, 'direct', []), ['r3']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r3'], {}, 'group', []), ['r3']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 4: [('missing settings default on', ('v', ['r4'], {}, 'direct', []), ['r4']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r4'], {}, 'group', []), ['r4']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 5: [('missing settings default on', ('v', ['r5'], {}, 'direct', []), ['r5']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r5'], {}, 'group', []), ['r5']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])]}
for _label, _args, _expected in _CASES[N]:
    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(viewer, readers, settings, chat_kind, admins):
    enabled = lambda u: settings.get(u, True)
    out = []
    for u in readers:
        if u == viewer and chat_kind != 'channel':
            continue
        if chat_kind == 'channel':
            ok = viewer in admins
        elif chat_kind == 'direct':
            ok = enabled(u) and enabled(viewer)
        else:
            ok = enabled(u)
        if ok:
            out.append(u)
    return sorted(out)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('missing settings default on', ('v', ['r1'], {}, 'direct', []), ['r1']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r1'], {}, 'group', []), ['r1']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 2: [('missing settings default on', ('v', ['r2'], {}, 'direct', []), ['r2']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r2'], {}, 'group', []), ['r2']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 3: [('missing settings default on', ('v', ['r3'], {}, 'direct', []), ['r3']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r3'], {}, 'group', []), ['r3']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 4: [('missing settings default on', ('v', ['r4'], {}, 'direct', []), ['r4']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r4'], {}, 'group', []), ['r4']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])], 5: [('missing settings default on', ('v', ['r5'], {}, 'direct', []), ['r5']), ('viewer disabled in direct chat', ('v', ['r'], {'v': False}, 'direct', []), []), ('viewer disabled in group', ('v', ['r', 'q'], {'v': False, 'q': False}, 'group', []), ['r']), ('reader disabled in direct chat', ('v', ['r'], {'r': False, 'v': True}, 'direct', []), []), ('channel admin', ('v', ['r', 'q', 'p'], {'r': False}, 'channel', ['v']), ['p', 'q', 'r']), ('channel non-admin', ('v', ['r'], {}, 'channel', ['a']), []), ('own receipt in group', ('v', ['v', 'r5'], {}, 'group', []), ['r5']), ('own receipt in channel as admin', ('v', ['v'], {}, 'channel', ['v']), [])]}
for _label, _args, _expected in _CASES[N]:
    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 viewer appears in their own "seen by" list in group or channel conversations.

settings[u] is a user's "send read receipts" flag (default True). In direct chats a reader is shown only when both the reader and the viewer have receipts enabled (reciprocity). In group chats only the reader's flag matters. In channels only admins see receipts and they see every reader regardless of settings. The viewer never sees their own receipt. Result: sorted visible readers.

split: open-access


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

N = 1
observations = []
def solve(messages, me, marker, window_start):
    eff = marker
    for seq, author in messages:
        if author == me and seq == eff + 1:
            eff = seq
    index = None
    for i, (seq, author) in enumerate(messages):
        if seq > eff and author != me:
            index = i
            break
    return {'index': index, 'older_unread': eff < window_start - 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('interleaved own replies', ([[11, 'bo'], [12, 'me'], [13, 'bo'], [14, 'me'], [15, 'cy']], 'me', 10, 11), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [22, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 7, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 2: [('interleaved own replies', ([[12, 'bo'], [13, 'me'], [14, 'bo'], [15, 'me'], [16, 'cy']], 'me', 11, 12), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [23, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 8, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 3: [('interleaved own replies', ([[13, 'bo'], [14, 'me'], [15, 'bo'], [16, 'me'], [17, 'cy']], 'me', 12, 13), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [24, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 9, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 4: [('interleaved own replies', ([[14, 'bo'], [15, 'me'], [16, 'bo'], [17, 'me'], [18, 'cy']], 'me', 13, 14), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [25, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 10, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 5: [('interleaved own replies', ([[15, 'bo'], [16, 'me'], [17, 'bo'], [18, 'me'], [19, 'cy']], 'me', 14, 15), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [26, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 11, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})]}
for _label, _args, _expected in _CASES[N]:
    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(messages, me, marker, window_start):
    eff = marker
    for seq, author in messages:
        if author == me and seq > eff and eff == marker:
            eff = seq
    index = None
    for i, (seq, author) in enumerate(messages):
        if seq > eff and author != me:
            index = i
            break
    return {'index': index, 'older_unread': eff < window_start - 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('interleaved own replies', ([[11, 'bo'], [12, 'me'], [13, 'bo'], [14, 'me'], [15, 'cy']], 'me', 10, 11), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [22, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 7, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 2: [('interleaved own replies', ([[12, 'bo'], [13, 'me'], [14, 'bo'], [15, 'me'], [16, 'cy']], 'me', 11, 12), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [23, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 8, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 3: [('interleaved own replies', ([[13, 'bo'], [14, 'me'], [15, 'bo'], [16, 'me'], [17, 'cy']], 'me', 12, 13), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [24, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 9, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 4: [('interleaved own replies', ([[14, 'bo'], [15, 'me'], [16, 'bo'], [17, 'me'], [18, 'cy']], 'me', 13, 14), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [25, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 10, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 5: [('interleaved own replies', ([[15, 'bo'], [16, 'me'], [17, 'bo'], [18, 'me'], [19, 'cy']], 'me', 14, 15), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [26, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 11, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})]}
for _label, _args, _expected in _CASES[N]:
    check(_label, solve(*_args), _expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
After the user replies in the middle of new messages, the divider still sits above messages they answered.

messages are ascending [seq, author] pairs of the loaded window that starts at window_start. Sending a message implies having read everything before it, so the effective marker is the larger of marker and the highest seq authored by me. The divider goes before the first loaded message after the effective marker not written by me (index, or None). older_unread is true when some unread seq lies before the loaded window (effective marker < window_start - 1).

split: open-access


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

N = 1
observations = []
def solve(messages, me, marker, window_start):
    eff = marker
    for seq, author in messages:
        if author == me and seq > eff:
            eff = seq
    index = None
    for i, (seq, author) in enumerate(messages):
        if seq > eff and author != me:
            index = i
            break
    return {'index': index, 'older_unread': eff < window_start}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('interleaved own replies', ([[11, 'bo'], [12, 'me'], [13, 'bo'], [14, 'me'], [15, 'cy']], 'me', 10, 11), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [22, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 7, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 2: [('interleaved own replies', ([[12, 'bo'], [13, 'me'], [14, 'bo'], [15, 'me'], [16, 'cy']], 'me', 11, 12), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [23, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 8, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 3: [('interleaved own replies', ([[13, 'bo'], [14, 'me'], [15, 'bo'], [16, 'me'], [17, 'cy']], 'me', 12, 13), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [24, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 9, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 4: [('interleaved own replies', ([[14, 'bo'], [15, 'me'], [16, 'bo'], [17, 'me'], [18, 'cy']], 'me', 13, 14), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [25, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 10, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 5: [('interleaved own replies', ([[15, 'bo'], [16, 'me'], [17, 'bo'], [18, 'me'], [19, 'cy']], 'me', 14, 15), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [26, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 11, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})]}
for _label, _args, _expected in _CASES[N]:
    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(messages, me, marker, window_start):
    eff = marker
    for seq, author in messages:
        if author == me and seq > eff:
            eff = seq
    index = None
    for i, (seq, author) in enumerate(messages):
        if seq > eff and author != me:
            index = i
            break
    return {'index': index, 'older_unread': eff + 1 < window_start - 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('interleaved own replies', ([[11, 'bo'], [12, 'me'], [13, 'bo'], [14, 'me'], [15, 'cy']], 'me', 10, 11), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [22, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 7, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 2: [('interleaved own replies', ([[12, 'bo'], [13, 'me'], [14, 'bo'], [15, 'me'], [16, 'cy']], 'me', 11, 12), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [23, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 8, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 3: [('interleaved own replies', ([[13, 'bo'], [14, 'me'], [15, 'bo'], [16, 'me'], [17, 'cy']], 'me', 12, 13), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [24, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 9, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 4: [('interleaved own replies', ([[14, 'bo'], [15, 'me'], [16, 'bo'], [17, 'me'], [18, 'cy']], 'me', 13, 14), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [25, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 10, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 5: [('interleaved own replies', ([[15, 'bo'], [16, 'me'], [17, 'bo'], [18, 'me'], [19, 'cy']], 'me', 14, 15), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [26, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 11, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})]}
for _label, _args, _expected in _CASES[N]:
    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 "older unread messages" banner appears when the window begins right after the marker, or misses a single unloaded unread.

messages are ascending [seq, author] pairs of the loaded window that starts at window_start. Sending a message implies having read everything before it, so the effective marker is the larger of marker and the highest seq authored by me. The divider goes before the first loaded message after the effective marker not written by me (index, or None). older_unread is true when some unread seq lies before the loaded window (effective marker < window_start - 1).

split: open-access


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

N = 1
observations = []
def solve(messages, me, marker, window_start):
    eff = marker
    for seq, author in messages:
        if author == me and seq > eff:
            eff = seq
    index = len(messages)
    for i, (seq, author) in enumerate(messages):
        if seq > eff and author != me:
            index = i
            break
    return {'index': index, 'older_unread': eff < window_start - 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('interleaved own replies', ([[11, 'bo'], [12, 'me'], [13, 'bo'], [14, 'me'], [15, 'cy']], 'me', 10, 11), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [22, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 7, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 2: [('interleaved own replies', ([[12, 'bo'], [13, 'me'], [14, 'bo'], [15, 'me'], [16, 'cy']], 'me', 11, 12), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [23, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 8, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 3: [('interleaved own replies', ([[13, 'bo'], [14, 'me'], [15, 'bo'], [16, 'me'], [17, 'cy']], 'me', 12, 13), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [24, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 9, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 4: [('interleaved own replies', ([[14, 'bo'], [15, 'me'], [16, 'bo'], [17, 'me'], [18, 'cy']], 'me', 13, 14), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [25, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 10, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 5: [('interleaved own replies', ([[15, 'bo'], [16, 'me'], [17, 'bo'], [18, 'me'], [19, 'cy']], 'me', 14, 15), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [26, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 11, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})]}
for _label, _args, _expected in _CASES[N]:
    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(messages, me, marker, window_start):
    eff = marker
    for seq, author in messages:
        if author == me and seq > eff:
            eff = seq
    index = -1
    for i, (seq, author) in enumerate(messages):
        if seq > eff and author != me:
            index = i
            break
    return {'index': index, 'older_unread': eff < window_start - 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('interleaved own replies', ([[11, 'bo'], [12, 'me'], [13, 'bo'], [14, 'me'], [15, 'cy']], 'me', 10, 11), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [22, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 7, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 2: [('interleaved own replies', ([[12, 'bo'], [13, 'me'], [14, 'bo'], [15, 'me'], [16, 'cy']], 'me', 11, 12), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [23, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 8, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 3: [('interleaved own replies', ([[13, 'bo'], [14, 'me'], [15, 'bo'], [16, 'me'], [17, 'cy']], 'me', 12, 13), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [24, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 9, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 4: [('interleaved own replies', ([[14, 'bo'], [15, 'me'], [16, 'bo'], [17, 'me'], [18, 'cy']], 'me', 13, 14), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [25, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 10, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})], 5: [('interleaved own replies', ([[15, 'bo'], [16, 'me'], [17, 'bo'], [18, 'me'], [19, 'cy']], 'me', 14, 15), {'index': 4, 'older_unread': False}), ('window starts right after marker', ([[20, 'bo'], [21, 'bo']], 'me', 19, 20), {'index': 0, 'older_unread': False}), ('one unloaded unread', ([[20, 'bo'], [26, 'bo']], 'me', 18, 20), {'index': 0, 'older_unread': True}), ('all read', ([[5, 'bo'], [6, 'cy']], 'me', 11, 5), {'index': None, 'older_unread': False}), ('only own messages after marker', ([[1, 'bo'], [2, 'me']], 'me', 1, 1), {'index': None, 'older_unread': False}), ('first unread foreign', ([[3, 'bo'], [4, 'cy'], [5, 'dd']], 'me', 3, 3), {'index': 1, 'older_unread': False})]}
for _label, _args, _expected in _CASES[N]:
    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:
When nothing is unread the divider is drawn at the end of the list instead of being omitted.

messages are ascending [seq, author] pairs of the loaded window that starts at window_start. Sending a message implies having read everything before it, so the effective marker is the larger of marker and the highest seq authored by me. The divider goes before the first loaded message after the effective marker not written by me (index, or None). older_unread is true when some unread seq lies before the loaded window (effective marker < window_start - 1).

split: open-access


prompt:
A viewer several hours east of UTC sees evening messages under the wrong day.

stamps are ascending unix seconds; offset_min is the viewer's UTC offset in minutes. A separator [index, label] precedes the first message of each local calendar day: "Today" for the local day containing now, "Yesterday" for the one before, otherwise the ISO local date.

split: open-access


prompt:
Shortly after local midnight the current day is labelled "Yesterday" because "today" is computed in UTC.

stamps are ascending unix seconds; offset_min is the viewer's UTC offset in minutes. A separator [index, label] precedes the first message of each local calendar day: "Today" for the local day containing now, "Yesterday" for the one before, otherwise the ISO local date.

split: open-access


prompt:
Viewers west of UTC see evening messages under the following day.

stamps are ascending unix seconds; offset_min is the viewer's UTC offset in minutes. A separator [index, label] precedes the first message of each local calendar day: "Today" for the local day containing now, "Yesterday" for the one before, otherwise the ISO local date.

split: open-access


prompt:
A message stamped slightly in the future by a skewed clock is labelled "Yesterday".

stamps are ascending unix seconds; offset_min is the viewer's UTC offset in minutes. A separator [index, label] precedes the first message of each local calendar day: "Today" for the local day containing now, "Yesterday" for the one before, otherwise the ISO local date.

split: open-access


prompt:
A separator is inserted before every message instead of once per day.

stamps are ascending unix seconds; offset_min is the viewer's UTC offset in minutes. A separator [index, label] precedes the first message of each local calendar day: "Today" for the local day containing now, "Yesterday" for the one before, otherwise the ISO local date.

split: open-access


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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = min(got) if got else horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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(have, horizon, head, max_ranges):
    got = set(have)
    lo = max(horizon, min(got)) if got else horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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:
Messages between the retention horizon and the first received message are never backfilled.

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

split: open-access


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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo - 1, hi):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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 newest message is never requested when it is the one that is missing.

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

split: open-access


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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1 if s > start + 1 else s])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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:
Backfill ranges include the first message that was already received.

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

split: open-access


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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi - 1])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, start])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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 gap that runs up to the head is requested short, so the newest missing messages stay missing.

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

split: open-access


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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.sort()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.sort(key=lambda r: r[1] - r[0], reverse=True)
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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:
Old gaps are backfilled before the recent history the user is looking at.

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

split: open-access


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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges[:max_ranges]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': len(ranges) <= max_ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    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 request budget of zero or a truncated plan reports the timeline as complete.

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

split: open-access


prompt:
Messages sharing the cursor timestamp are skipped when loading older history.

messages are [ts, id] pairs in any order; ordering is by (ts, id). cursor is None or the exclusive [ts, id] of the oldest message already shown. A page holds the newest `limit` messages strictly older than the cursor, in ascending order; next is the [ts, id] of the page's oldest item when older messages remain, else None.

split: open-access


prompt:
Messages with equal timestamps are paged in arrival order, so the cursor comparison and the page disagree.

messages are [ts, id] pairs in any order; ordering is by (ts, id). cursor is None or the exclusive [ts, id] of the oldest message already shown. A page holds the newest `limit` messages strictly older than the cursor, in ascending order; next is the [ts, id] of the page's oldest item when older messages remain, else None.

split: open-access


prompt:
Scrolling up loads the very oldest messages instead of those just above the view.

messages are [ts, id] pairs in any order; ordering is by (ts, id). cursor is None or the exclusive [ts, id] of the oldest message already shown. A page holds the newest `limit` messages strictly older than the cursor, in ascending order; next is the [ts, id] of the page's oldest item when older messages remain, else None.

split: open-access


prompt:
An extra empty page is requested whenever history length is an exact multiple of the page size.

messages are [ts, id] pairs in any order; ordering is by (ts, id). cursor is None or the exclusive [ts, id] of the oldest message already shown. A page holds the newest `limit` messages strictly older than the cursor, in ascending order; next is the [ts, id] of the page's oldest item when older messages remain, else None.

split: open-access


prompt:
The next cursor points at the newest message of the page, so the following page repeats most of it.

messages are [ts, id] pairs in any order; ordering is by (ts, id). cursor is None or the exclusive [ts, id] of the oldest message already shown. A page holds the newest `limit` messages strictly older than the cursor, in ascending order; next is the [ts, id] of the page's oldest item when older messages remain, else None.

split: open-access