FA-73186 / Probabilistic sketches / Open access
MinHash Jaccard estimation: hashes the minimum element · case 01
Every signature component comes from the same element, so the estimate is 0 or 1.
ROOT CAUSE
The signature hashes the smallest element instead of taking the minimum hash over all elements.
VERIFIED REPAIR
Take the minimum of each hash function over the whole set.
Unsuccessful approach: Max-hash is a different, incompatible signature scheme.
Case contract
Input {k, A, B} integer sets. Signature component i is min over v of (A_i v + B_i) mod 2^31-1 with fixed coefficients. The estimate is the fraction of positions where both signatures agree, rounded to 4 decimals. Two empty sets have undefined similarity (None, with empty signatures); exactly one empty set gives 0.0. Return [sigA, sigB, estimate].
Why this case matters
Near-duplicate detection and set-similarity joins compare MinHash signatures instead of the sets; signature and comparison rules must match exactly across producers.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
P = 2147483647
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941, 69069, 22695477]
Bc = [12345, 1013904223, 7, 99991, 31337, 424242, 1, 3]
def sig(s):
return [(A[i] * min(s) + Bc[i]) % P for i in range(k)]
a, b = x['A'], x['B']
if not a and not b:
return [[], [], None]
if not a or not b:
return [sig(a) if a else [], sig(b) if b else [], 0.0]
sa, sb = sig(a), sig(b)
matches = sum(1 for i in range(k) if sa[i] == sb[i])
return [sa, sb, round(matches / k, 4)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overlapping sets k=4',
{'A': [185, 180, 93, 45, 14, 71, 154, 36, 166],
'B': [45, 14, 71, 154, 36, 166, 145, 34, 146, 221],
'k': 4},
[[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5]],
['overlapping sets k=6',
{'A': [137, 9, 132, 163, 55, 20, 170, 179, 119],
'B': [163, 55, 20, 170, 179, 119, 47, 41, 24, 251],
'k': 6},
[[321824033, 87781176, 406660754, 805406688, 307613469, 235695117],
[146980803, 87781176, 509981506, 134317810, 307613469, 97986032],
0.3333]],
['overlapping sets k=8',
{'A': [148, 51, 156, 91, 149, 73, 41, 176, 152],
'B': [91, 149, 73, 41, 176, 152, 140, 118, 113, 264],
'k': 8},
[[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560],
[143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [6, 9], 'B': [], 'k': 3}, [[178652874, 145934324, 1397215521], [], 0.0]],
['identical sets',
{'A': [3, 8, 14], 'B': [14, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 268535474, 497068074],
[238199717, 8753041, 431298261, 268535474, 497068074],
1.0]],
['large values',
{'A': [1000000001, 7, 99], 'B': [1000000001, 8], 'k': 4},
[[651916080, 56169922, 661849663, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [77, 180, 129, 27, 120, 79, 147, 135, 166],
'B': [27, 120, 79, 147, 135, 166, 178, 114, 109, 210],
'k': 4},
[[619558248, 314726861, 27022876, 134317872], [24089818, 314726861, 27022876, 134317872], 0.75]],
['overlapping sets k=6',
{'A': [43, 26, 163, 158, 61, 6, 58, 100, 105],
'B': [158, 61, 6, 58, 100, 105, 18, 10, 87, 294],
'k': 6},
[[178652874, 87781176, 327977509, 268535753, 216447956, 481067515],
[163463678, 193351205, 604294635, 268535753, 216447956, 272647769],
0.3333]],
['overlapping sets k=8',
{'A': [119, 125, 38, 35, 22, 123, 186, 169, 60],
'B': [35, 22, 123, 186, 169, 60, 55, 134, 69, 203],
'k': 8},
[[321824033, 24558668, 112328382, 402753417, 72170210, 94532592, 1519519, 499300497],
[440917719, 24558668, 112328382, 536971019, 72170210, 87884509, 1519519, 312214540],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [7, 9], 'B': [], 'k': 3}, [[1282168119, 145934324, 914256891], [], 0.0]],
['identical sets',
{'A': [3, 8, 15], 'B': [15, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 134317748, 337731375],
[238199717, 8753041, 431298261, 134317748, 337731375],
1.0]],
['large values',
{'A': [1000000002, 7, 99], 'B': [1000000002, 8], 'k': 4},
[[1282168119, 56169922, 178891033, 1208059556],
[238199717, 480984718, 178891033, 1073841830],
0.25]]],
[['overlapping sets k=4',
{'A': [21, 131, 85, 16, 192, 176, 186, 106, 14],
'B': [16, 192, 176, 186, 106, 14, 154, 67, 112, 276],
'k': 4},
[[416840246, 27093348, 345992755, 100022], [290151962, 27093348, 345992755, 100022], 0.75]],
['overlapping sets k=6',
{'A': [17, 173, 195, 128, 127, 162, 64, 34, 2],
'B': [128, 127, 162, 64, 34, 2, 4, 31, 120, 261],
'k': 6},
[[59559188, 103586803, 200019250, 100115, 95164537, 302952338],
[59559188, 343803435, 27022876, 100115, 125282443, 302952338],
0.5]],
['overlapping sets k=8',
{'A': [104, 160, 182, 180, 79, 129, 139, 39, 130],
'B': [180, 79, 129, 139, 39, 130, 181, 110, 50, 200],
'k': 8},
[[87433960, 164274631, 36030499, 100301, 19057977, 161789813, 2693692, 212845964],
[20292519, 314726861, 45038122, 134317872, 19057977, 161789813, 2693692, 244128109],
0.375]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [8, 9], 'B': [], 'k': 3}, [[238199717, 145934324, 431298261], [], 0.0]],
['identical sets',
{'A': [3, 8, 16], 'B': [16, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 100022, 497068074],
[238199717, 8753041, 431298261, 100022, 497068074],
1.0]],
['large values',
{'A': [1000000003, 7, 99], 'B': [1000000003, 8], 'k': 4},
[[711462923, 56169922, 914256891, 1208059556],
[238199717, 318725747, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [47, 135, 53, 125, 192, 104, 165, 180, 91],
'B': [125, 192, 104, 165, 180, 91, 144, 142, 45, 255],
'k': 4},
[[325621332, 298921234, 172996381, 100363], [76042063, 11287721, 139351251, 100270], 0.0]],
['overlapping sets k=6',
{'A': [37, 42, 89, 127, 77, 170, 4, 111, 27],
'B': [127, 77, 170, 4, 111, 27, 20, 114, 70, 228],
'k': 6},
[[27887117, 330532488, 78683252, 134317934, 178394676, 329803467],
[83636661, 330532488, 78683252, 134317934, 144309083, 104634115],
0.5]],
['overlapping sets k=8',
{'A': [67, 151, 142, 156, 93, 90, 105, 112, 40],
'B': [156, 93, 90, 105, 112, 40, 161, 43, 152, 287],
'k': 8},
[[349698805, 40364295, 9007630, 100208, 76137897, 255898163, 2762761, 235541441],
[206527646, 193351205, 9007630, 100208, 76137897, 366756119, 2762761, 71150961],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [9, 9], 'B': [], 'k': 3}, [[1341714962, 145934324, 2095823278], [], 0.0]],
['identical sets',
{'A': [3, 8, 17], 'B': [17, 8, 3], 'k': 5},
[[238199717, 8753041, 379637885, 1073841830, 497068074],
[238199717, 8753041, 379637885, 1073841830, 497068074],
1.0]],
['large values',
{'A': [1000000004, 7, 99], 'B': [1000000004, 8], 'k': 4},
[[1282168119, 56169922, 914256891, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [38, 155, 109, 179, 16, 111, 170, 114, 19],
'B': [179, 16, 111, 170, 114, 19, 18, 198, 125, 300],
'k': 4},
[[24089818, 330532488, 78683252, 100022], [83636661, 330532488, 78683252, 100022], 0.75]],
['overlapping sets k=6',
{'A': [10, 150, 23, 4, 69, 99, 130, 93, 198],
'B': [4, 69, 99, 130, 93, 198, 145, 154, 30, 206],
'k': 6},
[[119106031, 56169922, 182004004, 402753355, 231506909, 423911817],
[119106031, 56169922, 182004004, 268535505, 375784655, 423911817],
0.6667]],
['overlapping sets k=8',
{'A': [58, 185, 14, 110, 196, 126, 6, 158, 12],
'B': [110, 196, 126, 6, 158, 12, 124, 92, 187, 209],
'k': 8},
[[139386205, 618166001, 561641882, 268535474, 303645782, 450762946, 414415, 136172865],
[178652874, 254039033, 242672003, 268535660, 201389003, 198742465, 414415, 136172865],
0.25]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [10, 9], 'B': [], 'k': 3}, [[297746560, 145934324, 1612864648], [], 0.0]],
['identical sets',
{'A': [3, 8, 18], 'B': [18, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 1073841830, 497068074],
[238199717, 8753041, 431298261, 1073841830, 497068074],
1.0]],
['large values',
{'A': [1000000005, 7, 99], 'B': [1000000005, 8], 'k': 4},
[[771009766, 56169922, 877498790, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
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 sets k=4 | [[416840246, 618166001, 1828513775, 268535474], [416840246, 618166001, 1828513775, 268535474], 1.0] | [[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5] | Failed |
| overlapping sets k=6 | [[1341714962, 145934324, 2095823278, 939624104, 1491141548, 1210277829], [595480775, 755347284, 1078245642, 1610712765, 1881953819, 1257332004], 0.0] | [[321824033, 87781176, 406660754, 805406688, 307613469, 235695117], [146980803, 87781176, 509981506, 134317810, 307613469, 97986032], 0.3333] | Failed |
| overlapping sets k=8 | [[146980803, 161739951, 1673532647, 939624166, 1066243684, 1932840060, 2831830, 930514560], [146980803, 161739951, 1673532647, 939624166, 1066243684, 1932840060, 2831830, 930514560], 1.0] | [[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560], [143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257], 0.5] | Failed |
| both empty | [[], [], None] | [[], [], None] | Passed |
| one empty | [[178652874, 1151085506, 1397215521], [], 0.0] | [[178652874, 145934324, 1397215521], [], 0.0] | Failed |
| identical sets | [[1163074433, 8753041, 698607764, 1744930460, 497068074], [1163074433, 8753041, 698607764, 1744930460, 497068074], 1.0] | [[238199717, 8753041, 431298261, 268535474, 497068074], [238199717, 8753041, 431298261, 268535474, 497068074], 1.0] | Failed |
| large values | [[1282168119, 816035112, 914256891, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | [[651916080, 56169922, 661849663, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | Failed |
SHA-256 / 09d4f567c2f15f2ab44ce789b0c185023421fb9101c03957b92a9246057403ce
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
P = 2147483647
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941, 69069, 22695477]
Bc = [12345, 1013904223, 7, 99991, 31337, 424242, 1, 3]
def sig(s):
return [max((A[i] * v + Bc[i]) % P for v in s) for i in range(k)]
a, b = x['A'], x['B']
if not a and not b:
return [[], [], None]
if not a or not b:
return [sig(a) if a else [], sig(b) if b else [], 0.0]
sa, sb = sig(a), sig(b)
matches = sum(1 for i in range(k) if sa[i] == sb[i])
return [sa, sb, round(matches / k, 4)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overlapping sets k=4',
{'A': [185, 180, 93, 45, 14, 71, 154, 36, 166],
'B': [45, 14, 71, 154, 36, 166, 145, 34, 146, 221],
'k': 4},
[[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5]],
['overlapping sets k=6',
{'A': [137, 9, 132, 163, 55, 20, 170, 179, 119],
'B': [163, 55, 20, 170, 179, 119, 47, 41, 24, 251],
'k': 6},
[[321824033, 87781176, 406660754, 805406688, 307613469, 235695117],
[146980803, 87781176, 509981506, 134317810, 307613469, 97986032],
0.3333]],
['overlapping sets k=8',
{'A': [148, 51, 156, 91, 149, 73, 41, 176, 152],
'B': [91, 149, 73, 41, 176, 152, 140, 118, 113, 264],
'k': 8},
[[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560],
[143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [6, 9], 'B': [], 'k': 3}, [[178652874, 145934324, 1397215521], [], 0.0]],
['identical sets',
{'A': [3, 8, 14], 'B': [14, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 268535474, 497068074],
[238199717, 8753041, 431298261, 268535474, 497068074],
1.0]],
['large values',
{'A': [1000000001, 7, 99], 'B': [1000000001, 8], 'k': 4},
[[651916080, 56169922, 661849663, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [77, 180, 129, 27, 120, 79, 147, 135, 166],
'B': [27, 120, 79, 147, 135, 166, 178, 114, 109, 210],
'k': 4},
[[619558248, 314726861, 27022876, 134317872], [24089818, 314726861, 27022876, 134317872], 0.75]],
['overlapping sets k=6',
{'A': [43, 26, 163, 158, 61, 6, 58, 100, 105],
'B': [158, 61, 6, 58, 100, 105, 18, 10, 87, 294],
'k': 6},
[[178652874, 87781176, 327977509, 268535753, 216447956, 481067515],
[163463678, 193351205, 604294635, 268535753, 216447956, 272647769],
0.3333]],
['overlapping sets k=8',
{'A': [119, 125, 38, 35, 22, 123, 186, 169, 60],
'B': [35, 22, 123, 186, 169, 60, 55, 134, 69, 203],
'k': 8},
[[321824033, 24558668, 112328382, 402753417, 72170210, 94532592, 1519519, 499300497],
[440917719, 24558668, 112328382, 536971019, 72170210, 87884509, 1519519, 312214540],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [7, 9], 'B': [], 'k': 3}, [[1282168119, 145934324, 914256891], [], 0.0]],
['identical sets',
{'A': [3, 8, 15], 'B': [15, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 134317748, 337731375],
[238199717, 8753041, 431298261, 134317748, 337731375],
1.0]],
['large values',
{'A': [1000000002, 7, 99], 'B': [1000000002, 8], 'k': 4},
[[1282168119, 56169922, 178891033, 1208059556],
[238199717, 480984718, 178891033, 1073841830],
0.25]]],
[['overlapping sets k=4',
{'A': [21, 131, 85, 16, 192, 176, 186, 106, 14],
'B': [16, 192, 176, 186, 106, 14, 154, 67, 112, 276],
'k': 4},
[[416840246, 27093348, 345992755, 100022], [290151962, 27093348, 345992755, 100022], 0.75]],
['overlapping sets k=6',
{'A': [17, 173, 195, 128, 127, 162, 64, 34, 2],
'B': [128, 127, 162, 64, 34, 2, 4, 31, 120, 261],
'k': 6},
[[59559188, 103586803, 200019250, 100115, 95164537, 302952338],
[59559188, 343803435, 27022876, 100115, 125282443, 302952338],
0.5]],
['overlapping sets k=8',
{'A': [104, 160, 182, 180, 79, 129, 139, 39, 130],
'B': [180, 79, 129, 139, 39, 130, 181, 110, 50, 200],
'k': 8},
[[87433960, 164274631, 36030499, 100301, 19057977, 161789813, 2693692, 212845964],
[20292519, 314726861, 45038122, 134317872, 19057977, 161789813, 2693692, 244128109],
0.375]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [8, 9], 'B': [], 'k': 3}, [[238199717, 145934324, 431298261], [], 0.0]],
['identical sets',
{'A': [3, 8, 16], 'B': [16, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 100022, 497068074],
[238199717, 8753041, 431298261, 100022, 497068074],
1.0]],
['large values',
{'A': [1000000003, 7, 99], 'B': [1000000003, 8], 'k': 4},
[[711462923, 56169922, 914256891, 1208059556],
[238199717, 318725747, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [47, 135, 53, 125, 192, 104, 165, 180, 91],
'B': [125, 192, 104, 165, 180, 91, 144, 142, 45, 255],
'k': 4},
[[325621332, 298921234, 172996381, 100363], [76042063, 11287721, 139351251, 100270], 0.0]],
['overlapping sets k=6',
{'A': [37, 42, 89, 127, 77, 170, 4, 111, 27],
'B': [127, 77, 170, 4, 111, 27, 20, 114, 70, 228],
'k': 6},
[[27887117, 330532488, 78683252, 134317934, 178394676, 329803467],
[83636661, 330532488, 78683252, 134317934, 144309083, 104634115],
0.5]],
['overlapping sets k=8',
{'A': [67, 151, 142, 156, 93, 90, 105, 112, 40],
'B': [156, 93, 90, 105, 112, 40, 161, 43, 152, 287],
'k': 8},
[[349698805, 40364295, 9007630, 100208, 76137897, 255898163, 2762761, 235541441],
[206527646, 193351205, 9007630, 100208, 76137897, 366756119, 2762761, 71150961],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [9, 9], 'B': [], 'k': 3}, [[1341714962, 145934324, 2095823278], [], 0.0]],
['identical sets',
{'A': [3, 8, 17], 'B': [17, 8, 3], 'k': 5},
[[238199717, 8753041, 379637885, 1073841830, 497068074],
[238199717, 8753041, 379637885, 1073841830, 497068074],
1.0]],
['large values',
{'A': [1000000004, 7, 99], 'B': [1000000004, 8], 'k': 4},
[[1282168119, 56169922, 914256891, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [38, 155, 109, 179, 16, 111, 170, 114, 19],
'B': [179, 16, 111, 170, 114, 19, 18, 198, 125, 300],
'k': 4},
[[24089818, 330532488, 78683252, 100022], [83636661, 330532488, 78683252, 100022], 0.75]],
['overlapping sets k=6',
{'A': [10, 150, 23, 4, 69, 99, 130, 93, 198],
'B': [4, 69, 99, 130, 93, 198, 145, 154, 30, 206],
'k': 6},
[[119106031, 56169922, 182004004, 402753355, 231506909, 423911817],
[119106031, 56169922, 182004004, 268535505, 375784655, 423911817],
0.6667]],
['overlapping sets k=8',
{'A': [58, 185, 14, 110, 196, 126, 6, 158, 12],
'B': [110, 196, 126, 6, 158, 12, 124, 92, 187, 209],
'k': 8},
[[139386205, 618166001, 561641882, 268535474, 303645782, 450762946, 414415, 136172865],
[178652874, 254039033, 242672003, 268535660, 201389003, 198742465, 414415, 136172865],
0.25]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [10, 9], 'B': [], 'k': 3}, [[297746560, 145934324, 1612864648], [], 0.0]],
['identical sets',
{'A': [3, 8, 18], 'B': [18, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 1073841830, 497068074],
[238199717, 8753041, 431298261, 1073841830, 497068074],
1.0]],
['large values',
{'A': [1000000005, 7, 99], 'B': [1000000005, 8], 'k': 4},
[[771009766, 56169922, 877498790, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
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 sets k=4 | [[1695198721, 2066472286, 1940842150, 1610713075], [1211229379, 2129694794, 1940842150, 2013366191], 0.25] | [[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5] | Failed |
| overlapping sets k=6 | [[2108229323, 2037395712, 2095823278, 1744930801, 1954092692, 2094205631], [2108229323, 2037395712, 1673532647, 1744930801, 2060317158, 2094205631], 0.6667] | [[321824033, 87781176, 406660754, 805406688, 307613469, 235695117], [146980803, 87781176, 509981506, 134317810, 307613469, 97986032], 0.3333] | Failed |
| overlapping sets k=8 | [[1635651878, 1625851863, 1967865019, 1744930553, 2007204925, 2000097281, 12156145, 2065288410], [2020807708, 1807915347, 1752215892, 2013366129, 1958060379, 1932840060, 18234217, 2065288410], 0.125] | [[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560], [143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257], 0.5] | Failed |
| both empty | [[], [], None] | [[], [], None] | Passed |
| one empty | [[1341714962, 1151085506, 2095823278], [], 0.0] | [[178652874, 145934324, 1397215521], [], 0.0] | Failed |
| identical sets | [[1163074433, 618166001, 1828513775, 1744930460, 2041290518], [1163074433, 618166001, 1828513775, 1744930460, 2041290518], 1.0] | [[238199717, 8753041, 431298261, 268535474, 497068074], [238199717, 8753041, 431298261, 268535474, 497068074], 1.0] | Failed |
| large values | [[1873839250, 988826535, 1579219518, 1803382265], [651916080, 988826535, 661849663, 1803382265], 0.5] | [[651916080, 56169922, 661849663, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | Failed |
SHA-256 / 0e7061fee9d337aa8468c57a78049d9aaad3e374ad8cff4df2ac6cc15001ce53
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
P = 2147483647
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941, 69069, 22695477]
Bc = [12345, 1013904223, 7, 99991, 31337, 424242, 1, 3]
def sig(s):
return [min((A[i] * v + Bc[i]) % P for v in s) for i in range(k)]
a, b = x['A'], x['B']
if not a and not b:
return [[], [], None]
if not a or not b:
return [sig(a) if a else [], sig(b) if b else [], 0.0]
sa, sb = sig(a), sig(b)
matches = sum(1 for i in range(k) if sa[i] == sb[i])
return [sa, sb, round(matches / k, 4)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overlapping sets k=4',
{'A': [185, 180, 93, 45, 14, 71, 154, 36, 166],
'B': [45, 14, 71, 154, 36, 166, 145, 34, 146, 221],
'k': 4},
[[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5]],
['overlapping sets k=6',
{'A': [137, 9, 132, 163, 55, 20, 170, 179, 119],
'B': [163, 55, 20, 170, 179, 119, 47, 41, 24, 251],
'k': 6},
[[321824033, 87781176, 406660754, 805406688, 307613469, 235695117],
[146980803, 87781176, 509981506, 134317810, 307613469, 97986032],
0.3333]],
['overlapping sets k=8',
{'A': [148, 51, 156, 91, 149, 73, 41, 176, 152],
'B': [91, 149, 73, 41, 176, 152, 140, 118, 113, 264],
'k': 8},
[[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560],
[143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [6, 9], 'B': [], 'k': 3}, [[178652874, 145934324, 1397215521], [], 0.0]],
['identical sets',
{'A': [3, 8, 14], 'B': [14, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 268535474, 497068074],
[238199717, 8753041, 431298261, 268535474, 497068074],
1.0]],
['large values',
{'A': [1000000001, 7, 99], 'B': [1000000001, 8], 'k': 4},
[[651916080, 56169922, 661849663, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [77, 180, 129, 27, 120, 79, 147, 135, 166],
'B': [27, 120, 79, 147, 135, 166, 178, 114, 109, 210],
'k': 4},
[[619558248, 314726861, 27022876, 134317872], [24089818, 314726861, 27022876, 134317872], 0.75]],
['overlapping sets k=6',
{'A': [43, 26, 163, 158, 61, 6, 58, 100, 105],
'B': [158, 61, 6, 58, 100, 105, 18, 10, 87, 294],
'k': 6},
[[178652874, 87781176, 327977509, 268535753, 216447956, 481067515],
[163463678, 193351205, 604294635, 268535753, 216447956, 272647769],
0.3333]],
['overlapping sets k=8',
{'A': [119, 125, 38, 35, 22, 123, 186, 169, 60],
'B': [35, 22, 123, 186, 169, 60, 55, 134, 69, 203],
'k': 8},
[[321824033, 24558668, 112328382, 402753417, 72170210, 94532592, 1519519, 499300497],
[440917719, 24558668, 112328382, 536971019, 72170210, 87884509, 1519519, 312214540],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [7, 9], 'B': [], 'k': 3}, [[1282168119, 145934324, 914256891], [], 0.0]],
['identical sets',
{'A': [3, 8, 15], 'B': [15, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 134317748, 337731375],
[238199717, 8753041, 431298261, 134317748, 337731375],
1.0]],
['large values',
{'A': [1000000002, 7, 99], 'B': [1000000002, 8], 'k': 4},
[[1282168119, 56169922, 178891033, 1208059556],
[238199717, 480984718, 178891033, 1073841830],
0.25]]],
[['overlapping sets k=4',
{'A': [21, 131, 85, 16, 192, 176, 186, 106, 14],
'B': [16, 192, 176, 186, 106, 14, 154, 67, 112, 276],
'k': 4},
[[416840246, 27093348, 345992755, 100022], [290151962, 27093348, 345992755, 100022], 0.75]],
['overlapping sets k=6',
{'A': [17, 173, 195, 128, 127, 162, 64, 34, 2],
'B': [128, 127, 162, 64, 34, 2, 4, 31, 120, 261],
'k': 6},
[[59559188, 103586803, 200019250, 100115, 95164537, 302952338],
[59559188, 343803435, 27022876, 100115, 125282443, 302952338],
0.5]],
['overlapping sets k=8',
{'A': [104, 160, 182, 180, 79, 129, 139, 39, 130],
'B': [180, 79, 129, 139, 39, 130, 181, 110, 50, 200],
'k': 8},
[[87433960, 164274631, 36030499, 100301, 19057977, 161789813, 2693692, 212845964],
[20292519, 314726861, 45038122, 134317872, 19057977, 161789813, 2693692, 244128109],
0.375]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [8, 9], 'B': [], 'k': 3}, [[238199717, 145934324, 431298261], [], 0.0]],
['identical sets',
{'A': [3, 8, 16], 'B': [16, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 100022, 497068074],
[238199717, 8753041, 431298261, 100022, 497068074],
1.0]],
['large values',
{'A': [1000000003, 7, 99], 'B': [1000000003, 8], 'k': 4},
[[711462923, 56169922, 914256891, 1208059556],
[238199717, 318725747, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [47, 135, 53, 125, 192, 104, 165, 180, 91],
'B': [125, 192, 104, 165, 180, 91, 144, 142, 45, 255],
'k': 4},
[[325621332, 298921234, 172996381, 100363], [76042063, 11287721, 139351251, 100270], 0.0]],
['overlapping sets k=6',
{'A': [37, 42, 89, 127, 77, 170, 4, 111, 27],
'B': [127, 77, 170, 4, 111, 27, 20, 114, 70, 228],
'k': 6},
[[27887117, 330532488, 78683252, 134317934, 178394676, 329803467],
[83636661, 330532488, 78683252, 134317934, 144309083, 104634115],
0.5]],
['overlapping sets k=8',
{'A': [67, 151, 142, 156, 93, 90, 105, 112, 40],
'B': [156, 93, 90, 105, 112, 40, 161, 43, 152, 287],
'k': 8},
[[349698805, 40364295, 9007630, 100208, 76137897, 255898163, 2762761, 235541441],
[206527646, 193351205, 9007630, 100208, 76137897, 366756119, 2762761, 71150961],
0.5]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [9, 9], 'B': [], 'k': 3}, [[1341714962, 145934324, 2095823278], [], 0.0]],
['identical sets',
{'A': [3, 8, 17], 'B': [17, 8, 3], 'k': 5},
[[238199717, 8753041, 379637885, 1073841830, 497068074],
[238199717, 8753041, 379637885, 1073841830, 497068074],
1.0]],
['large values',
{'A': [1000000004, 7, 99], 'B': [1000000004, 8], 'k': 4},
[[1282168119, 56169922, 914256891, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
0.0]]],
[['overlapping sets k=4',
{'A': [38, 155, 109, 179, 16, 111, 170, 114, 19],
'B': [179, 16, 111, 170, 114, 19, 18, 198, 125, 300],
'k': 4},
[[24089818, 330532488, 78683252, 100022], [83636661, 330532488, 78683252, 100022], 0.75]],
['overlapping sets k=6',
{'A': [10, 150, 23, 4, 69, 99, 130, 93, 198],
'B': [4, 69, 99, 130, 93, 198, 145, 154, 30, 206],
'k': 6},
[[119106031, 56169922, 182004004, 402753355, 231506909, 423911817],
[119106031, 56169922, 182004004, 268535505, 375784655, 423911817],
0.6667]],
['overlapping sets k=8',
{'A': [58, 185, 14, 110, 196, 126, 6, 158, 12],
'B': [110, 196, 126, 6, 158, 12, 124, 92, 187, 209],
'k': 8},
[[139386205, 618166001, 561641882, 268535474, 303645782, 450762946, 414415, 136172865],
[178652874, 254039033, 242672003, 268535660, 201389003, 198742465, 414415, 136172865],
0.25]],
['both empty', {'A': [], 'B': [], 'k': 4}, [[], [], None]],
['one empty', {'A': [10, 9], 'B': [], 'k': 3}, [[297746560, 145934324, 1612864648], [], 0.0]],
['identical sets',
{'A': [3, 8, 18], 'B': [18, 8, 3], 'k': 5},
[[238199717, 8753041, 431298261, 1073841830, 497068074],
[238199717, 8753041, 431298261, 1073841830, 497068074],
1.0]],
['large values',
{'A': [1000000005, 7, 99], 'B': [1000000005, 8], 'k': 4},
[[771009766, 56169922, 877498790, 1208059556],
[238199717, 480984718, 431298261, 1073841830],
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 sets k=4 | [[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5] | [[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5] | Passed |
| overlapping sets k=6 | [[321824033, 87781176, 406660754, 805406688, 307613469, 235695117], [146980803, 87781176, 509981506, 134317810, 307613469, 97986032], 0.3333] | [[321824033, 87781176, 406660754, 805406688, 307613469, 235695117], [146980803, 87781176, 509981506, 134317810, 307613469, 97986032], 0.3333] | Passed |
| overlapping sets k=8 | [[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560], [143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257], 0.5] | [[111511433, 27093348, 898627007, 100332, 76137897, 413810294, 2831830, 930514560], [143183504, 27093348, 898627007, 100332, 110223490, 114735638, 2831830, 417105257], 0.5] | Passed |
| both empty | [[], [], None] | [[], [], None] | Passed |
| one empty | [[178652874, 145934324, 1397215521], [], 0.0] | [[178652874, 145934324, 1397215521], [], 0.0] | Passed |
| identical sets | [[238199717, 8753041, 431298261, 268535474, 497068074], [238199717, 8753041, 431298261, 268535474, 497068074], 1.0] | [[238199717, 8753041, 431298261, 268535474, 497068074], [238199717, 8753041, 431298261, 268535474, 497068074], 1.0] | Passed |
| large values | [[651916080, 56169922, 661849663, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | [[651916080, 56169922, 661849663, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | Passed |
SHA-256 / 2dcb08bafeea271b3f69ffe80fb0387f6d96f924542bfb17e924cfab91a4c3c3
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:45.273017+00:00.
Case digest / 45bcada74fcdd811ee3646b090529c81c12ba5a8211bba2ab11e5d350ea2bd65