{"abstract":"A burst of distinct items keeps replacing the newest entry, churning the summary.","category":"Probabilistic sketches","checks":9,"contract":"Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].","evaluation_group":"w2-probabilistic_sketches-space-saving","failed_approach":"Breaking ties alphabetically ignores recency altogether.","family":"w2-probabilistic_sketches-space-saving-tie-break","id":"FA-73126","implementations":{"attempt":{"sha256":"1a0654d1265c785ed5c23008286cca1d9a0748bdb7dcf722748cf79449d70bdf","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    S = {}\n    tick = 0\n    for item in x['stream']:\n        tick += 1\n        if item in S:\n            S[item][0] += 1\n            S[item][2] = tick\n        elif len(S) < k:\n            S[item] = [1, 0, tick]\n        else:\n            victim = min(S, key=lambda key: (S[key][0], key))\n            cnt = S.pop(victim)[0]\n            S[item] = [cnt + 1, cnt, tick]\n    Ntot = len(x['stream'])\n    num, den = x['phi']\n    rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))\n    guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)\n    return [rows, guaranteed]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},\n   [[['a', 9, 3], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},\n   [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},\n   [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},\n   [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},\n   [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},\n   [[['a', 10, 4], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},\n   [[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},\n   [[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},\n   [[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},\n   [[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['d',\n               'b',\n               'a',\n               'a',\n               'a',\n               'e',\n               'c',\n               'a',\n               'f',\n               'c',\n               'a',\n               'e',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'd',\n               'b',\n               'c',\n               'c',\n               'c',\n               'a',\n               'd',\n               'c',\n               'b',\n               'd',\n               'b',\n               'a',\n               'b']},\n   [[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'c',\n               'c',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'c',\n               'd',\n               'a']},\n   [[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},\n   [[['c', 3, 2], ['a', 2, 0]], ['a']]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},\n   [[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['d',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c',\n               'b',\n               'a',\n               'b',\n               'a']},\n   [[['a', 9, 7], ['b', 9, 7]], []]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'f',\n               'f',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'a',\n               'a',\n               'b']},\n   [[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'c',\n               'c',\n               'e',\n               'a',\n               'f',\n               'c',\n               'c',\n               'e',\n               'd',\n               'f',\n               'b',\n               'a',\n               'a',\n               'c',\n               'b',\n               'b']},\n   [[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'd',\n               'e',\n               'a',\n               'd',\n               'a',\n               'g',\n               'a',\n               'c',\n               'g',\n               'c',\n               'b']},\n   [[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},\n   [[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c']},\n   [[['a', 13, 0], ['c', 6, 5]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'f',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'c',\n               'f',\n               'f',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'b',\n               'a',\n               'd',\n               'a',\n               'a']},\n   [[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'd',\n               'f',\n               'a',\n               'd',\n               'a',\n               'a',\n               'g']},\n   [[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},\n   [[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"27444b924f0a752e0b03bc930127163a735150bfe9840e1a02414a012fa449df","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    S = {}\n    tick = 0\n    for item in x['stream']:\n        tick += 1\n        if item in S:\n            S[item][0] += 1\n            S[item][2] = tick\n        elif len(S) < k:\n            S[item] = [1, 0, tick]\n        else:\n            victim = min(S, key=lambda key: (S[key][0], -S[key][2]))\n            cnt = S.pop(victim)[0]\n            S[item] = [cnt + 1, cnt, tick]\n    Ntot = len(x['stream'])\n    num, den = x['phi']\n    rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))\n    guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)\n    return [rows, guaranteed]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},\n   [[['a', 9, 3], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},\n   [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},\n   [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},\n   [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},\n   [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},\n   [[['a', 10, 4], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},\n   [[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},\n   [[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},\n   [[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},\n   [[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['d',\n               'b',\n               'a',\n               'a',\n               'a',\n               'e',\n               'c',\n               'a',\n               'f',\n               'c',\n               'a',\n               'e',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'd',\n               'b',\n               'c',\n               'c',\n               'c',\n               'a',\n               'd',\n               'c',\n               'b',\n               'd',\n               'b',\n               'a',\n               'b']},\n   [[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'c',\n               'c',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'c',\n               'd',\n               'a']},\n   [[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},\n   [[['c', 3, 2], ['a', 2, 0]], ['a']]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},\n   [[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['d',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c',\n               'b',\n               'a',\n               'b',\n               'a']},\n   [[['a', 9, 7], ['b', 9, 7]], []]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'f',\n               'f',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'a',\n               'a',\n               'b']},\n   [[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'c',\n               'c',\n               'e',\n               'a',\n               'f',\n               'c',\n               'c',\n               'e',\n               'd',\n               'f',\n               'b',\n               'a',\n               'a',\n               'c',\n               'b',\n               'b']},\n   [[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'd',\n               'e',\n               'a',\n               'd',\n               'a',\n               'g',\n               'a',\n               'c',\n               'g',\n               'c',\n               'b']},\n   [[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},\n   [[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c']},\n   [[['a', 13, 0], ['c', 6, 5]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'f',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'c',\n               'f',\n               'f',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'b',\n               'a',\n               'd',\n               'a',\n               'a']},\n   [[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'd',\n               'f',\n               'a',\n               'd',\n               'a',\n               'a',\n               'g']},\n   [[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},\n   [[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"ba81dc8785f3eb10330a037ce768b6cd708e1eaf456538b9f35ae983bc2ec660","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    S = {}\n    tick = 0\n    for item in x['stream']:\n        tick += 1\n        if item in S:\n            S[item][0] += 1\n            S[item][2] = tick\n        elif len(S) < k:\n            S[item] = [1, 0, tick]\n        else:\n            victim = min(S, key=lambda key: (S[key][0], S[key][2]))\n            cnt = S.pop(victim)[0]\n            S[item] = [cnt + 1, cnt, tick]\n    Ntot = len(x['stream'])\n    num, den = x['phi']\n    rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))\n    guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)\n    return [rows, guaranteed]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},\n   [[['a', 9, 3], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},\n   [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},\n   [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},\n   [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},\n   [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},\n   [[['a', 10, 4], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},\n   [[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},\n   [[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},\n   [[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},\n   [[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['d',\n               'b',\n               'a',\n               'a',\n               'a',\n               'e',\n               'c',\n               'a',\n               'f',\n               'c',\n               'a',\n               'e',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'd',\n               'b',\n               'c',\n               'c',\n               'c',\n               'a',\n               'd',\n               'c',\n               'b',\n               'd',\n               'b',\n               'a',\n               'b']},\n   [[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'c',\n               'c',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'c',\n               'd',\n               'a']},\n   [[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},\n   [[['c', 3, 2], ['a', 2, 0]], ['a']]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},\n   [[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['d',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c',\n               'b',\n               'a',\n               'b',\n               'a']},\n   [[['a', 9, 7], ['b', 9, 7]], []]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'f',\n               'f',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'a',\n               'a',\n               'b']},\n   [[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'c',\n               'c',\n               'e',\n               'a',\n               'f',\n               'c',\n               'c',\n               'e',\n               'd',\n               'f',\n               'b',\n               'a',\n               'a',\n               'c',\n               'b',\n               'b']},\n   [[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'd',\n               'e',\n               'a',\n               'd',\n               'a',\n               'g',\n               'a',\n               'c',\n               'g',\n               'c',\n               'b']},\n   [[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},\n   [[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c']},\n   [[['a', 13, 0], ['c', 6, 5]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'f',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'c',\n               'f',\n               'f',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'b',\n               'a',\n               'd',\n               'a',\n               'a']},\n   [[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'd',\n               'f',\n               'a',\n               'd',\n               'a',\n               'a',\n               'g']},\n   [[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},\n   [[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-space-saving-tie-break","generated_at":"2026-09-29T14:48:44.637249+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Top-k dashboards and abuse detectors use Space-Saving because its per-item error bound lets them separate guaranteed heavy hitters from possible ones.","repair":"Evict the minimum-count entry with the oldest tick.","root_cause":"Among minimum-count entries the one with the newest tick is evicted.","sha256":"5fc8f499fcfa12a45fa1bf62895f08bd680138ca65e22d344fbb19968af858eb","title":"Space-Saving heavy hitters: ties evict the most recently touched entry · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.662,"exit_code":1,"observations":[{"actual":[[["a",9,4],["b",6,4]],["a"]],"check":"skewed stream 0 k=2","expected":[[["a",9,3],["b",6,4]],["a"]],"passed":false},{"actual":[[["a",8,2],["b",4,2],["d",3,2]],["a"]],"check":"skewed stream 1 k=3","expected":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"passed":false},{"actual":[[["a",8,0],["c",4,3],["e",3,0]],["a"]],"check":"skewed stream 2 k=3","expected":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"passed":false},{"actual":[[["a",7,0],["b",5,0],["g",2,1],["d",1,0]],["a","b"]],"check":"skewed stream 3 k=4","expected":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"passed":false},{"actual":[[["c",3,2],["d",3,2]],[]],"check":"tie eviction by age","expected":[[["c",3,2],["d",3,2]],[]],"passed":true},{"actual":[[["c",4,3],["b",3,0]],[]],"check":"boundary threshold","expected":[[["c",4,3],["b",3,0]],[]],"passed":true},{"actual":[[["w",3,2],["y",3,2]],["w","y"]],"check":"refresh on hit","expected":[[["w",3,2],["y",3,2]],["w","y"]],"passed":true},{"actual":[[["q",3,0],["r",3,2]],["q"]],"check":"equal counts different recency","expected":[[["q",3,2],["r",3,2]],[]],"passed":false},{"actual":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"check":"no eviction","expected":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"skewed stream 0 k=2\", \"actual\": [[[\"a\", 9, 4], [\"b\", 6, 4]], [\"a\"]], \"expected\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 1 k=3\", \"actual\": [[[\"a\", 8, 2], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"expected\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 2 k=3\", \"actual\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"e\", 3, 0]], [\"a\"]], \"expected\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 3 k=4\", \"actual\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"d\", 1, 0]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"passed\": false}, {\"check\": \"tie eviction by age\", \"actual\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"expected\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"passed\": true}, {\"check\": \"boundary threshold\", \"actual\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"expected\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"passed\": true}, {\"check\": \"refresh on hit\", \"actual\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"expected\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"passed\": true}, {\"check\": \"equal counts different recency\", \"actual\": [[[\"q\", 3, 0], [\"r\", 3, 2]], [\"q\"]], \"expected\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"passed\": false}, {\"check\": \"no eviction\", \"actual\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"expected\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.336,"exit_code":1,"observations":[{"actual":[[["a",9,4],["b",6,4]],["a"]],"check":"skewed stream 0 k=2","expected":[[["a",9,3],["b",6,4]],["a"]],"passed":false},{"actual":[[["a",8,2],["b",4,2],["d",3,2]],["a"]],"check":"skewed stream 1 k=3","expected":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"passed":false},{"actual":[[["a",8,0],["c",4,3],["e",3,0]],["a"]],"check":"skewed stream 2 k=3","expected":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"passed":false},{"actual":[[["a",7,0],["b",5,0],["g",2,1],["d",1,0]],["a","b"]],"check":"skewed stream 3 k=4","expected":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"passed":false},{"actual":[[["c",3,2],["d",3,2]],[]],"check":"tie eviction by age","expected":[[["c",3,2],["d",3,2]],[]],"passed":true},{"actual":[[["c",4,3],["a",3,0]],[]],"check":"boundary threshold","expected":[[["c",4,3],["b",3,0]],[]],"passed":false},{"actual":[[["w",3,2],["y",3,2]],["w","y"]],"check":"refresh on hit","expected":[[["w",3,2],["y",3,2]],["w","y"]],"passed":true},{"actual":[[["q",3,0],["r",3,2]],["q"]],"check":"equal counts different recency","expected":[[["q",3,2],["r",3,2]],[]],"passed":false},{"actual":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"check":"no eviction","expected":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"skewed stream 0 k=2\", \"actual\": [[[\"a\", 9, 4], [\"b\", 6, 4]], [\"a\"]], \"expected\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 1 k=3\", \"actual\": [[[\"a\", 8, 2], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"expected\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 2 k=3\", \"actual\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"e\", 3, 0]], [\"a\"]], \"expected\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 3 k=4\", \"actual\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"d\", 1, 0]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"passed\": false}, {\"check\": \"tie eviction by age\", \"actual\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"expected\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"passed\": true}, {\"check\": \"boundary threshold\", \"actual\": [[[\"c\", 4, 3], [\"a\", 3, 0]], []], \"expected\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"passed\": false}, {\"check\": \"refresh on hit\", \"actual\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"expected\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"passed\": true}, {\"check\": \"equal counts different recency\", \"actual\": [[[\"q\", 3, 0], [\"r\", 3, 2]], [\"q\"]], \"expected\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"passed\": false}, {\"check\": \"no eviction\", \"actual\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"expected\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":38.277,"exit_code":0,"observations":[{"actual":[[["a",9,3],["b",6,4]],["a"]],"check":"skewed stream 0 k=2","expected":[[["a",9,3],["b",6,4]],["a"]],"passed":true},{"actual":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"check":"skewed stream 1 k=3","expected":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"passed":true},{"actual":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"check":"skewed stream 2 k=3","expected":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"passed":true},{"actual":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"check":"skewed stream 3 k=4","expected":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"passed":true},{"actual":[[["c",3,2],["d",3,2]],[]],"check":"tie eviction by age","expected":[[["c",3,2],["d",3,2]],[]],"passed":true},{"actual":[[["c",4,3],["b",3,0]],[]],"check":"boundary threshold","expected":[[["c",4,3],["b",3,0]],[]],"passed":true},{"actual":[[["w",3,2],["y",3,2]],["w","y"]],"check":"refresh on hit","expected":[[["w",3,2],["y",3,2]],["w","y"]],"passed":true},{"actual":[[["q",3,2],["r",3,2]],[]],"check":"equal counts different recency","expected":[[["q",3,2],["r",3,2]],[]],"passed":true},{"actual":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"check":"no eviction","expected":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"skewed stream 0 k=2\", \"actual\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"expected\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"passed\": true}, {\"check\": \"skewed stream 1 k=3\", \"actual\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"expected\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"passed\": true}, {\"check\": \"skewed stream 2 k=3\", \"actual\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"expected\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"passed\": true}, {\"check\": \"skewed stream 3 k=4\", \"actual\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"passed\": true}, {\"check\": \"tie eviction by age\", \"actual\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"expected\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"passed\": true}, {\"check\": \"boundary threshold\", \"actual\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"expected\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"passed\": true}, {\"check\": \"refresh on hit\", \"actual\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"expected\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"passed\": true}, {\"check\": \"equal counts different recency\", \"actual\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"expected\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"passed\": true}, {\"check\": \"no eviction\", \"actual\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"expected\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}