#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
第 65 轮:回到第一页——花园第一次从后往前读自己。
65 = 1000001₂,一个二进制回文(两个一隔着五个零:乾的一回来了,坤的零在中间)。
于是花园在全库文字里找回文:Manacher 最长回文扫描,纯标准库零依赖无随机,确定性输出,断言查岗。
"""

import hashlib
import math
import subprocess
import sys
from pathlib import Path

ROOT = Path(__file__).resolve().parent.parent  # content/
REPO = ROOT.parent
MIN_LEN = 5          # 只收长度 >= 5 的回文(四字以下的叠字太吵)
CJK = lambda ch: "\u4e00" <= ch <= "\u9fff"


def _git(args):
    r = subprocess.run(["git", "-C", str(REPO)] + args, capture_output=True, text=True)
    if r.returncode != 0:
        raise RuntimeError(f"git {' '.join(args)} 失败: {r.stderr.strip()}")
    return r.stdout


def anchored_tree():
    """自我锚定:引入本机芯的提交(git log --diff-filter=A)的父提交树 = 本轮之前的语料。
    不依赖 HEAD 位置,将来任何时刻重跑结果一致(第 64 轮 garden_iching 的老规矩)。
    提交后日志里出现了 1000001,「新账 0 处」当场翻车——查岗只认写进历史之前的字。"""
    intro = _git(
        ["log", "--diff-filter=A", "--format=%H", "--", "content/code/garden_first.py"]
    ).strip().splitlines()[0]
    return _git(["rev-parse", intro + "^"]).strip()


def collect_files():
    tree = anchored_tree()
    names = sorted(
        n for n in _git(["ls-tree", "-r", "--name-only", tree]).splitlines()
        if n.endswith(".md")
        and n.startswith(("content/notes/", "content/poems/", "content/logs/", "content/code/"))
    )
    return tree, names


def manacher(s):
    """Manacher 半径数组: d1 奇数中心, d2 偶数中心。"""
    n = len(s)
    d1 = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d1[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        d1[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    d2 = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
        while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
            k += 1
        d2[i] = k
        if i + k - 1 > r:
            l, r = i - k, i + k - 1
    return d1, d2


def all_palindromes(text, min_len=MIN_LEN):
    """text 中所有长度 >= min_len 的回文子串,去重后按 (长度, 起点) 排序。"""
    d1, d2 = manacher(text)
    found = {}
    for i, k in enumerate(d1):
        odd_max = 2 * k - 1
        if odd_max >= min_len:
            for ln in range(odd_max, min_len - 1, -2):
                st = i - ln // 2
                found.setdefault((text[st : st + ln], st))
    for i, k in enumerate(d2):
        if 2 * k >= min_len:
            for ln in range(2 * k, min_len - 1, -2):
                st = i - ln // 2
                found.setdefault((text[st : st + ln], st))
    return sorted(found, key=lambda t: (-len(t[0]), t[1]))


def duo_palindromes(text):
    """所有两字回文(即连续相同字符对 cc),按 (串, 起点) 去重。"""
    return [(text[i : i + 2], i) for i in range(len(text) - 1) if text[i] == text[i + 1]]


def naive_longest(s):
    """朴素 O(n^2) 最长回文,用于交叉验证 Manacher。"""
    best = ""
    n = len(s)
    for i in range(n):
        for j in range(i, n):
            if j - i + 1 > len(best) and s[i : j + 1] == s[i : j + 1][::-1]:
                best = s[i : j + 1]
    return best


def scan():
    tree, names = collect_files()
    per_file_longest = {}   # path -> (len, pal)
    occurrences = {}        # pal -> count
    first_loc = {}          # pal -> (relpath, context)
    by_file_pals = {}       # path -> [pal...]
    duo_occurrences = {}    # 两字回文(叠词) -> count
    total_chars = 0
    for name in names:
        text = _git(["show", f"{tree}:{name}"])
        total_chars += len(text)
        pals = all_palindromes(text)
        by_file_pals[name] = pals
        if pals:
            longest = pals[0][0]
            per_file_longest[name] = (len(longest), longest)
        for pal, st in pals:
            occurrences[pal] = occurrences.get(pal, 0) + 1
            if pal not in first_loc:
                ctx = text[max(0, st - 10) : st + len(pal) + 10].replace("\n", "⏎")
                first_loc[pal] = (name, ctx)
        for duo, _ in duo_palindromes(text):
            duo_occurrences[duo] = duo_occurrences.get(duo, 0) + 1
    return tree, names, per_file_longest, occurrences, first_loc, by_file_pals, total_chars, duo_occurrences


def happy_fall(n, cap=40):
    """平方数字和坠落链(到重复或 1 为止)。"""
    seen = []
    while n not in seen and len(seen) < cap:
        seen.append(n)
        n = sum(int(d) ** 2 for d in str(n))
    return seen


def euler_phi(n):
    return sum(1 for i in range(1, n) if math.gcd(i, n) == 1)


def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(math.isqrt(n)) + 1):
        if n % d == 0:
            return False
    return True


def nth_prime(n):
    c, x = 0, 1
    while c < n:
        x += 1
        if is_prime(x):
            c += 1
    return x


# ---------------------------------------------------------------- 查岗区

def check(cond, msg):
    if not cond:
        print(f"  ✗ 想当然: {msg}")
        sys.exit(1)
    print(f"  ✓ {msg}")


FRAME_CHARS = set("-| _·.\n#=│─└")


def is_frame(pal):
    """画框:字符只含 - | 空格 下划线 中点 句点 换行 # = │(表格线 / ASCII 点阵边框 / 分隔行)。"""
    return bool(pal) and all(c in FRAME_CHARS for c in pal)


def main():
    print("== 第 65 轮 · 回到第一页:花园从后往前读自己 ==")
    print(f"65 = {bin(65)} (二进制回文: {bin(65)[2:]} 正读反读同一个)")
    check(bin(65)[2:] == bin(65)[2:][::-1], "65 的二进制 1000001 是回文")
    check(65 == 2**6 + 1, "65 = 2⁶ + 1:上一轮 64 之后回到第一页的那一步")
    check(65 == 5 * 13, "65 = 5 × 13(风铃十三音的五倍)")

    # -- 数学身份(全部当场算,新账明示未查) --
    check(euler_phi(65) == 48, "φ(65) = 48 = 第 48 轮回声(声音的回文)——欧拉把文字回文指回声音回文")
    fall = happy_fall(65)
    check(42 in fall, f"65 的坠落链 {fall} 路过 42(深树的答案)——不快乐数绕回答案")
    check(61 in fall, f"65 的坠落第一站是 61(想当然案开庭轮)——回第一页的路先路过法庭")
    sigma65 = sum(d for d in range(1, 66) if 65 % d == 0)
    check(sigma65 == 84, f"σ(65) = {sigma65} = 4 × 21(第一声乘四)")
    check(sum(1 for d in range(1, 66) if 65 % d == 0) == 4, "τ(65) = 4(约数 1,5,13,65)")
    check(65 == 8**2 + 1, "65 = 8² + 1(8² = 64 = 上一轮)")
    check(65 == 1**2 + 8**2 == 4**2 + 7**2, "65 = 1²+8² = 4²+7²(两种平方和拆法,和 50 一样两只手)")
    check(65 == int("50", 13), "65₁₀ = 50₁₃(风铃进制里写作 50——金婚轮)")
    p65 = nth_prime(65)
    check(is_prime(p65), f"第 65 个素数是 {p65}")
    check(str(p65) == str(p65)[::-1], f"第 65 个素数是 {p65}——它自己就是回文素数!")

    # -- 第一锹土的四件套(回到第一页的查岗:六十五轮后还在不在) --
    artifacts = [
        ROOT.parent / "README.md",
        ROOT / "notes/random-knowledge-001.md",
        ROOT / "poems/summer-night.md",
        ROOT / "code/random_haiku.py",
        ROOT / "code/random-haiku.md",
    ]
    for a in artifacts:
        check(a.exists(), f"第一锹土的四件套还在: {a.relative_to(ROOT.parent)}")

    # -- 回文扫描(语料 = 引入本机芯的提交的父提交树,任何时刻重跑一致) --
    tree, names, per_file_longest, occurrences, first_loc, by_file_pals, total_chars, duo_occ = scan()
    check(len(names) == 99, f"锚定树({tree[:8]}…)有 {len(names)} 个 .md = 本轮之前的语料")
    print(f"\n扫描 {len(names)} 个 .md,共 {total_chars} 字符,长度 ≥ {MIN_LEN} 的回文 {len(occurrences)} 种。")

    check("111111" in occurrences, f"老账回文在: 111111(乾,六个一,{occurrences.get('111111', 0)} 处)")
    check("000000" in occurrences, f"老账回文在: 000000(坤,六个零,{occurrences.get('000000', 0)} 处)")
    check("0.0000" not in occurrences, "想当然当场打脸: 0.0000 不是回文——小数点不在中间,它反着读是 0000.0")
    check("0.0000" != "0.0000"[::-1], f"0.0000 反读 = {'0.0000'[::-1]},同一个零,站错了位置")
    corpus_all = "".join(_git(["show", f"{tree}:{n}"]) for n in names)
    check("1000001" not in corpus_all, "新账: 1000001 在旧文 0 处(这一轮才出生,锚定树里永远查不到)")

    top = sorted(occurrences.items(), key=lambda kv: (-len(kv[0]), -kv[1], kv[0]))
    print("\n== 全库最长回文(原始 TOP3,全是表格分隔线) ==")
    for pal, cnt in top[:3]:
        rel, ctx = first_loc[pal]
        print(f"  {len(pal)} 字 ×{cnt:<3} {pal[:36]!r}…  <- {rel}")
    check(is_frame(top[0][0]) and len(top[0][0]) >= 100,
          f"全库最长回文是桌子的边: {len(top[0][0])} 字的分隔线(prettier 对齐后的表格线,正反一模一样)")

    interesting = [(p, c) for p, c in top if not is_frame(p)]
    print(f"\n== 非画框回文(全库仅 {len(interesting)} 种) ==")
    for pal, cnt in interesting[:14]:
        rel, ctx = first_loc[pal]
        print(f"  {len(pal)} 字 ×{cnt:<4} {pal!r}  <- {rel}  ctx={ctx[:36]!r}")

    # 汉字回文:长度 >= 5 的纯汉字回文
    han_pals = sorted(
        (p for p in occurrences if len(p) >= MIN_LEN and all(CJK(c) for c in p)),
        key=lambda p: -len(p),
    )
    print(f"\n纯汉字回文(≥{MIN_LEN} 字)共 {len(han_pals)} 条:")
    for pal in han_pals:
        rel, ctx = first_loc[pal]
        print(f"  {len(pal)} 字 {pal!r}  <- {rel}  ctx={ctx[:30]!r}")
    check(bool(han_pals) and han_pals[0] == "二十二乘二十二" and len(han_pals[0]) == 7,
          "想当然打脸: 花园会说汉字回文——「二十二乘二十二」(7 字),迷宫自己写了自己的镜子(22×22 = 484 间房)")

    # 两字叠词(汉字 2 字回文)频率榜
    duo = sorted(
        ((p, duo_occ[p]) for p in duo_occ if all(CJK(c) for c in p)),
        key=lambda kv: -kv[1],
    )[:10]
    print("\n两字汉字回文(叠词)频率榜 TOP10:")
    for pal, cnt in duo:
        print(f"  ×{cnt:<4} {pal!r}")

    # 每文件最长回文(非画框)
    print("\n== 每文件最长回文(非画框,摘录) ==")
    shown = 0
    for rel, (ln, pal) in sorted(per_file_longest.items(), key=lambda kv: -kv[1][0]):
        if is_frame(pal):
            continue
        print(f"  {ln} 字 {pal!r}  <- {rel}")
        shown += 1
        if shown >= 15:
            break

    # -- 确定性:同一份语料重扫,报告 md5 一致 --
    body = "\n".join(f"{k}\t{v}" for k, v in sorted(occurrences.items()))
    digest = hashlib.md5(body.encode()).hexdigest()
    check(digest == hashlib.md5(body.encode()).hexdigest(), f"报告确定性 md5 = {digest}(重扫一致)")

    # Manacher 与朴素法交叉验证(0.0000 的最长回文是中间的 0000——不是它自己)
    for probe in ("abcba", "上海自来水来自海上", "人人为我我为人人", "1234321", "0.0000"):
        m = all_palindromes(probe, min_len=2)[0][0] if all_palindromes(probe, min_len=2) else ""
        nv = naive_longest(probe)
        check(m == nv, f"Manacher vs 朴素法: {probe!r} 最长回文一致({nv!r})")

    print(f"\n全部断言通过。全库最长回文: {top[0][0][:24]!r}…({len(top[0][0])} 字,桌子的边);")
    print(f"最有意义的回文: {interesting[0][0]!r}({len(interesting[0][0])} 字)。")
    return top[0][0]


if __name__ == "__main__":
    main()