FA-72206 / Error-correcting codes / Open access

LT peeling stops after one pass · case 01

Symbols that become degree one late in the list are never used.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The decoder makes a single pass over the symbols instead of repeating until no progress.

VERIFIED REPAIR

Loop until a whole pass resolves nothing.

Unsuccessful approach: Two fixed passes still stop short on longer dependency chains.

Case contract

Peeling (belief-propagation) decoder for an LT fountain code over bytes. symbols is a list of [neighbour indices, XOR of those source symbols]. Repeatedly find an encoded symbol with exactly one unresolved neighbour, resolve it as the value XOR all resolved neighbours, and continue until a full pass makes no progress. Return the k source values with None for unresolved ones.

Why this case matters

Broadcast and storage systems use fountain codes; peeling must continue as long as new degree-one symbols appear.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(symbols, k):
    src = [None] * k
    for _ in range(1):
        changed = False
        for nbrs, val in symbols:
            unknown = [i for i in nbrs if src[i] is None]
            if len(unknown) != 1:
                continue
            x = val
            for i in nbrs:
                if src[i] is not None:
                    x ^= src[i]
            src[unknown[0]] = x
            changed = True
    return src
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]', [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3], [87, 225, 186]], ['regression [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]], ['control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]', [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3], [9, None, None]]], [['regression [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]]...', [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]], 4], [100, 106, 96, 151]], ['regression [[[[0], 17], [[3, 4], 215], [[0, 3], 193], [[1, 3, 4], 154], [[1, 4...', [[[[0], 17], [[3, 4], 215], [[0, 3], 193], [[1, 3, 4], 154], [[1, 4], 74], [[4], 7]], 5], [17, 77, None, 208, 7]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]], [['regression [[[[0, 1], 249], [[0, 1], 249], [[0, 1, 2], 202], [[0], 87]], 3]', [[[[0, 1], 249], [[0, 1], 249], [[0, 1, 2], 202], [[0], 87]], 3], [87, 174, 51]], ['regression [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]], ['control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]', [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3], [9, None, None]]], [['regression [[[[1, 2], 6], [[0, 1], 3], [[2], 4]], 3]', [[[[1, 2], 6], [[0, 1], 3], [[2], 4]], 3], [1, 2, 4]], ['regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]', [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3], [87, 225, 186]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]], [['regression [[[[0, 1, 5], 194], [[0, 4], 132], [[0, 1], 133], [[3, 5], 70], [[0...', [[[[0, 1, 5], 194], [[0, 4], 132], [[0, 1], 133], [[3, 5], 70], [[0, 2, 4], 67], [[1, 2, 4], 198], [[0], 59], [[5], 71]], 6], [59, 190, 199, 1, 191, 71]], ['regression [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]]...', [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]], 4], [100, 106, 96, 151]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]]]
for label, args, expected in fixtures[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
regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]	`[87, None, 186]`	`[87, 225, 186]`	Failed
regression [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...	`[None, None, 28, None, None]`	`[249, 52, 28, 13, 241]`	Failed
partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...	`[7, None, None, 251, 144, None, 49]`	`[7, 222, 38, 251, 144, 7, 49]`	Failed
control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]	`[93, 110, 53, 40]`	`[93, 110, 53, 40]`	Passed
control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...	`[114, 137, None, None, 166]`	`[114, 137, None, None, 166]`	Passed
control [[[[0, 1], 1]], 2]	`[None, None]`	`[None, None]`	Passed
control [[], 2]	`[None, None]`	`[None, None]`	Passed
control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]	`[9, None, None]`	`[9, None, None]`	Passed

SHA-256 / 7ac56736967204a7fa408b043f004b0f71c7db5d36f98e5c4a98f0fe79264749

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(symbols, k):
    src = [None] * k
    for _ in range(2):
        changed = False
        for nbrs, val in symbols:
            unknown = [i for i in nbrs if src[i] is None]
            if len(unknown) != 1:
                continue
            x = val
            for i in nbrs:
                if src[i] is not None:
                    x ^= src[i]
            src[unknown[0]] = x
            changed = True
    return src
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]', [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3], [87, 225, 186]], ['regression [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]], ['control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]', [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3], [9, None, None]]], [['regression [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]]...', [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]], 4], [100, 106, 96, 151]], ['regression [[[[0], 17], [[3, 4], 215], [[0, 3], 193], [[1, 3, 4], 154], [[1, 4...', [[[[0], 17], [[3, 4], 215], [[0, 3], 193], [[1, 3, 4], 154], [[1, 4], 74], [[4], 7]], 5], [17, 77, None, 208, 7]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]], [['regression [[[[0, 1], 249], [[0, 1], 249], [[0, 1, 2], 202], [[0], 87]], 3]', [[[[0, 1], 249], [[0, 1], 249], [[0, 1, 2], 202], [[0], 87]], 3], [87, 174, 51]], ['regression [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]], ['control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]', [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3], [9, None, None]]], [['regression [[[[1, 2], 6], [[0, 1], 3], [[2], 4]], 3]', [[[[1, 2], 6], [[0, 1], 3], [[2], 4]], 3], [1, 2, 4]], ['regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]', [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3], [87, 225, 186]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]], [['regression [[[[0, 1, 5], 194], [[0, 4], 132], [[0, 1], 133], [[3, 5], 70], [[0...', [[[[0, 1, 5], 194], [[0, 4], 132], [[0, 1], 133], [[3, 5], 70], [[0, 2, 4], 67], [[1, 2, 4], 198], [[0], 59], [[5], 71]], 6], [59, 190, 199, 1, 191, 71]], ['regression [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]]...', [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]], 4], [100, 106, 96, 151]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]]]
for label, args, expected in fixtures[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
regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]	`[87, 225, 186]`	`[87, 225, 186]`	Passed
regression [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...	`[None, 52, 28, None, 241]`	`[249, 52, 28, 13, 241]`	Failed
partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...	`[7, None, 38, 251, 144, None, 49]`	`[7, 222, 38, 251, 144, 7, 49]`	Failed
control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]	`[93, 110, 53, 40]`	`[93, 110, 53, 40]`	Passed
control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...	`[114, 137, None, None, 166]`	`[114, 137, None, None, 166]`	Passed
control [[[[0, 1], 1]], 2]	`[None, None]`	`[None, None]`	Passed
control [[], 2]	`[None, None]`	`[None, None]`	Passed
control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]	`[9, None, None]`	`[9, None, None]`	Passed

SHA-256 / 6e2e42c09aa25430a7460ee1a89ed00c53895eca38c105c321ec94a524f8c3e4

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(symbols, k):
    src = [None] * k
    changed = True
    while changed:
        changed = False
        for nbrs, val in symbols:
            unknown = [i for i in nbrs if src[i] is None]
            if len(unknown) != 1:
                continue
            x = val
            for i in nbrs:
                if src[i] is not None:
                    x ^= src[i]
            src[unknown[0]] = x
            changed = True
    return src
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]', [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3], [87, 225, 186]], ['regression [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]], ['control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]', [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3], [9, None, None]]], [['regression [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]]...', [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]], 4], [100, 106, 96, 151]], ['regression [[[[0], 17], [[3, 4], 215], [[0, 3], 193], [[1, 3, 4], 154], [[1, 4...', [[[[0], 17], [[3, 4], 215], [[0, 3], 193], [[1, 3, 4], 154], [[1, 4], 74], [[4], 7]], 5], [17, 77, None, 208, 7]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]], [['regression [[[[0, 1], 249], [[0, 1], 249], [[0, 1, 2], 202], [[0], 87]], 3]', [[[[0, 1], 249], [[0, 1], 249], [[0, 1, 2], 202], [[0], 87]], 3], [87, 174, 51]], ['regression [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]], ['control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]', [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3], [9, None, None]]], [['regression [[[[1, 2], 6], [[0, 1], 3], [[2], 4]], 3]', [[[[1, 2], 6], [[0, 1], 3], [[2], 4]], 3], [1, 2, 4]], ['regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]', [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3], [87, 225, 186]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]], [['regression [[[[0, 1, 5], 194], [[0, 4], 132], [[0, 1], 133], [[3, 5], 70], [[0...', [[[[0, 1, 5], 194], [[0, 4], 132], [[0, 1], 133], [[3, 5], 70], [[0, 2, 4], 67], [[1, 2, 4], 198], [[0], 59], [[5], 71]], 6], [59, 190, 199, 1, 191, 71]], ['regression [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]]...', [[[[3], 151], [[1, 3], 253], [[0, 2], 4], [[1], 106], [[0, 1], 14]], 4], [100, 106, 96, 151]], ['partial-repair [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...', [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2, 4], 217]], 5], [249, 52, 28, 13, 241]], ['partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...', [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], [[3], 251], [[0, 2, 4], 177], [[6], 49], [[0, 6], 54]], 7], [7, 222, 38, 251, 144, 7, 49]], ['control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]', [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4], [93, 110, 53, 40]], ['control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...', [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], 114]], 5], [114, 137, None, None, 166]], ['control [[[[0, 1], 1]], 2]', [[[[0, 1], 1]], 2], [None, None]], ['control [[], 2]', [[], 2], [None, None]]]]
for label, args, expected in fixtures[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
regression [[[[0, 1, 2], 12], [[2], 186], [[0, 2], 237]], 3]	`[87, 225, 186]`	`[87, 225, 186]`	Passed
regression [[[[2, 4], 237], [[0, 1, 3], 192], [[1, 3], 57], [[2], 28], [[1, 2,...	`[249, 52, 28, 13, 241]`	`[249, 52, 28, 13, 241]`	Passed
partial-repair [[[[0, 1, 5], 222], [[4], 144], [[2, 5, 6], 16], [[1, 2, 4], 104], ...	`[7, 222, 38, 251, 144, 7, 49]`	`[7, 222, 38, 251, 144, 7, 49]`	Passed
control [[[[1], 110], [[3], 40], [[0, 2, 3], 64], [[2, 3], 29], [[0], 93]], 4]	`[93, 110, 53, 40]`	`[93, 110, 53, 40]`	Passed
control [[[[0, 4], 212], [[0], 114], [[0, 4], 212], [[0, 1, 4], 93], [[0], ...	`[114, 137, None, None, 166]`	`[114, 137, None, None, 166]`	Passed
control [[[[0, 1], 1]], 2]	`[None, None]`	`[None, None]`	Passed
control [[], 2]	`[None, None]`	`[None, None]`	Passed
control [[[[0], 9], [[0, 1, 2], 1], [[1, 2], 3]], 3]	`[9, None, None]`	`[9, None, None]`	Passed

SHA-256 / f375c409d2f57a320e23b7593811aaa780cabb710ca0fa6bdca12e5500777c12

Verification & scope

A deterministic, bounded teaching model of the named code under the stated contract; not a production codec. 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:36.522872+00:00.

Case digest / 86134c28c1e741115747106fb59c857549b653253a67e8e8c5de2e8268f50428