FA-73326 / Probabilistic sketches / Open access
Top-k tracking over a Count-Min sketch: equal estimate replaces the minimum · case 01
Keys with equal estimates churn the table, and the reported leader set depends on arrival order.
ROOT CAUSE
Replacement fires on ties with the minimum score.
VERIFIED REPAIR
Replace only when the newcomer estimate is strictly larger.
Unsuccessful approach: Comparing against the oldest tracked entry instead of the minimum rejects legitimate replacements.
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 = 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 | [[5, 8], [6, 8]] | [[3, 8], [5, 8]] | Failed |
| 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 | [[7, 3], [9, 3]] | [[4, 3], [9, 3]] | Failed |
| equal newcomer keeps incumbent | [[7, 3], [9, 3]] | [[4, 3], [9, 3]] | Failed |
| 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 / 9d75ee3ba76b6688ae10f549e39c06fe66d2bcaaa88ab071566e16ec55f24a5b
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[next(iter(top))]:
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], [2, 5]] | [[5, 12], [6, 6], [7, 6]] | Failed |
| stream 2 w=10 k=3 | [[3, 15], [6, 6], [5, 1]] | [[3, 15], [6, 6], [1, 5]] | Failed |
| stream 3 w=5 k=2 | [[3, 13], [6, 10]] | [[3, 13], [6, 10]] | Passed |
| hit refreshes estimate | [[1, 9], [2, 3]] | [[1, 9], [3, 4]] | Failed |
| 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 / 802a14da519ff4cd6c8066d76ebe072775a98396c8c484143c38bac1ca203876
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.567514+00:00.
Case digest / 2406e89ed6363c58d572130244b49d8d0aba4e4e5c20e2f029d659417659cc2d