FA-73311 / Probabilistic sketches / Open access
DGIM sliding-window bit counting: bucket at the window edge not expired · case 01
A 1 that is exactly W ticks old is still counted.
ROOT CAUSE
Expiry uses a strict comparison, keeping buckets whose timestamp equals t - W.
VERIFIED REPAIR
Expire buckets whose timestamp is at most t - W.
Unsuccessful approach: Expiring only when a 1 arrives lets stale buckets survive runs of zeros.
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) <= 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, 7]], [[1, 25], [2, 22], [2, 20], [4, 17]]] | [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]] | Failed |
| stream 2 W=16 | [[[20, 5], [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]]] | 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, 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, 2], [10, 0]], []] | [[[4, 3], [8, 1], [10, 0]], []] | Failed |
| empty window | [[[2, 0], [4, 0]], []] | [[[2, 0], [4, 0]], []] | Passed |
SHA-256 / 2efac189ebb92fa278c2b7f0c4fc7502c60e7a6778fb2434281f383f93a34528
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 bit and 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, 3], [10, 3]], [[1, 4], [1, 3], [2, 2]]] | [[[4, 3], [8, 1], [10, 0]], []] | Failed |
| empty window | [[[2, 0], [4, 0]], []] | [[[2, 0], [4, 0]], []] | Passed |
SHA-256 / 916ec55bd0652eb4e32afef279ce7e61520085a8f9244ea1d73cdac39c8b5ecc
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.350509+00:00.
Case digest / 1d11a05b644eb86b2bb53be4e39e029714686808f59764761f727f53a6067c01