FA-73146 / Probabilistic sketches / Open access
Reservoir sampling (Algorithm R) with supplied draws: replacement range excludes the current item · case 01
Later items are over-sampled because the acceptance probability is k/i instead of k/(i+1).
ROOT CAUSE
The draw is reduced modulo i, the count of earlier items, instead of i + 1.
VERIFIED REPAIR
Reduce the draw modulo i + 1.
Unsuccessful approach: Reducing modulo i + 2 under-samples later items instead.
Case contract
Input {k, items, draws}. The first k items fill the reservoir. For 0-based index i >= k the draw draws[i - k] gives j = draw mod (i + 1); when j < k slot j is replaced. Exactly one draw is consumed per item after the fill phase. Return the reservoir.
Why this case matters
Uniform stream samples feed audit logs and A/B diagnostics; any skew in the replacement rule biases the sample toward early or late events.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
items = x['items']
draws = x['draws']
res = []
for i, item in enumerate(items):
if i < k:
res.append(item)
else:
j = draws[i - k] % i
if j < k:
res[j] = item
return res
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['reservoir 0 k=3',
{'draws': [503, 385, 476, 488, 606, 108, 252, 164, 59, 250, 942, 523, 165, 983],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e8', 'e1', 'e9']],
['reservoir 1 k=2',
{'draws': [878, 281, 618, 928, 879, 391, 183, 62, 660, 169, 814],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e0', 'e3']],
['reservoir 2 k=4',
{'draws': [727, 622, 213, 583, 893, 937, 186, 620, 217, 656, 799, 958, 803, 920, 178, 243, 305],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e1', 'e8', 'e6']],
['reservoir 3 k=1',
{'draws': [611, 696, 835, 229, 731, 995, 790, 117, 923, 647],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e2']],
['reservoir 4 k=5',
{'draws': [510, 183, 524, 267, 413, 746, 732, 203, 700, 240, 732, 908, 296],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e5', 'e6', 'e2', 'e9', 'e7']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]],
[['reservoir 0 k=3',
{'draws': [429, 197, 290, 177, 971, 131, 62, 409, 364, 17, 814, 582, 979, 710],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e0', 'e3', 'e10']],
['reservoir 1 k=2',
{'draws': [618, 258, 338, 126, 358, 919, 861, 857, 443, 291, 148],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e5', 'e6']],
['reservoir 2 k=4',
{'draws': [106, 978, 558, 741, 260, 124, 968, 5, 740, 138, 214, 818, 130, 716, 684, 510, 645],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e10', 'e4', 'e2', 'e3']],
['reservoir 3 k=1',
{'draws': [638, 208, 553, 430, 153, 336, 213, 400, 598, 60],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e6']],
['reservoir 4 k=5',
{'draws': [5, 641, 334, 585, 354, 584, 201, 141, 682, 953, 308, 604, 445],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e8', 'e10', 'e2', 'e3', 'e9']],
['shorter than reservoir',
{'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},
['a', 'b', 'c']],
['crafted replacements',
{'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['e', 'c']]],
[['reservoir 0 k=3',
{'draws': [533, 409, 869, 398, 863, 761, 203, 237, 12, 354, 244, 883, 829, 798],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e11', 'e3', 'e2']],
['reservoir 1 k=2',
{'draws': [264, 40, 302, 942, 526, 53, 293, 784, 595, 721, 162],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e5', 'e6']],
['reservoir 2 k=4',
{'draws': [693, 14, 13, 722, 904, 717, 916, 354, 489, 959, 175, 892, 551, 857, 45, 179, 406],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e1', 'e7', 'e10']],
['reservoir 3 k=1',
{'draws': [348, 426, 687, 856, 902, 812, 612, 255, 545, 118],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e6']],
['reservoir 4 k=5',
{'draws': [384, 350, 593, 569, 642, 244, 923, 625, 358, 272, 497, 854, 402],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e6', 'e7', 'e10', 'e3', 'e4']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a'], 'k': 6}, ['a']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]],
[['reservoir 0 k=3',
{'draws': [538, 676, 232, 616, 107, 792, 778, 632, 710, 421, 135, 166, 239, 112],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e8', 'e4', 'e11']],
['reservoir 1 k=2',
{'draws': [943, 565, 900, 590, 917, 577, 294, 93, 35, 597, 462],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e6', 'e7']],
['reservoir 2 k=4',
{'draws': [101, 66, 640, 194, 962, 859, 108, 424, 866, 554, 146, 488, 486, 353, 692, 626, 747],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e5', 'e4', 'e7', 'e6']],
['reservoir 3 k=1',
{'draws': [507, 631, 535, 543, 801, 706, 895, 467, 252, 805],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e0']],
['reservoir 4 k=5',
{'draws': [631, 754, 93, 424, 593, 884, 850, 592, 410, 243, 577, 561, 1],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e0', 'e8', 'e2', 'e9', 'e10']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],
['crafted replacements',
{'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['e', 'c']]],
[['reservoir 0 k=3',
{'draws': [762, 620, 944, 96, 862, 52, 508, 532, 910, 706, 83, 2, 430, 802],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e4', 'e1', 'e5']],
['reservoir 1 k=2',
{'draws': [760, 573, 571, 862, 815, 852, 887, 584, 98, 704, 573],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e0', 'e4']],
['reservoir 2 k=4',
{'draws': [902, 434, 254, 114, 573, 476, 133, 547, 752, 830, 136, 186, 358, 553, 804, 564, 334],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e14', 'e7', 'e3']],
['reservoir 3 k=1',
{'draws': [78, 337, 584, 508, 238, 901, 332, 921, 804, 16],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e3']],
['reservoir 4 k=5',
{'draws': [65, 631, 860, 551, 878, 731, 235, 935, 569, 319, 581, 993, 213],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e0', 'e6', 'e8', 'e3', 'e7']],
['shorter than reservoir',
{'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},
['a', 'b', 'c']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]]]
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 |
|---|---|---|---|
| reservoir 0 k=3 | ['e9', 'e5', 'e6'] | ['e8', 'e1', 'e9'] | Failed |
| reservoir 1 k=2 | ['e2', 'e1'] | ['e0', 'e3'] | Failed |
| reservoir 2 k=4 | ['e0', 'e14', 'e7', 'e6'] | ['e0', 'e1', 'e8', 'e6'] | Failed |
| reservoir 3 k=1 | ['e2'] | ['e2'] | Passed |
| reservoir 4 k=5 | ['e5', 'e1', 'e2', 'e8', 'e4'] | ['e5', 'e6', 'e2', 'e9', 'e7'] | Failed |
| shorter than reservoir | ['a', 'b'] | ['a', 'b'] | Passed |
| crafted replacements | ['d', 'e'] | ['a', 'e'] | Failed |
SHA-256 / 6db6ed1babb4ca2cb3a40b571f98cf2c38f4f0e463b26cb41b417872eb95cbaf
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']
items = x['items']
draws = x['draws']
res = []
for i, item in enumerate(items):
if i < k:
res.append(item)
else:
j = draws[i - k] % (i + 2)
if j < k:
res[j] = item
return res
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['reservoir 0 k=3',
{'draws': [503, 385, 476, 488, 606, 108, 252, 164, 59, 250, 942, 523, 165, 983],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e8', 'e1', 'e9']],
['reservoir 1 k=2',
{'draws': [878, 281, 618, 928, 879, 391, 183, 62, 660, 169, 814],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e0', 'e3']],
['reservoir 2 k=4',
{'draws': [727, 622, 213, 583, 893, 937, 186, 620, 217, 656, 799, 958, 803, 920, 178, 243, 305],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e1', 'e8', 'e6']],
['reservoir 3 k=1',
{'draws': [611, 696, 835, 229, 731, 995, 790, 117, 923, 647],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e2']],
['reservoir 4 k=5',
{'draws': [510, 183, 524, 267, 413, 746, 732, 203, 700, 240, 732, 908, 296],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e5', 'e6', 'e2', 'e9', 'e7']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]],
[['reservoir 0 k=3',
{'draws': [429, 197, 290, 177, 971, 131, 62, 409, 364, 17, 814, 582, 979, 710],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e0', 'e3', 'e10']],
['reservoir 1 k=2',
{'draws': [618, 258, 338, 126, 358, 919, 861, 857, 443, 291, 148],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e5', 'e6']],
['reservoir 2 k=4',
{'draws': [106, 978, 558, 741, 260, 124, 968, 5, 740, 138, 214, 818, 130, 716, 684, 510, 645],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e10', 'e4', 'e2', 'e3']],
['reservoir 3 k=1',
{'draws': [638, 208, 553, 430, 153, 336, 213, 400, 598, 60],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e6']],
['reservoir 4 k=5',
{'draws': [5, 641, 334, 585, 354, 584, 201, 141, 682, 953, 308, 604, 445],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e8', 'e10', 'e2', 'e3', 'e9']],
['shorter than reservoir',
{'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},
['a', 'b', 'c']],
['crafted replacements',
{'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['e', 'c']]],
[['reservoir 0 k=3',
{'draws': [533, 409, 869, 398, 863, 761, 203, 237, 12, 354, 244, 883, 829, 798],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e11', 'e3', 'e2']],
['reservoir 1 k=2',
{'draws': [264, 40, 302, 942, 526, 53, 293, 784, 595, 721, 162],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e5', 'e6']],
['reservoir 2 k=4',
{'draws': [693, 14, 13, 722, 904, 717, 916, 354, 489, 959, 175, 892, 551, 857, 45, 179, 406],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e1', 'e7', 'e10']],
['reservoir 3 k=1',
{'draws': [348, 426, 687, 856, 902, 812, 612, 255, 545, 118],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e6']],
['reservoir 4 k=5',
{'draws': [384, 350, 593, 569, 642, 244, 923, 625, 358, 272, 497, 854, 402],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e6', 'e7', 'e10', 'e3', 'e4']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a'], 'k': 6}, ['a']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]],
[['reservoir 0 k=3',
{'draws': [538, 676, 232, 616, 107, 792, 778, 632, 710, 421, 135, 166, 239, 112],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e8', 'e4', 'e11']],
['reservoir 1 k=2',
{'draws': [943, 565, 900, 590, 917, 577, 294, 93, 35, 597, 462],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e6', 'e7']],
['reservoir 2 k=4',
{'draws': [101, 66, 640, 194, 962, 859, 108, 424, 866, 554, 146, 488, 486, 353, 692, 626, 747],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e5', 'e4', 'e7', 'e6']],
['reservoir 3 k=1',
{'draws': [507, 631, 535, 543, 801, 706, 895, 467, 252, 805],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e0']],
['reservoir 4 k=5',
{'draws': [631, 754, 93, 424, 593, 884, 850, 592, 410, 243, 577, 561, 1],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e0', 'e8', 'e2', 'e9', 'e10']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],
['crafted replacements',
{'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['e', 'c']]],
[['reservoir 0 k=3',
{'draws': [762, 620, 944, 96, 862, 52, 508, 532, 910, 706, 83, 2, 430, 802],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e4', 'e1', 'e5']],
['reservoir 1 k=2',
{'draws': [760, 573, 571, 862, 815, 852, 887, 584, 98, 704, 573],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e0', 'e4']],
['reservoir 2 k=4',
{'draws': [902, 434, 254, 114, 573, 476, 133, 547, 752, 830, 136, 186, 358, 553, 804, 564, 334],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e14', 'e7', 'e3']],
['reservoir 3 k=1',
{'draws': [78, 337, 584, 508, 238, 901, 332, 921, 804, 16],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e3']],
['reservoir 4 k=5',
{'draws': [65, 631, 860, 551, 878, 731, 235, 935, 569, 319, 581, 993, 213],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e0', 'e6', 'e8', 'e3', 'e7']],
['shorter than reservoir',
{'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},
['a', 'b', 'c']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]]]
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 |
|---|---|---|---|
| reservoir 0 k=3 | ['e6', 'e4', 'e2'] | ['e8', 'e1', 'e9'] | Failed |
| reservoir 1 k=2 | ['e4', 'e3'] | ['e0', 'e3'] | Failed |
| reservoir 2 k=4 | ['e0', 'e4', 'e9', 'e8'] | ['e0', 'e1', 'e8', 'e6'] | Failed |
| reservoir 3 k=1 | ['e3'] | ['e2'] | Failed |
| reservoir 4 k=5 | ['e0', 'e1', 'e10', 'e3', 'e4'] | ['e5', 'e6', 'e2', 'e9', 'e7'] | Failed |
| shorter than reservoir | ['a', 'b'] | ['a', 'b'] | Passed |
| crafted replacements | ['a', 'e'] | ['a', 'e'] | Passed |
SHA-256 / 910f1d90fc41c74b9360755876c704f9ec86475ec03158ff11cde82c338382f1
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']
items = x['items']
draws = x['draws']
res = []
for i, item in enumerate(items):
if i < k:
res.append(item)
else:
j = draws[i - k] % (i + 1)
if j < k:
res[j] = item
return res
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['reservoir 0 k=3',
{'draws': [503, 385, 476, 488, 606, 108, 252, 164, 59, 250, 942, 523, 165, 983],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e8', 'e1', 'e9']],
['reservoir 1 k=2',
{'draws': [878, 281, 618, 928, 879, 391, 183, 62, 660, 169, 814],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e0', 'e3']],
['reservoir 2 k=4',
{'draws': [727, 622, 213, 583, 893, 937, 186, 620, 217, 656, 799, 958, 803, 920, 178, 243, 305],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e1', 'e8', 'e6']],
['reservoir 3 k=1',
{'draws': [611, 696, 835, 229, 731, 995, 790, 117, 923, 647],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e2']],
['reservoir 4 k=5',
{'draws': [510, 183, 524, 267, 413, 746, 732, 203, 700, 240, 732, 908, 296],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e5', 'e6', 'e2', 'e9', 'e7']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]],
[['reservoir 0 k=3',
{'draws': [429, 197, 290, 177, 971, 131, 62, 409, 364, 17, 814, 582, 979, 710],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e0', 'e3', 'e10']],
['reservoir 1 k=2',
{'draws': [618, 258, 338, 126, 358, 919, 861, 857, 443, 291, 148],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e5', 'e6']],
['reservoir 2 k=4',
{'draws': [106, 978, 558, 741, 260, 124, 968, 5, 740, 138, 214, 818, 130, 716, 684, 510, 645],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e10', 'e4', 'e2', 'e3']],
['reservoir 3 k=1',
{'draws': [638, 208, 553, 430, 153, 336, 213, 400, 598, 60],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e6']],
['reservoir 4 k=5',
{'draws': [5, 641, 334, 585, 354, 584, 201, 141, 682, 953, 308, 604, 445],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e8', 'e10', 'e2', 'e3', 'e9']],
['shorter than reservoir',
{'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},
['a', 'b', 'c']],
['crafted replacements',
{'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['e', 'c']]],
[['reservoir 0 k=3',
{'draws': [533, 409, 869, 398, 863, 761, 203, 237, 12, 354, 244, 883, 829, 798],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e11', 'e3', 'e2']],
['reservoir 1 k=2',
{'draws': [264, 40, 302, 942, 526, 53, 293, 784, 595, 721, 162],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e5', 'e6']],
['reservoir 2 k=4',
{'draws': [693, 14, 13, 722, 904, 717, 916, 354, 489, 959, 175, 892, 551, 857, 45, 179, 406],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e1', 'e7', 'e10']],
['reservoir 3 k=1',
{'draws': [348, 426, 687, 856, 902, 812, 612, 255, 545, 118],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e6']],
['reservoir 4 k=5',
{'draws': [384, 350, 593, 569, 642, 244, 923, 625, 358, 272, 497, 854, 402],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e6', 'e7', 'e10', 'e3', 'e4']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a'], 'k': 6}, ['a']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]],
[['reservoir 0 k=3',
{'draws': [538, 676, 232, 616, 107, 792, 778, 632, 710, 421, 135, 166, 239, 112],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e8', 'e4', 'e11']],
['reservoir 1 k=2',
{'draws': [943, 565, 900, 590, 917, 577, 294, 93, 35, 597, 462],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e6', 'e7']],
['reservoir 2 k=4',
{'draws': [101, 66, 640, 194, 962, 859, 108, 424, 866, 554, 146, 488, 486, 353, 692, 626, 747],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e5', 'e4', 'e7', 'e6']],
['reservoir 3 k=1',
{'draws': [507, 631, 535, 543, 801, 706, 895, 467, 252, 805],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e0']],
['reservoir 4 k=5',
{'draws': [631, 754, 93, 424, 593, 884, 850, 592, 410, 243, 577, 561, 1],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e0', 'e8', 'e2', 'e9', 'e10']],
['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],
['crafted replacements',
{'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['e', 'c']]],
[['reservoir 0 k=3',
{'draws': [762, 620, 944, 96, 862, 52, 508, 532, 910, 706, 83, 2, 430, 802],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],
'k': 3},
['e4', 'e1', 'e5']],
['reservoir 1 k=2',
{'draws': [760, 573, 571, 862, 815, 852, 887, 584, 98, 704, 573],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],
'k': 2},
['e0', 'e4']],
['reservoir 2 k=4',
{'draws': [902, 434, 254, 114, 573, 476, 133, 547, 752, 830, 136, 186, 358, 553, 804, 564, 334],
'items': ['e0',
'e1',
'e2',
'e3',
'e4',
'e5',
'e6',
'e7',
'e8',
'e9',
'e10',
'e11',
'e12',
'e13',
'e14'],
'k': 4},
['e0', 'e14', 'e7', 'e3']],
['reservoir 3 k=1',
{'draws': [78, 337, 584, 508, 238, 901, 332, 921, 804, 16],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],
'k': 1},
['e3']],
['reservoir 4 k=5',
{'draws': [65, 631, 860, 551, 878, 731, 235, 935, 569, 319, 581, 993, 213],
'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],
'k': 5},
['e0', 'e6', 'e8', 'e3', 'e7']],
['shorter than reservoir',
{'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},
['a', 'b', 'c']],
['crafted replacements',
{'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},
['a', 'e']]]]
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 |
|---|---|---|---|
| reservoir 0 k=3 | ['e8', 'e1', 'e9'] | ['e8', 'e1', 'e9'] | Passed |
| reservoir 1 k=2 | ['e0', 'e3'] | ['e0', 'e3'] | Passed |
| reservoir 2 k=4 | ['e0', 'e1', 'e8', 'e6'] | ['e0', 'e1', 'e8', 'e6'] | Passed |
| reservoir 3 k=1 | ['e2'] | ['e2'] | Passed |
| reservoir 4 k=5 | ['e5', 'e6', 'e2', 'e9', 'e7'] | ['e5', 'e6', 'e2', 'e9', 'e7'] | Passed |
| shorter than reservoir | ['a', 'b'] | ['a', 'b'] | Passed |
| crafted replacements | ['a', 'e'] | ['a', 'e'] | Passed |
SHA-256 / f06abdb0e7ba2f0264fa3d7a7168f66938117441c330da452c4cc0125ad1e717
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.806875+00:00.
Case digest / ab616b14182b840203b028760fed3c44d4984fff8db8f2d452488359feba7c70