#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include <array>
#include <bitset>
#include <functional>
#include <iostream>
#include <map>
#include <set>

using namespace std;

typedef uint32_t State;
const State logState = 31;
const State maxState = 1 << logState;

bitset<8> rule(110);

State update(State s) {
  State r(0);
  bitset<logState> b(s);
  for (unsigned i=0; i<logState; i++)
    r |= rule[1 * b[(i + logState - 1) % logState]
	    + 2 * b[i]                
	    + 4 * b[(i + 1) % logState]] << i;
  return r;
}

typedef array<State, maxState> Trans;

void iterState(function<void(int)> f) {
  for (State s=0; s<maxState; s++)
    f(s);
}

void iterTrans(int times, function<void(int)> f, bool verbose=false) {
  if (verbose) cerr << times << " left\r";
  while (times--) {
    iterState(f);
    if (verbose) cerr << times << " left\r";
  }
  if (verbose) cerr << "           \r";
}

void init(Trans &t) {
  iterState([&](int s) { 
      t[s] = update(s); });
}

Trans* findCycle(Trans &t) {
  // forward to t=maxState; now every state is in a cycle
  iterTrans(logState, [&](int s) {
      t[s] = t[t[s]]; }, true);
  // compute loop id (lowest occuring state no): go through the loop again and
  // record the lowest occuring state number
  Trans &c(*new Trans());
  iterState([&](int s) { 
      c[s] = t[s]; });
  iterTrans(logState, [&](int s) {
      c[s] = min(c[s], c[t[s]]);
      t[s] = t[t[s]]; }, true);
  return &c;
}

void cycleStat(Trans &c) {
  struct Stat {
    State basin, len, minState;
    Stat() : basin(0), len(0), minState(maxState) {}
  };
  map<State, Stat> cyc;

  // how big is the basin of attraction?
  iterState([&](int s) { cyc[c[s]].basin++; });

  // how long is the cycle, what is the actual minimal state
  for (auto i : cyc) {
    Stat &s = cyc[i.first];
    State cur, start;
    cur = start = c[i.first]; 
    do {
      s.len++;
      s.minState = min(s.minState, cur);
      cur=update(cur);
    } while (cur != start);
  }

  // find duplicates cycles (only bitshifted)
  auto canonize = [](State s) {
    State cs = s;
    for (State i=0; i<logState; i++)
      cs = min(cs, (((s<<i) | (s>>(logState-i))) & (maxState - 1)));
    return cs;
  };
  map<State, set<State>> ccyc;
  for (auto i : cyc) {
    ccyc[canonize(i.second.minState)].insert(i.first);
  }

  // print it
  for (auto i : ccyc) {
    Stat &s = cyc[*(i.second.begin())];
    cout << bitset<logState>(i.first) << "\t"
	 << i.second.size() << "\t"
	 << s.len << "\t"
	 << s.basin << "\t"
	 << i.first << endl;
  }
}

void print(Trans &t) {
  for (auto s : t)
    cout << bitset<logState>(s) << endl;
}

void printTraj(State s, int count) {
  while (count--) {
    cout << bitset<logState>(s) << endl;
    s = update(s);
  }
}

int main(int argc, char **argv) {
  assert(argc >= 2);
  rule = atoi(argv[1]);
  if (!strcmp(argv[2], "traj")) {
    assert(argc == 5);
    printTraj(atoi(argv[3]), atoi(argv[4]));
  }
  if (!strcmp(argv[2], "cycle")) {
    Trans &t = *(new Trans);
    init(t);
    Trans &c(*findCycle(t));
    cycleStat(c);
  }
  return 0;
}