FA-15206 / Numerics / Open access
Dyck word ranking: opening depth update · case 01
The exact dyck word ranking result violates the stated contract at opening depth update.
ROOT CAUSE
The opening depth update step uses o instead of o+1.
VERIFIED REPAIR
Use o+1 at the opening depth update step.
Unsuccessful approach: The partial repair c+1 still violates the opening depth update invariant.
Case contract
Input balanced parentheses word with every prefix nonnegative; return zero-based lexicographic rank where opening precedes closing. Bounds: at most five opening parentheses.
Why this case matters
Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
word=x;n=len(word)//2
from functools import lru_cache
@lru_cache(None)
def count(o,c):
if c>o or o>n:return 0
if o==n and c==n:return 1
return (count(o+1,c) if o<n else 0)+(count(o,c+1) if c<o else 0)
r=0;o=c=0
for ch in word:
if ch==')':
r+=count(o+1,c)
c=c+1
else:o=o
return r
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('()', 0), ('(())', 0), ('()()()()()', 41), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('(())()', 2), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('((()()))', 1), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('(()(()))', 4), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(())(())', 7), ('()', 0), ('()()()()()', 41), ('(())()', 2), ('()(())', 3), ('()()()', 4), ('(((())))', 0)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("explicit oracle %d" % i, solve(args), expected)
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 |
|---|---|---|---|
| explicit oracle 0 | 1 | 0 | Failed |
| explicit oracle 1 | 3 | 0 | Failed |
| explicit oracle 2 | 56 | 41 | Failed |
| explicit oracle 3 | 3 | 1 | Failed |
| explicit oracle 4 | 7 | 0 | Failed |
| explicit oracle 5 | 7 | 1 | Failed |
| explicit oracle 6 | 7 | 2 | Failed |
| explicit oracle 7 | 7 | 3 | Failed |
SHA-256 / 2e61aae08b1f1513e2abef8fb2b6a93d9e83bbc5906d131627c92b2e09569fa6
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
word=x;n=len(word)//2
from functools import lru_cache
@lru_cache(None)
def count(o,c):
if c>o or o>n:return 0
if o==n and c==n:return 1
return (count(o+1,c) if o<n else 0)+(count(o,c+1) if c<o else 0)
r=0;o=c=0
for ch in word:
if ch==')':
r+=count(o+1,c)
c=c+1
else:o=c+1
return r
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('()', 0), ('(())', 0), ('()()()()()', 41), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('(())()', 2), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('((()()))', 1), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('(()(()))', 4), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(())(())', 7), ('()', 0), ('()()()()()', 41), ('(())()', 2), ('()(())', 3), ('()()()', 4), ('(((())))', 0)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("explicit oracle %d" % i, solve(args), expected)
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 |
|---|---|---|---|
| explicit oracle 0 | 0 | 0 | Passed |
| explicit oracle 1 | 2 | 0 | Failed |
| explicit oracle 2 | 41 | 41 | Passed |
| explicit oracle 3 | 1 | 1 | Passed |
| explicit oracle 4 | 6 | 0 | Failed |
| explicit oracle 5 | 5 | 1 | Failed |
| explicit oracle 6 | 5 | 2 | Failed |
| explicit oracle 7 | 5 | 3 | Failed |
SHA-256 / 9decf17cccab561c09582b26c8d36927ab9bd0365e054b92eface84634941a8c
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
word=x;n=len(word)//2
from functools import lru_cache
@lru_cache(None)
def count(o,c):
if c>o or o>n:return 0
if o==n and c==n:return 1
return (count(o+1,c) if o<n else 0)+(count(o,c+1) if c<o else 0)
r=0;o=c=0
for ch in word:
if ch==')':
r+=count(o+1,c)
c=c+1
else:o=o+1
return r
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('()', 0), ('(())', 0), ('()()()()()', 41), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('(())()', 2), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('((()()))', 1), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('(()(()))', 4), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(())(())', 7), ('()', 0), ('()()()()()', 41), ('(())()', 2), ('()(())', 3), ('()()()', 4), ('(((())))', 0)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("explicit oracle %d" % i, solve(args), expected)
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 |
|---|---|---|---|
| explicit oracle 0 | 0 | 0 | Passed |
| explicit oracle 1 | 0 | 0 | Passed |
| explicit oracle 2 | 41 | 41 | Passed |
| explicit oracle 3 | 1 | 1 | Passed |
| explicit oracle 4 | 0 | 0 | Passed |
| explicit oracle 5 | 1 | 1 | Passed |
| explicit oracle 6 | 2 | 2 | Passed |
| explicit oracle 7 | 3 | 3 | Passed |
SHA-256 / 2fb527741bc7295650a047b1f17b67234e8cde0e79719fa63bc5748c60761ec4
Verification & scope
A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. 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:39:24.533126+00:00.
Case digest / d78fd62ee4e2d9202bf90825817c03b6e038d89fdf27607880468f0046e136b4