"""Uniform-in-p classification of primitive stable lattices for a coordinate shape S (Grant pt212u).

Theorem (hull/core/glue).  For a lattice M in O_p let alpha_i, beta_i be defined by pi_i(M) = p^alpha_i Z_p and
M cap Z_p e_i = p^beta_i Z_p, hull Mh = (+) p^alpha_i e_i, core Mc = (+) p^beta_i e_i, glue G = M/Mc inside Mh/Mc.
Every generator R_y (y in the Z_p-basis of Lambda_S) is p^s times a signed partial matching of coordinates, so:
  M stable  <=>  (H) alpha_i + s >= alpha_j and (C) beta_i + s >= beta_j for every component i->j of every generator,
                 and (G) G is invariant under the induced maps on Mh/Mc.
Conversely (alpha, beta, G) with G meeting every factor trivially and projecting onto every factor gives back M.
A single-component word p^m E_ij in the generators forces beta_j <= alpha_i + m (bound B); these words are found by a
combinatorial search that does not depend on p, so the candidate set (alpha, beta) is the same finite set for every p.
When every delta = beta - alpha is 0 or 1, G is an F_p-subspace and the induced maps have entries 0, +-1 independent of p;
its count is done by an exact symbolic case split (count.py) and is a polynomial in p."""
import sys, itertools, collections, json, functools
sys.path.insert(0,'../oddcond1111')
from zorn import mul, E
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)}
NAMES=['a','u1','u2','u3','v1','v2','v3','b']
def generators(shape):
    S=SHAPES[shape]; out=[]
    for y in range(8):
        comp={}
        for i in range(8):
            img=mul(E[i],E[y]); nz=[(j,c) for j,c in enumerate(img) if c]
            if nz:
                assert len(nz)==1 and abs(nz[0][1])==1; comp[i]=(nz[0][0],nz[0][1])
        assert len({j for j,_ in comp.values()})==len(comp)      # partial matching
        out.append((0 if y in S else 1, comp, NAMES[y]))
    return out
def compose(w,g):   # row convention x.w.g
    s1,c1=w; s2,c2,_=g; c={}
    for i,(j,si) in c1.items():
        if j in c2: k,sj=c2[j]; c[i]=(k,si*sj)
    return (s1+s2,c)
@functools.lru_cache(None)
def single_words(shape,maxlen=8):
    """min scale m with a single-component word p^m E_ij; found by BFS over words (p-independent)."""
    G=generators(shape); best={}; seen=set()
    fr=[(0,{i:(i,1) for i in range(8)})]
    for L in range(maxlen):
        nf=[]
        for w in fr:
            for g in G:
                s,c=compose(w,g)
                if not c: continue
                key=(s,tuple(sorted((i,j) for i,(j,_) in c.items())))
                if key in seen or s>4: continue
                seen.add(key); nf.append((s,c))
                if len(c)==1:
                    (i,(j,_)),=c.items(); best[(i,j)]=min(best.get((i,j),9),s)
        fr=nf
    return best
def candidates(shape):
    G=generators(shape); m=single_words(shape)
    assert len(m)==64, ('missing single words',sorted(set(itertools.product(range(8),repeat=2))-set(m)))
    comps=[(s,i,j) for s,c,_ in G for i,(j,_) in c.items()]
    out=[]
    for al in itertools.product(range(4),repeat=8):
        if min(al)!=0: continue
        if any(al[j]>al[i]+m[(i,j)] for i in range(8) for j in range(8)): continue
        if any(al[i]+s<al[j] for s,i,j in comps): continue
        rng=[range(al[j],min(al[i]+m[(i,j)] for i in range(8))+1) for j in range(8)]
        for be in itertools.product(*rng):
            if any(be[i]+s<be[j] for s,i,j in comps): continue
            if any(be[j]>al[i]+m[(i,j)] for i in range(8) for j in range(8)): continue
            out.append((al,be))
    return out
def induced(shape,al,be):
    """induced maps on Mh/Mc: list over generators of {i:(j,coef_exponent k,sign)} restricted to delta>0 coordinates."""
    de=[b-a for a,b in zip(al,be)]; ops=[]
    for s,c,name in generators(shape):
        o={}
        for i,(j,sg) in c.items():
            if de[i]==0 or de[j]==0: continue
            k=al[i]+s-al[j]
            if k<de[j]: o[i]=(j,k,sg)
        ops.append((name,o))
    return de,ops
if __name__=='__main__':
    sh=sys.argv[1]
    m=single_words(sh)
    print('single-word exponents found for',len(m),'of 64 (i,j)')
    C=candidates(sh); print('candidates (alpha,beta):',len(C))
    dd=collections.Counter(max(b-a for a,b in zip(al,be)) for al,be in C); print('max delta histogram',dict(dd))
@functools.lru_cache(None)
def all_words(shape,maxlen=7,maxs=3):
    """every distinct (scale, signed matching) reachable as a word of length <= maxlen (p-independent)."""
    G=generators(shape); seen={}; fr=[(0,{i:(i,1) for i in range(8)})]
    for L in range(maxlen):
        nf=[]
        for w in fr:
            for g in G:
                s,c=compose(w,g)
                if not c or s>maxs: continue
                key=(s,tuple(sorted((i,j,sg) for i,(j,sg) in c.items())))
                if key in seen: continue
                seen[key]=1; nf.append((s,c))
        fr=nf
    return list(seen)
def killed(shape,al,be):
    """True if some word induces on Mh/Mc a map with exactly one surviving component j->i (then no glue G exists:
    take g in G with g_j a generator of its factor; the image is a nonzero element of factor i)."""
    de=[b-a for a,b in zip(al,be)]
    for s,comp in all_words(shape):
        surv=[(i,j) for i,j,sg in comp if de[i]>0 and de[j]>0 and al[i]+s-al[j]<de[j]]
        if len(surv)==1: return True
    return False
if __name__=='__main__' and len(sys.argv)>2 and sys.argv[2]=='kill':
    C=candidates(sys.argv[1]); W=all_words(sys.argv[1]); print('words',len(W))
    left=[(al,be) for al,be in C if not killed(sys.argv[1],al,be)]
    print('after single-survivor exclusion:',len(left),'max delta',dict(collections.Counter(max(b-a for a,b in zip(al,be)) for al,be in left)))
    json.dump(left,open(f'cand-{sys.argv[1]}.json','w'))
