FA-72861 / Probabilistic sketches / Open access
Bloom filter with double hashing: hash consumes code points instead of UTF-8 bytes · case 01
Non-ASCII keys map to different bits than in the reference writer, producing false negatives across implementations.
ROOT CAUSE
The FNV loop iterates Unicode code points instead of the UTF-8 byte sequence required by the contract.
THE FAILURE
The FNV loop iterates Unicode code points instead of the UTF-8 byte sequence required by the contract.
Unsuccessful approach: Latin-1 encoding still emits one byte per accented character instead of the UTF-8 multi-byte sequence.
Case contract
Input {m, k, add, query}. Each string is hashed with 32-bit FNV-1a over its UTF-8 bytes using seed 0 (h1) and seed 0x5bd1e995 (h2); h2 is forced odd by OR-ing 1. Probe i for i in 0..k-1 is ((h1 + i*h2) mod 2^32) mod m. Return [sorted set bit indices, membership booleans for query] where membership requires every probe bit.
Why this case matters
Bloom filters built with Kirsch-Mitzenmacher double hashing must reproduce the exact same probe sequence across writers and readers; any drift silently changes the bit layout.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
def fnv(s, seed):
h = (2166136261 ^ seed) & 0xFFFFFFFF
for b in map(ord, s):
h = ((h ^ b) * 16777619) & 0xFFFFFFFF
return h
def probes(s):
h1 = fnv(s, 0)
h2 = fnv(s, 0x5bd1e995) | 1
return [((h1 + i * h2) & 0xFFFFFFFF) % m for i in range(k)]
bits = [0] * m
for s in x['add']:
for p in probes(s):
bits[p] = 1
hits = [all(bits[p] for p in probes(s)) for s in x['query']]
return [[i for i in range(m) if bits[i]], hits]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['bloom 0 m=62 k=3',
{'add': ['smörgås', 'ember', 'eta', 'jalapeño', 'straße'],
'k': 3,
'm': 62,
'query': ['smörgås', 'ember', 'mu', 'straße', 'beta', 'south']},
[[0, 1, 15, 16, 18, 19, 20, 23, 26, 43, 46, 49, 51, 52, 56],
[True, True, True, True, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['crème', 'eta', 'øre', 'theta', 'kappa', 'jalapeño'],
'k': 4,
'm': 64,
'query': ['crème', 'eta', 'übung', 'east', 'frost', 'lambda']},
[[0, 1, 6, 8, 10, 17, 19, 20, 23, 26, 27, 30, 32, 37, 39, 41, 44, 46, 57, 61, 63],
[True, True, False, False, False, False]]],
['bloom 2 m=39 k=2',
{'add': ['straße', 'gamma', 'iota', 'øre'],
'k': 2,
'm': 39,
'query': ['straße', 'gamma', 'eta', 'zeta', 'frost', 'grove']},
[[0, 1, 3, 4, 7, 21, 27], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['river', 'jalapeño', 'mu', 'eta', 'übung', 'lambda', 'übung'],
'k': 5,
'm': 29,
'query': ['river', 'jalapeño', 'theta', 'north', 'café', 'naïve']},
[[0, 3, 5, 8, 9, 10, 11, 13, 14, 15, 16, 17, 20, 21, 22, 24, 25, 28],
[True, True, False, True, False, False]]],
['bloom 4 m=101 k=3',
{'add': ['eta', 'gamma', 'naïve', 'straße', 'kappa', 'grove', 'delta', 'café'],
'k': 3,
'm': 101,
'query': ['eta', 'gamma', 'north', 'øre', 'lambda', 'iota']},
[[1, 16, 19, 20, 23, 28, 36, 44, 46, 50, 52, 53, 66, 74, 79, 80, 82, 83, 84, 86, 94],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['café', 'stone', 'grove', 'straße'],
'k': 2,
'm': 16,
'query': ['café', 'stone', 'theta', 'naïve', 'gamma', 'ember']},
[[0, 3, 8, 9, 10, 15], [True, True, False, False, False, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 24, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=63 k=3',
{'add': ['epsilon', 'south', 'øre', 'mu', 'jalapeño'],
'k': 3,
'm': 63,
'query': ['epsilon', 'south', 'zeta', 'jalapeño', 'east', 'frost']},
[[3, 13, 15, 18, 26, 27, 30, 34, 46, 48, 54, 56, 58], [True, True, False, True, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['øre', 'zeta', 'café', 'kappa', 'grove', 'øre'],
'k': 4,
'm': 64,
'query': ['øre', 'zeta', 'naïve', 'smörgås', 'west', 'beta']},
[[0, 1, 6, 8, 9, 14, 19, 21, 24, 27, 31, 32, 38, 42, 44, 45, 46, 55, 57, 63],
[True, True, False, False, False, False]]],
['bloom 2 m=41 k=2',
{'add': ['west', 'crème', 'jalapeño', 'übung'],
'k': 2,
'm': 41,
'query': ['west', 'crème', 'øre', 'grove', 'frost', 'zeta']},
[[3, 15, 21, 23, 26, 27, 40], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['west', 'stone', 'café', 'straße', 'theta', 'crème', 'café'],
'k': 5,
'm': 29,
'query': ['west', 'stone', 'epsilon', 'gamma', 'beta', 'zeta']},
[[0, 1, 2, 6, 7, 9, 10, 11, 12, 13, 14, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27],
[True, True, True, False, False, False]]],
['bloom 4 m=102 k=3',
{'add': ['øre', 'smörgås', 'straße', 'crème', 'theta', 'east', 'cloud', 'straße'],
'k': 3,
'm': 102,
'query': ['øre', 'smörgås', 'west', 'epsilon', 'übung', 'grove']},
[[2, 7, 8, 16, 30, 31, 36, 39, 42, 49, 53, 60, 62, 63, 64, 75, 84, 89, 94],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['naïve', 'north', 'übung', 'jalapeño'],
'k': 2,
'm': 16,
'query': ['naïve', 'north', 'south', 'gamma', 'theta', 'øre']},
[[1, 2, 4, 7, 11], [True, True, False, False, False, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 25, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=64 k=3',
{'add': ['east', 'straße', 'west', 'grove', 'øre'],
'k': 3,
'm': 64,
'query': ['east', 'straße', 'ember', 'eta', 'cloud', 'gamma']},
[[3, 6, 19, 24, 25, 31, 38, 46, 53, 54, 57, 60], [True, True, False, False, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['grove', 'øre', 'west', 'delta', 'north', 'übung'],
'k': 4,
'm': 64,
'query': ['grove', 'øre', 'café', 'straße', 'lambda', 'south']},
[[1, 3, 4, 6, 14, 15, 19, 23, 24, 27, 31, 33, 38, 42, 44, 45, 46, 52, 53, 57, 60, 61],
[True, True, False, False, False, False]]],
['bloom 2 m=43 k=2',
{'add': ['delta', 'übung', 'gamma', 'café'],
'k': 2,
'm': 43,
'query': ['delta', 'übung', 'epsilon', 'theta', 'smörgås', 'alpha']},
[[0, 3, 4, 8, 18, 23, 29, 31], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['beta', 'theta', 'delta', 'east', 'epsilon', 'øre', 'straße'],
'k': 5,
'm': 29,
'query': ['beta', 'theta', 'crème', 'kappa', 'zeta', 'naïve']},
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 25, 28],
[True, True, False, True, False, False]]],
['bloom 4 m=103 k=3',
{'add': ['ember', 'west', 'smörgås', 'frost', 'south', 'naïve', 'theta', 'jalapeño'],
'k': 3,
'm': 103,
'query': ['ember', 'west', 'stone', 'grove', 'øre', 'cloud']},
[[0, 5, 6, 14, 15, 16, 23, 25, 31, 37, 48, 54, 59, 60, 72, 74, 77, 78, 80, 93, 94, 95],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['gamma', 'mu', 'eta', 'øre'],
'k': 2,
'm': 16,
'query': ['gamma', 'mu', 'smörgås', 'ember', 'east', 'øre']},
[[3, 6, 7, 8, 10, 11, 14], [True, True, False, False, False, True]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 26, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=65 k=3',
{'add': ['alpha', 'ember', 'eta', 'west', 'übung'],
'k': 3,
'm': 65,
'query': ['alpha', 'ember', 'river', 'theta', 'café', 'lambda']},
[[0, 6, 7, 9, 14, 15, 16, 26, 28, 37, 47, 49, 56, 64],
[True, True, False, False, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['alpha', 'east', 'epsilon', 'stone', 'grove', 'café'],
'k': 4,
'm': 64,
'query': ['alpha', 'east', 'zeta', 'delta', 'ember', 'west']},
[[9, 14, 16, 19, 24, 25, 26, 29, 31, 32, 36, 38, 43, 45, 47, 53, 54, 55, 58, 60],
[True, True, False, False, False, False]]],
['bloom 2 m=45 k=2',
{'add': ['gamma', 'north', 'river', 'straße'],
'k': 2,
'm': 45,
'query': ['gamma', 'north', 'lambda', 'mu', 'frost', 'beta']},
[[8, 9, 18, 19, 27, 29, 33], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['ember', 'eta', 'smörgås', 'iota', 'café', 'lambda', 'jalapeño'],
'k': 5,
'm': 29,
'query': ['ember', 'eta', 'øre', 'zeta', 'north', 'kappa']},
[[0, 3, 5, 7, 9, 10, 12, 13, 14, 15, 17, 19, 20, 21, 24, 25],
[True, True, False, False, False, False]]],
['bloom 4 m=104 k=3',
{'add': ['naïve', 'beta', 'straße', 'ember', 'jalapeño', 'theta', 'iota', 'øre'],
'k': 3,
'm': 104,
'query': ['naïve', 'beta', 'zeta', 'smörgås', 'frost', 'delta']},
[[0, 8, 9, 11, 16, 28, 30, 31, 34, 37, 47, 49, 52, 53, 57, 67, 78, 82, 87, 90, 93, 98, 99],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['beta', 'øre', 'stone', 'übung'],
'k': 2,
'm': 16,
'query': ['beta', 'øre', 'ember', 'delta', 'zeta', 'iota']},
[[1, 3, 4, 6, 7, 10, 15], [True, True, True, False, True, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 27, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=66 k=3',
{'add': ['frost', 'smörgås', 'mu', 'grove', 'café'],
'k': 3,
'm': 66,
'query': ['frost', 'smörgås', 'stone', 'delta', 'alpha', 'kappa']},
[[0, 6, 14, 29, 33, 36, 37, 41, 45, 46, 51, 55, 58, 61, 62],
[True, True, False, False, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['crème', 'river', 'smörgås', 'lambda', 'kappa', 'straße'],
'k': 4,
'm': 64,
'query': ['crème', 'river', 'zeta', 'mu', 'frost', 'epsilon']},
[[1, 3, 6, 8, 11, 16, 17, 18, 24, 25, 27, 30, 32, 37, 39, 42, 46, 60, 61, 63],
[True, True, False, False, False, False]]],
['bloom 2 m=47 k=2',
{'add': ['delta', 'south', 'café', 'jalapeño'],
'k': 2,
'm': 47,
'query': ['delta', 'south', 'mu', 'zeta', 'naïve', 'øre']},
[[0, 2, 11, 30, 35, 40, 43], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['café', 'cloud', 'straße', 'übung', 'south', 'theta', 'øre'],
'k': 5,
'm': 29,
'query': ['café', 'cloud', 'east', 'zeta', 'øre', 'kappa']},
[[1, 2, 4, 6, 7, 10, 11, 12, 13, 14, 16, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28],
[True, True, False, False, True, False]]],
['bloom 4 m=105 k=3',
{'add': ['grove', 'cloud', 'crème', 'iota', 'beta', 'lambda', 'øre', 'übung'],
'k': 3,
'm': 105,
'query': ['grove', 'cloud', 'delta', 'mu', 'zeta', 'café']},
[[2, 4, 10, 11, 15, 20, 31, 38, 61, 66, 67, 69, 72, 73, 74, 77, 78, 80, 81, 88, 91],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['jalapeño', 'frost', 'crème', 'café'],
'k': 2,
'm': 16,
'query': ['jalapeño', 'frost', 'smörgås', 'river', 'north', 'stone']},
[[0, 1, 4, 8, 9, 13, 14], [True, True, False, False, False, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 28, 'query': ['alpha', 'mu']},
[[], [False, False]]]]]
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 |
|---|---|---|---|
| bloom 0 m=62 k=3 | [[0, 1, 8, 15, 16, 18, 29, 43, 48, 49, 50, 53, 56, 60, 61], [True, True, False, True, False, False]] | [[0, 1, 15, 16, 18, 19, 20, 23, 26, 43, 46, 49, 51, 52, 56], [True, True, True, True, False, False]] | Failed |
| bloom 1 m=64 k=4 | [[0, 1, 8, 10, 19, 24, 27, 29, 37, 39, 40, 41, 42, 46, 51, 62, 63], [True, True, False, False, False, False]] | [[0, 1, 6, 8, 10, 17, 19, 20, 23, 26, 27, 30, 32, 37, 39, 41, 44, 46, 57, 61, 63], [True, True, False, False, False, False]] | Failed |
| bloom 2 m=39 k=2 | [[0, 1, 7, 23, 27, 36, 38], [True, True, True, False, False, False]] | [[0, 1, 3, 4, 7, 21, 27], [True, True, False, False, False, False]] | Failed |
| bloom 3 m=29 k=5 | [[0, 3, 5, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 28], [True, True, False, True, False, True]] | [[0, 3, 5, 8, 9, 10, 11, 13, 14, 15, 16, 17, 20, 21, 22, 24, 25, 28], [True, True, False, True, False, False]] | Failed |
| bloom 4 m=101 k=3 | [[1, 16, 19, 25, 31, 36, 44, 49, 50, 52, 53, 62, 66, 68, 74, 75, 79, 80, 82, 84, 87, 94, 100], [True, True, False, False, False, False]] | [[1, 16, 19, 20, 23, 28, 36, 44, 46, 50, 52, 53, 66, 74, 79, 80, 82, 83, 84, 86, 94], [True, True, False, False, False, False]] | Failed |
| bloom 5 m=16 k=2 | [[2, 3, 5, 8, 10, 12, 15], [True, True, False, True, False, False]] | [[0, 3, 8, 9, 10, 15], [True, True, False, False, False, False]] | Failed |
| empty filter rejects everything | [[], [False, False]] | [[], [False, False]] | Passed |
SHA-256 / 8a139790bcf7cc6d8df97490e4b3f2c79981515724605d78885404b75ed7219a
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']
k = x['k']
def fnv(s, seed):
h = (2166136261 ^ seed) & 0xFFFFFFFF
for b in s.encode('latin-1', 'replace'):
h = ((h ^ b) * 16777619) & 0xFFFFFFFF
return h
def probes(s):
h1 = fnv(s, 0)
h2 = fnv(s, 0x5bd1e995) | 1
return [((h1 + i * h2) & 0xFFFFFFFF) % m for i in range(k)]
bits = [0] * m
for s in x['add']:
for p in probes(s):
bits[p] = 1
hits = [all(bits[p] for p in probes(s)) for s in x['query']]
return [[i for i in range(m) if bits[i]], hits]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['bloom 0 m=62 k=3',
{'add': ['smörgås', 'ember', 'eta', 'jalapeño', 'straße'],
'k': 3,
'm': 62,
'query': ['smörgås', 'ember', 'mu', 'straße', 'beta', 'south']},
[[0, 1, 15, 16, 18, 19, 20, 23, 26, 43, 46, 49, 51, 52, 56],
[True, True, True, True, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['crème', 'eta', 'øre', 'theta', 'kappa', 'jalapeño'],
'k': 4,
'm': 64,
'query': ['crème', 'eta', 'übung', 'east', 'frost', 'lambda']},
[[0, 1, 6, 8, 10, 17, 19, 20, 23, 26, 27, 30, 32, 37, 39, 41, 44, 46, 57, 61, 63],
[True, True, False, False, False, False]]],
['bloom 2 m=39 k=2',
{'add': ['straße', 'gamma', 'iota', 'øre'],
'k': 2,
'm': 39,
'query': ['straße', 'gamma', 'eta', 'zeta', 'frost', 'grove']},
[[0, 1, 3, 4, 7, 21, 27], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['river', 'jalapeño', 'mu', 'eta', 'übung', 'lambda', 'übung'],
'k': 5,
'm': 29,
'query': ['river', 'jalapeño', 'theta', 'north', 'café', 'naïve']},
[[0, 3, 5, 8, 9, 10, 11, 13, 14, 15, 16, 17, 20, 21, 22, 24, 25, 28],
[True, True, False, True, False, False]]],
['bloom 4 m=101 k=3',
{'add': ['eta', 'gamma', 'naïve', 'straße', 'kappa', 'grove', 'delta', 'café'],
'k': 3,
'm': 101,
'query': ['eta', 'gamma', 'north', 'øre', 'lambda', 'iota']},
[[1, 16, 19, 20, 23, 28, 36, 44, 46, 50, 52, 53, 66, 74, 79, 80, 82, 83, 84, 86, 94],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['café', 'stone', 'grove', 'straße'],
'k': 2,
'm': 16,
'query': ['café', 'stone', 'theta', 'naïve', 'gamma', 'ember']},
[[0, 3, 8, 9, 10, 15], [True, True, False, False, False, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 24, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=63 k=3',
{'add': ['epsilon', 'south', 'øre', 'mu', 'jalapeño'],
'k': 3,
'm': 63,
'query': ['epsilon', 'south', 'zeta', 'jalapeño', 'east', 'frost']},
[[3, 13, 15, 18, 26, 27, 30, 34, 46, 48, 54, 56, 58], [True, True, False, True, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['øre', 'zeta', 'café', 'kappa', 'grove', 'øre'],
'k': 4,
'm': 64,
'query': ['øre', 'zeta', 'naïve', 'smörgås', 'west', 'beta']},
[[0, 1, 6, 8, 9, 14, 19, 21, 24, 27, 31, 32, 38, 42, 44, 45, 46, 55, 57, 63],
[True, True, False, False, False, False]]],
['bloom 2 m=41 k=2',
{'add': ['west', 'crème', 'jalapeño', 'übung'],
'k': 2,
'm': 41,
'query': ['west', 'crème', 'øre', 'grove', 'frost', 'zeta']},
[[3, 15, 21, 23, 26, 27, 40], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['west', 'stone', 'café', 'straße', 'theta', 'crème', 'café'],
'k': 5,
'm': 29,
'query': ['west', 'stone', 'epsilon', 'gamma', 'beta', 'zeta']},
[[0, 1, 2, 6, 7, 9, 10, 11, 12, 13, 14, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27],
[True, True, True, False, False, False]]],
['bloom 4 m=102 k=3',
{'add': ['øre', 'smörgås', 'straße', 'crème', 'theta', 'east', 'cloud', 'straße'],
'k': 3,
'm': 102,
'query': ['øre', 'smörgås', 'west', 'epsilon', 'übung', 'grove']},
[[2, 7, 8, 16, 30, 31, 36, 39, 42, 49, 53, 60, 62, 63, 64, 75, 84, 89, 94],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['naïve', 'north', 'übung', 'jalapeño'],
'k': 2,
'm': 16,
'query': ['naïve', 'north', 'south', 'gamma', 'theta', 'øre']},
[[1, 2, 4, 7, 11], [True, True, False, False, False, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 25, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=64 k=3',
{'add': ['east', 'straße', 'west', 'grove', 'øre'],
'k': 3,
'm': 64,
'query': ['east', 'straße', 'ember', 'eta', 'cloud', 'gamma']},
[[3, 6, 19, 24, 25, 31, 38, 46, 53, 54, 57, 60], [True, True, False, False, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['grove', 'øre', 'west', 'delta', 'north', 'übung'],
'k': 4,
'm': 64,
'query': ['grove', 'øre', 'café', 'straße', 'lambda', 'south']},
[[1, 3, 4, 6, 14, 15, 19, 23, 24, 27, 31, 33, 38, 42, 44, 45, 46, 52, 53, 57, 60, 61],
[True, True, False, False, False, False]]],
['bloom 2 m=43 k=2',
{'add': ['delta', 'übung', 'gamma', 'café'],
'k': 2,
'm': 43,
'query': ['delta', 'übung', 'epsilon', 'theta', 'smörgås', 'alpha']},
[[0, 3, 4, 8, 18, 23, 29, 31], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['beta', 'theta', 'delta', 'east', 'epsilon', 'øre', 'straße'],
'k': 5,
'm': 29,
'query': ['beta', 'theta', 'crème', 'kappa', 'zeta', 'naïve']},
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 25, 28],
[True, True, False, True, False, False]]],
['bloom 4 m=103 k=3',
{'add': ['ember', 'west', 'smörgås', 'frost', 'south', 'naïve', 'theta', 'jalapeño'],
'k': 3,
'm': 103,
'query': ['ember', 'west', 'stone', 'grove', 'øre', 'cloud']},
[[0, 5, 6, 14, 15, 16, 23, 25, 31, 37, 48, 54, 59, 60, 72, 74, 77, 78, 80, 93, 94, 95],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['gamma', 'mu', 'eta', 'øre'],
'k': 2,
'm': 16,
'query': ['gamma', 'mu', 'smörgås', 'ember', 'east', 'øre']},
[[3, 6, 7, 8, 10, 11, 14], [True, True, False, False, False, True]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 26, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=65 k=3',
{'add': ['alpha', 'ember', 'eta', 'west', 'übung'],
'k': 3,
'm': 65,
'query': ['alpha', 'ember', 'river', 'theta', 'café', 'lambda']},
[[0, 6, 7, 9, 14, 15, 16, 26, 28, 37, 47, 49, 56, 64],
[True, True, False, False, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['alpha', 'east', 'epsilon', 'stone', 'grove', 'café'],
'k': 4,
'm': 64,
'query': ['alpha', 'east', 'zeta', 'delta', 'ember', 'west']},
[[9, 14, 16, 19, 24, 25, 26, 29, 31, 32, 36, 38, 43, 45, 47, 53, 54, 55, 58, 60],
[True, True, False, False, False, False]]],
['bloom 2 m=45 k=2',
{'add': ['gamma', 'north', 'river', 'straße'],
'k': 2,
'm': 45,
'query': ['gamma', 'north', 'lambda', 'mu', 'frost', 'beta']},
[[8, 9, 18, 19, 27, 29, 33], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['ember', 'eta', 'smörgås', 'iota', 'café', 'lambda', 'jalapeño'],
'k': 5,
'm': 29,
'query': ['ember', 'eta', 'øre', 'zeta', 'north', 'kappa']},
[[0, 3, 5, 7, 9, 10, 12, 13, 14, 15, 17, 19, 20, 21, 24, 25],
[True, True, False, False, False, False]]],
['bloom 4 m=104 k=3',
{'add': ['naïve', 'beta', 'straße', 'ember', 'jalapeño', 'theta', 'iota', 'øre'],
'k': 3,
'm': 104,
'query': ['naïve', 'beta', 'zeta', 'smörgås', 'frost', 'delta']},
[[0, 8, 9, 11, 16, 28, 30, 31, 34, 37, 47, 49, 52, 53, 57, 67, 78, 82, 87, 90, 93, 98, 99],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['beta', 'øre', 'stone', 'übung'],
'k': 2,
'm': 16,
'query': ['beta', 'øre', 'ember', 'delta', 'zeta', 'iota']},
[[1, 3, 4, 6, 7, 10, 15], [True, True, True, False, True, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 27, 'query': ['alpha', 'mu']},
[[], [False, False]]]],
[['bloom 0 m=66 k=3',
{'add': ['frost', 'smörgås', 'mu', 'grove', 'café'],
'k': 3,
'm': 66,
'query': ['frost', 'smörgås', 'stone', 'delta', 'alpha', 'kappa']},
[[0, 6, 14, 29, 33, 36, 37, 41, 45, 46, 51, 55, 58, 61, 62],
[True, True, False, False, False, False]]],
['bloom 1 m=64 k=4',
{'add': ['crème', 'river', 'smörgås', 'lambda', 'kappa', 'straße'],
'k': 4,
'm': 64,
'query': ['crème', 'river', 'zeta', 'mu', 'frost', 'epsilon']},
[[1, 3, 6, 8, 11, 16, 17, 18, 24, 25, 27, 30, 32, 37, 39, 42, 46, 60, 61, 63],
[True, True, False, False, False, False]]],
['bloom 2 m=47 k=2',
{'add': ['delta', 'south', 'café', 'jalapeño'],
'k': 2,
'm': 47,
'query': ['delta', 'south', 'mu', 'zeta', 'naïve', 'øre']},
[[0, 2, 11, 30, 35, 40, 43], [True, True, False, False, False, False]]],
['bloom 3 m=29 k=5',
{'add': ['café', 'cloud', 'straße', 'übung', 'south', 'theta', 'øre'],
'k': 5,
'm': 29,
'query': ['café', 'cloud', 'east', 'zeta', 'øre', 'kappa']},
[[1, 2, 4, 6, 7, 10, 11, 12, 13, 14, 16, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28],
[True, True, False, False, True, False]]],
['bloom 4 m=105 k=3',
{'add': ['grove', 'cloud', 'crème', 'iota', 'beta', 'lambda', 'øre', 'übung'],
'k': 3,
'm': 105,
'query': ['grove', 'cloud', 'delta', 'mu', 'zeta', 'café']},
[[2, 4, 10, 11, 15, 20, 31, 38, 61, 66, 67, 69, 72, 73, 74, 77, 78, 80, 81, 88, 91],
[True, True, False, False, False, False]]],
['bloom 5 m=16 k=2',
{'add': ['jalapeño', 'frost', 'crème', 'café'],
'k': 2,
'm': 16,
'query': ['jalapeño', 'frost', 'smörgås', 'river', 'north', 'stone']},
[[0, 1, 4, 8, 9, 13, 14], [True, True, False, False, False, False]]],
['empty filter rejects everything',
{'add': [], 'k': 3, 'm': 28, 'query': ['alpha', 'mu']},
[[], [False, False]]]]]
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 |
|---|---|---|---|
| bloom 0 m=62 k=3 | [[0, 1, 8, 15, 16, 18, 29, 43, 48, 49, 50, 53, 56, 60, 61], [True, True, False, True, False, False]] | [[0, 1, 15, 16, 18, 19, 20, 23, 26, 43, 46, 49, 51, 52, 56], [True, True, True, True, False, False]] | Failed |
| bloom 1 m=64 k=4 | [[0, 1, 8, 10, 19, 24, 27, 29, 37, 39, 40, 41, 42, 46, 51, 62, 63], [True, True, False, False, False, False]] | [[0, 1, 6, 8, 10, 17, 19, 20, 23, 26, 27, 30, 32, 37, 39, 41, 44, 46, 57, 61, 63], [True, True, False, False, False, False]] | Failed |
| bloom 2 m=39 k=2 | [[0, 1, 7, 23, 27, 36, 38], [True, True, True, False, False, False]] | [[0, 1, 3, 4, 7, 21, 27], [True, True, False, False, False, False]] | Failed |
| bloom 3 m=29 k=5 | [[0, 3, 5, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 28], [True, True, False, True, False, True]] | [[0, 3, 5, 8, 9, 10, 11, 13, 14, 15, 16, 17, 20, 21, 22, 24, 25, 28], [True, True, False, True, False, False]] | Failed |
| bloom 4 m=101 k=3 | [[1, 16, 19, 25, 31, 36, 44, 49, 50, 52, 53, 62, 66, 68, 74, 75, 79, 80, 82, 84, 87, 94, 100], [True, True, False, False, False, False]] | [[1, 16, 19, 20, 23, 28, 36, 44, 46, 50, 52, 53, 66, 74, 79, 80, 82, 83, 84, 86, 94], [True, True, False, False, False, False]] | Failed |
| bloom 5 m=16 k=2 | [[2, 3, 5, 8, 10, 12, 15], [True, True, False, True, False, False]] | [[0, 3, 8, 9, 10, 15], [True, True, False, False, False, False]] | Failed |
| empty filter rejects everything | [[], [False, False]] | [[], [False, False]] | Passed |
SHA-256 / 66ef7452d5913230fc9f698bbd6c382cc4a75d5695c0c576436a2bd75b540ae9
HELD IN THE MEMBER ARCHIVE
The verified repair and its recorded checks are member-only.
This mechanism has 7 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.
Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.
Member access is invitation-based. Sign in with your invited account to inspect the repair.
Sign in to the archive ↗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:42.245467+00:00.
Case digest / eaab50f06dabacbf3c6cc36dd1c29fc958cc7f6e7beec64d7e7ae2cb59895a27