FA-73051 / Probabilistic sketches / Open access
Count-Min sketch with conservative update: zero and negative counts accepted · case 01
Deletions are acknowledged although conservative cells cannot decrease, and the stream total drifts.
ROOT CAUSE
Non-positive counts are not rejected.
VERIFIED REPAIR
Reject any count <= 0.
Unsuccessful approach: Rejecting only negative counts still acknowledges zero-count updates.
Case contract
Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is "rejected" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].
Why this case matters
Conservative update reduces Count-Min overestimation in heavy-hitter monitors, but only if the raise-to-target rule is applied exactly.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
w = x['w']
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677]
B = [12345, 1013904223, 7, 99991, 31337]
P = 2147483647
d = x['d']
t = [[0] * w for _ in range(d)]
def bucket(r, key):
return (A[r] * key + B[r]) % P % w
total = 0
res = []
for op in x['ops']:
if op[0] == 'add':
key, cnt = op[1], op[2]
est = min(t[r][bucket(r, key)] for r in range(d))
for r in range(d):
b = bucket(r, key)
t[r][b] = max(t[r][b], est + cnt)
total += cnt
res.append('ok')
else:
res.append(min(t[r][bucket(r, op[1])] for r in range(d)))
return [res, total, math.ceil(math.e / w * total), t]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000007, 3],
['add', 2700000021, 2],
['q', 900000007],
['q', 2700000021],
['q', 7]],
'w': 7},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 2],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 2],
12,
9,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 2],
['add', 2, 3],
['add', 3, 4],
['add', 4, 1],
['add', 5, 2],
['add', 6, 3],
['add', 7, 4],
['add', 8, 1],
['add', 9, 2],
['add', 10, 3],
['add', 11, 4],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
4,
4,
2,
'rejected'],
30,
17,
[[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000014, 3],
['add', 2700000042, 2],
['q', 900000014],
['q', 2700000042],
['q', 7]],
'w': 8},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 2, 0, 0, 0, 3], [0, 0, 2, 3, 0, 0, 0, 0], [3, 0, 2, 0, 0, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 3],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 3],
13,
9,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 3], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 3],
['add', 2, 1],
['add', 3, 3],
['add', 4, 1],
['add', 5, 3],
['add', 6, 1],
['add', 7, 3],
['add', 8, 1],
['add', 9, 3],
['add', 10, 1],
['add', 11, 3],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
3,
3,
3,
'rejected'],
24,
14,
[[4, 3, 3, 3, 3], [3, 3, 4, 4, 3], [0, 3, 1, 4, 3]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000021, 3],
['add', 2700000063, 2],
['q', 900000021],
['q', 2700000063],
['q', 7]],
'w': 9},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 2, 0, 0, 3, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0], [0, 3, 0, 0, 0, 0, 2, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 4],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 4],
14,
10,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 4], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 4],
['add', 2, 3],
['add', 3, 2],
['add', 4, 1],
['add', 5, 4],
['add', 6, 3],
['add', 7, 2],
['add', 8, 1],
['add', 9, 4],
['add', 10, 3],
['add', 11, 2],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
3,
3,
4,
'rejected'],
30,
17,
[[5, 4, 4, 3, 3], [4, 3, 5, 3, 4], [0, 4, 1, 5, 4]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000028, 3],
['add', 2700000084, 2],
['q', 900000028],
['q', 2700000084],
['q', 7]],
'w': 10},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 0, 2, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 3, 2, 0, 0, 0],
[0, 0, 0, 0, 3, 0, 0, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 5],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 5],
15,
11,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 5], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 1],
['add', 2, 1],
['add', 3, 1],
['add', 4, 1],
['add', 5, 1],
['add', 6, 1],
['add', 7, 1],
['add', 8, 1],
['add', 9, 1],
['add', 10, 1],
['add', 11, 1],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
1,
1,
1,
'rejected'],
12,
7,
[[2, 1, 1, 1, 1], [1, 1, 2, 2, 1], [0, 1, 1, 2, 1]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000035, 3],
['add', 2700000105, 2],
['q', 900000035],
['q', 2700000105],
['q', 7]],
'w': 11},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 2],
[0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 6],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 6],
16,
11,
[[6, 0, 5, 0], [6, 0, 0, 5], [0, 0, 5, 6], [6, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 2],
['add', 2, 3],
['add', 3, 4],
['add', 4, 1],
['add', 5, 2],
['add', 6, 3],
['add', 7, 4],
['add', 8, 1],
['add', 9, 2],
['add', 10, 3],
['add', 11, 4],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
4,
4,
2,
'rejected'],
30,
17,
[[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]]]
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 |
|---|---|---|---|
| colliding keys | [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]] | [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]] | Passed |
| zero and negative counts | [['ok', 'ok', 'ok', 5], 3, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]] | [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]] | Failed |
| huge keys wrap prime | [['ok', 'ok', 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]] | [['ok', 'ok', 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]] | Passed |
| uneven rows | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]] | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]] | Passed |
| single row | [['ok', 'ok', 2, 'ok'], 5, 5, [[2, 3, 0]]] | [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]] | Failed |
| many keys | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 1, 4, 4, 2, 'ok'], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 1, 4, 4, 2, 'rejected'], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]] | Failed |
SHA-256 / 91cae4156aad433d4b5bb115f6e375c370271422bd8f4fd960174cc906cff13e
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
w = x['w']
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677]
B = [12345, 1013904223, 7, 99991, 31337]
P = 2147483647
d = x['d']
t = [[0] * w for _ in range(d)]
def bucket(r, key):
return (A[r] * key + B[r]) % P % w
total = 0
res = []
for op in x['ops']:
if op[0] == 'add':
key, cnt = op[1], op[2]
if cnt < 0:
res.append('rejected')
continue
est = min(t[r][bucket(r, key)] for r in range(d))
for r in range(d):
b = bucket(r, key)
t[r][b] = max(t[r][b], est + cnt)
total += cnt
res.append('ok')
else:
res.append(min(t[r][bucket(r, op[1])] for r in range(d)))
return [res, total, math.ceil(math.e / w * total), t]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000007, 3],
['add', 2700000021, 2],
['q', 900000007],
['q', 2700000021],
['q', 7]],
'w': 7},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 2],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 2],
12,
9,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 2],
['add', 2, 3],
['add', 3, 4],
['add', 4, 1],
['add', 5, 2],
['add', 6, 3],
['add', 7, 4],
['add', 8, 1],
['add', 9, 2],
['add', 10, 3],
['add', 11, 4],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
4,
4,
2,
'rejected'],
30,
17,
[[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000014, 3],
['add', 2700000042, 2],
['q', 900000014],
['q', 2700000042],
['q', 7]],
'w': 8},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 2, 0, 0, 0, 3], [0, 0, 2, 3, 0, 0, 0, 0], [3, 0, 2, 0, 0, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 3],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 3],
13,
9,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 3], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 3],
['add', 2, 1],
['add', 3, 3],
['add', 4, 1],
['add', 5, 3],
['add', 6, 1],
['add', 7, 3],
['add', 8, 1],
['add', 9, 3],
['add', 10, 1],
['add', 11, 3],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
3,
3,
3,
'rejected'],
24,
14,
[[4, 3, 3, 3, 3], [3, 3, 4, 4, 3], [0, 3, 1, 4, 3]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000021, 3],
['add', 2700000063, 2],
['q', 900000021],
['q', 2700000063],
['q', 7]],
'w': 9},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 2, 0, 0, 3, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0], [0, 3, 0, 0, 0, 0, 2, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 4],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 4],
14,
10,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 4], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 4],
['add', 2, 3],
['add', 3, 2],
['add', 4, 1],
['add', 5, 4],
['add', 6, 3],
['add', 7, 2],
['add', 8, 1],
['add', 9, 4],
['add', 10, 3],
['add', 11, 2],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
3,
3,
4,
'rejected'],
30,
17,
[[5, 4, 4, 3, 3], [4, 3, 5, 3, 4], [0, 4, 1, 5, 4]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000028, 3],
['add', 2700000084, 2],
['q', 900000028],
['q', 2700000084],
['q', 7]],
'w': 10},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 0, 2, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 3, 2, 0, 0, 0],
[0, 0, 0, 0, 3, 0, 0, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 5],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 5],
15,
11,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 5], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 1],
['add', 2, 1],
['add', 3, 1],
['add', 4, 1],
['add', 5, 1],
['add', 6, 1],
['add', 7, 1],
['add', 8, 1],
['add', 9, 1],
['add', 10, 1],
['add', 11, 1],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
1,
1,
1,
'rejected'],
12,
7,
[[2, 1, 1, 1, 1], [1, 1, 2, 2, 1], [0, 1, 1, 2, 1]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000035, 3],
['add', 2700000105, 2],
['q', 900000035],
['q', 2700000105],
['q', 7]],
'w': 11},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 2],
[0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 6],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 6],
16,
11,
[[6, 0, 5, 0], [6, 0, 0, 5], [0, 0, 5, 6], [6, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 2],
['add', 2, 3],
['add', 3, 4],
['add', 4, 1],
['add', 5, 2],
['add', 6, 3],
['add', 7, 4],
['add', 8, 1],
['add', 9, 2],
['add', 10, 3],
['add', 11, 4],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
4,
4,
2,
'rejected'],
30,
17,
[[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]]]
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 |
|---|---|---|---|
| colliding keys | [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]] | [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]] | Passed |
| zero and negative counts | [['ok', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]] | [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]] | Failed |
| huge keys wrap prime | [['ok', 'ok', 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]] | [['ok', 'ok', 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]] | Passed |
| uneven rows | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]] | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]] | Passed |
| single row | [['ok', 'ok', 2, 'ok'], 5, 5, [[2, 3, 0]]] | [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]] | Failed |
| many keys | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 1, 4, 4, 2, 'ok'], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 1, 4, 4, 2, 'rejected'], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]] | Failed |
SHA-256 / 1bb067936fba3b2d277338cc72f1578a9081bd4129c435fb526f40859a875427
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
w = x['w']
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677]
B = [12345, 1013904223, 7, 99991, 31337]
P = 2147483647
d = x['d']
t = [[0] * w for _ in range(d)]
def bucket(r, key):
return (A[r] * key + B[r]) % P % w
total = 0
res = []
for op in x['ops']:
if op[0] == 'add':
key, cnt = op[1], op[2]
if cnt <= 0:
res.append('rejected')
continue
est = min(t[r][bucket(r, key)] for r in range(d))
for r in range(d):
b = bucket(r, key)
t[r][b] = max(t[r][b], est + cnt)
total += cnt
res.append('ok')
else:
res.append(min(t[r][bucket(r, op[1])] for r in range(d)))
return [res, total, math.ceil(math.e / w * total), t]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000007, 3],
['add', 2700000021, 2],
['q', 900000007],
['q', 2700000021],
['q', 7]],
'w': 7},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 2],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 2],
12,
9,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 2],
['add', 2, 3],
['add', 3, 4],
['add', 4, 1],
['add', 5, 2],
['add', 6, 3],
['add', 7, 4],
['add', 8, 1],
['add', 9, 2],
['add', 10, 3],
['add', 11, 4],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
4,
4,
2,
'rejected'],
30,
17,
[[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000014, 3],
['add', 2700000042, 2],
['q', 900000014],
['q', 2700000042],
['q', 7]],
'w': 8},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 2, 0, 0, 0, 3], [0, 0, 2, 3, 0, 0, 0, 0], [3, 0, 2, 0, 0, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 3],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 3],
13,
9,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 3], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 3],
['add', 2, 1],
['add', 3, 3],
['add', 4, 1],
['add', 5, 3],
['add', 6, 1],
['add', 7, 3],
['add', 8, 1],
['add', 9, 3],
['add', 10, 1],
['add', 11, 3],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
3,
3,
3,
'rejected'],
24,
14,
[[4, 3, 3, 3, 3], [3, 3, 4, 4, 3], [0, 3, 1, 4, 3]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000021, 3],
['add', 2700000063, 2],
['q', 900000021],
['q', 2700000063],
['q', 7]],
'w': 9},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 2, 0, 0, 3, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0], [0, 3, 0, 0, 0, 0, 2, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 4],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 4],
14,
10,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 4], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 4],
['add', 2, 3],
['add', 3, 2],
['add', 4, 1],
['add', 5, 4],
['add', 6, 3],
['add', 7, 2],
['add', 8, 1],
['add', 9, 4],
['add', 10, 3],
['add', 11, 2],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
3,
3,
4,
'rejected'],
30,
17,
[[5, 4, 4, 3, 3], [4, 3, 5, 3, 4], [0, 4, 1, 5, 4]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000028, 3],
['add', 2700000084, 2],
['q', 900000028],
['q', 2700000084],
['q', 7]],
'w': 10},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 0, 2, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 3, 2, 0, 0, 0],
[0, 0, 0, 0, 3, 0, 0, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 5],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 5],
15,
11,
[[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 5], [5, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 1],
['add', 2, 1],
['add', 3, 1],
['add', 4, 1],
['add', 5, 1],
['add', 6, 1],
['add', 7, 1],
['add', 8, 1],
['add', 9, 1],
['add', 10, 1],
['add', 11, 1],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
1,
1,
1,
'rejected'],
12,
7,
[[2, 1, 1, 1, 1], [1, 1, 2, 2, 1], [0, 1, 1, 2, 1]]]]],
[['colliding keys',
{'d': 3,
'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],
'w': 5},
[['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],
['zero and negative counts',
{'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},
[['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],
['huge keys wrap prime',
{'d': 3,
'ops': [['add', 900000035, 3],
['add', 2700000105, 2],
['q', 900000035],
['q', 2700000105],
['q', 7]],
'w': 11},
[['ok', 'ok', 3, 2, 0],
5,
2,
[[0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 2],
[0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0]]]],
['uneven rows',
{'d': 4,
'ops': [['add', 2, 3],
['add', 9, 5],
['add', 2, 2],
['add', 5, 6],
['q', 2],
['q', 9],
['q', 5]],
'w': 4},
[['ok', 'ok', 'ok', 'ok', 5, 5, 6],
16,
11,
[[6, 0, 5, 0], [6, 0, 0, 5], [0, 0, 5, 6], [6, 0, 5, 0]]]],
['single row',
{'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},
[['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],
['many keys',
{'d': 3,
'ops': [['add', 0, 1],
['add', 1, 2],
['add', 2, 3],
['add', 3, 4],
['add', 4, 1],
['add', 5, 2],
['add', 6, 3],
['add', 7, 4],
['add', 8, 1],
['add', 9, 2],
['add', 10, 3],
['add', 11, 4],
['q', 0],
['q', 3],
['q', 6],
['q', 9],
['add', 2, 0]],
'w': 5},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
1,
4,
4,
2,
'rejected'],
30,
17,
[[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]]]
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 |
|---|---|---|---|
| colliding keys | [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]] | [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]] | Passed |
| zero and negative counts | [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]] | [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]] | Passed |
| huge keys wrap prime | [['ok', 'ok', 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]] | [['ok', 'ok', 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]] | Passed |
| uneven rows | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]] | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]] | Passed |
| single row | [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]] | [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]] | Passed |
| many keys | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 1, 4, 4, 2, 'rejected'], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 1, 4, 4, 2, 'rejected'], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]] | Passed |
SHA-256 / 0e18fcfdc61a0aa0508c64b1667c489c348c474f4cfb57183103a8face239005
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:43.990173+00:00.
Case digest / 9420d0877ec1c24a53f98cbd7bd6fdf48483e153d418589438880492198d872e