FA-73166 / Probabilistic sketches / Open access
Weighted reservoir sampling by exponential keys: key raises u to the weight · case 01
Heavier items receive smaller keys and are sampled less often than light ones.
ROOT CAUSE
The key is u^weight instead of u^(1/weight).
VERIFIED REPAIR
Use u^(1/weight), i.e. ln(u)/weight.
Unsuccessful approach: Multiplying u by the weight is a heuristic with the wrong inclusion probabilities.
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(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 | [0, 7] | [2, 7] | Failed |
| weighted sample 1 k=3 | [4, 5, 0] | [7, 4, 0] | Failed |
| weighted sample 2 k=4 | [0, 3, 4, 7] | [7, 6, 0, 1] | Failed |
| zero and negative weights | [4, 3] | [4, 3] | Passed |
| equal keys tie | [3, 7] | [3, 7] | Passed |
| heavier weight wins | [1] | [2] | Failed |
| light weight small uniform | [1, 3] | [3, 2] | Failed |
SHA-256 / 6b2f2dbb6f3d4ba60da1e9a98efe6a2356589468c64263a9f76b89314447f46f
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 = (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, 6] | [2, 7] | Failed |
| weighted sample 1 k=3 | [7, 4, 0] | [7, 4, 0] | Passed |
| weighted sample 2 k=4 | [6, 7, 1, 0] | [7, 6, 0, 1] | Failed |
| 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 | [2, 3] | [3, 2] | Failed |
SHA-256 / c168d7955124c253becea8286718eaef6e2668a1f8305cf9db73ab90771e8b60
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:44.924790+00:00.
Case digest / cd5c0a081c56934aa929240e96540ffbcd2be936b9fcf8ae83ed944fda53673a