FA-46096 / Bounded deques / Open access

Deque coalescing starts fresh runs at zero · case 01

Deque coalescing starts fresh runs at zero.

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

ROOT CAUSE

Deque coalescing starts fresh runs at zero.

VERIFIED REPAIR

Restore the documented run initial count 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,0])
    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, 0], [1, 1]], [1, 1, 2]]`	`[[[1, 2], [2, 1], [1, 2]], [2, 3, 5]]`	Failed
single	`[[[1, 0]], [0]]`	`[[[1, 1]], [1]]`	Failed
empty	`[[], []]`	`[[], []]`	Passed
all same	`[[[1, 3]], [3]]`	`[[[1, 4]], [4]]`	Failed
all different	`[[[1, 0], [2, 0], [3, 0]], [0, 0, 0]]`	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	Failed
unequal runs	`[[[1, 1], [2, 2], [3, 0]], [1, 3, 3]]`	`[[[1, 2], [2, 3], [3, 1]], [2, 5, 6]]`	Failed

SHA-256 / 6d0f38423b90c4da23c288cd4c7bfe3de8e788ed55d1c87e66ae5f5d3a406dcc

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] += 1
        else:
            runs.append([value,1 if not runs else 0])
    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, 0], [1, 1]], [2, 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, 4]], [4]]`	`[[[1, 4]], [4]]`	Passed
all different	`[[[1, 1], [2, 0], [3, 0]], [1, 1, 1]]`	`[[[1, 1], [2, 1], [3, 1]], [1, 2, 3]]`	Failed
unequal runs	`[[[1, 2], [2, 2], [3, 0]], [2, 4, 4]]`	`[[[1, 2], [2, 3], [3, 1]], [2, 5, 6]]`	Failed

SHA-256 / 920de8c43dc789b1ce1fadc364f196dbae33ceab6405116dca15a656cbd6001e

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

Case digest / c600d00904dae8df47dfc29baf7e686c681ac77710a6bb2666665a88adf46d6b