"""General-p method A: Zorn model, exact HNF, BFS over maximal stable sublattices.
Child finder: (i) 'eig' = common left-eigen functionals (valid when every simple module of
Abar = A/pA is 1-dimensional over F_p; certified by certify()), (ii) 'brute' = all projective
functionals, minimal cyclic submodules of the dual (any module)."""
import numpy as np, itertools, json, sys, time
from zorn import mul, E
from lat import hnf, index_exp, solve_rows
SHAPES={'U':(0,1,7),'Q':(0,1,4,7),'N4':(0,1,5,7),'P5':(0,1,2,6,7),'P6':(0,1,2,4,6,7)}
def gens(S,p):
    if S=='Z': return [[1,0,0,0,0,0,0,1]]+[[p*(i==j) for i in range(8)] for j in range(8)]
    return [E[i] for i in S]+[[p*(i==j) for i in range(8)] for j in range(8) if j not in S]
def mats(g,side='R'): return [[mul(E[i],y) if side=='R' else mul(y,E[i]) for i in range(8)] for y in g]
def mm(A,B,mod): return [[sum(A[i][k]*B[k][j] for k in range(8))%mod for j in range(8)] for i in range(8)]
def order_algebra(M,p,N=7):
    mod=p**N; vec=lambda X:[int(x) for r in X for x in r]
    I=[[int(i==j) for j in range(8)] for i in range(8)]
    H=hnf([vec(I)],64,mod); fr=[I]
    while fr:
        new=[]
        for A in fr:
            for g in M:
                B=mm(A,g,mod); H2=hnf(list(H)+[vec(B)],64,mod)
                if H2!=H: H=H2; new.append(B)
        fr=new
    c=next(c for c in range(N) if all(solve_rows(H,[p**c*(k==j) for j in range(64)]) is not None for k in range(64)))
    return H,c
def certify(M,p):
    """True iff every simple Abar-module is 1-dim over F_p (commutator ideal nilpotent + split)."""
    H,c=order_algebra(M,p)
    mod=p**7
    B=[[ [H[k][8*i+j] for j in range(8)] for i in range(8)] for k in range(64)]
    def coords(X):
        v=solve_rows(H,[x%mod for r in X for x in r]); return np.array([t%p for t in v],dtype=np.int64)
    C=np.zeros((64,64,64),dtype=np.int64)
    for i in range(64):
        for j in range(64): C[i,j]=coords(mm(B[i],B[j],mod))
    def prod(x,y): return np.einsum('i,j,ijk->k',x,y,C)%p
    def span(vs):
        R=[]
        for v in vs:
            v=v.copy()%p
            for r in R:
                c0=np.nonzero(r)[0][0]
                if v[c0]: v=(v-v[c0]*r)%p
            if v.any():
                c0=np.nonzero(v)[0][0]; v=(v*pow(int(v[c0]),-1,p))%p; R.append(v)
        return R
    e=np.eye(64,dtype=np.int64)
    comm=span([(prod(e[i],e[j])-prod(e[j],e[i]))%p for i in range(64) for j in range(i+1,64)])
    I=comm
    while True:
        I2=span(I+[prod(e[k],x) for k in range(64) for x in I]+[prod(x,e[k]) for k in range(64) for x in I])
        if len(I2)==len(I): break
        I=I2
    P=I; nil=False
    for _ in range(66):
        if not P: nil=True;break
        P=span([prod(x,y) for x in P for y in I])
    # split: left-multiplication by each basis element has all eigenvalues in F_p: (L^p-L)^64 = 0
    split=True
    for k in range(64):
        L=np.array([prod(e[k],e[j]) for j in range(64)]).T%p
        Lp=np.linalg.matrix_power(L,1) 
        X=np.eye(64,dtype=np.int64)
        for _ in range(p): X=(X@L)%p
        D=(X-L)%p; Y=np.eye(64,dtype=np.int64)
        for _ in range(7): Y=(Y@Y@D)%p if False else Y
        Z=D.copy()
        for _ in range(6): Z=(Z@Z)%p   # D^(64)
        if Z.any(): split=False;break
    return {'c':c,'dim_commutator_ideal':len(I),'nilpotent':nil,'split':split,'one_dim_simples':nil and split}
# ---------- child finders ----------
def nullspace(A,p):
    """basis of {x : A x = 0} over F_p, A as list of rows (n cols)."""
    A=[list(map(lambda t:int(t)%p,r)) for r in A]; n=len(A[0]) if A else 0
    piv=[];R=[]
    for r in A:
        for c0,pr in zip(piv,R):
            if r[c0]: t=r[c0]; r=[(a-t*b)%p for a,b in zip(r,pr)]
        if any(r):
            c0=next(i for i,x in enumerate(r) if x); inv=pow(r[c0],-1,p); r=[x*inv%p for x in r]
            R=[[(a-q[c0]*b)%p for a,b in zip(q,r)] for q in R]; R.append(r); piv.append(c0)
    free=[j for j in range(n) if j not in piv]; out=[]
    for f in free:
        v=[0]*n; v[f]=1
        for c0,r in zip(piv,R): v[c0]=(-r[f])%p
        out.append(v)
    return out
def common_eigen_functionals(X,p):
    """all phi (up to scalar) with phi X_y = lam_y phi for all y. X: list of 8x8 (row action c -> c X)."""
    # phi as row vector; condition phi (X - lam I) = 0 <=> (X - lam I)^T phi^T = 0
    spaces=[[[int(i==j) for j in range(8)] for i in range(8)]]   # list of bases (rows) of candidate subspaces
    for Xy in X:
        new=[]
        for Bs in spaces:
            for lam in range(p):
                # phi = sum c_k Bs[k]; need sum c_k Bs[k] (Xy - lam I) = 0
                rows=[[sum(Bs[k][i]*(Xy[i][j]-(lam if i==j else 0)) for i in range(8))%p for k in range(len(Bs))] for j in range(8)]
                ns=nullspace(rows,p)
                if ns: new.append([[sum(c[k]*Bs[k][j] for k in range(len(Bs)))%p for j in range(8)] for c in ns])
        spaces=new
    out=[]
    for Bs in spaces:
        d=len(Bs)
        for co in itertools.product(range(p),repeat=d):
            if any(co) and co[next(i for i,x in enumerate(co) if x)]==1:
                out.append([sum(c*Bs[k][j] for k,c in enumerate(co))%p for j in range(8)])
    return out
def action(H,M,p):
    X=[]
    for Mm in M:
        img=[[sum(H[i][k]*Mm[k][j] for k in range(8)) for j in range(8)] for i in range(8)]
        C=[solve_rows(H,r) for r in img]; assert all(c is not None for c in C),'unstable'
        X.append([[t%p for t in r] for r in C])
    return X
def children_eig(H,M,p,MOD):
    X=action(H,M,p); out=[]
    XT=[[[Xy[j][i] for j in range(8)] for i in range(8)] for Xy in X]   # need X phi = lam phi (column phi)
    for phi in common_eigen_functionals(XT,p):
        ker=nullspace([phi],p)
        rows=[[sum(c[k]*H[k][j] for k in range(8)) for j in range(8)] for c in ker]+[[p*x for x in r] for r in H]
        out.append(hnf(rows,8,MOD))
    return out
def batch_rref(Mt,p):
    A=Mt.copy()%p; B,m,n=A.shape; rank=np.zeros(B,int); ar=np.arange(B); inv=np.array([0]+[pow(i,-1,p) for i in range(1,p)])
    for c in range(n):
        cand=(A[:,:,c]!=0)&(np.arange(m)[None,:]>=rank[:,None]); has=cand.any(1); r=np.argmax(cand,1)
        idx=ar[has]; rr=r[has]; rk=rank[has]
        tmp=A[idx,rr].copy(); A[idx,rr]=A[idx,rk]; A[idx,rk]=tmp
        A[idx,rk]=(A[idx,rk]*inv[A[idx,rk,c]][:,None])%p
        f=A[idx,:,c].copy(); f[np.arange(len(idx)),rk]=0
        A[idx]=(A[idx]-f[:,:,None]*A[idx,rk][:,None,:])%p
        rank[idx]+=1
    return A[:,:n,:],rank
_PROJ={}
def proj(p):
    if p not in _PROJ:
        _PROJ[p]=np.array([v for v in itertools.product(range(p),repeat=8) if any(v) and v[next(i for i,x in enumerate(v) if x)]==1],dtype=np.int16)
    return _PROJ[p]
def word_basis(X,p):
    basis=[];ech={}
    def insert(Mx):
        v=[int(x)%p for x in Mx.reshape(-1)]
        for i in sorted(ech):
            if v[i]: t=v[i]; v=[(a-t*b)%p for a,b in zip(v,ech[i])]
        if not any(v): return
        i=next(i for i,x in enumerate(v) if x); iv=pow(v[i],-1,p); ech[i]=[x*iv%p for x in v]; basis.append(Mx%p)
    insert(np.eye(8,dtype=np.int64)); s=0
    while s<len(basis):
        e=len(basis)
        for A in basis[s:e]:
            for g in X: insert((A@g)%p)
        s=e
    return np.array(basis)
def children_brute(H,M,p,MOD,chunk=20000):
    X=[np.array(x,dtype=np.int64) for x in action(H,M,p)]
    Wa=word_basis(X,p)   # acts on column functionals: phi -> a phi
    P=proj(p); subs={}
    for s in range(0,len(P),chunk):
        Q=P[s:s+chunk].astype(np.int64)
        imgs=np.einsum('mij,bj->bmi',Wa,Q)%p
        R,rk=batch_rref(imgs,p)
        for b in range(len(Q)):
            key=R[b,:rk[b]].tobytes()
            if key not in subs: subs[key]=(int(rk[b]),R[b,:rk[b]].copy())
    subs=list(subs.values())
    def inside(sm,bg):
        _,r=batch_rref(np.vstack([bg,sm])[None].astype(np.int64),p); return r[0]==len(bg)
    minimal=[s for s in subs if not any(t[0]<s[0] and inside(t[1],s[1]) for t in subs)]
    out=[]
    for d,C in minimal:
        ker=nullspace(C.tolist(),p)
        rows=[[sum(c[k]*H[k][j] for k in range(8)) for j in range(8)] for c in ker]+[[p*x for x in r] for r in H]
        out.append(hnf(rows,8,MOD))
    return out
def run(name,p,mode=None,side='R',verbose=True):
    S=SHAPES[name]; g=gens(S,p); M=mats(g,side)
    cert=certify(M,p); c=cert['c']; MOD=p**(c+3)
    if mode is None: mode='eig' if cert['one_dim_simples'] else 'brute'
    child=children_eig if mode=='eig' else children_brute
    O=hnf([E[i] for i in range(8)],8,MOD); Lam=hnf(g,8,MOD)
    seen={O:0}; fr=[O]; t=time.time()
    while fr:
        nf=[]
        for H in fr:
            for K in child(H,M,p,MOD):
                if all(all(x%p==0 for x in r) for r in K): continue
                if K not in seen: seen[K]=index_exp(K,p); nf.append(K)
        fr=nf
        if verbose: print(name,p,mode,'frontier',len(fr),'total',len(seen),round(time.time()-t,1),flush=True)
    PO={};PL={}; shift=8-len(S)
    for K,k in seen.items():
        PO[k]=PO.get(k,0)+1
        if all(solve_rows(Lam,r) is not None for r in K): PL[k-shift]=PL.get(k-shift,0)+1
    return {'order':name,'p':p,'side':side,'mode':mode,'certificate':cert,'dimS':len(S),'P_O':dict(sorted(PO.items())),'P_Lambda':dict(sorted(PL.items())),'n_primitive':len(seen)}
if __name__=='__main__':
    if sys.argv[1]=='cert':
        for p in map(int,sys.argv[2].split(',')):
            for n in SHAPES:
                t=time.time(); print(n,p,certify(mats(gens(SHAPES[n],p)),p),round(time.time()-t,1),flush=True)
    else:
        names=sys.argv[1].split(','); p=int(sys.argv[2]); mode=sys.argv[3] if len(sys.argv)>3 and sys.argv[3]!='auto' else None
        res=[]
        for n in names:
            r=run(n,p,mode); print(json.dumps(r),flush=True); res.append(r)
            json.dump(res,open(f'results-genp-{"_".join(names)}-p{p}-{mode or "auto"}.json','w'),indent=1)
