FA-73211 / Probabilistic sketches / Open access
MinHash LSH banding: band key omits the band index · case 01
Two signatures that agree on different bands are paired although no band matches.
ROOT CAUSE
The bucket key is only the band contents, so identical tuples in different bands collide.
VERIFIED REPAIR
Include the band index in each bucket key.
Unsuccessful approach: Summing the band values with the index is a lossy key that merges unequal bands.
Case contract
Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.
Why this case matters
Locality-sensitive hashing prunes all-pairs similarity search; banding mistakes either flood the verifier with false candidates or silently miss near-duplicates.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
b = x['b']
r = x['r']
sigs = x['sigs']
if any(len(sig) != b * r for ident, sig in sigs):
return 'invalid'
buckets = {}
for ident, sig in sigs:
for i in range(b):
key = tuple(sig[i * r:(i + 1) * r])
buckets.setdefault(key, []).append(ident)
pairs = set()
for members in buckets.values():
for u in members:
for v in members:
if u < v:
pairs.add((u, v))
return [[list(p) for p in sorted(pairs)], round((1 / b) ** (1 / r), 3)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [4, 2, 3, 1, 0, 4]],
[2, [2, 1, 3, 1, 1, 4]],
[3, [2, 4, 3, 1, 2, 4]],
[4, [2, 1, 3, 1, 1, 4]],
[5, [2, 1, 1, 1, 2, 2]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [2, 1, 3, 1, 1, 3]],
[2, [2, 1, 3, 1, 4, 3]],
[3, [2, 1, 3, 1, 4, 4]],
[4, [1, 1, 2, 4, 0, 2]],
[5, [2, 1, 3, 1, 4, 4]]]},
[[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [1, 2, 4, 0, 0, 1, 3, 4]],
[2, [0, 4, 4, 0, 1, 1, 3, 4]],
[3, [3, 1, 0, 3, 1, 3, 1, 2]],
[4, [1, 1, 4, 1, 4, 3, 3, 4]],
[5, [1, 4, 4, 3, 1, 3, 1, 3]]]},
[[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 1, 1, 1, 0, 2, 1, 0, 4]],
[2, [3, 1, 1, 1, 0, 0, 3, 3, 3]],
[3, [1, 1, 3, 1, 0, 3, 3, 1, 2]],
[4, [2, 2, 1, 4, 0, 1, 2, 1, 2]],
[5, [0, 2, 1, 1, 0, 2, 3, 1, 2]]]},
[[[1, 5], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 1, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 1]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 1]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [0, 0, 2, 2, 3, 1]],
[2, [4, 2, 4, 2, 3, 1]],
[3, [0, 0, 2, 2, 3, 1]],
[4, [0, 0, 2, 2, 3, 1]],
[5, [1, 0, 2, 4, 4, 1]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 0, 1, 2, 4, 0]],
[2, [3, 1, 2, 2, 2, 0]],
[3, [3, 1, 2, 3, 4, 0]],
[4, [2, 1, 2, 2, 2, 0]],
[5, [3, 3, 3, 3, 3, 0]]]},
[[[2, 3], [2, 4]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [2, 0, 4, 3, 0, 4, 4, 3]],
[2, [2, 0, 2, 3, 0, 3, 0, 3]],
[3, [2, 1, 0, 2, 0, 3, 3, 3]],
[4, [0, 0, 0, 3, 0, 3, 3, 3]],
[5, [3, 3, 2, 1, 0, 3, 0, 4]]]},
[[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [2, 3, 0, 4, 3, 1, 2, 2, 3]],
[2, [2, 3, 3, 4, 0, 1, 4, 0, 3]],
[3, [2, 3, 0, 4, 3, 1, 2, 2, 3]],
[4, [2, 3, 3, 2, 3, 1, 1, 2, 3]],
[5, [2, 3, 0, 4, 3, 1, 2, 2, 3]]]},
[[[1, 3], [1, 5], [2, 4], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 2, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 2]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 2]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [0, 1, 2, 0, 3, 4]],
[2, [4, 0, 2, 0, 3, 3]],
[3, [0, 0, 2, 0, 4, 4]],
[4, [2, 1, 4, 0, 3, 2]],
[5, [0, 0, 3, 3, 4, 2]]]},
[[[1, 2], [1, 3], [2, 3], [3, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [4, 3, 0, 0, 1, 2]],
[2, [4, 3, 0, 0, 1, 2]],
[3, [3, 3, 0, 0, 1, 2]],
[4, [4, 3, 0, 0, 1, 2]],
[5, [4, 0, 4, 1, 2, 2]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [0, 0, 3, 1, 2, 3, 4, 3]],
[2, [0, 0, 0, 4, 2, 0, 3, 4]],
[3, [3, 0, 0, 1, 2, 0, 4, 3]],
[4, [0, 3, 0, 0, 2, 4, 3, 2]],
[5, [1, 0, 3, 1, 1, 4, 0, 4]]]},
[[[1, 2], [1, 3], [1, 5], [2, 3]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [4, 3, 0, 0, 4, 4, 3, 2, 1]],
[2, [4, 1, 3, 0, 0, 0, 1, 4, 1]],
[3, [4, 1, 3, 0, 0, 0, 4, 0, 1]],
[4, [4, 4, 4, 0, 0, 4, 0, 1, 1]],
[5, [1, 2, 3, 0, 0, 0, 1, 1, 1]]]},
[[[2, 3], [2, 5], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 3, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 3]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 3]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [4, 3, 4, 3, 0, 4]],
[2, [4, 2, 3, 3, 0, 1]],
[3, [4, 2, 1, 3, 0, 1]],
[4, [4, 2, 3, 3, 2, 1]],
[5, [4, 4, 3, 3, 0, 0]]]},
[[[2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [3, 1, 4, 4, 2, 3]],
[2, [1, 4, 0, 2, 2, 3]],
[3, [3, 0, 4, 4, 2, 2]],
[4, [3, 1, 0, 4, 3, 3]],
[5, [4, 1, 4, 1, 3, 3]]]},
[[], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [3, 3, 2, 2, 0, 4, 4, 4]],
[2, [1, 3, 1, 1, 4, 0, 4, 1]],
[3, [3, 3, 1, 1, 0, 2, 1, 4]],
[4, [4, 0, 1, 1, 0, 4, 1, 4]],
[5, [3, 3, 1, 2, 0, 0, 1, 4]]]},
[[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 1, 3, 2, 2, 2, 4, 3, 2]],
[2, [3, 1, 3, 0, 2, 2, 4, 4, 3]],
[3, [1, 1, 4, 1, 2, 2, 4, 3, 2]],
[4, [1, 1, 3, 2, 2, 2, 4, 3, 2]],
[5, [1, 1, 2, 4, 2, 2, 2, 3, 1]]]},
[[[1, 3], [1, 4], [3, 4]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 4, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 4]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 4]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [3, 3, 2, 3, 0, 4]],
[2, [4, 3, 2, 3, 1, 0]],
[3, [1, 2, 2, 3, 3, 0]],
[4, [1, 3, 2, 3, 0, 0]],
[5, [1, 3, 4, 3, 4, 3]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [2, 1, 4, 2, 2, 4]],
[2, [3, 1, 4, 2, 2, 0]],
[3, [2, 1, 4, 2, 2, 4]],
[4, [3, 2, 4, 2, 2, 0]],
[5, [3, 1, 4, 4, 0, 0]]]},
[[[1, 3], [2, 4], [2, 5]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [1, 0, 0, 1, 3, 1, 4, 3]],
[2, [3, 2, 3, 1, 4, 4, 3, 3]],
[3, [1, 0, 0, 1, 4, 1, 4, 3]],
[4, [1, 0, 3, 2, 4, 3, 3, 3]],
[5, [4, 0, 0, 4, 1, 3, 1, 3]]]},
[[[1, 3], [1, 4], [2, 4], [3, 4]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 4, 1, 3, 1, 3, 1, 2, 4]],
[2, [0, 1, 4, 0, 4, 3, 1, 3, 0]],
[3, [1, 4, 1, 0, 4, 1, 3, 4, 3]],
[4, [1, 4, 3, 4, 4, 3, 1, 3, 3]],
[5, [1, 2, 3, 0, 4, 3, 1, 3, 4]]]},
[[[1, 3], [2, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 5, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 5]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 5]]]},
[[], 0.707]]]]
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 |
|---|---|---|---|
| bands 0 b=3 r=2 | [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577] | [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577] | Passed |
| bands 1 b=2 r=3 | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | Passed |
| bands 2 b=4 r=2 | [[[1, 2], [1, 3], [1, 4], [2, 4], [3, 5], [4, 5]], 0.5] | [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5] | Failed |
| bands 3 b=3 r=3 | [[[1, 5], [3, 5]], 0.693] | [[[1, 5], [3, 5]], 0.693] | Passed |
| same values in different bands | [[[1, 2]], 0.707] | [[], 0.707] | Failed |
| overlong signature | invalid | invalid | Passed |
| interleaved agreement | [[[1, 3]], 0.794] | [[[1, 3]], 0.794] | Passed |
| equal sums differ | [[], 0.707] | [[], 0.707] | Passed |
SHA-256 / 010d81e87690cfacbc92135c88acd86a260b9965aadc28f098c27d16ea00d5e7
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
b = x['b']
r = x['r']
sigs = x['sigs']
if any(len(sig) != b * r for ident, sig in sigs):
return 'invalid'
buckets = {}
for ident, sig in sigs:
for i in range(b):
key = (sum(sig[i * r:(i + 1) * r]) + i,)
buckets.setdefault(key, []).append(ident)
pairs = set()
for members in buckets.values():
for u in members:
for v in members:
if u < v:
pairs.add((u, v))
return [[list(p) for p in sorted(pairs)], round((1 / b) ** (1 / r), 3)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [4, 2, 3, 1, 0, 4]],
[2, [2, 1, 3, 1, 1, 4]],
[3, [2, 4, 3, 1, 2, 4]],
[4, [2, 1, 3, 1, 1, 4]],
[5, [2, 1, 1, 1, 2, 2]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [2, 1, 3, 1, 1, 3]],
[2, [2, 1, 3, 1, 4, 3]],
[3, [2, 1, 3, 1, 4, 4]],
[4, [1, 1, 2, 4, 0, 2]],
[5, [2, 1, 3, 1, 4, 4]]]},
[[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [1, 2, 4, 0, 0, 1, 3, 4]],
[2, [0, 4, 4, 0, 1, 1, 3, 4]],
[3, [3, 1, 0, 3, 1, 3, 1, 2]],
[4, [1, 1, 4, 1, 4, 3, 3, 4]],
[5, [1, 4, 4, 3, 1, 3, 1, 3]]]},
[[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 1, 1, 1, 0, 2, 1, 0, 4]],
[2, [3, 1, 1, 1, 0, 0, 3, 3, 3]],
[3, [1, 1, 3, 1, 0, 3, 3, 1, 2]],
[4, [2, 2, 1, 4, 0, 1, 2, 1, 2]],
[5, [0, 2, 1, 1, 0, 2, 3, 1, 2]]]},
[[[1, 5], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 1, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 1]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 1]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [0, 0, 2, 2, 3, 1]],
[2, [4, 2, 4, 2, 3, 1]],
[3, [0, 0, 2, 2, 3, 1]],
[4, [0, 0, 2, 2, 3, 1]],
[5, [1, 0, 2, 4, 4, 1]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 0, 1, 2, 4, 0]],
[2, [3, 1, 2, 2, 2, 0]],
[3, [3, 1, 2, 3, 4, 0]],
[4, [2, 1, 2, 2, 2, 0]],
[5, [3, 3, 3, 3, 3, 0]]]},
[[[2, 3], [2, 4]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [2, 0, 4, 3, 0, 4, 4, 3]],
[2, [2, 0, 2, 3, 0, 3, 0, 3]],
[3, [2, 1, 0, 2, 0, 3, 3, 3]],
[4, [0, 0, 0, 3, 0, 3, 3, 3]],
[5, [3, 3, 2, 1, 0, 3, 0, 4]]]},
[[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [2, 3, 0, 4, 3, 1, 2, 2, 3]],
[2, [2, 3, 3, 4, 0, 1, 4, 0, 3]],
[3, [2, 3, 0, 4, 3, 1, 2, 2, 3]],
[4, [2, 3, 3, 2, 3, 1, 1, 2, 3]],
[5, [2, 3, 0, 4, 3, 1, 2, 2, 3]]]},
[[[1, 3], [1, 5], [2, 4], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 2, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 2]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 2]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [0, 1, 2, 0, 3, 4]],
[2, [4, 0, 2, 0, 3, 3]],
[3, [0, 0, 2, 0, 4, 4]],
[4, [2, 1, 4, 0, 3, 2]],
[5, [0, 0, 3, 3, 4, 2]]]},
[[[1, 2], [1, 3], [2, 3], [3, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [4, 3, 0, 0, 1, 2]],
[2, [4, 3, 0, 0, 1, 2]],
[3, [3, 3, 0, 0, 1, 2]],
[4, [4, 3, 0, 0, 1, 2]],
[5, [4, 0, 4, 1, 2, 2]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [0, 0, 3, 1, 2, 3, 4, 3]],
[2, [0, 0, 0, 4, 2, 0, 3, 4]],
[3, [3, 0, 0, 1, 2, 0, 4, 3]],
[4, [0, 3, 0, 0, 2, 4, 3, 2]],
[5, [1, 0, 3, 1, 1, 4, 0, 4]]]},
[[[1, 2], [1, 3], [1, 5], [2, 3]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [4, 3, 0, 0, 4, 4, 3, 2, 1]],
[2, [4, 1, 3, 0, 0, 0, 1, 4, 1]],
[3, [4, 1, 3, 0, 0, 0, 4, 0, 1]],
[4, [4, 4, 4, 0, 0, 4, 0, 1, 1]],
[5, [1, 2, 3, 0, 0, 0, 1, 1, 1]]]},
[[[2, 3], [2, 5], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 3, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 3]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 3]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [4, 3, 4, 3, 0, 4]],
[2, [4, 2, 3, 3, 0, 1]],
[3, [4, 2, 1, 3, 0, 1]],
[4, [4, 2, 3, 3, 2, 1]],
[5, [4, 4, 3, 3, 0, 0]]]},
[[[2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [3, 1, 4, 4, 2, 3]],
[2, [1, 4, 0, 2, 2, 3]],
[3, [3, 0, 4, 4, 2, 2]],
[4, [3, 1, 0, 4, 3, 3]],
[5, [4, 1, 4, 1, 3, 3]]]},
[[], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [3, 3, 2, 2, 0, 4, 4, 4]],
[2, [1, 3, 1, 1, 4, 0, 4, 1]],
[3, [3, 3, 1, 1, 0, 2, 1, 4]],
[4, [4, 0, 1, 1, 0, 4, 1, 4]],
[5, [3, 3, 1, 2, 0, 0, 1, 4]]]},
[[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 1, 3, 2, 2, 2, 4, 3, 2]],
[2, [3, 1, 3, 0, 2, 2, 4, 4, 3]],
[3, [1, 1, 4, 1, 2, 2, 4, 3, 2]],
[4, [1, 1, 3, 2, 2, 2, 4, 3, 2]],
[5, [1, 1, 2, 4, 2, 2, 2, 3, 1]]]},
[[[1, 3], [1, 4], [3, 4]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 4, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 4]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 4]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [3, 3, 2, 3, 0, 4]],
[2, [4, 3, 2, 3, 1, 0]],
[3, [1, 2, 2, 3, 3, 0]],
[4, [1, 3, 2, 3, 0, 0]],
[5, [1, 3, 4, 3, 4, 3]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [2, 1, 4, 2, 2, 4]],
[2, [3, 1, 4, 2, 2, 0]],
[3, [2, 1, 4, 2, 2, 4]],
[4, [3, 2, 4, 2, 2, 0]],
[5, [3, 1, 4, 4, 0, 0]]]},
[[[1, 3], [2, 4], [2, 5]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [1, 0, 0, 1, 3, 1, 4, 3]],
[2, [3, 2, 3, 1, 4, 4, 3, 3]],
[3, [1, 0, 0, 1, 4, 1, 4, 3]],
[4, [1, 0, 3, 2, 4, 3, 3, 3]],
[5, [4, 0, 0, 4, 1, 3, 1, 3]]]},
[[[1, 3], [1, 4], [2, 4], [3, 4]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 4, 1, 3, 1, 3, 1, 2, 4]],
[2, [0, 1, 4, 0, 4, 3, 1, 3, 0]],
[3, [1, 4, 1, 0, 4, 1, 3, 4, 3]],
[4, [1, 4, 3, 4, 4, 3, 1, 3, 3]],
[5, [1, 2, 3, 0, 4, 3, 1, 3, 4]]]},
[[[1, 3], [2, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 5, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 5]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 5]]]},
[[], 0.707]]]]
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 |
|---|---|---|---|
| bands 0 b=3 r=2 | [[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.577] | [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577] | Failed |
| bands 1 b=2 r=3 | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | Passed |
| bands 2 b=4 r=2 | [[[1, 2], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5] | [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5] | Failed |
| bands 3 b=3 r=3 | [[[1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5]], 0.693] | [[[1, 5], [3, 5]], 0.693] | Failed |
| same values in different bands | [[], 0.707] | [[], 0.707] | Passed |
| overlong signature | invalid | invalid | Passed |
| interleaved agreement | [[[1, 3]], 0.794] | [[[1, 3]], 0.794] | Passed |
| equal sums differ | [[[4, 5], [4, 9], [5, 9]], 0.707] | [[], 0.707] | Failed |
SHA-256 / 15e62fe43e179ea1637dce652948e1025fa55d5b82b2a3a52e3f1d38996f5ae2
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
b = x['b']
r = x['r']
sigs = x['sigs']
if any(len(sig) != b * r for ident, sig in sigs):
return 'invalid'
buckets = {}
for ident, sig in sigs:
for i in range(b):
key = (i, tuple(sig[i * r:(i + 1) * r]))
buckets.setdefault(key, []).append(ident)
pairs = set()
for members in buckets.values():
for u in members:
for v in members:
if u < v:
pairs.add((u, v))
return [[list(p) for p in sorted(pairs)], round((1 / b) ** (1 / r), 3)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [4, 2, 3, 1, 0, 4]],
[2, [2, 1, 3, 1, 1, 4]],
[3, [2, 4, 3, 1, 2, 4]],
[4, [2, 1, 3, 1, 1, 4]],
[5, [2, 1, 1, 1, 2, 2]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [2, 1, 3, 1, 1, 3]],
[2, [2, 1, 3, 1, 4, 3]],
[3, [2, 1, 3, 1, 4, 4]],
[4, [1, 1, 2, 4, 0, 2]],
[5, [2, 1, 3, 1, 4, 4]]]},
[[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [1, 2, 4, 0, 0, 1, 3, 4]],
[2, [0, 4, 4, 0, 1, 1, 3, 4]],
[3, [3, 1, 0, 3, 1, 3, 1, 2]],
[4, [1, 1, 4, 1, 4, 3, 3, 4]],
[5, [1, 4, 4, 3, 1, 3, 1, 3]]]},
[[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 1, 1, 1, 0, 2, 1, 0, 4]],
[2, [3, 1, 1, 1, 0, 0, 3, 3, 3]],
[3, [1, 1, 3, 1, 0, 3, 3, 1, 2]],
[4, [2, 2, 1, 4, 0, 1, 2, 1, 2]],
[5, [0, 2, 1, 1, 0, 2, 3, 1, 2]]]},
[[[1, 5], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 1, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 1]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 1]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [0, 0, 2, 2, 3, 1]],
[2, [4, 2, 4, 2, 3, 1]],
[3, [0, 0, 2, 2, 3, 1]],
[4, [0, 0, 2, 2, 3, 1]],
[5, [1, 0, 2, 4, 4, 1]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 0, 1, 2, 4, 0]],
[2, [3, 1, 2, 2, 2, 0]],
[3, [3, 1, 2, 3, 4, 0]],
[4, [2, 1, 2, 2, 2, 0]],
[5, [3, 3, 3, 3, 3, 0]]]},
[[[2, 3], [2, 4]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [2, 0, 4, 3, 0, 4, 4, 3]],
[2, [2, 0, 2, 3, 0, 3, 0, 3]],
[3, [2, 1, 0, 2, 0, 3, 3, 3]],
[4, [0, 0, 0, 3, 0, 3, 3, 3]],
[5, [3, 3, 2, 1, 0, 3, 0, 4]]]},
[[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [2, 3, 0, 4, 3, 1, 2, 2, 3]],
[2, [2, 3, 3, 4, 0, 1, 4, 0, 3]],
[3, [2, 3, 0, 4, 3, 1, 2, 2, 3]],
[4, [2, 3, 3, 2, 3, 1, 1, 2, 3]],
[5, [2, 3, 0, 4, 3, 1, 2, 2, 3]]]},
[[[1, 3], [1, 5], [2, 4], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 2, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 2]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 2]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [0, 1, 2, 0, 3, 4]],
[2, [4, 0, 2, 0, 3, 3]],
[3, [0, 0, 2, 0, 4, 4]],
[4, [2, 1, 4, 0, 3, 2]],
[5, [0, 0, 3, 3, 4, 2]]]},
[[[1, 2], [1, 3], [2, 3], [3, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [4, 3, 0, 0, 1, 2]],
[2, [4, 3, 0, 0, 1, 2]],
[3, [3, 3, 0, 0, 1, 2]],
[4, [4, 3, 0, 0, 1, 2]],
[5, [4, 0, 4, 1, 2, 2]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [0, 0, 3, 1, 2, 3, 4, 3]],
[2, [0, 0, 0, 4, 2, 0, 3, 4]],
[3, [3, 0, 0, 1, 2, 0, 4, 3]],
[4, [0, 3, 0, 0, 2, 4, 3, 2]],
[5, [1, 0, 3, 1, 1, 4, 0, 4]]]},
[[[1, 2], [1, 3], [1, 5], [2, 3]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [4, 3, 0, 0, 4, 4, 3, 2, 1]],
[2, [4, 1, 3, 0, 0, 0, 1, 4, 1]],
[3, [4, 1, 3, 0, 0, 0, 4, 0, 1]],
[4, [4, 4, 4, 0, 0, 4, 0, 1, 1]],
[5, [1, 2, 3, 0, 0, 0, 1, 1, 1]]]},
[[[2, 3], [2, 5], [3, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 3, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 3]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 3]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [4, 3, 4, 3, 0, 4]],
[2, [4, 2, 3, 3, 0, 1]],
[3, [4, 2, 1, 3, 0, 1]],
[4, [4, 2, 3, 3, 2, 1]],
[5, [4, 4, 3, 3, 0, 0]]]},
[[[2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [3, 1, 4, 4, 2, 3]],
[2, [1, 4, 0, 2, 2, 3]],
[3, [3, 0, 4, 4, 2, 2]],
[4, [3, 1, 0, 4, 3, 3]],
[5, [4, 1, 4, 1, 3, 3]]]},
[[], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [3, 3, 2, 2, 0, 4, 4, 4]],
[2, [1, 3, 1, 1, 4, 0, 4, 1]],
[3, [3, 3, 1, 1, 0, 2, 1, 4]],
[4, [4, 0, 1, 1, 0, 4, 1, 4]],
[5, [3, 3, 1, 2, 0, 0, 1, 4]]]},
[[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 1, 3, 2, 2, 2, 4, 3, 2]],
[2, [3, 1, 3, 0, 2, 2, 4, 4, 3]],
[3, [1, 1, 4, 1, 2, 2, 4, 3, 2]],
[4, [1, 1, 3, 2, 2, 2, 4, 3, 2]],
[5, [1, 1, 2, 4, 2, 2, 2, 3, 1]]]},
[[[1, 3], [1, 4], [3, 4]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 4, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 4]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 4]]]},
[[], 0.707]]],
[['bands 0 b=3 r=2',
{'b': 3,
'r': 2,
'sigs': [[1, [3, 3, 2, 3, 0, 4]],
[2, [4, 3, 2, 3, 1, 0]],
[3, [1, 2, 2, 3, 3, 0]],
[4, [1, 3, 2, 3, 0, 0]],
[5, [1, 3, 4, 3, 4, 3]]]},
[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [4, 5]], 0.577]],
['bands 1 b=2 r=3',
{'b': 2,
'r': 3,
'sigs': [[1, [2, 1, 4, 2, 2, 4]],
[2, [3, 1, 4, 2, 2, 0]],
[3, [2, 1, 4, 2, 2, 4]],
[4, [3, 2, 4, 2, 2, 0]],
[5, [3, 1, 4, 4, 0, 0]]]},
[[[1, 3], [2, 4], [2, 5]], 0.794]],
['bands 2 b=4 r=2',
{'b': 4,
'r': 2,
'sigs': [[1, [1, 0, 0, 1, 3, 1, 4, 3]],
[2, [3, 2, 3, 1, 4, 4, 3, 3]],
[3, [1, 0, 0, 1, 4, 1, 4, 3]],
[4, [1, 0, 3, 2, 4, 3, 3, 3]],
[5, [4, 0, 0, 4, 1, 3, 1, 3]]]},
[[[1, 3], [1, 4], [2, 4], [3, 4]], 0.5]],
['bands 3 b=3 r=3',
{'b': 3,
'r': 3,
'sigs': [[1, [1, 4, 1, 3, 1, 3, 1, 2, 4]],
[2, [0, 1, 4, 0, 4, 3, 1, 3, 0]],
[3, [1, 4, 1, 0, 4, 1, 3, 4, 3]],
[4, [1, 4, 3, 4, 4, 3, 1, 3, 3]],
[5, [1, 2, 3, 0, 4, 3, 1, 3, 4]]]},
[[[1, 3], [2, 5]], 0.693]],
['same values in different bands',
{'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 5, 6, 6]]]},
[[], 0.707]],
['overlong signature',
{'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},
'invalid'],
['interleaved agreement',
{'b': 2,
'r': 3,
'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 5]]]},
[[[1, 3]], 0.794]],
['equal sums differ',
{'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 5]]]},
[[], 0.707]]]]
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 |
|---|---|---|---|
| bands 0 b=3 r=2 | [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577] | [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577] | Passed |
| bands 1 b=2 r=3 | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | Passed |
| bands 2 b=4 r=2 | [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5] | [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5] | Passed |
| bands 3 b=3 r=3 | [[[1, 5], [3, 5]], 0.693] | [[[1, 5], [3, 5]], 0.693] | Passed |
| same values in different bands | [[], 0.707] | [[], 0.707] | Passed |
| overlong signature | invalid | invalid | Passed |
| interleaved agreement | [[[1, 3]], 0.794] | [[[1, 3]], 0.794] | Passed |
| equal sums differ | [[], 0.707] | [[], 0.707] | Passed |
SHA-256 / 6ca43b0487f3cd9bf6eead3f89ccedf46fcad81589797a6d21b87557f339f4b9
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.445574+00:00.
Case digest / 353cea99521401a7459e14cb1148d9e40259554268af9e2a4a964201dce2cd0d