FA-73336 / Probabilistic sketches / Open access
Top-k tracking over a Count-Min sketch: candidate scored before its own update · case 01
Each key is scored without its current occurrence, so newcomers can never beat equal incumbents.
ROOT CAUSE
The estimate is read before the sketch is updated with the current count.
VERIFIED REPAIR
Update the sketch first, then read the minimum estimate.
Unsuccessful approach: Reading the maximum cell uses the most collision-contaminated row.
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']:
est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))
for r in range(3):
t[r][(A[r] * key + B[r]) % P % w] += c
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, 7], [5, 5]] | [[3, 8], [5, 8]] | Failed |
| stream 1 w=6 k=3 | [[5, 10], [2, 4], [1, 3]] | [[5, 12], [6, 6], [7, 6]] | Failed |
| stream 2 w=10 k=3 | [[3, 11], [6, 5], [4, 2]] | [[3, 15], [6, 6], [1, 5]] | Failed |
| stream 3 w=5 k=2 | [[3, 11], [6, 9]] | [[3, 13], [6, 10]] | Failed |
| hit refreshes estimate | [[1, 7], [2, 0]] | [[1, 9], [3, 4]] | Failed |
| tie with minimum | [[4, 0], [9, 0]] | [[4, 3], [9, 3]] | Failed |
| equal newcomer keeps incumbent | [[4, 0], [9, 0]] | [[4, 3], [9, 3]] | Failed |
| colliding refresh | [[1, 5], [2, 2]] | [[1, 7], [2, 5]] | Failed |
| tie among minima eviction | [[4, 0], [9, 0]] | [[7, 6], [9, 3]] | Failed |
| newcomer below minimum | [[2, 5], [1, 0]] | [[1, 6], [2, 6]] | Failed |
SHA-256 / a743b2f5779c859e293a58b2c168e63a45f3a5ddc05283af67636e7c3931e953
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 = max(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 | [[4, 12], [5, 11]] | [[3, 8], [5, 8]] | Failed |
| stream 1 w=6 k=3 | [[7, 24], [5, 20], [1, 14]] | [[5, 12], [6, 6], [7, 6]] | Failed |
| stream 2 w=10 k=3 | [[1, 23], [3, 20], [4, 16]] | [[3, 15], [6, 6], [1, 5]] | Failed |
| stream 3 w=5 k=2 | [[3, 22], [6, 17]] | [[3, 13], [6, 10]] | Failed |
| hit refreshes estimate | [[1, 9], [3, 4]] | [[1, 9], [3, 4]] | Passed |
| tie with minimum | [[4, 6], [9, 3]] | [[4, 3], [9, 3]] | Failed |
| equal newcomer keeps incumbent | [[9, 6], [4, 3]] | [[4, 3], [9, 3]] | Failed |
| colliding refresh | [[1, 7], [2, 5]] | [[1, 7], [2, 5]] | Passed |
| tie among minima eviction | [[7, 6], [9, 6]] | [[7, 6], [9, 3]] | Failed |
| newcomer below minimum | [[1, 6], [2, 6]] | [[1, 6], [2, 6]] | Passed |
SHA-256 / e3fa5e0327eaa588b33b7a52b3467ab345d73c1e41216477ae072e24f6d6fd67
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.593611+00:00.
Case digest / d95abaa2829ad137f6e96776f2ec5770767f5eb4903f269ea612f6d2733db215