{"abstract":"Two signatures that agree on different bands are paired although no band matches.","category":"Probabilistic sketches","checks":8,"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.","evaluation_group":"w2-probabilistic_sketches-lsh-banding","failed_approach":"Summing the band values with the index is a lossy key that merges unequal bands.","family":"w2-probabilistic_sketches-lsh-banding-band-identity","id":"FA-73211","implementations":{"attempt":{"sha256":"15e62fe43e179ea1637dce652948e1025fa55d5b82b2a3a52e3f1d38996f5ae2","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    b = x['b']\n    r = x['r']\n    sigs = x['sigs']\n    if any(len(sig) != b * r for ident, sig in sigs):\n        return 'invalid'\n    buckets = {}\n    for ident, sig in sigs:\n        for i in range(b):\n            key = (sum(sig[i * r:(i + 1) * r]) + i,)\n            buckets.setdefault(key, []).append(ident)\n    pairs = set()\n    for members in buckets.values():\n        for u in members:\n            for v in members:\n                if u < v:\n                    pairs.add((u, v))\n    return [[list(p) for p in sorted(pairs)], round((1 / b) ** (1 / r), 3)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [4, 2, 3, 1, 0, 4]],\n             [2, [2, 1, 3, 1, 1, 4]],\n             [3, [2, 4, 3, 1, 2, 4]],\n             [4, [2, 1, 3, 1, 1, 4]],\n             [5, [2, 1, 1, 1, 2, 2]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [2, 1, 3, 1, 1, 3]],\n             [2, [2, 1, 3, 1, 4, 3]],\n             [3, [2, 1, 3, 1, 4, 4]],\n             [4, [1, 1, 2, 4, 0, 2]],\n             [5, [2, 1, 3, 1, 4, 4]]]},\n   [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [1, 2, 4, 0, 0, 1, 3, 4]],\n             [2, [0, 4, 4, 0, 1, 1, 3, 4]],\n             [3, [3, 1, 0, 3, 1, 3, 1, 2]],\n             [4, [1, 1, 4, 1, 4, 3, 3, 4]],\n             [5, [1, 4, 4, 3, 1, 3, 1, 3]]]},\n   [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 1, 1, 1, 0, 2, 1, 0, 4]],\n             [2, [3, 1, 1, 1, 0, 0, 3, 3, 3]],\n             [3, [1, 1, 3, 1, 0, 3, 3, 1, 2]],\n             [4, [2, 2, 1, 4, 0, 1, 2, 1, 2]],\n             [5, [0, 2, 1, 1, 0, 2, 3, 1, 2]]]},\n   [[[1, 5], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 1, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 1]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 1]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [0, 0, 2, 2, 3, 1]],\n             [2, [4, 2, 4, 2, 3, 1]],\n             [3, [0, 0, 2, 2, 3, 1]],\n             [4, [0, 0, 2, 2, 3, 1]],\n             [5, [1, 0, 2, 4, 4, 1]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 0, 1, 2, 4, 0]],\n             [2, [3, 1, 2, 2, 2, 0]],\n             [3, [3, 1, 2, 3, 4, 0]],\n             [4, [2, 1, 2, 2, 2, 0]],\n             [5, [3, 3, 3, 3, 3, 0]]]},\n   [[[2, 3], [2, 4]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [2, 0, 4, 3, 0, 4, 4, 3]],\n             [2, [2, 0, 2, 3, 0, 3, 0, 3]],\n             [3, [2, 1, 0, 2, 0, 3, 3, 3]],\n             [4, [0, 0, 0, 3, 0, 3, 3, 3]],\n             [5, [3, 3, 2, 1, 0, 3, 0, 4]]]},\n   [[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [2, 3, 0, 4, 3, 1, 2, 2, 3]],\n             [2, [2, 3, 3, 4, 0, 1, 4, 0, 3]],\n             [3, [2, 3, 0, 4, 3, 1, 2, 2, 3]],\n             [4, [2, 3, 3, 2, 3, 1, 1, 2, 3]],\n             [5, [2, 3, 0, 4, 3, 1, 2, 2, 3]]]},\n   [[[1, 3], [1, 5], [2, 4], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 2, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 2]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 2]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [0, 1, 2, 0, 3, 4]],\n             [2, [4, 0, 2, 0, 3, 3]],\n             [3, [0, 0, 2, 0, 4, 4]],\n             [4, [2, 1, 4, 0, 3, 2]],\n             [5, [0, 0, 3, 3, 4, 2]]]},\n   [[[1, 2], [1, 3], [2, 3], [3, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [4, 3, 0, 0, 1, 2]],\n             [2, [4, 3, 0, 0, 1, 2]],\n             [3, [3, 3, 0, 0, 1, 2]],\n             [4, [4, 3, 0, 0, 1, 2]],\n             [5, [4, 0, 4, 1, 2, 2]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [0, 0, 3, 1, 2, 3, 4, 3]],\n             [2, [0, 0, 0, 4, 2, 0, 3, 4]],\n             [3, [3, 0, 0, 1, 2, 0, 4, 3]],\n             [4, [0, 3, 0, 0, 2, 4, 3, 2]],\n             [5, [1, 0, 3, 1, 1, 4, 0, 4]]]},\n   [[[1, 2], [1, 3], [1, 5], [2, 3]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [4, 3, 0, 0, 4, 4, 3, 2, 1]],\n             [2, [4, 1, 3, 0, 0, 0, 1, 4, 1]],\n             [3, [4, 1, 3, 0, 0, 0, 4, 0, 1]],\n             [4, [4, 4, 4, 0, 0, 4, 0, 1, 1]],\n             [5, [1, 2, 3, 0, 0, 0, 1, 1, 1]]]},\n   [[[2, 3], [2, 5], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 3, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 3]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 3]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [4, 3, 4, 3, 0, 4]],\n             [2, [4, 2, 3, 3, 0, 1]],\n             [3, [4, 2, 1, 3, 0, 1]],\n             [4, [4, 2, 3, 3, 2, 1]],\n             [5, [4, 4, 3, 3, 0, 0]]]},\n   [[[2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [3, 1, 4, 4, 2, 3]],\n             [2, [1, 4, 0, 2, 2, 3]],\n             [3, [3, 0, 4, 4, 2, 2]],\n             [4, [3, 1, 0, 4, 3, 3]],\n             [5, [4, 1, 4, 1, 3, 3]]]},\n   [[], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [3, 3, 2, 2, 0, 4, 4, 4]],\n             [2, [1, 3, 1, 1, 4, 0, 4, 1]],\n             [3, [3, 3, 1, 1, 0, 2, 1, 4]],\n             [4, [4, 0, 1, 1, 0, 4, 1, 4]],\n             [5, [3, 3, 1, 2, 0, 0, 1, 4]]]},\n   [[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 1, 3, 2, 2, 2, 4, 3, 2]],\n             [2, [3, 1, 3, 0, 2, 2, 4, 4, 3]],\n             [3, [1, 1, 4, 1, 2, 2, 4, 3, 2]],\n             [4, [1, 1, 3, 2, 2, 2, 4, 3, 2]],\n             [5, [1, 1, 2, 4, 2, 2, 2, 3, 1]]]},\n   [[[1, 3], [1, 4], [3, 4]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 4, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 4]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 4]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [3, 3, 2, 3, 0, 4]],\n             [2, [4, 3, 2, 3, 1, 0]],\n             [3, [1, 2, 2, 3, 3, 0]],\n             [4, [1, 3, 2, 3, 0, 0]],\n             [5, [1, 3, 4, 3, 4, 3]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [2, 1, 4, 2, 2, 4]],\n             [2, [3, 1, 4, 2, 2, 0]],\n             [3, [2, 1, 4, 2, 2, 4]],\n             [4, [3, 2, 4, 2, 2, 0]],\n             [5, [3, 1, 4, 4, 0, 0]]]},\n   [[[1, 3], [2, 4], [2, 5]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [1, 0, 0, 1, 3, 1, 4, 3]],\n             [2, [3, 2, 3, 1, 4, 4, 3, 3]],\n             [3, [1, 0, 0, 1, 4, 1, 4, 3]],\n             [4, [1, 0, 3, 2, 4, 3, 3, 3]],\n             [5, [4, 0, 0, 4, 1, 3, 1, 3]]]},\n   [[[1, 3], [1, 4], [2, 4], [3, 4]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 4, 1, 3, 1, 3, 1, 2, 4]],\n             [2, [0, 1, 4, 0, 4, 3, 1, 3, 0]],\n             [3, [1, 4, 1, 0, 4, 1, 3, 4, 3]],\n             [4, [1, 4, 3, 4, 4, 3, 1, 3, 3]],\n             [5, [1, 2, 3, 0, 4, 3, 1, 3, 4]]]},\n   [[[1, 3], [2, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 5, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 5]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 5]]]},\n   [[], 0.707]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"010d81e87690cfacbc92135c88acd86a260b9965aadc28f098c27d16ea00d5e7","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    b = x['b']\n    r = x['r']\n    sigs = x['sigs']\n    if any(len(sig) != b * r for ident, sig in sigs):\n        return 'invalid'\n    buckets = {}\n    for ident, sig in sigs:\n        for i in range(b):\n            key = tuple(sig[i * r:(i + 1) * r])\n            buckets.setdefault(key, []).append(ident)\n    pairs = set()\n    for members in buckets.values():\n        for u in members:\n            for v in members:\n                if u < v:\n                    pairs.add((u, v))\n    return [[list(p) for p in sorted(pairs)], round((1 / b) ** (1 / r), 3)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [4, 2, 3, 1, 0, 4]],\n             [2, [2, 1, 3, 1, 1, 4]],\n             [3, [2, 4, 3, 1, 2, 4]],\n             [4, [2, 1, 3, 1, 1, 4]],\n             [5, [2, 1, 1, 1, 2, 2]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [2, 1, 3, 1, 1, 3]],\n             [2, [2, 1, 3, 1, 4, 3]],\n             [3, [2, 1, 3, 1, 4, 4]],\n             [4, [1, 1, 2, 4, 0, 2]],\n             [5, [2, 1, 3, 1, 4, 4]]]},\n   [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [1, 2, 4, 0, 0, 1, 3, 4]],\n             [2, [0, 4, 4, 0, 1, 1, 3, 4]],\n             [3, [3, 1, 0, 3, 1, 3, 1, 2]],\n             [4, [1, 1, 4, 1, 4, 3, 3, 4]],\n             [5, [1, 4, 4, 3, 1, 3, 1, 3]]]},\n   [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 1, 1, 1, 0, 2, 1, 0, 4]],\n             [2, [3, 1, 1, 1, 0, 0, 3, 3, 3]],\n             [3, [1, 1, 3, 1, 0, 3, 3, 1, 2]],\n             [4, [2, 2, 1, 4, 0, 1, 2, 1, 2]],\n             [5, [0, 2, 1, 1, 0, 2, 3, 1, 2]]]},\n   [[[1, 5], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 1, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 1]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 1]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [0, 0, 2, 2, 3, 1]],\n             [2, [4, 2, 4, 2, 3, 1]],\n             [3, [0, 0, 2, 2, 3, 1]],\n             [4, [0, 0, 2, 2, 3, 1]],\n             [5, [1, 0, 2, 4, 4, 1]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 0, 1, 2, 4, 0]],\n             [2, [3, 1, 2, 2, 2, 0]],\n             [3, [3, 1, 2, 3, 4, 0]],\n             [4, [2, 1, 2, 2, 2, 0]],\n             [5, [3, 3, 3, 3, 3, 0]]]},\n   [[[2, 3], [2, 4]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [2, 0, 4, 3, 0, 4, 4, 3]],\n             [2, [2, 0, 2, 3, 0, 3, 0, 3]],\n             [3, [2, 1, 0, 2, 0, 3, 3, 3]],\n             [4, [0, 0, 0, 3, 0, 3, 3, 3]],\n             [5, [3, 3, 2, 1, 0, 3, 0, 4]]]},\n   [[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [2, 3, 0, 4, 3, 1, 2, 2, 3]],\n             [2, [2, 3, 3, 4, 0, 1, 4, 0, 3]],\n             [3, [2, 3, 0, 4, 3, 1, 2, 2, 3]],\n             [4, [2, 3, 3, 2, 3, 1, 1, 2, 3]],\n             [5, [2, 3, 0, 4, 3, 1, 2, 2, 3]]]},\n   [[[1, 3], [1, 5], [2, 4], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 2, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 2]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 2]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [0, 1, 2, 0, 3, 4]],\n             [2, [4, 0, 2, 0, 3, 3]],\n             [3, [0, 0, 2, 0, 4, 4]],\n             [4, [2, 1, 4, 0, 3, 2]],\n             [5, [0, 0, 3, 3, 4, 2]]]},\n   [[[1, 2], [1, 3], [2, 3], [3, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [4, 3, 0, 0, 1, 2]],\n             [2, [4, 3, 0, 0, 1, 2]],\n             [3, [3, 3, 0, 0, 1, 2]],\n             [4, [4, 3, 0, 0, 1, 2]],\n             [5, [4, 0, 4, 1, 2, 2]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [0, 0, 3, 1, 2, 3, 4, 3]],\n             [2, [0, 0, 0, 4, 2, 0, 3, 4]],\n             [3, [3, 0, 0, 1, 2, 0, 4, 3]],\n             [4, [0, 3, 0, 0, 2, 4, 3, 2]],\n             [5, [1, 0, 3, 1, 1, 4, 0, 4]]]},\n   [[[1, 2], [1, 3], [1, 5], [2, 3]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [4, 3, 0, 0, 4, 4, 3, 2, 1]],\n             [2, [4, 1, 3, 0, 0, 0, 1, 4, 1]],\n             [3, [4, 1, 3, 0, 0, 0, 4, 0, 1]],\n             [4, [4, 4, 4, 0, 0, 4, 0, 1, 1]],\n             [5, [1, 2, 3, 0, 0, 0, 1, 1, 1]]]},\n   [[[2, 3], [2, 5], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 3, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 3]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 3]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [4, 3, 4, 3, 0, 4]],\n             [2, [4, 2, 3, 3, 0, 1]],\n             [3, [4, 2, 1, 3, 0, 1]],\n             [4, [4, 2, 3, 3, 2, 1]],\n             [5, [4, 4, 3, 3, 0, 0]]]},\n   [[[2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [3, 1, 4, 4, 2, 3]],\n             [2, [1, 4, 0, 2, 2, 3]],\n             [3, [3, 0, 4, 4, 2, 2]],\n             [4, [3, 1, 0, 4, 3, 3]],\n             [5, [4, 1, 4, 1, 3, 3]]]},\n   [[], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [3, 3, 2, 2, 0, 4, 4, 4]],\n             [2, [1, 3, 1, 1, 4, 0, 4, 1]],\n             [3, [3, 3, 1, 1, 0, 2, 1, 4]],\n             [4, [4, 0, 1, 1, 0, 4, 1, 4]],\n             [5, [3, 3, 1, 2, 0, 0, 1, 4]]]},\n   [[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 1, 3, 2, 2, 2, 4, 3, 2]],\n             [2, [3, 1, 3, 0, 2, 2, 4, 4, 3]],\n             [3, [1, 1, 4, 1, 2, 2, 4, 3, 2]],\n             [4, [1, 1, 3, 2, 2, 2, 4, 3, 2]],\n             [5, [1, 1, 2, 4, 2, 2, 2, 3, 1]]]},\n   [[[1, 3], [1, 4], [3, 4]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 4, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 4]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 4]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [3, 3, 2, 3, 0, 4]],\n             [2, [4, 3, 2, 3, 1, 0]],\n             [3, [1, 2, 2, 3, 3, 0]],\n             [4, [1, 3, 2, 3, 0, 0]],\n             [5, [1, 3, 4, 3, 4, 3]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [2, 1, 4, 2, 2, 4]],\n             [2, [3, 1, 4, 2, 2, 0]],\n             [3, [2, 1, 4, 2, 2, 4]],\n             [4, [3, 2, 4, 2, 2, 0]],\n             [5, [3, 1, 4, 4, 0, 0]]]},\n   [[[1, 3], [2, 4], [2, 5]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [1, 0, 0, 1, 3, 1, 4, 3]],\n             [2, [3, 2, 3, 1, 4, 4, 3, 3]],\n             [3, [1, 0, 0, 1, 4, 1, 4, 3]],\n             [4, [1, 0, 3, 2, 4, 3, 3, 3]],\n             [5, [4, 0, 0, 4, 1, 3, 1, 3]]]},\n   [[[1, 3], [1, 4], [2, 4], [3, 4]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 4, 1, 3, 1, 3, 1, 2, 4]],\n             [2, [0, 1, 4, 0, 4, 3, 1, 3, 0]],\n             [3, [1, 4, 1, 0, 4, 1, 3, 4, 3]],\n             [4, [1, 4, 3, 4, 4, 3, 1, 3, 3]],\n             [5, [1, 2, 3, 0, 4, 3, 1, 3, 4]]]},\n   [[[1, 3], [2, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 5, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 5]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 5]]]},\n   [[], 0.707]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"6ca43b0487f3cd9bf6eead3f89ccedf46fcad81589797a6d21b87557f339f4b9","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    b = x['b']\n    r = x['r']\n    sigs = x['sigs']\n    if any(len(sig) != b * r for ident, sig in sigs):\n        return 'invalid'\n    buckets = {}\n    for ident, sig in sigs:\n        for i in range(b):\n            key = (i, tuple(sig[i * r:(i + 1) * r]))\n            buckets.setdefault(key, []).append(ident)\n    pairs = set()\n    for members in buckets.values():\n        for u in members:\n            for v in members:\n                if u < v:\n                    pairs.add((u, v))\n    return [[list(p) for p in sorted(pairs)], round((1 / b) ** (1 / r), 3)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [4, 2, 3, 1, 0, 4]],\n             [2, [2, 1, 3, 1, 1, 4]],\n             [3, [2, 4, 3, 1, 2, 4]],\n             [4, [2, 1, 3, 1, 1, 4]],\n             [5, [2, 1, 1, 1, 2, 2]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [2, 1, 3, 1, 1, 3]],\n             [2, [2, 1, 3, 1, 4, 3]],\n             [3, [2, 1, 3, 1, 4, 4]],\n             [4, [1, 1, 2, 4, 0, 2]],\n             [5, [2, 1, 3, 1, 4, 4]]]},\n   [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [1, 2, 4, 0, 0, 1, 3, 4]],\n             [2, [0, 4, 4, 0, 1, 1, 3, 4]],\n             [3, [3, 1, 0, 3, 1, 3, 1, 2]],\n             [4, [1, 1, 4, 1, 4, 3, 3, 4]],\n             [5, [1, 4, 4, 3, 1, 3, 1, 3]]]},\n   [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 1, 1, 1, 0, 2, 1, 0, 4]],\n             [2, [3, 1, 1, 1, 0, 0, 3, 3, 3]],\n             [3, [1, 1, 3, 1, 0, 3, 3, 1, 2]],\n             [4, [2, 2, 1, 4, 0, 1, 2, 1, 2]],\n             [5, [0, 2, 1, 1, 0, 2, 3, 1, 2]]]},\n   [[[1, 5], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 1, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 1]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 1]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [0, 0, 2, 2, 3, 1]],\n             [2, [4, 2, 4, 2, 3, 1]],\n             [3, [0, 0, 2, 2, 3, 1]],\n             [4, [0, 0, 2, 2, 3, 1]],\n             [5, [1, 0, 2, 4, 4, 1]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 0, 1, 2, 4, 0]],\n             [2, [3, 1, 2, 2, 2, 0]],\n             [3, [3, 1, 2, 3, 4, 0]],\n             [4, [2, 1, 2, 2, 2, 0]],\n             [5, [3, 3, 3, 3, 3, 0]]]},\n   [[[2, 3], [2, 4]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [2, 0, 4, 3, 0, 4, 4, 3]],\n             [2, [2, 0, 2, 3, 0, 3, 0, 3]],\n             [3, [2, 1, 0, 2, 0, 3, 3, 3]],\n             [4, [0, 0, 0, 3, 0, 3, 3, 3]],\n             [5, [3, 3, 2, 1, 0, 3, 0, 4]]]},\n   [[[1, 2], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [2, 3, 0, 4, 3, 1, 2, 2, 3]],\n             [2, [2, 3, 3, 4, 0, 1, 4, 0, 3]],\n             [3, [2, 3, 0, 4, 3, 1, 2, 2, 3]],\n             [4, [2, 3, 3, 2, 3, 1, 1, 2, 3]],\n             [5, [2, 3, 0, 4, 3, 1, 2, 2, 3]]]},\n   [[[1, 3], [1, 5], [2, 4], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 2, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 2]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 2]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [0, 1, 2, 0, 3, 4]],\n             [2, [4, 0, 2, 0, 3, 3]],\n             [3, [0, 0, 2, 0, 4, 4]],\n             [4, [2, 1, 4, 0, 3, 2]],\n             [5, [0, 0, 3, 3, 4, 2]]]},\n   [[[1, 2], [1, 3], [2, 3], [3, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [4, 3, 0, 0, 1, 2]],\n             [2, [4, 3, 0, 0, 1, 2]],\n             [3, [3, 3, 0, 0, 1, 2]],\n             [4, [4, 3, 0, 0, 1, 2]],\n             [5, [4, 0, 4, 1, 2, 2]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [0, 0, 3, 1, 2, 3, 4, 3]],\n             [2, [0, 0, 0, 4, 2, 0, 3, 4]],\n             [3, [3, 0, 0, 1, 2, 0, 4, 3]],\n             [4, [0, 3, 0, 0, 2, 4, 3, 2]],\n             [5, [1, 0, 3, 1, 1, 4, 0, 4]]]},\n   [[[1, 2], [1, 3], [1, 5], [2, 3]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [4, 3, 0, 0, 4, 4, 3, 2, 1]],\n             [2, [4, 1, 3, 0, 0, 0, 1, 4, 1]],\n             [3, [4, 1, 3, 0, 0, 0, 4, 0, 1]],\n             [4, [4, 4, 4, 0, 0, 4, 0, 1, 1]],\n             [5, [1, 2, 3, 0, 0, 0, 1, 1, 1]]]},\n   [[[2, 3], [2, 5], [3, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 3, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 3]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 3]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [4, 3, 4, 3, 0, 4]],\n             [2, [4, 2, 3, 3, 0, 1]],\n             [3, [4, 2, 1, 3, 0, 1]],\n             [4, [4, 2, 3, 3, 2, 1]],\n             [5, [4, 4, 3, 3, 0, 0]]]},\n   [[[2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [3, 1, 4, 4, 2, 3]],\n             [2, [1, 4, 0, 2, 2, 3]],\n             [3, [3, 0, 4, 4, 2, 2]],\n             [4, [3, 1, 0, 4, 3, 3]],\n             [5, [4, 1, 4, 1, 3, 3]]]},\n   [[], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [3, 3, 2, 2, 0, 4, 4, 4]],\n             [2, [1, 3, 1, 1, 4, 0, 4, 1]],\n             [3, [3, 3, 1, 1, 0, 2, 1, 4]],\n             [4, [4, 0, 1, 1, 0, 4, 1, 4]],\n             [5, [3, 3, 1, 2, 0, 0, 1, 4]]]},\n   [[[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 1, 3, 2, 2, 2, 4, 3, 2]],\n             [2, [3, 1, 3, 0, 2, 2, 4, 4, 3]],\n             [3, [1, 1, 4, 1, 2, 2, 4, 3, 2]],\n             [4, [1, 1, 3, 2, 2, 2, 4, 3, 2]],\n             [5, [1, 1, 2, 4, 2, 2, 2, 3, 1]]]},\n   [[[1, 3], [1, 4], [3, 4]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 4, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 4]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 4]]]},\n   [[], 0.707]]],\n [['bands 0 b=3 r=2',\n   {'b': 3,\n    'r': 2,\n    'sigs': [[1, [3, 3, 2, 3, 0, 4]],\n             [2, [4, 3, 2, 3, 1, 0]],\n             [3, [1, 2, 2, 3, 3, 0]],\n             [4, [1, 3, 2, 3, 0, 0]],\n             [5, [1, 3, 4, 3, 4, 3]]]},\n   [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [4, 5]], 0.577]],\n  ['bands 1 b=2 r=3',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [2, 1, 4, 2, 2, 4]],\n             [2, [3, 1, 4, 2, 2, 0]],\n             [3, [2, 1, 4, 2, 2, 4]],\n             [4, [3, 2, 4, 2, 2, 0]],\n             [5, [3, 1, 4, 4, 0, 0]]]},\n   [[[1, 3], [2, 4], [2, 5]], 0.794]],\n  ['bands 2 b=4 r=2',\n   {'b': 4,\n    'r': 2,\n    'sigs': [[1, [1, 0, 0, 1, 3, 1, 4, 3]],\n             [2, [3, 2, 3, 1, 4, 4, 3, 3]],\n             [3, [1, 0, 0, 1, 4, 1, 4, 3]],\n             [4, [1, 0, 3, 2, 4, 3, 3, 3]],\n             [5, [4, 0, 0, 4, 1, 3, 1, 3]]]},\n   [[[1, 3], [1, 4], [2, 4], [3, 4]], 0.5]],\n  ['bands 3 b=3 r=3',\n   {'b': 3,\n    'r': 3,\n    'sigs': [[1, [1, 4, 1, 3, 1, 3, 1, 2, 4]],\n             [2, [0, 1, 4, 0, 4, 3, 1, 3, 0]],\n             [3, [1, 4, 1, 0, 4, 1, 3, 4, 3]],\n             [4, [1, 4, 3, 4, 4, 3, 1, 3, 3]],\n             [5, [1, 2, 3, 0, 4, 3, 1, 3, 4]]]},\n   [[[1, 3], [2, 5]], 0.693]],\n  ['same values in different bands',\n   {'b': 2, 'r': 2, 'sigs': [[1, [7, 7, 1, 2]], [2, [3, 4, 7, 7]], [3, [5, 5, 6, 6]]]},\n   [[], 0.707]],\n  ['overlong signature',\n   {'b': 2, 'r': 2, 'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 2, 3, 4]]]},\n   'invalid'],\n  ['interleaved agreement',\n   {'b': 2,\n    'r': 3,\n    'sigs': [[1, [1, 2, 3, 4, 5, 6]], [2, [1, 9, 3, 9, 5, 9]], [3, [1, 2, 3, 0, 0, 5]]]},\n   [[[1, 3]], 0.794]],\n  ['equal sums differ',\n   {'b': 2, 'r': 2, 'sigs': [[4, [1, 3, 8, 8]], [9, [2, 2, 9, 9]], [5, [3, 1, 0, 5]]]},\n   [[], 0.707]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-lsh-banding-band-identity","generated_at":"2026-09-29T14:48:45.445574+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Locality-sensitive hashing prunes all-pairs similarity search; banding mistakes either flood the verifier with false candidates or silently miss near-duplicates.","repair":"Include the band index in each bucket key.","root_cause":"The bucket key is only the band contents, so identical tuples in different bands collide.","sha256":"353cea99521401a7459e14cb1148d9e40259554268af9e2a4a964201dce2cd0d","title":"MinHash LSH banding: band key omits the band index · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":42.312,"exit_code":1,"observations":[{"actual":[[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]],0.577],"check":"bands 0 b=3 r=2","expected":[[[1,2],[1,3],[1,4],[2,3],[2,4],[2,5],[3,4],[4,5]],0.577],"passed":false},{"actual":[[[1,2],[1,3],[1,5],[2,3],[2,5],[3,5]],0.794],"check":"bands 1 b=2 r=3","expected":[[[1,2],[1,3],[1,5],[2,3],[2,5],[3,5]],0.794],"passed":true},{"actual":[[[1,2],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]],0.5],"check":"bands 2 b=4 r=2","expected":[[[1,2],[1,4],[2,4],[3,5]],0.5],"passed":false},{"actual":[[[1,4],[1,5],[2,3],[2,4],[3,4],[3,5]],0.693],"check":"bands 3 b=3 r=3","expected":[[[1,5],[3,5]],0.693],"passed":false},{"actual":[[],0.707],"check":"same values in different bands","expected":[[],0.707],"passed":true},{"actual":"invalid","check":"overlong signature","expected":"invalid","passed":true},{"actual":[[[1,3]],0.794],"check":"interleaved agreement","expected":[[[1,3]],0.794],"passed":true},{"actual":[[[4,5],[4,9],[5,9]],0.707],"check":"equal sums differ","expected":[[],0.707],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"bands 0 b=3 r=2\", \"actual\": [[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.577], \"expected\": [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577], \"passed\": false}, {\"check\": \"bands 1 b=2 r=3\", \"actual\": [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794], \"expected\": [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794], \"passed\": true}, {\"check\": \"bands 2 b=4 r=2\", \"actual\": [[[1, 2], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]], 0.5], \"expected\": [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5], \"passed\": false}, {\"check\": \"bands 3 b=3 r=3\", \"actual\": [[[1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5]], 0.693], \"expected\": [[[1, 5], [3, 5]], 0.693], \"passed\": false}, {\"check\": \"same values in different bands\", \"actual\": [[], 0.707], \"expected\": [[], 0.707], \"passed\": true}, {\"check\": \"overlong signature\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"interleaved agreement\", \"actual\": [[[1, 3]], 0.794], \"expected\": [[[1, 3]], 0.794], \"passed\": true}, {\"check\": \"equal sums differ\", \"actual\": [[[4, 5], [4, 9], [5, 9]], 0.707], \"expected\": [[], 0.707], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":42.157,"exit_code":1,"observations":[{"actual":[[[1,2],[1,3],[1,4],[2,3],[2,4],[2,5],[3,4],[4,5]],0.577],"check":"bands 0 b=3 r=2","expected":[[[1,2],[1,3],[1,4],[2,3],[2,4],[2,5],[3,4],[4,5]],0.577],"passed":true},{"actual":[[[1,2],[1,3],[1,5],[2,3],[2,5],[3,5]],0.794],"check":"bands 1 b=2 r=3","expected":[[[1,2],[1,3],[1,5],[2,3],[2,5],[3,5]],0.794],"passed":true},{"actual":[[[1,2],[1,3],[1,4],[2,4],[3,5],[4,5]],0.5],"check":"bands 2 b=4 r=2","expected":[[[1,2],[1,4],[2,4],[3,5]],0.5],"passed":false},{"actual":[[[1,5],[3,5]],0.693],"check":"bands 3 b=3 r=3","expected":[[[1,5],[3,5]],0.693],"passed":true},{"actual":[[[1,2]],0.707],"check":"same values in different bands","expected":[[],0.707],"passed":false},{"actual":"invalid","check":"overlong signature","expected":"invalid","passed":true},{"actual":[[[1,3]],0.794],"check":"interleaved agreement","expected":[[[1,3]],0.794],"passed":true},{"actual":[[],0.707],"check":"equal sums differ","expected":[[],0.707],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"bands 0 b=3 r=2\", \"actual\": [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577], \"expected\": [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577], \"passed\": true}, {\"check\": \"bands 1 b=2 r=3\", \"actual\": [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794], \"expected\": [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794], \"passed\": true}, {\"check\": \"bands 2 b=4 r=2\", \"actual\": [[[1, 2], [1, 3], [1, 4], [2, 4], [3, 5], [4, 5]], 0.5], \"expected\": [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5], \"passed\": false}, {\"check\": \"bands 3 b=3 r=3\", \"actual\": [[[1, 5], [3, 5]], 0.693], \"expected\": [[[1, 5], [3, 5]], 0.693], \"passed\": true}, {\"check\": \"same values in different bands\", \"actual\": [[[1, 2]], 0.707], \"expected\": [[], 0.707], \"passed\": false}, {\"check\": \"overlong signature\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"interleaved agreement\", \"actual\": [[[1, 3]], 0.794], \"expected\": [[[1, 3]], 0.794], \"passed\": true}, {\"check\": \"equal sums differ\", \"actual\": [[], 0.707], \"expected\": [[], 0.707], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":38.932,"exit_code":0,"observations":[{"actual":[[[1,2],[1,3],[1,4],[2,3],[2,4],[2,5],[3,4],[4,5]],0.577],"check":"bands 0 b=3 r=2","expected":[[[1,2],[1,3],[1,4],[2,3],[2,4],[2,5],[3,4],[4,5]],0.577],"passed":true},{"actual":[[[1,2],[1,3],[1,5],[2,3],[2,5],[3,5]],0.794],"check":"bands 1 b=2 r=3","expected":[[[1,2],[1,3],[1,5],[2,3],[2,5],[3,5]],0.794],"passed":true},{"actual":[[[1,2],[1,4],[2,4],[3,5]],0.5],"check":"bands 2 b=4 r=2","expected":[[[1,2],[1,4],[2,4],[3,5]],0.5],"passed":true},{"actual":[[[1,5],[3,5]],0.693],"check":"bands 3 b=3 r=3","expected":[[[1,5],[3,5]],0.693],"passed":true},{"actual":[[],0.707],"check":"same values in different bands","expected":[[],0.707],"passed":true},{"actual":"invalid","check":"overlong signature","expected":"invalid","passed":true},{"actual":[[[1,3]],0.794],"check":"interleaved agreement","expected":[[[1,3]],0.794],"passed":true},{"actual":[[],0.707],"check":"equal sums differ","expected":[[],0.707],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"bands 0 b=3 r=2\", \"actual\": [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577], \"expected\": [[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]], 0.577], \"passed\": true}, {\"check\": \"bands 1 b=2 r=3\", \"actual\": [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794], \"expected\": [[[1, 2], [1, 3], [1, 5], [2, 3], [2, 5], [3, 5]], 0.794], \"passed\": true}, {\"check\": \"bands 2 b=4 r=2\", \"actual\": [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5], \"expected\": [[[1, 2], [1, 4], [2, 4], [3, 5]], 0.5], \"passed\": true}, {\"check\": \"bands 3 b=3 r=3\", \"actual\": [[[1, 5], [3, 5]], 0.693], \"expected\": [[[1, 5], [3, 5]], 0.693], \"passed\": true}, {\"check\": \"same values in different bands\", \"actual\": [[], 0.707], \"expected\": [[], 0.707], \"passed\": true}, {\"check\": \"overlong signature\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"interleaved agreement\", \"actual\": [[[1, 3]], 0.794], \"expected\": [[[1, 3]], 0.794], \"passed\": true}, {\"check\": \"equal sums differ\", \"actual\": [[], 0.707], \"expected\": [[], 0.707], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}