FA-73011 / Probabilistic sketches / Open access
HyperLogLog cardinality estimate: estimate truncated instead of rounded · case 01
Reported counts are systematically one lower whenever the fractional part is at least one half.
ROOT CAUSE
The final estimate is truncated toward zero.
VERIFIED REPAIR
Round the final estimate to the nearest integer.
Unsuccessful approach: Ceiling rounds up every non-integer estimate.
Case contract
Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].
Why this case matters
Distinct-count dashboards and query planners rely on the bias corrections of the HyperLogLog estimator at both small and large cardinalities.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
regs = x['regs']
m = len(regs)
if m == 16:
alpha = 0.673
elif m == 32:
alpha = 0.697
elif m == 64:
alpha = 0.709
else:
alpha = 0.7213 / (1 + 1.079 / m)
E = alpha * m * m / sum(2.0 ** -r for r in regs)
V = regs.count(0)
if E <= 2.5 * m and V > 0:
E = m * math.log(m / V)
elif E > (2 ** 32) / 30:
E = -(2 ** 32) * math.log(1 - E / 2 ** 32)
return [int(E), V]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 1, 1]}, [8, 10]],
['dense m=32',
{'regs': [4,
5,
2,
2,
6,
6,
3,
6,
3,
5,
6,
6,
2,
4,
3,
6,
2,
3,
6,
5,
2,
4,
5,
4,
4,
4,
4,
2,
4,
3,
6,
6]},
[247, 0]],
['dense m=64',
{'regs': [7,
3,
7,
8,
6,
6,
4,
6,
7,
4,
6,
4,
3,
3,
8,
8,
3,
8,
8,
8,
8,
8,
5,
4,
8,
7,
6,
6,
8,
3,
3,
8,
8,
8,
8,
6,
3,
6,
4,
3,
6,
5,
5,
7,
5,
4,
5,
7,
6,
8,
5,
4,
8,
4,
6,
4,
6,
8,
8,
6,
3,
8,
4,
4]},
[1249, 0]],
['m=128 formula alpha',
{'regs': [6,
4,
4,
5,
4,
8,
4,
5,
8,
6,
6,
8,
6,
4,
7,
8,
6,
4,
7,
5,
6,
6,
4,
5,
8,
5,
9,
4,
8,
8,
4,
9,
7,
4,
9,
9,
9,
4,
6,
9,
5,
7,
4,
9,
8,
5,
7,
4,
5,
6,
8,
4,
7,
5,
7,
6,
9,
7,
6,
7,
9,
8,
6,
4,
4,
7,
4,
6,
6,
6,
4,
6,
9,
9,
5,
9,
8,
6,
9,
9,
6,
6,
7,
4,
8,
4,
4,
4,
4,
7,
5,
8,
9,
8,
8,
9,
4,
8,
7,
8,
8,
9,
9,
4,
7,
4,
8,
5,
7,
9,
5,
5,
5,
5,
7,
8,
4,
6,
7,
7,
6,
8,
8,
8,
8,
5,
5,
8]},
[4107, 0]],
['all registers full', {'regs': [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]}, [43, 0]],
['large range correction',
{'regs': [25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
4,
2,
1,
2,
3,
3,
1,
1,
3,
4,
2,
4,
2,
3,
1,
1,
3,
4,
1,
1,
1,
2,
2,
4,
4,
4,
4,
1,
3]},
[76, 3]],
['dense m=16', {'regs': [4, 7, 5, 7, 3, 6, 6, 3, 3, 3, 4, 6, 4, 6, 7, 5]}, [206, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 2, 1]}, [8, 10]],
['dense m=32',
{'regs': [2,
3,
2,
4,
3,
4,
5,
6,
5,
2,
4,
3,
6,
3,
5,
3,
2,
5,
5,
5,
2,
2,
6,
6,
3,
3,
2,
4,
6,
5,
2,
5]},
[207, 0]],
['dense m=64',
{'regs': [4,
7,
5,
7,
3,
7,
3,
7,
6,
6,
3,
8,
8,
8,
8,
4,
7,
6,
5,
7,
5,
8,
6,
4,
3,
8,
7,
3,
8,
6,
5,
8,
5,
5,
7,
5,
8,
5,
3,
6,
4,
7,
3,
6,
4,
8,
4,
6,
3,
4,
8,
6,
6,
7,
7,
6,
8,
4,
8,
8,
8,
6,
8,
3]},
[1313, 0]],
['m=128 formula alpha',
{'regs': [5,
4,
7,
9,
8,
7,
5,
5,
4,
9,
5,
4,
7,
9,
8,
9,
9,
8,
9,
5,
8,
4,
8,
9,
5,
4,
6,
4,
4,
8,
4,
5,
6,
4,
4,
6,
4,
5,
5,
4,
7,
8,
4,
7,
9,
9,
4,
7,
6,
6,
5,
4,
5,
8,
6,
8,
5,
8,
8,
7,
7,
4,
7,
4,
8,
9,
6,
4,
5,
7,
6,
4,
6,
9,
6,
8,
4,
4,
5,
4,
7,
5,
9,
4,
8,
9,
8,
4,
4,
9,
7,
4,
6,
5,
9,
5,
8,
5,
5,
4,
7,
8,
9,
6,
7,
9,
5,
5,
9,
9,
9,
5,
5,
5,
5,
8,
9,
4,
9,
5,
4,
8,
9,
8,
6,
8,
9,
8]},
[3817, 0]],
['all registers full', {'regs': [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]}, [86, 0]],
['large range correction',
{'regs': [26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
2,
3,
3,
4,
1,
3,
4,
3,
2,
3,
2,
4,
2,
1,
1,
4,
4,
2,
1,
4,
4,
2,
3,
3,
2,
1,
4,
3,
4]},
[81, 3]],
['dense m=16', {'regs': [7, 4, 3, 4, 4, 5, 4, 7, 4, 4, 3, 3, 6, 7, 7, 7]}, [206, 0]],
['all ones no empty register',
{'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[22, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 3, 1]}, [8, 10]],
['dense m=32',
{'regs': [2,
4,
3,
5,
3,
5,
2,
4,
2,
2,
6,
5,
3,
6,
4,
5,
3,
4,
4,
3,
6,
4,
3,
3,
3,
5,
2,
2,
6,
4,
6,
2]},
[209, 0]],
['dense m=64',
{'regs': [6,
3,
4,
7,
3,
8,
7,
8,
6,
4,
8,
6,
7,
7,
5,
6,
5,
8,
4,
4,
6,
3,
3,
6,
8,
6,
4,
8,
8,
5,
4,
6,
6,
5,
3,
8,
6,
4,
7,
7,
6,
7,
6,
4,
6,
5,
7,
8,
8,
6,
7,
4,
6,
4,
6,
3,
6,
7,
8,
5,
7,
5,
6,
8]},
[1446, 0]],
['m=128 formula alpha',
{'regs': [5,
9,
9,
9,
4,
8,
8,
7,
4,
8,
5,
8,
9,
9,
4,
4,
4,
5,
5,
4,
6,
7,
8,
7,
5,
5,
4,
6,
6,
8,
8,
9,
7,
9,
9,
5,
7,
5,
9,
8,
7,
9,
5,
8,
5,
7,
5,
8,
8,
6,
9,
5,
4,
9,
4,
4,
8,
6,
7,
4,
7,
4,
7,
4,
8,
8,
8,
9,
7,
9,
8,
8,
8,
5,
5,
6,
6,
4,
6,
6,
6,
8,
7,
9,
8,
5,
8,
4,
7,
8,
4,
8,
8,
4,
7,
4,
5,
5,
5,
6,
9,
4,
6,
9,
6,
5,
5,
6,
6,
6,
6,
5,
9,
8,
9,
6,
9,
7,
8,
5,
5,
5,
8,
6,
8,
7,
4,
9]},
[4556, 0]],
['all registers full', {'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]}, [22, 0]],
['large range correction',
{'regs': [27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
3,
1,
1,
4,
2,
4,
3,
3,
1,
3,
2,
4,
3,
3,
4,
4,
1,
2,
4,
2,
3,
4,
1,
1,
1,
3,
3,
2,
4]},
[76, 3]],
['dense m=16', {'regs': [4, 6, 4, 7, 7, 6, 4, 7, 3, 4, 3, 7, 6, 7, 7, 6]}, [283, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 4, 1]}, [8, 10]],
['dense m=32',
{'regs': [6,
4,
6,
4,
5,
5,
3,
4,
5,
4,
3,
3,
4,
2,
2,
3,
2,
5,
4,
3,
3,
4,
5,
4,
6,
5,
6,
2,
6,
5,
4,
4]},
[267, 0]],
['dense m=64',
{'regs': [5,
4,
5,
6,
8,
5,
4,
7,
5,
3,
8,
8,
6,
8,
8,
5,
7,
7,
6,
4,
4,
7,
6,
5,
7,
8,
8,
8,
6,
8,
4,
3,
4,
8,
5,
4,
7,
8,
3,
7,
6,
3,
4,
6,
6,
5,
8,
3,
4,
3,
3,
7,
5,
5,
3,
5,
4,
7,
3,
6,
7,
6,
4,
3]},
[1133, 0]],
['m=128 formula alpha',
{'regs': [6,
6,
4,
6,
8,
7,
6,
9,
4,
4,
5,
7,
6,
9,
7,
4,
9,
7,
5,
5,
6,
9,
6,
7,
7,
4,
9,
9,
5,
4,
5,
4,
4,
6,
9,
9,
7,
7,
9,
7,
4,
7,
4,
5,
9,
8,
7,
6,
9,
9,
4,
9,
8,
4,
6,
6,
5,
8,
5,
7,
8,
7,
8,
7,
7,
4,
6,
9,
9,
4,
6,
5,
6,
6,
8,
4,
6,
8,
6,
7,
9,
5,
9,
8,
9,
9,
7,
6,
5,
6,
5,
6,
6,
7,
7,
9,
8,
6,
8,
6,
9,
8,
9,
4,
9,
4,
6,
4,
4,
6,
7,
9,
4,
6,
7,
5,
5,
5,
7,
5,
6,
6,
7,
6,
7,
7,
6,
5]},
[4615, 0]],
['all registers full', {'regs': [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]}, [43, 0]],
['large range correction',
{'regs': [24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
1,
2,
1,
2,
4,
3,
3,
4,
4,
3,
4,
4,
3,
4,
1,
4,
3,
3,
3,
2,
2,
3,
3,
1,
4,
2,
3,
3,
1]},
[83, 3]],
['dense m=16', {'regs': [5, 4, 5, 3, 4, 7, 7, 5, 5, 3, 6, 7, 3, 5, 7, 6]}, [240, 0]],
['all ones no empty register',
{'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[22, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 5, 1]}, [8, 10]],
['dense m=32',
{'regs': [4,
2,
4,
4,
5,
5,
4,
3,
6,
2,
5,
2,
2,
5,
4,
4,
3,
6,
5,
6,
6,
5,
4,
5,
6,
4,
2,
5,
4,
2,
5,
3]},
[255, 0]],
['dense m=64',
{'regs': [7,
7,
7,
4,
7,
6,
3,
3,
6,
4,
4,
8,
8,
7,
8,
4,
8,
8,
8,
6,
4,
5,
5,
8,
8,
5,
4,
4,
4,
7,
6,
5,
8,
7,
3,
5,
3,
8,
3,
4,
3,
8,
5,
3,
4,
3,
8,
3,
7,
5,
7,
3,
7,
8,
6,
6,
4,
3,
6,
3,
7,
3,
5,
7]},
[1031, 0]],
['m=128 formula alpha',
{'regs': [6,
8,
8,
6,
7,
5,
8,
4,
6,
4,
4,
8,
6,
7,
8,
6,
7,
7,
7,
4,
7,
6,
7,
8,
5,
9,
9,
8,
4,
9,
5,
7,
6,
8,
7,
8,
4,
4,
7,
9,
8,
7,
6,
6,
4,
8,
8,
4,
5,
4,
7,
6,
5,
4,
7,
5,
5,
5,
6,
5,
5,
8,
6,
5,
9,
4,
4,
7,
7,
8,
4,
7,
4,
8,
5,
6,
8,
7,
8,
9,
7,
9,
9,
7,
8,
4,
5,
8,
6,
4,
7,
7,
7,
4,
5,
8,
9,
8,
6,
8,
5,
8,
8,
7,
5,
9,
4,
4,
7,
9,
7,
5,
8,
7,
5,
5,
6,
5,
7,
7,
7,
7,
5,
6,
4,
8,
5,
7]},
[4454, 0]],
['all registers full', {'regs': [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]}, [86, 0]],
['large range correction',
{'regs': [25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
3,
1,
2,
1,
2,
1,
1,
2,
1,
4,
2,
2,
3,
2,
3,
1,
2,
2,
4,
3,
3,
2,
3,
3,
2,
4,
2,
3,
2]},
[76, 3]],
['dense m=16', {'regs': [6, 5, 7, 7, 7, 7, 3, 7, 5, 7, 7, 6, 3, 6, 3, 3]}, [259, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]]]
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 |
|---|---|---|---|
| sparse m=16 | [7, 10] | [8, 10] | Failed |
| dense m=32 | [246, 0] | [247, 0] | Failed |
| dense m=64 | [1249, 0] | [1249, 0] | Passed |
| m=128 formula alpha | [4106, 0] | [4107, 0] | Failed |
| all registers full | [43, 0] | [43, 0] | Passed |
| large range correction | [403802869, 0] | [403802870, 0] | Failed |
| mixed m=32 with zeros | [75, 3] | [76, 3] | Failed |
| dense m=16 | [206, 0] | [206, 0] | Passed |
| all ones no empty register | [44, 0] | [45, 0] | Failed |
| exactly one empty register | [44, 1] | [44, 1] | Passed |
SHA-256 / ff18477738ddf4128fd74e5d0282611545773fe1283389cad959e40b5ce55d51
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
regs = x['regs']
m = len(regs)
if m == 16:
alpha = 0.673
elif m == 32:
alpha = 0.697
elif m == 64:
alpha = 0.709
else:
alpha = 0.7213 / (1 + 1.079 / m)
E = alpha * m * m / sum(2.0 ** -r for r in regs)
V = regs.count(0)
if E <= 2.5 * m and V > 0:
E = m * math.log(m / V)
elif E > (2 ** 32) / 30:
E = -(2 ** 32) * math.log(1 - E / 2 ** 32)
return [math.ceil(E), V]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 1, 1]}, [8, 10]],
['dense m=32',
{'regs': [4,
5,
2,
2,
6,
6,
3,
6,
3,
5,
6,
6,
2,
4,
3,
6,
2,
3,
6,
5,
2,
4,
5,
4,
4,
4,
4,
2,
4,
3,
6,
6]},
[247, 0]],
['dense m=64',
{'regs': [7,
3,
7,
8,
6,
6,
4,
6,
7,
4,
6,
4,
3,
3,
8,
8,
3,
8,
8,
8,
8,
8,
5,
4,
8,
7,
6,
6,
8,
3,
3,
8,
8,
8,
8,
6,
3,
6,
4,
3,
6,
5,
5,
7,
5,
4,
5,
7,
6,
8,
5,
4,
8,
4,
6,
4,
6,
8,
8,
6,
3,
8,
4,
4]},
[1249, 0]],
['m=128 formula alpha',
{'regs': [6,
4,
4,
5,
4,
8,
4,
5,
8,
6,
6,
8,
6,
4,
7,
8,
6,
4,
7,
5,
6,
6,
4,
5,
8,
5,
9,
4,
8,
8,
4,
9,
7,
4,
9,
9,
9,
4,
6,
9,
5,
7,
4,
9,
8,
5,
7,
4,
5,
6,
8,
4,
7,
5,
7,
6,
9,
7,
6,
7,
9,
8,
6,
4,
4,
7,
4,
6,
6,
6,
4,
6,
9,
9,
5,
9,
8,
6,
9,
9,
6,
6,
7,
4,
8,
4,
4,
4,
4,
7,
5,
8,
9,
8,
8,
9,
4,
8,
7,
8,
8,
9,
9,
4,
7,
4,
8,
5,
7,
9,
5,
5,
5,
5,
7,
8,
4,
6,
7,
7,
6,
8,
8,
8,
8,
5,
5,
8]},
[4107, 0]],
['all registers full', {'regs': [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]}, [43, 0]],
['large range correction',
{'regs': [25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
4,
2,
1,
2,
3,
3,
1,
1,
3,
4,
2,
4,
2,
3,
1,
1,
3,
4,
1,
1,
1,
2,
2,
4,
4,
4,
4,
1,
3]},
[76, 3]],
['dense m=16', {'regs': [4, 7, 5, 7, 3, 6, 6, 3, 3, 3, 4, 6, 4, 6, 7, 5]}, [206, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 2, 1]}, [8, 10]],
['dense m=32',
{'regs': [2,
3,
2,
4,
3,
4,
5,
6,
5,
2,
4,
3,
6,
3,
5,
3,
2,
5,
5,
5,
2,
2,
6,
6,
3,
3,
2,
4,
6,
5,
2,
5]},
[207, 0]],
['dense m=64',
{'regs': [4,
7,
5,
7,
3,
7,
3,
7,
6,
6,
3,
8,
8,
8,
8,
4,
7,
6,
5,
7,
5,
8,
6,
4,
3,
8,
7,
3,
8,
6,
5,
8,
5,
5,
7,
5,
8,
5,
3,
6,
4,
7,
3,
6,
4,
8,
4,
6,
3,
4,
8,
6,
6,
7,
7,
6,
8,
4,
8,
8,
8,
6,
8,
3]},
[1313, 0]],
['m=128 formula alpha',
{'regs': [5,
4,
7,
9,
8,
7,
5,
5,
4,
9,
5,
4,
7,
9,
8,
9,
9,
8,
9,
5,
8,
4,
8,
9,
5,
4,
6,
4,
4,
8,
4,
5,
6,
4,
4,
6,
4,
5,
5,
4,
7,
8,
4,
7,
9,
9,
4,
7,
6,
6,
5,
4,
5,
8,
6,
8,
5,
8,
8,
7,
7,
4,
7,
4,
8,
9,
6,
4,
5,
7,
6,
4,
6,
9,
6,
8,
4,
4,
5,
4,
7,
5,
9,
4,
8,
9,
8,
4,
4,
9,
7,
4,
6,
5,
9,
5,
8,
5,
5,
4,
7,
8,
9,
6,
7,
9,
5,
5,
9,
9,
9,
5,
5,
5,
5,
8,
9,
4,
9,
5,
4,
8,
9,
8,
6,
8,
9,
8]},
[3817, 0]],
['all registers full', {'regs': [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]}, [86, 0]],
['large range correction',
{'regs': [26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
2,
3,
3,
4,
1,
3,
4,
3,
2,
3,
2,
4,
2,
1,
1,
4,
4,
2,
1,
4,
4,
2,
3,
3,
2,
1,
4,
3,
4]},
[81, 3]],
['dense m=16', {'regs': [7, 4, 3, 4, 4, 5, 4, 7, 4, 4, 3, 3, 6, 7, 7, 7]}, [206, 0]],
['all ones no empty register',
{'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[22, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 3, 1]}, [8, 10]],
['dense m=32',
{'regs': [2,
4,
3,
5,
3,
5,
2,
4,
2,
2,
6,
5,
3,
6,
4,
5,
3,
4,
4,
3,
6,
4,
3,
3,
3,
5,
2,
2,
6,
4,
6,
2]},
[209, 0]],
['dense m=64',
{'regs': [6,
3,
4,
7,
3,
8,
7,
8,
6,
4,
8,
6,
7,
7,
5,
6,
5,
8,
4,
4,
6,
3,
3,
6,
8,
6,
4,
8,
8,
5,
4,
6,
6,
5,
3,
8,
6,
4,
7,
7,
6,
7,
6,
4,
6,
5,
7,
8,
8,
6,
7,
4,
6,
4,
6,
3,
6,
7,
8,
5,
7,
5,
6,
8]},
[1446, 0]],
['m=128 formula alpha',
{'regs': [5,
9,
9,
9,
4,
8,
8,
7,
4,
8,
5,
8,
9,
9,
4,
4,
4,
5,
5,
4,
6,
7,
8,
7,
5,
5,
4,
6,
6,
8,
8,
9,
7,
9,
9,
5,
7,
5,
9,
8,
7,
9,
5,
8,
5,
7,
5,
8,
8,
6,
9,
5,
4,
9,
4,
4,
8,
6,
7,
4,
7,
4,
7,
4,
8,
8,
8,
9,
7,
9,
8,
8,
8,
5,
5,
6,
6,
4,
6,
6,
6,
8,
7,
9,
8,
5,
8,
4,
7,
8,
4,
8,
8,
4,
7,
4,
5,
5,
5,
6,
9,
4,
6,
9,
6,
5,
5,
6,
6,
6,
6,
5,
9,
8,
9,
6,
9,
7,
8,
5,
5,
5,
8,
6,
8,
7,
4,
9]},
[4556, 0]],
['all registers full', {'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]}, [22, 0]],
['large range correction',
{'regs': [27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
3,
1,
1,
4,
2,
4,
3,
3,
1,
3,
2,
4,
3,
3,
4,
4,
1,
2,
4,
2,
3,
4,
1,
1,
1,
3,
3,
2,
4]},
[76, 3]],
['dense m=16', {'regs': [4, 6, 4, 7, 7, 6, 4, 7, 3, 4, 3, 7, 6, 7, 7, 6]}, [283, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 4, 1]}, [8, 10]],
['dense m=32',
{'regs': [6,
4,
6,
4,
5,
5,
3,
4,
5,
4,
3,
3,
4,
2,
2,
3,
2,
5,
4,
3,
3,
4,
5,
4,
6,
5,
6,
2,
6,
5,
4,
4]},
[267, 0]],
['dense m=64',
{'regs': [5,
4,
5,
6,
8,
5,
4,
7,
5,
3,
8,
8,
6,
8,
8,
5,
7,
7,
6,
4,
4,
7,
6,
5,
7,
8,
8,
8,
6,
8,
4,
3,
4,
8,
5,
4,
7,
8,
3,
7,
6,
3,
4,
6,
6,
5,
8,
3,
4,
3,
3,
7,
5,
5,
3,
5,
4,
7,
3,
6,
7,
6,
4,
3]},
[1133, 0]],
['m=128 formula alpha',
{'regs': [6,
6,
4,
6,
8,
7,
6,
9,
4,
4,
5,
7,
6,
9,
7,
4,
9,
7,
5,
5,
6,
9,
6,
7,
7,
4,
9,
9,
5,
4,
5,
4,
4,
6,
9,
9,
7,
7,
9,
7,
4,
7,
4,
5,
9,
8,
7,
6,
9,
9,
4,
9,
8,
4,
6,
6,
5,
8,
5,
7,
8,
7,
8,
7,
7,
4,
6,
9,
9,
4,
6,
5,
6,
6,
8,
4,
6,
8,
6,
7,
9,
5,
9,
8,
9,
9,
7,
6,
5,
6,
5,
6,
6,
7,
7,
9,
8,
6,
8,
6,
9,
8,
9,
4,
9,
4,
6,
4,
4,
6,
7,
9,
4,
6,
7,
5,
5,
5,
7,
5,
6,
6,
7,
6,
7,
7,
6,
5]},
[4615, 0]],
['all registers full', {'regs': [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]}, [43, 0]],
['large range correction',
{'regs': [24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
1,
2,
1,
2,
4,
3,
3,
4,
4,
3,
4,
4,
3,
4,
1,
4,
3,
3,
3,
2,
2,
3,
3,
1,
4,
2,
3,
3,
1]},
[83, 3]],
['dense m=16', {'regs': [5, 4, 5, 3, 4, 7, 7, 5, 5, 3, 6, 7, 3, 5, 7, 6]}, [240, 0]],
['all ones no empty register',
{'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[22, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 5, 1]}, [8, 10]],
['dense m=32',
{'regs': [4,
2,
4,
4,
5,
5,
4,
3,
6,
2,
5,
2,
2,
5,
4,
4,
3,
6,
5,
6,
6,
5,
4,
5,
6,
4,
2,
5,
4,
2,
5,
3]},
[255, 0]],
['dense m=64',
{'regs': [7,
7,
7,
4,
7,
6,
3,
3,
6,
4,
4,
8,
8,
7,
8,
4,
8,
8,
8,
6,
4,
5,
5,
8,
8,
5,
4,
4,
4,
7,
6,
5,
8,
7,
3,
5,
3,
8,
3,
4,
3,
8,
5,
3,
4,
3,
8,
3,
7,
5,
7,
3,
7,
8,
6,
6,
4,
3,
6,
3,
7,
3,
5,
7]},
[1031, 0]],
['m=128 formula alpha',
{'regs': [6,
8,
8,
6,
7,
5,
8,
4,
6,
4,
4,
8,
6,
7,
8,
6,
7,
7,
7,
4,
7,
6,
7,
8,
5,
9,
9,
8,
4,
9,
5,
7,
6,
8,
7,
8,
4,
4,
7,
9,
8,
7,
6,
6,
4,
8,
8,
4,
5,
4,
7,
6,
5,
4,
7,
5,
5,
5,
6,
5,
5,
8,
6,
5,
9,
4,
4,
7,
7,
8,
4,
7,
4,
8,
5,
6,
8,
7,
8,
9,
7,
9,
9,
7,
8,
4,
5,
8,
6,
4,
7,
7,
7,
4,
5,
8,
9,
8,
6,
8,
5,
8,
8,
7,
5,
9,
4,
4,
7,
9,
7,
5,
8,
7,
5,
5,
6,
5,
7,
7,
7,
7,
5,
6,
4,
8,
5,
7]},
[4454, 0]],
['all registers full', {'regs': [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]}, [86, 0]],
['large range correction',
{'regs': [25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
3,
1,
2,
1,
2,
1,
1,
2,
1,
4,
2,
2,
3,
2,
3,
1,
2,
2,
4,
3,
3,
2,
3,
3,
2,
4,
2,
3,
2]},
[76, 3]],
['dense m=16', {'regs': [6, 5, 7, 7, 7, 7, 3, 7, 5, 7, 7, 6, 3, 6, 3, 3]}, [259, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]]]
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 |
|---|---|---|---|
| sparse m=16 | [8, 10] | [8, 10] | Passed |
| dense m=32 | [247, 0] | [247, 0] | Passed |
| dense m=64 | [1250, 0] | [1249, 0] | Failed |
| m=128 formula alpha | [4107, 0] | [4107, 0] | Passed |
| all registers full | [44, 0] | [43, 0] | Failed |
| large range correction | [403802870, 0] | [403802870, 0] | Passed |
| mixed m=32 with zeros | [76, 3] | [76, 3] | Passed |
| dense m=16 | [207, 0] | [206, 0] | Failed |
| all ones no empty register | [45, 0] | [45, 0] | Passed |
| exactly one empty register | [45, 1] | [44, 1] | Failed |
SHA-256 / 7f73ef107c19a4444d32d856d202531648eada98f45dd9e3535bfff85fc341e8
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
regs = x['regs']
m = len(regs)
if m == 16:
alpha = 0.673
elif m == 32:
alpha = 0.697
elif m == 64:
alpha = 0.709
else:
alpha = 0.7213 / (1 + 1.079 / m)
E = alpha * m * m / sum(2.0 ** -r for r in regs)
V = regs.count(0)
if E <= 2.5 * m and V > 0:
E = m * math.log(m / V)
elif E > (2 ** 32) / 30:
E = -(2 ** 32) * math.log(1 - E / 2 ** 32)
return [round(E), V]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 1, 1]}, [8, 10]],
['dense m=32',
{'regs': [4,
5,
2,
2,
6,
6,
3,
6,
3,
5,
6,
6,
2,
4,
3,
6,
2,
3,
6,
5,
2,
4,
5,
4,
4,
4,
4,
2,
4,
3,
6,
6]},
[247, 0]],
['dense m=64',
{'regs': [7,
3,
7,
8,
6,
6,
4,
6,
7,
4,
6,
4,
3,
3,
8,
8,
3,
8,
8,
8,
8,
8,
5,
4,
8,
7,
6,
6,
8,
3,
3,
8,
8,
8,
8,
6,
3,
6,
4,
3,
6,
5,
5,
7,
5,
4,
5,
7,
6,
8,
5,
4,
8,
4,
6,
4,
6,
8,
8,
6,
3,
8,
4,
4]},
[1249, 0]],
['m=128 formula alpha',
{'regs': [6,
4,
4,
5,
4,
8,
4,
5,
8,
6,
6,
8,
6,
4,
7,
8,
6,
4,
7,
5,
6,
6,
4,
5,
8,
5,
9,
4,
8,
8,
4,
9,
7,
4,
9,
9,
9,
4,
6,
9,
5,
7,
4,
9,
8,
5,
7,
4,
5,
6,
8,
4,
7,
5,
7,
6,
9,
7,
6,
7,
9,
8,
6,
4,
4,
7,
4,
6,
6,
6,
4,
6,
9,
9,
5,
9,
8,
6,
9,
9,
6,
6,
7,
4,
8,
4,
4,
4,
4,
7,
5,
8,
9,
8,
8,
9,
4,
8,
7,
8,
8,
9,
9,
4,
7,
4,
8,
5,
7,
9,
5,
5,
5,
5,
7,
8,
4,
6,
7,
7,
6,
8,
8,
8,
8,
5,
5,
8]},
[4107, 0]],
['all registers full', {'regs': [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]}, [43, 0]],
['large range correction',
{'regs': [25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
4,
2,
1,
2,
3,
3,
1,
1,
3,
4,
2,
4,
2,
3,
1,
1,
3,
4,
1,
1,
1,
2,
2,
4,
4,
4,
4,
1,
3]},
[76, 3]],
['dense m=16', {'regs': [4, 7, 5, 7, 3, 6, 6, 3, 3, 3, 4, 6, 4, 6, 7, 5]}, [206, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 2, 1]}, [8, 10]],
['dense m=32',
{'regs': [2,
3,
2,
4,
3,
4,
5,
6,
5,
2,
4,
3,
6,
3,
5,
3,
2,
5,
5,
5,
2,
2,
6,
6,
3,
3,
2,
4,
6,
5,
2,
5]},
[207, 0]],
['dense m=64',
{'regs': [4,
7,
5,
7,
3,
7,
3,
7,
6,
6,
3,
8,
8,
8,
8,
4,
7,
6,
5,
7,
5,
8,
6,
4,
3,
8,
7,
3,
8,
6,
5,
8,
5,
5,
7,
5,
8,
5,
3,
6,
4,
7,
3,
6,
4,
8,
4,
6,
3,
4,
8,
6,
6,
7,
7,
6,
8,
4,
8,
8,
8,
6,
8,
3]},
[1313, 0]],
['m=128 formula alpha',
{'regs': [5,
4,
7,
9,
8,
7,
5,
5,
4,
9,
5,
4,
7,
9,
8,
9,
9,
8,
9,
5,
8,
4,
8,
9,
5,
4,
6,
4,
4,
8,
4,
5,
6,
4,
4,
6,
4,
5,
5,
4,
7,
8,
4,
7,
9,
9,
4,
7,
6,
6,
5,
4,
5,
8,
6,
8,
5,
8,
8,
7,
7,
4,
7,
4,
8,
9,
6,
4,
5,
7,
6,
4,
6,
9,
6,
8,
4,
4,
5,
4,
7,
5,
9,
4,
8,
9,
8,
4,
4,
9,
7,
4,
6,
5,
9,
5,
8,
5,
5,
4,
7,
8,
9,
6,
7,
9,
5,
5,
9,
9,
9,
5,
5,
5,
5,
8,
9,
4,
9,
5,
4,
8,
9,
8,
6,
8,
9,
8]},
[3817, 0]],
['all registers full', {'regs': [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]}, [86, 0]],
['large range correction',
{'regs': [26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
2,
3,
3,
4,
1,
3,
4,
3,
2,
3,
2,
4,
2,
1,
1,
4,
4,
2,
1,
4,
4,
2,
3,
3,
2,
1,
4,
3,
4]},
[81, 3]],
['dense m=16', {'regs': [7, 4, 3, 4, 4, 5, 4, 7, 4, 4, 3, 3, 6, 7, 7, 7]}, [206, 0]],
['all ones no empty register',
{'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[22, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 3, 1]}, [8, 10]],
['dense m=32',
{'regs': [2,
4,
3,
5,
3,
5,
2,
4,
2,
2,
6,
5,
3,
6,
4,
5,
3,
4,
4,
3,
6,
4,
3,
3,
3,
5,
2,
2,
6,
4,
6,
2]},
[209, 0]],
['dense m=64',
{'regs': [6,
3,
4,
7,
3,
8,
7,
8,
6,
4,
8,
6,
7,
7,
5,
6,
5,
8,
4,
4,
6,
3,
3,
6,
8,
6,
4,
8,
8,
5,
4,
6,
6,
5,
3,
8,
6,
4,
7,
7,
6,
7,
6,
4,
6,
5,
7,
8,
8,
6,
7,
4,
6,
4,
6,
3,
6,
7,
8,
5,
7,
5,
6,
8]},
[1446, 0]],
['m=128 formula alpha',
{'regs': [5,
9,
9,
9,
4,
8,
8,
7,
4,
8,
5,
8,
9,
9,
4,
4,
4,
5,
5,
4,
6,
7,
8,
7,
5,
5,
4,
6,
6,
8,
8,
9,
7,
9,
9,
5,
7,
5,
9,
8,
7,
9,
5,
8,
5,
7,
5,
8,
8,
6,
9,
5,
4,
9,
4,
4,
8,
6,
7,
4,
7,
4,
7,
4,
8,
8,
8,
9,
7,
9,
8,
8,
8,
5,
5,
6,
6,
4,
6,
6,
6,
8,
7,
9,
8,
5,
8,
4,
7,
8,
4,
8,
8,
4,
7,
4,
5,
5,
5,
6,
9,
4,
6,
9,
6,
5,
5,
6,
6,
6,
6,
5,
9,
8,
9,
6,
9,
7,
8,
5,
5,
5,
8,
6,
8,
7,
4,
9]},
[4556, 0]],
['all registers full', {'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]}, [22, 0]],
['large range correction',
{'regs': [27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
3,
1,
1,
4,
2,
4,
3,
3,
1,
3,
2,
4,
3,
3,
4,
4,
1,
2,
4,
2,
3,
4,
1,
1,
1,
3,
3,
2,
4]},
[76, 3]],
['dense m=16', {'regs': [4, 6, 4, 7, 7, 6, 4, 7, 3, 4, 3, 7, 6, 7, 7, 6]}, [283, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 4, 1]}, [8, 10]],
['dense m=32',
{'regs': [6,
4,
6,
4,
5,
5,
3,
4,
5,
4,
3,
3,
4,
2,
2,
3,
2,
5,
4,
3,
3,
4,
5,
4,
6,
5,
6,
2,
6,
5,
4,
4]},
[267, 0]],
['dense m=64',
{'regs': [5,
4,
5,
6,
8,
5,
4,
7,
5,
3,
8,
8,
6,
8,
8,
5,
7,
7,
6,
4,
4,
7,
6,
5,
7,
8,
8,
8,
6,
8,
4,
3,
4,
8,
5,
4,
7,
8,
3,
7,
6,
3,
4,
6,
6,
5,
8,
3,
4,
3,
3,
7,
5,
5,
3,
5,
4,
7,
3,
6,
7,
6,
4,
3]},
[1133, 0]],
['m=128 formula alpha',
{'regs': [6,
6,
4,
6,
8,
7,
6,
9,
4,
4,
5,
7,
6,
9,
7,
4,
9,
7,
5,
5,
6,
9,
6,
7,
7,
4,
9,
9,
5,
4,
5,
4,
4,
6,
9,
9,
7,
7,
9,
7,
4,
7,
4,
5,
9,
8,
7,
6,
9,
9,
4,
9,
8,
4,
6,
6,
5,
8,
5,
7,
8,
7,
8,
7,
7,
4,
6,
9,
9,
4,
6,
5,
6,
6,
8,
4,
6,
8,
6,
7,
9,
5,
9,
8,
9,
9,
7,
6,
5,
6,
5,
6,
6,
7,
7,
9,
8,
6,
8,
6,
9,
8,
9,
4,
9,
4,
6,
4,
4,
6,
7,
9,
4,
6,
7,
5,
5,
5,
7,
5,
6,
6,
7,
6,
7,
7,
6,
5]},
[4615, 0]],
['all registers full', {'regs': [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]}, [43, 0]],
['large range correction',
{'regs': [24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
1,
2,
1,
2,
4,
3,
3,
4,
4,
3,
4,
4,
3,
4,
1,
4,
3,
3,
3,
2,
2,
3,
3,
1,
4,
2,
3,
3,
1]},
[83, 3]],
['dense m=16', {'regs': [5, 4, 5, 3, 4, 7, 7, 5, 5, 3, 6, 7, 3, 5, 7, 6]}, [240, 0]],
['all ones no empty register',
{'regs': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[22, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]],
[['sparse m=16', {'regs': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 3, 5, 1]}, [8, 10]],
['dense m=32',
{'regs': [4,
2,
4,
4,
5,
5,
4,
3,
6,
2,
5,
2,
2,
5,
4,
4,
3,
6,
5,
6,
6,
5,
4,
5,
6,
4,
2,
5,
4,
2,
5,
3]},
[255, 0]],
['dense m=64',
{'regs': [7,
7,
7,
4,
7,
6,
3,
3,
6,
4,
4,
8,
8,
7,
8,
4,
8,
8,
8,
6,
4,
5,
5,
8,
8,
5,
4,
4,
4,
7,
6,
5,
8,
7,
3,
5,
3,
8,
3,
4,
3,
8,
5,
3,
4,
3,
8,
3,
7,
5,
7,
3,
7,
8,
6,
6,
4,
3,
6,
3,
7,
3,
5,
7]},
[1031, 0]],
['m=128 formula alpha',
{'regs': [6,
8,
8,
6,
7,
5,
8,
4,
6,
4,
4,
8,
6,
7,
8,
6,
7,
7,
7,
4,
7,
6,
7,
8,
5,
9,
9,
8,
4,
9,
5,
7,
6,
8,
7,
8,
4,
4,
7,
9,
8,
7,
6,
6,
4,
8,
8,
4,
5,
4,
7,
6,
5,
4,
7,
5,
5,
5,
6,
5,
5,
8,
6,
5,
9,
4,
4,
7,
7,
8,
4,
7,
4,
8,
5,
6,
8,
7,
8,
9,
7,
9,
9,
7,
8,
4,
5,
8,
6,
4,
7,
7,
7,
4,
5,
8,
9,
8,
6,
8,
5,
8,
8,
7,
5,
9,
4,
4,
7,
9,
7,
5,
8,
7,
5,
5,
6,
5,
7,
7,
7,
7,
5,
6,
4,
8,
5,
7]},
[4454, 0]],
['all registers full', {'regs': [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]}, [86, 0]],
['large range correction',
{'regs': [25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24, 25, 26, 27, 24]},
[403802870, 0]],
['mixed m=32 with zeros',
{'regs': [0,
0,
0,
3,
1,
2,
1,
2,
1,
1,
2,
1,
4,
2,
2,
3,
2,
3,
1,
2,
2,
4,
3,
3,
2,
3,
3,
2,
4,
2,
3,
2]},
[76, 3]],
['dense m=16', {'regs': [6, 5, 7, 7, 7, 7, 3, 7, 5, 7, 7, 6, 3, 6, 3, 3]}, [259, 0]],
['all ones no empty register',
{'regs': [1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1]},
[45, 0]],
['exactly one empty register',
{'regs': [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]},
[44, 1]]]]
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 |
|---|---|---|---|
| sparse m=16 | [8, 10] | [8, 10] | Passed |
| dense m=32 | [247, 0] | [247, 0] | Passed |
| dense m=64 | [1249, 0] | [1249, 0] | Passed |
| m=128 formula alpha | [4107, 0] | [4107, 0] | Passed |
| all registers full | [43, 0] | [43, 0] | Passed |
| large range correction | [403802870, 0] | [403802870, 0] | Passed |
| mixed m=32 with zeros | [76, 3] | [76, 3] | Passed |
| dense m=16 | [206, 0] | [206, 0] | Passed |
| all ones no empty register | [45, 0] | [45, 0] | Passed |
| exactly one empty register | [44, 1] | [44, 1] | Passed |
SHA-256 / dc6614b47c66fa516cdb22459d4b116690e8d5c136ab5631efb91f87c6900c38
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:43.510421+00:00.
Case digest / f2504dfac88e1c594d695f1edc9e1e159a75f55da38bd6375fa7cae7fab0bd28