FA-72921 / Probabilistic sketches / Open access
Bloom filter cardinality estimation: estimate uses a base-2 logarithm · case 01
Every item-count estimate is inflated by a factor of about 1.44.
ROOT CAUSE
The estimator takes log base 2 of the clear-bit fraction instead of the natural logarithm.
VERIFIED REPAIR
Use the natural logarithm, which follows from the exponential bit-survival model.
Unsuccessful approach: Switching to base 10 scales every estimate by a different wrong constant.
Case contract
Input {m, k, a, b} with a and b lists of set-bit indices (duplicates possible). For a bit set of X distinct indices the item estimate is -(m/k) ln(1 - X/m); a saturated set (X = m) has no estimate (None). The union uses the OR of both bit sets; the intersection is ea + eb - eu clamped at 0, and is None when any input estimate is None. Return the four values rounded to 3 decimals.
Why this case matters
Estimating how many items two Bloom filters hold, and how many they share, drives capacity alarms and set-similarity decisions without access to the items.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
def est(bits):
X = len(bits)
if X >= m:
return None
return -(m / k) * math.log2(1 - X / m)
a = set(x['a'])
b = set(x['b'])
u = a | b
ea, eb, eu = est(a), est(b), est(u)
if ea is None or eb is None or eu is None:
inter = None
else:
inter = max(0.0, ea + eb - eu)
return [None if v is None else round(v, 3) for v in (ea, eb, eu, inter)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overlapping filters',
{'a': [2, 6, 7, 8, 15, 16, 19, 28, 29, 33, 34, 35, 39, 40, 41, 42, 45, 51, 59, 63],
'b': [2, 6, 7, 8, 14, 15, 16, 19, 20, 22, 28, 29, 30, 33, 35, 36, 39, 47, 49, 51, 52],
'k': 3,
'm': 65},
[7.967, 8.454, 12.209, 4.213]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40],
'k': 2,
'm': 80},
[5.917, 5.917, 12.863, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 1], 'k': 2, 'm': 16},
[None, 1.068, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 6], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 21], 'b': [3, 7, 11, 21], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 9], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 34.171, 88.723, 0.0]]],
[['overlapping filters',
{'a': [1, 2, 7, 12, 21, 24, 25, 32, 34, 40, 41, 42, 49, 50, 52, 56, 59, 60, 63, 65],
'b': [1, 2, 4, 6, 7, 12, 16, 21, 23, 24, 25, 28, 32, 34, 35, 40, 43, 48, 54, 55, 59],
'k': 3,
'm': 66},
[7.942, 8.426, 13.335, 3.033]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],
'k': 2,
'm': 80},
[6.501, 6.501, 14.267, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 2], 'k': 2, 'm': 16},
[None, 1.068, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 7], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 22], 'b': [3, 7, 11, 22], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 10], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 31.387, 88.723, 0.0]]],
[['overlapping filters',
{'a': [4, 5, 10, 11, 16, 24, 25, 26, 30, 33, 34, 36, 37, 39, 50, 57, 59, 60, 62, 65],
'b': [0, 4, 5, 10, 11, 15, 16, 17, 18, 24, 25, 26, 30, 31, 33, 39, 43, 50, 52, 59],
'k': 3,
'm': 67},
[7.918, 7.918, 11.52, 4.317]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],
'k': 2,
'm': 80},
[7.093, 7.093, 15.722, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 3], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 8], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 23], 'b': [3, 7, 11, 23], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 11], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 28.825, 88.723, 0.0]]],
[['overlapping filters',
{'a': [3, 14, 15, 16, 17, 18, 19, 26, 37, 42, 46, 47, 48, 50, 51, 54, 57, 61, 62, 64],
'b': [3, 11, 13, 14, 15, 16, 17, 18, 19, 23, 24, 26, 29, 36, 37, 38, 42, 49, 61, 63, 66],
'k': 3,
'm': 68},
[7.895, 8.372, 13.19, 3.077]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43],
'k': 2,
'm': 80},
[7.695, 7.695, 17.231, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 4], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 9], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.042, 0.51]],
['identical filters',
{'a': [3, 7, 11, 24], 'b': [3, 7, 11, 24], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 12], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 26.454, 88.723, 0.0]]],
[['overlapping filters',
{'a': [3, 11, 12, 19, 21, 22, 23, 29, 30, 31, 36, 39, 43, 44, 50, 52, 57, 59, 66, 68],
'b': [1, 2, 3, 8, 11, 12, 18, 19, 21, 22, 23, 28, 29, 30, 31, 33, 34, 36, 55, 61, 65],
'k': 3,
'm': 69},
[7.873, 8.347, 13.123, 3.097]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44],
'k': 2,
'm': 80},
[8.306, 8.306, 18.8, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 5], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 10], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 25], 'b': [3, 7, 11, 25], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 13], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 24.246, 88.723, 0.0]]]]
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 |
|---|---|---|---|
| overlapping filters | [11.494, 12.197, 17.613, 6.078] | [7.967, 8.454, 12.209, 4.213] | Failed |
| disjoint bits clamp intersection | [8.536, 8.536, 18.558, 0.0] | [5.917, 5.917, 12.863, 0.0] | Failed |
| saturated filter | [None, 1.541, None, None] | [None, 1.068, None, None] | Failed |
| duplicate indices | [1.504, 0.736, 1.9, 0.34] | [1.042, 0.51, 1.317, 0.236] | Failed |
| identical filters | [2.027, 2.027, 2.027, 2.027] | [1.405, 1.405, 1.405, 1.405] | Failed |
| empty second filter | [2.28, -0.0, 2.28, 0.0] | [1.58, -0.0, 1.58, 0.0] | Failed |
| dense overlap | [64.0, 49.298, 128.0, 0.0] | [44.361, 34.171, 88.723, 0.0] | Failed |
SHA-256 / 2e6e7e6a21f8fdcda21ef267d3f0ae2776c93f9df32dd14347710e0a54324bd0
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
def est(bits):
X = len(bits)
if X >= m:
return None
return -(m / k) * math.log10(1 - X / m)
a = set(x['a'])
b = set(x['b'])
u = a | b
ea, eb, eu = est(a), est(b), est(u)
if ea is None or eb is None or eu is None:
inter = None
else:
inter = max(0.0, ea + eb - eu)
return [None if v is None else round(v, 3) for v in (ea, eb, eu, inter)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overlapping filters',
{'a': [2, 6, 7, 8, 15, 16, 19, 28, 29, 33, 34, 35, 39, 40, 41, 42, 45, 51, 59, 63],
'b': [2, 6, 7, 8, 14, 15, 16, 19, 20, 22, 28, 29, 30, 33, 35, 36, 39, 47, 49, 51, 52],
'k': 3,
'm': 65},
[7.967, 8.454, 12.209, 4.213]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40],
'k': 2,
'm': 80},
[5.917, 5.917, 12.863, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 1], 'k': 2, 'm': 16},
[None, 1.068, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 6], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 21], 'b': [3, 7, 11, 21], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 9], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 34.171, 88.723, 0.0]]],
[['overlapping filters',
{'a': [1, 2, 7, 12, 21, 24, 25, 32, 34, 40, 41, 42, 49, 50, 52, 56, 59, 60, 63, 65],
'b': [1, 2, 4, 6, 7, 12, 16, 21, 23, 24, 25, 28, 32, 34, 35, 40, 43, 48, 54, 55, 59],
'k': 3,
'm': 66},
[7.942, 8.426, 13.335, 3.033]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],
'k': 2,
'm': 80},
[6.501, 6.501, 14.267, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 2], 'k': 2, 'm': 16},
[None, 1.068, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 7], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 22], 'b': [3, 7, 11, 22], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 10], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 31.387, 88.723, 0.0]]],
[['overlapping filters',
{'a': [4, 5, 10, 11, 16, 24, 25, 26, 30, 33, 34, 36, 37, 39, 50, 57, 59, 60, 62, 65],
'b': [0, 4, 5, 10, 11, 15, 16, 17, 18, 24, 25, 26, 30, 31, 33, 39, 43, 50, 52, 59],
'k': 3,
'm': 67},
[7.918, 7.918, 11.52, 4.317]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],
'k': 2,
'm': 80},
[7.093, 7.093, 15.722, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 3], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 8], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 23], 'b': [3, 7, 11, 23], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 11], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 28.825, 88.723, 0.0]]],
[['overlapping filters',
{'a': [3, 14, 15, 16, 17, 18, 19, 26, 37, 42, 46, 47, 48, 50, 51, 54, 57, 61, 62, 64],
'b': [3, 11, 13, 14, 15, 16, 17, 18, 19, 23, 24, 26, 29, 36, 37, 38, 42, 49, 61, 63, 66],
'k': 3,
'm': 68},
[7.895, 8.372, 13.19, 3.077]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43],
'k': 2,
'm': 80},
[7.695, 7.695, 17.231, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 4], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 9], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.042, 0.51]],
['identical filters',
{'a': [3, 7, 11, 24], 'b': [3, 7, 11, 24], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 12], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 26.454, 88.723, 0.0]]],
[['overlapping filters',
{'a': [3, 11, 12, 19, 21, 22, 23, 29, 30, 31, 36, 39, 43, 44, 50, 52, 57, 59, 66, 68],
'b': [1, 2, 3, 8, 11, 12, 18, 19, 21, 22, 23, 28, 29, 30, 31, 33, 34, 36, 55, 61, 65],
'k': 3,
'm': 69},
[7.873, 8.347, 13.123, 3.097]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44],
'k': 2,
'm': 80},
[8.306, 8.306, 18.8, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 5], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 10], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 25], 'b': [3, 7, 11, 25], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 13], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 24.246, 88.723, 0.0]]]]
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 |
|---|---|---|---|
| overlapping filters | [3.46, 3.672, 5.302, 1.83] | [7.967, 8.454, 12.209, 4.213] | Failed |
| disjoint bits clamp intersection | [2.57, 2.57, 5.586, 0.0] | [5.917, 5.917, 12.863, 0.0] | Failed |
| saturated filter | [None, 0.464, None, None] | [None, 1.068, None, None] | Failed |
| duplicate indices | [0.453, 0.222, 0.572, 0.102] | [1.042, 0.51, 1.317, 0.236] | Failed |
| identical filters | [0.61, 0.61, 0.61, 0.61] | [1.405, 1.405, 1.405, 1.405] | Failed |
| empty second filter | [0.686, -0.0, 0.686, 0.0] | [1.58, -0.0, 1.58, 0.0] | Failed |
| dense overlap | [19.266, 14.84, 38.532, 0.0] | [44.361, 34.171, 88.723, 0.0] | Failed |
SHA-256 / a04d2ad6e6db3b3a3c1f588585205cf1e707afbf655bd710f1d61bf0c19b8683
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
m = x['m']
k = x['k']
def est(bits):
X = len(bits)
if X >= m:
return None
return -(m / k) * math.log(1 - X / m)
a = set(x['a'])
b = set(x['b'])
u = a | b
ea, eb, eu = est(a), est(b), est(u)
if ea is None or eb is None or eu is None:
inter = None
else:
inter = max(0.0, ea + eb - eu)
return [None if v is None else round(v, 3) for v in (ea, eb, eu, inter)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overlapping filters',
{'a': [2, 6, 7, 8, 15, 16, 19, 28, 29, 33, 34, 35, 39, 40, 41, 42, 45, 51, 59, 63],
'b': [2, 6, 7, 8, 14, 15, 16, 19, 20, 22, 28, 29, 30, 33, 35, 36, 39, 47, 49, 51, 52],
'k': 3,
'm': 65},
[7.967, 8.454, 12.209, 4.213]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40],
'k': 2,
'm': 80},
[5.917, 5.917, 12.863, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 1], 'k': 2, 'm': 16},
[None, 1.068, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 6], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 21], 'b': [3, 7, 11, 21], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 9], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 34.171, 88.723, 0.0]]],
[['overlapping filters',
{'a': [1, 2, 7, 12, 21, 24, 25, 32, 34, 40, 41, 42, 49, 50, 52, 56, 59, 60, 63, 65],
'b': [1, 2, 4, 6, 7, 12, 16, 21, 23, 24, 25, 28, 32, 34, 35, 40, 43, 48, 54, 55, 59],
'k': 3,
'm': 66},
[7.942, 8.426, 13.335, 3.033]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],
'k': 2,
'm': 80},
[6.501, 6.501, 14.267, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 2], 'k': 2, 'm': 16},
[None, 1.068, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 7], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 22], 'b': [3, 7, 11, 22], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 10], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 31.387, 88.723, 0.0]]],
[['overlapping filters',
{'a': [4, 5, 10, 11, 16, 24, 25, 26, 30, 33, 34, 36, 37, 39, 50, 57, 59, 60, 62, 65],
'b': [0, 4, 5, 10, 11, 15, 16, 17, 18, 24, 25, 26, 30, 31, 33, 39, 43, 50, 52, 59],
'k': 3,
'm': 67},
[7.918, 7.918, 11.52, 4.317]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],
'k': 2,
'm': 80},
[7.093, 7.093, 15.722, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 3], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 8], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 23], 'b': [3, 7, 11, 23], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 11], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 28.825, 88.723, 0.0]]],
[['overlapping filters',
{'a': [3, 14, 15, 16, 17, 18, 19, 26, 37, 42, 46, 47, 48, 50, 51, 54, 57, 61, 62, 64],
'b': [3, 11, 13, 14, 15, 16, 17, 18, 19, 23, 24, 26, 29, 36, 37, 38, 42, 49, 61, 63, 66],
'k': 3,
'm': 68},
[7.895, 8.372, 13.19, 3.077]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43],
'k': 2,
'm': 80},
[7.695, 7.695, 17.231, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 4], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 9], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.042, 0.51]],
['identical filters',
{'a': [3, 7, 11, 24], 'b': [3, 7, 11, 24], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 12], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 26.454, 88.723, 0.0]]],
[['overlapping filters',
{'a': [3, 11, 12, 19, 21, 22, 23, 29, 30, 31, 36, 39, 43, 44, 50, 52, 57, 59, 66, 68],
'b': [1, 2, 3, 8, 11, 12, 18, 19, 21, 22, 23, 28, 29, 30, 31, 33, 34, 36, 55, 61, 65],
'k': 3,
'm': 69},
[7.873, 8.347, 13.123, 3.097]],
['disjoint bits clamp intersection',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44],
'k': 2,
'm': 80},
[8.306, 8.306, 18.8, 0.0]],
['saturated filter',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 'b': [1, 2, 5], 'k': 2, 'm': 16},
[None, 1.661, None, None]],
['duplicate indices',
{'a': [1, 1, 2, 3, 3, 10], 'b': [2, 2, 9], 'k': 4, 'm': 50},
[1.042, 0.51, 1.317, 0.236]],
['identical filters',
{'a': [3, 7, 11, 25], 'b': [3, 7, 11, 25], 'k': 3, 'm': 40},
[1.405, 1.405, 1.405, 1.405]],
['empty second filter', {'a': [0, 4, 13], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],
['dense overlap',
{'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
'b': [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
'k': 1,
'm': 32},
[44.361, 24.246, 88.723, 0.0]]]]
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 |
|---|---|---|---|
| overlapping filters | [7.967, 8.454, 12.209, 4.213] | [7.967, 8.454, 12.209, 4.213] | Passed |
| disjoint bits clamp intersection | [5.917, 5.917, 12.863, 0.0] | [5.917, 5.917, 12.863, 0.0] | Passed |
| saturated filter | [None, 1.068, None, None] | [None, 1.068, None, None] | Passed |
| duplicate indices | [1.042, 0.51, 1.317, 0.236] | [1.042, 0.51, 1.317, 0.236] | Passed |
| identical filters | [1.405, 1.405, 1.405, 1.405] | [1.405, 1.405, 1.405, 1.405] | Passed |
| empty second filter | [1.58, -0.0, 1.58, 0.0] | [1.58, -0.0, 1.58, 0.0] | Passed |
| dense overlap | [44.361, 34.171, 88.723, 0.0] | [44.361, 34.171, 88.723, 0.0] | Passed |
SHA-256 / b2425ce83f2222fa1703f0e5fb389202b5970e301b7318b4b3126b3513f1c7f4
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.746389+00:00.
Case digest / 3872d908cdcb66170eba6c2de9ec2a92c52bba94a3790ad4ffb38e9dc4772341