FA-15201 / Numerics / Open access
Dyck word ranking: closing depth update · case 01
The exact dyck word ranking result violates the stated contract at closing depth update.
ROOT CAUSE
The closing depth update step uses c instead of c+1.
VERIFIED REPAIR
Use c+1 at the closing depth update step.
Unsuccessful approach: The partial repair o+1 still violates the closing 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
else:o=o+1
return r
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('(())(())', 7), ('()', 0), ('()()()()()', 41), ('(())', 0), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2)], [('(())()()', 8), ('()()()()', 13), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()(())', 12), ('((())())()', 11), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('()()()()', 13), ('(()()(()))', 18), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('((())(()))', 9), ('(()())(())', 21), ('()', 0), ('()()()()()', 41), ('(()())', 1), ('(())()', 2), ('()(())', 3), ('()()()', 4)]]
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 | 8 | 7 | Failed |
| explicit oracle 1 | 0 | 0 | Passed |
| explicit oracle 2 | 48 | 41 | Failed |
| explicit oracle 3 | 0 | 0 | Passed |
| explicit oracle 4 | 1 | 1 | Passed |
| explicit oracle 5 | 0 | 0 | Passed |
| explicit oracle 6 | 1 | 1 | Passed |
| explicit oracle 7 | 2 | 2 | Passed |
SHA-256 / ff7eb206349da1a03c9f07cbd14265b57bd4377b31a74614ea642d0e7111ffd0
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=o+1
else:o=o+1
return r
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('(())(())', 7), ('()', 0), ('()()()()()', 41), ('(())', 0), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2)], [('(())()()', 8), ('()()()()', 13), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()(())', 12), ('((())())()', 11), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('()()()()', 13), ('(()()(()))', 18), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('((())(()))', 9), ('(()())(())', 21), ('()', 0), ('()()()()()', 41), ('(()())', 1), ('(())()', 2), ('()(())', 3), ('()()()', 4)]]
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 | 5 | 7 | Failed |
| explicit oracle 1 | 0 | 0 | Passed |
| explicit oracle 2 | 36 | 41 | Failed |
| explicit oracle 3 | 0 | 0 | Passed |
| explicit oracle 4 | 1 | 1 | Passed |
| explicit oracle 5 | 0 | 0 | Passed |
| explicit oracle 6 | 1 | 1 | Passed |
| explicit oracle 7 | 2 | 2 | Passed |
SHA-256 / 9d1675a567882579d60ff50780ee0066aae081a30cc0aec988356cf6fb80c47f
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 = [[('(())(())', 7), ('()', 0), ('()()()()()', 41), ('(())', 0), ('()()', 1), ('((()))', 0), ('(()())', 1), ('(())()', 2)], [('(())()()', 8), ('()()()()', 13), ('()', 0), ('()()()()()', 41), ('()((()))', 9), ('()(()())', 10), ('()(())()', 11), ('()()(())', 12)], [('()()(())', 12), ('((())())()', 11), ('()', 0), ('()()()()()', 41), ('((()))(())', 12), ('((()))()()', 13), ('(()((())))', 14), ('(()(()()))', 15)], [('()()()()', 13), ('(()()(()))', 18), ('()', 0), ('()()()()()', 41), ('()((()()))', 29), ('()((())())', 30), ('()((()))()', 31), ('()(()(()))', 32)], [('((())(()))', 9), ('(()())(())', 21), ('()', 0), ('()()()()()', 41), ('(()())', 1), ('(())()', 2), ('()(())', 3), ('()()()', 4)]]
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 | 7 | 7 | Passed |
| explicit oracle 1 | 0 | 0 | Passed |
| explicit oracle 2 | 41 | 41 | Passed |
| explicit oracle 3 | 0 | 0 | Passed |
| explicit oracle 4 | 1 | 1 | Passed |
| explicit oracle 5 | 0 | 0 | Passed |
| explicit oracle 6 | 1 | 1 | Passed |
| explicit oracle 7 | 2 | 2 | Passed |
SHA-256 / 9e7bf295362e14e0af446dfd4c35ace05e7d59e1e6ab8e2805bd80cc415fb222
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.532509+00:00.
Case digest / ff5d8f4a6b1c1676ed7010f1926163421edd4a8a31048cfd79746e10131f468a