"""Method A: Zorn model, exact HNF lattices, BFS over maximal stable sublattices.
Counts one-sided (right or left) ideals of 3-local octonion orders Lambda_S = preimage of a
subalgebra S of O/3O (O = Zorn(Z_3), maximal), i.e. Z_3-lattices L in Lambda with L*Lambda <= L.
Z(x) = P_Lambda(x) + x^{dim S} P_O(x)/(1-x^8),  x = 3^{-s}  (see note)."""
import numpy as np, json, sys, time, itertools
from zorn import mul, E, norm
from lat import hnf, index_exp, solve_rows
p=3
ORDERS={'Z':'Z',            # Z_3 + 3O
        'D':(0,7),'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),'O':tuple(range(8))}
def order_gens(S):
    if S=='Z': return [[1,0,0,0,0,0,0,1]]+[[3*(i==j) for i in range(8)] for j in range(8)]
    return [E[i] for i in S]+[[3*(i==j) for i in range(8)] for j in range(8) if j not in S]
def dimS(S): return 1 if S=='Z' else len(S)
def act_mats(gens,side):
    # row-vector convention: x -> x*y (side R) has matrix M[i]=mul(e_i,y)
    out=[]
    for y in gens:
        M=[mul(E[i],y) if side=='R' else mul(y,E[i]) for i in range(8)]
        out.append(M)
    return out
def algebra_c(mats,N=8):
    """smallest c with p^c M_8(Z_p) inside the Z_p-algebra generated by mats (and 1)."""
    mod=p**N
    def vec(M): return [int(x) for r in M for x in r]
    def mm(A,B): return [[sum(A[i][k]*B[k][j] for k in range(8))%mod for j in range(8)] for i in range(8)]
    I=[[int(i==j) for j in range(8)] for i in range(8)]
    basis=[I]; H=hnf([vec(I)],64,mod)
    frontier=[I]
    while frontier:
        new=[]
        for A in frontier:
            for g in mats:
                B=mm(A,g)
                H2=hnf(list(H)+[vec(B)],64,mod)
                if H2!=H: H=H2; new.append(B)
        frontier=new
    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 c,H
    raise RuntimeError('c >= N')
def batch_rref3(Mt):
    """Mt: (B,m,8) int arrays mod 3. returns canonical rref (B,8,8) and ranks."""
    A=Mt.copy()%3; B,m,n=A.shape; rank=np.zeros(B,int)
    ar=np.arange(B)
    for c in range(n):
        rowsidx=np.arange(m)[None,:]
        cand=(A[:,:,c]!=0)&(rowsidx>=rank[:,None])
        has=cand.any(1)
        r=np.argmax(cand,1)
        idx=ar[has]; rr=r[has]; rk=rank[has]
        # swap rows rr and rk
        tmp=A[idx,rr].copy(); A[idx,rr]=A[idx,rk]; A[idx,rk]=tmp
        piv=A[idx,rk,c]; inv=np.where(piv==1,1,2)
        A[idx,rk]=(A[idx,rk]*inv[:,None])%3
        f=A[idx,:,c].copy(); f[np.arange(len(idx)),rk]=0
        A[idx]=(A[idx]-f[:,:,None]*A[idx,rk][:,None,:])%3
        rank[idx]+=1
    return A[:,:8,:],rank
PROJ=np.array([v for v in itertools.product(range(3),repeat=8) if any(v) and v[next(i for i,x in enumerate(v) if x)]==1],dtype=np.int64)  # 3280 x 8
def word_basis(X):
    """F_3 basis of the unital algebra generated by matrices X (list of 8x8 int arrays)."""
    basis=[];rows=[]
    def ins(M):
        v=M.reshape(-1)%3
        R=np.array(rows+[v]) if rows else v[None]
        _,rk=batch_rref3(np.array([np.vstack(rows+[v])]).astype(np.int64)) if False else (None,None)
        return v
    # simple incremental elimination over 64 coords
    ech={}
    def insert(M):
        v=[int(x)%3 for x in M.reshape(-1)]
        for i in sorted(ech):
            if v[i]: t=v[i]; v=[(a-t*b)%3 for a,b in zip(v,ech[i])]
        if not any(v): return False
        i=next(i for i,x in enumerate(v) if x); inv=1 if v[i]==1 else 2
        ech[i]=[x*inv%3 for x in v]; basis.append(M%3); return True
    insert(np.eye(8,dtype=np.int64)); start=0
    while start<len(basis):
        end=len(basis)
        for A in basis[start:end]:
            for g in X: insert((A@g)%3)
        start=end
    return basis
def maximal_sublattices(H,mats):
    Hn=np.array(H,dtype=object)
    X=[]
    for M in mats:
        img=[ [sum(H[i][k]*M[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), 'not stable'
        X.append(np.array(C,dtype=np.int64)%3)
    # row action c -> c X ; functionals phi (column) -> X phi. minimal submodules of functionals.
    W=word_basis([x for x in X])          # algebra spanned by words (acting on columns: X phi)
    Wa=np.array(W)                          # (m,8,8)
    imgs=np.einsum('mij,bj->bmi',Wa,PROJ)%3 # (B,m,8): images a phi
    R,rk=batch_rref3(imgs)
    keys={}
    for b in range(len(PROJ)):
        key=R[b,:rk[b]].tobytes()
        if key not in keys: keys[key]=(rk[b],R[b,:rk[b]].copy())
    subs=list(keys.values())
    def inside(small,big):
        Mt=np.vstack([big,small])[None]
        _,r=batch_rref3(Mt.astype(np.int64)); return r[0]==len(big)
    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:
        # kernel of functionals C (d x 8): rows c with C c^T = 0
        ker=[v for v in itertools.product(range(3),repeat=8)] if False else None
        # compute kernel basis mod 3 via rref of C
        piv=[next(j for j in range(8) if C[i,j]) for i in range(d)]
        free=[j for j in range(8) if j not in piv]
        kb=[]
        for f in free:
            v=[0]*8; v[f]=1
            for i,pc in enumerate(piv): v[pc]=(-int(C[i,f]))%3
            kb.append(v)
        rows=[[sum(c[k]*H[k][j] for k in range(8)) for j in range(8)] for c in kb]+[[3*x for x in r] for r in H]
        out.append((d,hnf(rows,8,p**(MODN))))
    return out
MODN=12
def run(name,side,verbose=True):
    S=ORDERS[name]; gens=order_gens(S); mats=act_mats(gens,side)
    c,_=algebra_c(mats)
    global MODN; MODN=c+3
    O=hnf([E[i] for i in range(8)],8,p**MODN)
    Lam=hnf(gens,8,p**MODN)
    seen={O:0}; frontier=[O]; levels={0:1}
    t=time.time()
    while frontier:
        nf=[]
        for H in frontier:
            for d,K in maximal_sublattices(H,mats):
                # primitive: K not inside 3O
                if all(all(x%3==0 for x in r) for r in K): continue
                if K not in seen:
                    seen[K]=index_exp(K,p); nf.append(K)
        frontier=nf
        if verbose: print(name,side,'frontier',len(frontier),'total',len(seen),round(time.time()-t,1),flush=True)
    PO={};PL={}
    shift=8-dimS(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,'side':side,'c':c,'dimS':dimS(S),'P_O':dict(sorted(PO.items())),'P_Lambda':dict(sorted(PL.items())),'n_primitive':len(seen)}
if __name__=='__main__':
    names=sys.argv[1].split(',') ; sides=sys.argv[2].split(',') if len(sys.argv)>2 else ['R','L']
    res=[]
    for n in names:
        for s in sides:
            r=run(n,s); print(json.dumps(r),flush=True); res.append(r)
    json.dump(res,open(f'results-A-{"_".join(names)}-{"".join(sides)}.json','w'),indent=1)
