FA-46346 / Bounded deques / Open access

Deque uniqueness prepends each first occurrence · case 01

Deque uniqueness prepends each first occurrence.

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

ROOT CAUSE

Deque uniqueness prepends each first occurrence.

VERIFIED REPAIR

Restore the documented first stability 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(i)
        else:
            keep.insert(0,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	`[[3, 2, 1], [2, 4]]`	`[[1, 2, 3], [2, 4]]`	Failed
1	`[[1, 0], [2, 3]]`	`[[0, 1], [2, 3]]`	Failed
2	`[[1], [1, 2]]`	`[[1], [1, 2]]`	Passed
3	`[[], []]`	`[[], []]`	Passed
4	`[[3, 2, 1], []]`	`[[1, 2, 3], []]`	Failed
5	`[[2, 1, 3], [2]]`	`[[3, 1, 2], [2]]`	Failed

SHA-256 / 48551e792002cfe24c394b3c54bf9ab05afa5c664f02d22c8d0dca3a228a5d50

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)
        else:
            keep.append(v) if not keep else keep.insert(0,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	`[[3, 2, 1], [2, 4]]`	`[[1, 2, 3], [2, 4]]`	Failed
1	`[[1, 0], [2, 3]]`	`[[0, 1], [2, 3]]`	Failed
2	`[[1], [1, 2]]`	`[[1], [1, 2]]`	Passed
3	`[[], []]`	`[[], []]`	Passed
4	`[[3, 2, 1], []]`	`[[1, 2, 3], []]`	Failed
5	`[[2, 1, 3], [2]]`	`[[3, 1, 2], [2]]`	Failed

SHA-256 / 129eb099e1b754dcbe1d04c1589918e89ed458600da12aad7c8269588dc83dd7

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

Case digest / f5f3284cbf9e8ea3711b777a192b785479317e7adef147de2d8f4c3aa32a71f5