FAILURE MAP
← Case archive

FA-46316 / Bounded deques / Open access

Deque reorder sorts its supplied permutation before applying it · case 01

Deque reorder sorts its supplied permutation before applying it.

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

ROOT CAUSE

Deque reorder sorts its supplied permutation before applying it.

VERIFIED REPAIR

Restore the documented permutation order invariant in permutation-reorder.

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

Case contract

Reorder a bounded deque by a complete permutation of old indices, then return the inverse mapping used by bookmarks. Invalid duplicate, missing or out-of-range indices reject without changing the deque.

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):
    a,order=x
    valid=sorted(order)==list(range(len(a)))
    if not valid:return [a,False,[]]
    result=[a[i] for i in sorted(order)]
    inverse=[0]*len(a)
    for new,old in enumerate(order):inverse[old]=new
    return [result,True,inverse]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[2,0,1]]), {1: [[3, 1, 2], True, [1, 2, 0]], 2: [[4, 2, 3], True, [1, 2, 0]], 3: [[5, 3, 4], True, [1, 2, 0]], 4: [[6, 4, 5], True, [1, 2, 0]], 5: [[7, 5, 6], True, [1, 2, 0]]}[N])
check('1', solve([[N,N+1],[0,0]]), {1: [[1, 2], False, []], 2: [[2, 3], False, []], 3: [[3, 4], False, []], 4: [[4, 5], False, []], 5: [[5, 6], False, []]}[N])
check('2', solve([[N,N+1],[0]]), {1: [[1, 2], False, []], 2: [[2, 3], False, []], 3: [[3, 4], False, []], 4: [[4, 5], False, []], 5: [[5, 6], False, []]}[N])
check('3', solve([[N],[0]]), {1: [[1], True, [0]], 2: [[2], True, [0]], 3: [[3], True, [0]], 4: [[4], True, [0]], 5: [[5], True, [0]]}[N])
check('4', solve([[],[]]), {1: [[], True, []], 2: [[], True, []], 3: [[], True, []], 4: [[], True, []], 5: [[], True, []]}[N])
check('5', solve([[N,N+1,N+2,N+3],[1,3,0,2]]), {1: [[2, 4, 1, 3], True, [2, 0, 3, 1]], 2: [[3, 5, 2, 4], True, [2, 0, 3, 1]], 3: [[4, 6, 3, 5], True, [2, 0, 3, 1]], 4: [[5, 7, 4, 6], True, [2, 0, 3, 1]], 5: [[6, 8, 5, 7], True, [2, 0, 3, 1]]}[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 fixtureActualExpectedOutcome
0[[1, 2, 3], True, [1, 2, 0]][[3, 1, 2], True, [1, 2, 0]]Failed
1[[1, 2], False, []][[1, 2], False, []]Passed
2[[1, 2], False, []][[1, 2], False, []]Passed
3[[1], True, [0]][[1], True, [0]]Passed
4[[], True, []][[], True, []]Passed
5[[1, 2, 3, 4], True, [2, 0, 3, 1]][[2, 4, 1, 3], True, [2, 0, 3, 1]]Failed

SHA-256 / d30007653488f1bddf8f9cc5c0f72994e18620312cc0de4ba6f54aa608c1639c

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    a,order=x
    valid=sorted(order)==list(range(len(a)))
    if not valid:return [a,False,[]]
    result=[a[i] for i in (order if len(a)<3 else sorted(order))]
    inverse=[0]*len(a)
    for new,old in enumerate(order):inverse[old]=new
    return [result,True,inverse]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[2,0,1]]), {1: [[3, 1, 2], True, [1, 2, 0]], 2: [[4, 2, 3], True, [1, 2, 0]], 3: [[5, 3, 4], True, [1, 2, 0]], 4: [[6, 4, 5], True, [1, 2, 0]], 5: [[7, 5, 6], True, [1, 2, 0]]}[N])
check('1', solve([[N,N+1],[0,0]]), {1: [[1, 2], False, []], 2: [[2, 3], False, []], 3: [[3, 4], False, []], 4: [[4, 5], False, []], 5: [[5, 6], False, []]}[N])
check('2', solve([[N,N+1],[0]]), {1: [[1, 2], False, []], 2: [[2, 3], False, []], 3: [[3, 4], False, []], 4: [[4, 5], False, []], 5: [[5, 6], False, []]}[N])
check('3', solve([[N],[0]]), {1: [[1], True, [0]], 2: [[2], True, [0]], 3: [[3], True, [0]], 4: [[4], True, [0]], 5: [[5], True, [0]]}[N])
check('4', solve([[],[]]), {1: [[], True, []], 2: [[], True, []], 3: [[], True, []], 4: [[], True, []], 5: [[], True, []]}[N])
check('5', solve([[N,N+1,N+2,N+3],[1,3,0,2]]), {1: [[2, 4, 1, 3], True, [2, 0, 3, 1]], 2: [[3, 5, 2, 4], True, [2, 0, 3, 1]], 3: [[4, 6, 3, 5], True, [2, 0, 3, 1]], 4: [[5, 7, 4, 6], True, [2, 0, 3, 1]], 5: [[6, 8, 5, 7], True, [2, 0, 3, 1]]}[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 fixtureActualExpectedOutcome
0[[1, 2, 3], True, [1, 2, 0]][[3, 1, 2], True, [1, 2, 0]]Failed
1[[1, 2], False, []][[1, 2], False, []]Passed
2[[1, 2], False, []][[1, 2], False, []]Passed
3[[1], True, [0]][[1], True, [0]]Passed
4[[], True, []][[], True, []]Passed
5[[1, 2, 3, 4], True, [2, 0, 3, 1]][[2, 4, 1, 3], True, [2, 0, 3, 1]]Failed

SHA-256 / 1563b54544a96ca58e9c97b2b3d526af16a2d6e89d2bcde9fa4c8807ec0e6aa5

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    a,order=x
    valid=sorted(order)==list(range(len(a)))
    if not valid:return [a,False,[]]
    result=[a[i] for i in order]
    inverse=[0]*len(a)
    for new,old in enumerate(order):inverse[old]=new
    return [result,True,inverse]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[2,0,1]]), {1: [[3, 1, 2], True, [1, 2, 0]], 2: [[4, 2, 3], True, [1, 2, 0]], 3: [[5, 3, 4], True, [1, 2, 0]], 4: [[6, 4, 5], True, [1, 2, 0]], 5: [[7, 5, 6], True, [1, 2, 0]]}[N])
check('1', solve([[N,N+1],[0,0]]), {1: [[1, 2], False, []], 2: [[2, 3], False, []], 3: [[3, 4], False, []], 4: [[4, 5], False, []], 5: [[5, 6], False, []]}[N])
check('2', solve([[N,N+1],[0]]), {1: [[1, 2], False, []], 2: [[2, 3], False, []], 3: [[3, 4], False, []], 4: [[4, 5], False, []], 5: [[5, 6], False, []]}[N])
check('3', solve([[N],[0]]), {1: [[1], True, [0]], 2: [[2], True, [0]], 3: [[3], True, [0]], 4: [[4], True, [0]], 5: [[5], True, [0]]}[N])
check('4', solve([[],[]]), {1: [[], True, []], 2: [[], True, []], 3: [[], True, []], 4: [[], True, []], 5: [[], True, []]}[N])
check('5', solve([[N,N+1,N+2,N+3],[1,3,0,2]]), {1: [[2, 4, 1, 3], True, [2, 0, 3, 1]], 2: [[3, 5, 2, 4], True, [2, 0, 3, 1]], 3: [[4, 6, 3, 5], True, [2, 0, 3, 1]], 4: [[5, 7, 4, 6], True, [2, 0, 3, 1]], 5: [[6, 8, 5, 7], True, [2, 0, 3, 1]]}[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 fixtureActualExpectedOutcome
0[[3, 1, 2], True, [1, 2, 0]][[3, 1, 2], True, [1, 2, 0]]Passed
1[[1, 2], False, []][[1, 2], False, []]Passed
2[[1, 2], False, []][[1, 2], False, []]Passed
3[[1], True, [0]][[1], True, [0]]Passed
4[[], True, []][[], True, []]Passed
5[[2, 4, 1, 3], True, [2, 0, 3, 1]][[2, 4, 1, 3], True, [2, 0, 3, 1]]Passed

SHA-256 / 5763b2a059ee17f1ef717747dbb018e886fdd5f637613eb27a9b26fece6f938c

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

Case digest / 657646614e733a6501bb91edd06b82eaba624d15e61524fbc270497f8d450345