FA-73106 / Probabilistic sketches / Open access
Weighted Misra-Gries frequent items: discarded mass omits the newcomer · case 01
The reported error bound is smaller than the mass actually discarded.
ROOT CAUSE
Each decrement step accounts for the k counters but not the incoming item's share.
VERIFIED REPAIR
Add dec*(k+1) per decrement step.
Unsuccessful approach: Counting dec once ignores the k counters that were also reduced.
Case contract
Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].
Why this case matters
Heavy-hitter detection over weighted traffic (bytes per flow, spend per account) relies on the deterministic Misra-Gries error bound removed/(k+1).
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
C = {}
removed = 0
for item, wt in x['stream']:
if item in C:
C[item] += wt
elif len(C) < k:
C[item] = wt
else:
dec = min(min(C.values()), wt)
for key in list(C):
C[key] -= dec
if C[key] == 0:
del C[key]
wt -= dec
removed += dec * k
if wt > 0:
C[item] = wt
return [sorted([key, v] for key, v in C.items()), removed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 4],
['c', 1],
['a', 3],
['d', 1],
['d', 3],
['a', 5],
['e', 2],
['d', 3],
['d', 4],
['a', 5],
['a', 4]]},
[[['a', 14], ['d', 12]], 9]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['e', 5],
['c', 5],
['b', 3],
['d', 2],
['c', 2],
['d', 2],
['d', 1],
['c', 3],
['a', 4],
['d', 4],
['f', 1]]},
[[['a', 1], ['c', 4], ['d', 3]], 24]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['d', 2],
['c', 2],
['c', 1],
['c', 4],
['a', 1],
['c', 4],
['d', 4],
['c', 5],
['c', 3],
['c', 4],
['a', 1]]},
[[['c', 21], ['d', 4]], 6]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 5],
['a', 5],
['a', 2],
['a', 3],
['d', 4],
['a', 3],
['e', 4],
['e', 1],
['g', 4],
['g', 1],
['g', 3]]},
[[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 7]]},
[[['b', 1], ['c', 5]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 1]]},
[[['a', 2], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 1],
['e', 5],
['d', 4],
['e', 5],
['b', 1],
['e', 4],
['a', 5],
['b', 3],
['d', 1],
['d', 2],
['e', 1],
['d', 1]]},
[[['d', 2], ['e', 7]], 24]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['c', 2],
['b', 5],
['b', 5],
['c', 1],
['d', 1],
['a', 5],
['c', 2],
['f', 4],
['a', 2],
['f', 5],
['b', 2],
['d', 4]]},
[[['b', 5], ['d', 2], ['f', 3]], 28]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['c', 2],
['d', 2],
['c', 4],
['d', 5],
['d', 1],
['b', 2],
['b', 5],
['c', 3],
['e', 4],
['c', 5],
['e', 3],
['b', 2]]},
[[['c', 4], ['e', 4]], 30]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 2],
['g', 1],
['c', 5],
['a', 3],
['b', 2],
['b', 1],
['d', 3],
['g', 2],
['e', 3],
['b', 4],
['d', 2],
['d', 4]]},
[[['b', 2], ['d', 4], ['e', 1]], 25]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 8]]},
[[['b', 1], ['c', 6]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 2]]},
[[['a', 3], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['c', 3],
['e', 5],
['c', 1],
['a', 2],
['a', 2],
['a', 4],
['c', 3],
['d', 5],
['e', 3],
['a', 1],
['c', 1],
['b', 5],
['d', 1]]},
[[['b', 5], ['d', 1]], 30]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['a', 1],
['e', 4],
['e', 5],
['b', 2],
['f', 3],
['d', 3],
['b', 1],
['b', 1],
['f', 3],
['d', 2],
['c', 3],
['f', 3],
['c', 3]]},
[[['c', 4], ['e', 3], ['f', 3]], 24]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['e', 3],
['a', 1],
['c', 5],
['b', 5],
['c', 3],
['e', 4],
['b', 1],
['a', 5],
['e', 3],
['d', 1],
['e', 1],
['e', 1],
['e', 5]]},
[[['a', 3], ['e', 8]], 27]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 3],
['f', 4],
['e', 4],
['b', 2],
['c', 1],
['g', 1],
['f', 4],
['e', 3],
['a', 1],
['e', 4],
['e', 2],
['b', 2],
['f', 1]]},
[[['a', 2], ['b', 2], ['e', 11], ['f', 7]], 10]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 9]]},
[[['b', 1], ['c', 7]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 3]]},
[[['a', 4], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 3],
['e', 1],
['d', 3],
['c', 1],
['c', 4],
['c', 3],
['e', 5],
['e', 2],
['b', 5],
['a', 2],
['e', 5],
['d', 3],
['a', 1],
['b', 4]]},
[[['b', 3]], 39]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['d', 3],
['a', 5],
['c', 2],
['d', 1],
['b', 2],
['d', 3],
['b', 3],
['d', 4],
['c', 1],
['f', 5],
['d', 1],
['e', 5],
['b', 2],
['d', 3]]},
[[['d', 8], ['e', 3], ['f', 1]], 28]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['c', 5],
['b', 5],
['c', 2],
['c', 5],
['d', 4],
['a', 4],
['b', 4],
['c', 5],
['c', 1],
['e', 2],
['b', 3],
['e', 2],
['b', 3],
['d', 5]]},
[[['c', 3], ['d', 2]], 45]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['b', 5],
['d', 2],
['a', 4],
['f', 3],
['a', 1],
['b', 2],
['g', 1],
['c', 2],
['d', 3],
['d', 5],
['d', 3],
['e', 4],
['c', 3],
['g', 4]]},
[[['b', 1], ['d', 7], ['e', 1], ['g', 3]], 30]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 10]]},
[[['b', 1], ['c', 8]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 4]]},
[[['a', 5], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['b', 4],
['d', 3],
['d', 4],
['e', 4],
['c', 1],
['a', 3],
['b', 2],
['b', 5],
['e', 5],
['e', 1],
['d', 4],
['e', 3],
['c', 3],
['d', 3],
['e', 5]]},
[[['d', 1], ['e', 7]], 42]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['d', 3],
['a', 5],
['b', 5],
['e', 3],
['c', 4],
['d', 4],
['e', 4],
['e', 2],
['b', 4],
['d', 1],
['a', 4],
['b', 3],
['f', 1],
['f', 2],
['d', 4]]},
[[['b', 1], ['d', 4]], 44]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['d', 3],
['a', 5],
['a', 5],
['e', 3],
['b', 4],
['c', 4],
['a', 2],
['e', 1],
['e', 2],
['a', 5],
['e', 1],
['c', 3],
['c', 4],
['c', 1],
['c', 3]]},
[[['a', 6], ['c', 7]], 33]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['b', 1],
['g', 4],
['f', 3],
['g', 1],
['f', 1],
['e', 1],
['g', 3],
['g', 5],
['g', 2],
['a', 4],
['d', 2],
['e', 2],
['d', 3],
['d', 3],
['e', 5]]},
[[['d', 5], ['e', 4], ['g', 11]], 20]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 11]]},
[[['b', 1], ['c', 9]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 5]]},
[[['a', 6], ['b', 1], ['c', 1]], 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 |
|---|---|---|---|
| weighted stream 0 k=2 | [[['a', 14], ['d', 12]], 6] | [[['a', 14], ['d', 12]], 9] | Failed |
| weighted stream 1 k=3 | [[['a', 1], ['c', 4], ['d', 3]], 18] | [[['a', 1], ['c', 4], ['d', 3]], 24] | Failed |
| weighted stream 2 k=2 | [[['c', 21], ['d', 4]], 4] | [[['c', 21], ['d', 4]], 6] | Failed |
| weighted stream 3 k=4 | [[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0] | [[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0] | Passed |
| newcomer fully absorbed | [[['a', 2], ['b', 1]], 6] | [[['a', 2], ['b', 1]], 9] | Failed |
| newcomer survives decrement | [[['b', 1], ['c', 5]], 4] | [[['b', 1], ['c', 5]], 6] | Failed |
| exact capacity | [[['a', 2], ['b', 1], ['c', 1]], 0] | [[['a', 2], ['b', 1], ['c', 1]], 0] | Passed |
SHA-256 / f623d582933971c2801c2e7ada9a85a9d4dbf4aa6cce7d62ee3004c199735eb7
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
C = {}
removed = 0
for item, wt in x['stream']:
if item in C:
C[item] += wt
elif len(C) < k:
C[item] = wt
else:
dec = min(min(C.values()), wt)
for key in list(C):
C[key] -= dec
if C[key] == 0:
del C[key]
wt -= dec
removed += dec
if wt > 0:
C[item] = wt
return [sorted([key, v] for key, v in C.items()), removed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 4],
['c', 1],
['a', 3],
['d', 1],
['d', 3],
['a', 5],
['e', 2],
['d', 3],
['d', 4],
['a', 5],
['a', 4]]},
[[['a', 14], ['d', 12]], 9]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['e', 5],
['c', 5],
['b', 3],
['d', 2],
['c', 2],
['d', 2],
['d', 1],
['c', 3],
['a', 4],
['d', 4],
['f', 1]]},
[[['a', 1], ['c', 4], ['d', 3]], 24]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['d', 2],
['c', 2],
['c', 1],
['c', 4],
['a', 1],
['c', 4],
['d', 4],
['c', 5],
['c', 3],
['c', 4],
['a', 1]]},
[[['c', 21], ['d', 4]], 6]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 5],
['a', 5],
['a', 2],
['a', 3],
['d', 4],
['a', 3],
['e', 4],
['e', 1],
['g', 4],
['g', 1],
['g', 3]]},
[[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 7]]},
[[['b', 1], ['c', 5]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 1]]},
[[['a', 2], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 1],
['e', 5],
['d', 4],
['e', 5],
['b', 1],
['e', 4],
['a', 5],
['b', 3],
['d', 1],
['d', 2],
['e', 1],
['d', 1]]},
[[['d', 2], ['e', 7]], 24]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['c', 2],
['b', 5],
['b', 5],
['c', 1],
['d', 1],
['a', 5],
['c', 2],
['f', 4],
['a', 2],
['f', 5],
['b', 2],
['d', 4]]},
[[['b', 5], ['d', 2], ['f', 3]], 28]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['c', 2],
['d', 2],
['c', 4],
['d', 5],
['d', 1],
['b', 2],
['b', 5],
['c', 3],
['e', 4],
['c', 5],
['e', 3],
['b', 2]]},
[[['c', 4], ['e', 4]], 30]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 2],
['g', 1],
['c', 5],
['a', 3],
['b', 2],
['b', 1],
['d', 3],
['g', 2],
['e', 3],
['b', 4],
['d', 2],
['d', 4]]},
[[['b', 2], ['d', 4], ['e', 1]], 25]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 8]]},
[[['b', 1], ['c', 6]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 2]]},
[[['a', 3], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['c', 3],
['e', 5],
['c', 1],
['a', 2],
['a', 2],
['a', 4],
['c', 3],
['d', 5],
['e', 3],
['a', 1],
['c', 1],
['b', 5],
['d', 1]]},
[[['b', 5], ['d', 1]], 30]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['a', 1],
['e', 4],
['e', 5],
['b', 2],
['f', 3],
['d', 3],
['b', 1],
['b', 1],
['f', 3],
['d', 2],
['c', 3],
['f', 3],
['c', 3]]},
[[['c', 4], ['e', 3], ['f', 3]], 24]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['e', 3],
['a', 1],
['c', 5],
['b', 5],
['c', 3],
['e', 4],
['b', 1],
['a', 5],
['e', 3],
['d', 1],
['e', 1],
['e', 1],
['e', 5]]},
[[['a', 3], ['e', 8]], 27]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 3],
['f', 4],
['e', 4],
['b', 2],
['c', 1],
['g', 1],
['f', 4],
['e', 3],
['a', 1],
['e', 4],
['e', 2],
['b', 2],
['f', 1]]},
[[['a', 2], ['b', 2], ['e', 11], ['f', 7]], 10]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 9]]},
[[['b', 1], ['c', 7]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 3]]},
[[['a', 4], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 3],
['e', 1],
['d', 3],
['c', 1],
['c', 4],
['c', 3],
['e', 5],
['e', 2],
['b', 5],
['a', 2],
['e', 5],
['d', 3],
['a', 1],
['b', 4]]},
[[['b', 3]], 39]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['d', 3],
['a', 5],
['c', 2],
['d', 1],
['b', 2],
['d', 3],
['b', 3],
['d', 4],
['c', 1],
['f', 5],
['d', 1],
['e', 5],
['b', 2],
['d', 3]]},
[[['d', 8], ['e', 3], ['f', 1]], 28]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['c', 5],
['b', 5],
['c', 2],
['c', 5],
['d', 4],
['a', 4],
['b', 4],
['c', 5],
['c', 1],
['e', 2],
['b', 3],
['e', 2],
['b', 3],
['d', 5]]},
[[['c', 3], ['d', 2]], 45]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['b', 5],
['d', 2],
['a', 4],
['f', 3],
['a', 1],
['b', 2],
['g', 1],
['c', 2],
['d', 3],
['d', 5],
['d', 3],
['e', 4],
['c', 3],
['g', 4]]},
[[['b', 1], ['d', 7], ['e', 1], ['g', 3]], 30]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 10]]},
[[['b', 1], ['c', 8]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 4]]},
[[['a', 5], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['b', 4],
['d', 3],
['d', 4],
['e', 4],
['c', 1],
['a', 3],
['b', 2],
['b', 5],
['e', 5],
['e', 1],
['d', 4],
['e', 3],
['c', 3],
['d', 3],
['e', 5]]},
[[['d', 1], ['e', 7]], 42]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['d', 3],
['a', 5],
['b', 5],
['e', 3],
['c', 4],
['d', 4],
['e', 4],
['e', 2],
['b', 4],
['d', 1],
['a', 4],
['b', 3],
['f', 1],
['f', 2],
['d', 4]]},
[[['b', 1], ['d', 4]], 44]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['d', 3],
['a', 5],
['a', 5],
['e', 3],
['b', 4],
['c', 4],
['a', 2],
['e', 1],
['e', 2],
['a', 5],
['e', 1],
['c', 3],
['c', 4],
['c', 1],
['c', 3]]},
[[['a', 6], ['c', 7]], 33]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['b', 1],
['g', 4],
['f', 3],
['g', 1],
['f', 1],
['e', 1],
['g', 3],
['g', 5],
['g', 2],
['a', 4],
['d', 2],
['e', 2],
['d', 3],
['d', 3],
['e', 5]]},
[[['d', 5], ['e', 4], ['g', 11]], 20]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 11]]},
[[['b', 1], ['c', 9]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 5]]},
[[['a', 6], ['b', 1], ['c', 1]], 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 |
|---|---|---|---|
| weighted stream 0 k=2 | [[['a', 14], ['d', 12]], 3] | [[['a', 14], ['d', 12]], 9] | Failed |
| weighted stream 1 k=3 | [[['a', 1], ['c', 4], ['d', 3]], 6] | [[['a', 1], ['c', 4], ['d', 3]], 24] | Failed |
| weighted stream 2 k=2 | [[['c', 21], ['d', 4]], 2] | [[['c', 21], ['d', 4]], 6] | Failed |
| weighted stream 3 k=4 | [[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0] | [[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0] | Passed |
| newcomer fully absorbed | [[['a', 2], ['b', 1]], 3] | [[['a', 2], ['b', 1]], 9] | Failed |
| newcomer survives decrement | [[['b', 1], ['c', 5]], 2] | [[['b', 1], ['c', 5]], 6] | Failed |
| exact capacity | [[['a', 2], ['b', 1], ['c', 1]], 0] | [[['a', 2], ['b', 1], ['c', 1]], 0] | Passed |
SHA-256 / 50bf4a7c4b46d99df958046b9475808893e8e5053bf073a0f91023e85cee4b9f
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
C = {}
removed = 0
for item, wt in x['stream']:
if item in C:
C[item] += wt
elif len(C) < k:
C[item] = wt
else:
dec = min(min(C.values()), wt)
for key in list(C):
C[key] -= dec
if C[key] == 0:
del C[key]
wt -= dec
removed += dec * (k + 1)
if wt > 0:
C[item] = wt
return [sorted([key, v] for key, v in C.items()), removed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 4],
['c', 1],
['a', 3],
['d', 1],
['d', 3],
['a', 5],
['e', 2],
['d', 3],
['d', 4],
['a', 5],
['a', 4]]},
[[['a', 14], ['d', 12]], 9]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['e', 5],
['c', 5],
['b', 3],
['d', 2],
['c', 2],
['d', 2],
['d', 1],
['c', 3],
['a', 4],
['d', 4],
['f', 1]]},
[[['a', 1], ['c', 4], ['d', 3]], 24]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['d', 2],
['c', 2],
['c', 1],
['c', 4],
['a', 1],
['c', 4],
['d', 4],
['c', 5],
['c', 3],
['c', 4],
['a', 1]]},
[[['c', 21], ['d', 4]], 6]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 5],
['a', 5],
['a', 2],
['a', 3],
['d', 4],
['a', 3],
['e', 4],
['e', 1],
['g', 4],
['g', 1],
['g', 3]]},
[[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 7]]},
[[['b', 1], ['c', 5]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 1]]},
[[['a', 2], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 1],
['e', 5],
['d', 4],
['e', 5],
['b', 1],
['e', 4],
['a', 5],
['b', 3],
['d', 1],
['d', 2],
['e', 1],
['d', 1]]},
[[['d', 2], ['e', 7]], 24]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['c', 2],
['b', 5],
['b', 5],
['c', 1],
['d', 1],
['a', 5],
['c', 2],
['f', 4],
['a', 2],
['f', 5],
['b', 2],
['d', 4]]},
[[['b', 5], ['d', 2], ['f', 3]], 28]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['c', 2],
['d', 2],
['c', 4],
['d', 5],
['d', 1],
['b', 2],
['b', 5],
['c', 3],
['e', 4],
['c', 5],
['e', 3],
['b', 2]]},
[[['c', 4], ['e', 4]], 30]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 2],
['g', 1],
['c', 5],
['a', 3],
['b', 2],
['b', 1],
['d', 3],
['g', 2],
['e', 3],
['b', 4],
['d', 2],
['d', 4]]},
[[['b', 2], ['d', 4], ['e', 1]], 25]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 8]]},
[[['b', 1], ['c', 6]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 2]]},
[[['a', 3], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['c', 3],
['e', 5],
['c', 1],
['a', 2],
['a', 2],
['a', 4],
['c', 3],
['d', 5],
['e', 3],
['a', 1],
['c', 1],
['b', 5],
['d', 1]]},
[[['b', 5], ['d', 1]], 30]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['a', 1],
['e', 4],
['e', 5],
['b', 2],
['f', 3],
['d', 3],
['b', 1],
['b', 1],
['f', 3],
['d', 2],
['c', 3],
['f', 3],
['c', 3]]},
[[['c', 4], ['e', 3], ['f', 3]], 24]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['e', 3],
['a', 1],
['c', 5],
['b', 5],
['c', 3],
['e', 4],
['b', 1],
['a', 5],
['e', 3],
['d', 1],
['e', 1],
['e', 1],
['e', 5]]},
[[['a', 3], ['e', 8]], 27]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['a', 3],
['f', 4],
['e', 4],
['b', 2],
['c', 1],
['g', 1],
['f', 4],
['e', 3],
['a', 1],
['e', 4],
['e', 2],
['b', 2],
['f', 1]]},
[[['a', 2], ['b', 2], ['e', 11], ['f', 7]], 10]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 9]]},
[[['b', 1], ['c', 7]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 3]]},
[[['a', 4], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['d', 3],
['e', 1],
['d', 3],
['c', 1],
['c', 4],
['c', 3],
['e', 5],
['e', 2],
['b', 5],
['a', 2],
['e', 5],
['d', 3],
['a', 1],
['b', 4]]},
[[['b', 3]], 39]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['d', 3],
['a', 5],
['c', 2],
['d', 1],
['b', 2],
['d', 3],
['b', 3],
['d', 4],
['c', 1],
['f', 5],
['d', 1],
['e', 5],
['b', 2],
['d', 3]]},
[[['d', 8], ['e', 3], ['f', 1]], 28]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['c', 5],
['b', 5],
['c', 2],
['c', 5],
['d', 4],
['a', 4],
['b', 4],
['c', 5],
['c', 1],
['e', 2],
['b', 3],
['e', 2],
['b', 3],
['d', 5]]},
[[['c', 3], ['d', 2]], 45]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['b', 5],
['d', 2],
['a', 4],
['f', 3],
['a', 1],
['b', 2],
['g', 1],
['c', 2],
['d', 3],
['d', 5],
['d', 3],
['e', 4],
['c', 3],
['g', 4]]},
[[['b', 1], ['d', 7], ['e', 1], ['g', 3]], 30]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 10]]},
[[['b', 1], ['c', 8]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 4]]},
[[['a', 5], ['b', 1], ['c', 1]], 0]]],
[['weighted stream 0 k=2',
{'k': 2,
'stream': [['b', 4],
['d', 3],
['d', 4],
['e', 4],
['c', 1],
['a', 3],
['b', 2],
['b', 5],
['e', 5],
['e', 1],
['d', 4],
['e', 3],
['c', 3],
['d', 3],
['e', 5]]},
[[['d', 1], ['e', 7]], 42]],
['weighted stream 1 k=3',
{'k': 3,
'stream': [['d', 3],
['a', 5],
['b', 5],
['e', 3],
['c', 4],
['d', 4],
['e', 4],
['e', 2],
['b', 4],
['d', 1],
['a', 4],
['b', 3],
['f', 1],
['f', 2],
['d', 4]]},
[[['b', 1], ['d', 4]], 44]],
['weighted stream 2 k=2',
{'k': 2,
'stream': [['d', 3],
['a', 5],
['a', 5],
['e', 3],
['b', 4],
['c', 4],
['a', 2],
['e', 1],
['e', 2],
['a', 5],
['e', 1],
['c', 3],
['c', 4],
['c', 1],
['c', 3]]},
[[['a', 6], ['c', 7]], 33]],
['weighted stream 3 k=4',
{'k': 4,
'stream': [['b', 1],
['g', 4],
['f', 3],
['g', 1],
['f', 1],
['e', 1],
['g', 3],
['g', 5],
['g', 2],
['a', 4],
['d', 2],
['e', 2],
['d', 3],
['d', 3],
['e', 5]]},
[[['d', 5], ['e', 4], ['g', 11]], 20]],
['newcomer fully absorbed',
{'k': 2, 'stream': [['a', 5], ['b', 4], ['c', 3]]},
[[['a', 2], ['b', 1]], 9]],
['newcomer survives decrement',
{'k': 2, 'stream': [['a', 2], ['b', 3], ['c', 11]]},
[[['b', 1], ['c', 9]], 6]],
['exact capacity',
{'k': 3, 'stream': [['a', 1], ['b', 1], ['c', 1], ['a', 5]]},
[[['a', 6], ['b', 1], ['c', 1]], 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 |
|---|---|---|---|
| weighted stream 0 k=2 | [[['a', 14], ['d', 12]], 9] | [[['a', 14], ['d', 12]], 9] | Passed |
| weighted stream 1 k=3 | [[['a', 1], ['c', 4], ['d', 3]], 24] | [[['a', 1], ['c', 4], ['d', 3]], 24] | Passed |
| weighted stream 2 k=2 | [[['c', 21], ['d', 4]], 6] | [[['c', 21], ['d', 4]], 6] | Passed |
| weighted stream 3 k=4 | [[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0] | [[['a', 18], ['d', 4], ['e', 5], ['g', 8]], 0] | Passed |
| newcomer fully absorbed | [[['a', 2], ['b', 1]], 9] | [[['a', 2], ['b', 1]], 9] | Passed |
| newcomer survives decrement | [[['b', 1], ['c', 5]], 6] | [[['b', 1], ['c', 5]], 6] | Passed |
| exact capacity | [[['a', 2], ['b', 1], ['c', 1]], 0] | [[['a', 2], ['b', 1], ['c', 1]], 0] | Passed |
SHA-256 / 0fdc29d94abd088a6de46b49563bf7ebe69dd686782c706b06e1f15ed32c8be9
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:44.458561+00:00.
Case digest / f852acff80bcc94a133ed3f6f7f3d59b67b83d85f2cd7dbd6e62af4cb2a22c96