"""dualn.py -- the two ends of a base of degree n: which ideals does span
j hide?

QUESTION. dualdeg.py's setting: f monic of degree n, q = |a_0| >= 2,
O = Z[x]/(f), digits 0, ..., q - 1, T_j = {sum_(k<j) d_k beta^k}. Span
j hides I iff every nonzero character chi of O/I has some k < j with
beta^k chi dead (chi(beta^k) != 0, q chi(beta^k) = 0). The colon law is
a degree-2 law, and H1 (for some k <= j, q beta^(j-k) in I and 1, ...,
beta^(k-1) span O/(I : beta^(j-k))) misses 84 cubic pairs, every one
hidden. Which law in ideal terms holds at every degree?

SECTION M (a read, no prediction). Every H1 miss printed whole: the
base, the ideal's row HNF and index, for each k <= j the two halves of
H1 (q beta^(j-k) in I; 1, ..., beta^(k-1) span O/(I : beta^(j-k))) and
the colon's index, and the l-primary parts I_l (the ideal over I of
index the l-part of [O : I]) with span j's count and H1 at each
(run with --misses). It read: at q = 6 all 40 at index 36 = 6^2, j =
2, each l-part meeting H1 at its own k; at q = 4 and 2 one prime, a k
with q beta^(j-k) in I never also spanning; 24 of the q = 4 ones at
N = q^j.

THE CHAIN LAW C (frozen before its code). G = O/I, g_k = beta^k mod
I. S grows from the empty set by any k < j with q g_k in G_S, the
subgroup the g_s, s in S, generate; C holds iff G_S reaches G.
  (i) Greedy is the whole search: q g_k in G_S survives S growing.
  (ii) IF. chi != 0; at the first step whose G_S chi is not zero on,
      chi(g) != 0 for the g added, and q g lies in the earlier G_S,
      so q chi(g) = 0: beta^k chi is dead, span j hides I.
  (iii) ONLY IF at N = q^j. The sum of the D g_k is then a direct
      factorization of G by the cyclic sets {0, g, ..., (q - 1) g},
      so one D g_k is a subgroup (Hajos, Math. Z. 47 (1942) 427-467,
      for cyclic sets of any length; Corradi and Szabo, Comment. Math.
      Univ. Carolin. 51 (2010), Theorem 1): q g_k = 0, and G/<g_k> is
      factored directly by the other images; induction.
  (iv) C contains H1: with H1's k, beta^(j-k), ..., beta^(j-1) enter
      first and generate (beta^(j-k) O + I)/I; on the quotient O/(I +
      beta^(j-k) O) the chain of O/beta^(j-k) O, where T_(j-k) is
      complete, by (iii), maps on. With the quadratic only if (hidden
      implies the colon law, H1 at k = 1), C is exact at degree 2.
  (v) N < q^j, a multiple factorization: C may fail. At q = 2 with
      O/I = (Z/4)^2 and I + 2O the F_4 prime, beta is a unit mod I + 2O, no
      g_k lies in 2G, and C fails at its first step.

PREDICTIONS (frozen). C0 the 100 quadratic bases of dualdeg.py's
sweep: C = hidden, 0 off. P1 C true and unhidden: 0 at every cubic
base. P2 C = hidden at every pair with N = q^j. P3 H1 true and C false:
0. P4 the misses (hidden, C false) only at N < q^j, H1's 12 at q = 2
among them, H1's other 72 repaired. PLANT: the step test 2q g_k in G_S
must break P1. KILL: P1, P2 or P3 off kills the run; C as the law at
degree n dies at one P4 miss, expected at the 12.

FINDINGS (entered after the run, from its printed output).
  C0 38960 pairs, 17144 live, 9085 hidden: C off 0.
  P1 0 over the 24966 pairs; the plant 3346. P2 0 off over the 4428 complete pairs of the
     12626 live. P3 0.
  P4 12 misses, none at N = q^j, exactly H1's 12 at q = 2; the other
     72 of H1's 84 repaired. The 12 are Q^2 (j = 6 and 7) and 2Q (j =
     7), Q = (2, beta^2 + beta + 1), at x^3 + x^2 + x +/- 2 and
     x^3 - x^2 + x +/- 2: multiple factorizations of O/I by the sets
     {0, beta^k}, k < j, with no chain.
  K  C dies as the law at degree n, at the 12 predicted; it is a
     theorem as a sufficient condition at every degree and as a
     criterion at N = q^j, and, by the quadratic only if, exact at every
     quadratic pair. At all 12 every g_k, k < j, has order 4 and the
     chain stops at its first step, |G_S| = 1. Toy scale: q^J <= 128
     cubic, 10^4 quadratic.

RUN RECORD. 61.8 s, 44.2 MB under a memory guard. With the findings
as checks (the orders and |G_S| at the 12 added): 6/6, 63.9 s, 45.3 MB.
"""

import sys
import time

from dualdeg import powers, ideals, tiles, hidden_by_count, mul, fmt

CHECKS = []


def check(name, ok, detail=""):
    CHECKS.append(bool(ok))
    print(f"  {'PASS' if ok else 'FAIL'}  {name}" +
          (f"  ({detail})" if detail else ""))


def primes_of(m):
    out, p = [], 2
    while m > 1:
        if m % p == 0:
            out.append(p)
            while m % p == 0:
                m //= p
        p += 1
    return out


class Base:
    def __init__(self, a, points=128):
        self.a, self.n, self.q = a, len(a), abs(a[0])
        J = 0
        while self.q ** (J + 1) <= points:
            J += 1
        self.J = J
        self.pw = powers(a, J + 1)
        self.Is = ideals(a, self.q ** J)
        self.T = tiles(a, self.q, J, self.pw)
        self.cq = tuple(self.q * x for x in self.pw[0])

    def colon(self, L, i):
        ks = [K for K in self.Is if all(mul(self.pw[i], r, self.a) in L
                                        for r in K.rows())]
        return min(ks, key=lambda K: K.N)

    def spans(self, K, k):
        n = self.n
        gens = [K.key(self.pw[i]) for i in range(k)]
        seen = {tuple([0] * n)}
        frontier = list(seen)
        while frontier:
            nxt = []
            for v in frontier:
                for g in gens:
                    w = K.key(tuple(x + y for x, y in zip(v, g)))
                    if w not in seen:
                        seen.add(w)
                        nxt.append(w)
            frontier = nxt
        return len(seen) == K.N

    def split(self, L, j):
        """For k = 1..j: (q beta^(j-k) in L, span, index of the colon)."""
        out = []
        for k in range(1, j + 1):
            i = j - k
            K = self.colon(L, i)
            out.append((mul(self.pw[i], self.cq, self.a) in L,
                        self.spans(K, k), K.N))
        return out

    def h1(self, L, j):
        return any(a_ and b_ for a_, b_, _ in self.split(L, j))

    def part(self, L, l):
        e = 1
        while L.N % (l ** e) == 0:
            e += 1
        le = l ** (e - 1)
        ps = [K for K in self.Is if K.N == le
              and all(r in K for r in L.rows())]
        assert len(ps) == 1
        return ps[0]


def cubic_bases():
    for q in range(2, 7):
        for c in (q, -q):
            for a2 in range(-2, 3):
                for a1 in range(-2, 3):
                    yield (c, a1, a2)


def section_misses():
    print("M  every H1 miss, printed whole")
    total = 0
    for a in cubic_bases():
        B = Base(a)
        for L in B.Is:
            for j in range(1, B.J + 1):
                if (B.q ** j) % L.N:
                    continue
                hid = hidden_by_count(L, B.T[j])
                if hid == B.h1(L, j):
                    continue
                total += 1
                sp = B.split(L, j)
                ks = " ".join(f"k{k + 1}:{'q' if x else '-'}"
                              f"{'s' if y else '-'}{N}"
                              for k, (x, y, N) in enumerate(sp))
                parts = []
                for l in primes_of(L.N):
                    P = B.part(L, l)
                    parts.append(f"{l}:{P.N} hid "
                                 f"{int(hidden_by_count(P, B.T[j]))} h1 "
                                 f"{int(B.h1(P, j))}")
                print(f"  {fmt(a):22s} q {B.q} j {j} N {L.N:3d} "
                      f"d {L.d} H {[r[1:] for r in L.H[:-1]]} "
                      f"hid {int(hid)} | {ks} | {'; '.join(parts)}")
    print(f"  {total} misses")


def addv(u, v):
    return tuple(x + y for x, y in zip(u, v))


def chain(B, L, mult=1):
    """C at j = 1..J: the greedy closure of S, adding k < j while
    mult q g_k lies in G_S; returns [|G_S| at j] for j = 0..J, C at j
    being |G_S| = N."""
    zero = L.key(tuple([0] * B.n))
    H = {zero}
    used = set()
    out = [1]
    for j in range(1, B.J + 1):
        grew = True
        while grew:
            grew = False
            for k in range(j):
                if k in used:
                    continue
                qg = L.key(tuple(mult * B.q * x for x in B.pw[k]))
                if qg in H:
                    used.add(k)
                    g = L.key(B.pw[k])
                    if g not in H:
                        new, x = set(H), g
                        while x not in H:
                            new |= {L.key(addv(h, x)) for h in H}
                            x = L.key(addv(x, g))
                        H = new
                    grew = True
        out.append(len(H))
    return out


def order(L, v):
    zero = L.key(tuple(0 for _ in v))
    m, x = 1, L.key(v)
    while x != zero:
        m += 1
        x = L.key(tuple(m * y for y in v))
    return m


def sweep(bases, points, h1=False):
    """Per pair (L, j), j >= 1: hidden, C, the plant, live, H1."""
    rows = []
    for a in bases:
        B = Base(a, points)
        for L in B.Is:
            c = chain(B, L)
            cp = chain(B, L, 2)
            for j in range(1, B.J + 1):
                hid = hidden_by_count(L, B.T[j])
                live = (B.q ** j) % L.N == 0
                rows.append(dict(a=a, q=B.q, N=L.N, j=j, hid=hid,
                                 c=c[j] == L.N, cp=cp[j] == L.N,
                                 reach=c[j], live=live, full=L.N == B.q ** j,
                                 h1=B.h1(L, j) if h1 and live else None,
                                 L=L))
    return rows


def quad_bases():
    out = [(q, p) for q in range(2, 13) for p in range(-1, q + 1)]
    return out + [(17, 8)]


def section_chain():
    print()
    print("C0 the positive control: the 100 quadratic bases, q^J <= 10^4")
    rows = sweep(quad_bases(), 10 ** 4)
    live = [r for r in rows if r["live"]]
    off = sum(r["c"] != r["hid"] for r in rows)
    print(f"  pairs {len(rows)}, live {len(live)}, hidden "
          f"{sum(r['hid'] for r in live)}, C off {off}")
    check("C0 C = hidden at every quadratic pair", off == 0 and
          (len(rows), len(live), sum(r["hid"] for r in live)) ==
          (38960, 17144, 9085), f"{off} off")
    print()
    print("P  the 250 cubic bases, q^J <= 128")
    rows = sweep(cubic_bases(), 128, h1=True)
    live = [r for r in rows if r["live"]]
    p1 = sum(r["c"] and not r["hid"] for r in rows)
    p1p = sum(r["cp"] and not r["hid"] for r in rows)
    full = [r for r in live if r["full"]]
    p2 = sum(r["c"] != r["hid"] for r in full)
    p3 = sum(r["h1"] and not r["c"] for r in live)
    miss = [r for r in live if r["hid"] and not r["c"]]
    print(f"  pairs {len(rows)}, live {len(live)}, hidden "
          f"{sum(r['hid'] for r in live)}, complete (N = q^j) {len(full)}")
    print(f"  P1 C true and unhidden: {p1}; plant (2q) {p1p}")
    print(f"  P2 off at N = q^j: {p2}")
    print(f"  P3 H1 true and C false: {p3}")
    h1miss = [r for r in live if r["hid"] and not r["h1"]]
    print(f"  P4 misses (hidden, C false): {len(miss)}, at N = q^j "
          f"{sum(r['full'] for r in miss)}; H1's misses {len(h1miss)}, "
          f"of them C false {sum(not r['c'] for r in h1miss)}")
    names = {}
    for a in sorted({r["a"] for r in miss}):
        B = Base(a, 128)
        Q = [K for K in B.Is if K.N == 4 and (2, 0, 0) in K
             and (1, 1, 1) in K]
        Qr = Q[0].rows()
        sq = [mul(u, v, a) for u in Qr for v in Qr]
        Q2 = [K for K in B.Is if K.N == 16 and all(s in K for s in sq)]
        twoQ = [K for K in B.Is if K.N == 32
                and all(tuple(2 * x for x in u) in K for u in Qr)]
        names[a] = (len(Q), Q2, twoQ)
    named = []
    for r in miss:
        L = r["L"]
        nq, Q2, twoQ = names[r["a"]]
        name = ("Q^2" if any(K.rows() == L.rows() for K in Q2) else
                "2Q" if any(K.rows() == L.rows() for K in twoQ) else "?")
        B = Base(r["a"], 128)
        ords = sorted({order(L, B.pw[k]) for k in range(r["j"])})
        named.append((name, r["j"], r["reach"], ords))
        print(f"    {fmt(r['a']):22s} q {r['q']} j {r['j']} N {r['N']:3d}"
              f" d {L.d} H {[x[1:] for x in L.H[:-1]]}  I = {name}"
              f" (Q found {nq}), |G_S| {r['reach']}, orders of g_k {ords}")
    check("P1 C true and unhidden: 0; the plant fires",
          p1 == 0 and p1p == 3346 and len(rows) == 24966,
          f"{p1} over {len(rows)}, plant {p1p}")
    check("P2 C = hidden at every complete pair",
          p2 == 0 and len(full) == 4428 and len(live) == 12626,
          f"{p2} off over {len(full)} of {len(live)}")
    check("P3 H1 true and C false: 0", p3 == 0, f"{p3}")
    check("P4 the 12 misses: Q^2 or 2Q, none complete, H1's 84 hold "
          "them", len(miss) == 12 and not any(r["full"] for r in miss)
          and len(h1miss) == 84
          and sum(not r["c"] for r in h1miss) == 12
          and all(nm in ("Q^2", "2Q") for nm, _, _, _ in named))
    check("P4 at every miss the chain stops at its first step, each g_k "
          "of order 4", all(rc == 1 and o == [4] for _, _, rc, o in named))
    return off, p1, p1p, p2, p3, miss


def main():
    t0 = time.time()
    if "--misses" in sys.argv:
        section_misses()
    section_chain()
    print()
    print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass, "
          f"{time.time() - t0:.1f} s")
    return 0 if all(CHECKS) else 1


if __name__ == "__main__":
    sys.exit(main())