#!/usr/bin/env python3
"""Catalan 数漫游:为什么 14 是 14。

第 4 个 Catalan 数 C4 = 14,它同时等于 1²+2²+3²。
本脚本实测:C_n 递推、Dyck 词枚举(山路)、以及花园内部彩蛋
——卡普雷卡常数 6174 = 14 × 21²。
"""


def catalan(n: int) -> int:
    """递推计算第 n 个 Catalan 数:C_{k+1} = C_k · 2(2k+1)/(k+2)"""
    c = 1  # C0
    for k in range(n):
        c = c * 2 * (2 * k + 1) // (k + 2)
    return c


def dyck_words(n: int) -> list[str]:
    """枚举半长度 n 的所有 Dyck 词(合法括号串),个数应为 C_n。"""
    res: list[str] = []

    def backtrack(s: str, opened: int, closed: int) -> None:
        if len(s) == 2 * n:
            res.append(s)
            return
        if opened < n:
            backtrack(s + "(", opened + 1, closed)
        if closed < opened:
            backtrack(s + ")", opened, closed + 1)

    backtrack("", 0, 0)
    return res


def draw_mountain(word: str) -> str:
    """把一条 Dyck 词画成山路:上坡 /,下坡 \。"""
    level = 0
    rows = []
    for ch in word:
        if ch == "(":
            rows.append("  " * level + "/")
            level += 1
        else:
            level -= 1
            rows.append("  " * level + "\\")
    return "\n".join(rows)


def divisor_count(n: int) -> int:
    return sum(1 for d in range(1, n + 1) if n % d == 0)


if __name__ == "__main__":
    print("== Catalan 数列 C0..C7 ==")
    seq = [catalan(i) for i in range(8)]
    print(seq)
    assert seq[4] == 14, "C4 应为 14"
    print(f"C4 = {seq[4]}  ✅ 第 4 个 Catalan 数是 14")

    print("\n== 14 的双重身份 ==")
    assert 1 + 4 + 9 == 14
    print("1² + 2² + 3² = 14  ✅ 前三个平方数之和")
    assert divisor_count(14) == divisor_count(15) == 4
    print("d(14) = d(15) = 4  ✅ 14 与 15 因数个数相同(都是 4 个)")

    print("\n== Dyck 词:半长度 4 的山路 ==")
    words = dyck_words(4)
    print(f"共 {len(words)} 条,应为 C4 = 14  ✅" if len(words) == 14 else f"数量不对:{len(words)}")
    for w in words:
        print(" ", w)

    print("\n== 山路长这样(取最高的那座山) ==")
    print(draw_mountain("(((())))"))

    print("\n== 花园彩蛋:卡普雷卡常数 ==")
    k = 6174
    assert k == 14 * 21 * 21
    print(f"{k} = 14 × 21²  ✅ 数字黑洞 6174 恰好是 14 的倍数")
    assert catalan(5) == 42
    print(f"C5 = {catalan(5)}  ✅ 14 的下一个 Catalan 数是 42——第 13 个素数是 41,41 和 42 正好手拉手")

    print("\n全部断言通过。")