FA-47006 / Bounded deques / Open access
Lazy reversed deque removes the physical front · case 01
Lazy reversed deque removes the physical front.
ROOT CAUSE
Lazy reversed deque removes the physical front.
VERIFIED REPAIR
Restore the documented front removal invariant in lazy-orientation.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
A bounded deque stores physical values and a lazy reversed flag. Flip toggles orientation without moving storage; logical append and front-pop select the appropriate physical endpoint. Full append rejects.
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):
storage,reverse,op,value,cap=x
logical=storage[::-1] if reverse else storage[:]
if op=='flip':return [storage,not reverse,logical[::-1],None]
if op=='push':
if len(storage)==cap:return [storage,reverse,logical,'full']
physical=[value]+storage if reverse else storage+[value]
return [physical,reverse,logical+[value],None]
if not storage:return [storage,reverse,logical,'empty']
result=storage[1:]
removed=storage[-1] if reverse else storage[0]
remaining=result[::-1] if reverse else result[:]
return [result,reverse,remaining,removed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],True,"pop",0,4]), {1: [[1, 2], True, [2, 1], 3], 2: [[2, 3], True, [3, 2], 4], 3: [[3, 4], True, [4, 3], 5], 4: [[4, 5], True, [5, 4], 6], 5: [[5, 6], True, [6, 5], 7]}[N])
check('1', solve([[N,N+1],True,"push",N+2,4]), {1: [[3, 1, 2], True, [2, 1, 3], None], 2: [[4, 2, 3], True, [3, 2, 4], None], 3: [[5, 3, 4], True, [4, 3, 5], None], 4: [[6, 4, 5], True, [5, 4, 6], None], 5: [[7, 5, 6], True, [6, 5, 7], None]}[N])
check('2', solve([[N,N+1],False,"flip",0,3]), {1: [[1, 2], True, [2, 1], None], 2: [[2, 3], True, [3, 2], None], 3: [[3, 4], True, [4, 3], None], 4: [[4, 5], True, [5, 4], None], 5: [[5, 6], True, [6, 5], None]}[N])
check('3', solve([[N,N+1],True,"flip",0,3]), {1: [[1, 2], False, [1, 2], None], 2: [[2, 3], False, [2, 3], None], 3: [[3, 4], False, [3, 4], None], 4: [[4, 5], False, [4, 5], None], 5: [[5, 6], False, [5, 6], None]}[N])
check('4', solve([[N],False,"push",N+1,1]), {1: [[1], False, [1], 'full'], 2: [[2], False, [2], 'full'], 3: [[3], False, [3], 'full'], 4: [[4], False, [4], 'full'], 5: [[5], False, [5], 'full']}[N])
check('5', solve([[],True,"pop",0,3]), {1: [[], True, [], 'empty'], 2: [[], True, [], 'empty'], 3: [[], True, [], 'empty'], 4: [[], True, [], 'empty'], 5: [[], True, [], 'empty']}[N])
check('6', solve([[N,N+1],False,"pop",0,3]), {1: [[2], False, [2], 1], 2: [[3], False, [3], 2], 3: [[4], False, [4], 3], 4: [[5], False, [5], 4], 5: [[6], False, [6], 5]}[N])
check('7', solve([[N],False,"push",N+1,3]), {1: [[1, 2], False, [1, 2], None], 2: [[2, 3], False, [2, 3], None], 3: [[3, 4], False, [3, 4], None], 4: [[4, 5], False, [4, 5], None], 5: [[5, 6], False, [5, 6], None]}[N])
check('full reversed rejection', solve([[N,N+1],True,'push',N+2,2]), [[N,N+1],True,[N+1,N],'full'])
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 | [[2, 3], True, [3, 2], 3] | [[1, 2], True, [2, 1], 3] | Failed |
| 1 | [[3, 1, 2], True, [2, 1, 3], None] | [[3, 1, 2], True, [2, 1, 3], None] | Passed |
| 2 | [[1, 2], True, [2, 1], None] | [[1, 2], True, [2, 1], None] | Passed |
| 3 | [[1, 2], False, [1, 2], None] | [[1, 2], False, [1, 2], None] | Passed |
| 4 | [[1], False, [1], 'full'] | [[1], False, [1], 'full'] | Passed |
| 5 | [[], True, [], 'empty'] | [[], True, [], 'empty'] | Passed |
| 6 | [[2], False, [2], 1] | [[2], False, [2], 1] | Passed |
| 7 | [[1, 2], False, [1, 2], None] | [[1, 2], False, [1, 2], None] | Passed |
| full reversed rejection | [[1, 2], True, [2, 1], 'full'] | [[1, 2], True, [2, 1], 'full'] | Passed |
SHA-256 / 75bee201141d6cc22fd39b82c06ac37e808f4863763fcfb01c5096a900a82cca
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
storage,reverse,op,value,cap=x
logical=storage[::-1] if reverse else storage[:]
if op=='flip':return [storage,not reverse,logical[::-1],None]
if op=='push':
if len(storage)==cap:return [storage,reverse,logical,'full']
physical=[value]+storage if reverse else storage+[value]
return [physical,reverse,logical+[value],None]
if not storage:return [storage,reverse,logical,'empty']
result=storage[:-1] if reverse and len(storage)==1 else storage[1:]
removed=storage[-1] if reverse else storage[0]
remaining=result[::-1] if reverse else result[:]
return [result,reverse,remaining,removed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],True,"pop",0,4]), {1: [[1, 2], True, [2, 1], 3], 2: [[2, 3], True, [3, 2], 4], 3: [[3, 4], True, [4, 3], 5], 4: [[4, 5], True, [5, 4], 6], 5: [[5, 6], True, [6, 5], 7]}[N])
check('1', solve([[N,N+1],True,"push",N+2,4]), {1: [[3, 1, 2], True, [2, 1, 3], None], 2: [[4, 2, 3], True, [3, 2, 4], None], 3: [[5, 3, 4], True, [4, 3, 5], None], 4: [[6, 4, 5], True, [5, 4, 6], None], 5: [[7, 5, 6], True, [6, 5, 7], None]}[N])
check('2', solve([[N,N+1],False,"flip",0,3]), {1: [[1, 2], True, [2, 1], None], 2: [[2, 3], True, [3, 2], None], 3: [[3, 4], True, [4, 3], None], 4: [[4, 5], True, [5, 4], None], 5: [[5, 6], True, [6, 5], None]}[N])
check('3', solve([[N,N+1],True,"flip",0,3]), {1: [[1, 2], False, [1, 2], None], 2: [[2, 3], False, [2, 3], None], 3: [[3, 4], False, [3, 4], None], 4: [[4, 5], False, [4, 5], None], 5: [[5, 6], False, [5, 6], None]}[N])
check('4', solve([[N],False,"push",N+1,1]), {1: [[1], False, [1], 'full'], 2: [[2], False, [2], 'full'], 3: [[3], False, [3], 'full'], 4: [[4], False, [4], 'full'], 5: [[5], False, [5], 'full']}[N])
check('5', solve([[],True,"pop",0,3]), {1: [[], True, [], 'empty'], 2: [[], True, [], 'empty'], 3: [[], True, [], 'empty'], 4: [[], True, [], 'empty'], 5: [[], True, [], 'empty']}[N])
check('6', solve([[N,N+1],False,"pop",0,3]), {1: [[2], False, [2], 1], 2: [[3], False, [3], 2], 3: [[4], False, [4], 3], 4: [[5], False, [5], 4], 5: [[6], False, [6], 5]}[N])
check('7', solve([[N],False,"push",N+1,3]), {1: [[1, 2], False, [1, 2], None], 2: [[2, 3], False, [2, 3], None], 3: [[3, 4], False, [3, 4], None], 4: [[4, 5], False, [4, 5], None], 5: [[5, 6], False, [5, 6], None]}[N])
check('full reversed rejection', solve([[N,N+1],True,'push',N+2,2]), [[N,N+1],True,[N+1,N],'full'])
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 | [[2, 3], True, [3, 2], 3] | [[1, 2], True, [2, 1], 3] | Failed |
| 1 | [[3, 1, 2], True, [2, 1, 3], None] | [[3, 1, 2], True, [2, 1, 3], None] | Passed |
| 2 | [[1, 2], True, [2, 1], None] | [[1, 2], True, [2, 1], None] | Passed |
| 3 | [[1, 2], False, [1, 2], None] | [[1, 2], False, [1, 2], None] | Passed |
| 4 | [[1], False, [1], 'full'] | [[1], False, [1], 'full'] | Passed |
| 5 | [[], True, [], 'empty'] | [[], True, [], 'empty'] | Passed |
| 6 | [[2], False, [2], 1] | [[2], False, [2], 1] | Passed |
| 7 | [[1, 2], False, [1, 2], None] | [[1, 2], False, [1, 2], None] | Passed |
| full reversed rejection | [[1, 2], True, [2, 1], 'full'] | [[1, 2], True, [2, 1], 'full'] | Passed |
SHA-256 / e397531c0a06a7e1e0f6165b31ab23e118d9bdaf9187a1f0466942e0fa26a59b
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
storage,reverse,op,value,cap=x
logical=storage[::-1] if reverse else storage[:]
if op=='flip':return [storage,not reverse,logical[::-1],None]
if op=='push':
if len(storage)==cap:return [storage,reverse,logical,'full']
physical=[value]+storage if reverse else storage+[value]
return [physical,reverse,logical+[value],None]
if not storage:return [storage,reverse,logical,'empty']
result=storage[:-1] if reverse else storage[1:]
removed=storage[-1] if reverse else storage[0]
remaining=result[::-1] if reverse else result[:]
return [result,reverse,remaining,removed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],True,"pop",0,4]), {1: [[1, 2], True, [2, 1], 3], 2: [[2, 3], True, [3, 2], 4], 3: [[3, 4], True, [4, 3], 5], 4: [[4, 5], True, [5, 4], 6], 5: [[5, 6], True, [6, 5], 7]}[N])
check('1', solve([[N,N+1],True,"push",N+2,4]), {1: [[3, 1, 2], True, [2, 1, 3], None], 2: [[4, 2, 3], True, [3, 2, 4], None], 3: [[5, 3, 4], True, [4, 3, 5], None], 4: [[6, 4, 5], True, [5, 4, 6], None], 5: [[7, 5, 6], True, [6, 5, 7], None]}[N])
check('2', solve([[N,N+1],False,"flip",0,3]), {1: [[1, 2], True, [2, 1], None], 2: [[2, 3], True, [3, 2], None], 3: [[3, 4], True, [4, 3], None], 4: [[4, 5], True, [5, 4], None], 5: [[5, 6], True, [6, 5], None]}[N])
check('3', solve([[N,N+1],True,"flip",0,3]), {1: [[1, 2], False, [1, 2], None], 2: [[2, 3], False, [2, 3], None], 3: [[3, 4], False, [3, 4], None], 4: [[4, 5], False, [4, 5], None], 5: [[5, 6], False, [5, 6], None]}[N])
check('4', solve([[N],False,"push",N+1,1]), {1: [[1], False, [1], 'full'], 2: [[2], False, [2], 'full'], 3: [[3], False, [3], 'full'], 4: [[4], False, [4], 'full'], 5: [[5], False, [5], 'full']}[N])
check('5', solve([[],True,"pop",0,3]), {1: [[], True, [], 'empty'], 2: [[], True, [], 'empty'], 3: [[], True, [], 'empty'], 4: [[], True, [], 'empty'], 5: [[], True, [], 'empty']}[N])
check('6', solve([[N,N+1],False,"pop",0,3]), {1: [[2], False, [2], 1], 2: [[3], False, [3], 2], 3: [[4], False, [4], 3], 4: [[5], False, [5], 4], 5: [[6], False, [6], 5]}[N])
check('7', solve([[N],False,"push",N+1,3]), {1: [[1, 2], False, [1, 2], None], 2: [[2, 3], False, [2, 3], None], 3: [[3, 4], False, [3, 4], None], 4: [[4, 5], False, [4, 5], None], 5: [[5, 6], False, [5, 6], None]}[N])
check('full reversed rejection', solve([[N,N+1],True,'push',N+2,2]), [[N,N+1],True,[N+1,N],'full'])
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], True, [2, 1], 3] | [[1, 2], True, [2, 1], 3] | Passed |
| 1 | [[3, 1, 2], True, [2, 1, 3], None] | [[3, 1, 2], True, [2, 1, 3], None] | Passed |
| 2 | [[1, 2], True, [2, 1], None] | [[1, 2], True, [2, 1], None] | Passed |
| 3 | [[1, 2], False, [1, 2], None] | [[1, 2], False, [1, 2], None] | Passed |
| 4 | [[1], False, [1], 'full'] | [[1], False, [1], 'full'] | Passed |
| 5 | [[], True, [], 'empty'] | [[], True, [], 'empty'] | Passed |
| 6 | [[2], False, [2], 1] | [[2], False, [2], 1] | Passed |
| 7 | [[1, 2], False, [1, 2], None] | [[1, 2], False, [1, 2], None] | Passed |
| full reversed rejection | [[1, 2], True, [2, 1], 'full'] | [[1, 2], True, [2, 1], 'full'] | Passed |
SHA-256 / 7717b8a00c3961ff1a3605d14928e172f7e050412a6cf1e267e97d35211f64d0
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:37.441797+00:00.
Case digest / acca887fd3b266fe43addd591a6f6b514aa7f8f0d45a162d949483b305fed399