FA-72926 / Probabilistic sketches / Open access
Counting Bloom filter with 4-bit counters: repeated probe position counted twice · case 01
An item whose stride wraps onto an earlier position inflates that counter, and later removals leave residue or drain other items.
ROOT CAUSE
Positions are not de-duplicated, so an item whose probes repeat increments the same counter more than once.
VERIFIED REPAIR
Collect distinct positions per item so each counter changes at most once per operation.
Unsuccessful approach: De-duplicating only for add still decrements a repeated position twice on remove, leaving the filter inconsistent.
Case contract
Input {m, k, ops}; items are pre-hashed non-negative integers. Positions are the distinct values of (h1 + i*h2) mod m for i in 0..k-1 with h1 = item mod m and h2 = 1 + (item div m) mod (m-1), in first-seen order. add increments each distinct position once, saturating at 15. A saturated counter is sticky: remove never decrements it. remove is atomic: if any position is zero the result is "absent" and nothing changes; otherwise it decrements every non-saturated position. has requires every position to be positive. Return [results, counters].
Why this case matters
Counting Bloom filters support deletion in caches and routing tables; counter overflow, duplicate positions and non-atomic removals create false negatives that are otherwise impossible.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
c = [0] * m
def positions(item):
h1 = item % m
h2 = 1 + (item // m) % (m - 1)
out = []
for i in range(k):
p = (h1 + i * h2) % m
out.append(p)
return out
res = []
for op, item in x['ops']:
pos = positions(item)
if op == 'add':
for p in pos:
if c[p] < 15:
c[p] = c[p] + 1
res.append('added')
elif op == 'remove':
if any(c[p] == 0 for p in pos):
res.append('absent')
continue
for p in pos:
if c[p] < 15:
c[p] = c[p] - 1
res.append('removed')
else:
res.append(all(c[p] > 0 for p in pos))
return [res, c]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['duplicate probe positions',
{'k': 4,
'm': 12,
'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
[['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 12,
'ops': [['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['has', 63]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 12, 'ops': [['add', 137], ['add', 8], ['has', 137], ['remove', 8]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 12,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 12, 'ops': [['add', 6], ['remove', 42], ['has', 6]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 12, 'ops': [['add', 2], ['add', 14], ['has', 26], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 12, 'ops': [['add', 31], ['add', 32], ['remove', 31], ['has', 31], ['has', 32]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]]],
['remove absent from empty',
{'k': 2, 'm': 12, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 12,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 14,
'ops': [['add', 87], ['add', 1], ['has', 87], ['remove', 87], ['has', 87], ['has', 1]]},
[['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 14,
'ops': [['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['has', 87]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 14, 'ops': [['add', 187], ['add', 9], ['has', 187], ['remove', 9]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 14,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 14, 'ops': [['add', 7], ['remove', 49], ['has', 7]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 14, 'ops': [['add', 2], ['add', 16], ['has', 30], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 14, 'ops': [['add', 32], ['add', 33], ['remove', 32], ['has', 32], ['has', 33]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 14, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 14,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 15,
'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 15,
'ops': [['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['has', 63]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 15, 'ops': [['add', 215], ['add', 10], ['has', 215], ['remove', 10]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 15,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 15, 'ops': [['add', 8], ['remove', 53], ['has', 8]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 15, 'ops': [['add', 2], ['add', 17], ['has', 32], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 15, 'ops': [['add', 33], ['add', 34], ['remove', 33], ['has', 33], ['has', 34]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 15, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 15,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 16,
'ops': [['add', 115], ['add', 1], ['has', 115], ['remove', 115], ['has', 115], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 16,
'ops': [['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['has', 115]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 16, 'ops': [['add', 245], ['add', 11], ['has', 245], ['remove', 11]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 16,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 16, 'ops': [['add', 9], ['remove', 57], ['has', 9]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 16, 'ops': [['add', 2], ['add', 18], ['has', 34], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 16, 'ops': [['add', 34], ['add', 35], ['remove', 34], ['has', 34], ['has', 35]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 16, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 16,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 18,
'ops': [['add', 147], ['add', 1], ['has', 147], ['remove', 147], ['has', 147], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 18,
'ops': [['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['has', 147]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 18, 'ops': [['add', 311], ['add', 12], ['has', 311], ['remove', 12]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 18,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 18, 'ops': [['add', 10], ['remove', 64], ['has', 10]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 18, 'ops': [['add', 2], ['add', 20], ['has', 38], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True],
[0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 18, 'ops': [['add', 35], ['add', 36], ['remove', 35], ['has', 35], ['has', 36]]},
[['added', 'added', 'removed', False, True],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 18, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 18,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]]]
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 |
|---|---|---|---|
| duplicate probe positions | [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]] | [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]] | Passed |
| hot item with repeated positions | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 15, 0, 0, 0, 0, 0, 15, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | Failed |
| wide stride item | [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]] | [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]] | Passed |
| saturating counter | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', True], [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', True], [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]] | Passed |
| atomic removal of absent item | [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]] | [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]] | Passed |
| partial overlap membership | [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]] | [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]] | Passed |
| normal add and remove | [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]] | [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]] | Passed |
| remove absent from empty | [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | Passed |
| saturated then drained | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]] | Passed |
SHA-256 / a9a5cb1b2a4fc592f0cddca7193d2e778d7b2195c3a944b9448e11a449f3f1bf
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
c = [0] * m
def positions(item):
h1 = item % m
h2 = 1 + (item // m) % (m - 1)
out = []
for i in range(k):
p = (h1 + i * h2) % m
if p not in out or op == 'remove':
out.append(p)
return out
res = []
for op, item in x['ops']:
pos = positions(item)
if op == 'add':
for p in pos:
if c[p] < 15:
c[p] = c[p] + 1
res.append('added')
elif op == 'remove':
if any(c[p] == 0 for p in pos):
res.append('absent')
continue
for p in pos:
if c[p] < 15:
c[p] = c[p] - 1
res.append('removed')
else:
res.append(all(c[p] > 0 for p in pos))
return [res, c]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['duplicate probe positions',
{'k': 4,
'm': 12,
'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
[['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 12,
'ops': [['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['has', 63]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 12, 'ops': [['add', 137], ['add', 8], ['has', 137], ['remove', 8]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 12,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 12, 'ops': [['add', 6], ['remove', 42], ['has', 6]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 12, 'ops': [['add', 2], ['add', 14], ['has', 26], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 12, 'ops': [['add', 31], ['add', 32], ['remove', 31], ['has', 31], ['has', 32]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]]],
['remove absent from empty',
{'k': 2, 'm': 12, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 12,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 14,
'ops': [['add', 87], ['add', 1], ['has', 87], ['remove', 87], ['has', 87], ['has', 1]]},
[['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 14,
'ops': [['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['has', 87]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 14, 'ops': [['add', 187], ['add', 9], ['has', 187], ['remove', 9]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 14,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 14, 'ops': [['add', 7], ['remove', 49], ['has', 7]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 14, 'ops': [['add', 2], ['add', 16], ['has', 30], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 14, 'ops': [['add', 32], ['add', 33], ['remove', 32], ['has', 32], ['has', 33]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 14, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 14,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 15,
'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 15,
'ops': [['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['has', 63]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 15, 'ops': [['add', 215], ['add', 10], ['has', 215], ['remove', 10]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 15,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 15, 'ops': [['add', 8], ['remove', 53], ['has', 8]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 15, 'ops': [['add', 2], ['add', 17], ['has', 32], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 15, 'ops': [['add', 33], ['add', 34], ['remove', 33], ['has', 33], ['has', 34]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 15, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 15,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 16,
'ops': [['add', 115], ['add', 1], ['has', 115], ['remove', 115], ['has', 115], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 16,
'ops': [['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['has', 115]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 16, 'ops': [['add', 245], ['add', 11], ['has', 245], ['remove', 11]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 16,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 16, 'ops': [['add', 9], ['remove', 57], ['has', 9]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 16, 'ops': [['add', 2], ['add', 18], ['has', 34], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 16, 'ops': [['add', 34], ['add', 35], ['remove', 34], ['has', 34], ['has', 35]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 16, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 16,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 18,
'ops': [['add', 147], ['add', 1], ['has', 147], ['remove', 147], ['has', 147], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 18,
'ops': [['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['has', 147]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 18, 'ops': [['add', 311], ['add', 12], ['has', 311], ['remove', 12]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 18,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 18, 'ops': [['add', 10], ['remove', 64], ['has', 10]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 18, 'ops': [['add', 2], ['add', 20], ['has', 38], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True],
[0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 18, 'ops': [['add', 35], ['add', 36], ['remove', 35], ['has', 35], ['has', 36]]},
[['added', 'added', 'removed', False, True],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 18, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 18,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]]]
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 |
|---|---|---|---|
| duplicate probe positions | [['added', 'added', True, 'removed', False, False], [0, 1, 1, 0, 1, 0, 0, 0, 0, -1, 0, 0]] | [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]] | Failed |
| hot item with repeated positions | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'absent', 'absent', 'absent', 'absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | Failed |
| wide stride item | [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]] | [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]] | Passed |
| saturating counter | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', True], [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', True], [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]] | Passed |
| atomic removal of absent item | [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]] | [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]] | Passed |
| partial overlap membership | [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]] | [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]] | Passed |
| normal add and remove | [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]] | [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]] | Passed |
| remove absent from empty | [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | Passed |
| saturated then drained | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]] | Passed |
SHA-256 / 038819c8d77ebb7f57ca5517598c4de0510393754d5a07472b1989a471d1abbf
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
c = [0] * m
def positions(item):
h1 = item % m
h2 = 1 + (item // m) % (m - 1)
out = []
for i in range(k):
p = (h1 + i * h2) % m
if p not in out:
out.append(p)
return out
res = []
for op, item in x['ops']:
pos = positions(item)
if op == 'add':
for p in pos:
if c[p] < 15:
c[p] = c[p] + 1
res.append('added')
elif op == 'remove':
if any(c[p] == 0 for p in pos):
res.append('absent')
continue
for p in pos:
if c[p] < 15:
c[p] = c[p] - 1
res.append('removed')
else:
res.append(all(c[p] > 0 for p in pos))
return [res, c]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['duplicate probe positions',
{'k': 4,
'm': 12,
'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
[['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 12,
'ops': [['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['has', 63]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 12, 'ops': [['add', 137], ['add', 8], ['has', 137], ['remove', 8]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 12,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 12, 'ops': [['add', 6], ['remove', 42], ['has', 6]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 12, 'ops': [['add', 2], ['add', 14], ['has', 26], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 12, 'ops': [['add', 31], ['add', 32], ['remove', 31], ['has', 31], ['has', 32]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]]],
['remove absent from empty',
{'k': 2, 'm': 12, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 12,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 14,
'ops': [['add', 87], ['add', 1], ['has', 87], ['remove', 87], ['has', 87], ['has', 1]]},
[['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 14,
'ops': [['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['add', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['remove', 87],
['has', 87]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 14, 'ops': [['add', 187], ['add', 9], ['has', 187], ['remove', 9]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 14,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 14, 'ops': [['add', 7], ['remove', 49], ['has', 7]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 14, 'ops': [['add', 2], ['add', 16], ['has', 30], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 14, 'ops': [['add', 32], ['add', 33], ['remove', 32], ['has', 32], ['has', 33]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 14, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 14,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 15,
'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 15,
'ops': [['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['add', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['remove', 63],
['has', 63]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 15, 'ops': [['add', 215], ['add', 10], ['has', 215], ['remove', 10]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 15,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 15, 'ops': [['add', 8], ['remove', 53], ['has', 8]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 15, 'ops': [['add', 2], ['add', 17], ['has', 32], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 15, 'ops': [['add', 33], ['add', 34], ['remove', 33], ['has', 33], ['has', 34]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 15, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 15,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 16,
'ops': [['add', 115], ['add', 1], ['has', 115], ['remove', 115], ['has', 115], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 16,
'ops': [['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['add', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['remove', 115],
['has', 115]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 16, 'ops': [['add', 245], ['add', 11], ['has', 245], ['remove', 11]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 16,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 16, 'ops': [['add', 9], ['remove', 57], ['has', 9]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 16, 'ops': [['add', 2], ['add', 18], ['has', 34], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 16, 'ops': [['add', 34], ['add', 35], ['remove', 34], ['has', 34], ['has', 35]]},
[['added', 'added', 'removed', False, True], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 16, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 16,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]],
[['duplicate probe positions',
{'k': 4,
'm': 18,
'ops': [['add', 147], ['add', 1], ['has', 147], ['remove', 147], ['has', 147], ['has', 1]]},
[['added', 'added', True, 'removed', False, True],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['hot item with repeated positions',
{'k': 4,
'm': 18,
'ops': [['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['add', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['remove', 147],
['has', 147]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
False],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['wide stride item',
{'k': 3, 'm': 18, 'ops': [['add', 311], ['add', 12], ['has', 311], ['remove', 12]]},
[['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturating counter',
{'k': 2,
'm': 18,
'ops': [['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['add', 4],
['remove', 4],
['has', 4]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
True],
[0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['atomic removal of absent item',
{'k': 3, 'm': 18, 'ops': [['add', 10], ['remove', 64], ['has', 10]]},
[['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]]],
['partial overlap membership',
{'k': 3, 'm': 18, 'ops': [['add', 2], ['add', 20], ['has', 38], ['has', 3], ['has', 2]]},
[['added', 'added', False, False, True],
[0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['normal add and remove',
{'k': 2, 'm': 18, 'ops': [['add', 35], ['add', 36], ['remove', 35], ['has', 35], ['has', 36]]},
[['added', 'added', 'removed', False, True],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['remove absent from empty',
{'k': 2, 'm': 18, 'ops': [['remove', 9], ['has', 9]]},
[['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
['saturated then drained',
{'k': 1,
'm': 18,
'ops': [['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['add', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['remove', 6],
['has', 6]]},
[['added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'added',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
'removed',
True],
[0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]]]
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 |
|---|---|---|---|
| duplicate probe positions | [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]] | [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]] | Passed |
| hot item with repeated positions | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | Passed |
| wide stride item | [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]] | [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]] | Passed |
| saturating counter | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', True], [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', True], [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]] | Passed |
| atomic removal of absent item | [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]] | [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]] | Passed |
| partial overlap membership | [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]] | [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]] | Passed |
| normal add and remove | [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]] | [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]] | Passed |
| remove absent from empty | [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] | Passed |
| saturated then drained | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]] | [['added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'added', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', 'removed', True], [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]] | Passed |
SHA-256 / b1752ed904752db5c3830a5b34af03464bdda54fa5d33ac76f7fa036f848ea62
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:42.829266+00:00.
Case digest / b8557bf3dcb90b461ca7980a1aa64542fd0dfad4c0e3b61f921b89f9c0048eda