#!/usr/bin/env python3
"""Independent finite checks for the word-periodicity / canonicalization unit.
Run with Python 3.10+: python algorithms-word-canon-check.py
No external dependencies. Exhaustive checks supplement, not replace, proofs.
"""
from itertools import product
from math import gcd
import json


def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def primitive_root(s):
    if not s:
        raise ValueError("the empty word has no primitive root")
    p = len(s) - prefix_function(s)[-1]
    if len(s) % p:
        p = len(s)
    return s[:p], len(s) // p


def duval_intervals(s, stats=None):
    n = len(s)
    i = 0
    comparisons = 0
    batches = []
    while i < n:
        start = i
        j, k = i + 1, i
        while j < n:
            comparisons += 1
            if not s[k] <= s[j]:
                break
            comparisons += 1
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        p = j - k
        scanned = s[start:j]
        block = s[start:start+p]
        q, r = divmod(len(scanned), p)
        assert is_lyndon_rotation(block)
        assert scanned == block*q + block[:r]
        out = []
        while i <= k:
            out.append((i, i+p))
            yield (i, i + p)
            i += p
        batches.append({"start": start, "stop_j": j, "stop_k": k,
                        "period": p, "intervals": out,
                        "scanned": scanned, "leftover": s[i:j]})
        assert j-start < 2*(i-start)
    if stats is not None:
        stats.update(comparisons=comparisons, batches=batches)


def minimal_rotation_index(s, stats=None):
    n = len(s)
    if n == 0:
        if stats is not None:
            stats.update(character_pairs=0, trace=[])
        return 0
    i, j, k = 0, 1, 0
    pairs = 0
    trace = []
    while i < n and j < n and k < n:
        x = s[(i + k) % n]
        y = s[(j + k) % n]
        pairs += 1
        if x == y:
            k += 1
            continue
        old = (i, j, k)
        if x > y:
            losing = (i, min(n, i+k+1))
            for t in range(k+1):
                if i+t < n:
                    assert rotation(s, i+t) > rotation(s, (j+t) % n)
            i += k + 1
            if i == j:
                i += 1
        else:
            losing = (j, min(n, j+k+1))
            for t in range(k+1):
                if j+t < n:
                    assert rotation(s, j+t) > rotation(s, (i+t) % n)
            j += k + 1
            if i == j:
                j += 1
        trace.append({"before": old, "chars": (x, y),
                      "discarded_half_open": losing, "after": (i, j, 0)})
        k = 0
    if stats is not None:
        stats.update(character_pairs=pairs, trace=trace, terminal=(i,j,k))
    return min(i, j)


def rotation(s, k):
    return s[k:] + s[:k]


def is_lyndon_rotation(s):
    return bool(s) and all(s < rotation(s, k) for k in range(1,len(s)))


def periods_oracle(s):
    return [p for p in range(1, len(s)+1)
            if all(s[i] == s[i+p] for i in range(len(s)-p))]


def root_oracle(s):
    for p in range(1,len(s)+1):
        if len(s)%p == 0 and s[:p]*(len(s)//p) == s:
            return s[:p],len(s)//p
    raise AssertionError("nonempty input expected")


def cfl_cut_oracle(s):
    """Enumerate every cut set; recognizes factors via explicit rotations."""
    if not s:
        return [()]
    answers=[]
    for mask in range(1 << (len(s)-1)):
        ends = [0] + [i+1 for i in range(len(s)-1) if mask >> i & 1] + [len(s)]
        parts=tuple(s[a:b] for a,b in zip(ends,ends[1:]))
        if all(is_lyndon_rotation(t) for t in parts) and all(a>=b for a,b in zip(parts,parts[1:])):
            answers.append(parts)
    return answers


def words(alphabet,max_length):
    for n in range(max_length+1):
        for a in product(alphabet,repeat=n):
            yield ''.join(a)


def check():
    counts={"words":0,"unique_cfl_cut_checks":0,"fine_wilf_pairs":0,
            "duval_comparison_bound":0,"rotation_elimination_checks":0}
    corpus=set(words('abc',8)) | set(words('ab',12))
    for s in sorted(corpus,key=lambda t:(len(t),t)):
        n=len(s);counts["words"]+=1
        ds={};ints=list(duval_intervals(s,ds)); parts=tuple(s[a:b] for a,b in ints)
        assert ''.join(parts)==s
        assert all(is_lyndon_rotation(t) for t in parts)
        assert all(a>=b for a,b in zip(parts,parts[1:]))
        assert ds["comparisons"] < 4*n if n else ds["comparisons"]==0
        counts["duval_comparison_bound"]+=1
        ms={};a=minimal_rotation_index(s,ms)
        if not s:
            assert a==0 and parts==()
            continue
        rots=[rotation(s,k) for k in range(n)]
        minimum=min(rots);expected=[k for k,v in enumerate(rots) if v==minimum]
        assert a==expected[0],(s,a,expected)
        assert ms['character_pairs'] <= 4*n
        counts["rotation_elimination_checks"]+=1
        root,power=primitive_root(s)
        assert (root,power)==root_oracle(s)
        assert expected==list(range(a,n,len(root)))
        assert len(set(rots))==len(root)
        assert is_lyndon_rotation(minimum[:len(root)])
        ps=periods_oracle(s)
        bs=[b for b in range(n) if s[:b]==s[n-b:]]
        assert sorted(n-b for b in bs)==ps
        assert n-prefix_function(s)[-1]==min(ps)
        assert is_lyndon_rotation(s)==all(s<s[k:] for k in range(1,n))
        for p in ps:
            for q in ps:
                if n >= p+q-gcd(p,q):
                    assert gcd(p,q) in ps,(s,p,q)
                    counts['fine_wilf_pairs']+=1
        if n<=7:
            answers=cfl_cut_oracle(s)
            assert answers==[parts],(s,parts,answers)
            counts['unique_cfl_cut_checks']+=1
    assert periods_oracle('abaaba')==[3,5,6]
    assert 2 not in periods_oracle('aaabaaa')
    assert {4,6}.issubset(periods_oracle('aaabaaa'))
    assert primitive_root('abababa')==('abababa',1)
    assert is_lyndon_rotation('aabaabab')
    assert not is_lyndon_rotation('aba')
    s='bbaabbaabbaa';ds={};ints=list(duval_intervals(s,ds));ms={}
    a=minimal_rotation_index(s,ms);r,e=primitive_root(s)
    capstone={"input":s,"prefix_function":prefix_function(s),"root":r,"exponent":e,
              "cfl_intervals":ints,"cfl_factors":[s[a:b] for a,b in ints],
              "duval":ds,"minimum_index":a,"minimum_rotation":rotation(s,a),
              "all_minimum_indices":list(range(a,len(s),len(r))),"rotation":ms}
    return {"status":"PASS","counts":counts,"capstone":capstone,
            "scope":"all ternary words through length 8 and binary words through length 12; every cut checked through length 7"}

if __name__=='__main__':
    if not __debug__:
        raise SystemExit('Run without -O: this audit requires assertions to be enabled.')
    print(json.dumps(check(),ensure_ascii=False,indent=2))