FA-46861 / Bounded deques / Open access
Deque block rebalance cuts the right remainder at old occupancy · case 01
Deque block rebalance cuts the right remainder at old occupancy.
ROOT CAUSE
Deque block rebalance cuts the right remainder at old occupancy.
VERIFIED REPAIR
Restore the documented right cut invariant in block-rebalance.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
Redistribute two adjacent deque blocks to a requested left occupancy without changing element order or block identities. Return signed left-to-right transfer count and new directory lengths.
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,b,target,aid,bid=x
joined=a+b
left=joined[:target]
right=joined[len(a):]
left_id=aid
right_id=bid
transfer=len(a)-target
directory=[[left_id,len(left)],[right_id,len(right)]]
return [left,right,left_id,right_id,transfer,directory]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[N+3],2,3,8]), {1: [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]], 2: [[2, 3], [4, 5], 3, 8, 1, [[3, 2], [8, 2]]], 3: [[3, 4], [5, 6], 3, 8, 1, [[3, 2], [8, 2]]], 4: [[4, 5], [6, 7], 3, 8, 1, [[3, 2], [8, 2]]], 5: [[5, 6], [7, 8], 3, 8, 1, [[3, 2], [8, 2]]]}[N])
check('1', solve([[N],[N+1,N+2,N+3],3,4,9]), {1: [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]], 2: [[2, 3, 4], [5], 4, 9, -2, [[4, 3], [9, 1]]], 3: [[3, 4, 5], [6], 4, 9, -2, [[4, 3], [9, 1]]], 4: [[4, 5, 6], [7], 4, 9, -2, [[4, 3], [9, 1]]], 5: [[5, 6, 7], [8], 4, 9, -2, [[4, 3], [9, 1]]]}[N])
check('2', solve([[N,N+1],[N+2,N+3],2,5,10]), {1: [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]], 2: [[2, 3], [4, 5], 5, 10, 0, [[5, 2], [10, 2]]], 3: [[3, 4], [5, 6], 5, 10, 0, [[5, 2], [10, 2]]], 4: [[4, 5], [6, 7], 5, 10, 0, [[5, 2], [10, 2]]], 5: [[5, 6], [7, 8], 5, 10, 0, [[5, 2], [10, 2]]]}[N])
check('3', solve([[],[N,N+1],1,2,7]), {1: [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]], 2: [[2], [3], 2, 7, -1, [[2, 1], [7, 1]]], 3: [[3], [4], 2, 7, -1, [[2, 1], [7, 1]]], 4: [[4], [5], 2, 7, -1, [[2, 1], [7, 1]]], 5: [[5], [6], 2, 7, -1, [[2, 1], [7, 1]]]}[N])
check('4', solve([[N,N+1],[],0,4,6]), {1: [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]], 2: [[], [2, 3], 4, 6, 2, [[4, 0], [6, 2]]], 3: [[], [3, 4], 4, 6, 2, [[4, 0], [6, 2]]], 4: [[], [4, 5], 4, 6, 2, [[4, 0], [6, 2]]], 5: [[], [5, 6], 4, 6, 2, [[4, 0], [6, 2]]]}[N])
check('5', solve([[N],[N+1],2,1,5]), {1: [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]], 2: [[2, 3], [], 1, 5, -1, [[1, 2], [5, 0]]], 3: [[3, 4], [], 1, 5, -1, [[1, 2], [5, 0]]], 4: [[4, 5], [], 1, 5, -1, [[1, 2], [5, 0]]], 5: [[5, 6], [], 1, 5, -1, [[1, 2], [5, 0]]]}[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], [4], 3, 8, 1, [[3, 2], [8, 1]]] | [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]] | Failed |
| 1 | [[1, 2, 3], [2, 3, 4], 4, 9, -2, [[4, 3], [9, 3]]] | [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]] | Failed |
| 2 | [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]] | [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]] | Passed |
| 3 | [[1], [1, 2], 2, 7, -1, [[2, 1], [7, 2]]] | [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]] | Failed |
| 4 | [[], [], 4, 6, 2, [[4, 0], [6, 0]]] | [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]] | Failed |
| 5 | [[1, 2], [2], 1, 5, -1, [[1, 2], [5, 1]]] | [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]] | Failed |
SHA-256 / 82132551da8f49a549a0419b75c0be29aab241fc842e8195bdc9a4e5616a65bc
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,b,target,aid,bid=x
joined=a+b
left=joined[:target]
right=joined[target:] if target==0 else joined[len(a):]
left_id=aid
right_id=bid
transfer=len(a)-target
directory=[[left_id,len(left)],[right_id,len(right)]]
return [left,right,left_id,right_id,transfer,directory]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[N+3],2,3,8]), {1: [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]], 2: [[2, 3], [4, 5], 3, 8, 1, [[3, 2], [8, 2]]], 3: [[3, 4], [5, 6], 3, 8, 1, [[3, 2], [8, 2]]], 4: [[4, 5], [6, 7], 3, 8, 1, [[3, 2], [8, 2]]], 5: [[5, 6], [7, 8], 3, 8, 1, [[3, 2], [8, 2]]]}[N])
check('1', solve([[N],[N+1,N+2,N+3],3,4,9]), {1: [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]], 2: [[2, 3, 4], [5], 4, 9, -2, [[4, 3], [9, 1]]], 3: [[3, 4, 5], [6], 4, 9, -2, [[4, 3], [9, 1]]], 4: [[4, 5, 6], [7], 4, 9, -2, [[4, 3], [9, 1]]], 5: [[5, 6, 7], [8], 4, 9, -2, [[4, 3], [9, 1]]]}[N])
check('2', solve([[N,N+1],[N+2,N+3],2,5,10]), {1: [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]], 2: [[2, 3], [4, 5], 5, 10, 0, [[5, 2], [10, 2]]], 3: [[3, 4], [5, 6], 5, 10, 0, [[5, 2], [10, 2]]], 4: [[4, 5], [6, 7], 5, 10, 0, [[5, 2], [10, 2]]], 5: [[5, 6], [7, 8], 5, 10, 0, [[5, 2], [10, 2]]]}[N])
check('3', solve([[],[N,N+1],1,2,7]), {1: [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]], 2: [[2], [3], 2, 7, -1, [[2, 1], [7, 1]]], 3: [[3], [4], 2, 7, -1, [[2, 1], [7, 1]]], 4: [[4], [5], 2, 7, -1, [[2, 1], [7, 1]]], 5: [[5], [6], 2, 7, -1, [[2, 1], [7, 1]]]}[N])
check('4', solve([[N,N+1],[],0,4,6]), {1: [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]], 2: [[], [2, 3], 4, 6, 2, [[4, 0], [6, 2]]], 3: [[], [3, 4], 4, 6, 2, [[4, 0], [6, 2]]], 4: [[], [4, 5], 4, 6, 2, [[4, 0], [6, 2]]], 5: [[], [5, 6], 4, 6, 2, [[4, 0], [6, 2]]]}[N])
check('5', solve([[N],[N+1],2,1,5]), {1: [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]], 2: [[2, 3], [], 1, 5, -1, [[1, 2], [5, 0]]], 3: [[3, 4], [], 1, 5, -1, [[1, 2], [5, 0]]], 4: [[4, 5], [], 1, 5, -1, [[1, 2], [5, 0]]], 5: [[5, 6], [], 1, 5, -1, [[1, 2], [5, 0]]]}[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], [4], 3, 8, 1, [[3, 2], [8, 1]]] | [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]] | Failed |
| 1 | [[1, 2, 3], [2, 3, 4], 4, 9, -2, [[4, 3], [9, 3]]] | [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]] | Failed |
| 2 | [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]] | [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]] | Passed |
| 3 | [[1], [1, 2], 2, 7, -1, [[2, 1], [7, 2]]] | [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]] | Failed |
| 4 | [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]] | [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]] | Passed |
| 5 | [[1, 2], [2], 1, 5, -1, [[1, 2], [5, 1]]] | [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]] | Failed |
SHA-256 / b5c02b893c15546575c4ced619eed6d5de524027605151b7eb92e1d0fcadfaf1
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,b,target,aid,bid=x
joined=a+b
left=joined[:target]
right=joined[target:]
left_id=aid
right_id=bid
transfer=len(a)-target
directory=[[left_id,len(left)],[right_id,len(right)]]
return [left,right,left_id,right_id,transfer,directory]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[N+3],2,3,8]), {1: [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]], 2: [[2, 3], [4, 5], 3, 8, 1, [[3, 2], [8, 2]]], 3: [[3, 4], [5, 6], 3, 8, 1, [[3, 2], [8, 2]]], 4: [[4, 5], [6, 7], 3, 8, 1, [[3, 2], [8, 2]]], 5: [[5, 6], [7, 8], 3, 8, 1, [[3, 2], [8, 2]]]}[N])
check('1', solve([[N],[N+1,N+2,N+3],3,4,9]), {1: [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]], 2: [[2, 3, 4], [5], 4, 9, -2, [[4, 3], [9, 1]]], 3: [[3, 4, 5], [6], 4, 9, -2, [[4, 3], [9, 1]]], 4: [[4, 5, 6], [7], 4, 9, -2, [[4, 3], [9, 1]]], 5: [[5, 6, 7], [8], 4, 9, -2, [[4, 3], [9, 1]]]}[N])
check('2', solve([[N,N+1],[N+2,N+3],2,5,10]), {1: [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]], 2: [[2, 3], [4, 5], 5, 10, 0, [[5, 2], [10, 2]]], 3: [[3, 4], [5, 6], 5, 10, 0, [[5, 2], [10, 2]]], 4: [[4, 5], [6, 7], 5, 10, 0, [[5, 2], [10, 2]]], 5: [[5, 6], [7, 8], 5, 10, 0, [[5, 2], [10, 2]]]}[N])
check('3', solve([[],[N,N+1],1,2,7]), {1: [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]], 2: [[2], [3], 2, 7, -1, [[2, 1], [7, 1]]], 3: [[3], [4], 2, 7, -1, [[2, 1], [7, 1]]], 4: [[4], [5], 2, 7, -1, [[2, 1], [7, 1]]], 5: [[5], [6], 2, 7, -1, [[2, 1], [7, 1]]]}[N])
check('4', solve([[N,N+1],[],0,4,6]), {1: [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]], 2: [[], [2, 3], 4, 6, 2, [[4, 0], [6, 2]]], 3: [[], [3, 4], 4, 6, 2, [[4, 0], [6, 2]]], 4: [[], [4, 5], 4, 6, 2, [[4, 0], [6, 2]]], 5: [[], [5, 6], 4, 6, 2, [[4, 0], [6, 2]]]}[N])
check('5', solve([[N],[N+1],2,1,5]), {1: [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]], 2: [[2, 3], [], 1, 5, -1, [[1, 2], [5, 0]]], 3: [[3, 4], [], 1, 5, -1, [[1, 2], [5, 0]]], 4: [[4, 5], [], 1, 5, -1, [[1, 2], [5, 0]]], 5: [[5, 6], [], 1, 5, -1, [[1, 2], [5, 0]]]}[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, 4], 3, 8, 1, [[3, 2], [8, 2]]] | [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]] | Passed |
| 1 | [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]] | [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]] | Passed |
| 2 | [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]] | [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]] | Passed |
| 3 | [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]] | [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]] | Passed |
| 4 | [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]] | [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]] | Passed |
| 5 | [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]] | [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]] | Passed |
SHA-256 / 11d0b7614a186d9f7d2caf833d429e69c852dffcab5bdba2b6c8814051bd71fb
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:36.080501+00:00.
Case digest / e2275c46f4cf7303e3ac524fd06f3f3aefa915394c0454d0aea68c7ddd159c73