|
bgneal@46
|
1 """ Code example from Complexity and Computation, a book about
|
|
bgneal@46
|
2 exploring complexity science with Python. Available free from
|
|
bgneal@46
|
3
|
|
bgneal@46
|
4 http://greenteapress.com/complexity
|
|
bgneal@46
|
5
|
|
bgneal@46
|
6 Copyright 2011 Allen B. Downey.
|
|
bgneal@46
|
7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
|
|
bgneal@46
|
8 """
|
|
bgneal@46
|
9
|
|
bgneal@46
|
10 import numpy
|
|
bgneal@46
|
11
|
|
bgneal@46
|
12 class CA(object):
|
|
bgneal@46
|
13 """A CA is a cellular automaton; the parameters for __init__ are:
|
|
bgneal@46
|
14
|
|
bgneal@46
|
15 rule: an integer in the range 0-255 that represents the CA rule
|
|
bgneal@46
|
16 using Wolfram's encoding.
|
|
bgneal@46
|
17 n: the number of rows (timesteps) in the result.
|
|
bgneal@46
|
18 ratio: the ratio of columns to rows.
|
|
bgneal@46
|
19 """
|
|
bgneal@46
|
20
|
|
bgneal@46
|
21 def __init__(self, rule, n=100, ratio=2):
|
|
bgneal@46
|
22 """Attributes:
|
|
bgneal@46
|
23 table: rule dictionary that maps from triple to next state.
|
|
bgneal@46
|
24 n, m: are the number of rows, columns.
|
|
bgneal@46
|
25 array: the numpy array that contains the data.
|
|
bgneal@46
|
26 next: the index of the next empty row.
|
|
bgneal@46
|
27 """
|
|
bgneal@46
|
28 self.table = self.make_table(rule)
|
|
bgneal@46
|
29 self.n = n
|
|
bgneal@46
|
30 self.m = ratio*n + 1
|
|
bgneal@46
|
31 self.array = numpy.zeros((n, self.m), dtype=numpy.int8)
|
|
bgneal@46
|
32 self.next = 0
|
|
bgneal@46
|
33
|
|
bgneal@46
|
34 def make_table(self, rule):
|
|
bgneal@46
|
35 """Returns a table for the given CA rule. The table is a
|
|
bgneal@46
|
36 dictionary that maps 3-tuples to binary values.
|
|
bgneal@46
|
37 """
|
|
bgneal@46
|
38 table = {}
|
|
bgneal@46
|
39 for i, bit in enumerate(binary(rule, 8)):
|
|
bgneal@46
|
40 t = binary(7-i, 3)
|
|
bgneal@46
|
41 table[t] = bit
|
|
bgneal@46
|
42 return table
|
|
bgneal@46
|
43
|
|
bgneal@46
|
44 def start_single(self):
|
|
bgneal@46
|
45 """Starts with one cell in the middle of the top row."""
|
|
bgneal@46
|
46 self.array[0, self.m/2] = 1
|
|
bgneal@46
|
47 self.next += 1
|
|
bgneal@46
|
48
|
|
bgneal@46
|
49 def start_random(self):
|
|
bgneal@46
|
50 """Start with random values in the top row."""
|
|
bgneal@46
|
51 self.array[0] = numpy.random.random([1,self.m]).round()
|
|
bgneal@46
|
52 self.next += 1
|
|
bgneal@46
|
53
|
|
bgneal@46
|
54 def loop(self, steps=1):
|
|
bgneal@46
|
55 """Executes the given number of time steps."""
|
|
bgneal@46
|
56 [self.step() for i in xrange(steps)]
|
|
bgneal@46
|
57
|
|
bgneal@46
|
58 def step(self):
|
|
bgneal@46
|
59 """Executes one time step by computing the next row of the array."""
|
|
bgneal@46
|
60 i = self.next
|
|
bgneal@46
|
61 self.next += 1
|
|
bgneal@46
|
62
|
|
bgneal@46
|
63 a = self.array
|
|
bgneal@46
|
64 t = self.table
|
|
bgneal@46
|
65 for j in xrange(1,self.m-1):
|
|
bgneal@46
|
66 a[i,j] = t[tuple(a[i-1, j-1:j+2])]
|
|
bgneal@46
|
67
|
|
bgneal@46
|
68 def get_array(self, start=0, end=None):
|
|
bgneal@46
|
69 """Gets a slice of columns from the CA, with slice indices
|
|
bgneal@46
|
70 (start, end). Avoid copying if possible.
|
|
bgneal@46
|
71 """
|
|
bgneal@46
|
72 if start==0 and end==None:
|
|
bgneal@46
|
73 return self.array
|
|
bgneal@46
|
74 else:
|
|
bgneal@46
|
75 return self.array[:, start:end]
|
|
bgneal@46
|
76
|
|
bgneal@46
|
77
|
|
bgneal@46
|
78 def binary(n, digits):
|
|
bgneal@46
|
79 """Returns a tuple of (digits) integers representing the
|
|
bgneal@46
|
80 integer (n) in binary. For example, binary(3,3) returns (0, 1, 1)"""
|
|
bgneal@46
|
81 t = []
|
|
bgneal@46
|
82 for i in range(digits):
|
|
bgneal@46
|
83 n, r = divmod(n, 2)
|
|
bgneal@46
|
84 t.append(r)
|
|
bgneal@46
|
85
|
|
bgneal@46
|
86 return tuple(reversed(t))
|
|
bgneal@46
|
87
|
|
bgneal@46
|
88
|
|
bgneal@46
|
89 def print_table(table):
|
|
bgneal@46
|
90 """Prints the rule table in LaTeX format."""
|
|
bgneal@46
|
91 t = table.items()
|
|
bgneal@46
|
92 t.sort(reverse=True)
|
|
bgneal@46
|
93
|
|
bgneal@46
|
94 print '\\beforefig'
|
|
bgneal@46
|
95 print '\\centerline{'
|
|
bgneal@46
|
96 print '\\begin{tabular}{|c|c|c|c|c|c|c|c|c|}'
|
|
bgneal@46
|
97 print '\\hline'
|
|
bgneal@46
|
98
|
|
bgneal@46
|
99 res = ['prev']
|
|
bgneal@46
|
100 for k, v in t:
|
|
bgneal@46
|
101 s = ''.join([str(x) for x in k])
|
|
bgneal@46
|
102 res.append(s)
|
|
bgneal@46
|
103 print ' & '.join(res) + ' \\\\ \n\\hline'
|
|
bgneal@46
|
104
|
|
bgneal@46
|
105 res = ['next']
|
|
bgneal@46
|
106 for k, v in t:
|
|
bgneal@46
|
107 res.append(str(v))
|
|
bgneal@46
|
108 print ' & '.join(res) + ' \\\\ \n\\hline'
|
|
bgneal@46
|
109
|
|
bgneal@46
|
110 print '\\end{tabular}}'
|
|
bgneal@46
|
111
|
|
bgneal@46
|
112
|
