"""
Adversarial double-check of the Z_82 finding.
1) Reproduce the 88 (3,16)-free candidates; save them.
2) Validate BOTH exact searchers on ground truth (small n, brute force).
3) For sampled free candidates: verify triangle-freedom by raw edge scan,
   verify alpha<=15 with TWO different exact algorithms + randomized attacks.
"""
import json, re, os, sys, time, random, itertools
sys.setrecursionlimit(100000)

BODIES = r"C:\Users\jack\rc_corpus\bodies"
FULL = lambda n: (1 << n) - 1
def rot(x, k, n):
    return x if k == 0 else ((x << k) | (x >> (n - k))) & FULL(n)
def popcount(x): return bin(x).count("1")

def class_orbits(n, a):
    cls_of = {}
    for r in range(1, n//2 + 1):
        cls_of[r] = r; cls_of[n-r] = r
    seen=set(); orbs=[]
    for r in range(1, n//2+1):
        if r in seen: continue
        o=set(); x=r
        while True:
            c=cls_of[x]
            if c in o: break
            o.add(c); x=(a*x)%n
        orbs.append(o); seen|=o
    return orbs

def adj_from_m0(m0, n):
    return [rot(m0, v, n) for v in range(n)]

def is_triangle_free(adj, n):
    for v in range(n):
        m = adj[v]
        mm = m
        while mm:
            u = (mm & -mm).bit_length()-1; mm &= mm-1
            if adj[u] & m & ~((1 << (u+1)) - 1) & m:
                pass
        # simpler: any edge inside N(v)?
        nb = m
        while nb:
            ub = nb & -nb; u = ub.bit_length()-1; nb ^= ub
            if adj[u] & m & ((1 << u) - 1):
                return False
    return True

# ---------- searcher 1: coloring B&B (as in main audit) ----------
def alpha_max_coloring(adj, n, t, budget_s=60):
    """Return True if independent set of size t EXISTS (exact), else False."""
    comp=[0]*n; full=FULL(n)
    for v in range(n):
        comp[v] = full & ~adj[v] & ~(1<<v)
    best=[0]; t0=time.time()
    class TO(Exception): pass
    def color_sort(P):
        order=[];bounds=[];U=P;c=0
        while U:
            c+=1; avail=U
            while avail:
                b=avail&-avail; v=b.bit_length()-1
                order.append(v); bounds.append(c)
                U^=b; avail&=~b; avail&=~comp[v]
        return order,bounds
    def expand(C,P):
        if time.time()-t0>budget_s: raise TO()
        if len(C)>best[0]: best[0]=len(C)
        if len(C)>=t: return list(C)
        order,bounds=color_sort(P)
        for i in range(len(order)-1,-1,-1):
            if len(C)+bounds[i]<t: return None
            v=order[i]
            C.append(v)
            r=expand(C,P&comp[v])
            if r: return r
            C.pop(); P&=~(1<<v)
        return None
    try:
        r=expand([],full)
        return (True, r, best[0]) if r else (False, None, best[0])
    except TO:
        return (None, None, best[0])

# ---------- searcher 2: complement clique Tomita-style, max-degree branching ----------
def alpha_max_deg(adj, n, t, budget_s=60):
    comp=[0]*n; full=FULL(n)
    deg=[popcount(adj[v]) for v in range(n)]
    for v in range(n):
        comp[v]=full&~adj[v]&~(1<<v)
    cdeg=[popcount(comp[v]) for v in range(n)]
    t0=time.time()
    class TO(Exception): pass
    def expand(C,P):
        if time.time()-t0>budget_s: raise TO()
        if len(C)>=t: return list(C)
        if not P: return None
        # branch on max-degree-in-P vertex
        pv=-1;bd=-1
        x=P
        while x:
            b=x&-x; v=b.bit_length()-1; x^=b
            d=popcount(comp[v]&P)
            if d>bd: bd=d; pv=v
        for v in [pv]:
            rest=P
            while rest:
                b=rest&-rest; u=b.bit_length()-1; rest^=b
                if u==v: continue
                C.append(u)
                r=expand(C,P&comp[u])
                if r: return r
                C.pop()
                P&=~b
        return None
    try:
        r=expand([],full)
        return (True,r,None) if r else (False,None,None)
    except TO:
        return (None,None,None)

def brute_alpha(adj, n):
    best=0
    for k in range(n,0,-1):
        for sub in itertools.combinations(range(n),k):
            ok=all(not(adj[a]>>b&1) for a,b in itertools.combinations(sub,2))
            if ok: return k
    return 1

# ---------- ground-truth validation on small circulants ----------
print("GROUND TRUTH: validating both exact searchers on n=14..20 circulants")
rng=random.Random(7)
ok1=ok2=0; bad=0
for trial in range(60):
    n=rng.choice([14,15,16,17,18,20])
    S=set()
    for _ in range(rng.randint(2,6)):
        S.add(rng.randint(1,n//2))
    m0=0
    for c in S: m0|=(1<<c)|(1<<((n-c)%n))
    adj=adj_from_m0(m0,n)
    truth=brute_alpha(adj,n)
    r1=alpha_max_coloring(adj,n,99,budget_s=10)[2]     # best found size (exact since tiny)
    r2,_ ,_=alpha_max_deg(adj,n,99,budget_s=10)        # bool existence of huge set -> need max size; instead ask t=truth existence
    e2=alpha_max_deg(adj,n,min(truth+1,n),budget_s=10)[0]
    e1=alpha_max_coloring(adj,n,min(truth+1,n),budget_s=10)[0]
    good1 = (r1==truth) and (e1 is False)
    good2 = (e2 is False)
    ok1+=good1; ok2+=good2; bad += (not(good1 and good2))
print(f"s1 exact-max match {ok1}/60, s2 nonexistence match {ok2}/60, disagreements {bad}")

# ---------- reproduce Z_82 free candidates ----------
pid="rcs_ppr_nfq9eydk3r1db32nzht1"
p=json.load(open(os.path.join(BODIES,pid+".json"),encoding="utf-8"))
rec=json.loads(re.search(r"```json\r?\n(\{.*?\})\r?\n```",p["body"],re.S).group(1))
n=82; a=3; t_cell=16
orbs=class_orbits(n,a)
k=len(orbs)
orb_masks=[]
for o in orbs:
    m=0
    for c in o: m|=(1<<c)|(1<<((n-c)%n))
    orb_masks.append(m)
comp_cache={}
free_masks=[]; tri_free_cnt=0
for mask in range(1,1<<k):
    m0=0; mm=mask; i=0
    while mm:
        if mm&1: m0|=orb_masks[i]
        mm>>=1;i+=1
    adj=adj_from_m0(m0,n)
    if not is_triangle_free(adj,n): continue
    tri_free_cnt+=1
    ex,mxs,_=alpha_max_coloring(adj,n,t_cell,budget_s=120)
    if ex is False:
        free_masks.append(m0)
print("triangle-free candidates:",tri_free_cnt," (3,16)-free:",len(free_masks))

# ---------- adversarial attack on up to 6 free candidates ----------
random.seed(1234)
report=[]
for m0 in random.sample(free_masks, min(6,len(free_masks))):
    adj=adj_from_m0(m0,n)
    tf=is_triangle_free(adj,n)
    e1,_,best1=alpha_max_coloring(adj,n,t_cell,budget_s=180)
    e2,_,_=alpha_max_deg(adj,n,t_cell,budget_s=180)
    # randomized greedy attacks: try hard to BUILD an IS of size 16
    attack_best=0
    for trial in range(3000):
        order=list(range(n)); random.shuffle(order)
        IS=[]
        banned=0
        for v in order:
            if not (banned>>v&1):
                IS.append(v); banned|=adj[v]|(1<<v)
                if len(IS)>=t_cell: break
        attack_best=max(attack_best,len(IS))
        if attack_best>=t_cell: break
    report.append({"m0":m0,"deg":popcount(m0),"triangle_free":tf,
                   "s1_exists":e1,"s1_best":best1,"s2_exists":e2,
                   "greedy_attack_max_is":attack_best,"attacks":trial+1})
    print(report[-1])

json.dump({"free_count":len(free_masks),"free_masks":[hex(m) for m in free_masks],
           "attack_report":report},
          open(r"C:\Users\jack\rc_audit\z82_free.json","w"),indent=1)
print("saved z82_free.json")