2 files changed, 87 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..010c76d
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,6 @@
+CXX=g++ -std=c++0x -O3 -Wall -Wextra -Werror
+
+all: cacount
+
+clean:
+	-rm cacount *~
\ No newline at end of file
diff --git a/cacount.cpp b/cacount.cpp
new file mode 100644
index 0000000..7c052d3
--- /dev/null
+++ b/cacount.cpp
@@ -0,0 +1,81 @@
+#include <string.h>
+#include <assert.h>
+#include <array>
+#include <bitset>
+#include <functional>
+#include <iostream>
+#include <stdlib.h>
+
+using namespace std;
+
+typedef uint32_t State;
+const State logState = 16;
+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 iterTrans(int times, function<void(int)> f) {
+  while (times--)
+    for (State s=0; s<maxState; s++)
+      f(s);
+}
+
+void init(Trans &t) {
+  iterTrans(1, [&](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]]; });
+  // compute loop id (lowest state no): go through the loop again and
+  // record the lowest occuring state no
+  Trans &c(*new Trans());
+  iterTrans(1, [&](int s) { 
+      c[s] = t[s]; });
+  iterTrans(logState, [&](int s) {
+      c[s] = min(c[s], c[t[s]]);
+      t[s] = t[t[s]]; });
+  return &c;
+}
+
+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));
+    print(c);
+  }
+  return 0;
+}