FA-73231 / Probabilistic sketches / Open access
MinHash LSH banding: pairs reported in both orders · case 01
The verifier compares every candidate twice, once per ordering.
ROOT CAUSE
Pairs are admitted for u != v, so both (u, v) and (v, u) are reported.
VERIFIED REPAIR
Admit only u < v.
Unsuccessful approach: Allowing u <= v reports every signature paired with itself.
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 = (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, 1], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3], [4, 5], [5, 2], [5, 4]], 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, 1], [2, 3], [2, 5], [3, 1], [3, 2], [3, 5], [5, 1], [5, 2], [5, 3]], 0.794] | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | Failed |
| bands 2 b=4 r=2 | [[[1, 2], [1, 4], [2, 1], [2, 4], [3, 5], [4, 1], [4, 2], [5, 3]], 0.5] | [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5] | Failed |
| bands 3 b=3 r=3 | [[[1, 5], [3, 5], [5, 1], [5, 3]], 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], [3, 1]], 0.794] | [[[1, 3]], 0.794] | Failed |
| equal sums differ | [[], 0.707] | [[], 0.707] | Passed |
SHA-256 / 2e151b21e568daddc253c9563e7dae4fc12241988f3bdf09d5b93293b6c53067
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 = (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, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [2, 5], [3, 3], [3, 4], [4, 4], [4, 5], [5, 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, 1], [1, 2], [1, 3], [1, 5], [2, 2], [2, 3], [2, 5], [3, 3], [3, 5], [4, 4], [5, 5]], 0.794] | [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794] | Failed |
| bands 2 b=4 r=2 | [[[1, 1], [1, 2], [1, 4], [2, 2], [2, 4], [3, 3], [3, 5], [4, 4], [5, 5]], 0.5] | [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5] | Failed |
| bands 3 b=3 r=3 | [[[1, 1], [1, 5], [2, 2], [3, 3], [3, 5], [4, 4], [5, 5]], 0.693] | [[[1, 5], [3, 5]], 0.693] | Failed |
| same values in different bands | [[[1, 1], [2, 2], [3, 3]], 0.707] | [[], 0.707] | Failed |
| overlong signature | invalid | invalid | Passed |
| interleaved agreement | [[[1, 1], [1, 3], [2, 2], [3, 3]], 0.794] | [[[1, 3]], 0.794] | Failed |
| equal sums differ | [[[4, 4], [5, 5], [9, 9]], 0.707] | [[], 0.707] | Failed |
SHA-256 / 19c2e0e0cd4e9fb1d1e8c40d68c43acbe33a453a8ec281b380d97ff182c4c0ba
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.580469+00:00.
Case digest / 344715c630b02949896e8c989c2e76e04339d7e5aae8e58687627351dae9e368