FA-73041 / Probabilistic sketches / Open access
Count-Min sketch with conservative update: conservative update lowers larger cells · case 01
Cells already inflated by other keys are lowered to this key's target, so other keys become underestimated.
ROOT CAUSE
Each cell is assigned est + count unconditionally instead of being raised only when smaller.
VERIFIED REPAIR
Raise each cell to max(cell, e + count).
Unsuccessful approach: Adding count to every cell is the plain Count-Min update and overestimates colliding keys.
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]
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] = 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', 2, 2, 0], 5, 2, [[0, 2, 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]]] | Failed |
| uneven rows | [['ok', 'ok', 'ok', 'ok', 2, 2, 2], 12, 9, [[2, 0, 5, 0], [2, 0, 0, 5], [0, 0, 5, 2], [2, 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]]] | Failed |
| 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, 1, 1, 2, 'rejected'], 30, 17, [[5, 2, 2, 4, 4], [2, 3, 5, 5, 2], [0, 1, 1, 5, 1]]] | [['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 / 21b32a52432b45fc4c80bff9ae6b007856d4fe333c77991ca4084aaa214e0133
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] = t[r][b] + 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, 5, 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]]] | Failed |
| uneven rows | [['ok', 'ok', 'ok', 'ok', 5, 5, 2], 12, 9, [[7, 0, 5, 0], [7, 0, 0, 5], [0, 0, 10, 2], [7, 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]]] | Failed |
| 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, 7, 7, 3, 'rejected'], 30, 17, [[10, 3, 3, 7, 7], [5, 7, 7, 6, 5], [0, 10, 1, 9, 10]]] | [['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 / 75475eceb73f73bf4d49e4e815261a6f7e3df81591fa031c34f2dca9055f427e
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.904723+00:00.
Case digest / 4a5c73db204505b5d2f136b31c3aef925c32a24e54dcdb12cd99d7546ee6f447