1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#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]]; });
// 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]]; });
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);
}
// print it
for (auto i : cyc) {
Stat &s = i.second;
cout << s.minState << "\t"
<< bitset<logState>(s.minState) << "\t"
<< s.len << "\t"
<< s.basin << 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;
}
|
