Mercurial > public > think_complexity

comparison ch6ex3.py @ 43:6cd37534c12e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 3: exploring rule 110 cellular automata.
author Brian Neal <bgneal@gmail.com>
date Mon, 14 Jan 2013 20:41:41 -0600
parents
children
comparison
equal deleted inserted replaced
42:039249efe42f 43:6cd37534c12e
1 """Chapter 6, exercise 3 in Allen Downey's Think Complexity book.
2
3 This exercise asks you to experiment with Rule 110 and see how many spaceships you can find.
4
5 1. Modify your program from the previous exercises so it starts with an initial
6 condition that yields the stable background pattern.
7
8 2. Modify the initial condition by adding different patterns in the center of
9 the row and see which ones yield spaceships. You might want to enumerate all
10 possible patterns of n bits, for some reasonable value of n. For each
11 spaceship, can you find the period and rate of translation? What is the
12 biggest spaceship you can find?
13
14 """
15 import os.path
16 import cPickle
17
18 from CircularCA import CircularCA
19 from CADrawer import PyplotDrawer
20
21 FILENAME = 'rule110.pkl'
22 RULE = 110
23
24 def find_ic(show=False):
25 """This function sets up a rule 110 CA with a random initial condition and
26 runs it for 600 time steps. The last row is the initial condition (IC) we
27 are interested in for producing future CA to investigate rule 110 and
28 spaceships.
29
30 We use 600 steps because of figure 6.6 in Think Complexity.
31
32 The CA is run through 600 steps and then the last row is pickled in a file
33 for future use.
34
35 """
36 ca = CircularCA(RULE, 600, 600)
37 ca.start_random()
38 ca.loop(599)
39
40 if show:
41 drawer = PyplotDrawer()
42 drawer.draw(ca)
43 drawer.show()
44
45 # get the last row of the CA and pickle it to a file so we can use it in the
46 # future:
47
48 last_row = ca.array[599, :]
49 with open(FILENAME, 'wb') as fp:
50 cPickle.dump(last_row, fp, protocol=2)
51
52 print "last row pickled in {}".format(FILENAME)
53
54
55 def rule110(script, n):
56 """Open the IC pickle file and initialize a CA with it.
57 Modify the 32 center columns with the bit pattern given by n, which should
58 be a hexidecimal number.
59 Then step the CA and display it.
60
61 """
62 print 'loading {}...'.format(FILENAME)
63 with open(FILENAME, 'rb') as fp:
64 ic = cPickle.load(fp)
65
66 print 'creating CA...'
67 ca = CircularCA(RULE, 600, 600)
68 ca.start_row(ic)
69
70 n = int(n, 16)
71 print 'modifying center of row with {:x}'.format(n)
72 a = ca.array
73 mask = 1 << 31
74 j = 600 / 2 - 16 + 1 # +1 because of the ghost column on the left
75 for i in xrange(32):
76 a[0, j] = 1 if n & mask else 0
77 j += 1
78 mask >>= 1
79
80 print 'stepping CA...'
81 ca.loop(599)
82
83 drawer = PyplotDrawer()
84 drawer.draw(ca)
85 drawer.show()
86
87
88 if __name__ == '__main__':
89 import sys
90
91 if not os.path.exists(FILENAME):
92 find_ic()
93
94 rule110(*sys.argv)