Code:
// Public domain
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
static const unsigned char st[256][2]=
{{2,168} ,{2,168} ,{3,163} ,{4,163} ,{5,165} ,{6,89} ,{7,245} ,{8,217} ,{9,245} ,{10,245} , // 0-9
{11,233} ,{12,244} ,{13,227} ,{14,74} ,{15,221} ,{16,221} ,{17,218} ,{18,226} ,{19,243} ,{20,218} , // 10
{21,238} ,{22,242} ,{23,74} ,{24,238} ,{25,241} ,{26,240} ,{27,239} ,{28,224} ,{29,225} ,{30,221} , // 20
{31,232} ,{32,72} ,{33,224} ,{34,228} ,{35,223} ,{36,225} ,{37,238} ,{38,73} ,{39,167} ,{40,76} , // 30
{41,237} ,{42,234} ,{43,231} ,{44,72} ,{45,31} ,{46,63} ,{47,225} ,{48,237} ,{49,236} ,{50,235} , // 40
{51,53} ,{52,234} ,{47,53} ,{54,234} ,{55,229} ,{56,219} ,{57,229} ,{58,233} ,{59,232} ,{60,228} , // 50
{61,226} ,{62,72} ,{63,74} ,{64,222} ,{65,75} ,{66,220} ,{67,167} ,{68,57} ,{69,218} ,{6,70} , // 60
{71,1} ,{71,72} ,{71,73} ,{61,74} ,{75,217} ,{56,76} ,{77,167} ,{78,79} ,{77,79} ,{80,166} , // 70
{81,162} ,{82,162} ,{83,162} ,{84,162} ,{85,165} ,{86,89} ,{87,89} ,{88,165} ,{77,89} ,{90,162} , // 80
{91,93} ,{92,93} ,{80,93} ,{94,161} ,{95,100} ,{96,93} ,{97,93} ,{98,93} ,{99,93} ,{90,93} , // 90
{101,161},{94,102} ,{103,120},{101,104},{102,105},{104,106},{107,108},{104,106},{105,109},{108,110}, // 100
{111,160},{112,134},{113,108},{114,108},{115,126},{116,117},{92,117} ,{118,121},{94,119} ,{103,120}, // 110
{119,107},{122,124},{123,117},{94,117} ,{113,125},{126,127},{113,124},{128,139},{129,130},{114,124}, // 120
{131,133},{132,109},{112,110},{134,135},{111,110},{134,136},{110,137},{134,138},{134,127},{128,140}, // 130
{128,141},{142,145},{143,144},{115,124},{113,125},{142,146},{128,147},{148,151},{149,125},{79,150} , // 140
{148,127},{142,152},{148,153},{150,154},{155,156},{149,139},{157,158},{149,139},{159,156},{149,139}, // 150
{131,130},{101,117},{98,163} ,{115,164},{114,141},{91,163} ,{79,147} ,{58,168} ,{143,169},{170,199}, // 160
{129,171},{128,172},{110,173},{174,177},{128,175},{176,171},{129,171},{174,178},{179,180},{174,172}, // 170
{176,181},{141,182},{157,183},{179,184},{185,186},{157,178},{187,189},{188,181},{1,181} ,{151,190}, // 180
{191,193},{192,182},{188,182},{187,194},{172,195},{175,196},{170,197},{152,198},{185,169},{170,200}, // 190
{176,201},{170,202},{203,204},{148,180},{185,205},{203,206},{185,207},{192,208},{209,210},{188,194}, // 200
{211,212},{192,184},{213,215},{214,193},{188,184},{216,208},{1,193} ,{84,163} ,{54,219} ,{54,1} , // 210
{221,94} ,{54,217} ,{55,223} ,{85,224} ,{69,225} ,{63,76} ,{56,227} ,{86,217} ,{58,229} ,{230,219}, // 220
{231,79} ,{57,86} ,{229,165},{56,217} ,{224,214},{54,225} ,{54,216} ,{66,216} ,{58,234} ,{54,75} , // 230
{61,214} ,{57,237} ,{222,74} , {78,74} ,{85,163} ,{82,217} ,{0,0} ,{0,0} ,{0,0} ,{0,0} , // 240
{0,0} ,{0,0} ,{0,0} ,{0,0} ,{0,0} ,{0,0}}; // 250
vector<int> v[256];
int main() {
// Calculate final state for all sequences of up to 28 bits. Save first 10 per state.
bool done=false;
for (int i=0; i<28 && !done; ++i) {
done=true;
for (int j=0; j<(1<<i); ++j) {
int s=0;
for (int k=0; k<i; ++k)
s=st[s][j>>k&1];
if (v[s].size()<10) {
v[s].push_back(1<<i|j);
done=false;
}
}
}
// Calculate transitions neede to reach each state
int dist[256]={0};
dist[0]=1;
for (int i=1; i<=256; ++i) {
for (int j=0; j<256; ++j) {
if (dist[j]==i) {
if (dist[st[j][0]]==0) dist[st[j][0]]=i+1;
if (dist[st[j][1]]==0) dist[st[j][1]]=i+1;
}
}
}
// Print sequences by state
for (int i=0; i<256; ++i) {
if (dist[i])
printf("State %d reachable in %d steps\n", i, dist[i]-1);
else
printf("State %d not reachable\n", i);
for (int j=0; j<int(v[i].size()); ++j) {
printf("%3d: ", i);
unsigned x=v[i][j];
while (x>1) {
printf("%d", x&1);
x>>=1;
}
printf("\n");
}
printf("\n");
}
return 0;
}