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