# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1358217701 21600
# Node ID 6cd37534c12e2399d8a542ecb891e7aa3a53ac48
# Parent  039249efe42f7c39d77bf0750c6c77b694b334c8
Chapter 6, exercise 3: exploring rule 110 cellular automata.

diff -r 039249efe42f -r 6cd37534c12e CircularCA.py
--- a/CircularCA.py	Sun Jan 13 16:24:00 2013 -0600
+++ b/CircularCA.py	Mon Jan 14 20:41:41 2013 -0600
@@ -34,6 +34,11 @@
         self.array[0, 1] = 1
         self.next = 1
 
+    def start_row(self, row):
+        """Set the first row to row and set next to 1."""
+        self.array[0, :] = row
+        self.next = 1
+
     def step(self):
         """Executes one time step by computing the next row of the array."""
         i = self.next
diff -r 039249efe42f -r 6cd37534c12e ch6ex3.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch6ex3.py	Mon Jan 14 20:41:41 2013 -0600
@@ -0,0 +1,94 @@
+"""Chapter 6, exercise 3 in Allen Downey's Think Complexity book.
+
+This exercise asks you to experiment with Rule 110 and see how many spaceships you can find.
+
+1. Modify your program from the previous exercises so it starts with an initial
+   condition that yields the stable background pattern.
+
+2. Modify the initial condition by adding different patterns in the center of
+   the row and see which ones yield spaceships. You might want to enumerate all
+   possible patterns of n bits, for some reasonable value of n. For each
+   spaceship, can you find the period and rate of translation? What is the
+   biggest spaceship you can find?
+
+"""
+import os.path
+import cPickle
+
+from CircularCA import CircularCA
+from CADrawer import PyplotDrawer
+
+FILENAME = 'rule110.pkl'
+RULE = 110
+
+def find_ic(show=False):
+    """This function sets up a rule 110 CA with a random initial condition and
+    runs it for 600 time steps. The last row is the initial condition (IC) we
+    are interested in for producing future CA to investigate rule 110 and
+    spaceships.
+
+    We use 600 steps because of figure 6.6 in Think Complexity.
+
+    The CA is run through 600 steps and then the last row is pickled in a file
+    for future use.
+
+    """
+    ca = CircularCA(RULE, 600, 600)
+    ca.start_random()
+    ca.loop(599)
+
+    if show:
+        drawer = PyplotDrawer()
+        drawer.draw(ca)
+        drawer.show()
+
+    # get the last row of the CA and pickle it to a file so we can use it in the
+    # future:
+
+    last_row = ca.array[599, :]
+    with open(FILENAME, 'wb') as fp:
+        cPickle.dump(last_row, fp, protocol=2)
+
+    print "last row pickled in {}".format(FILENAME)
+
+
+def rule110(script, n):
+    """Open the IC pickle file and initialize a CA with it.
+    Modify the 32 center columns with the bit pattern given by n, which should
+    be a hexidecimal number.
+    Then step the CA and display it.
+
+    """
+    print 'loading {}...'.format(FILENAME)
+    with open(FILENAME, 'rb') as fp:
+        ic = cPickle.load(fp)
+
+    print 'creating CA...'
+    ca = CircularCA(RULE, 600, 600)
+    ca.start_row(ic)
+
+    n = int(n, 16)
+    print 'modifying center of row with {:x}'.format(n)
+    a = ca.array
+    mask = 1 << 31
+    j = 600 / 2 - 16 + 1    # +1 because of the ghost column on the left
+    for i in xrange(32):
+        a[0, j] = 1 if n & mask else 0
+        j += 1
+        mask >>= 1
+
+    print 'stepping CA...'
+    ca.loop(599)
+
+    drawer = PyplotDrawer()
+    drawer.draw(ca)
+    drawer.show()
+
+
+if __name__ == '__main__':
+    import sys
+
+    if not os.path.exists(FILENAME):
+        find_ic()
+
+    rule110(*sys.argv)