FA-73331 / Probabilistic sketches / Open access
Top-k tracking over a Count-Min sketch: tie among minima evicts the newest entry · case 01
Which minimum-score key survives depends on insertion history instead of the stated tie-break.
ROOT CAUSE
Among equal minimum scores the most recently inserted key is evicted.
VERIFIED REPAIR
Evict the smallest score, breaking ties by the smallest key.
Unsuccessful approach: Breaking ties by the largest key reverses the stated rule.
Case contract
Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.
Why this case matters
Streaming top-k dashboards pair a frequency sketch with a small candidate table; stale scores or loose replacement rules make the reported leaders wrong.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
w = x['w']
k = x['k']
A = [1103515245, 1812433253, 1664525017]
B = [12345, 1013904223, 7]
P = 2147483647
t = [[0] * w for _ in range(3)]
top = {}
for key, c in x['stream']:
for r in range(3):
t[r][(A[r] * key + B[r]) % P % w] += c
est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))
if key in top:
top[key] = est
elif len(top) < k:
top[key] = est
else:
victim = [q for q in top if top[q] == min(top.values())][-1]
if est > top[victim]:
del top[victim]
top[key] = est
return sorted([[q, v] for q, v in top.items()], key=lambda row: (-row[1], row[0]))
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[7, 4],
[1, 3],
[2, 3],
[3, 2],
[5, 2],
[3, 1],
[3, 4],
[5, 3],
[4, 1],
[5, 3],
[4, 3],
[3, 1],
[4, 4],
[6, 4],
[6, 4]],
'w': 8},
[[3, 8], [5, 8]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 2],
[1, 3],
[5, 4],
[6, 2],
[6, 4],
[5, 3],
[2, 1],
[4, 2],
[3, 2],
[5, 3],
[2, 3],
[2, 1],
[1, 2],
[5, 2],
[7, 4]],
'w': 6},
[[5, 12], [6, 6], [7, 6]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[6, 1],
[3, 1],
[3, 2],
[5, 1],
[1, 2],
[6, 1],
[4, 2],
[3, 4],
[6, 3],
[4, 1],
[3, 4],
[1, 3],
[6, 1],
[7, 1]],
'w': 10},
[[3, 15], [6, 6], [1, 5]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[3, 4],
[5, 4],
[6, 2],
[6, 3],
[3, 1],
[3, 3],
[4, 1],
[5, 1],
[7, 1],
[6, 2],
[6, 1],
[6, 1],
[7, 1],
[3, 3],
[3, 2]],
'w': 5},
[[3, 13], [6, 10]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 2]], 'w': 16},
[[1, 9], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 2]], 'w': 1}, [[1, 7], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 6]], 'w': 16},
[[7, 6], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 3]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[2, 1],
[7, 1],
[6, 3],
[6, 1],
[2, 4],
[2, 2],
[2, 4],
[5, 4],
[4, 4],
[4, 2],
[5, 2],
[2, 4],
[2, 4],
[5, 1],
[6, 3]],
'w': 8},
[[2, 19], [4, 9]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 4],
[1, 3],
[6, 1],
[5, 3],
[2, 3],
[5, 4],
[5, 3],
[3, 4],
[5, 1],
[2, 4],
[7, 1],
[6, 4],
[2, 2],
[3, 4],
[5, 3],
[5, 3]],
'w': 6},
[[5, 17], [2, 9], [3, 8]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 3],
[5, 3],
[4, 1],
[3, 4],
[6, 1],
[3, 1],
[6, 3],
[7, 3],
[5, 3],
[2, 1],
[3, 2],
[7, 3],
[2, 1],
[3, 2],
[3, 1],
[2, 4]],
'w': 10},
[[3, 13], [5, 6], [7, 6]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[7, 2],
[4, 4],
[2, 4],
[4, 4],
[2, 4],
[5, 2],
[2, 3],
[4, 4],
[1, 1],
[4, 3],
[6, 1],
[2, 3],
[1, 1],
[2, 3],
[6, 2],
[2, 4]],
'w': 5},
[[2, 21], [4, 16]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 3]], 'w': 16},
[[1, 10], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 2]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 3]], 'w': 1}, [[1, 8], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 7]], 'w': 16},
[[7, 7], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 4]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[1, 1],
[3, 4],
[4, 3],
[3, 2],
[1, 4],
[1, 3],
[7, 4],
[4, 3],
[5, 3],
[5, 4],
[2, 2],
[1, 3],
[7, 4],
[3, 2],
[5, 2],
[5, 1]],
'w': 8},
[[1, 11], [5, 10]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[5, 2],
[2, 4],
[5, 2],
[6, 3],
[7, 2],
[4, 3],
[2, 4],
[7, 1],
[4, 4],
[7, 1],
[4, 4],
[4, 3],
[5, 4],
[5, 4],
[6, 4],
[3, 3],
[6, 4]],
'w': 6},
[[4, 14], [5, 12], [6, 11]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[3, 3],
[2, 1],
[6, 4],
[1, 2],
[6, 3],
[3, 3],
[5, 1],
[6, 4],
[2, 2],
[7, 1],
[5, 4],
[3, 3],
[2, 1],
[2, 4],
[4, 2],
[4, 1]],
'w': 10},
[[3, 13], [6, 11], [2, 8]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[5, 1],
[5, 4],
[5, 3],
[5, 3],
[5, 1],
[3, 4],
[4, 3],
[7, 1],
[7, 4],
[2, 2],
[4, 1],
[4, 4],
[5, 1],
[6, 2],
[5, 2],
[1, 1],
[6, 3]],
'w': 5},
[[5, 17], [6, 9]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]], 'w': 16},
[[1, 11], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 3]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 4]], 'w': 1}, [[1, 9], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 8]], 'w': 16},
[[7, 8], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 5]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[1, 4],
[6, 3],
[4, 1],
[7, 3],
[5, 3],
[3, 2],
[2, 4],
[2, 4],
[3, 3],
[1, 1],
[1, 1],
[4, 4],
[2, 1],
[5, 4],
[1, 4],
[4, 1],
[1, 2],
[2, 3]],
'w': 8},
[[1, 12], [2, 12]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[3, 3],
[2, 3],
[4, 2],
[5, 2],
[2, 1],
[7, 4],
[6, 1],
[6, 2],
[4, 4],
[2, 3],
[4, 2],
[7, 4],
[5, 2],
[4, 3],
[6, 4],
[2, 3],
[6, 3],
[6, 4]],
'w': 6},
[[6, 14], [4, 11], [2, 10]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[6, 3],
[3, 2],
[2, 1],
[2, 2],
[2, 3],
[3, 4],
[7, 2],
[2, 2],
[5, 3],
[7, 3],
[7, 2],
[6, 4],
[6, 1],
[7, 3],
[6, 2],
[6, 1],
[5, 1]],
'w': 10},
[[6, 11], [3, 10], [7, 10]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[1, 4],
[3, 3],
[5, 3],
[3, 2],
[6, 4],
[1, 1],
[2, 4],
[2, 4],
[7, 4],
[7, 4],
[3, 1],
[7, 2],
[2, 4],
[5, 1],
[6, 2],
[1, 2],
[3, 2],
[4, 3]],
'w': 5},
[[2, 15], [3, 14]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 5]], 'w': 16},
[[1, 12], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 4]], 'w': 16},
[[12, 4], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5]], 'w': 1}, [[1, 10], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 9]], 'w': 16},
[[7, 9], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 6]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[2, 4],
[7, 1],
[1, 2],
[6, 3],
[3, 4],
[7, 3],
[5, 2],
[7, 3],
[4, 3],
[4, 4],
[7, 3],
[2, 4],
[2, 3],
[5, 2],
[3, 1],
[1, 2],
[1, 4],
[7, 3]],
'w': 8},
[[7, 13], [2, 11]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 3],
[3, 2],
[2, 4],
[3, 4],
[4, 3],
[4, 1],
[7, 1],
[5, 2],
[1, 1],
[4, 2],
[2, 4],
[6, 1],
[7, 4],
[1, 4],
[2, 3],
[5, 3],
[6, 4],
[3, 2],
[3, 3]],
'w': 6},
[[2, 11], [3, 11], [7, 8]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[4, 1],
[6, 3],
[6, 4],
[7, 3],
[2, 1],
[7, 3],
[7, 3],
[1, 3],
[3, 1],
[7, 4],
[5, 2],
[4, 1],
[7, 4],
[1, 1],
[5, 2],
[2, 4],
[7, 2],
[2, 4],
[7, 4]],
'w': 10},
[[7, 23], [2, 9], [6, 7]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[6, 4],
[6, 2],
[1, 3],
[4, 3],
[4, 2],
[3, 2],
[3, 4],
[5, 3],
[4, 2],
[3, 1],
[1, 2],
[2, 1],
[7, 4],
[4, 3],
[2, 2],
[7, 1],
[5, 4],
[1, 2],
[7, 1]],
'w': 5},
[[4, 13], [5, 10]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 6]], 'w': 16},
[[1, 13], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 5]], 'w': 16},
[[12, 5], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 6]], 'w': 1}, [[1, 11], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 10]], 'w': 16},
[[7, 10], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 7]], 'w': 16},
[[8, 7], [2, 6]]]]]
for label, args, expected in cases[N - 1]:
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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| stream 0 w=8 k=2 | [[3, 8], [5, 8]] | [[3, 8], [5, 8]] | Passed |
| stream 1 w=6 k=3 | [[5, 12], [6, 6], [7, 6]] | [[5, 12], [6, 6], [7, 6]] | Passed |
| stream 2 w=10 k=3 | [[3, 15], [6, 6], [1, 5]] | [[3, 15], [6, 6], [1, 5]] | Passed |
| stream 3 w=5 k=2 | [[3, 13], [6, 10]] | [[3, 13], [6, 10]] | Passed |
| hit refreshes estimate | [[1, 9], [3, 4]] | [[1, 9], [3, 4]] | Passed |
| tie with minimum | [[4, 3], [9, 3]] | [[4, 3], [9, 3]] | Passed |
| equal newcomer keeps incumbent | [[4, 3], [9, 3]] | [[4, 3], [9, 3]] | Passed |
| colliding refresh | [[1, 7], [2, 5]] | [[1, 7], [2, 5]] | Passed |
| tie among minima eviction | [[7, 6], [4, 3]] | [[7, 6], [9, 3]] | Failed |
| newcomer below minimum | [[1, 6], [2, 6]] | [[1, 6], [2, 6]] | Passed |
SHA-256 / 13659c72014fb531bbe9aee1e0d5c2efb7399f3017c933f2c3fb36bacc31dcee
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
w = x['w']
k = x['k']
A = [1103515245, 1812433253, 1664525017]
B = [12345, 1013904223, 7]
P = 2147483647
t = [[0] * w for _ in range(3)]
top = {}
for key, c in x['stream']:
for r in range(3):
t[r][(A[r] * key + B[r]) % P % w] += c
est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))
if key in top:
top[key] = est
elif len(top) < k:
top[key] = est
else:
victim = min(top, key=lambda q: (top[q], -q))
if est > top[victim]:
del top[victim]
top[key] = est
return sorted([[q, v] for q, v in top.items()], key=lambda row: (-row[1], row[0]))
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[7, 4],
[1, 3],
[2, 3],
[3, 2],
[5, 2],
[3, 1],
[3, 4],
[5, 3],
[4, 1],
[5, 3],
[4, 3],
[3, 1],
[4, 4],
[6, 4],
[6, 4]],
'w': 8},
[[3, 8], [5, 8]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 2],
[1, 3],
[5, 4],
[6, 2],
[6, 4],
[5, 3],
[2, 1],
[4, 2],
[3, 2],
[5, 3],
[2, 3],
[2, 1],
[1, 2],
[5, 2],
[7, 4]],
'w': 6},
[[5, 12], [6, 6], [7, 6]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[6, 1],
[3, 1],
[3, 2],
[5, 1],
[1, 2],
[6, 1],
[4, 2],
[3, 4],
[6, 3],
[4, 1],
[3, 4],
[1, 3],
[6, 1],
[7, 1]],
'w': 10},
[[3, 15], [6, 6], [1, 5]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[3, 4],
[5, 4],
[6, 2],
[6, 3],
[3, 1],
[3, 3],
[4, 1],
[5, 1],
[7, 1],
[6, 2],
[6, 1],
[6, 1],
[7, 1],
[3, 3],
[3, 2]],
'w': 5},
[[3, 13], [6, 10]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 2]], 'w': 16},
[[1, 9], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 2]], 'w': 1}, [[1, 7], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 6]], 'w': 16},
[[7, 6], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 3]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[2, 1],
[7, 1],
[6, 3],
[6, 1],
[2, 4],
[2, 2],
[2, 4],
[5, 4],
[4, 4],
[4, 2],
[5, 2],
[2, 4],
[2, 4],
[5, 1],
[6, 3]],
'w': 8},
[[2, 19], [4, 9]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 4],
[1, 3],
[6, 1],
[5, 3],
[2, 3],
[5, 4],
[5, 3],
[3, 4],
[5, 1],
[2, 4],
[7, 1],
[6, 4],
[2, 2],
[3, 4],
[5, 3],
[5, 3]],
'w': 6},
[[5, 17], [2, 9], [3, 8]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 3],
[5, 3],
[4, 1],
[3, 4],
[6, 1],
[3, 1],
[6, 3],
[7, 3],
[5, 3],
[2, 1],
[3, 2],
[7, 3],
[2, 1],
[3, 2],
[3, 1],
[2, 4]],
'w': 10},
[[3, 13], [5, 6], [7, 6]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[7, 2],
[4, 4],
[2, 4],
[4, 4],
[2, 4],
[5, 2],
[2, 3],
[4, 4],
[1, 1],
[4, 3],
[6, 1],
[2, 3],
[1, 1],
[2, 3],
[6, 2],
[2, 4]],
'w': 5},
[[2, 21], [4, 16]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 3]], 'w': 16},
[[1, 10], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 2]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 3]], 'w': 1}, [[1, 8], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 7]], 'w': 16},
[[7, 7], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 4]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[1, 1],
[3, 4],
[4, 3],
[3, 2],
[1, 4],
[1, 3],
[7, 4],
[4, 3],
[5, 3],
[5, 4],
[2, 2],
[1, 3],
[7, 4],
[3, 2],
[5, 2],
[5, 1]],
'w': 8},
[[1, 11], [5, 10]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[5, 2],
[2, 4],
[5, 2],
[6, 3],
[7, 2],
[4, 3],
[2, 4],
[7, 1],
[4, 4],
[7, 1],
[4, 4],
[4, 3],
[5, 4],
[5, 4],
[6, 4],
[3, 3],
[6, 4]],
'w': 6},
[[4, 14], [5, 12], [6, 11]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[3, 3],
[2, 1],
[6, 4],
[1, 2],
[6, 3],
[3, 3],
[5, 1],
[6, 4],
[2, 2],
[7, 1],
[5, 4],
[3, 3],
[2, 1],
[2, 4],
[4, 2],
[4, 1]],
'w': 10},
[[3, 13], [6, 11], [2, 8]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[5, 1],
[5, 4],
[5, 3],
[5, 3],
[5, 1],
[3, 4],
[4, 3],
[7, 1],
[7, 4],
[2, 2],
[4, 1],
[4, 4],
[5, 1],
[6, 2],
[5, 2],
[1, 1],
[6, 3]],
'w': 5},
[[5, 17], [6, 9]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]], 'w': 16},
[[1, 11], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 3]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 4]], 'w': 1}, [[1, 9], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 8]], 'w': 16},
[[7, 8], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 5]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[1, 4],
[6, 3],
[4, 1],
[7, 3],
[5, 3],
[3, 2],
[2, 4],
[2, 4],
[3, 3],
[1, 1],
[1, 1],
[4, 4],
[2, 1],
[5, 4],
[1, 4],
[4, 1],
[1, 2],
[2, 3]],
'w': 8},
[[1, 12], [2, 12]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[3, 3],
[2, 3],
[4, 2],
[5, 2],
[2, 1],
[7, 4],
[6, 1],
[6, 2],
[4, 4],
[2, 3],
[4, 2],
[7, 4],
[5, 2],
[4, 3],
[6, 4],
[2, 3],
[6, 3],
[6, 4]],
'w': 6},
[[6, 14], [4, 11], [2, 10]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[6, 3],
[3, 2],
[2, 1],
[2, 2],
[2, 3],
[3, 4],
[7, 2],
[2, 2],
[5, 3],
[7, 3],
[7, 2],
[6, 4],
[6, 1],
[7, 3],
[6, 2],
[6, 1],
[5, 1]],
'w': 10},
[[6, 11], [3, 10], [7, 10]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[1, 4],
[3, 3],
[5, 3],
[3, 2],
[6, 4],
[1, 1],
[2, 4],
[2, 4],
[7, 4],
[7, 4],
[3, 1],
[7, 2],
[2, 4],
[5, 1],
[6, 2],
[1, 2],
[3, 2],
[4, 3]],
'w': 5},
[[2, 15], [3, 14]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 5]], 'w': 16},
[[1, 12], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 4]], 'w': 16},
[[12, 4], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5]], 'w': 1}, [[1, 10], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 9]], 'w': 16},
[[7, 9], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 6]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[2, 4],
[7, 1],
[1, 2],
[6, 3],
[3, 4],
[7, 3],
[5, 2],
[7, 3],
[4, 3],
[4, 4],
[7, 3],
[2, 4],
[2, 3],
[5, 2],
[3, 1],
[1, 2],
[1, 4],
[7, 3]],
'w': 8},
[[7, 13], [2, 11]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 3],
[3, 2],
[2, 4],
[3, 4],
[4, 3],
[4, 1],
[7, 1],
[5, 2],
[1, 1],
[4, 2],
[2, 4],
[6, 1],
[7, 4],
[1, 4],
[2, 3],
[5, 3],
[6, 4],
[3, 2],
[3, 3]],
'w': 6},
[[2, 11], [3, 11], [7, 8]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[4, 1],
[6, 3],
[6, 4],
[7, 3],
[2, 1],
[7, 3],
[7, 3],
[1, 3],
[3, 1],
[7, 4],
[5, 2],
[4, 1],
[7, 4],
[1, 1],
[5, 2],
[2, 4],
[7, 2],
[2, 4],
[7, 4]],
'w': 10},
[[7, 23], [2, 9], [6, 7]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[6, 4],
[6, 2],
[1, 3],
[4, 3],
[4, 2],
[3, 2],
[3, 4],
[5, 3],
[4, 2],
[3, 1],
[1, 2],
[2, 1],
[7, 4],
[4, 3],
[2, 2],
[7, 1],
[5, 4],
[1, 2],
[7, 1]],
'w': 5},
[[4, 13], [5, 10]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 6]], 'w': 16},
[[1, 13], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 5]], 'w': 16},
[[12, 5], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 6]], 'w': 1}, [[1, 11], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 10]], 'w': 16},
[[7, 10], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 7]], 'w': 16},
[[8, 7], [2, 6]]]]]
for label, args, expected in cases[N - 1]:
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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| stream 0 w=8 k=2 | [[3, 8], [5, 8]] | [[3, 8], [5, 8]] | Passed |
| stream 1 w=6 k=3 | [[5, 12], [6, 6], [7, 6]] | [[5, 12], [6, 6], [7, 6]] | Passed |
| stream 2 w=10 k=3 | [[3, 15], [6, 6], [1, 5]] | [[3, 15], [6, 6], [1, 5]] | Passed |
| stream 3 w=5 k=2 | [[3, 13], [6, 10]] | [[3, 13], [6, 10]] | Passed |
| hit refreshes estimate | [[1, 9], [3, 4]] | [[1, 9], [3, 4]] | Passed |
| tie with minimum | [[4, 3], [9, 3]] | [[4, 3], [9, 3]] | Passed |
| equal newcomer keeps incumbent | [[4, 3], [9, 3]] | [[4, 3], [9, 3]] | Passed |
| colliding refresh | [[1, 7], [2, 5]] | [[1, 7], [2, 5]] | Passed |
| tie among minima eviction | [[7, 6], [4, 3]] | [[7, 6], [9, 3]] | Failed |
| newcomer below minimum | [[1, 6], [2, 6]] | [[1, 6], [2, 6]] | Passed |
SHA-256 / e5bd79c30e00027e17138ddab565b21f51a11a67878de45351b2c7e3ac61e1b9
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
w = x['w']
k = x['k']
A = [1103515245, 1812433253, 1664525017]
B = [12345, 1013904223, 7]
P = 2147483647
t = [[0] * w for _ in range(3)]
top = {}
for key, c in x['stream']:
for r in range(3):
t[r][(A[r] * key + B[r]) % P % w] += c
est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))
if key in top:
top[key] = est
elif len(top) < k:
top[key] = est
else:
victim = min(top, key=lambda q: (top[q], q))
if est > top[victim]:
del top[victim]
top[key] = est
return sorted([[q, v] for q, v in top.items()], key=lambda row: (-row[1], row[0]))
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[7, 4],
[1, 3],
[2, 3],
[3, 2],
[5, 2],
[3, 1],
[3, 4],
[5, 3],
[4, 1],
[5, 3],
[4, 3],
[3, 1],
[4, 4],
[6, 4],
[6, 4]],
'w': 8},
[[3, 8], [5, 8]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 2],
[1, 3],
[5, 4],
[6, 2],
[6, 4],
[5, 3],
[2, 1],
[4, 2],
[3, 2],
[5, 3],
[2, 3],
[2, 1],
[1, 2],
[5, 2],
[7, 4]],
'w': 6},
[[5, 12], [6, 6], [7, 6]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[6, 1],
[3, 1],
[3, 2],
[5, 1],
[1, 2],
[6, 1],
[4, 2],
[3, 4],
[6, 3],
[4, 1],
[3, 4],
[1, 3],
[6, 1],
[7, 1]],
'w': 10},
[[3, 15], [6, 6], [1, 5]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[3, 4],
[5, 4],
[6, 2],
[6, 3],
[3, 1],
[3, 3],
[4, 1],
[5, 1],
[7, 1],
[6, 2],
[6, 1],
[6, 1],
[7, 1],
[3, 3],
[3, 2]],
'w': 5},
[[3, 13], [6, 10]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 2]], 'w': 16},
[[1, 9], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 2]], 'w': 1}, [[1, 7], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 6]], 'w': 16},
[[7, 6], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 3]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[2, 1],
[7, 1],
[6, 3],
[6, 1],
[2, 4],
[2, 2],
[2, 4],
[5, 4],
[4, 4],
[4, 2],
[5, 2],
[2, 4],
[2, 4],
[5, 1],
[6, 3]],
'w': 8},
[[2, 19], [4, 9]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 4],
[1, 3],
[6, 1],
[5, 3],
[2, 3],
[5, 4],
[5, 3],
[3, 4],
[5, 1],
[2, 4],
[7, 1],
[6, 4],
[2, 2],
[3, 4],
[5, 3],
[5, 3]],
'w': 6},
[[5, 17], [2, 9], [3, 8]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 3],
[5, 3],
[4, 1],
[3, 4],
[6, 1],
[3, 1],
[6, 3],
[7, 3],
[5, 3],
[2, 1],
[3, 2],
[7, 3],
[2, 1],
[3, 2],
[3, 1],
[2, 4]],
'w': 10},
[[3, 13], [5, 6], [7, 6]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[7, 2],
[4, 4],
[2, 4],
[4, 4],
[2, 4],
[5, 2],
[2, 3],
[4, 4],
[1, 1],
[4, 3],
[6, 1],
[2, 3],
[1, 1],
[2, 3],
[6, 2],
[2, 4]],
'w': 5},
[[2, 21], [4, 16]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 3]], 'w': 16},
[[1, 10], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 2]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 3]], 'w': 1}, [[1, 8], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 7]], 'w': 16},
[[7, 7], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 4]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[1, 1],
[3, 4],
[4, 3],
[3, 2],
[1, 4],
[1, 3],
[7, 4],
[4, 3],
[5, 3],
[5, 4],
[2, 2],
[1, 3],
[7, 4],
[3, 2],
[5, 2],
[5, 1]],
'w': 8},
[[1, 11], [5, 10]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[5, 2],
[2, 4],
[5, 2],
[6, 3],
[7, 2],
[4, 3],
[2, 4],
[7, 1],
[4, 4],
[7, 1],
[4, 4],
[4, 3],
[5, 4],
[5, 4],
[6, 4],
[3, 3],
[6, 4]],
'w': 6},
[[4, 14], [5, 12], [6, 11]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[3, 3],
[2, 1],
[6, 4],
[1, 2],
[6, 3],
[3, 3],
[5, 1],
[6, 4],
[2, 2],
[7, 1],
[5, 4],
[3, 3],
[2, 1],
[2, 4],
[4, 2],
[4, 1]],
'w': 10},
[[3, 13], [6, 11], [2, 8]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[5, 1],
[5, 4],
[5, 3],
[5, 3],
[5, 1],
[3, 4],
[4, 3],
[7, 1],
[7, 4],
[2, 2],
[4, 1],
[4, 4],
[5, 1],
[6, 2],
[5, 2],
[1, 1],
[6, 3]],
'w': 5},
[[5, 17], [6, 9]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]], 'w': 16},
[[1, 11], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 3]], 'w': 16},
[[4, 3], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 4]], 'w': 1}, [[1, 9], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 8]], 'w': 16},
[[7, 8], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 5]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[1, 4],
[6, 3],
[4, 1],
[7, 3],
[5, 3],
[3, 2],
[2, 4],
[2, 4],
[3, 3],
[1, 1],
[1, 1],
[4, 4],
[2, 1],
[5, 4],
[1, 4],
[4, 1],
[1, 2],
[2, 3]],
'w': 8},
[[1, 12], [2, 12]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[3, 3],
[2, 3],
[4, 2],
[5, 2],
[2, 1],
[7, 4],
[6, 1],
[6, 2],
[4, 4],
[2, 3],
[4, 2],
[7, 4],
[5, 2],
[4, 3],
[6, 4],
[2, 3],
[6, 3],
[6, 4]],
'w': 6},
[[6, 14], [4, 11], [2, 10]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[3, 4],
[6, 3],
[3, 2],
[2, 1],
[2, 2],
[2, 3],
[3, 4],
[7, 2],
[2, 2],
[5, 3],
[7, 3],
[7, 2],
[6, 4],
[6, 1],
[7, 3],
[6, 2],
[6, 1],
[5, 1]],
'w': 10},
[[6, 11], [3, 10], [7, 10]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[1, 4],
[3, 3],
[5, 3],
[3, 2],
[6, 4],
[1, 1],
[2, 4],
[2, 4],
[7, 4],
[7, 4],
[3, 1],
[7, 2],
[2, 4],
[5, 1],
[6, 2],
[1, 2],
[3, 2],
[4, 3]],
'w': 5},
[[2, 15], [3, 14]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 5]], 'w': 16},
[[1, 12], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 4]], 'w': 16},
[[12, 4], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5]], 'w': 1}, [[1, 10], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 9]], 'w': 16},
[[7, 9], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 6]], 'w': 16},
[[1, 6], [2, 6]]]],
[['stream 0 w=8 k=2',
{'k': 2,
'stream': [[4, 3],
[2, 4],
[7, 1],
[1, 2],
[6, 3],
[3, 4],
[7, 3],
[5, 2],
[7, 3],
[4, 3],
[4, 4],
[7, 3],
[2, 4],
[2, 3],
[5, 2],
[3, 1],
[1, 2],
[1, 4],
[7, 3]],
'w': 8},
[[7, 13], [2, 11]]],
['stream 1 w=6 k=3',
{'k': 3,
'stream': [[7, 3],
[3, 2],
[2, 4],
[3, 4],
[4, 3],
[4, 1],
[7, 1],
[5, 2],
[1, 1],
[4, 2],
[2, 4],
[6, 1],
[7, 4],
[1, 4],
[2, 3],
[5, 3],
[6, 4],
[3, 2],
[3, 3]],
'w': 6},
[[2, 11], [3, 11], [7, 8]]],
['stream 2 w=10 k=3',
{'k': 3,
'stream': [[4, 1],
[6, 3],
[6, 4],
[7, 3],
[2, 1],
[7, 3],
[7, 3],
[1, 3],
[3, 1],
[7, 4],
[5, 2],
[4, 1],
[7, 4],
[1, 1],
[5, 2],
[2, 4],
[7, 2],
[2, 4],
[7, 4]],
'w': 10},
[[7, 23], [2, 9], [6, 7]]],
['stream 3 w=5 k=2',
{'k': 2,
'stream': [[6, 4],
[6, 2],
[1, 3],
[4, 3],
[4, 2],
[3, 2],
[3, 4],
[5, 3],
[4, 2],
[3, 1],
[1, 2],
[2, 1],
[7, 4],
[4, 3],
[2, 2],
[7, 1],
[5, 4],
[1, 2],
[7, 1]],
'w': 5},
[[4, 13], [5, 10]]],
['hit refreshes estimate',
{'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 6]], 'w': 16},
[[1, 13], [3, 4]]],
['tie with minimum',
{'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 5]], 'w': 16},
[[12, 5], [9, 3]]],
['equal newcomer keeps incumbent',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},
[[4, 3], [9, 3]]],
['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 6]], 'w': 1}, [[1, 11], [2, 5]]],
['tie among minima eviction',
{'k': 2, 'stream': [[4, 3], [9, 3], [7, 10]], 'w': 16},
[[7, 10], [9, 3]]],
['newcomer below minimum',
{'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 7]], 'w': 16},
[[8, 7], [2, 6]]]]]
for label, args, expected in cases[N - 1]:
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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| stream 0 w=8 k=2 | [[3, 8], [5, 8]] | [[3, 8], [5, 8]] | Passed |
| stream 1 w=6 k=3 | [[5, 12], [6, 6], [7, 6]] | [[5, 12], [6, 6], [7, 6]] | Passed |
| stream 2 w=10 k=3 | [[3, 15], [6, 6], [1, 5]] | [[3, 15], [6, 6], [1, 5]] | Passed |
| stream 3 w=5 k=2 | [[3, 13], [6, 10]] | [[3, 13], [6, 10]] | Passed |
| hit refreshes estimate | [[1, 9], [3, 4]] | [[1, 9], [3, 4]] | Passed |
| tie with minimum | [[4, 3], [9, 3]] | [[4, 3], [9, 3]] | Passed |
| equal newcomer keeps incumbent | [[4, 3], [9, 3]] | [[4, 3], [9, 3]] | Passed |
| colliding refresh | [[1, 7], [2, 5]] | [[1, 7], [2, 5]] | Passed |
| tie among minima eviction | [[7, 6], [9, 3]] | [[7, 6], [9, 3]] | Passed |
| newcomer below minimum | [[1, 6], [2, 6]] | [[1, 6], [2, 6]] | Passed |
SHA-256 / 34a73195594a7665da7339509ce989854344cc08c60290b7354c7bf37860177a
Verification & scope
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.
Observations recorded using Python 3.12.14 at 2026-09-29T14:48:46.568028+00:00.
Case digest / 8481ff3f3ab772aebf6ab929a398a2c5436047f0db93e269f8d06451cdb8da98