FA-15196 / Numerics / Open access
Dyck word ranking: skipped opening subtree · case 01
The exact dyck word ranking result violates the stated contract at skipped opening subtree.
ROOT CAUSE
The skipped opening subtree step uses count(o,c+1) instead of count(o+1,c).
VERIFIED REPAIR
Use count(o+1,c) at the skipped opening subtree step.
Unsuccessful approach: The partial repair count(o,c) still violates the skipped opening subtree 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,c+1)
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), ('()()()()()', 41), ('(())', 0), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('((()))', 0), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('()(())', 3), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('((()()))', 1), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(()(()))', 4), ('()', 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 | 23 | 41 | Failed |
| explicit oracle 2 | 2 | 0 | Failed |
| explicit oracle 3 | 2 | 1 | Failed |
| explicit oracle 4 | 3 | 0 | Failed |
| explicit oracle 5 | 4 | 1 | Failed |
| explicit oracle 6 | 4 | 2 | Failed |
| explicit oracle 7 | 4 | 3 | Failed |
SHA-256 / c20de48cac46e20c5a5870a89aff9e2cf174fcdcf57a97b672a6f9d6f842e575
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,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), ('()()()()()', 41), ('(())', 0), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('((()))', 0), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('()(())', 3), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('((()()))', 1), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(()(()))', 4), ('()', 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 | 64 | 41 | Failed |
| explicit oracle 2 | 2 | 0 | Failed |
| explicit oracle 3 | 3 | 1 | Failed |
| explicit oracle 4 | 3 | 0 | Failed |
| explicit oracle 5 | 5 | 1 | Failed |
| explicit oracle 6 | 6 | 2 | Failed |
| explicit oracle 7 | 7 | 3 | Failed |
SHA-256 / 1ee50d1916428346c3d4c5f70dc2a37c4233094c46f87a6930238b5bf47f4656
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), ('()()()()()', 41), ('(())', 0), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2), ('()(())', 3)], [('(())', 0), ('((()))', 0), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()', 1), ('()(())', 3), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('((()))', 0), ('((()()))', 1), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('(()())', 1), ('(()(()))', 4), ('()', 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 | 41 | 41 | Passed |
| explicit oracle 2 | 0 | 0 | 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 / ab4d8a4c887bc13cea3edda5e7b43f48b04fb2534f85bc36cff6d757e3885a6e
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.346536+00:00.
Case digest / 11ae488e94f1084d76c18ac3687ad41220d3c35a4a181f7ac451225b1e067f21