FA-72996 / Probabilistic sketches / Open access
HyperLogLog cardinality estimate: linear counting uses non-empty registers · case 01
Small cardinalities are estimated from the wrong register population.
ROOT CAUSE
Linear counting divides by the number of non-empty registers instead of empty ones.
VERIFIED REPAIR
Apply m ln(m / V) with V the number of zero registers.
Unsuccessful approach: Scaling by V instead of m shrinks the small-range 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 / (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 | [16, 10] | [8, 10] | Failed |
| 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 | [3, 3] | [76, 3] | Failed |
| dense m=16 | [206, 0] | [206, 0] | Passed |
| all ones no empty register | [45, 0] | [45, 0] | Passed |
| exactly one empty register | [1, 1] | [44, 1] | Failed |
SHA-256 / 8869bfd31bbe977791f6cdfd7b89f12c1eed3a0fc09712e9c22f27e3ad3ead9d
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 = V * 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 | [5, 10] | [8, 10] | Failed |
| 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 | [7, 3] | [76, 3] | Failed |
| dense m=16 | [206, 0] | [206, 0] | Passed |
| all ones no empty register | [45, 0] | [45, 0] | Passed |
| exactly one empty register | [3, 1] | [44, 1] | Failed |
SHA-256 / 2ce12f696110ad3200989c64f7579c5fa5b43bbf0fe43c8975fd9802e08aa567
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.465317+00:00.
Case digest / 07070e4c01d214e270a445d051b29b2dc763fa6460a6cc6eb2bec2a2e013a1bb