broken_source:
"""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('utf-8'):
            h = ((h ^ b) * 16777619) & 0xFFFFFFFF
        return h
    def probes(s):
        h1 = fnv(s, 0)
        h2 = fnv(s, 0x5bd1e995)
        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)

source:
"""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('utf-8'):
            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)

prompt:
Bit layouts diverge from a conforming writer and, for power-of-two m, some items collapse onto few bits.

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.

split: open-access


broken_source:
"""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('utf-8'):
            h = ((h ^ b) * 16777619) & 0xFFFFFFFF
        return h
    def probes(s):
        h1 = fnv(s, 0)
        h2 = fnv(s, 0x5bd1e995) | 1
        return [(h1 + i * h2) % 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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""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('utf-8'):
            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)

prompt:
A Python port disagrees with the 32-bit reference writer about which bits are set.

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.

split: open-access


broken_source:
"""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('utf-8'):
            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 = [any(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)

source:
"""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('utf-8'):
            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 = [bool(bits[probes(s)[0]]) and any(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)

prompt:
Items that were never inserted are reported present whenever one of their probe bits is set.

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.

split: open-access


broken_source:
"""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)

source:
"""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)

prompt:
Non-ASCII keys map to different bits than in the reference writer, producing false negatives across implementations.

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.

split: open-access