FA-73201 / Probabilistic sketches / Open access
MinHash Jaccard estimation: offset added after reduction · case 01
Signature values exceed the field and disagree with producers that reduce the full expression.
ROOT CAUSE
The offset is added after reducing A_i v modulo the prime.
VERIFIED REPAIR
Reduce (A_i v + B_i) modulo the prime.
Unsuccessful approach: Reducing only the input leaves the whole expression unreduced.
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 [min((A[i] * v % P + Bc[i]) 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, 1230113641, 69675629, 268535474], [51964590, 1230113641, 69675629, 268535474], 0.75] | [[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5] | Failed |
| overlapping sets k=6 | [[321824033, 1169425813, 406660754, 805406688, 307613469, 235695117], [146980803, 1169425813, 509981506, 134317810, 307613469, 97986032], 0.3333] | [[321824033, 87781176, 406660754, 805406688, 307613469, 235695117], [146980803, 87781176, 509981506, 134317810, 307613469, 97986032], 0.3333] | Failed |
| overlapping sets k=8 | [[111511433, 1106203305, 898627007, 100332, 76137897, 413810294, 2831830, 930514560], [143183504, 1351489297, 898627007, 100332, 110223490, 114735638, 2831830, 417105257], 0.375] | [[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 | [[238199717, 2156236688, 431298261, 268535474, 497068074], [238199717, 2156236688, 431298261, 268535474, 497068074], 1.0] | [[238199717, 8753041, 431298261, 268535474, 497068074], [238199717, 8753041, 431298261, 268535474, 497068074], 1.0] | Failed |
| large values | [[651916080, 2203653569, 661849663, 1208059556], [238199717, 2628468365, 431298261, 1073841830], 0.0] | [[651916080, 56169922, 661849663, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | Failed |
SHA-256 / 931aa00a8deaa3a6cdedc43dc8071f405f71d8b5bdb554774da4d6401864a9a2
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 [min((A[i] * (v % P) + Bc[i]) 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 | [[15449225775, 26387969765, 23303350245, 28185822885], [15449225775, 26387969765, 23303350245, 28185822885], 1.0] | [[139386205, 618166001, 69675629, 268535474], [51964590, 359609062, 69675629, 268535474], 0.5] | Failed |
| overlapping sets k=6 | [[9931649550, 17325803500, 14980725160, 18119493280, 14376043430, 14095179711], [22070317245, 37262569283, 33290500347, 40265418411, 31946724877, 31322103062], 0.0] | [[321824033, 87781176, 406660754, 805406688, 307613469, 235695117], [146980803, 87781176, 509981506, 134317810, 307613469, 97986032], 0.3333] | Failed |
| overlapping sets k=8 | [[45244137390, 75323667596, 68245525704, 82544002752, 65490753094, 64209865823, 2831830, 930514560], [45244137390, 75323667596, 68245525704, 82544002752, 65490753094, 64209865823, 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 | [[6621103815, 11888503741, 9987150109], [], 0.0] | [[178652874, 145934324, 1397215521], [], 0.0] | Failed |
| identical sets | [[3310558080, 6451203982, 4993575058, 6039897754, 4792035368], [3310558080, 6451203982, 4993575058, 6039897754, 4792035368], 1.0] | [[238199717, 8753041, 431298261, 268535474, 497068074], [238199717, 8753041, 431298261, 268535474, 497068074], 1.0] | Failed |
| large values | [[7724619060, 13700936994, 11651675126, 14092961438], [8828134305, 15513370247, 13316200143, 16106227359], 0.0] | [[651916080, 56169922, 661849663, 1208059556], [238199717, 480984718, 431298261, 1073841830], 0.0] | Failed |
SHA-256 / 47035ae7e54a149e46150e05c56d0140f8c1a4af245cea814ab059ce59bdf5da
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.327478+00:00.
Case digest / 2ee284f87dd0fea5b8bfb2205d239fd2440a4863374107a692a9f533ea4bb982