FAILURE MAP
← Case archive

FA-71941 / Error-correcting codes / Open access

Viterbi reports the best metric of any state · case 01

The reported path metric understates the errors on the terminated path.

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

ROOT CAUSE

The metric is min(metric) even though the decoded path is the state-0 survivor.

VERIFIED REPAIR

Report metric[0], the metric of the survivor actually returned.

Unsuccessful approach: Returning the survivor of the best state instead abandons trellis termination.

Case contract

Hard-decision Viterbi decoder for the terminated K=3 (7,5) code (outputs g=7 then g=5 per step, two zero tail bits). Branch metric is the Hamming distance between the received pair and the branch output. Survivors keep the first strictly better candidate (states in ascending order, input 0 before 1). Decoding ends in state 0 and the two tail bits are removed. Return [decoded bits, final path metric]; odd or too-short input returns None.

Why this case matters

Receivers recover convolutionally coded frames by maximum-likelihood trellis search.

1 / The failure

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

N = 1
observations = []
def solve(r):
    if len(r) % 2 or len(r) < 4:
        return None
    INF = 10 ** 9
    metric = [0, INF, INF, INF]
    paths = [[], [], [], []]
    for t in range(len(r) // 2):
        y0, y1 = r[2 * t], r[2 * t + 1]
        new_m = [INF] * 4
        new_p = [None] * 4
        for st in range(4):
            if metric[st] >= INF:
                continue
            for b in (0, 1):
                reg = (b << 2) | st
                o0 = bin(reg & 7).count('1') % 2
                o1 = bin(reg & 5).count('1') % 2
                ns = reg >> 1
                m = metric[st] + (o0 != y0) + (o1 != y1)
                if m < new_m[ns]:
                    new_m[ns] = m
                    new_p[ns] = paths[st] + [b]
        metric, paths = new_m, new_p
    return [paths[0][:-2], min(metric)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]]', [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]], [[1, 1, 0], 2]], ['regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]], [[0, 1, 0, 0], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]], [[1, 1, 0], 0]], ['control [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]]', [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]], [[1, 1, 0], 1]], ['control [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]]', [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]], [[1, 1, 0], 2]], ['control [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]], [[0, 1, 0, 0], 0]], ['control [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]]', [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]], [[0, 1, 0, 0], 1]], ['control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]]', [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]], [[0, 1, 0, 0], 2]]], [['regression [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]], [[1, 1, 0, 0, 0, 0], 2]], ['regression [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]]', [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]], [[1, 0, 0, 0, 1, 1, 1], 2]], ['control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]]', [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]], [[0, 1, 0, 0], 2]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]], [[1, 0, 1, 0, 0], 0]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]], [[1, 0, 1, 0, 0], 1]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]], [[1, 0, 1, 0, 0], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 1, 0, 0, 0, 0], 0]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], [[1, 1, 0, 0, 0, 0], 1]]], [['regression [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]]', [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]], [[0, 1, 0, 1, 1], 2]], ['regression [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]]', [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]], [[0, 0, 0, 1, 0, 1], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], [[1, 1, 0, 0, 0, 0], 1]], ['control [[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]', [[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 1, 0, 0, 0, 0], 2]], ['control [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 0]], ['control [[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 1]], ['control [[1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 2]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 0]]], [['regression [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]], [[0, 1, 0, 1], 2]], ['regression [[1, 1, 1, 0]]', [[1, 1, 1, 0]], [[], 3]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 0]], ['control [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 1]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0]], [[0, 0, 0, 0, 0, 0, 1, 1], 2]], ['control [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 0]], ['control [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 1]], ['control [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 2]]], [['regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]], [[0, 1, 0, 0], 2]], ['regression [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]], [[1, 0, 1, 0, 0], 2]], ['control [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 2]], ['control [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 0]], ['control [[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 1]], ['control [[0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 2]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[1, 0, 1, 0, 0, 0, 1, 0, 1], 0]], ['control [[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[1, 0, 1, 0, 0, 0, 1, 0, 1], 1]]]]
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 fixtureActualExpectedOutcome
regression [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]][[1, 1, 0], 1][[1, 1, 0], 2]Failed
regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]][[0, 1, 0, 0], 1][[0, 1, 0, 0], 2]Failed
control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]][[1, 1, 0], 0][[1, 1, 0], 0]Passed
control [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]][[1, 1, 0], 1][[1, 1, 0], 1]Passed
control [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]][[1, 1, 0], 2][[1, 1, 0], 2]Passed
control [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]][[0, 1, 0, 0], 0][[0, 1, 0, 0], 0]Passed
control [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]][[0, 1, 0, 0], 1][[0, 1, 0, 0], 1]Passed
control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]][[0, 1, 0, 0], 2][[0, 1, 0, 0], 2]Passed

SHA-256 / c8c8c5da1b3f67ffd6813f5157edb835c434f577ac0a37bd7e73a53ed800a75a

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(r):
    if len(r) % 2 or len(r) < 4:
        return None
    INF = 10 ** 9
    metric = [0, INF, INF, INF]
    paths = [[], [], [], []]
    for t in range(len(r) // 2):
        y0, y1 = r[2 * t], r[2 * t + 1]
        new_m = [INF] * 4
        new_p = [None] * 4
        for st in range(4):
            if metric[st] >= INF:
                continue
            for b in (0, 1):
                reg = (b << 2) | st
                o0 = bin(reg & 7).count('1') % 2
                o1 = bin(reg & 5).count('1') % 2
                ns = reg >> 1
                m = metric[st] + (o0 != y0) + (o1 != y1)
                if m < new_m[ns]:
                    new_m[ns] = m
                    new_p[ns] = paths[st] + [b]
        metric, paths = new_m, new_p
    best = metric.index(min(metric))
    return [paths[best][:-2], metric[best]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]]', [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]], [[1, 1, 0], 2]], ['regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]], [[0, 1, 0, 0], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]], [[1, 1, 0], 0]], ['control [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]]', [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]], [[1, 1, 0], 1]], ['control [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]]', [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]], [[1, 1, 0], 2]], ['control [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]], [[0, 1, 0, 0], 0]], ['control [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]]', [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]], [[0, 1, 0, 0], 1]], ['control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]]', [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]], [[0, 1, 0, 0], 2]]], [['regression [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]], [[1, 1, 0, 0, 0, 0], 2]], ['regression [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]]', [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]], [[1, 0, 0, 0, 1, 1, 1], 2]], ['control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]]', [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]], [[0, 1, 0, 0], 2]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]], [[1, 0, 1, 0, 0], 0]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]], [[1, 0, 1, 0, 0], 1]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]], [[1, 0, 1, 0, 0], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 1, 0, 0, 0, 0], 0]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], [[1, 1, 0, 0, 0, 0], 1]]], [['regression [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]]', [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]], [[0, 1, 0, 1, 1], 2]], ['regression [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]]', [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]], [[0, 0, 0, 1, 0, 1], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], [[1, 1, 0, 0, 0, 0], 1]], ['control [[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]', [[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 1, 0, 0, 0, 0], 2]], ['control [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 0]], ['control [[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 1]], ['control [[1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 2]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 0]]], [['regression [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]], [[0, 1, 0, 1], 2]], ['regression [[1, 1, 1, 0]]', [[1, 1, 1, 0]], [[], 3]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 0]], ['control [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 1]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0]], [[0, 0, 0, 0, 0, 0, 1, 1], 2]], ['control [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 0]], ['control [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 1]], ['control [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 2]]], [['regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]], [[0, 1, 0, 0], 2]], ['regression [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]], [[1, 0, 1, 0, 0], 2]], ['control [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 2]], ['control [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 0]], ['control [[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 1]], ['control [[0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 2]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[1, 0, 1, 0, 0, 0, 1, 0, 1], 0]], ['control [[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[1, 0, 1, 0, 0, 0, 1, 0, 1], 1]]]]
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 fixtureActualExpectedOutcome
regression [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]][[1, 1, 0], 1][[1, 1, 0], 2]Failed
regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]][[0, 1, 0, 0], 1][[0, 1, 0, 0], 2]Failed
control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]][[1, 1, 0], 0][[1, 1, 0], 0]Passed
control [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]][[1, 1, 0], 1][[1, 1, 0], 1]Passed
control [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]][[1, 1, 0], 2][[1, 1, 0], 2]Passed
control [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]][[0, 1, 0, 0], 0][[0, 1, 0, 0], 0]Passed
control [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]][[0, 1, 0, 0], 1][[0, 1, 0, 0], 1]Passed
control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]][[0, 1, 0, 0], 2][[0, 1, 0, 0], 2]Passed

SHA-256 / 14051c48d8dffc72d8b58b528988570627222e6e59f1f955594852343fd54899

3 / The verified repair

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

N = 1
observations = []
def solve(r):
    if len(r) % 2 or len(r) < 4:
        return None
    INF = 10 ** 9
    metric = [0, INF, INF, INF]
    paths = [[], [], [], []]
    for t in range(len(r) // 2):
        y0, y1 = r[2 * t], r[2 * t + 1]
        new_m = [INF] * 4
        new_p = [None] * 4
        for st in range(4):
            if metric[st] >= INF:
                continue
            for b in (0, 1):
                reg = (b << 2) | st
                o0 = bin(reg & 7).count('1') % 2
                o1 = bin(reg & 5).count('1') % 2
                ns = reg >> 1
                m = metric[st] + (o0 != y0) + (o1 != y1)
                if m < new_m[ns]:
                    new_m[ns] = m
                    new_p[ns] = paths[st] + [b]
        metric, paths = new_m, new_p
    return [paths[0][:-2], metric[0]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]]', [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]], [[1, 1, 0], 2]], ['regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]], [[0, 1, 0, 0], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]], [[1, 1, 0], 0]], ['control [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]]', [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]], [[1, 1, 0], 1]], ['control [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]]', [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]], [[1, 1, 0], 2]], ['control [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]], [[0, 1, 0, 0], 0]], ['control [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]]', [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]], [[0, 1, 0, 0], 1]], ['control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]]', [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]], [[0, 1, 0, 0], 2]]], [['regression [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]], [[1, 1, 0, 0, 0, 0], 2]], ['regression [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]]', [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]], [[1, 0, 0, 0, 1, 1, 1], 2]], ['control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]]', [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]], [[0, 1, 0, 0], 2]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]], [[1, 0, 1, 0, 0], 0]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]], [[1, 0, 1, 0, 0], 1]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]]', [[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0]], [[1, 0, 1, 0, 0], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 1, 0, 0, 0, 0], 0]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], [[1, 1, 0, 0, 0, 0], 1]]], [['regression [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]]', [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]], [[0, 1, 0, 1, 1], 2]], ['regression [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]]', [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]], [[0, 0, 0, 1, 0, 1], 2]], ['control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]]', [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], [[1, 1, 0, 0, 0, 0], 1]], ['control [[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]', [[1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 1, 0, 0, 0, 0], 2]], ['control [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 0]], ['control [[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 1]], ['control [[1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]]', [[1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]], [[1, 0, 0, 0, 1, 1, 1], 2]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 0]]], [['regression [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]]', [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]], [[0, 1, 0, 1], 2]], ['regression [[1, 1, 1, 0]]', [[1, 1, 1, 0]], [[], 3]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 0]], ['control [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]]', [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]], [[0, 0, 0, 0, 0, 0, 1, 1], 1]], ['control [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0]]', [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0]], [[0, 0, 0, 0, 0, 0, 1, 1], 2]], ['control [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 0]], ['control [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 1]], ['control [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 2]]], [['regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]]', [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]], [[0, 1, 0, 0], 2]], ['regression [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]], [[1, 0, 1, 0, 0], 2]], ['control [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]]', [[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1]], [[0, 1, 0, 1, 1], 2]], ['control [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 0]], ['control [[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 1]], ['control [[0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]]', [[0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]], [[0, 0, 0, 1, 0, 1], 2]], ['control [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[1, 0, 1, 0, 0, 0, 1, 0, 1], 0]], ['control [[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]]', [[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1]], [[1, 0, 1, 0, 0, 0, 1, 0, 1], 1]]]]
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 fixtureActualExpectedOutcome
regression [[1, 1, 0, 1, 0, 1, 1, 0, 0, 1]][[1, 1, 0], 2][[1, 1, 0], 2]Passed
regression [[0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]][[0, 1, 0, 0], 2][[0, 1, 0, 0], 2]Passed
control [[1, 1, 0, 1, 0, 1, 1, 1, 0, 0]][[1, 1, 0], 0][[1, 1, 0], 0]Passed
control [[1, 1, 0, 0, 0, 1, 1, 1, 0, 0]][[1, 1, 0], 1][[1, 1, 0], 1]Passed
control [[0, 1, 0, 1, 0, 1, 1, 1, 0, 1]][[1, 1, 0], 2][[1, 1, 0], 2]Passed
control [[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]][[0, 1, 0, 0], 0][[0, 1, 0, 0], 0]Passed
control [[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]][[0, 1, 0, 0], 1][[0, 1, 0, 0], 1]Passed
control [[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]][[0, 1, 0, 0], 2][[0, 1, 0, 0], 2]Passed

SHA-256 / 29ff94e9899ef12ca9ef3da4fd9e3e3e83ff5ebcf61ae53eec30a13d81948dd3

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:34.072957+00:00.

Case digest / 1fbcf5e7f7a6d7eab2046490c4852eb7e4ac837ee362f1d3062d4093dec1c23a