FA-46091 / Bounded deques / Open access

Deque coalescing replaces a repeated run length with one · case 01

Deque coalescing replaces a repeated run length with one.

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

ROOT CAUSE

Deque coalescing replaces a repeated run length with one.

VERIFIED REPAIR

Restore the documented run increment invariant in adjacent-coalesce.

Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.

Case contract

Coalesce adjacent equal deque payloads into [payload,run length] descriptors. Preserve non-adjacent equal runs and report cumulative exclusive run ends.

Why this case matters

Controlled bounded deque implementation model with explicit storage and lifecycle observations.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(x):
    items = x
    runs = []
    for value in items:
        if runs and runs[-1][0] == value:
            runs[-1][1] = 1
        else:
            runs.append([value,1])
    ends=[]
    total=0
    for value,count in runs:
        total += count
        ends.append(total)
    return [runs,ends]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('separate same values', solve([N,N,N+1,N,N]), {1: [[[1, 2], [2, 1], [1, 2]], [2, 3, 5]], 2: [[[2, 2], [3, 1], [2, 2]], [2, 3, 5]], 3: [[[3, 2], [4, 1], [3, 2]], [2, 3, 5]], 4: [[[4, 2], [5, 1], [4, 2]], [2, 3, 5]], 5: [[[5, 2], [6, 1], [5, 2]], [2, 3, 5]]}[N])
check('single', solve([N]), {1: [[[1, 1]], [1]], 2: [[[2, 1]], [1]], 3: [[[3, 1]], [1]], 4: [[[4, 1]], [1]], 5: [[[5, 1]], [1]]}[N])
check('empty', solve([]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])
check('all same', solve([N,N,N,N]), {1: [[[1, 4]], [4]], 2: [[[2, 4]], [4]], 3: [[[3, 4]], [4]], 4: [[[4, 4]], [4]], 5: [[[5, 4]], [4]]}[N])
check('all different', solve([N,N+1,N+2]), {1: [[[1, 1], [2, 1], [3, 1]], [1, 2, 3]], 2: [[[2, 1], [3, 1], [4, 1]], [1, 2, 3]], 3: [[[3, 1], [4, 1], [5, 1]], [1, 2, 3]], 4: [[[4, 1], [5, 1], [6, 1]], [1, 2, 3]], 5: [[[5, 1], [6, 1], [7, 1]], [1, 2, 3]]}[N])
check('unequal runs', solve([N,N,N+1,N+1,N+1,N+2]), {1: [[[1, 2], [2, 3], [3, 1]], [2, 5, 6]], 2: [[[2, 2], [3, 3], [4, 1]], [2, 5, 6]], 3: [[[3, 2], [4, 3], [5, 1]], [2, 5, 6]], 4: [[[4, 2], [5, 3], [6, 1]], [2, 5, 6]], 5: [[[5, 2], [6, 3], [7, 1]], [2, 5, 6]]}[N])
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
separate same values	`[[[1, 1], [2, 1], [1, 1]], [1, 2, 3]]`	`[[[1, 2], [2, 1], [1, 2]], [2, 3, 5]]`	Failed
single	`[[[1, 1]], [1]]`	`[[[1, 1]], [1]]`	Passed
empty	`[[], []]`	`[[], []]`	Passed
all same	`[[[1, 1]], [1]]`	`[[[1, 4]], [4]]`	Failed
all different	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	Passed
unequal runs	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	`[[[1, 2], [2, 3], [3, 1]], [2, 5, 6]]`	Failed

SHA-256 / ccd7ef815a037beb910b99fcf7892a53f3ed70af0a1f1ab0c8231258c2ce6c5a

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    items = x
    runs = []
    for value in items:
        if runs and runs[-1][0] == value:
            runs[-1][1] = min(2,runs[-1][1]+1)
        else:
            runs.append([value,1])
    ends=[]
    total=0
    for value,count in runs:
        total += count
        ends.append(total)
    return [runs,ends]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('separate same values', solve([N,N,N+1,N,N]), {1: [[[1, 2], [2, 1], [1, 2]], [2, 3, 5]], 2: [[[2, 2], [3, 1], [2, 2]], [2, 3, 5]], 3: [[[3, 2], [4, 1], [3, 2]], [2, 3, 5]], 4: [[[4, 2], [5, 1], [4, 2]], [2, 3, 5]], 5: [[[5, 2], [6, 1], [5, 2]], [2, 3, 5]]}[N])
check('single', solve([N]), {1: [[[1, 1]], [1]], 2: [[[2, 1]], [1]], 3: [[[3, 1]], [1]], 4: [[[4, 1]], [1]], 5: [[[5, 1]], [1]]}[N])
check('empty', solve([]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])
check('all same', solve([N,N,N,N]), {1: [[[1, 4]], [4]], 2: [[[2, 4]], [4]], 3: [[[3, 4]], [4]], 4: [[[4, 4]], [4]], 5: [[[5, 4]], [4]]}[N])
check('all different', solve([N,N+1,N+2]), {1: [[[1, 1], [2, 1], [3, 1]], [1, 2, 3]], 2: [[[2, 1], [3, 1], [4, 1]], [1, 2, 3]], 3: [[[3, 1], [4, 1], [5, 1]], [1, 2, 3]], 4: [[[4, 1], [5, 1], [6, 1]], [1, 2, 3]], 5: [[[5, 1], [6, 1], [7, 1]], [1, 2, 3]]}[N])
check('unequal runs', solve([N,N,N+1,N+1,N+1,N+2]), {1: [[[1, 2], [2, 3], [3, 1]], [2, 5, 6]], 2: [[[2, 2], [3, 3], [4, 1]], [2, 5, 6]], 3: [[[3, 2], [4, 3], [5, 1]], [2, 5, 6]], 4: [[[4, 2], [5, 3], [6, 1]], [2, 5, 6]], 5: [[[5, 2], [6, 3], [7, 1]], [2, 5, 6]]}[N])
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
separate same values	`[[[1, 2], [2, 1], [1, 2]], [2, 3, 5]]`	`[[[1, 2], [2, 1], [1, 2]], [2, 3, 5]]`	Passed
single	`[[[1, 1]], [1]]`	`[[[1, 1]], [1]]`	Passed
empty	`[[], []]`	`[[], []]`	Passed
all same	`[[[1, 2]], [2]]`	`[[[1, 4]], [4]]`	Failed
all different	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	Passed
unequal runs	`[[[1, 2], [2, 2], [3, 1]], [2, 4, 5]]`	`[[[1, 2], [2, 3], [3, 1]], [2, 5, 6]]`	Failed

SHA-256 / 6d38d1fb1f41fa55c8e4a304fa3c2f5ad90aa6f6e6cf8aea889208246141d808

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    items = x
    runs = []
    for value in items:
        if runs and runs[-1][0] == value:
            runs[-1][1] += 1
        else:
            runs.append([value,1])
    ends=[]
    total=0
    for value,count in runs:
        total += count
        ends.append(total)
    return [runs,ends]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('separate same values', solve([N,N,N+1,N,N]), {1: [[[1, 2], [2, 1], [1, 2]], [2, 3, 5]], 2: [[[2, 2], [3, 1], [2, 2]], [2, 3, 5]], 3: [[[3, 2], [4, 1], [3, 2]], [2, 3, 5]], 4: [[[4, 2], [5, 1], [4, 2]], [2, 3, 5]], 5: [[[5, 2], [6, 1], [5, 2]], [2, 3, 5]]}[N])
check('single', solve([N]), {1: [[[1, 1]], [1]], 2: [[[2, 1]], [1]], 3: [[[3, 1]], [1]], 4: [[[4, 1]], [1]], 5: [[[5, 1]], [1]]}[N])
check('empty', solve([]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])
check('all same', solve([N,N,N,N]), {1: [[[1, 4]], [4]], 2: [[[2, 4]], [4]], 3: [[[3, 4]], [4]], 4: [[[4, 4]], [4]], 5: [[[5, 4]], [4]]}[N])
check('all different', solve([N,N+1,N+2]), {1: [[[1, 1], [2, 1], [3, 1]], [1, 2, 3]], 2: [[[2, 1], [3, 1], [4, 1]], [1, 2, 3]], 3: [[[3, 1], [4, 1], [5, 1]], [1, 2, 3]], 4: [[[4, 1], [5, 1], [6, 1]], [1, 2, 3]], 5: [[[5, 1], [6, 1], [7, 1]], [1, 2, 3]]}[N])
check('unequal runs', solve([N,N,N+1,N+1,N+1,N+2]), {1: [[[1, 2], [2, 3], [3, 1]], [2, 5, 6]], 2: [[[2, 2], [3, 3], [4, 1]], [2, 5, 6]], 3: [[[3, 2], [4, 3], [5, 1]], [2, 5, 6]], 4: [[[4, 2], [5, 3], [6, 1]], [2, 5, 6]], 5: [[[5, 2], [6, 3], [7, 1]], [2, 5, 6]]}[N])
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
separate same values	`[[[1, 2], [2, 1], [1, 2]], [2, 3, 5]]`	`[[[1, 2], [2, 1], [1, 2]], [2, 3, 5]]`	Passed
single	`[[[1, 1]], [1]]`	`[[[1, 1]], [1]]`	Passed
empty	`[[], []]`	`[[], []]`	Passed
all same	`[[[1, 4]], [4]]`	`[[[1, 4]], [4]]`	Passed
all different	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	Passed
unequal runs	`[[[1, 2], [2, 3], [3, 1]], [2, 5, 6]]`	`[[[1, 2], [2, 3], [3, 1]], [2, 5, 6]]`	Passed

SHA-256 / f77ddc7133d238358bab6c3f17915950bdf9f95ffa45e9c66eea2676e907f04c

Verification & scope

Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. 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:44:28.759836+00:00.

Case digest / 5cf1bfdc464d6dd59634ae87eb57c110bec86725e34f9444a17c7dccc457ad27