FA-46341 / Bounded deques / Open access

Deque uniqueness reports duplicate values instead of removed positions · case 01

Deque uniqueness reports duplicate values instead of removed positions.

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

ROOT CAUSE

Deque uniqueness reports duplicate values instead of removed positions.

VERIFIED REPAIR

Restore the documented duplicate index invariant in stable-unique.

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

Case contract

Keep the first occurrence of each deque payload and return survivor values plus original positions removed. Payload equality is integer equality; zero is a valid value.

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
    seen=set()
    keep=[]
    removed=[]
    for i,v in enumerate(items):
        if v in seen:removed.append(v)
        else:
            keep.append(v)
            seen.add(v)
    return [keep,removed]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([N,N+1,N,N+2,N+1]), {1: [[1, 2, 3], [2, 4]], 2: [[2, 3, 4], [2, 4]], 3: [[3, 4, 5], [2, 4]], 4: [[4, 5, 6], [2, 4]], 5: [[5, 6, 7], [2, 4]]}[N])
check('1', solve([0,N,0,N]), {1: [[0, 1], [2, 3]], 2: [[0, 2], [2, 3]], 3: [[0, 3], [2, 3]], 4: [[0, 4], [2, 3]], 5: [[0, 5], [2, 3]]}[N])
check('2', solve([N,N,N]), {1: [[1], [1, 2]], 2: [[2], [1, 2]], 3: [[3], [1, 2]], 4: [[4], [1, 2]], 5: [[5], [1, 2]]}[N])
check('3', solve([]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])
check('4', solve([N,N+1,N+2]), {1: [[1, 2, 3], []], 2: [[2, 3, 4], []], 3: [[3, 4, 5], []], 4: [[4, 5, 6], []], 5: [[5, 6, 7], []]}[N])
check('5', solve([N+2,N,N+2,N+1]), {1: [[3, 1, 2], [2]], 2: [[4, 2, 3], [2]], 3: [[5, 3, 4], [2]], 4: [[6, 4, 5], [2]], 5: [[7, 5, 6], [2]]}[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
0	`[[1, 2, 3], [1, 2]]`	`[[1, 2, 3], [2, 4]]`	Failed
1	`[[0, 1], [0, 1]]`	`[[0, 1], [2, 3]]`	Failed
2	`[[1], [1, 1]]`	`[[1], [1, 2]]`	Failed
3	`[[], []]`	`[[], []]`	Passed
4	`[[1, 2, 3], []]`	`[[1, 2, 3], []]`	Passed
5	`[[3, 1, 2], [3]]`	`[[3, 1, 2], [2]]`	Failed

SHA-256 / 07f0ca1241d9d2415a29f256fc69921810e306de3a17f1297093c24384de559d

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    items=x
    seen=set()
    keep=[]
    removed=[]
    for i,v in enumerate(items):
        if v in seen:removed.append(i if v==0 else v)
        else:
            keep.append(v)
            seen.add(v)
    return [keep,removed]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([N,N+1,N,N+2,N+1]), {1: [[1, 2, 3], [2, 4]], 2: [[2, 3, 4], [2, 4]], 3: [[3, 4, 5], [2, 4]], 4: [[4, 5, 6], [2, 4]], 5: [[5, 6, 7], [2, 4]]}[N])
check('1', solve([0,N,0,N]), {1: [[0, 1], [2, 3]], 2: [[0, 2], [2, 3]], 3: [[0, 3], [2, 3]], 4: [[0, 4], [2, 3]], 5: [[0, 5], [2, 3]]}[N])
check('2', solve([N,N,N]), {1: [[1], [1, 2]], 2: [[2], [1, 2]], 3: [[3], [1, 2]], 4: [[4], [1, 2]], 5: [[5], [1, 2]]}[N])
check('3', solve([]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])
check('4', solve([N,N+1,N+2]), {1: [[1, 2, 3], []], 2: [[2, 3, 4], []], 3: [[3, 4, 5], []], 4: [[4, 5, 6], []], 5: [[5, 6, 7], []]}[N])
check('5', solve([N+2,N,N+2,N+1]), {1: [[3, 1, 2], [2]], 2: [[4, 2, 3], [2]], 3: [[5, 3, 4], [2]], 4: [[6, 4, 5], [2]], 5: [[7, 5, 6], [2]]}[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
0	`[[1, 2, 3], [1, 2]]`	`[[1, 2, 3], [2, 4]]`	Failed
1	`[[0, 1], [2, 1]]`	`[[0, 1], [2, 3]]`	Failed
2	`[[1], [1, 1]]`	`[[1], [1, 2]]`	Failed
3	`[[], []]`	`[[], []]`	Passed
4	`[[1, 2, 3], []]`	`[[1, 2, 3], []]`	Passed
5	`[[3, 1, 2], [3]]`	`[[3, 1, 2], [2]]`	Failed

SHA-256 / 4c2438f831e6beff05396b540f2f1aa99a70179c04c5b4051e7dfb9ec43c1436

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    items=x
    seen=set()
    keep=[]
    removed=[]
    for i,v in enumerate(items):
        if v in seen:removed.append(i)
        else:
            keep.append(v)
            seen.add(v)
    return [keep,removed]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([N,N+1,N,N+2,N+1]), {1: [[1, 2, 3], [2, 4]], 2: [[2, 3, 4], [2, 4]], 3: [[3, 4, 5], [2, 4]], 4: [[4, 5, 6], [2, 4]], 5: [[5, 6, 7], [2, 4]]}[N])
check('1', solve([0,N,0,N]), {1: [[0, 1], [2, 3]], 2: [[0, 2], [2, 3]], 3: [[0, 3], [2, 3]], 4: [[0, 4], [2, 3]], 5: [[0, 5], [2, 3]]}[N])
check('2', solve([N,N,N]), {1: [[1], [1, 2]], 2: [[2], [1, 2]], 3: [[3], [1, 2]], 4: [[4], [1, 2]], 5: [[5], [1, 2]]}[N])
check('3', solve([]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])
check('4', solve([N,N+1,N+2]), {1: [[1, 2, 3], []], 2: [[2, 3, 4], []], 3: [[3, 4, 5], []], 4: [[4, 5, 6], []], 5: [[5, 6, 7], []]}[N])
check('5', solve([N+2,N,N+2,N+1]), {1: [[3, 1, 2], [2]], 2: [[4, 2, 3], [2]], 3: [[5, 3, 4], [2]], 4: [[6, 4, 5], [2]], 5: [[7, 5, 6], [2]]}[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
0	`[[1, 2, 3], [2, 4]]`	`[[1, 2, 3], [2, 4]]`	Passed
1	`[[0, 1], [2, 3]]`	`[[0, 1], [2, 3]]`	Passed
2	`[[1], [1, 2]]`	`[[1], [1, 2]]`	Passed
3	`[[], []]`	`[[], []]`	Passed
4	`[[1, 2, 3], []]`	`[[1, 2, 3], []]`	Passed
5	`[[3, 1, 2], [2]]`	`[[3, 1, 2], [2]]`	Passed

SHA-256 / db55b9adbae1f45722eab54cffeb4ad620087c984ffa07e5cee2363925e8ad3c

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

Case digest / cafa6238608826ce26d18910b69f0e307a2b0c08720b7ab08e7c4f7a0a378cd3