FA-73291 / Probabilistic sketches / Open access
Cuckoo filter with partial-key relocation: lookup checks only the primary bucket · case 01
Items placed in their alternate bucket are reported absent.
ROOT CAUSE
Membership inspects only i1.
VERIFIED REPAIR
Check both candidate buckets.
Unsuccessful approach: Probing i1 XOR f checks an unhashed alternate that relocation never uses.
Case contract
Input {m (power of two), max_kicks, ops} with pre-hashed 32-bit items. Fingerprint f is bits 24-31, with 0 remapped to 1 (0 marks an empty slot in packed tables). i1 = h mod m and the alternate bucket is alt(i, f) = (i XOR (f*0x5bd1e995 mod 2^32)) mod m, so it is computable from the fingerprint alone. Buckets hold 2 fingerprints. Insert tries i1, then i2, then performs up to max_kicks evictions starting at i1, swapping slot (kick mod 2); on failure the table is restored and "full" is returned. Delete removes one copy, from i1 first. Return [results, buckets].
Why this case matters
Cuckoo filters give deletable approximate membership for caches and dedup stores; relocation only works if the alternate bucket is derivable from the stored fingerprint.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
maxk = x['max_kicks']
buckets = [[] for _ in range(m)]
def fp(h):
f = (h >> 24) & 0xFF
return f if f else 1
def alt(i, f):
return (i ^ ((f * 0x5bd1e995) & 0xFFFFFFFF)) & (m - 1)
res = []
for op, h in x['ops']:
f = fp(h)
i1 = h & (m - 1)
i2 = alt(i1, f)
if op == 'ins':
if len(buckets[i1]) < 2:
buckets[i1].append(f)
res.append('ok')
continue
if len(buckets[i2]) < 2:
buckets[i2].append(f)
res.append('ok')
continue
saved = [list(bk) for bk in buckets]
i = i1
placed = False
for n in range(maxk):
slot = n % 2
f, buckets[i][slot] = buckets[i][slot], f
i = alt(i, f)
if len(buckets[i]) < 2:
buckets[i].append(f)
placed = True
break
if placed:
res.append('ok')
else:
buckets = saved
res.append('full')
elif op == 'has':
res.append(f in buckets[i1])
else:
if f in buckets[i1]:
buckets[i1].remove(f)
res.append(True)
elif f in buckets[i2]:
buckets[i2].remove(f)
res.append(True)
else:
res.append(False)
return [res, buckets]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 4053727168],
['ins', 2090112333],
['ins', 4166861756],
['ins', 2773431433],
['ins', 936790768],
['ins', 4092435925],
['ins', 1926221132],
['ins', 2840737955],
['ins', 2820504097],
['has', 4053727168],
['has', 2090112333],
['has', 4166861756],
['has', 2773431433],
['has', 936790768],
['has', 4092435925],
['del', 2090112333],
['has', 2090112333],
['has', 1631804978]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[241, 248], [165], [243, 114], [55, 169]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 4049152218],
['ins', 4119180372],
['ins', 4174459859],
['ins', 3472142201],
['ins', 2787193319],
['ins', 2868232378],
['ins', 1273646965],
['ins', 169222886],
['ins', 2977310459],
['ins', 1284001336],
['ins', 493096980],
['ins', 2962394317],
['ins', 3792145538],
['ins', 817217868],
['ins', 1471274732],
['ins', 3039844410],
['has', 4049152218],
['has', 4119180372],
['has', 4174459859],
['has', 3472142201],
['has', 2787193319],
['has', 2868232378],
['del', 4119180372],
['has', 4119180372],
['has', 2619116454]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1057150321],
['ins', 249819674],
['ins', 2073545798],
['ins', 263027109],
['ins', 2756491437],
['ins', 3951341878],
['ins', 1961187033],
['ins', 1539010652],
['ins', 3788730431],
['ins', 581588937],
['has', 1057150321],
['has', 249819674],
['has', 2073545798],
['has', 263027109],
['has', 2756491437],
['has', 3951341878],
['del', 249819674],
['has', 249819674],
['has', 2428817573]]},
[['ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
'ok',
'ok',
'ok',
True,
True,
True,
True,
False,
True,
True,
False,
False],
[[91], [63, 15], [235, 123], [225, 34]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 3789782486],
['ins', 313437937],
['ins', 1269036109],
['ins', 3831223018],
['ins', 3169414613],
['ins', 352655826],
['ins', 1455663028],
['ins', 3861257430],
['ins', 2012308387],
['ins', 3682187405],
['ins', 4144766613],
['ins', 1226905701],
['ins', 1648098192],
['ins', 2311553967],
['ins', 1205192322],
['ins', 1075026296],
['ins', 3523968378],
['ins', 620420201],
['has', 3789782486],
['has', 313437937],
['has', 1269036109],
['has', 3831223018],
['has', 3169414613],
['has', 352655826],
['del', 313437937],
['has', 313437937],
['has', 1988851048]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 6], ['has', 6], ['ins', 16777222], ['has', 16777222]]},
[['ok', True, 'ok', True], [[], [], [1, 1], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 620756995], ['has', 620756995]]},
[['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 4,
'ops': [['ins', 2427847248],
['ins', 1880610265],
['ins', 1587388028],
['ins', 1622648335],
['ins', 836275908],
['ins', 2015902217],
['ins', 2680590424],
['has', 2680590424]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 2378664753],
['ins', 333538489],
['ins', 1381905127],
['ins', 3798994753],
['ins', 3675580320],
['ins', 383347823],
['ins', 4040964303],
['ins', 499293357],
['ins', 545063865],
['has', 545063865]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False],
[[219, 29], [141, 19], [], [82, 226]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 2,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 732265847],
['ins', 1810542448],
['ins', 1958173573],
['ins', 1539460854],
['ins', 2114796178],
['ins', 3545636457],
['ins', 4135382597],
['ins', 3892817675],
['ins', 438016941],
['has', 732265847],
['has', 1810542448],
['has', 1958173573],
['has', 1539460854],
['has', 2114796178],
['has', 3545636457],
['del', 1810542448],
['has', 1810542448],
['has', 2049146592]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[43], [116, 211], [91, 126], [232, 246]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 344496995],
['ins', 1850418827],
['ins', 3897751000],
['ins', 3463570078],
['ins', 1162402666],
['ins', 1898656778],
['ins', 383968521],
['ins', 2007988446],
['ins', 281781798],
['ins', 871214629],
['ins', 806266810],
['ins', 3429544281],
['ins', 2010328261],
['ins', 455238739],
['ins', 1620563447],
['ins', 719915703],
['has', 344496995],
['has', 1850418827],
['has', 3897751000],
['has', 3463570078],
['has', 1162402666],
['has', 1898656778],
['del', 1850418827],
['has', 1850418827],
['has', 3035418391]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[232, 206], [22, 204], [48, 51], [20, 69], [27], [119], [16, 119], [113, 96]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 766617118],
['ins', 877620278],
['ins', 4275105416],
['ins', 1303245290],
['ins', 3451862689],
['ins', 2637149561],
['ins', 3479941498],
['ins', 2044492405],
['ins', 2944051255],
['ins', 2216655256],
['has', 766617118],
['has', 877620278],
['has', 4275105416],
['has', 1303245290],
['has', 3451862689],
['has', 2637149561],
['del', 877620278],
['has', 877620278],
['has', 2759628967]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[254, 121], [205, 157], [207], [77, 45]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 639277804],
['ins', 2134252242],
['ins', 564247903],
['ins', 3252176342],
['ins', 2887268535],
['ins', 3809114112],
['ins', 843347271],
['ins', 3790659506],
['ins', 3547675276],
['ins', 738614994],
['ins', 861586606],
['ins', 3332826411],
['ins', 1292373985],
['ins', 2781861741],
['ins', 3516548937],
['ins', 51826789],
['ins', 2496943570],
['ins', 1160646918],
['has', 639277804],
['has', 2134252242],
['has', 564247903],
['has', 3252176342],
['has', 2887268535],
['has', 3809114112],
['del', 2134252242],
['has', 2134252242],
['has', 935263858]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[227, 77], [209], [44, 225], [198, 172], [38, 211], [3, 165], [193, 51], [33, 50]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 7], ['has', 7], ['ins', 16777223], ['has', 16777223]]},
[['ok', True, 'ok', True], [[], [], [], [1, 1]]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410178],
['ins', 1023410178],
['ins', 1023410178],
['del', 1023410178],
['has', 1023410178]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 654311427], ['has', 654311427]]},
[['ok', 'ok', 'ok', True], [[39], [], [], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1091792544],
['ins', 3159258982],
['ins', 6655988],
['ins', 3780476686],
['ins', 3221151820],
['ins', 1354260753],
['ins', 3503243708],
['ins', 2855214902],
['has', 2855214902]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True],
[[208, 1], [80, 65], [170, 188], [191, 225]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 2820483633],
['ins', 2026478793],
['ins', 3254196126],
['ins', 1946366892],
['ins', 1094111634],
['ins', 2388744848],
['ins', 2389839112],
['ins', 515044471],
['ins', 53530770],
['has', 53530770]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True],
[[116, 142], [168, 120], [3, 65], [30, 193]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 3,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1777236018],
['ins', 1670145830],
['ins', 1941989665],
['ins', 815435462],
['ins', 223861203],
['ins', 2013373959],
['ins', 2361849580],
['ins', 590950523],
['ins', 4250565577],
['has', 1777236018],
['has', 1670145830],
['has', 1941989665],
['has', 815435462],
['has', 223861203],
['has', 2013373959],
['del', 1670145830],
['has', 1670145830],
['has', 3153783919]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[140, 35], [115], [48, 105], [120, 13]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 3783348771],
['ins', 778649113],
['ins', 2658092326],
['ins', 3280724357],
['ins', 509673299],
['ins', 4192536040],
['ins', 3556431545],
['ins', 808068520],
['ins', 4124021509],
['ins', 1279264443],
['ins', 319971617],
['ins', 3929937397],
['ins', 3553621260],
['ins', 3193883894],
['ins', 1614892168],
['ins', 2819704474],
['has', 3783348771],
['has', 778649113],
['has', 2658092326],
['has', 3280724357],
['has', 509673299],
['has', 4192536040],
['del', 778649113],
['has', 778649113],
['has', 20192387]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[48, 158], [211], [168], [225, 30], [211, 245], [195, 249], [190, 19], [76, 234]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1242447109],
['ins', 57101625],
['ins', 1717012336],
['ins', 2477213626],
['ins', 81213852],
['ins', 171443414],
['ins', 1652493013],
['ins', 683056220],
['ins', 434760181],
['ins', 4153897861],
['has', 1242447109],
['has', 57101625],
['has', 1717012336],
['has', 2477213626],
['has', 81213852],
['has', 171443414],
['del', 57101625],
['has', 57101625],
['has', 3654960159]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[102, 4], [25], [147, 10], [98, 74]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 2236733609],
['ins', 3939410963],
['ins', 2724510957],
['ins', 1062065107],
['ins', 2304609820],
['ins', 616512379],
['ins', 3185211465],
['ins', 2149931096],
['ins', 1360730688],
['ins', 1166229974],
['ins', 563851633],
['ins', 1282711990],
['ins', 3774149403],
['ins', 1784829478],
['ins', 517992672],
['ins', 2318531676],
['ins', 723049147],
['ins', 1310520849],
['has', 2236733609],
['has', 3939410963],
['has', 2724510957],
['has', 1062065107],
['has', 2304609820],
['has', 616512379],
['del', 3939410963],
['has', 3939410963],
['has', 487237028]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[63, 128], [133, 189], [76], [224], [137, 33], [162, 81], [106, 30], [36, 69]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 8], ['has', 8], ['ins', 16777224], ['has', 16777224]]},
[['ok', True, 'ok', True], [[1, 1], [], [], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 687865859], ['has', 687865859]]},
[['ok', 'ok', 'ok', True], [[], [], [], [33, 37], [], [], [41], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 4,
'ops': [['ins', 1386070799],
['ins', 3104973709],
['ins', 2606612743],
['ins', 2328394719],
['ins', 4161737019],
['ins', 11222],
['ins', 283246673],
['ins', 3932342861],
['ins', 1826216374],
['has', 1826216374]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', True],
[[155, 185], [16, 82], [1, 108], [138, 248]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 1688258414],
['ins', 1587554040],
['ins', 452842125],
['ins', 2408027354],
['ins', 4039342963],
['ins', 3256509956],
['ins', 2220059300],
['has', 2220059300]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', False], [[94, 194], [26], [100, 143], [240]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 1,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 2508887774],
['ins', 3876506741],
['ins', 2397794896],
['ins', 521281616],
['ins', 1454258696],
['ins', 2418086625],
['ins', 1770269695],
['ins', 3954805098],
['ins', 334587253],
['has', 2508887774],
['has', 3876506741],
['has', 2397794896],
['has', 521281616],
['has', 1454258696],
['has', 2418086625],
['del', 3876506741],
['has', 3876506741],
['has', 1410375853]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[142, 31], [144], [235, 86], [105, 149]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 3626487179],
['ins', 1981200738],
['ins', 3299150810],
['ins', 879079952],
['ins', 569019066],
['ins', 1345246527],
['ins', 1279738884],
['ins', 329365259],
['ins', 3365708295],
['ins', 796732648],
['ins', 4104718778],
['ins', 2034888840],
['ins', 2274417079],
['ins', 3665801012],
['ins', 3713680567],
['ins', 3857873293],
['has', 3626487179],
['has', 1981200738],
['has', 3299150810],
['has', 879079952],
['has', 569019066],
['has', 1345246527],
['del', 1981200738],
['has', 1981200738],
['has', 3276243551]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[52, 47], [], [33], [216, 19], [76, 135], [121, 229], [196, 244], [200, 80]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3383446702],
['ins', 3102517778],
['ins', 551288533],
['ins', 427253337],
['ins', 630972810],
['ins', 261755786],
['ins', 2659101998],
['ins', 4089137114],
['ins', 619206018],
['ins', 827057174],
['has', 3383446702],
['has', 3102517778],
['has', 551288533],
['has', 427253337],
['has', 630972810],
['has', 261755786],
['del', 3102517778],
['has', 3102517778],
['has', 3884327477]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[158, 25], [32, 15], [243], [37, 201]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 576117675],
['ins', 3591995004],
['ins', 857862156],
['ins', 1433687209],
['ins', 301617113],
['ins', 3539330867],
['ins', 4152333277],
['ins', 1466665443],
['ins', 1161213858],
['ins', 2858962672],
['ins', 541647563],
['ins', 3757975831],
['ins', 3381058760],
['ins', 2650519778],
['ins', 1327108968],
['ins', 718689777],
['ins', 2171645977],
['ins', 1707898975],
['has', 576117675],
['has', 3591995004],
['has', 857862156],
['has', 1433687209],
['has', 301617113],
['has', 3539330867],
['del', 3591995004],
['has', 3591995004],
['has', 1355596815]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[87, 170], [85, 34], [69], [32, 210], [17, 51], [247, 201], [], [223, 101]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 9], ['has', 9], ['ins', 16777225], ['has', 16777225]]},
[['ok', True, 'ok', True], [[], [1, 1], [], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410178],
['ins', 1023410178],
['ins', 1023410178],
['del', 1023410178],
['has', 1023410178]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 721420291], ['has', 721420291]]},
[['ok', 'ok', 'ok', True], [[], [], [], [33, 37], [43], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3532591849],
['ins', 3312616903],
['ins', 927288817],
['ins', 436703699],
['ins', 3535596479],
['ins', 271263656],
['ins', 1018485099],
['ins', 1318602685],
['ins', 3734357799],
['has', 3734357799]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', False],
[[16], [210, 210], [197, 55], [60, 26]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 3928427799],
['ins', 841794179],
['ins', 4137117381],
['ins', 2214111069],
['ins', 74342131],
['ins', 2542867317],
['ins', 3143370314],
['has', 3143370314]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True], [[], [246, 131], [151, 187], [234, 50]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 2,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 754608121],
['ins', 1960208437],
['ins', 3951175178],
['ins', 1064988886],
['ins', 3939298075],
['ins', 1095070989],
['ins', 1643589898],
['ins', 3693486421],
['ins', 2812500932],
['has', 754608121],
['has', 1960208437],
['has', 3951175178],
['has', 1064988886],
['has', 3939298075],
['has', 1095070989],
['del', 1960208437],
['has', 1960208437],
['has', 584649671]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[65, 167], [44], [235, 63], [234, 97]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 224567547],
['ins', 2432915099],
['ins', 2215905994],
['ins', 671185022],
['ins', 3716804100],
['ins', 601285828],
['ins', 12858679],
['ins', 3759422002],
['ins', 3853628108],
['ins', 2271239656],
['ins', 3456356083],
['ins', 2687261260],
['ins', 3878729198],
['ins', 3979473486],
['ins', 4034375652],
['ins', 1046284924],
['has', 224567547],
['has', 2432915099],
['has', 2215905994],
['has', 671185022],
['has', 3716804100],
['has', 601285828],
['del', 2432915099],
['has', 2432915099],
['has', 1720764829]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[135], [], [132, 224], [13], [221, 35], [229, 206], [40, 231], [1, 237]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1632830720],
['ins', 1469336575],
['ins', 352685739],
['ins', 384400481],
['ins', 208997603],
['ins', 2690591441],
['ins', 2236537193],
['ins', 3295284666],
['ins', 284313747],
['ins', 324373489],
['has', 1632830720],
['has', 1469336575],
['has', 352685739],
['has', 384400481],
['has', 208997603],
['has', 2690591441],
['del', 1469336575],
['has', 1469336575],
['has', 528732436]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[97], [133, 160], [21, 196], [12, 22]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 1644275844],
['ins', 2900757313],
['ins', 2988486797],
['ins', 179906599],
['ins', 287880722],
['ins', 171405751],
['ins', 3525701444],
['ins', 4108271424],
['ins', 137937707],
['ins', 292658010],
['ins', 248385554],
['ins', 4191124304],
['ins', 2126259745],
['ins', 1346195861],
['ins', 3499831342],
['ins', 3344096474],
['ins', 3832504526],
['ins', 1756343263],
['has', 1644275844],
['has', 2900757313],
['has', 2988486797],
['has', 179906599],
['has', 287880722],
['has', 171405751],
['del', 2900757313],
['has', 2900757313],
['has', 1733874548]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[244, 249], [126], [17, 17], [8], [98, 14], [80, 10], [210, 208], [10, 178]]]],
['zero fingerprint byte',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 10], ['has', 10], ['ins', 16777226], ['has', 16777226]]},
[['ok', True, 'ok', True], [[], [], [1, 1], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 754974723], ['has', 754974723]]},
[['ok', 'ok', 'ok', True], [[], [], [45], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 348667353],
['ins', 1470437433],
['ins', 2596314351],
['ins', 3605354277],
['ins', 2183123397],
['ins', 2831721252],
['ins', 3982916143],
['ins', 1159395843],
['has', 1159395843]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', False],
[[168], [130, 20], [87, 237], [154, 214]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3777452496],
['ins', 4168010152],
['ins', 1415993158],
['ins', 2835527604],
['ins', 2455083042],
['ins', 1654735134],
['ins', 2169901690],
['ins', 1437706628],
['has', 1437706628]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True],
[[225, 248], [169, 85], [84, 146], [129]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 3,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]]]
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 |
|---|---|---|---|
| fill 0 m=4 kicks=3 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', True, True, True, True, False, False, True, False, False], [[241, 248], [165], [243, 114], [55, 169]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[241, 248], [165], [243, 114], [55, 169]]] | Failed |
| fill 1 m=8 kicks=4 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]] | Passed |
| fill 2 m=4 kicks=2 | [['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', 'ok', 'ok', 'ok', True, False, True, True, False, True, True, False, False], [[91], [63, 15], [235, 123], [225, 34]]] | [['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', 'ok', 'ok', 'ok', True, True, True, True, False, True, True, False, False], [[91], [63, 15], [235, 123], [225, 34]]] | Failed |
| fill 3 m=8 kicks=6 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', 'full', 'full', 'full', True, True, True, True, True, False, True, False, False], [[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', 'full', 'full', 'full', True, True, True, True, True, True, True, False, False], [[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]] | Failed |
| zero fingerprint byte | [['ok', True, 'ok', True], [[], [], [1, 1], []]] | [['ok', True, 'ok', True], [[], [], [1, 1], []]] | Passed |
| triple insert then delete | [['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]] | [['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]] | Passed |
| alternate bucket placement | [['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]] | [['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]] | Passed |
| insert needs full kick budget | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', False], [[49, 144], [120, 112], [94], [96, 159]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]] | Failed |
| insert rejected at kick budget | [['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False], [[219, 29], [141, 19], [], [82, 226]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False], [[219, 29], [141, 19], [], [82, 226]]] | Passed |
| one-bucket pressure | [['ok', 'ok', 'ok', 'ok', 'full', 'full', False, False], [[51, 17], [68, 34]]] | [['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]] | Failed |
SHA-256 / 2c0a0b35cf6cc8b234bcd95db0270dab6c8fc4df99715d487d7d5063213c30a9
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
maxk = x['max_kicks']
buckets = [[] for _ in range(m)]
def fp(h):
f = (h >> 24) & 0xFF
return f if f else 1
def alt(i, f):
return (i ^ ((f * 0x5bd1e995) & 0xFFFFFFFF)) & (m - 1)
res = []
for op, h in x['ops']:
f = fp(h)
i1 = h & (m - 1)
i2 = alt(i1, f)
if op == 'ins':
if len(buckets[i1]) < 2:
buckets[i1].append(f)
res.append('ok')
continue
if len(buckets[i2]) < 2:
buckets[i2].append(f)
res.append('ok')
continue
saved = [list(bk) for bk in buckets]
i = i1
placed = False
for n in range(maxk):
slot = n % 2
f, buckets[i][slot] = buckets[i][slot], f
i = alt(i, f)
if len(buckets[i]) < 2:
buckets[i].append(f)
placed = True
break
if placed:
res.append('ok')
else:
buckets = saved
res.append('full')
elif op == 'has':
res.append(f in buckets[i1] or f in buckets[(i1 ^ f) & (m - 1)])
else:
if f in buckets[i1]:
buckets[i1].remove(f)
res.append(True)
elif f in buckets[i2]:
buckets[i2].remove(f)
res.append(True)
else:
res.append(False)
return [res, buckets]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 4053727168],
['ins', 2090112333],
['ins', 4166861756],
['ins', 2773431433],
['ins', 936790768],
['ins', 4092435925],
['ins', 1926221132],
['ins', 2840737955],
['ins', 2820504097],
['has', 4053727168],
['has', 2090112333],
['has', 4166861756],
['has', 2773431433],
['has', 936790768],
['has', 4092435925],
['del', 2090112333],
['has', 2090112333],
['has', 1631804978]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[241, 248], [165], [243, 114], [55, 169]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 4049152218],
['ins', 4119180372],
['ins', 4174459859],
['ins', 3472142201],
['ins', 2787193319],
['ins', 2868232378],
['ins', 1273646965],
['ins', 169222886],
['ins', 2977310459],
['ins', 1284001336],
['ins', 493096980],
['ins', 2962394317],
['ins', 3792145538],
['ins', 817217868],
['ins', 1471274732],
['ins', 3039844410],
['has', 4049152218],
['has', 4119180372],
['has', 4174459859],
['has', 3472142201],
['has', 2787193319],
['has', 2868232378],
['del', 4119180372],
['has', 4119180372],
['has', 2619116454]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1057150321],
['ins', 249819674],
['ins', 2073545798],
['ins', 263027109],
['ins', 2756491437],
['ins', 3951341878],
['ins', 1961187033],
['ins', 1539010652],
['ins', 3788730431],
['ins', 581588937],
['has', 1057150321],
['has', 249819674],
['has', 2073545798],
['has', 263027109],
['has', 2756491437],
['has', 3951341878],
['del', 249819674],
['has', 249819674],
['has', 2428817573]]},
[['ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
'ok',
'ok',
'ok',
True,
True,
True,
True,
False,
True,
True,
False,
False],
[[91], [63, 15], [235, 123], [225, 34]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 3789782486],
['ins', 313437937],
['ins', 1269036109],
['ins', 3831223018],
['ins', 3169414613],
['ins', 352655826],
['ins', 1455663028],
['ins', 3861257430],
['ins', 2012308387],
['ins', 3682187405],
['ins', 4144766613],
['ins', 1226905701],
['ins', 1648098192],
['ins', 2311553967],
['ins', 1205192322],
['ins', 1075026296],
['ins', 3523968378],
['ins', 620420201],
['has', 3789782486],
['has', 313437937],
['has', 1269036109],
['has', 3831223018],
['has', 3169414613],
['has', 352655826],
['del', 313437937],
['has', 313437937],
['has', 1988851048]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 6], ['has', 6], ['ins', 16777222], ['has', 16777222]]},
[['ok', True, 'ok', True], [[], [], [1, 1], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 620756995], ['has', 620756995]]},
[['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 4,
'ops': [['ins', 2427847248],
['ins', 1880610265],
['ins', 1587388028],
['ins', 1622648335],
['ins', 836275908],
['ins', 2015902217],
['ins', 2680590424],
['has', 2680590424]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 2378664753],
['ins', 333538489],
['ins', 1381905127],
['ins', 3798994753],
['ins', 3675580320],
['ins', 383347823],
['ins', 4040964303],
['ins', 499293357],
['ins', 545063865],
['has', 545063865]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False],
[[219, 29], [141, 19], [], [82, 226]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 2,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 732265847],
['ins', 1810542448],
['ins', 1958173573],
['ins', 1539460854],
['ins', 2114796178],
['ins', 3545636457],
['ins', 4135382597],
['ins', 3892817675],
['ins', 438016941],
['has', 732265847],
['has', 1810542448],
['has', 1958173573],
['has', 1539460854],
['has', 2114796178],
['has', 3545636457],
['del', 1810542448],
['has', 1810542448],
['has', 2049146592]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[43], [116, 211], [91, 126], [232, 246]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 344496995],
['ins', 1850418827],
['ins', 3897751000],
['ins', 3463570078],
['ins', 1162402666],
['ins', 1898656778],
['ins', 383968521],
['ins', 2007988446],
['ins', 281781798],
['ins', 871214629],
['ins', 806266810],
['ins', 3429544281],
['ins', 2010328261],
['ins', 455238739],
['ins', 1620563447],
['ins', 719915703],
['has', 344496995],
['has', 1850418827],
['has', 3897751000],
['has', 3463570078],
['has', 1162402666],
['has', 1898656778],
['del', 1850418827],
['has', 1850418827],
['has', 3035418391]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[232, 206], [22, 204], [48, 51], [20, 69], [27], [119], [16, 119], [113, 96]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 766617118],
['ins', 877620278],
['ins', 4275105416],
['ins', 1303245290],
['ins', 3451862689],
['ins', 2637149561],
['ins', 3479941498],
['ins', 2044492405],
['ins', 2944051255],
['ins', 2216655256],
['has', 766617118],
['has', 877620278],
['has', 4275105416],
['has', 1303245290],
['has', 3451862689],
['has', 2637149561],
['del', 877620278],
['has', 877620278],
['has', 2759628967]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[254, 121], [205, 157], [207], [77, 45]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 639277804],
['ins', 2134252242],
['ins', 564247903],
['ins', 3252176342],
['ins', 2887268535],
['ins', 3809114112],
['ins', 843347271],
['ins', 3790659506],
['ins', 3547675276],
['ins', 738614994],
['ins', 861586606],
['ins', 3332826411],
['ins', 1292373985],
['ins', 2781861741],
['ins', 3516548937],
['ins', 51826789],
['ins', 2496943570],
['ins', 1160646918],
['has', 639277804],
['has', 2134252242],
['has', 564247903],
['has', 3252176342],
['has', 2887268535],
['has', 3809114112],
['del', 2134252242],
['has', 2134252242],
['has', 935263858]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[227, 77], [209], [44, 225], [198, 172], [38, 211], [3, 165], [193, 51], [33, 50]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 7], ['has', 7], ['ins', 16777223], ['has', 16777223]]},
[['ok', True, 'ok', True], [[], [], [], [1, 1]]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410178],
['ins', 1023410178],
['ins', 1023410178],
['del', 1023410178],
['has', 1023410178]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 654311427], ['has', 654311427]]},
[['ok', 'ok', 'ok', True], [[39], [], [], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1091792544],
['ins', 3159258982],
['ins', 6655988],
['ins', 3780476686],
['ins', 3221151820],
['ins', 1354260753],
['ins', 3503243708],
['ins', 2855214902],
['has', 2855214902]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True],
[[208, 1], [80, 65], [170, 188], [191, 225]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 2820483633],
['ins', 2026478793],
['ins', 3254196126],
['ins', 1946366892],
['ins', 1094111634],
['ins', 2388744848],
['ins', 2389839112],
['ins', 515044471],
['ins', 53530770],
['has', 53530770]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True],
[[116, 142], [168, 120], [3, 65], [30, 193]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 3,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1777236018],
['ins', 1670145830],
['ins', 1941989665],
['ins', 815435462],
['ins', 223861203],
['ins', 2013373959],
['ins', 2361849580],
['ins', 590950523],
['ins', 4250565577],
['has', 1777236018],
['has', 1670145830],
['has', 1941989665],
['has', 815435462],
['has', 223861203],
['has', 2013373959],
['del', 1670145830],
['has', 1670145830],
['has', 3153783919]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[140, 35], [115], [48, 105], [120, 13]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 3783348771],
['ins', 778649113],
['ins', 2658092326],
['ins', 3280724357],
['ins', 509673299],
['ins', 4192536040],
['ins', 3556431545],
['ins', 808068520],
['ins', 4124021509],
['ins', 1279264443],
['ins', 319971617],
['ins', 3929937397],
['ins', 3553621260],
['ins', 3193883894],
['ins', 1614892168],
['ins', 2819704474],
['has', 3783348771],
['has', 778649113],
['has', 2658092326],
['has', 3280724357],
['has', 509673299],
['has', 4192536040],
['del', 778649113],
['has', 778649113],
['has', 20192387]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[48, 158], [211], [168], [225, 30], [211, 245], [195, 249], [190, 19], [76, 234]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1242447109],
['ins', 57101625],
['ins', 1717012336],
['ins', 2477213626],
['ins', 81213852],
['ins', 171443414],
['ins', 1652493013],
['ins', 683056220],
['ins', 434760181],
['ins', 4153897861],
['has', 1242447109],
['has', 57101625],
['has', 1717012336],
['has', 2477213626],
['has', 81213852],
['has', 171443414],
['del', 57101625],
['has', 57101625],
['has', 3654960159]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[102, 4], [25], [147, 10], [98, 74]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 2236733609],
['ins', 3939410963],
['ins', 2724510957],
['ins', 1062065107],
['ins', 2304609820],
['ins', 616512379],
['ins', 3185211465],
['ins', 2149931096],
['ins', 1360730688],
['ins', 1166229974],
['ins', 563851633],
['ins', 1282711990],
['ins', 3774149403],
['ins', 1784829478],
['ins', 517992672],
['ins', 2318531676],
['ins', 723049147],
['ins', 1310520849],
['has', 2236733609],
['has', 3939410963],
['has', 2724510957],
['has', 1062065107],
['has', 2304609820],
['has', 616512379],
['del', 3939410963],
['has', 3939410963],
['has', 487237028]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[63, 128], [133, 189], [76], [224], [137, 33], [162, 81], [106, 30], [36, 69]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 8], ['has', 8], ['ins', 16777224], ['has', 16777224]]},
[['ok', True, 'ok', True], [[1, 1], [], [], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 687865859], ['has', 687865859]]},
[['ok', 'ok', 'ok', True], [[], [], [], [33, 37], [], [], [41], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 4,
'ops': [['ins', 1386070799],
['ins', 3104973709],
['ins', 2606612743],
['ins', 2328394719],
['ins', 4161737019],
['ins', 11222],
['ins', 283246673],
['ins', 3932342861],
['ins', 1826216374],
['has', 1826216374]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', True],
[[155, 185], [16, 82], [1, 108], [138, 248]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 1688258414],
['ins', 1587554040],
['ins', 452842125],
['ins', 2408027354],
['ins', 4039342963],
['ins', 3256509956],
['ins', 2220059300],
['has', 2220059300]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', False], [[94, 194], [26], [100, 143], [240]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 1,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 2508887774],
['ins', 3876506741],
['ins', 2397794896],
['ins', 521281616],
['ins', 1454258696],
['ins', 2418086625],
['ins', 1770269695],
['ins', 3954805098],
['ins', 334587253],
['has', 2508887774],
['has', 3876506741],
['has', 2397794896],
['has', 521281616],
['has', 1454258696],
['has', 2418086625],
['del', 3876506741],
['has', 3876506741],
['has', 1410375853]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[142, 31], [144], [235, 86], [105, 149]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 3626487179],
['ins', 1981200738],
['ins', 3299150810],
['ins', 879079952],
['ins', 569019066],
['ins', 1345246527],
['ins', 1279738884],
['ins', 329365259],
['ins', 3365708295],
['ins', 796732648],
['ins', 4104718778],
['ins', 2034888840],
['ins', 2274417079],
['ins', 3665801012],
['ins', 3713680567],
['ins', 3857873293],
['has', 3626487179],
['has', 1981200738],
['has', 3299150810],
['has', 879079952],
['has', 569019066],
['has', 1345246527],
['del', 1981200738],
['has', 1981200738],
['has', 3276243551]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[52, 47], [], [33], [216, 19], [76, 135], [121, 229], [196, 244], [200, 80]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3383446702],
['ins', 3102517778],
['ins', 551288533],
['ins', 427253337],
['ins', 630972810],
['ins', 261755786],
['ins', 2659101998],
['ins', 4089137114],
['ins', 619206018],
['ins', 827057174],
['has', 3383446702],
['has', 3102517778],
['has', 551288533],
['has', 427253337],
['has', 630972810],
['has', 261755786],
['del', 3102517778],
['has', 3102517778],
['has', 3884327477]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[158, 25], [32, 15], [243], [37, 201]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 576117675],
['ins', 3591995004],
['ins', 857862156],
['ins', 1433687209],
['ins', 301617113],
['ins', 3539330867],
['ins', 4152333277],
['ins', 1466665443],
['ins', 1161213858],
['ins', 2858962672],
['ins', 541647563],
['ins', 3757975831],
['ins', 3381058760],
['ins', 2650519778],
['ins', 1327108968],
['ins', 718689777],
['ins', 2171645977],
['ins', 1707898975],
['has', 576117675],
['has', 3591995004],
['has', 857862156],
['has', 1433687209],
['has', 301617113],
['has', 3539330867],
['del', 3591995004],
['has', 3591995004],
['has', 1355596815]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[87, 170], [85, 34], [69], [32, 210], [17, 51], [247, 201], [], [223, 101]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 9], ['has', 9], ['ins', 16777225], ['has', 16777225]]},
[['ok', True, 'ok', True], [[], [1, 1], [], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410178],
['ins', 1023410178],
['ins', 1023410178],
['del', 1023410178],
['has', 1023410178]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 721420291], ['has', 721420291]]},
[['ok', 'ok', 'ok', True], [[], [], [], [33, 37], [43], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3532591849],
['ins', 3312616903],
['ins', 927288817],
['ins', 436703699],
['ins', 3535596479],
['ins', 271263656],
['ins', 1018485099],
['ins', 1318602685],
['ins', 3734357799],
['has', 3734357799]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', False],
[[16], [210, 210], [197, 55], [60, 26]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 3928427799],
['ins', 841794179],
['ins', 4137117381],
['ins', 2214111069],
['ins', 74342131],
['ins', 2542867317],
['ins', 3143370314],
['has', 3143370314]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True], [[], [246, 131], [151, 187], [234, 50]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 2,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 754608121],
['ins', 1960208437],
['ins', 3951175178],
['ins', 1064988886],
['ins', 3939298075],
['ins', 1095070989],
['ins', 1643589898],
['ins', 3693486421],
['ins', 2812500932],
['has', 754608121],
['has', 1960208437],
['has', 3951175178],
['has', 1064988886],
['has', 3939298075],
['has', 1095070989],
['del', 1960208437],
['has', 1960208437],
['has', 584649671]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[65, 167], [44], [235, 63], [234, 97]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 224567547],
['ins', 2432915099],
['ins', 2215905994],
['ins', 671185022],
['ins', 3716804100],
['ins', 601285828],
['ins', 12858679],
['ins', 3759422002],
['ins', 3853628108],
['ins', 2271239656],
['ins', 3456356083],
['ins', 2687261260],
['ins', 3878729198],
['ins', 3979473486],
['ins', 4034375652],
['ins', 1046284924],
['has', 224567547],
['has', 2432915099],
['has', 2215905994],
['has', 671185022],
['has', 3716804100],
['has', 601285828],
['del', 2432915099],
['has', 2432915099],
['has', 1720764829]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[135], [], [132, 224], [13], [221, 35], [229, 206], [40, 231], [1, 237]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1632830720],
['ins', 1469336575],
['ins', 352685739],
['ins', 384400481],
['ins', 208997603],
['ins', 2690591441],
['ins', 2236537193],
['ins', 3295284666],
['ins', 284313747],
['ins', 324373489],
['has', 1632830720],
['has', 1469336575],
['has', 352685739],
['has', 384400481],
['has', 208997603],
['has', 2690591441],
['del', 1469336575],
['has', 1469336575],
['has', 528732436]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[97], [133, 160], [21, 196], [12, 22]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 1644275844],
['ins', 2900757313],
['ins', 2988486797],
['ins', 179906599],
['ins', 287880722],
['ins', 171405751],
['ins', 3525701444],
['ins', 4108271424],
['ins', 137937707],
['ins', 292658010],
['ins', 248385554],
['ins', 4191124304],
['ins', 2126259745],
['ins', 1346195861],
['ins', 3499831342],
['ins', 3344096474],
['ins', 3832504526],
['ins', 1756343263],
['has', 1644275844],
['has', 2900757313],
['has', 2988486797],
['has', 179906599],
['has', 287880722],
['has', 171405751],
['del', 2900757313],
['has', 2900757313],
['has', 1733874548]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[244, 249], [126], [17, 17], [8], [98, 14], [80, 10], [210, 208], [10, 178]]]],
['zero fingerprint byte',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 10], ['has', 10], ['ins', 16777226], ['has', 16777226]]},
[['ok', True, 'ok', True], [[], [], [1, 1], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 754974723], ['has', 754974723]]},
[['ok', 'ok', 'ok', True], [[], [], [45], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 348667353],
['ins', 1470437433],
['ins', 2596314351],
['ins', 3605354277],
['ins', 2183123397],
['ins', 2831721252],
['ins', 3982916143],
['ins', 1159395843],
['has', 1159395843]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', False],
[[168], [130, 20], [87, 237], [154, 214]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3777452496],
['ins', 4168010152],
['ins', 1415993158],
['ins', 2835527604],
['ins', 2455083042],
['ins', 1654735134],
['ins', 2169901690],
['ins', 1437706628],
['has', 1437706628]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True],
[[225, 248], [169, 85], [84, 146], [129]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 3,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]]]
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 |
|---|---|---|---|
| fill 0 m=4 kicks=3 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[241, 248], [165], [243, 114], [55, 169]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[241, 248], [165], [243, 114], [55, 169]]] | Passed |
| fill 1 m=8 kicks=4 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]] | Passed |
| fill 2 m=4 kicks=2 | [['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', 'ok', 'ok', 'ok', True, True, True, True, False, True, True, False, False], [[91], [63, 15], [235, 123], [225, 34]]] | [['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', 'ok', 'ok', 'ok', True, True, True, True, False, True, True, False, False], [[91], [63, 15], [235, 123], [225, 34]]] | Passed |
| fill 3 m=8 kicks=6 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', 'full', 'full', 'full', True, True, True, True, True, False, True, False, False], [[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', 'full', 'full', 'full', True, True, True, True, True, True, True, False, False], [[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]] | Failed |
| zero fingerprint byte | [['ok', True, 'ok', True], [[], [], [1, 1], []]] | [['ok', True, 'ok', True], [[], [], [1, 1], []]] | Passed |
| triple insert then delete | [['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]] | [['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]] | Passed |
| alternate bucket placement | [['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]] | [['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]] | Passed |
| insert needs full kick budget | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]] | Passed |
| insert rejected at kick budget | [['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False], [[219, 29], [141, 19], [], [82, 226]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False], [[219, 29], [141, 19], [], [82, 226]]] | Passed |
| one-bucket pressure | [['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]] | [['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]] | Passed |
SHA-256 / 658dd7c272623f227cf4f337d42c005dc169abae80207fe48ecfb8761341997d
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
maxk = x['max_kicks']
buckets = [[] for _ in range(m)]
def fp(h):
f = (h >> 24) & 0xFF
return f if f else 1
def alt(i, f):
return (i ^ ((f * 0x5bd1e995) & 0xFFFFFFFF)) & (m - 1)
res = []
for op, h in x['ops']:
f = fp(h)
i1 = h & (m - 1)
i2 = alt(i1, f)
if op == 'ins':
if len(buckets[i1]) < 2:
buckets[i1].append(f)
res.append('ok')
continue
if len(buckets[i2]) < 2:
buckets[i2].append(f)
res.append('ok')
continue
saved = [list(bk) for bk in buckets]
i = i1
placed = False
for n in range(maxk):
slot = n % 2
f, buckets[i][slot] = buckets[i][slot], f
i = alt(i, f)
if len(buckets[i]) < 2:
buckets[i].append(f)
placed = True
break
if placed:
res.append('ok')
else:
buckets = saved
res.append('full')
elif op == 'has':
res.append(f in buckets[i1] or f in buckets[i2])
else:
if f in buckets[i1]:
buckets[i1].remove(f)
res.append(True)
elif f in buckets[i2]:
buckets[i2].remove(f)
res.append(True)
else:
res.append(False)
return [res, buckets]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 4053727168],
['ins', 2090112333],
['ins', 4166861756],
['ins', 2773431433],
['ins', 936790768],
['ins', 4092435925],
['ins', 1926221132],
['ins', 2840737955],
['ins', 2820504097],
['has', 4053727168],
['has', 2090112333],
['has', 4166861756],
['has', 2773431433],
['has', 936790768],
['has', 4092435925],
['del', 2090112333],
['has', 2090112333],
['has', 1631804978]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[241, 248], [165], [243, 114], [55, 169]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 4049152218],
['ins', 4119180372],
['ins', 4174459859],
['ins', 3472142201],
['ins', 2787193319],
['ins', 2868232378],
['ins', 1273646965],
['ins', 169222886],
['ins', 2977310459],
['ins', 1284001336],
['ins', 493096980],
['ins', 2962394317],
['ins', 3792145538],
['ins', 817217868],
['ins', 1471274732],
['ins', 3039844410],
['has', 4049152218],
['has', 4119180372],
['has', 4174459859],
['has', 3472142201],
['has', 2787193319],
['has', 2868232378],
['del', 4119180372],
['has', 4119180372],
['has', 2619116454]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1057150321],
['ins', 249819674],
['ins', 2073545798],
['ins', 263027109],
['ins', 2756491437],
['ins', 3951341878],
['ins', 1961187033],
['ins', 1539010652],
['ins', 3788730431],
['ins', 581588937],
['has', 1057150321],
['has', 249819674],
['has', 2073545798],
['has', 263027109],
['has', 2756491437],
['has', 3951341878],
['del', 249819674],
['has', 249819674],
['has', 2428817573]]},
[['ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
'ok',
'ok',
'ok',
True,
True,
True,
True,
False,
True,
True,
False,
False],
[[91], [63, 15], [235, 123], [225, 34]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 3789782486],
['ins', 313437937],
['ins', 1269036109],
['ins', 3831223018],
['ins', 3169414613],
['ins', 352655826],
['ins', 1455663028],
['ins', 3861257430],
['ins', 2012308387],
['ins', 3682187405],
['ins', 4144766613],
['ins', 1226905701],
['ins', 1648098192],
['ins', 2311553967],
['ins', 1205192322],
['ins', 1075026296],
['ins', 3523968378],
['ins', 620420201],
['has', 3789782486],
['has', 313437937],
['has', 1269036109],
['has', 3831223018],
['has', 3169414613],
['has', 352655826],
['del', 313437937],
['has', 313437937],
['has', 1988851048]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 6], ['has', 6], ['ins', 16777222], ['has', 16777222]]},
[['ok', True, 'ok', True], [[], [], [1, 1], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 620756995], ['has', 620756995]]},
[['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 4,
'ops': [['ins', 2427847248],
['ins', 1880610265],
['ins', 1587388028],
['ins', 1622648335],
['ins', 836275908],
['ins', 2015902217],
['ins', 2680590424],
['has', 2680590424]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 2378664753],
['ins', 333538489],
['ins', 1381905127],
['ins', 3798994753],
['ins', 3675580320],
['ins', 383347823],
['ins', 4040964303],
['ins', 499293357],
['ins', 545063865],
['has', 545063865]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False],
[[219, 29], [141, 19], [], [82, 226]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 2,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 732265847],
['ins', 1810542448],
['ins', 1958173573],
['ins', 1539460854],
['ins', 2114796178],
['ins', 3545636457],
['ins', 4135382597],
['ins', 3892817675],
['ins', 438016941],
['has', 732265847],
['has', 1810542448],
['has', 1958173573],
['has', 1539460854],
['has', 2114796178],
['has', 3545636457],
['del', 1810542448],
['has', 1810542448],
['has', 2049146592]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[43], [116, 211], [91, 126], [232, 246]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 344496995],
['ins', 1850418827],
['ins', 3897751000],
['ins', 3463570078],
['ins', 1162402666],
['ins', 1898656778],
['ins', 383968521],
['ins', 2007988446],
['ins', 281781798],
['ins', 871214629],
['ins', 806266810],
['ins', 3429544281],
['ins', 2010328261],
['ins', 455238739],
['ins', 1620563447],
['ins', 719915703],
['has', 344496995],
['has', 1850418827],
['has', 3897751000],
['has', 3463570078],
['has', 1162402666],
['has', 1898656778],
['del', 1850418827],
['has', 1850418827],
['has', 3035418391]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[232, 206], [22, 204], [48, 51], [20, 69], [27], [119], [16, 119], [113, 96]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 766617118],
['ins', 877620278],
['ins', 4275105416],
['ins', 1303245290],
['ins', 3451862689],
['ins', 2637149561],
['ins', 3479941498],
['ins', 2044492405],
['ins', 2944051255],
['ins', 2216655256],
['has', 766617118],
['has', 877620278],
['has', 4275105416],
['has', 1303245290],
['has', 3451862689],
['has', 2637149561],
['del', 877620278],
['has', 877620278],
['has', 2759628967]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[254, 121], [205, 157], [207], [77, 45]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 639277804],
['ins', 2134252242],
['ins', 564247903],
['ins', 3252176342],
['ins', 2887268535],
['ins', 3809114112],
['ins', 843347271],
['ins', 3790659506],
['ins', 3547675276],
['ins', 738614994],
['ins', 861586606],
['ins', 3332826411],
['ins', 1292373985],
['ins', 2781861741],
['ins', 3516548937],
['ins', 51826789],
['ins', 2496943570],
['ins', 1160646918],
['has', 639277804],
['has', 2134252242],
['has', 564247903],
['has', 3252176342],
['has', 2887268535],
['has', 3809114112],
['del', 2134252242],
['has', 2134252242],
['has', 935263858]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[227, 77], [209], [44, 225], [198, 172], [38, 211], [3, 165], [193, 51], [33, 50]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 7], ['has', 7], ['ins', 16777223], ['has', 16777223]]},
[['ok', True, 'ok', True], [[], [], [], [1, 1]]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410178],
['ins', 1023410178],
['ins', 1023410178],
['del', 1023410178],
['has', 1023410178]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 654311427], ['has', 654311427]]},
[['ok', 'ok', 'ok', True], [[39], [], [], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1091792544],
['ins', 3159258982],
['ins', 6655988],
['ins', 3780476686],
['ins', 3221151820],
['ins', 1354260753],
['ins', 3503243708],
['ins', 2855214902],
['has', 2855214902]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True],
[[208, 1], [80, 65], [170, 188], [191, 225]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 2820483633],
['ins', 2026478793],
['ins', 3254196126],
['ins', 1946366892],
['ins', 1094111634],
['ins', 2388744848],
['ins', 2389839112],
['ins', 515044471],
['ins', 53530770],
['has', 53530770]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True],
[[116, 142], [168, 120], [3, 65], [30, 193]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 3,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1777236018],
['ins', 1670145830],
['ins', 1941989665],
['ins', 815435462],
['ins', 223861203],
['ins', 2013373959],
['ins', 2361849580],
['ins', 590950523],
['ins', 4250565577],
['has', 1777236018],
['has', 1670145830],
['has', 1941989665],
['has', 815435462],
['has', 223861203],
['has', 2013373959],
['del', 1670145830],
['has', 1670145830],
['has', 3153783919]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[140, 35], [115], [48, 105], [120, 13]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 3783348771],
['ins', 778649113],
['ins', 2658092326],
['ins', 3280724357],
['ins', 509673299],
['ins', 4192536040],
['ins', 3556431545],
['ins', 808068520],
['ins', 4124021509],
['ins', 1279264443],
['ins', 319971617],
['ins', 3929937397],
['ins', 3553621260],
['ins', 3193883894],
['ins', 1614892168],
['ins', 2819704474],
['has', 3783348771],
['has', 778649113],
['has', 2658092326],
['has', 3280724357],
['has', 509673299],
['has', 4192536040],
['del', 778649113],
['has', 778649113],
['has', 20192387]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[48, 158], [211], [168], [225, 30], [211, 245], [195, 249], [190, 19], [76, 234]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1242447109],
['ins', 57101625],
['ins', 1717012336],
['ins', 2477213626],
['ins', 81213852],
['ins', 171443414],
['ins', 1652493013],
['ins', 683056220],
['ins', 434760181],
['ins', 4153897861],
['has', 1242447109],
['has', 57101625],
['has', 1717012336],
['has', 2477213626],
['has', 81213852],
['has', 171443414],
['del', 57101625],
['has', 57101625],
['has', 3654960159]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[102, 4], [25], [147, 10], [98, 74]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 2236733609],
['ins', 3939410963],
['ins', 2724510957],
['ins', 1062065107],
['ins', 2304609820],
['ins', 616512379],
['ins', 3185211465],
['ins', 2149931096],
['ins', 1360730688],
['ins', 1166229974],
['ins', 563851633],
['ins', 1282711990],
['ins', 3774149403],
['ins', 1784829478],
['ins', 517992672],
['ins', 2318531676],
['ins', 723049147],
['ins', 1310520849],
['has', 2236733609],
['has', 3939410963],
['has', 2724510957],
['has', 1062065107],
['has', 2304609820],
['has', 616512379],
['del', 3939410963],
['has', 3939410963],
['has', 487237028]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[63, 128], [133, 189], [76], [224], [137, 33], [162, 81], [106, 30], [36, 69]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 8], ['has', 8], ['ins', 16777224], ['has', 16777224]]},
[['ok', True, 'ok', True], [[1, 1], [], [], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 687865859], ['has', 687865859]]},
[['ok', 'ok', 'ok', True], [[], [], [], [33, 37], [], [], [41], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 4,
'ops': [['ins', 1386070799],
['ins', 3104973709],
['ins', 2606612743],
['ins', 2328394719],
['ins', 4161737019],
['ins', 11222],
['ins', 283246673],
['ins', 3932342861],
['ins', 1826216374],
['has', 1826216374]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', True],
[[155, 185], [16, 82], [1, 108], [138, 248]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 1688258414],
['ins', 1587554040],
['ins', 452842125],
['ins', 2408027354],
['ins', 4039342963],
['ins', 3256509956],
['ins', 2220059300],
['has', 2220059300]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', False], [[94, 194], [26], [100, 143], [240]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 1,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 2508887774],
['ins', 3876506741],
['ins', 2397794896],
['ins', 521281616],
['ins', 1454258696],
['ins', 2418086625],
['ins', 1770269695],
['ins', 3954805098],
['ins', 334587253],
['has', 2508887774],
['has', 3876506741],
['has', 2397794896],
['has', 521281616],
['has', 1454258696],
['has', 2418086625],
['del', 3876506741],
['has', 3876506741],
['has', 1410375853]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[142, 31], [144], [235, 86], [105, 149]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 3626487179],
['ins', 1981200738],
['ins', 3299150810],
['ins', 879079952],
['ins', 569019066],
['ins', 1345246527],
['ins', 1279738884],
['ins', 329365259],
['ins', 3365708295],
['ins', 796732648],
['ins', 4104718778],
['ins', 2034888840],
['ins', 2274417079],
['ins', 3665801012],
['ins', 3713680567],
['ins', 3857873293],
['has', 3626487179],
['has', 1981200738],
['has', 3299150810],
['has', 879079952],
['has', 569019066],
['has', 1345246527],
['del', 1981200738],
['has', 1981200738],
['has', 3276243551]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[52, 47], [], [33], [216, 19], [76, 135], [121, 229], [196, 244], [200, 80]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3383446702],
['ins', 3102517778],
['ins', 551288533],
['ins', 427253337],
['ins', 630972810],
['ins', 261755786],
['ins', 2659101998],
['ins', 4089137114],
['ins', 619206018],
['ins', 827057174],
['has', 3383446702],
['has', 3102517778],
['has', 551288533],
['has', 427253337],
['has', 630972810],
['has', 261755786],
['del', 3102517778],
['has', 3102517778],
['has', 3884327477]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[158, 25], [32, 15], [243], [37, 201]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 576117675],
['ins', 3591995004],
['ins', 857862156],
['ins', 1433687209],
['ins', 301617113],
['ins', 3539330867],
['ins', 4152333277],
['ins', 1466665443],
['ins', 1161213858],
['ins', 2858962672],
['ins', 541647563],
['ins', 3757975831],
['ins', 3381058760],
['ins', 2650519778],
['ins', 1327108968],
['ins', 718689777],
['ins', 2171645977],
['ins', 1707898975],
['has', 576117675],
['has', 3591995004],
['has', 857862156],
['has', 1433687209],
['has', 301617113],
['has', 3539330867],
['del', 3591995004],
['has', 3591995004],
['has', 1355596815]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[87, 170], [85, 34], [69], [32, 210], [17, 51], [247, 201], [], [223, 101]]]],
['zero fingerprint byte',
{'m': 4, 'max_kicks': 3, 'ops': [['ins', 9], ['has', 9], ['ins', 16777225], ['has', 16777225]]},
[['ok', True, 'ok', True], [[], [1, 1], [], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410178],
['ins', 1023410178],
['ins', 1023410178],
['del', 1023410178],
['has', 1023410178]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 721420291], ['has', 721420291]]},
[['ok', 'ok', 'ok', True], [[], [], [], [33, 37], [43], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3532591849],
['ins', 3312616903],
['ins', 927288817],
['ins', 436703699],
['ins', 3535596479],
['ins', 271263656],
['ins', 1018485099],
['ins', 1318602685],
['ins', 3734357799],
['has', 3734357799]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', False],
[[16], [210, 210], [197, 55], [60, 26]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 1,
'ops': [['ins', 3928427799],
['ins', 841794179],
['ins', 4137117381],
['ins', 2214111069],
['ins', 74342131],
['ins', 2542867317],
['ins', 3143370314],
['has', 3143370314]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True], [[], [246, 131], [151, 187], [234, 50]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 2,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]],
[['fill 0 m=4 kicks=3',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 754608121],
['ins', 1960208437],
['ins', 3951175178],
['ins', 1064988886],
['ins', 3939298075],
['ins', 1095070989],
['ins', 1643589898],
['ins', 3693486421],
['ins', 2812500932],
['has', 754608121],
['has', 1960208437],
['has', 3951175178],
['has', 1064988886],
['has', 3939298075],
['has', 1095070989],
['del', 1960208437],
['has', 1960208437],
['has', 584649671]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[65, 167], [44], [235, 63], [234, 97]]]],
['fill 1 m=8 kicks=4',
{'m': 8,
'max_kicks': 4,
'ops': [['ins', 224567547],
['ins', 2432915099],
['ins', 2215905994],
['ins', 671185022],
['ins', 3716804100],
['ins', 601285828],
['ins', 12858679],
['ins', 3759422002],
['ins', 3853628108],
['ins', 2271239656],
['ins', 3456356083],
['ins', 2687261260],
['ins', 3878729198],
['ins', 3979473486],
['ins', 4034375652],
['ins', 1046284924],
['has', 224567547],
['has', 2432915099],
['has', 2215905994],
['has', 671185022],
['has', 3716804100],
['has', 601285828],
['del', 2432915099],
['has', 2432915099],
['has', 1720764829]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[135], [], [132, 224], [13], [221, 35], [229, 206], [40, 231], [1, 237]]]],
['fill 2 m=4 kicks=2',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 1632830720],
['ins', 1469336575],
['ins', 352685739],
['ins', 384400481],
['ins', 208997603],
['ins', 2690591441],
['ins', 2236537193],
['ins', 3295284666],
['ins', 284313747],
['ins', 324373489],
['has', 1632830720],
['has', 1469336575],
['has', 352685739],
['has', 384400481],
['has', 208997603],
['has', 2690591441],
['del', 1469336575],
['has', 1469336575],
['has', 528732436]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[97], [133, 160], [21, 196], [12, 22]]]],
['fill 3 m=8 kicks=6',
{'m': 8,
'max_kicks': 6,
'ops': [['ins', 1644275844],
['ins', 2900757313],
['ins', 2988486797],
['ins', 179906599],
['ins', 287880722],
['ins', 171405751],
['ins', 3525701444],
['ins', 4108271424],
['ins', 137937707],
['ins', 292658010],
['ins', 248385554],
['ins', 4191124304],
['ins', 2126259745],
['ins', 1346195861],
['ins', 3499831342],
['ins', 3344096474],
['ins', 3832504526],
['ins', 1756343263],
['has', 1644275844],
['has', 2900757313],
['has', 2988486797],
['has', 179906599],
['has', 287880722],
['has', 171405751],
['del', 2900757313],
['has', 2900757313],
['has', 1733874548]]},
[['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'full',
'full',
'full',
True,
True,
True,
True,
True,
True,
True,
False,
False],
[[244, 249], [126], [17, 17], [8], [98, 14], [80, 10], [210, 208], [10, 178]]]],
['zero fingerprint byte',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 10], ['has', 10], ['ins', 16777226], ['has', 16777226]]},
[['ok', True, 'ok', True], [[], [], [1, 1], []]]],
['triple insert then delete',
{'m': 4,
'max_kicks': 3,
'ops': [['ins', 1023410179],
['ins', 1023410179],
['ins', 1023410179],
['del', 1023410179],
['has', 1023410179]]},
[['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]]],
['alternate bucket placement',
{'m': 8,
'max_kicks': 2,
'ops': [['ins', 553648131], ['ins', 620756995], ['ins', 754974723], ['has', 754974723]]},
[['ok', 'ok', 'ok', True], [[], [], [45], [33, 37], [], [], [], []]]],
['insert needs full kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 348667353],
['ins', 1470437433],
['ins', 2596314351],
['ins', 3605354277],
['ins', 2183123397],
['ins', 2831721252],
['ins', 3982916143],
['ins', 1159395843],
['has', 1159395843]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', False],
[[168], [130, 20], [87, 237], [154, 214]]]],
['insert rejected at kick budget',
{'m': 4,
'max_kicks': 2,
'ops': [['ins', 3777452496],
['ins', 4168010152],
['ins', 1415993158],
['ins', 2835527604],
['ins', 2455083042],
['ins', 1654735134],
['ins', 2169901690],
['ins', 1437706628],
['has', 1437706628]]},
[['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', True],
[[225, 248], [169, 85], [84, 146], [129]]]],
['one-bucket pressure',
{'m': 2,
'max_kicks': 3,
'ops': [['ins', 285212673],
['ins', 570425345],
['ins', 855638017],
['ins', 1140850689],
['ins', 1426063361],
['ins', 1711276033],
['has', 285212673],
['has', 1711276033]]},
[['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]]]]]
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 |
|---|---|---|---|
| fill 0 m=4 kicks=3 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[241, 248], [165], [243, 114], [55, 169]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[241, 248], [165], [243, 114], [55, 169]]] | Passed |
| fill 1 m=8 kicks=4 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', True, True, True, True, True, True, True, False, False], [[76, 226], [206], [241, 170], [248, 177], [29], [75, 176], [10], [166, 87]]] | Passed |
| fill 2 m=4 kicks=2 | [['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', 'ok', 'ok', 'ok', True, True, True, True, False, True, True, False, False], [[91], [63, 15], [235, 123], [225, 34]]] | [['ok', 'ok', 'ok', 'ok', 'full', 'ok', 'full', 'ok', 'ok', 'ok', True, True, True, True, False, True, True, False, False], [[91], [63, 15], [235, 123], [225, 34]]] | Passed |
| fill 3 m=8 kicks=6 | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', 'full', 'full', 'full', True, True, True, True, True, True, True, False, False], [[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'full', 'ok', 'ok', 'full', 'full', 'full', True, True, True, True, True, True, True, False, False], [[230, 73], [71], [228, 219], [119, 21], [86], [75, 188], [225, 247], [137]]] | Passed |
| zero fingerprint byte | [['ok', True, 'ok', True], [[], [], [1, 1], []]] | [['ok', True, 'ok', True], [[], [], [1, 1], []]] | Passed |
| triple insert then delete | [['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]] | [['ok', 'ok', 'ok', True, True], [[], [], [61], [61]]] | Passed |
| alternate bucket placement | [['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]] | [['ok', 'ok', 'ok', True], [[], [], [37], [33, 37], [], [], [], []]] | Passed |
| insert needs full kick budget | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', True], [[49, 144], [120, 112], [94], [96, 159]]] | Passed |
| insert rejected at kick budget | [['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False], [[219, 29], [141, 19], [], [82, 226]]] | [['ok', 'ok', 'ok', 'ok', 'ok', 'full', 'full', 'ok', 'full', False], [[219, 29], [141, 19], [], [82, 226]]] | Passed |
| one-bucket pressure | [['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]] | [['ok', 'ok', 'ok', 'ok', 'full', 'full', True, False], [[51, 17], [68, 34]]] | Passed |
SHA-256 / c73990fc1d9b9e34d7e3f942a52433612304b6c19cf3d505335ffd505fcb64f9
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:46.103939+00:00.
Case digest / 88a6007f3865c12be0b2c795d3e2c7356f8d2959a462d15fc1630c0f151f7a80