{"abstract":"Later items are over-sampled because the acceptance probability is k/i instead of k/(i+1).","category":"Probabilistic sketches","checks":7,"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.","evaluation_group":"w2-probabilistic_sketches-reservoir-algorithm-r","failed_approach":"Reducing modulo i + 2 under-samples later items instead.","family":"w2-probabilistic_sketches-reservoir-algorithm-r-draw-range","id":"FA-73146","implementations":{"attempt":{"sha256":"910f1d90fc41c74b9360755876c704f9ec86475ec03158ff11cde82c338382f1","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    items = x['items']\n    draws = x['draws']\n    res = []\n    for i, item in enumerate(items):\n        if i < k:\n            res.append(item)\n        else:\n            j = draws[i - k] % (i + 2)\n            if j < k:\n                res[j] = item\n    return res\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['reservoir 0 k=3',\n   {'draws': [503, 385, 476, 488, 606, 108, 252, 164, 59, 250, 942, 523, 165, 983],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e8', 'e1', 'e9']],\n  ['reservoir 1 k=2',\n   {'draws': [878, 281, 618, 928, 879, 391, 183, 62, 660, 169, 814],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e0', 'e3']],\n  ['reservoir 2 k=4',\n   {'draws': [727, 622, 213, 583, 893, 937, 186, 620, 217, 656, 799, 958, 803, 920, 178, 243, 305],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e1', 'e8', 'e6']],\n  ['reservoir 3 k=1',\n   {'draws': [611, 696, 835, 229, 731, 995, 790, 117, 923, 647],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e2']],\n  ['reservoir 4 k=5',\n   {'draws': [510, 183, 524, 267, 413, 746, 732, 203, 700, 240, 732, 908, 296],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e5', 'e6', 'e2', 'e9', 'e7']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]],\n [['reservoir 0 k=3',\n   {'draws': [429, 197, 290, 177, 971, 131, 62, 409, 364, 17, 814, 582, 979, 710],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e0', 'e3', 'e10']],\n  ['reservoir 1 k=2',\n   {'draws': [618, 258, 338, 126, 358, 919, 861, 857, 443, 291, 148],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e5', 'e6']],\n  ['reservoir 2 k=4',\n   {'draws': [106, 978, 558, 741, 260, 124, 968, 5, 740, 138, 214, 818, 130, 716, 684, 510, 645],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e10', 'e4', 'e2', 'e3']],\n  ['reservoir 3 k=1',\n   {'draws': [638, 208, 553, 430, 153, 336, 213, 400, 598, 60],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e6']],\n  ['reservoir 4 k=5',\n   {'draws': [5, 641, 334, 585, 354, 584, 201, 141, 682, 953, 308, 604, 445],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e8', 'e10', 'e2', 'e3', 'e9']],\n  ['shorter than reservoir',\n   {'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},\n   ['a', 'b', 'c']],\n  ['crafted replacements',\n   {'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['e', 'c']]],\n [['reservoir 0 k=3',\n   {'draws': [533, 409, 869, 398, 863, 761, 203, 237, 12, 354, 244, 883, 829, 798],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e11', 'e3', 'e2']],\n  ['reservoir 1 k=2',\n   {'draws': [264, 40, 302, 942, 526, 53, 293, 784, 595, 721, 162],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e5', 'e6']],\n  ['reservoir 2 k=4',\n   {'draws': [693, 14, 13, 722, 904, 717, 916, 354, 489, 959, 175, 892, 551, 857, 45, 179, 406],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e1', 'e7', 'e10']],\n  ['reservoir 3 k=1',\n   {'draws': [348, 426, 687, 856, 902, 812, 612, 255, 545, 118],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e6']],\n  ['reservoir 4 k=5',\n   {'draws': [384, 350, 593, 569, 642, 244, 923, 625, 358, 272, 497, 854, 402],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e6', 'e7', 'e10', 'e3', 'e4']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a'], 'k': 6}, ['a']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]],\n [['reservoir 0 k=3',\n   {'draws': [538, 676, 232, 616, 107, 792, 778, 632, 710, 421, 135, 166, 239, 112],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e8', 'e4', 'e11']],\n  ['reservoir 1 k=2',\n   {'draws': [943, 565, 900, 590, 917, 577, 294, 93, 35, 597, 462],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e6', 'e7']],\n  ['reservoir 2 k=4',\n   {'draws': [101, 66, 640, 194, 962, 859, 108, 424, 866, 554, 146, 488, 486, 353, 692, 626, 747],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e5', 'e4', 'e7', 'e6']],\n  ['reservoir 3 k=1',\n   {'draws': [507, 631, 535, 543, 801, 706, 895, 467, 252, 805],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e0']],\n  ['reservoir 4 k=5',\n   {'draws': [631, 754, 93, 424, 593, 884, 850, 592, 410, 243, 577, 561, 1],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e0', 'e8', 'e2', 'e9', 'e10']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],\n  ['crafted replacements',\n   {'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['e', 'c']]],\n [['reservoir 0 k=3',\n   {'draws': [762, 620, 944, 96, 862, 52, 508, 532, 910, 706, 83, 2, 430, 802],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e4', 'e1', 'e5']],\n  ['reservoir 1 k=2',\n   {'draws': [760, 573, 571, 862, 815, 852, 887, 584, 98, 704, 573],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e0', 'e4']],\n  ['reservoir 2 k=4',\n   {'draws': [902, 434, 254, 114, 573, 476, 133, 547, 752, 830, 136, 186, 358, 553, 804, 564, 334],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e14', 'e7', 'e3']],\n  ['reservoir 3 k=1',\n   {'draws': [78, 337, 584, 508, 238, 901, 332, 921, 804, 16],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e3']],\n  ['reservoir 4 k=5',\n   {'draws': [65, 631, 860, 551, 878, 731, 235, 935, 569, 319, 581, 993, 213],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e0', 'e6', 'e8', 'e3', 'e7']],\n  ['shorter than reservoir',\n   {'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},\n   ['a', 'b', 'c']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"6db6ed1babb4ca2cb3a40b571f98cf2c38f4f0e463b26cb41b417872eb95cbaf","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    items = x['items']\n    draws = x['draws']\n    res = []\n    for i, item in enumerate(items):\n        if i < k:\n            res.append(item)\n        else:\n            j = draws[i - k] % i\n            if j < k:\n                res[j] = item\n    return res\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['reservoir 0 k=3',\n   {'draws': [503, 385, 476, 488, 606, 108, 252, 164, 59, 250, 942, 523, 165, 983],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e8', 'e1', 'e9']],\n  ['reservoir 1 k=2',\n   {'draws': [878, 281, 618, 928, 879, 391, 183, 62, 660, 169, 814],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e0', 'e3']],\n  ['reservoir 2 k=4',\n   {'draws': [727, 622, 213, 583, 893, 937, 186, 620, 217, 656, 799, 958, 803, 920, 178, 243, 305],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e1', 'e8', 'e6']],\n  ['reservoir 3 k=1',\n   {'draws': [611, 696, 835, 229, 731, 995, 790, 117, 923, 647],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e2']],\n  ['reservoir 4 k=5',\n   {'draws': [510, 183, 524, 267, 413, 746, 732, 203, 700, 240, 732, 908, 296],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e5', 'e6', 'e2', 'e9', 'e7']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]],\n [['reservoir 0 k=3',\n   {'draws': [429, 197, 290, 177, 971, 131, 62, 409, 364, 17, 814, 582, 979, 710],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e0', 'e3', 'e10']],\n  ['reservoir 1 k=2',\n   {'draws': [618, 258, 338, 126, 358, 919, 861, 857, 443, 291, 148],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e5', 'e6']],\n  ['reservoir 2 k=4',\n   {'draws': [106, 978, 558, 741, 260, 124, 968, 5, 740, 138, 214, 818, 130, 716, 684, 510, 645],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e10', 'e4', 'e2', 'e3']],\n  ['reservoir 3 k=1',\n   {'draws': [638, 208, 553, 430, 153, 336, 213, 400, 598, 60],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e6']],\n  ['reservoir 4 k=5',\n   {'draws': [5, 641, 334, 585, 354, 584, 201, 141, 682, 953, 308, 604, 445],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e8', 'e10', 'e2', 'e3', 'e9']],\n  ['shorter than reservoir',\n   {'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},\n   ['a', 'b', 'c']],\n  ['crafted replacements',\n   {'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['e', 'c']]],\n [['reservoir 0 k=3',\n   {'draws': [533, 409, 869, 398, 863, 761, 203, 237, 12, 354, 244, 883, 829, 798],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e11', 'e3', 'e2']],\n  ['reservoir 1 k=2',\n   {'draws': [264, 40, 302, 942, 526, 53, 293, 784, 595, 721, 162],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e5', 'e6']],\n  ['reservoir 2 k=4',\n   {'draws': [693, 14, 13, 722, 904, 717, 916, 354, 489, 959, 175, 892, 551, 857, 45, 179, 406],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e1', 'e7', 'e10']],\n  ['reservoir 3 k=1',\n   {'draws': [348, 426, 687, 856, 902, 812, 612, 255, 545, 118],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e6']],\n  ['reservoir 4 k=5',\n   {'draws': [384, 350, 593, 569, 642, 244, 923, 625, 358, 272, 497, 854, 402],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e6', 'e7', 'e10', 'e3', 'e4']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a'], 'k': 6}, ['a']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]],\n [['reservoir 0 k=3',\n   {'draws': [538, 676, 232, 616, 107, 792, 778, 632, 710, 421, 135, 166, 239, 112],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e8', 'e4', 'e11']],\n  ['reservoir 1 k=2',\n   {'draws': [943, 565, 900, 590, 917, 577, 294, 93, 35, 597, 462],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e6', 'e7']],\n  ['reservoir 2 k=4',\n   {'draws': [101, 66, 640, 194, 962, 859, 108, 424, 866, 554, 146, 488, 486, 353, 692, 626, 747],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e5', 'e4', 'e7', 'e6']],\n  ['reservoir 3 k=1',\n   {'draws': [507, 631, 535, 543, 801, 706, 895, 467, 252, 805],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e0']],\n  ['reservoir 4 k=5',\n   {'draws': [631, 754, 93, 424, 593, 884, 850, 592, 410, 243, 577, 561, 1],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e0', 'e8', 'e2', 'e9', 'e10']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],\n  ['crafted replacements',\n   {'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['e', 'c']]],\n [['reservoir 0 k=3',\n   {'draws': [762, 620, 944, 96, 862, 52, 508, 532, 910, 706, 83, 2, 430, 802],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e4', 'e1', 'e5']],\n  ['reservoir 1 k=2',\n   {'draws': [760, 573, 571, 862, 815, 852, 887, 584, 98, 704, 573],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e0', 'e4']],\n  ['reservoir 2 k=4',\n   {'draws': [902, 434, 254, 114, 573, 476, 133, 547, 752, 830, 136, 186, 358, 553, 804, 564, 334],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e14', 'e7', 'e3']],\n  ['reservoir 3 k=1',\n   {'draws': [78, 337, 584, 508, 238, 901, 332, 921, 804, 16],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e3']],\n  ['reservoir 4 k=5',\n   {'draws': [65, 631, 860, 551, 878, 731, 235, 935, 569, 319, 581, 993, 213],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e0', 'e6', 'e8', 'e3', 'e7']],\n  ['shorter than reservoir',\n   {'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},\n   ['a', 'b', 'c']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"f06abdb0e7ba2f0264fa3d7a7168f66938117441c330da452c4cc0125ad1e717","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    items = x['items']\n    draws = x['draws']\n    res = []\n    for i, item in enumerate(items):\n        if i < k:\n            res.append(item)\n        else:\n            j = draws[i - k] % (i + 1)\n            if j < k:\n                res[j] = item\n    return res\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['reservoir 0 k=3',\n   {'draws': [503, 385, 476, 488, 606, 108, 252, 164, 59, 250, 942, 523, 165, 983],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e8', 'e1', 'e9']],\n  ['reservoir 1 k=2',\n   {'draws': [878, 281, 618, 928, 879, 391, 183, 62, 660, 169, 814],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e0', 'e3']],\n  ['reservoir 2 k=4',\n   {'draws': [727, 622, 213, 583, 893, 937, 186, 620, 217, 656, 799, 958, 803, 920, 178, 243, 305],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e1', 'e8', 'e6']],\n  ['reservoir 3 k=1',\n   {'draws': [611, 696, 835, 229, 731, 995, 790, 117, 923, 647],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e2']],\n  ['reservoir 4 k=5',\n   {'draws': [510, 183, 524, 267, 413, 746, 732, 203, 700, 240, 732, 908, 296],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e5', 'e6', 'e2', 'e9', 'e7']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]],\n [['reservoir 0 k=3',\n   {'draws': [429, 197, 290, 177, 971, 131, 62, 409, 364, 17, 814, 582, 979, 710],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e0', 'e3', 'e10']],\n  ['reservoir 1 k=2',\n   {'draws': [618, 258, 338, 126, 358, 919, 861, 857, 443, 291, 148],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e5', 'e6']],\n  ['reservoir 2 k=4',\n   {'draws': [106, 978, 558, 741, 260, 124, 968, 5, 740, 138, 214, 818, 130, 716, 684, 510, 645],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e10', 'e4', 'e2', 'e3']],\n  ['reservoir 3 k=1',\n   {'draws': [638, 208, 553, 430, 153, 336, 213, 400, 598, 60],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e6']],\n  ['reservoir 4 k=5',\n   {'draws': [5, 641, 334, 585, 354, 584, 201, 141, 682, 953, 308, 604, 445],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e8', 'e10', 'e2', 'e3', 'e9']],\n  ['shorter than reservoir',\n   {'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},\n   ['a', 'b', 'c']],\n  ['crafted replacements',\n   {'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['e', 'c']]],\n [['reservoir 0 k=3',\n   {'draws': [533, 409, 869, 398, 863, 761, 203, 237, 12, 354, 244, 883, 829, 798],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e11', 'e3', 'e2']],\n  ['reservoir 1 k=2',\n   {'draws': [264, 40, 302, 942, 526, 53, 293, 784, 595, 721, 162],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e5', 'e6']],\n  ['reservoir 2 k=4',\n   {'draws': [693, 14, 13, 722, 904, 717, 916, 354, 489, 959, 175, 892, 551, 857, 45, 179, 406],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e1', 'e7', 'e10']],\n  ['reservoir 3 k=1',\n   {'draws': [348, 426, 687, 856, 902, 812, 612, 255, 545, 118],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e6']],\n  ['reservoir 4 k=5',\n   {'draws': [384, 350, 593, 569, 642, 244, 923, 625, 358, 272, 497, 854, 402],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e6', 'e7', 'e10', 'e3', 'e4']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a'], 'k': 6}, ['a']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]],\n [['reservoir 0 k=3',\n   {'draws': [538, 676, 232, 616, 107, 792, 778, 632, 710, 421, 135, 166, 239, 112],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e8', 'e4', 'e11']],\n  ['reservoir 1 k=2',\n   {'draws': [943, 565, 900, 590, 917, 577, 294, 93, 35, 597, 462],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e6', 'e7']],\n  ['reservoir 2 k=4',\n   {'draws': [101, 66, 640, 194, 962, 859, 108, 424, 866, 554, 146, 488, 486, 353, 692, 626, 747],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e5', 'e4', 'e7', 'e6']],\n  ['reservoir 3 k=1',\n   {'draws': [507, 631, 535, 543, 801, 706, 895, 467, 252, 805],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e0']],\n  ['reservoir 4 k=5',\n   {'draws': [631, 754, 93, 424, 593, 884, 850, 592, 410, 243, 577, 561, 1],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e0', 'e8', 'e2', 'e9', 'e10']],\n  ['shorter than reservoir', {'draws': [1, 2, 3], 'items': ['a', 'b'], 'k': 6}, ['a', 'b']],\n  ['crafted replacements',\n   {'draws': [1, 3, 0, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['e', 'c']]],\n [['reservoir 0 k=3',\n   {'draws': [762, 620, 944, 96, 862, 52, 508, 532, 910, 706, 83, 2, 430, 802],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11'],\n    'k': 3},\n   ['e4', 'e1', 'e5']],\n  ['reservoir 1 k=2',\n   {'draws': [760, 573, 571, 862, 815, 852, 887, 584, 98, 704, 573],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8'],\n    'k': 2},\n   ['e0', 'e4']],\n  ['reservoir 2 k=4',\n   {'draws': [902, 434, 254, 114, 573, 476, 133, 547, 752, 830, 136, 186, 358, 553, 804, 564, 334],\n    'items': ['e0',\n              'e1',\n              'e2',\n              'e3',\n              'e4',\n              'e5',\n              'e6',\n              'e7',\n              'e8',\n              'e9',\n              'e10',\n              'e11',\n              'e12',\n              'e13',\n              'e14'],\n    'k': 4},\n   ['e0', 'e14', 'e7', 'e3']],\n  ['reservoir 3 k=1',\n   {'draws': [78, 337, 584, 508, 238, 901, 332, 921, 804, 16],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7'],\n    'k': 1},\n   ['e3']],\n  ['reservoir 4 k=5',\n   {'draws': [65, 631, 860, 551, 878, 731, 235, 935, 569, 319, 581, 993, 213],\n    'items': ['e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10'],\n    'k': 5},\n   ['e0', 'e6', 'e8', 'e3', 'e7']],\n  ['shorter than reservoir',\n   {'draws': [1, 2, 3], 'items': ['a', 'b', 'c'], 'k': 6},\n   ['a', 'b', 'c']],\n  ['crafted replacements',\n   {'draws': [1, 3, 1, 7, 5, 2, 9], 'items': ['a', 'b', 'c', 'd', 'e'], 'k': 2},\n   ['a', 'e']]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-reservoir-algorithm-r-draw-range","generated_at":"2026-09-29T14:48:44.806875+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Uniform stream samples feed audit logs and A/B diagnostics; any skew in the replacement rule biases the sample toward early or late events.","repair":"Reduce the draw modulo i + 1.","root_cause":"The draw is reduced modulo i, the count of earlier items, instead of i + 1.","sha256":"ab616b14182b840203b028760fed3c44d4984fff8db8f2d452488359feba7c70","title":"Reservoir sampling (Algorithm R) with supplied draws: replacement range excludes the current item · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.748,"exit_code":1,"observations":[{"actual":["e6","e4","e2"],"check":"reservoir 0 k=3","expected":["e8","e1","e9"],"passed":false},{"actual":["e4","e3"],"check":"reservoir 1 k=2","expected":["e0","e3"],"passed":false},{"actual":["e0","e4","e9","e8"],"check":"reservoir 2 k=4","expected":["e0","e1","e8","e6"],"passed":false},{"actual":["e3"],"check":"reservoir 3 k=1","expected":["e2"],"passed":false},{"actual":["e0","e1","e10","e3","e4"],"check":"reservoir 4 k=5","expected":["e5","e6","e2","e9","e7"],"passed":false},{"actual":["a","b"],"check":"shorter than reservoir","expected":["a","b"],"passed":true},{"actual":["a","e"],"check":"crafted replacements","expected":["a","e"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"reservoir 0 k=3\", \"actual\": [\"e6\", \"e4\", \"e2\"], \"expected\": [\"e8\", \"e1\", \"e9\"], \"passed\": false}, {\"check\": \"reservoir 1 k=2\", \"actual\": [\"e4\", \"e3\"], \"expected\": [\"e0\", \"e3\"], \"passed\": false}, {\"check\": \"reservoir 2 k=4\", \"actual\": [\"e0\", \"e4\", \"e9\", \"e8\"], \"expected\": [\"e0\", \"e1\", \"e8\", \"e6\"], \"passed\": false}, {\"check\": \"reservoir 3 k=1\", \"actual\": [\"e3\"], \"expected\": [\"e2\"], \"passed\": false}, {\"check\": \"reservoir 4 k=5\", \"actual\": [\"e0\", \"e1\", \"e10\", \"e3\", \"e4\"], \"expected\": [\"e5\", \"e6\", \"e2\", \"e9\", \"e7\"], \"passed\": false}, {\"check\": \"shorter than reservoir\", \"actual\": [\"a\", \"b\"], \"expected\": [\"a\", \"b\"], \"passed\": true}, {\"check\": \"crafted replacements\", \"actual\": [\"a\", \"e\"], \"expected\": [\"a\", \"e\"], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.359,"exit_code":1,"observations":[{"actual":["e9","e5","e6"],"check":"reservoir 0 k=3","expected":["e8","e1","e9"],"passed":false},{"actual":["e2","e1"],"check":"reservoir 1 k=2","expected":["e0","e3"],"passed":false},{"actual":["e0","e14","e7","e6"],"check":"reservoir 2 k=4","expected":["e0","e1","e8","e6"],"passed":false},{"actual":["e2"],"check":"reservoir 3 k=1","expected":["e2"],"passed":true},{"actual":["e5","e1","e2","e8","e4"],"check":"reservoir 4 k=5","expected":["e5","e6","e2","e9","e7"],"passed":false},{"actual":["a","b"],"check":"shorter than reservoir","expected":["a","b"],"passed":true},{"actual":["d","e"],"check":"crafted replacements","expected":["a","e"],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"reservoir 0 k=3\", \"actual\": [\"e9\", \"e5\", \"e6\"], \"expected\": [\"e8\", \"e1\", \"e9\"], \"passed\": false}, {\"check\": \"reservoir 1 k=2\", \"actual\": [\"e2\", \"e1\"], \"expected\": [\"e0\", \"e3\"], \"passed\": false}, {\"check\": \"reservoir 2 k=4\", \"actual\": [\"e0\", \"e14\", \"e7\", \"e6\"], \"expected\": [\"e0\", \"e1\", \"e8\", \"e6\"], \"passed\": false}, {\"check\": \"reservoir 3 k=1\", \"actual\": [\"e2\"], \"expected\": [\"e2\"], \"passed\": true}, {\"check\": \"reservoir 4 k=5\", \"actual\": [\"e5\", \"e1\", \"e2\", \"e8\", \"e4\"], \"expected\": [\"e5\", \"e6\", \"e2\", \"e9\", \"e7\"], \"passed\": false}, {\"check\": \"shorter than reservoir\", \"actual\": [\"a\", \"b\"], \"expected\": [\"a\", \"b\"], \"passed\": true}, {\"check\": \"crafted replacements\", \"actual\": [\"d\", \"e\"], \"expected\": [\"a\", \"e\"], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.358,"exit_code":0,"observations":[{"actual":["e8","e1","e9"],"check":"reservoir 0 k=3","expected":["e8","e1","e9"],"passed":true},{"actual":["e0","e3"],"check":"reservoir 1 k=2","expected":["e0","e3"],"passed":true},{"actual":["e0","e1","e8","e6"],"check":"reservoir 2 k=4","expected":["e0","e1","e8","e6"],"passed":true},{"actual":["e2"],"check":"reservoir 3 k=1","expected":["e2"],"passed":true},{"actual":["e5","e6","e2","e9","e7"],"check":"reservoir 4 k=5","expected":["e5","e6","e2","e9","e7"],"passed":true},{"actual":["a","b"],"check":"shorter than reservoir","expected":["a","b"],"passed":true},{"actual":["a","e"],"check":"crafted replacements","expected":["a","e"],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"reservoir 0 k=3\", \"actual\": [\"e8\", \"e1\", \"e9\"], \"expected\": [\"e8\", \"e1\", \"e9\"], \"passed\": true}, {\"check\": \"reservoir 1 k=2\", \"actual\": [\"e0\", \"e3\"], \"expected\": [\"e0\", \"e3\"], \"passed\": true}, {\"check\": \"reservoir 2 k=4\", \"actual\": [\"e0\", \"e1\", \"e8\", \"e6\"], \"expected\": [\"e0\", \"e1\", \"e8\", \"e6\"], \"passed\": true}, {\"check\": \"reservoir 3 k=1\", \"actual\": [\"e2\"], \"expected\": [\"e2\"], \"passed\": true}, {\"check\": \"reservoir 4 k=5\", \"actual\": [\"e5\", \"e6\", \"e2\", \"e9\", \"e7\"], \"expected\": [\"e5\", \"e6\", \"e2\", \"e9\", \"e7\"], \"passed\": true}, {\"check\": \"shorter than reservoir\", \"actual\": [\"a\", \"b\"], \"expected\": [\"a\", \"b\"], \"passed\": true}, {\"check\": \"crafted replacements\", \"actual\": [\"a\", \"e\"], \"expected\": [\"a\", \"e\"], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}