FA-73021 / Probabilistic sketches / Open access
HyperLogLog merge across precisions: fold index uses the low bits · case 01
Registers are merged into slots that the lower-precision sketch would never have chosen.
ROOT CAUSE
The folded index keeps the low q bits of j instead of its top q bits.
VERIFIED REPAIR
Keep the top q bits: j >> d.
Unsuccessful approach: Shifting by q instead of d selects the wrong bits whenever p is not 2q.
Case contract
Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].
Why this case matters
Merging distinct-count sketches produced with different precision settings requires re-deriving ranks, not just re-indexing registers.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
def fold(sk, q):
d = sk['p'] - q
out = [0] * (1 << q)
for j, r in enumerate(sk['regs']):
if r == 0:
continue
nj = j & ((1 << q) - 1)
low = j & ((1 << d) - 1)
if low != 0:
nr = d - low.bit_length() + 1
else:
nr = r + d
out[nj] = max(out[nj], nr)
return out
q = min(x['a']['p'], x['b']['p'])
fa = fold(x['a'], q)
fb = fold(x['b'], q)
return [q, [max(u, v) for u, v in zip(fa, fb)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fold p5 into p3',
{'a': {'p': 5,
'regs': [3,
2,
4,
3,
0,
4,
5,
1,
1,
1,
0,
0,
0,
5,
3,
0,
4,
2,
5,
3,
0,
3,
0,
0,
3,
0,
0,
5,
4,
3,
1,
0]},
'b': {'p': 3, 'regs': [2, 1, 0, 4, 3, 0, 1, 3]}},
[3, [5, 2, 3, 4, 6, 2, 5, 6]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 3, 0, 2]},
'b': {'p': 4, 'regs': [5, 0, 5, 3, 3, 2, 2, 2, 4, 4, 0, 3, 4, 0, 4, 4]}},
[2, [7, 5, 6, 6]]],
['same precision',
{'a': {'p': 3, 'regs': [0, 0, 4, 0, 1, 5, 0, 0]},
'b': {'p': 3, 'regs': [0, 2, 1, 4, 0, 0, 0, 0]}},
[3, [0, 2, 4, 4, 1, 5, 0, 0]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [4, 4, 4, 4]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 1]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 5, 0, 0, 0, 0, 4, 2]},
'b': {'p': 6,
'regs': [0,
5,
0,
0,
0,
0,
0,
0,
3,
2,
0,
0,
0,
0,
0,
0,
0,
3,
0,
0,
5,
0,
0,
1,
0,
0,
4,
0,
4,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4,
0,
3,
0,
0,
0,
0,
0,
5,
0,
0,
0,
0,
3,
0,
0,
0,
0,
0,
0,
2,
1,
3,
0,
0,
0]}},
[3, [3, 6, 3, 2, 1, 6, 4, 2]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
0,
1,
2,
0,
2,
0,
3,
0,
4,
5,
0,
3,
0,
0,
3,
3,
1,
2,
0,
5,
0,
3,
0,
4,
1,
0,
1,
1,
4,
3,
4]},
'b': {'p': 3, 'regs': [3, 0, 3, 3, 0, 1, 1, 2]}},
[3, [3, 2, 3, 5, 5, 7, 6, 3]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 0, 0, 0]},
'b': {'p': 4, 'regs': [1, 2, 5, 0, 1, 0, 2, 0, 3, 2, 4, 1, 4, 0, 3, 1]}},
[2, [3, 3, 5, 6]]],
['same precision',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 1, 2, 5, 4]},
'b': {'p': 3, 'regs': [2, 1, 0, 0, 0, 0, 0, 0]}},
[3, [2, 1, 0, 0, 1, 2, 5, 4]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [5, 5, 5, 5]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 2]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 0, 2, 4, 5, 0, 5, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
2,
5,
0,
0,
0,
0,
0,
1,
0,
0,
1,
4,
2,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
4,
0,
1,
0,
0,
0,
2,
0,
0,
0,
4,
3,
0,
0,
2,
5,
0,
0,
0]}},
[3, [1, 0, 3, 4, 5, 4, 5, 6]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [1,
2,
2,
1,
3,
3,
3,
0,
1,
0,
4,
5,
0,
0,
0,
0,
0,
2,
4,
0,
2,
4,
0,
4,
0,
3,
1,
2,
5,
5,
0,
0]},
'b': {'p': 3, 'regs': [4, 0, 0, 1, 4, 4, 0, 0]}},
[3, [4, 5, 3, 1, 4, 4, 2, 7]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 2, 0, 0]},
'b': {'p': 4, 'regs': [2, 5, 1, 1, 1, 2, 4, 5, 1, 3, 3, 3, 0, 3, 1, 3]}},
[2, [4, 3, 3, 2]]],
['same precision',
{'a': {'p': 3, 'regs': [5, 0, 0, 4, 0, 0, 2, 5]},
'b': {'p': 3, 'regs': [3, 0, 1, 1, 5, 3, 1, 0]}},
[3, [5, 0, 1, 4, 5, 3, 2, 5]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [6, 6, 6, 6]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [1, 0, 0, 3, 0, 0, 0, 5]},
'b': {'p': 6,
'regs': [0,
2,
2,
0,
0,
0,
0,
0,
0,
5,
0,
0,
0,
5,
3,
0,
3,
4,
0,
4,
0,
4,
0,
0,
0,
0,
1,
0,
0,
0,
0,
4,
0,
0,
0,
0,
3,
0,
3,
0,
0,
0,
0,
0,
0,
1,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
4,
0,
0,
5,
0,
0,
0,
0]}},
[3, [3, 3, 6, 3, 1, 1, 5, 7]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
0,
4,
0,
0,
0,
0,
5,
1,
4,
4,
0,
2,
3,
5,
1,
0,
0,
1,
1,
5,
3,
0,
0,
0,
5,
4,
3,
4,
5,
3,
2]},
'b': {'p': 3, 'regs': [5, 3, 1, 2, 0, 3, 3, 3]}},
[3, [5, 3, 3, 4, 1, 7, 3, 6]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 0, 0, 0]},
'b': {'p': 4, 'regs': [1, 0, 3, 0, 4, 4, 2, 1, 4, 4, 2, 0, 0, 1, 2, 1]}},
[2, [3, 6, 6, 2]]],
['same precision',
{'a': {'p': 3, 'regs': [3, 3, 2, 1, 5, 3, 0, 0]},
'b': {'p': 3, 'regs': [0, 1, 0, 0, 0, 2, 2, 5]}},
[3, [3, 3, 2, 1, 5, 3, 2, 5]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [3, 3, 3, 3]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 1]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [4, 2, 0, 0, 4, 0, 2, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
2,
0,
0,
5,
0,
0,
5,
0,
4,
2,
0,
0,
1,
0,
0,
0,
2,
1,
0,
0,
0,
0,
5,
0,
0,
0,
5,
3,
4,
5,
0,
5,
0,
0,
0,
0,
0,
3,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
0,
5,
0,
1,
0,
0,
0,
0,
0,
0]}},
[3, [4, 3, 2, 3, 8, 6, 2, 3]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
5,
1,
2,
0,
5,
0,
1,
1,
0,
5,
1,
0,
1,
0,
2,
3,
1,
0,
3,
4,
0,
0,
5,
0,
5,
1,
0,
0,
0,
0,
0]},
'b': {'p': 3, 'regs': [5, 1, 1, 4, 2, 3, 5, 0]}},
[3, [5, 2, 3, 4, 5, 6, 5, 0]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 3, 3, 0]},
'b': {'p': 4, 'regs': [1, 3, 2, 0, 0, 5, 2, 2, 3, 2, 4, 2, 3, 3, 1, 3]}},
[2, [3, 3, 5, 5]]],
['same precision',
{'a': {'p': 3, 'regs': [4, 0, 0, 3, 0, 4, 1, 1]},
'b': {'p': 3, 'regs': [0, 0, 0, 0, 3, 0, 4, 0]}},
[3, [4, 0, 0, 3, 3, 4, 4, 1]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [4, 4, 4, 4]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 2]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 0, 4, 4, 0, 5, 3, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
0,
2,
0,
0,
0,
1,
0,
0,
3,
0,
0,
0,
0,
0,
0,
0,
2,
0,
5,
0,
0,
4,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
4,
0,
0,
0,
5,
0,
0,
0,
0,
0,
0,
0,
0,
3,
1,
3,
1,
5,
0,
0,
0,
0,
2,
0,
3,
0,
0,
4]}},
[3, [1, 4, 4, 7, 3, 8, 3, 2]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| fold p5 into p3 | [3, [6, 2, 1, 4, 6, 2, 1, 3]] | [3, [5, 2, 3, 4, 6, 2, 5, 6]] | Failed |
| fold p4 into p2 | [2, [7, 3, 1, 2]] | [2, [7, 5, 6, 6]] | Failed |
| same precision | [3, [0, 2, 4, 4, 1, 5, 0, 0]] | [3, [0, 2, 4, 4, 1, 5, 0, 0]] | Passed |
| only low-zero slots | [2, [4, 1, 0, 0]] | [2, [4, 4, 4, 4]] | Failed |
| only odd slots | [2, [0, 2, 0, 1]] | [2, [2, 2, 2, 2]] | Failed |
| fold p6 into p3 | [3, [6, 5, 2, 2, 1, 0, 4, 2]] | [3, [3, 6, 3, 2, 1, 6, 4, 2]] | Failed |
| empty sketches | [2, [0, 0, 0, 0]] | [2, [0, 0, 0, 0]] | Passed |
SHA-256 / f46b387c8a8f384104b5d23d8e086a3f2b36befa4bb0f8912690ec7d39453539
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
def fold(sk, q):
d = sk['p'] - q
out = [0] * (1 << q)
for j, r in enumerate(sk['regs']):
if r == 0:
continue
nj = j >> q
low = j & ((1 << d) - 1)
if low != 0:
nr = d - low.bit_length() + 1
else:
nr = r + d
out[nj] = max(out[nj], nr)
return out
q = min(x['a']['p'], x['b']['p'])
fa = fold(x['a'], q)
fb = fold(x['b'], q)
return [q, [max(u, v) for u, v in zip(fa, fb)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fold p5 into p3',
{'a': {'p': 5,
'regs': [3,
2,
4,
3,
0,
4,
5,
1,
1,
1,
0,
0,
0,
5,
3,
0,
4,
2,
5,
3,
0,
3,
0,
0,
3,
0,
0,
5,
4,
3,
1,
0]},
'b': {'p': 3, 'regs': [2, 1, 0, 4, 3, 0, 1, 3]}},
[3, [5, 2, 3, 4, 6, 2, 5, 6]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 3, 0, 2]},
'b': {'p': 4, 'regs': [5, 0, 5, 3, 3, 2, 2, 2, 4, 4, 0, 3, 4, 0, 4, 4]}},
[2, [7, 5, 6, 6]]],
['same precision',
{'a': {'p': 3, 'regs': [0, 0, 4, 0, 1, 5, 0, 0]},
'b': {'p': 3, 'regs': [0, 2, 1, 4, 0, 0, 0, 0]}},
[3, [0, 2, 4, 4, 1, 5, 0, 0]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [4, 4, 4, 4]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 1]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 5, 0, 0, 0, 0, 4, 2]},
'b': {'p': 6,
'regs': [0,
5,
0,
0,
0,
0,
0,
0,
3,
2,
0,
0,
0,
0,
0,
0,
0,
3,
0,
0,
5,
0,
0,
1,
0,
0,
4,
0,
4,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4,
0,
3,
0,
0,
0,
0,
0,
5,
0,
0,
0,
0,
3,
0,
0,
0,
0,
0,
0,
2,
1,
3,
0,
0,
0]}},
[3, [3, 6, 3, 2, 1, 6, 4, 2]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
0,
1,
2,
0,
2,
0,
3,
0,
4,
5,
0,
3,
0,
0,
3,
3,
1,
2,
0,
5,
0,
3,
0,
4,
1,
0,
1,
1,
4,
3,
4]},
'b': {'p': 3, 'regs': [3, 0, 3, 3, 0, 1, 1, 2]}},
[3, [3, 2, 3, 5, 5, 7, 6, 3]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 0, 0, 0]},
'b': {'p': 4, 'regs': [1, 2, 5, 0, 1, 0, 2, 0, 3, 2, 4, 1, 4, 0, 3, 1]}},
[2, [3, 3, 5, 6]]],
['same precision',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 1, 2, 5, 4]},
'b': {'p': 3, 'regs': [2, 1, 0, 0, 0, 0, 0, 0]}},
[3, [2, 1, 0, 0, 1, 2, 5, 4]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [5, 5, 5, 5]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 2]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 0, 2, 4, 5, 0, 5, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
2,
5,
0,
0,
0,
0,
0,
1,
0,
0,
1,
4,
2,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
4,
0,
1,
0,
0,
0,
2,
0,
0,
0,
4,
3,
0,
0,
2,
5,
0,
0,
0]}},
[3, [1, 0, 3, 4, 5, 4, 5, 6]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [1,
2,
2,
1,
3,
3,
3,
0,
1,
0,
4,
5,
0,
0,
0,
0,
0,
2,
4,
0,
2,
4,
0,
4,
0,
3,
1,
2,
5,
5,
0,
0]},
'b': {'p': 3, 'regs': [4, 0, 0, 1, 4, 4, 0, 0]}},
[3, [4, 5, 3, 1, 4, 4, 2, 7]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 2, 0, 0]},
'b': {'p': 4, 'regs': [2, 5, 1, 1, 1, 2, 4, 5, 1, 3, 3, 3, 0, 3, 1, 3]}},
[2, [4, 3, 3, 2]]],
['same precision',
{'a': {'p': 3, 'regs': [5, 0, 0, 4, 0, 0, 2, 5]},
'b': {'p': 3, 'regs': [3, 0, 1, 1, 5, 3, 1, 0]}},
[3, [5, 0, 1, 4, 5, 3, 2, 5]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [6, 6, 6, 6]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [1, 0, 0, 3, 0, 0, 0, 5]},
'b': {'p': 6,
'regs': [0,
2,
2,
0,
0,
0,
0,
0,
0,
5,
0,
0,
0,
5,
3,
0,
3,
4,
0,
4,
0,
4,
0,
0,
0,
0,
1,
0,
0,
0,
0,
4,
0,
0,
0,
0,
3,
0,
3,
0,
0,
0,
0,
0,
0,
1,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
4,
0,
0,
5,
0,
0,
0,
0]}},
[3, [3, 3, 6, 3, 1, 1, 5, 7]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
0,
4,
0,
0,
0,
0,
5,
1,
4,
4,
0,
2,
3,
5,
1,
0,
0,
1,
1,
5,
3,
0,
0,
0,
5,
4,
3,
4,
5,
3,
2]},
'b': {'p': 3, 'regs': [5, 3, 1, 2, 0, 3, 3, 3]}},
[3, [5, 3, 3, 4, 1, 7, 3, 6]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 0, 0, 0]},
'b': {'p': 4, 'regs': [1, 0, 3, 0, 4, 4, 2, 1, 4, 4, 2, 0, 0, 1, 2, 1]}},
[2, [3, 6, 6, 2]]],
['same precision',
{'a': {'p': 3, 'regs': [3, 3, 2, 1, 5, 3, 0, 0]},
'b': {'p': 3, 'regs': [0, 1, 0, 0, 0, 2, 2, 5]}},
[3, [3, 3, 2, 1, 5, 3, 2, 5]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [3, 3, 3, 3]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 1]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [4, 2, 0, 0, 4, 0, 2, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
2,
0,
0,
5,
0,
0,
5,
0,
4,
2,
0,
0,
1,
0,
0,
0,
2,
1,
0,
0,
0,
0,
5,
0,
0,
0,
5,
3,
4,
5,
0,
5,
0,
0,
0,
0,
0,
3,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
0,
5,
0,
1,
0,
0,
0,
0,
0,
0]}},
[3, [4, 3, 2, 3, 8, 6, 2, 3]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
5,
1,
2,
0,
5,
0,
1,
1,
0,
5,
1,
0,
1,
0,
2,
3,
1,
0,
3,
4,
0,
0,
5,
0,
5,
1,
0,
0,
0,
0,
0]},
'b': {'p': 3, 'regs': [5, 1, 1, 4, 2, 3, 5, 0]}},
[3, [5, 2, 3, 4, 5, 6, 5, 0]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 3, 3, 0]},
'b': {'p': 4, 'regs': [1, 3, 2, 0, 0, 5, 2, 2, 3, 2, 4, 2, 3, 3, 1, 3]}},
[2, [3, 3, 5, 5]]],
['same precision',
{'a': {'p': 3, 'regs': [4, 0, 0, 3, 0, 4, 1, 1]},
'b': {'p': 3, 'regs': [0, 0, 0, 0, 3, 0, 4, 0]}},
[3, [4, 0, 0, 3, 3, 4, 4, 1]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [4, 4, 4, 4]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 2]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 0, 4, 4, 0, 5, 3, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
0,
2,
0,
0,
0,
1,
0,
0,
3,
0,
0,
0,
0,
0,
0,
0,
2,
0,
5,
0,
0,
4,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
4,
0,
0,
0,
5,
0,
0,
0,
0,
0,
0,
0,
0,
3,
1,
3,
1,
5,
0,
0,
0,
0,
2,
0,
3,
0,
0,
4]}},
[3, [1, 4, 4, 7, 3, 8, 3, 2]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| fold p5 into p3 | [3, [5, 3, 6, 6, 0, 0, 0, 0]] | [3, [5, 2, 3, 4, 6, 2, 5, 6]] | Failed |
| fold p4 into p2 | [2, [7, 5, 6, 6]] | [2, [7, 5, 6, 6]] | Passed |
| same precision | [3, [5, 0, 0, 0, 0, 0, 0, 0]] | [3, [0, 2, 4, 4, 1, 5, 0, 0]] | Failed |
| only low-zero slots | [2, [4, 4, 4, 4]] | [2, [4, 4, 4, 4]] | Passed |
| only odd slots | [2, [2, 2, 2, 2]] | [2, [2, 2, 2, 2]] | Passed |
| fold p6 into p3 | [3, [5, 6, 3, 2, 1, 6, 2, 2]] | [3, [3, 6, 3, 2, 1, 6, 4, 2]] | Failed |
| empty sketches | [2, [0, 0, 0, 0]] | [2, [0, 0, 0, 0]] | Passed |
SHA-256 / 440865fce009978f49002fba17020f676781a1827fd2ae535299657cf6303443
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
def fold(sk, q):
d = sk['p'] - q
out = [0] * (1 << q)
for j, r in enumerate(sk['regs']):
if r == 0:
continue
nj = j >> d
low = j & ((1 << d) - 1)
if low != 0:
nr = d - low.bit_length() + 1
else:
nr = r + d
out[nj] = max(out[nj], nr)
return out
q = min(x['a']['p'], x['b']['p'])
fa = fold(x['a'], q)
fb = fold(x['b'], q)
return [q, [max(u, v) for u, v in zip(fa, fb)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fold p5 into p3',
{'a': {'p': 5,
'regs': [3,
2,
4,
3,
0,
4,
5,
1,
1,
1,
0,
0,
0,
5,
3,
0,
4,
2,
5,
3,
0,
3,
0,
0,
3,
0,
0,
5,
4,
3,
1,
0]},
'b': {'p': 3, 'regs': [2, 1, 0, 4, 3, 0, 1, 3]}},
[3, [5, 2, 3, 4, 6, 2, 5, 6]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 3, 0, 2]},
'b': {'p': 4, 'regs': [5, 0, 5, 3, 3, 2, 2, 2, 4, 4, 0, 3, 4, 0, 4, 4]}},
[2, [7, 5, 6, 6]]],
['same precision',
{'a': {'p': 3, 'regs': [0, 0, 4, 0, 1, 5, 0, 0]},
'b': {'p': 3, 'regs': [0, 2, 1, 4, 0, 0, 0, 0]}},
[3, [0, 2, 4, 4, 1, 5, 0, 0]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [4, 4, 4, 4]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 1]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 5, 0, 0, 0, 0, 4, 2]},
'b': {'p': 6,
'regs': [0,
5,
0,
0,
0,
0,
0,
0,
3,
2,
0,
0,
0,
0,
0,
0,
0,
3,
0,
0,
5,
0,
0,
1,
0,
0,
4,
0,
4,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4,
0,
3,
0,
0,
0,
0,
0,
5,
0,
0,
0,
0,
3,
0,
0,
0,
0,
0,
0,
2,
1,
3,
0,
0,
0]}},
[3, [3, 6, 3, 2, 1, 6, 4, 2]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
0,
1,
2,
0,
2,
0,
3,
0,
4,
5,
0,
3,
0,
0,
3,
3,
1,
2,
0,
5,
0,
3,
0,
4,
1,
0,
1,
1,
4,
3,
4]},
'b': {'p': 3, 'regs': [3, 0, 3, 3, 0, 1, 1, 2]}},
[3, [3, 2, 3, 5, 5, 7, 6, 3]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 0, 0, 0]},
'b': {'p': 4, 'regs': [1, 2, 5, 0, 1, 0, 2, 0, 3, 2, 4, 1, 4, 0, 3, 1]}},
[2, [3, 3, 5, 6]]],
['same precision',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 1, 2, 5, 4]},
'b': {'p': 3, 'regs': [2, 1, 0, 0, 0, 0, 0, 0]}},
[3, [2, 1, 0, 0, 1, 2, 5, 4]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [5, 5, 5, 5]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 2]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 0, 2, 4, 5, 0, 5, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
2,
5,
0,
0,
0,
0,
0,
1,
0,
0,
1,
4,
2,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
4,
0,
1,
0,
0,
0,
2,
0,
0,
0,
4,
3,
0,
0,
2,
5,
0,
0,
0]}},
[3, [1, 0, 3, 4, 5, 4, 5, 6]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [1,
2,
2,
1,
3,
3,
3,
0,
1,
0,
4,
5,
0,
0,
0,
0,
0,
2,
4,
0,
2,
4,
0,
4,
0,
3,
1,
2,
5,
5,
0,
0]},
'b': {'p': 3, 'regs': [4, 0, 0, 1, 4, 4, 0, 0]}},
[3, [4, 5, 3, 1, 4, 4, 2, 7]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 2, 0, 0]},
'b': {'p': 4, 'regs': [2, 5, 1, 1, 1, 2, 4, 5, 1, 3, 3, 3, 0, 3, 1, 3]}},
[2, [4, 3, 3, 2]]],
['same precision',
{'a': {'p': 3, 'regs': [5, 0, 0, 4, 0, 0, 2, 5]},
'b': {'p': 3, 'regs': [3, 0, 1, 1, 5, 3, 1, 0]}},
[3, [5, 0, 1, 4, 5, 3, 2, 5]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [6, 6, 6, 6]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [1, 0, 0, 3, 0, 0, 0, 5]},
'b': {'p': 6,
'regs': [0,
2,
2,
0,
0,
0,
0,
0,
0,
5,
0,
0,
0,
5,
3,
0,
3,
4,
0,
4,
0,
4,
0,
0,
0,
0,
1,
0,
0,
0,
0,
4,
0,
0,
0,
0,
3,
0,
3,
0,
0,
0,
0,
0,
0,
1,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
4,
0,
0,
5,
0,
0,
0,
0]}},
[3, [3, 3, 6, 3, 1, 1, 5, 7]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
0,
4,
0,
0,
0,
0,
5,
1,
4,
4,
0,
2,
3,
5,
1,
0,
0,
1,
1,
5,
3,
0,
0,
0,
5,
4,
3,
4,
5,
3,
2]},
'b': {'p': 3, 'regs': [5, 3, 1, 2, 0, 3, 3, 3]}},
[3, [5, 3, 3, 4, 1, 7, 3, 6]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 0, 0, 0]},
'b': {'p': 4, 'regs': [1, 0, 3, 0, 4, 4, 2, 1, 4, 4, 2, 0, 0, 1, 2, 1]}},
[2, [3, 6, 6, 2]]],
['same precision',
{'a': {'p': 3, 'regs': [3, 3, 2, 1, 5, 3, 0, 0]},
'b': {'p': 3, 'regs': [0, 1, 0, 0, 0, 2, 2, 5]}},
[3, [3, 3, 2, 1, 5, 3, 2, 5]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [3, 3, 3, 3]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 1]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [4, 2, 0, 0, 4, 0, 2, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
2,
0,
0,
5,
0,
0,
5,
0,
4,
2,
0,
0,
1,
0,
0,
0,
2,
1,
0,
0,
0,
0,
5,
0,
0,
0,
5,
3,
4,
5,
0,
5,
0,
0,
0,
0,
0,
3,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
0,
5,
0,
1,
0,
0,
0,
0,
0,
0]}},
[3, [4, 3, 2, 3, 8, 6, 2, 3]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]],
[['fold p5 into p3',
{'a': {'p': 5,
'regs': [0,
5,
1,
2,
0,
5,
0,
1,
1,
0,
5,
1,
0,
1,
0,
2,
3,
1,
0,
3,
4,
0,
0,
5,
0,
5,
1,
0,
0,
0,
0,
0]},
'b': {'p': 3, 'regs': [5, 1, 1, 4, 2, 3, 5, 0]}},
[3, [5, 2, 3, 4, 5, 6, 5, 0]]],
['fold p4 into p2',
{'a': {'p': 2, 'regs': [0, 3, 3, 0]},
'b': {'p': 4, 'regs': [1, 3, 2, 0, 0, 5, 2, 2, 3, 2, 4, 2, 3, 3, 1, 3]}},
[2, [3, 3, 5, 5]]],
['same precision',
{'a': {'p': 3, 'regs': [4, 0, 0, 3, 0, 4, 1, 1]},
'b': {'p': 3, 'regs': [0, 0, 0, 0, 3, 0, 4, 0]}},
[3, [4, 0, 0, 3, 3, 4, 4, 1]]],
['only low-zero slots',
{'a': {'p': 4, 'regs': [2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]},
'b': {'p': 2, 'regs': [0, 1, 0, 0]}},
[2, [4, 4, 4, 4]]],
['only odd slots',
{'a': {'p': 4, 'regs': [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]},
'b': {'p': 2, 'regs': [0, 0, 0, 2]}},
[2, [2, 2, 2, 2]]],
['fold p6 into p3',
{'a': {'p': 3, 'regs': [0, 0, 4, 4, 0, 5, 3, 0]},
'b': {'p': 6,
'regs': [0,
0,
0,
0,
2,
0,
0,
0,
1,
0,
0,
3,
0,
0,
0,
0,
0,
0,
0,
2,
0,
5,
0,
0,
4,
0,
0,
0,
0,
1,
0,
0,
0,
1,
0,
0,
4,
0,
0,
0,
5,
0,
0,
0,
0,
0,
0,
0,
0,
3,
1,
3,
1,
5,
0,
0,
0,
0,
2,
0,
3,
0,
0,
4]}},
[3, [1, 4, 4, 7, 3, 8, 3, 2]]],
['empty sketches',
{'a': {'p': 3, 'regs': [0, 0, 0, 0, 0, 0, 0, 0]}, 'b': {'p': 2, 'regs': [0, 0, 0, 0]}},
[2, [0, 0, 0, 0]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| fold p5 into p3 | [3, [5, 2, 3, 4, 6, 2, 5, 6]] | [3, [5, 2, 3, 4, 6, 2, 5, 6]] | Passed |
| fold p4 into p2 | [2, [7, 5, 6, 6]] | [2, [7, 5, 6, 6]] | Passed |
| same precision | [3, [0, 2, 4, 4, 1, 5, 0, 0]] | [3, [0, 2, 4, 4, 1, 5, 0, 0]] | Passed |
| only low-zero slots | [2, [4, 4, 4, 4]] | [2, [4, 4, 4, 4]] | Passed |
| only odd slots | [2, [2, 2, 2, 2]] | [2, [2, 2, 2, 2]] | Passed |
| fold p6 into p3 | [3, [3, 6, 3, 2, 1, 6, 4, 2]] | [3, [3, 6, 3, 2, 1, 6, 4, 2]] | Passed |
| empty sketches | [2, [0, 0, 0, 0]] | [2, [0, 0, 0, 0]] | Passed |
SHA-256 / 90487cbbe4bc3f7e2e4b4b7a1387c0680be67d996a0fe4dd526d15f86395efaa
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.655730+00:00.
Case digest / 38d22299d13d26bec215dafab7886bbf5ba6872829d9688c6288841d752a2e99