{"abstract":"Every item-count estimate is inflated by a factor of about 1.44.","category":"Probabilistic sketches","checks":7,"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.","evaluation_group":"w2-probabilistic_sketches-bloom-cardinality","failed_approach":"Switching to base 10 scales every estimate by a different wrong constant.","family":"w2-probabilistic_sketches-bloom-cardinality-log-base","id":"FA-72921","implementations":{"attempt":{"sha256":"a04d2ad6e6db3b3a3c1f588585205cf1e707afbf655bd710f1d61bf0c19b8683","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    m = x['m']\n    k = x['k']\n    def est(bits):\n        X = len(bits)\n        if X >= m:\n            return None\n        return -(m / k) * math.log10(1 - X / m)\n    a = set(x['a'])\n    b = set(x['b'])\n    u = a | b\n    ea, eb, eu = est(a), est(b), est(u)\n    if ea is None or eb is None or eu is None:\n        inter = None\n    else:\n        inter = max(0.0, ea + eb - eu)\n    return [None if v is None else round(v, 3) for v in (ea, eb, eu, inter)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['overlapping filters',\n   {'a': [2, 6, 7, 8, 15, 16, 19, 28, 29, 33, 34, 35, 39, 40, 41, 42, 45, 51, 59, 63],\n    'b': [2, 6, 7, 8, 14, 15, 16, 19, 20, 22, 28, 29, 30, 33, 35, 36, 39, 47, 49, 51, 52],\n    'k': 3,\n    'm': 65},\n   [7.967, 8.454, 12.209, 4.213]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40],\n    'k': 2,\n    'm': 80},\n   [5.917, 5.917, 12.863, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.068, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 6], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 21], 'b': [3, 7, 11, 21], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 9], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 34.171, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [1, 2, 7, 12, 21, 24, 25, 32, 34, 40, 41, 42, 49, 50, 52, 56, 59, 60, 63, 65],\n    'b': [1, 2, 4, 6, 7, 12, 16, 21, 23, 24, 25, 28, 32, 34, 35, 40, 43, 48, 54, 55, 59],\n    'k': 3,\n    'm': 66},\n   [7.942, 8.426, 13.335, 3.033]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],\n    'k': 2,\n    'm': 80},\n   [6.501, 6.501, 14.267, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.068, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 7], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 22], 'b': [3, 7, 11, 22], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 10], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 31.387, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [4, 5, 10, 11, 16, 24, 25, 26, 30, 33, 34, 36, 37, 39, 50, 57, 59, 60, 62, 65],\n    'b': [0, 4, 5, 10, 11, 15, 16, 17, 18, 24, 25, 26, 30, 31, 33, 39, 43, 50, 52, 59],\n    'k': 3,\n    'm': 67},\n   [7.918, 7.918, 11.52, 4.317]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],\n    'k': 2,\n    'm': 80},\n   [7.093, 7.093, 15.722, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 8], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 23], 'b': [3, 7, 11, 23], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 11], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 28.825, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [3, 14, 15, 16, 17, 18, 19, 26, 37, 42, 46, 47, 48, 50, 51, 54, 57, 61, 62, 64],\n    'b': [3, 11, 13, 14, 15, 16, 17, 18, 19, 23, 24, 26, 29, 36, 37, 38, 42, 49, 61, 63, 66],\n    'k': 3,\n    'm': 68},\n   [7.895, 8.372, 13.19, 3.077]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43],\n    'k': 2,\n    'm': 80},\n   [7.695, 7.695, 17.231, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 9], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.042, 0.51]],\n  ['identical filters',\n   {'a': [3, 7, 11, 24], 'b': [3, 7, 11, 24], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 12], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 26.454, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [3, 11, 12, 19, 21, 22, 23, 29, 30, 31, 36, 39, 43, 44, 50, 52, 57, 59, 66, 68],\n    'b': [1, 2, 3, 8, 11, 12, 18, 19, 21, 22, 23, 28, 29, 30, 31, 33, 34, 36, 55, 61, 65],\n    'k': 3,\n    'm': 69},\n   [7.873, 8.347, 13.123, 3.097]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44],\n    'k': 2,\n    'm': 80},\n   [8.306, 8.306, 18.8, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 10], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 25], 'b': [3, 7, 11, 25], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 13], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 24.246, 88.723, 0.0]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"2e6e7e6a21f8fdcda21ef267d3f0ae2776c93f9df32dd14347710e0a54324bd0","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    m = x['m']\n    k = x['k']\n    def est(bits):\n        X = len(bits)\n        if X >= m:\n            return None\n        return -(m / k) * math.log2(1 - X / m)\n    a = set(x['a'])\n    b = set(x['b'])\n    u = a | b\n    ea, eb, eu = est(a), est(b), est(u)\n    if ea is None or eb is None or eu is None:\n        inter = None\n    else:\n        inter = max(0.0, ea + eb - eu)\n    return [None if v is None else round(v, 3) for v in (ea, eb, eu, inter)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['overlapping filters',\n   {'a': [2, 6, 7, 8, 15, 16, 19, 28, 29, 33, 34, 35, 39, 40, 41, 42, 45, 51, 59, 63],\n    'b': [2, 6, 7, 8, 14, 15, 16, 19, 20, 22, 28, 29, 30, 33, 35, 36, 39, 47, 49, 51, 52],\n    'k': 3,\n    'm': 65},\n   [7.967, 8.454, 12.209, 4.213]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40],\n    'k': 2,\n    'm': 80},\n   [5.917, 5.917, 12.863, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.068, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 6], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 21], 'b': [3, 7, 11, 21], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 9], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 34.171, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [1, 2, 7, 12, 21, 24, 25, 32, 34, 40, 41, 42, 49, 50, 52, 56, 59, 60, 63, 65],\n    'b': [1, 2, 4, 6, 7, 12, 16, 21, 23, 24, 25, 28, 32, 34, 35, 40, 43, 48, 54, 55, 59],\n    'k': 3,\n    'm': 66},\n   [7.942, 8.426, 13.335, 3.033]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],\n    'k': 2,\n    'm': 80},\n   [6.501, 6.501, 14.267, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.068, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 7], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 22], 'b': [3, 7, 11, 22], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 10], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 31.387, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [4, 5, 10, 11, 16, 24, 25, 26, 30, 33, 34, 36, 37, 39, 50, 57, 59, 60, 62, 65],\n    'b': [0, 4, 5, 10, 11, 15, 16, 17, 18, 24, 25, 26, 30, 31, 33, 39, 43, 50, 52, 59],\n    'k': 3,\n    'm': 67},\n   [7.918, 7.918, 11.52, 4.317]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],\n    'k': 2,\n    'm': 80},\n   [7.093, 7.093, 15.722, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 8], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 23], 'b': [3, 7, 11, 23], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 11], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 28.825, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [3, 14, 15, 16, 17, 18, 19, 26, 37, 42, 46, 47, 48, 50, 51, 54, 57, 61, 62, 64],\n    'b': [3, 11, 13, 14, 15, 16, 17, 18, 19, 23, 24, 26, 29, 36, 37, 38, 42, 49, 61, 63, 66],\n    'k': 3,\n    'm': 68},\n   [7.895, 8.372, 13.19, 3.077]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43],\n    'k': 2,\n    'm': 80},\n   [7.695, 7.695, 17.231, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 9], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.042, 0.51]],\n  ['identical filters',\n   {'a': [3, 7, 11, 24], 'b': [3, 7, 11, 24], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 12], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 26.454, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [3, 11, 12, 19, 21, 22, 23, 29, 30, 31, 36, 39, 43, 44, 50, 52, 57, 59, 66, 68],\n    'b': [1, 2, 3, 8, 11, 12, 18, 19, 21, 22, 23, 28, 29, 30, 31, 33, 34, 36, 55, 61, 65],\n    'k': 3,\n    'm': 69},\n   [7.873, 8.347, 13.123, 3.097]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44],\n    'k': 2,\n    'm': 80},\n   [8.306, 8.306, 18.8, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 10], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 25], 'b': [3, 7, 11, 25], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 13], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 24.246, 88.723, 0.0]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"b2425ce83f2222fa1703f0e5fb389202b5970e301b7318b4b3126b3513f1c7f4","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    m = x['m']\n    k = x['k']\n    def est(bits):\n        X = len(bits)\n        if X >= m:\n            return None\n        return -(m / k) * math.log(1 - X / m)\n    a = set(x['a'])\n    b = set(x['b'])\n    u = a | b\n    ea, eb, eu = est(a), est(b), est(u)\n    if ea is None or eb is None or eu is None:\n        inter = None\n    else:\n        inter = max(0.0, ea + eb - eu)\n    return [None if v is None else round(v, 3) for v in (ea, eb, eu, inter)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['overlapping filters',\n   {'a': [2, 6, 7, 8, 15, 16, 19, 28, 29, 33, 34, 35, 39, 40, 41, 42, 45, 51, 59, 63],\n    'b': [2, 6, 7, 8, 14, 15, 16, 19, 20, 22, 28, 29, 30, 33, 35, 36, 39, 47, 49, 51, 52],\n    'k': 3,\n    'm': 65},\n   [7.967, 8.454, 12.209, 4.213]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40],\n    'k': 2,\n    'm': 80},\n   [5.917, 5.917, 12.863, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.068, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 6], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 21], 'b': [3, 7, 11, 21], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 9], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 34.171, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [1, 2, 7, 12, 21, 24, 25, 32, 34, 40, 41, 42, 49, 50, 52, 56, 59, 60, 63, 65],\n    'b': [1, 2, 4, 6, 7, 12, 16, 21, 23, 24, 25, 28, 32, 34, 35, 40, 43, 48, 54, 55, 59],\n    'k': 3,\n    'm': 66},\n   [7.942, 8.426, 13.335, 3.033]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],\n    'k': 2,\n    'm': 80},\n   [6.501, 6.501, 14.267, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.068, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 7], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 22], 'b': [3, 7, 11, 22], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 10], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 31.387, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [4, 5, 10, 11, 16, 24, 25, 26, 30, 33, 34, 36, 37, 39, 50, 57, 59, 60, 62, 65],\n    'b': [0, 4, 5, 10, 11, 15, 16, 17, 18, 24, 25, 26, 30, 31, 33, 39, 43, 50, 52, 59],\n    'k': 3,\n    'm': 67},\n   [7.918, 7.918, 11.52, 4.317]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],\n    'k': 2,\n    'm': 80},\n   [7.093, 7.093, 15.722, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 8], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 23], 'b': [3, 7, 11, 23], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 11], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 28.825, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [3, 14, 15, 16, 17, 18, 19, 26, 37, 42, 46, 47, 48, 50, 51, 54, 57, 61, 62, 64],\n    'b': [3, 11, 13, 14, 15, 16, 17, 18, 19, 23, 24, 26, 29, 36, 37, 38, 42, 49, 61, 63, 66],\n    'k': 3,\n    'm': 68},\n   [7.895, 8.372, 13.19, 3.077]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43],\n    'k': 2,\n    'm': 80},\n   [7.695, 7.695, 17.231, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 9], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.042, 0.51]],\n  ['identical filters',\n   {'a': [3, 7, 11, 24], 'b': [3, 7, 11, 24], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 12], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 26.454, 88.723, 0.0]]],\n [['overlapping filters',\n   {'a': [3, 11, 12, 19, 21, 22, 23, 29, 30, 31, 36, 39, 43, 44, 50, 52, 57, 59, 66, 68],\n    'b': [1, 2, 3, 8, 11, 12, 18, 19, 21, 22, 23, 28, 29, 30, 31, 33, 34, 36, 55, 61, 65],\n    'k': 3,\n    'm': 69},\n   [7.873, 8.347, 13.123, 3.097]],\n  ['disjoint bits clamp intersection',\n   {'a': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],\n    'b': [30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44],\n    'k': 2,\n    'm': 80},\n   [8.306, 8.306, 18.8, 0.0]],\n  ['saturated filter',\n   {'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},\n   [None, 1.661, None, None]],\n  ['duplicate indices',\n   {'a': [1, 1, 2, 3, 3, 10], 'b': [2, 2, 9], 'k': 4, 'm': 50},\n   [1.042, 0.51, 1.317, 0.236]],\n  ['identical filters',\n   {'a': [3, 7, 11, 25], 'b': [3, 7, 11, 25], 'k': 3, 'm': 40},\n   [1.405, 1.405, 1.405, 1.405]],\n  ['empty second filter', {'a': [0, 4, 13], 'b': [], 'k': 2, 'm': 30}, [1.58, -0.0, 1.58, 0.0]],\n  ['dense overlap',\n   {'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],\n    'b': [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],\n    'k': 1,\n    'm': 32},\n   [44.361, 24.246, 88.723, 0.0]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-bloom-cardinality-log-base","generated_at":"2026-09-29T14:48:42.746389+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"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.","repair":"Use the natural logarithm, which follows from the exponential bit-survival model.","root_cause":"The estimator takes log base 2 of the clear-bit fraction instead of the natural logarithm.","sha256":"3872d908cdcb66170eba6c2de9ec2a92c52bba94a3790ad4ffb38e9dc4772341","title":"Bloom filter cardinality estimation: estimate uses a base-2 logarithm · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":38.728,"exit_code":1,"observations":[{"actual":[3.46,3.672,5.302,1.83],"check":"overlapping filters","expected":[7.967,8.454,12.209,4.213],"passed":false},{"actual":[2.57,2.57,5.586,0.0],"check":"disjoint bits clamp intersection","expected":[5.917,5.917,12.863,0.0],"passed":false},{"actual":[null,0.464,null,null],"check":"saturated filter","expected":[null,1.068,null,null],"passed":false},{"actual":[0.453,0.222,0.572,0.102],"check":"duplicate indices","expected":[1.042,0.51,1.317,0.236],"passed":false},{"actual":[0.61,0.61,0.61,0.61],"check":"identical filters","expected":[1.405,1.405,1.405,1.405],"passed":false},{"actual":[0.686,-0.0,0.686,0.0],"check":"empty second filter","expected":[1.58,-0.0,1.58,0.0],"passed":false},{"actual":[19.266,14.84,38.532,0.0],"check":"dense overlap","expected":[44.361,34.171,88.723,0.0],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"overlapping filters\", \"actual\": [3.46, 3.672, 5.302, 1.83], \"expected\": [7.967, 8.454, 12.209, 4.213], \"passed\": false}, {\"check\": \"disjoint bits clamp intersection\", \"actual\": [2.57, 2.57, 5.586, 0.0], \"expected\": [5.917, 5.917, 12.863, 0.0], \"passed\": false}, {\"check\": \"saturated filter\", \"actual\": [null, 0.464, null, null], \"expected\": [null, 1.068, null, null], \"passed\": false}, {\"check\": \"duplicate indices\", \"actual\": [0.453, 0.222, 0.572, 0.102], \"expected\": [1.042, 0.51, 1.317, 0.236], \"passed\": false}, {\"check\": \"identical filters\", \"actual\": [0.61, 0.61, 0.61, 0.61], \"expected\": [1.405, 1.405, 1.405, 1.405], \"passed\": false}, {\"check\": \"empty second filter\", \"actual\": [0.686, -0.0, 0.686, 0.0], \"expected\": [1.58, -0.0, 1.58, 0.0], \"passed\": false}, {\"check\": \"dense overlap\", \"actual\": [19.266, 14.84, 38.532, 0.0], \"expected\": [44.361, 34.171, 88.723, 0.0], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.072,"exit_code":1,"observations":[{"actual":[11.494,12.197,17.613,6.078],"check":"overlapping filters","expected":[7.967,8.454,12.209,4.213],"passed":false},{"actual":[8.536,8.536,18.558,0.0],"check":"disjoint bits clamp intersection","expected":[5.917,5.917,12.863,0.0],"passed":false},{"actual":[null,1.541,null,null],"check":"saturated filter","expected":[null,1.068,null,null],"passed":false},{"actual":[1.504,0.736,1.9,0.34],"check":"duplicate indices","expected":[1.042,0.51,1.317,0.236],"passed":false},{"actual":[2.027,2.027,2.027,2.027],"check":"identical filters","expected":[1.405,1.405,1.405,1.405],"passed":false},{"actual":[2.28,-0.0,2.28,0.0],"check":"empty second filter","expected":[1.58,-0.0,1.58,0.0],"passed":false},{"actual":[64.0,49.298,128.0,0.0],"check":"dense overlap","expected":[44.361,34.171,88.723,0.0],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"overlapping filters\", \"actual\": [11.494, 12.197, 17.613, 6.078], \"expected\": [7.967, 8.454, 12.209, 4.213], \"passed\": false}, {\"check\": \"disjoint bits clamp intersection\", \"actual\": [8.536, 8.536, 18.558, 0.0], \"expected\": [5.917, 5.917, 12.863, 0.0], \"passed\": false}, {\"check\": \"saturated filter\", \"actual\": [null, 1.541, null, null], \"expected\": [null, 1.068, null, null], \"passed\": false}, {\"check\": \"duplicate indices\", \"actual\": [1.504, 0.736, 1.9, 0.34], \"expected\": [1.042, 0.51, 1.317, 0.236], \"passed\": false}, {\"check\": \"identical filters\", \"actual\": [2.027, 2.027, 2.027, 2.027], \"expected\": [1.405, 1.405, 1.405, 1.405], \"passed\": false}, {\"check\": \"empty second filter\", \"actual\": [2.28, -0.0, 2.28, 0.0], \"expected\": [1.58, -0.0, 1.58, 0.0], \"passed\": false}, {\"check\": \"dense overlap\", \"actual\": [64.0, 49.298, 128.0, 0.0], \"expected\": [44.361, 34.171, 88.723, 0.0], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":37.232,"exit_code":0,"observations":[{"actual":[7.967,8.454,12.209,4.213],"check":"overlapping filters","expected":[7.967,8.454,12.209,4.213],"passed":true},{"actual":[5.917,5.917,12.863,0.0],"check":"disjoint bits clamp intersection","expected":[5.917,5.917,12.863,0.0],"passed":true},{"actual":[null,1.068,null,null],"check":"saturated filter","expected":[null,1.068,null,null],"passed":true},{"actual":[1.042,0.51,1.317,0.236],"check":"duplicate indices","expected":[1.042,0.51,1.317,0.236],"passed":true},{"actual":[1.405,1.405,1.405,1.405],"check":"identical filters","expected":[1.405,1.405,1.405,1.405],"passed":true},{"actual":[1.58,-0.0,1.58,0.0],"check":"empty second filter","expected":[1.58,-0.0,1.58,0.0],"passed":true},{"actual":[44.361,34.171,88.723,0.0],"check":"dense overlap","expected":[44.361,34.171,88.723,0.0],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"overlapping filters\", \"actual\": [7.967, 8.454, 12.209, 4.213], \"expected\": [7.967, 8.454, 12.209, 4.213], \"passed\": true}, {\"check\": \"disjoint bits clamp intersection\", \"actual\": [5.917, 5.917, 12.863, 0.0], \"expected\": [5.917, 5.917, 12.863, 0.0], \"passed\": true}, {\"check\": \"saturated filter\", \"actual\": [null, 1.068, null, null], \"expected\": [null, 1.068, null, null], \"passed\": true}, {\"check\": \"duplicate indices\", \"actual\": [1.042, 0.51, 1.317, 0.236], \"expected\": [1.042, 0.51, 1.317, 0.236], \"passed\": true}, {\"check\": \"identical filters\", \"actual\": [1.405, 1.405, 1.405, 1.405], \"expected\": [1.405, 1.405, 1.405, 1.405], \"passed\": true}, {\"check\": \"empty second filter\", \"actual\": [1.58, -0.0, 1.58, 0.0], \"expected\": [1.58, -0.0, 1.58, 0.0], \"passed\": true}, {\"check\": \"dense overlap\", \"actual\": [44.361, 34.171, 88.723, 0.0], \"expected\": [44.361, 34.171, 88.723, 0.0], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}