FA-73251 / Probabilistic sketches / Open access
K-minimum-values distinct counting: union keeps shared hashes twice · case 01
Values present in both sketches occupy two union slots, overstating the union and its overlap.
ROOT CAUSE
The union concatenates both kept lists without de-duplication.
VERIFIED REPAIR
Take the k smallest distinct values of the combined kept sets.
Unsuccessful approach: Keeping every union value lets the overlap count include values beyond the k-th.
Case contract
Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].
Why this case matters
KMV sketches power approximate COUNT(DISTINCT) with set operations in analytics engines; the unbiased (k-1)/v_k form and the union rule are easy to get subtly wrong.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
def kept(hs):
return sorted(set(hs))[:k]
def est(vals):
if len(vals) < k:
return len(vals)
return round((k - 1) * 2 ** 32 / vals[k - 1])
A = kept(x['a'])
B = kept(x['b'])
U = sorted(A + B)[:k]
eu = est(U)
if len(U) < k:
inter = len(set(A) & set(B))
else:
both = sum(1 for v in U if v in A and v in B)
inter = round(both / k * eu)
return [est(A), est(B), eu, inter]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['streams 0 k=4',
{'a': [767117601,
1349057482,
512140804,
2709330522,
97797847,
2991703416,
247407200,
502807838,
953930153,
4276337012,
825867426,
927935964,
767117601,
1349057482,
512140804],
'b': [767117601,
1349057482,
512140804,
2709330522,
97797847,
3243866592,
2367279148,
2430077702,
2971523655,
1478379009],
'k': 4},
[25, 10, 25, 12]],
['streams 1 k=5',
{'a': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
844670565,
1574495990,
3092220355,
1623550118,
1677170996,
355484359,
1577212364,
222802868,
3302194479,
1232086826,
4029593972,
846568436,
2280170916,
2039090929,
2369642582],
'b': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
3736327325,
4143402618,
3225214513,
2668680618,
690502660,
4038350892,
2109753841],
'k': 5},
[19, 8, 20, 0]],
['streams 2 k=3',
{'a': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492,
2831125304,
3278849932,
2146240677],
'b': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492],
'k': 3},
[8, 8, 8, 8]],
['streams 3 k=6',
{'a': [1347661301,
1126717335,
1593064253,
3578257729,
3263214743,
1485141222,
507376609,
870194170,
405495016,
463928501,
3212162911,
200606854,
3827729694,
3442164173,
3023093882,
3815698597,
1832272475,
945613159,
136487868,
1731202674,
3903788721,
2182062801,
1489904681,
708728146,
1980483838,
1269587876,
3424059671,
3167970027,
3314237818,
161588255,
1347661301,
1126717335,
1593064253],
'b': [1347661301,
1126717335,
1593064253,
3578257729,
1184217959,
795322907,
2681969582,
1479728863,
915549410,
1616093956,
1998008578,
566339276],
'k': 6},
[42, 16, 42, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
2958152150,
1105148405,
1551545311,
2382410247,
299374495,
3902367104,
3814609907,
616469427,
2903262975,
2673828359],
'b': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
1904501607,
2415525956,
972943297,
1101134287,
4209348669],
'k': 4},
[12, 12, 13, 6]],
['streams 1 k=5',
{'a': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
3882412494,
3638249284,
629708383,
2652904385,
619827854,
2252659737,
4038367328,
751384629,
2736132274,
2052511795,
1546656212,
2490980400,
1192536461,
3397803296,
3575214874],
'b': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
801257707,
231860101,
1552367569,
2200650299,
1300574527,
1169595163,
1486586779],
'k': 5},
[14, 14, 23, 5]],
['streams 2 k=3',
{'a': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795,
3366336454,
3360405550,
3252767639],
'b': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795],
'k': 3},
[4, 4, 4, 4]],
['streams 3 k=6',
{'a': [1412588383,
1682740534,
1107531143,
3554458900,
2859580621,
3296482680,
2191809106,
4155174719,
3651321607,
3668767012,
3871583709,
53568284,
232037959,
2442976016,
217741541,
3800768541,
2101516655,
2409083912,
918078055,
2969028849,
3001715579,
3922319082,
2100936555,
2284049623,
3774876442,
3238172673,
3672802287,
3806827876,
2442511505,
3389659053,
1412588383,
1682740534,
1107531143],
'b': [1412588383,
1682740534,
1107531143,
3554458900,
321792195,
4055119656,
4005216604,
4067339772,
2438348428,
2893845634,
4168021051,
1191737207],
'k': 6},
[15, 9, 19, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
874550077,
874052348,
2099297276,
2917681254,
3461079448,
4523874,
1892412104,
1348947199,
2220012561,
4274378431],
'b': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
320314762,
2913424927,
3760403017,
3874375803,
3498294633],
'k': 4},
[15, 8, 15, 4]],
['streams 1 k=5',
{'a': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
429269052,
4120988501,
2192756914,
2080257154,
215643658,
2236181558,
3506517446,
3204080191,
2539102762,
1231819029,
129435166,
1969895105,
1451722624,
4208772152,
2008054505],
'b': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
3624728915,
4097927174,
3560188535,
2101457494,
1008357362,
2961406180,
2250944138],
'k': 5},
[45, 13, 45, 27]],
['streams 2 k=3',
{'a': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124,
163959442,
4243274568,
1097577740],
'b': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124],
'k': 3},
[28, 28, 28, 28]],
['streams 3 k=6',
{'a': [3736875704,
2512119594,
3432728552,
1249721439,
4076278131,
1681936286,
3644273863,
1144985545,
1058589555,
2372866836,
2747157307,
319015226,
1616345963,
3215957022,
2575778964,
2002333856,
105152923,
971771153,
3904739092,
139512839,
3596088601,
3125993293,
3698817286,
571115313,
2651377839,
404892510,
335085347,
3997319691,
423428202,
1253418186,
3736875704,
2512119594,
3432728552],
'b': [3736875704,
2512119594,
3432728552,
1249721439,
2190917676,
1217641816,
2195352441,
1962797028,
1369215451,
146219861,
2422264426,
2740291298],
'k': 6},
[51, 10, 53, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
469293850,
3311372855,
3291632216,
3532104316,
792576761,
2383663819,
3796612359,
534629630,
3752143492,
3784451643],
'b': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
778329530,
4126190270,
369138172,
3244871941,
426427744],
'k': 4},
[5, 17, 24, 6]],
['streams 1 k=5',
{'a': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
2365171429,
473117839,
1494688212,
3130081894,
3456600902,
1870835644,
1831585095,
856053019,
2401707901,
8291469,
994865049,
2075147938,
2281118336,
470394482,
2564274781],
'b': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
3616671026,
3377000285,
291138770,
4144176995,
410153163,
1894447883,
2251698],
'k': 5},
[36, 42, 59, 24]],
['streams 2 k=3',
{'a': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100,
3123627193,
2732919500,
1916452664],
'b': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100],
'k': 3},
[25, 25, 25, 25]],
['streams 3 k=6',
{'a': [920449838,
3707669583,
2705746824,
603387996,
145050205,
1943098641,
2902033596,
942056830,
1094682071,
482655062,
1597161973,
2776457123,
540173509,
49617459,
3062849472,
721066780,
1881851915,
2771669550,
271560229,
4250659366,
849113494,
2890310823,
2849978717,
2813753673,
2723489037,
3843541794,
2539258177,
294140292,
131741950,
1174692757,
920449838,
3707669583,
2705746824],
'b': [920449838,
3707669583,
2705746824,
603387996,
396707761,
853541794,
990402306,
2774188573,
1932619200,
40971593,
4209408016,
3008903819],
'k': 6},
[44, 22, 73, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
3402435104,
2615317700,
2901867586,
2191387195,
3244643901,
143617512,
4128185702,
3695416152,
3485519680,
1295479236],
'b': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
2172377362,
122431251,
2879905546,
3080363355,
742472857],
'k': 4},
[6, 6, 10, 2]],
['streams 1 k=5',
{'a': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3856414966,
182199786,
3302563887,
3489282613,
3728782849,
2555406465,
3392268813,
468049757,
2334691707,
3652253765,
2830979039,
2618409554,
629677788,
1134145340,
1003578828],
'b': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3383921903,
1576598490,
1966729080,
3816342364,
951010101,
559264201,
3070372495],
'k': 5},
[17, 17, 27, 11]],
['streams 2 k=3',
{'a': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371,
618180559,
2081251765,
530858903],
'b': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371],
'k': 3},
[14, 14, 14, 14]],
['streams 3 k=6',
{'a': [1308497545,
1688068524,
2659577736,
1794751184,
3886248964,
2353903802,
3929595655,
3522020961,
4226953245,
1619288587,
3373914572,
808857433,
2095738713,
3699811607,
2323854089,
4254321459,
2563706603,
1910759716,
2164426481,
690823666,
2412713602,
1704719407,
2407797195,
541403854,
3575208143,
381803083,
3474890246,
3033023633,
2039329698,
3301104757,
1308497545,
1688068524,
2659577736],
'b': [1308497545,
1688068524,
2659577736,
1794751184,
923787522,
3928497192,
1582544665,
3091940628,
1369092784,
2483888591,
2347320516,
1678251482],
'k': 6},
[13, 13, 16, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]]]
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 |
|---|---|---|---|
| streams 0 k=4 | [25, 10, 26, 13] | [25, 10, 25, 12] | Failed |
| streams 1 k=5 | [19, 8, 20, 0] | [19, 8, 20, 0] | Passed |
| streams 2 k=3 | [8, 8, 72, 72] | [8, 8, 8, 8] | Failed |
| streams 3 k=6 | [42, 16, 42, 0] | [42, 16, 42, 0] | Passed |
| small exact sets | [3, 2, 419021200, 167608480] | [3, 2, 4, 1] | Failed |
| exactly k distinct | [29, 2, 86, 57] | [29, 2, 43, 14] | Failed |
| shared value beyond union sketch | [14, 14, 43, 0] | [14, 14, 43, 0] | Passed |
| duplicated small hashes | [6, 954437177, 1073741824, 715827883] | [6, 954437177, 954437177, 318145726] | Failed |
SHA-256 / 3b5e858073f0393b6f9df6502c1f3768785dd35995bd6cf15fbeda44e60216c0
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']
def kept(hs):
return sorted(set(hs))[:k]
def est(vals):
if len(vals) < k:
return len(vals)
return round((k - 1) * 2 ** 32 / vals[k - 1])
A = kept(x['a'])
B = kept(x['b'])
U = sorted(set(A) | set(B))
eu = est(U)
if len(U) < k:
inter = len(set(A) & set(B))
else:
both = sum(1 for v in U if v in A and v in B)
inter = round(both / k * eu)
return [est(A), est(B), eu, inter]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['streams 0 k=4',
{'a': [767117601,
1349057482,
512140804,
2709330522,
97797847,
2991703416,
247407200,
502807838,
953930153,
4276337012,
825867426,
927935964,
767117601,
1349057482,
512140804],
'b': [767117601,
1349057482,
512140804,
2709330522,
97797847,
3243866592,
2367279148,
2430077702,
2971523655,
1478379009],
'k': 4},
[25, 10, 25, 12]],
['streams 1 k=5',
{'a': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
844670565,
1574495990,
3092220355,
1623550118,
1677170996,
355484359,
1577212364,
222802868,
3302194479,
1232086826,
4029593972,
846568436,
2280170916,
2039090929,
2369642582],
'b': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
3736327325,
4143402618,
3225214513,
2668680618,
690502660,
4038350892,
2109753841],
'k': 5},
[19, 8, 20, 0]],
['streams 2 k=3',
{'a': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492,
2831125304,
3278849932,
2146240677],
'b': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492],
'k': 3},
[8, 8, 8, 8]],
['streams 3 k=6',
{'a': [1347661301,
1126717335,
1593064253,
3578257729,
3263214743,
1485141222,
507376609,
870194170,
405495016,
463928501,
3212162911,
200606854,
3827729694,
3442164173,
3023093882,
3815698597,
1832272475,
945613159,
136487868,
1731202674,
3903788721,
2182062801,
1489904681,
708728146,
1980483838,
1269587876,
3424059671,
3167970027,
3314237818,
161588255,
1347661301,
1126717335,
1593064253],
'b': [1347661301,
1126717335,
1593064253,
3578257729,
1184217959,
795322907,
2681969582,
1479728863,
915549410,
1616093956,
1998008578,
566339276],
'k': 6},
[42, 16, 42, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
2958152150,
1105148405,
1551545311,
2382410247,
299374495,
3902367104,
3814609907,
616469427,
2903262975,
2673828359],
'b': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
1904501607,
2415525956,
972943297,
1101134287,
4209348669],
'k': 4},
[12, 12, 13, 6]],
['streams 1 k=5',
{'a': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
3882412494,
3638249284,
629708383,
2652904385,
619827854,
2252659737,
4038367328,
751384629,
2736132274,
2052511795,
1546656212,
2490980400,
1192536461,
3397803296,
3575214874],
'b': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
801257707,
231860101,
1552367569,
2200650299,
1300574527,
1169595163,
1486586779],
'k': 5},
[14, 14, 23, 5]],
['streams 2 k=3',
{'a': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795,
3366336454,
3360405550,
3252767639],
'b': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795],
'k': 3},
[4, 4, 4, 4]],
['streams 3 k=6',
{'a': [1412588383,
1682740534,
1107531143,
3554458900,
2859580621,
3296482680,
2191809106,
4155174719,
3651321607,
3668767012,
3871583709,
53568284,
232037959,
2442976016,
217741541,
3800768541,
2101516655,
2409083912,
918078055,
2969028849,
3001715579,
3922319082,
2100936555,
2284049623,
3774876442,
3238172673,
3672802287,
3806827876,
2442511505,
3389659053,
1412588383,
1682740534,
1107531143],
'b': [1412588383,
1682740534,
1107531143,
3554458900,
321792195,
4055119656,
4005216604,
4067339772,
2438348428,
2893845634,
4168021051,
1191737207],
'k': 6},
[15, 9, 19, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
874550077,
874052348,
2099297276,
2917681254,
3461079448,
4523874,
1892412104,
1348947199,
2220012561,
4274378431],
'b': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
320314762,
2913424927,
3760403017,
3874375803,
3498294633],
'k': 4},
[15, 8, 15, 4]],
['streams 1 k=5',
{'a': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
429269052,
4120988501,
2192756914,
2080257154,
215643658,
2236181558,
3506517446,
3204080191,
2539102762,
1231819029,
129435166,
1969895105,
1451722624,
4208772152,
2008054505],
'b': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
3624728915,
4097927174,
3560188535,
2101457494,
1008357362,
2961406180,
2250944138],
'k': 5},
[45, 13, 45, 27]],
['streams 2 k=3',
{'a': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124,
163959442,
4243274568,
1097577740],
'b': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124],
'k': 3},
[28, 28, 28, 28]],
['streams 3 k=6',
{'a': [3736875704,
2512119594,
3432728552,
1249721439,
4076278131,
1681936286,
3644273863,
1144985545,
1058589555,
2372866836,
2747157307,
319015226,
1616345963,
3215957022,
2575778964,
2002333856,
105152923,
971771153,
3904739092,
139512839,
3596088601,
3125993293,
3698817286,
571115313,
2651377839,
404892510,
335085347,
3997319691,
423428202,
1253418186,
3736875704,
2512119594,
3432728552],
'b': [3736875704,
2512119594,
3432728552,
1249721439,
2190917676,
1217641816,
2195352441,
1962797028,
1369215451,
146219861,
2422264426,
2740291298],
'k': 6},
[51, 10, 53, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
469293850,
3311372855,
3291632216,
3532104316,
792576761,
2383663819,
3796612359,
534629630,
3752143492,
3784451643],
'b': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
778329530,
4126190270,
369138172,
3244871941,
426427744],
'k': 4},
[5, 17, 24, 6]],
['streams 1 k=5',
{'a': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
2365171429,
473117839,
1494688212,
3130081894,
3456600902,
1870835644,
1831585095,
856053019,
2401707901,
8291469,
994865049,
2075147938,
2281118336,
470394482,
2564274781],
'b': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
3616671026,
3377000285,
291138770,
4144176995,
410153163,
1894447883,
2251698],
'k': 5},
[36, 42, 59, 24]],
['streams 2 k=3',
{'a': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100,
3123627193,
2732919500,
1916452664],
'b': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100],
'k': 3},
[25, 25, 25, 25]],
['streams 3 k=6',
{'a': [920449838,
3707669583,
2705746824,
603387996,
145050205,
1943098641,
2902033596,
942056830,
1094682071,
482655062,
1597161973,
2776457123,
540173509,
49617459,
3062849472,
721066780,
1881851915,
2771669550,
271560229,
4250659366,
849113494,
2890310823,
2849978717,
2813753673,
2723489037,
3843541794,
2539258177,
294140292,
131741950,
1174692757,
920449838,
3707669583,
2705746824],
'b': [920449838,
3707669583,
2705746824,
603387996,
396707761,
853541794,
990402306,
2774188573,
1932619200,
40971593,
4209408016,
3008903819],
'k': 6},
[44, 22, 73, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
3402435104,
2615317700,
2901867586,
2191387195,
3244643901,
143617512,
4128185702,
3695416152,
3485519680,
1295479236],
'b': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
2172377362,
122431251,
2879905546,
3080363355,
742472857],
'k': 4},
[6, 6, 10, 2]],
['streams 1 k=5',
{'a': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3856414966,
182199786,
3302563887,
3489282613,
3728782849,
2555406465,
3392268813,
468049757,
2334691707,
3652253765,
2830979039,
2618409554,
629677788,
1134145340,
1003578828],
'b': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3383921903,
1576598490,
1966729080,
3816342364,
951010101,
559264201,
3070372495],
'k': 5},
[17, 17, 27, 11]],
['streams 2 k=3',
{'a': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371,
618180559,
2081251765,
530858903],
'b': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371],
'k': 3},
[14, 14, 14, 14]],
['streams 3 k=6',
{'a': [1308497545,
1688068524,
2659577736,
1794751184,
3886248964,
2353903802,
3929595655,
3522020961,
4226953245,
1619288587,
3373914572,
808857433,
2095738713,
3699811607,
2323854089,
4254321459,
2563706603,
1910759716,
2164426481,
690823666,
2412713602,
1704719407,
2407797195,
541403854,
3575208143,
381803083,
3474890246,
3033023633,
2039329698,
3301104757,
1308497545,
1688068524,
2659577736],
'b': [1308497545,
1688068524,
2659577736,
1794751184,
923787522,
3928497192,
1582544665,
3091940628,
1369092784,
2483888591,
2347320516,
1678251482],
'k': 6},
[13, 13, 16, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]]]
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 |
|---|---|---|---|
| streams 0 k=4 | [25, 10, 25, 12] | [25, 10, 25, 12] | Passed |
| streams 1 k=5 | [19, 8, 20, 4] | [19, 8, 20, 0] | Failed |
| streams 2 k=3 | [8, 8, 8, 8] | [8, 8, 8, 8] | Passed |
| streams 3 k=6 | [42, 16, 42, 0] | [42, 16, 42, 0] | Passed |
| small exact sets | [3, 2, 4, 1] | [3, 2, 4, 1] | Passed |
| exactly k distinct | [29, 2, 43, 14] | [29, 2, 43, 14] | Passed |
| shared value beyond union sketch | [14, 14, 43, 14] | [14, 14, 43, 0] | Failed |
| duplicated small hashes | [6, 954437177, 954437177, 318145726] | [6, 954437177, 954437177, 318145726] | Passed |
SHA-256 / 9f6146ea6213dc92d1c52eed427dc8bfaca021313870347f89d472d8809f266b
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']
def kept(hs):
return sorted(set(hs))[:k]
def est(vals):
if len(vals) < k:
return len(vals)
return round((k - 1) * 2 ** 32 / vals[k - 1])
A = kept(x['a'])
B = kept(x['b'])
U = sorted(set(A) | set(B))[:k]
eu = est(U)
if len(U) < k:
inter = len(set(A) & set(B))
else:
both = sum(1 for v in U if v in A and v in B)
inter = round(both / k * eu)
return [est(A), est(B), eu, inter]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['streams 0 k=4',
{'a': [767117601,
1349057482,
512140804,
2709330522,
97797847,
2991703416,
247407200,
502807838,
953930153,
4276337012,
825867426,
927935964,
767117601,
1349057482,
512140804],
'b': [767117601,
1349057482,
512140804,
2709330522,
97797847,
3243866592,
2367279148,
2430077702,
2971523655,
1478379009],
'k': 4},
[25, 10, 25, 12]],
['streams 1 k=5',
{'a': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
844670565,
1574495990,
3092220355,
1623550118,
1677170996,
355484359,
1577212364,
222802868,
3302194479,
1232086826,
4029593972,
846568436,
2280170916,
2039090929,
2369642582],
'b': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
3736327325,
4143402618,
3225214513,
2668680618,
690502660,
4038350892,
2109753841],
'k': 5},
[19, 8, 20, 0]],
['streams 2 k=3',
{'a': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492,
2831125304,
3278849932,
2146240677],
'b': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492],
'k': 3},
[8, 8, 8, 8]],
['streams 3 k=6',
{'a': [1347661301,
1126717335,
1593064253,
3578257729,
3263214743,
1485141222,
507376609,
870194170,
405495016,
463928501,
3212162911,
200606854,
3827729694,
3442164173,
3023093882,
3815698597,
1832272475,
945613159,
136487868,
1731202674,
3903788721,
2182062801,
1489904681,
708728146,
1980483838,
1269587876,
3424059671,
3167970027,
3314237818,
161588255,
1347661301,
1126717335,
1593064253],
'b': [1347661301,
1126717335,
1593064253,
3578257729,
1184217959,
795322907,
2681969582,
1479728863,
915549410,
1616093956,
1998008578,
566339276],
'k': 6},
[42, 16, 42, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
2958152150,
1105148405,
1551545311,
2382410247,
299374495,
3902367104,
3814609907,
616469427,
2903262975,
2673828359],
'b': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
1904501607,
2415525956,
972943297,
1101134287,
4209348669],
'k': 4},
[12, 12, 13, 6]],
['streams 1 k=5',
{'a': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
3882412494,
3638249284,
629708383,
2652904385,
619827854,
2252659737,
4038367328,
751384629,
2736132274,
2052511795,
1546656212,
2490980400,
1192536461,
3397803296,
3575214874],
'b': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
801257707,
231860101,
1552367569,
2200650299,
1300574527,
1169595163,
1486586779],
'k': 5},
[14, 14, 23, 5]],
['streams 2 k=3',
{'a': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795,
3366336454,
3360405550,
3252767639],
'b': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795],
'k': 3},
[4, 4, 4, 4]],
['streams 3 k=6',
{'a': [1412588383,
1682740534,
1107531143,
3554458900,
2859580621,
3296482680,
2191809106,
4155174719,
3651321607,
3668767012,
3871583709,
53568284,
232037959,
2442976016,
217741541,
3800768541,
2101516655,
2409083912,
918078055,
2969028849,
3001715579,
3922319082,
2100936555,
2284049623,
3774876442,
3238172673,
3672802287,
3806827876,
2442511505,
3389659053,
1412588383,
1682740534,
1107531143],
'b': [1412588383,
1682740534,
1107531143,
3554458900,
321792195,
4055119656,
4005216604,
4067339772,
2438348428,
2893845634,
4168021051,
1191737207],
'k': 6},
[15, 9, 19, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
874550077,
874052348,
2099297276,
2917681254,
3461079448,
4523874,
1892412104,
1348947199,
2220012561,
4274378431],
'b': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
320314762,
2913424927,
3760403017,
3874375803,
3498294633],
'k': 4},
[15, 8, 15, 4]],
['streams 1 k=5',
{'a': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
429269052,
4120988501,
2192756914,
2080257154,
215643658,
2236181558,
3506517446,
3204080191,
2539102762,
1231819029,
129435166,
1969895105,
1451722624,
4208772152,
2008054505],
'b': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
3624728915,
4097927174,
3560188535,
2101457494,
1008357362,
2961406180,
2250944138],
'k': 5},
[45, 13, 45, 27]],
['streams 2 k=3',
{'a': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124,
163959442,
4243274568,
1097577740],
'b': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124],
'k': 3},
[28, 28, 28, 28]],
['streams 3 k=6',
{'a': [3736875704,
2512119594,
3432728552,
1249721439,
4076278131,
1681936286,
3644273863,
1144985545,
1058589555,
2372866836,
2747157307,
319015226,
1616345963,
3215957022,
2575778964,
2002333856,
105152923,
971771153,
3904739092,
139512839,
3596088601,
3125993293,
3698817286,
571115313,
2651377839,
404892510,
335085347,
3997319691,
423428202,
1253418186,
3736875704,
2512119594,
3432728552],
'b': [3736875704,
2512119594,
3432728552,
1249721439,
2190917676,
1217641816,
2195352441,
1962797028,
1369215451,
146219861,
2422264426,
2740291298],
'k': 6},
[51, 10, 53, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
469293850,
3311372855,
3291632216,
3532104316,
792576761,
2383663819,
3796612359,
534629630,
3752143492,
3784451643],
'b': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
778329530,
4126190270,
369138172,
3244871941,
426427744],
'k': 4},
[5, 17, 24, 6]],
['streams 1 k=5',
{'a': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
2365171429,
473117839,
1494688212,
3130081894,
3456600902,
1870835644,
1831585095,
856053019,
2401707901,
8291469,
994865049,
2075147938,
2281118336,
470394482,
2564274781],
'b': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
3616671026,
3377000285,
291138770,
4144176995,
410153163,
1894447883,
2251698],
'k': 5},
[36, 42, 59, 24]],
['streams 2 k=3',
{'a': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100,
3123627193,
2732919500,
1916452664],
'b': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100],
'k': 3},
[25, 25, 25, 25]],
['streams 3 k=6',
{'a': [920449838,
3707669583,
2705746824,
603387996,
145050205,
1943098641,
2902033596,
942056830,
1094682071,
482655062,
1597161973,
2776457123,
540173509,
49617459,
3062849472,
721066780,
1881851915,
2771669550,
271560229,
4250659366,
849113494,
2890310823,
2849978717,
2813753673,
2723489037,
3843541794,
2539258177,
294140292,
131741950,
1174692757,
920449838,
3707669583,
2705746824],
'b': [920449838,
3707669583,
2705746824,
603387996,
396707761,
853541794,
990402306,
2774188573,
1932619200,
40971593,
4209408016,
3008903819],
'k': 6},
[44, 22, 73, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
3402435104,
2615317700,
2901867586,
2191387195,
3244643901,
143617512,
4128185702,
3695416152,
3485519680,
1295479236],
'b': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
2172377362,
122431251,
2879905546,
3080363355,
742472857],
'k': 4},
[6, 6, 10, 2]],
['streams 1 k=5',
{'a': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3856414966,
182199786,
3302563887,
3489282613,
3728782849,
2555406465,
3392268813,
468049757,
2334691707,
3652253765,
2830979039,
2618409554,
629677788,
1134145340,
1003578828],
'b': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3383921903,
1576598490,
1966729080,
3816342364,
951010101,
559264201,
3070372495],
'k': 5},
[17, 17, 27, 11]],
['streams 2 k=3',
{'a': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371,
618180559,
2081251765,
530858903],
'b': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371],
'k': 3},
[14, 14, 14, 14]],
['streams 3 k=6',
{'a': [1308497545,
1688068524,
2659577736,
1794751184,
3886248964,
2353903802,
3929595655,
3522020961,
4226953245,
1619288587,
3373914572,
808857433,
2095738713,
3699811607,
2323854089,
4254321459,
2563706603,
1910759716,
2164426481,
690823666,
2412713602,
1704719407,
2407797195,
541403854,
3575208143,
381803083,
3474890246,
3033023633,
2039329698,
3301104757,
1308497545,
1688068524,
2659577736],
'b': [1308497545,
1688068524,
2659577736,
1794751184,
923787522,
3928497192,
1582544665,
3091940628,
1369092784,
2483888591,
2347320516,
1678251482],
'k': 6},
[13, 13, 16, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]]]
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 |
|---|---|---|---|
| streams 0 k=4 | [25, 10, 25, 12] | [25, 10, 25, 12] | Passed |
| streams 1 k=5 | [19, 8, 20, 0] | [19, 8, 20, 0] | Passed |
| streams 2 k=3 | [8, 8, 8, 8] | [8, 8, 8, 8] | Passed |
| streams 3 k=6 | [42, 16, 42, 0] | [42, 16, 42, 0] | Passed |
| small exact sets | [3, 2, 4, 1] | [3, 2, 4, 1] | Passed |
| exactly k distinct | [29, 2, 43, 14] | [29, 2, 43, 14] | Passed |
| shared value beyond union sketch | [14, 14, 43, 0] | [14, 14, 43, 0] | Passed |
| duplicated small hashes | [6, 954437177, 954437177, 318145726] | [6, 954437177, 954437177, 318145726] | Passed |
SHA-256 / ec4fd9e25ef3c88447d7d8016f7210714f9324a2a34a4ea3aef1ff6546ed2683
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.839866+00:00.
Case digest / ffd89b52e6e1cc6c5684d6cccd5d195e82d6d84c88cdb4a5ebe66f5823b376b1