FA-15211 / Numerics / Open access
Dyck word ranking: balanced word rank origin · case 01
The exact dyck word ranking result violates the stated contract at balanced word rank origin.
ROOT CAUSE
The balanced word rank origin step uses r+1 instead of r.
VERIFIED REPAIR
Use r at the balanced word rank origin step.
Unsuccessful approach: The partial repair max(0,r-1) still violates the balanced word rank origin 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+1
return r+1
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('()', 0), ('()()', 1), ('()()()()()', 41), ('(())', 0), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('()(())', 3), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('((())())', 2), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('(()()())', 5), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(())()()', 8), ('()', 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 | 2 | 1 | Failed |
| explicit oracle 2 | 42 | 41 | Failed |
| explicit oracle 3 | 1 | 0 | Failed |
| explicit oracle 4 | 1 | 0 | Failed |
| explicit oracle 5 | 2 | 1 | Failed |
| explicit oracle 6 | 3 | 2 | Failed |
| explicit oracle 7 | 4 | 3 | Failed |
SHA-256 / 334760c7068180ddff82effa752d73e7356c410ae0c852b2dcaa79d48758b983
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=o+1
return max(0,r-1)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('()', 0), ('()()', 1), ('()()()()()', 41), ('(())', 0), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('()(())', 3), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('((())())', 2), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('(()()())', 5), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(())()()', 8), ('()', 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 | 1 | Failed |
| explicit oracle 2 | 40 | 41 | Failed |
| explicit oracle 3 | 0 | 0 | Passed |
| explicit oracle 4 | 0 | 0 | Passed |
| explicit oracle 5 | 0 | 1 | Failed |
| explicit oracle 6 | 1 | 2 | Failed |
| explicit oracle 7 | 2 | 3 | Failed |
SHA-256 / 9765a95814dc78028a1728bb538550543c29316306312e90778bc1053597e1b3
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), ('()()', 1), ('()()()()()', 41), ('(())', 0), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('()(())', 3), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('((())())', 2), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('(()()())', 5), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(())()()', 8), ('()', 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 | 1 | 1 | Passed |
| explicit oracle 2 | 41 | 41 | Passed |
| explicit oracle 3 | 0 | 0 | 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 / 185802b867dfbba9c97333fab66e51024c8382d09b8395f555dc090d4c71ef66
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.564516+00:00.
Case digest / e602a064848e3ba10616974aef7d42ab894ebb3a20f450b536e92b8deb71730c