FA-73301 / Probabilistic sketches / Open access
DGIM sliding-window bit counting: three buckets of a size allowed · case 01
The histogram holds more buckets than the invariant allows and estimates change.
ROOT CAUSE
Merging starts only when four buckets share a size.
VERIFIED REPAIR
Merge as soon as more than two buckets share a size.
Unsuccessful approach: Merging at two buckets of a size halves the resolution and increases the error.
Case contract
Input {W, bits, queries}; timestamps start at 1. Buckets are [size, timestamp of most recent 1], newest first. Before processing time t, buckets with timestamp <= t - W expire. A 1 bit adds [1, t]; while more than two buckets share a size, the two oldest of that size merge into one of double size keeping the more recent timestamp, cascading upward. At a query time the estimate is the total size minus floor(oldest size / 2). Return [[t, estimate] per query, final buckets].
Why this case matters
Exponential-histogram counters approximate "events in the last W ticks" in logarithmic memory for streaming monitors; merge and expiry rules determine the error bound.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
W = x['W']
buckets = []
out = []
for t, bit in enumerate(x['bits'], 1):
while buckets and buckets[-1][1] <= t - W:
buckets.pop()
if bit:
buckets.insert(0, [1, t])
size = 1
while True:
idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
if len(idx) <= 3:
break
a, z = idx[-2], idx[-1]
buckets[a] = [size * 2, buckets[a][1]]
del buckets[z]
size *= 2
if t in x['queries']:
if buckets:
total = sum(bk[0] for bk in buckets)
out.append([t, total - buckets[-1][0] // 2])
else:
out.append([t, 0])
return [out, buckets]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
{'W': 10,
'bits': [1,
0,
1,
1,
0,
1,
0,
0,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1],
'queries': [15, 27, 30]},
[[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
'queries': [12, 22, 25]},
[[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
1,
0,
1,
1,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
0,
0,
1,
0,
1,
1,
1],
'queries': [20, 37, 40]},
[[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
['stream 3 W=6',
{'W': 6,
'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
'queries': [10, 17, 20]},
[[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
[[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
[[[4, 3], [8, 1], [10, 0]], []]],
['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
0,
1,
1,
0,
0,
0,
1,
1,
0,
0,
0,
1,
0,
1,
1,
0,
1,
1,
1,
1,
0,
0,
0,
1,
0,
1,
1,
1],
'queries': [15, 27, 30]},
[[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
['stream 1 W=8',
{'W': 8,
'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
'queries': [12, 22, 25]},
[[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
['stream 2 W=16',
{'W': 16,
'bits': [1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
0,
0,
0,
1,
0,
1],
'queries': [20, 37, 40]},
[[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
'queries': [10, 17, 20]},
[[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
[[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
[[[4, 3], [8, 1], [11, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
0,
0,
1,
1,
1,
0,
0,
0,
1,
1,
1,
0,
0,
1,
0,
1,
1,
0,
0,
1,
0,
1,
1,
0,
1,
1,
1,
0],
'queries': [15, 27, 30]},
[[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
'queries': [12, 22, 25]},
[[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
['stream 2 W=16',
{'W': 16,
'bits': [1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
0,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
0,
1,
1,
1,
1,
1,
1,
0,
0,
1,
0,
1,
1],
'queries': [20, 37, 40]},
[[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
'queries': [10, 17, 20]},
[[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
[[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
[[[4, 3], [8, 1], [12, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
1,
1,
1,
1,
0,
0,
0,
1,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
0,
0,
1,
0,
0,
1],
'queries': [15, 27, 30]},
[[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
'queries': [12, 22, 25]},
[[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
0,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
1,
0,
1,
0,
1,
1,
0,
1,
1,
0,
1,
1,
0,
1,
0,
0,
1,
1,
1,
1,
0],
'queries': [20, 37, 40]},
[[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
'queries': [10, 17, 20]},
[[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
[[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
[[[4, 3], [8, 1], [13, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
0,
0,
0,
1,
1,
1,
1,
1,
0,
1,
0,
0,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1,
0],
'queries': [15, 27, 30]},
[[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
['stream 1 W=8',
{'W': 8,
'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
'queries': [12, 22, 25]},
[[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
0,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
0,
1,
1,
1,
0,
1,
1,
1,
0,
0,
0,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1],
'queries': [20, 37, 40]},
[[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
'queries': [10, 17, 20]},
[[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
[[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
[[[4, 3], [8, 1], [14, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 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 |
|---|---|---|---|
| stream 0 W=10 | [[[15, 5], [27, 9], [30, 8]], [[1, 30], [1, 29], [1, 27], [2, 26], [2, 24], [2, 22]]] | [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]] | Failed |
| stream 1 W=8 | [[[12, 3], [22, 5], [25, 4]], [[1, 25], [1, 22], [1, 21], [2, 20]]] | [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]] | Failed |
| stream 2 W=16 | [[[20, 4], [37, 9], [40, 8]], [[1, 40], [1, 39], [2, 38], [2, 33], [4, 29]]] | [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]] | Failed |
| stream 3 W=6 | [[[10, 2], [17, 3], [20, 3]], [[1, 20], [1, 18], [2, 17]]] | [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]] | Failed |
| all ones | [[[7, 6], [15, 13]], [[1, 15], [1, 14], [1, 13], [2, 12], [2, 10], [4, 8], [4, 4]]] | [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]] | Failed |
| trailing zeros expire | [[[4, 3], [8, 1], [10, 0]], []] | [[[4, 3], [8, 1], [10, 0]], []] | Passed |
| empty window | [[[2, 0], [4, 0]], []] | [[[2, 0], [4, 0]], []] | Passed |
SHA-256 / 758cd4290c93dfc020ee5a3d854977b4172123e18e92cdfc1bf4832d91e526d2
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
W = x['W']
buckets = []
out = []
for t, bit in enumerate(x['bits'], 1):
while buckets and buckets[-1][1] <= t - W:
buckets.pop()
if bit:
buckets.insert(0, [1, t])
size = 1
while True:
idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
if len(idx) <= 1:
break
a, z = idx[-2], idx[-1]
buckets[a] = [size * 2, buckets[a][1]]
del buckets[z]
size *= 2
if t in x['queries']:
if buckets:
total = sum(bk[0] for bk in buckets)
out.append([t, total - buckets[-1][0] // 2])
else:
out.append([t, 0])
return [out, buckets]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
{'W': 10,
'bits': [1,
0,
1,
1,
0,
1,
0,
0,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1],
'queries': [15, 27, 30]},
[[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
'queries': [12, 22, 25]},
[[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
1,
0,
1,
1,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
0,
0,
1,
0,
1,
1,
1],
'queries': [20, 37, 40]},
[[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
['stream 3 W=6',
{'W': 6,
'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
'queries': [10, 17, 20]},
[[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
[[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
[[[4, 3], [8, 1], [10, 0]], []]],
['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
0,
1,
1,
0,
0,
0,
1,
1,
0,
0,
0,
1,
0,
1,
1,
0,
1,
1,
1,
1,
0,
0,
0,
1,
0,
1,
1,
1],
'queries': [15, 27, 30]},
[[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
['stream 1 W=8',
{'W': 8,
'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
'queries': [12, 22, 25]},
[[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
['stream 2 W=16',
{'W': 16,
'bits': [1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
0,
0,
0,
1,
0,
1],
'queries': [20, 37, 40]},
[[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
'queries': [10, 17, 20]},
[[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
[[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
[[[4, 3], [8, 1], [11, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
0,
0,
1,
1,
1,
0,
0,
0,
1,
1,
1,
0,
0,
1,
0,
1,
1,
0,
0,
1,
0,
1,
1,
0,
1,
1,
1,
0],
'queries': [15, 27, 30]},
[[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
'queries': [12, 22, 25]},
[[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
['stream 2 W=16',
{'W': 16,
'bits': [1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
0,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
0,
1,
1,
1,
1,
1,
1,
0,
0,
1,
0,
1,
1],
'queries': [20, 37, 40]},
[[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
'queries': [10, 17, 20]},
[[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
[[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
[[[4, 3], [8, 1], [12, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
1,
1,
1,
1,
0,
0,
0,
1,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
0,
0,
1,
0,
0,
1],
'queries': [15, 27, 30]},
[[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
'queries': [12, 22, 25]},
[[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
0,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
1,
0,
1,
0,
1,
1,
0,
1,
1,
0,
1,
1,
0,
1,
0,
0,
1,
1,
1,
1,
0],
'queries': [20, 37, 40]},
[[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
'queries': [10, 17, 20]},
[[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
[[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
[[[4, 3], [8, 1], [13, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
0,
0,
0,
1,
1,
1,
1,
1,
0,
1,
0,
0,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1,
0],
'queries': [15, 27, 30]},
[[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
['stream 1 W=8',
{'W': 8,
'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
'queries': [12, 22, 25]},
[[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
0,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
0,
1,
1,
1,
0,
1,
1,
1,
0,
0,
0,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1],
'queries': [20, 37, 40]},
[[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
'queries': [10, 17, 20]},
[[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
[[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
[[[4, 3], [8, 1], [14, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 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 |
|---|---|---|---|
| stream 0 W=10 | [[[15, 4], [27, 7], [30, 9]], [[1, 30], [4, 29], [8, 24]]] | [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]] | Failed |
| stream 1 W=8 | [[[12, 4], [22, 4], [25, 5]], [[1, 25], [2, 22], [4, 20]]] | [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]] | Failed |
| stream 2 W=16 | [[[20, 5], [37, 9], [40, 12]], [[4, 40], [16, 33]]] | [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]] | Failed |
| stream 3 W=6 | [[[10, 2], [17, 4], [20, 2]], [[4, 20]]] | [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]] | Failed |
| all ones | [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]] | [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]] | Passed |
| trailing zeros expire | [[[4, 2], [8, 2], [10, 0]], []] | [[[4, 3], [8, 1], [10, 0]], []] | Failed |
| empty window | [[[2, 0], [4, 0]], []] | [[[2, 0], [4, 0]], []] | Passed |
SHA-256 / a8b57801df0c44e65ba64dc013facc12372e4ea2e7467336b82c31017ce018a9
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
W = x['W']
buckets = []
out = []
for t, bit in enumerate(x['bits'], 1):
while buckets and buckets[-1][1] <= t - W:
buckets.pop()
if bit:
buckets.insert(0, [1, t])
size = 1
while True:
idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
if len(idx) <= 2:
break
a, z = idx[-2], idx[-1]
buckets[a] = [size * 2, buckets[a][1]]
del buckets[z]
size *= 2
if t in x['queries']:
if buckets:
total = sum(bk[0] for bk in buckets)
out.append([t, total - buckets[-1][0] // 2])
else:
out.append([t, 0])
return [out, buckets]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
{'W': 10,
'bits': [1,
0,
1,
1,
0,
1,
0,
0,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1],
'queries': [15, 27, 30]},
[[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
'queries': [12, 22, 25]},
[[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
1,
0,
1,
1,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
0,
0,
1,
0,
1,
1,
1],
'queries': [20, 37, 40]},
[[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
['stream 3 W=6',
{'W': 6,
'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
'queries': [10, 17, 20]},
[[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
[[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
[[[4, 3], [8, 1], [10, 0]], []]],
['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
0,
1,
1,
0,
0,
0,
1,
1,
0,
0,
0,
1,
0,
1,
1,
0,
1,
1,
1,
1,
0,
0,
0,
1,
0,
1,
1,
1],
'queries': [15, 27, 30]},
[[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
['stream 1 W=8',
{'W': 8,
'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
'queries': [12, 22, 25]},
[[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
['stream 2 W=16',
{'W': 16,
'bits': [1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
0,
1,
1,
0,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
0,
0,
0,
0,
1,
0,
1],
'queries': [20, 37, 40]},
[[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
'queries': [10, 17, 20]},
[[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
[[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
[[[4, 3], [8, 1], [11, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
0,
0,
1,
1,
1,
0,
0,
0,
1,
1,
1,
0,
0,
1,
0,
1,
1,
0,
0,
1,
0,
1,
1,
0,
1,
1,
1,
0],
'queries': [15, 27, 30]},
[[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
'queries': [12, 22, 25]},
[[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
['stream 2 W=16',
{'W': 16,
'bits': [1,
1,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
0,
1,
1,
0,
1,
1,
1,
1,
1,
1,
1,
0,
0,
0,
1,
0,
1,
1,
1,
1,
1,
1,
0,
0,
1,
0,
1,
1],
'queries': [20, 37, 40]},
[[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
'queries': [10, 17, 20]},
[[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
[[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
[[[4, 3], [8, 1], [12, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
1,
1,
1,
1,
1,
0,
0,
0,
1,
1,
0,
1,
1,
1,
0,
1,
0,
1,
1,
1,
0,
1,
1,
0,
0,
1,
0,
0,
1],
'queries': [15, 27, 30]},
[[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
['stream 1 W=8',
{'W': 8,
'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
'queries': [12, 22, 25]},
[[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
0,
1,
1,
1,
1,
0,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1,
0,
1,
1,
0,
1,
0,
1,
1,
0,
1,
1,
0,
1,
1,
0,
1,
0,
0,
1,
1,
1,
1,
0],
'queries': [20, 37, 40]},
[[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
'queries': [10, 17, 20]},
[[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
[[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
[[[4, 3], [8, 1], [13, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 0]], []]]],
[['stream 0 W=10',
{'W': 10,
'bits': [0,
0,
0,
0,
1,
1,
1,
1,
1,
0,
1,
0,
0,
0,
1,
1,
1,
1,
0,
1,
1,
1,
1,
0,
1,
1,
1,
0,
1,
0],
'queries': [15, 27, 30]},
[[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
['stream 1 W=8',
{'W': 8,
'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
'queries': [12, 22, 25]},
[[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
['stream 2 W=16',
{'W': 16,
'bits': [0,
0,
1,
1,
1,
0,
0,
1,
1,
1,
1,
1,
1,
1,
0,
1,
1,
1,
0,
0,
1,
1,
1,
0,
1,
1,
1,
0,
0,
0,
1,
0,
1,
0,
1,
1,
1,
1,
0,
1],
'queries': [20, 37, 40]},
[[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
['stream 3 W=6',
{'W': 6,
'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
'queries': [10, 17, 20]},
[[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
['all ones',
{'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
[[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
['trailing zeros expire',
{'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
[[[4, 3], [8, 1], [14, 0]], []]],
['empty window',
{'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
[[[2, 0], [4, 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 |
|---|---|---|---|
| stream 0 W=10 | [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]] | [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]] | Passed |
| stream 1 W=8 | [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]] | [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]] | Passed |
| stream 2 W=16 | [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]] | [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]] | Passed |
| stream 3 W=6 | [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]] | [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]] | Passed |
| all ones | [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]] | [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]] | Passed |
| trailing zeros expire | [[[4, 3], [8, 1], [10, 0]], []] | [[[4, 3], [8, 1], [10, 0]], []] | Passed |
| empty window | [[[2, 0], [4, 0]], []] | [[[2, 0], [4, 0]], []] | Passed |
SHA-256 / cbb4b49bb49a918c01372f5d8bb755fb5f2cf38a08771c3a1af1b60e3eb8c7e4
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:48:46.220032+00:00.
Case digest / f32f33fca9b955b6976f9ae052bd1f0330e1f5e448d953928d34f4aa808a036d