FA-73171 / Probabilistic sketches / Open access
Weighted reservoir sampling by exponential keys: keeps the smallest keys · case 01
The sample favours the lightest items.
ROOT CAUSE
The k smallest keys are retained instead of the k largest.
VERIFIED REPAIR
Keep the k largest keys.
Unsuccessful approach: Ranking by the magnitude of the log key selects the smallest keys again.
Case contract
Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.
Why this case matters
Weighted sampling without replacement (A-Res) chooses representative traces or accounts in proportion to traffic; key or eligibility mistakes skew the sample.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
k = x['k']
keyed = []
for ident, wt, num, den in x['items']:
if wt <= 0:
continue
key = math.log(num / den) / wt
keyed.append((key, -ident))
keyed.sort()
return [-negid for key, negid in keyed[:k]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted sample 0 k=2',
{'items': [[0, 0.5, 91, 99],
[1, 1, 42, 99],
[2, 5, 91, 99],
[3, 0.5, 48, 99],
[4, 0.5, 13, 99],
[5, 3, 4, 99],
[6, 3, 63, 99],
[7, 2, 87, 99]],
'k': 2},
[2, 7]],
['weighted sample 1 k=3',
{'items': [[0, 1, 65, 99],
[1, 0.5, 34, 99],
[2, 2, 22, 99],
[3, 1, 43, 99],
[4, 1, 77, 99],
[5, 0.5, 50, 99],
[6, 5, 2, 99],
[7, 3, 76, 99]],
'k': 3},
[7, 4, 0]],
['weighted sample 2 k=4',
{'items': [[0, 1, 74, 99],
[1, 3, 25, 99],
[2, 3, 5, 99],
[3, 0.5, 53, 99],
[4, 1, 61, 99],
[5, 1, 6, 99],
[6, 5, 34, 99],
[7, 3, 56, 99]],
'k': 4},
[7, 6, 0, 1]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 41, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 11, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 21, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 31, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 8, 99],
[1, 5, 66, 99],
[2, 5, 27, 99],
[3, 5, 16, 99],
[4, 0.5, 70, 99],
[5, 3, 4, 99],
[6, 0.5, 5, 99],
[7, 0.5, 32, 99]],
'k': 2},
[1, 2]],
['weighted sample 1 k=3',
{'items': [[0, 0.5, 34, 99],
[1, 0.5, 41, 99],
[2, 5, 97, 99],
[3, 3, 35, 99],
[4, 3, 98, 99],
[5, 3, 86, 99],
[6, 0.5, 26, 99],
[7, 1, 66, 99]],
'k': 3},
[4, 2, 5]],
['weighted sample 2 k=4',
{'items': [[0, 2, 63, 99],
[1, 5, 82, 99],
[2, 0.5, 17, 99],
[3, 3, 50, 99],
[4, 3, 90, 99],
[5, 5, 18, 99],
[6, 1, 85, 99],
[7, 1, 8, 99]],
'k': 4},
[4, 1, 6, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 42, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 12, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 22, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 32, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 2, 38, 99],
[1, 2, 4, 99],
[2, 5, 4, 99],
[3, 5, 92, 99],
[4, 5, 71, 99],
[5, 1, 36, 99],
[6, 2, 24, 99],
[7, 3, 79, 99]],
'k': 2},
[3, 4]],
['weighted sample 1 k=3',
{'items': [[0, 1, 74, 99],
[1, 5, 71, 99],
[2, 3, 25, 99],
[3, 0.5, 97, 99],
[4, 5, 51, 99],
[5, 1, 86, 99],
[6, 1, 82, 99],
[7, 5, 81, 99]],
'k': 3},
[7, 3, 1]],
['weighted sample 2 k=4',
{'items': [[0, 5, 98, 99],
[1, 2, 23, 99],
[2, 5, 17, 99],
[3, 2, 35, 99],
[4, 0.5, 16, 99],
[5, 3, 77, 99],
[6, 3, 56, 99],
[7, 0.5, 87, 99]],
'k': 4},
[0, 5, 6, 7]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 43, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 13, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 23, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 33, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 5, 55, 99],
[1, 2, 83, 99],
[2, 2, 87, 99],
[3, 3, 17, 99],
[4, 1, 74, 99],
[5, 0.5, 82, 99],
[6, 2, 71, 99],
[7, 1, 7, 99]],
'k': 2},
[2, 1]],
['weighted sample 1 k=3',
{'items': [[0, 1, 55, 99],
[1, 1, 50, 99],
[2, 2, 55, 99],
[3, 1, 34, 99],
[4, 1, 58, 99],
[5, 3, 47, 99],
[6, 0.5, 66, 99],
[7, 2, 69, 99]],
'k': 3},
[7, 5, 2]],
['weighted sample 2 k=4',
{'items': [[0, 3, 42, 99],
[1, 0.5, 69, 99],
[2, 3, 41, 99],
[3, 0.5, 42, 99],
[4, 2, 48, 99],
[5, 5, 91, 99],
[6, 5, 74, 99],
[7, 3, 31, 99]],
'k': 4},
[5, 6, 0, 2]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 44, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 14, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 24, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 34, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 87, 99],
[1, 1, 1, 99],
[2, 2, 6, 99],
[3, 5, 67, 99],
[4, 1, 66, 99],
[5, 3, 45, 99],
[6, 0.5, 25, 99],
[7, 1, 41, 99]],
'k': 2},
[3, 0]],
['weighted sample 1 k=3',
{'items': [[0, 1, 25, 99],
[1, 3, 18, 99],
[2, 5, 2, 99],
[3, 2, 65, 99],
[4, 3, 14, 99],
[5, 3, 89, 99],
[6, 3, 10, 99],
[7, 1, 78, 99]],
'k': 3},
[5, 3, 7]],
['weighted sample 2 k=4',
{'items': [[0, 2, 49, 99],
[1, 2, 66, 99],
[2, 0.5, 24, 99],
[3, 0.5, 88, 99],
[4, 1, 6, 99],
[5, 1, 8, 99],
[6, 1, 93, 99],
[7, 0.5, 41, 99]],
'k': 4},
[6, 1, 3, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 45, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 15, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 25, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 35, 100], [3, 1, 70, 100]], 'k': 2},
[2, 3]]]]
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 sample 0 k=2 | [4, 3] | [2, 7] | Failed |
| weighted sample 1 k=3 | [1, 5, 3] | [7, 4, 0] | Failed |
| weighted sample 2 k=4 | [5, 3, 2, 4] | [7, 6, 0, 1] | Failed |
| zero and negative weights | [3, 4] | [4, 3] | Failed |
| equal keys tie | [5, 7] | [3, 7] | Failed |
| heavier weight wins | [1] | [2] | Failed |
| light weight small uniform | [1, 2] | [3, 2] | Failed |
SHA-256 / bec4411978783004dc2c5c1c0d209cbbd16504fa56c955dc1ddd60d921a2b951
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
k = x['k']
keyed = []
for ident, wt, num, den in x['items']:
if wt <= 0:
continue
key = math.log(num / den) / wt
keyed.append((key, -ident))
keyed.sort(key=lambda kv: abs(kv[0]), reverse=True)
return [-negid for key, negid in keyed[:k]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted sample 0 k=2',
{'items': [[0, 0.5, 91, 99],
[1, 1, 42, 99],
[2, 5, 91, 99],
[3, 0.5, 48, 99],
[4, 0.5, 13, 99],
[5, 3, 4, 99],
[6, 3, 63, 99],
[7, 2, 87, 99]],
'k': 2},
[2, 7]],
['weighted sample 1 k=3',
{'items': [[0, 1, 65, 99],
[1, 0.5, 34, 99],
[2, 2, 22, 99],
[3, 1, 43, 99],
[4, 1, 77, 99],
[5, 0.5, 50, 99],
[6, 5, 2, 99],
[7, 3, 76, 99]],
'k': 3},
[7, 4, 0]],
['weighted sample 2 k=4',
{'items': [[0, 1, 74, 99],
[1, 3, 25, 99],
[2, 3, 5, 99],
[3, 0.5, 53, 99],
[4, 1, 61, 99],
[5, 1, 6, 99],
[6, 5, 34, 99],
[7, 3, 56, 99]],
'k': 4},
[7, 6, 0, 1]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 41, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 11, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 21, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 31, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 8, 99],
[1, 5, 66, 99],
[2, 5, 27, 99],
[3, 5, 16, 99],
[4, 0.5, 70, 99],
[5, 3, 4, 99],
[6, 0.5, 5, 99],
[7, 0.5, 32, 99]],
'k': 2},
[1, 2]],
['weighted sample 1 k=3',
{'items': [[0, 0.5, 34, 99],
[1, 0.5, 41, 99],
[2, 5, 97, 99],
[3, 3, 35, 99],
[4, 3, 98, 99],
[5, 3, 86, 99],
[6, 0.5, 26, 99],
[7, 1, 66, 99]],
'k': 3},
[4, 2, 5]],
['weighted sample 2 k=4',
{'items': [[0, 2, 63, 99],
[1, 5, 82, 99],
[2, 0.5, 17, 99],
[3, 3, 50, 99],
[4, 3, 90, 99],
[5, 5, 18, 99],
[6, 1, 85, 99],
[7, 1, 8, 99]],
'k': 4},
[4, 1, 6, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 42, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 12, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 22, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 32, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 2, 38, 99],
[1, 2, 4, 99],
[2, 5, 4, 99],
[3, 5, 92, 99],
[4, 5, 71, 99],
[5, 1, 36, 99],
[6, 2, 24, 99],
[7, 3, 79, 99]],
'k': 2},
[3, 4]],
['weighted sample 1 k=3',
{'items': [[0, 1, 74, 99],
[1, 5, 71, 99],
[2, 3, 25, 99],
[3, 0.5, 97, 99],
[4, 5, 51, 99],
[5, 1, 86, 99],
[6, 1, 82, 99],
[7, 5, 81, 99]],
'k': 3},
[7, 3, 1]],
['weighted sample 2 k=4',
{'items': [[0, 5, 98, 99],
[1, 2, 23, 99],
[2, 5, 17, 99],
[3, 2, 35, 99],
[4, 0.5, 16, 99],
[5, 3, 77, 99],
[6, 3, 56, 99],
[7, 0.5, 87, 99]],
'k': 4},
[0, 5, 6, 7]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 43, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 13, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 23, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 33, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 5, 55, 99],
[1, 2, 83, 99],
[2, 2, 87, 99],
[3, 3, 17, 99],
[4, 1, 74, 99],
[5, 0.5, 82, 99],
[6, 2, 71, 99],
[7, 1, 7, 99]],
'k': 2},
[2, 1]],
['weighted sample 1 k=3',
{'items': [[0, 1, 55, 99],
[1, 1, 50, 99],
[2, 2, 55, 99],
[3, 1, 34, 99],
[4, 1, 58, 99],
[5, 3, 47, 99],
[6, 0.5, 66, 99],
[7, 2, 69, 99]],
'k': 3},
[7, 5, 2]],
['weighted sample 2 k=4',
{'items': [[0, 3, 42, 99],
[1, 0.5, 69, 99],
[2, 3, 41, 99],
[3, 0.5, 42, 99],
[4, 2, 48, 99],
[5, 5, 91, 99],
[6, 5, 74, 99],
[7, 3, 31, 99]],
'k': 4},
[5, 6, 0, 2]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 44, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 14, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 24, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 34, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 87, 99],
[1, 1, 1, 99],
[2, 2, 6, 99],
[3, 5, 67, 99],
[4, 1, 66, 99],
[5, 3, 45, 99],
[6, 0.5, 25, 99],
[7, 1, 41, 99]],
'k': 2},
[3, 0]],
['weighted sample 1 k=3',
{'items': [[0, 1, 25, 99],
[1, 3, 18, 99],
[2, 5, 2, 99],
[3, 2, 65, 99],
[4, 3, 14, 99],
[5, 3, 89, 99],
[6, 3, 10, 99],
[7, 1, 78, 99]],
'k': 3},
[5, 3, 7]],
['weighted sample 2 k=4',
{'items': [[0, 2, 49, 99],
[1, 2, 66, 99],
[2, 0.5, 24, 99],
[3, 0.5, 88, 99],
[4, 1, 6, 99],
[5, 1, 8, 99],
[6, 1, 93, 99],
[7, 0.5, 41, 99]],
'k': 4},
[6, 1, 3, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 45, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 15, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 25, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 35, 100], [3, 1, 70, 100]], 'k': 2},
[2, 3]]]]
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 sample 0 k=2 | [4, 3] | [2, 7] | Failed |
| weighted sample 1 k=3 | [1, 5, 3] | [7, 4, 0] | Failed |
| weighted sample 2 k=4 | [5, 3, 2, 4] | [7, 6, 0, 1] | Failed |
| zero and negative weights | [3, 4] | [4, 3] | Failed |
| equal keys tie | [5, 7] | [3, 7] | Failed |
| heavier weight wins | [1] | [2] | Failed |
| light weight small uniform | [1, 2] | [3, 2] | Failed |
SHA-256 / 83137e6e4f52356d623d23f1875b327eeeab73e03c15ac6bae93c4ace2bc54c2
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
k = x['k']
keyed = []
for ident, wt, num, den in x['items']:
if wt <= 0:
continue
key = math.log(num / den) / wt
keyed.append((key, -ident))
keyed.sort(reverse=True)
return [-negid for key, negid in keyed[:k]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted sample 0 k=2',
{'items': [[0, 0.5, 91, 99],
[1, 1, 42, 99],
[2, 5, 91, 99],
[3, 0.5, 48, 99],
[4, 0.5, 13, 99],
[5, 3, 4, 99],
[6, 3, 63, 99],
[7, 2, 87, 99]],
'k': 2},
[2, 7]],
['weighted sample 1 k=3',
{'items': [[0, 1, 65, 99],
[1, 0.5, 34, 99],
[2, 2, 22, 99],
[3, 1, 43, 99],
[4, 1, 77, 99],
[5, 0.5, 50, 99],
[6, 5, 2, 99],
[7, 3, 76, 99]],
'k': 3},
[7, 4, 0]],
['weighted sample 2 k=4',
{'items': [[0, 1, 74, 99],
[1, 3, 25, 99],
[2, 3, 5, 99],
[3, 0.5, 53, 99],
[4, 1, 61, 99],
[5, 1, 6, 99],
[6, 5, 34, 99],
[7, 3, 56, 99]],
'k': 4},
[7, 6, 0, 1]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 41, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 11, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 21, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 31, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 8, 99],
[1, 5, 66, 99],
[2, 5, 27, 99],
[3, 5, 16, 99],
[4, 0.5, 70, 99],
[5, 3, 4, 99],
[6, 0.5, 5, 99],
[7, 0.5, 32, 99]],
'k': 2},
[1, 2]],
['weighted sample 1 k=3',
{'items': [[0, 0.5, 34, 99],
[1, 0.5, 41, 99],
[2, 5, 97, 99],
[3, 3, 35, 99],
[4, 3, 98, 99],
[5, 3, 86, 99],
[6, 0.5, 26, 99],
[7, 1, 66, 99]],
'k': 3},
[4, 2, 5]],
['weighted sample 2 k=4',
{'items': [[0, 2, 63, 99],
[1, 5, 82, 99],
[2, 0.5, 17, 99],
[3, 3, 50, 99],
[4, 3, 90, 99],
[5, 5, 18, 99],
[6, 1, 85, 99],
[7, 1, 8, 99]],
'k': 4},
[4, 1, 6, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 42, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 12, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 22, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 32, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 2, 38, 99],
[1, 2, 4, 99],
[2, 5, 4, 99],
[3, 5, 92, 99],
[4, 5, 71, 99],
[5, 1, 36, 99],
[6, 2, 24, 99],
[7, 3, 79, 99]],
'k': 2},
[3, 4]],
['weighted sample 1 k=3',
{'items': [[0, 1, 74, 99],
[1, 5, 71, 99],
[2, 3, 25, 99],
[3, 0.5, 97, 99],
[4, 5, 51, 99],
[5, 1, 86, 99],
[6, 1, 82, 99],
[7, 5, 81, 99]],
'k': 3},
[7, 3, 1]],
['weighted sample 2 k=4',
{'items': [[0, 5, 98, 99],
[1, 2, 23, 99],
[2, 5, 17, 99],
[3, 2, 35, 99],
[4, 0.5, 16, 99],
[5, 3, 77, 99],
[6, 3, 56, 99],
[7, 0.5, 87, 99]],
'k': 4},
[0, 5, 6, 7]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 43, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 13, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 23, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 33, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 5, 55, 99],
[1, 2, 83, 99],
[2, 2, 87, 99],
[3, 3, 17, 99],
[4, 1, 74, 99],
[5, 0.5, 82, 99],
[6, 2, 71, 99],
[7, 1, 7, 99]],
'k': 2},
[2, 1]],
['weighted sample 1 k=3',
{'items': [[0, 1, 55, 99],
[1, 1, 50, 99],
[2, 2, 55, 99],
[3, 1, 34, 99],
[4, 1, 58, 99],
[5, 3, 47, 99],
[6, 0.5, 66, 99],
[7, 2, 69, 99]],
'k': 3},
[7, 5, 2]],
['weighted sample 2 k=4',
{'items': [[0, 3, 42, 99],
[1, 0.5, 69, 99],
[2, 3, 41, 99],
[3, 0.5, 42, 99],
[4, 2, 48, 99],
[5, 5, 91, 99],
[6, 5, 74, 99],
[7, 3, 31, 99]],
'k': 4},
[5, 6, 0, 2]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 44, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 14, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 24, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 34, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 87, 99],
[1, 1, 1, 99],
[2, 2, 6, 99],
[3, 5, 67, 99],
[4, 1, 66, 99],
[5, 3, 45, 99],
[6, 0.5, 25, 99],
[7, 1, 41, 99]],
'k': 2},
[3, 0]],
['weighted sample 1 k=3',
{'items': [[0, 1, 25, 99],
[1, 3, 18, 99],
[2, 5, 2, 99],
[3, 2, 65, 99],
[4, 3, 14, 99],
[5, 3, 89, 99],
[6, 3, 10, 99],
[7, 1, 78, 99]],
'k': 3},
[5, 3, 7]],
['weighted sample 2 k=4',
{'items': [[0, 2, 49, 99],
[1, 2, 66, 99],
[2, 0.5, 24, 99],
[3, 0.5, 88, 99],
[4, 1, 6, 99],
[5, 1, 8, 99],
[6, 1, 93, 99],
[7, 0.5, 41, 99]],
'k': 4},
[6, 1, 3, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 45, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 15, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 25, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 35, 100], [3, 1, 70, 100]], 'k': 2},
[2, 3]]]]
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 sample 0 k=2 | [2, 7] | [2, 7] | Passed |
| weighted sample 1 k=3 | [7, 4, 0] | [7, 4, 0] | Passed |
| weighted sample 2 k=4 | [7, 6, 0, 1] | [7, 6, 0, 1] | Passed |
| zero and negative weights | [4, 3] | [4, 3] | Passed |
| equal keys tie | [3, 7] | [3, 7] | Passed |
| heavier weight wins | [2] | [2] | Passed |
| light weight small uniform | [3, 2] | [3, 2] | Passed |
SHA-256 / 258ac424db1b6b4e7c70eee463ec0fe659d88534f1c2d31dfd76d70200b5f4ae
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:45.055218+00:00.
Case digest / c69234ea73e9e8d746a3683b54f2874e3516e160e949de60e46516d8fe2c95c1