# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1358115840 21600
# Node ID 039249efe42f7c39d77bf0750c6c77b694b334c8
# Parent  d4d9650afe1e7ee1e05d8f1236ee3c71dc1dc578
Chapter 6, exercise 2, #4. Wrote a program to output the center column of
a rule 30 CA as a stream of bytes. It is very slow though. It has to run a very
long time to produce enough data for dieharder. Committing it now but will have
to let it run overnight or something to generate a large file.

diff -r d4d9650afe1e -r 039249efe42f CircularCA.py
--- a/CircularCA.py	Sun Jan 13 13:10:46 2013 -0600
+++ b/CircularCA.py	Sun Jan 13 16:24:00 2013 -0600
@@ -14,19 +14,19 @@
 class CircularCA(CA):
     """A circular cellular automaton; the cells are arranged in a ring."""
 
-    def __init__(self, rule, n=100, ratio=2):
+    def __init__(self, rule, n=100, m=50):
         """Parameters:
 
         * rule: an integer in the range 0-255 that represents the CA rule
         using Wolfram's encoding
         * n: the number of rows (time steps) in the result
-        * ratio: the ratio of columns to rows
+        * m: the number of columns
 
         """
         self.table = self.make_table(rule)
         self.n = n
         # a ghost column is added to either end
-        self.m = ratio * n + 3      # add 2 ghost columns
+        self.m = m + 2      # add 2 ghost columns
         self.array = numpy.zeros((n, self.m), dtype=numpy.int8)
         self.next = 0
 
@@ -50,6 +50,10 @@
         for j in xrange(1, self.m - 1):
             a[i, j] = t[tuple(a[i - 1, j-1:j+2])]
 
+    def loop(self, steps=1):
+        """Executes the given number of time steps."""
+        for i in xrange(steps):
+            self.step()
 
     def get_array(self, start=0, end=None):
         """Gets a slice of columns from the CA, with slice indices
@@ -62,16 +66,26 @@
         else:
             return self.array[:, start+1:end+1]
 
+    def wrap(self):
+        """Copies the last row to row 0, then resets the CA to start back at the
+        top.
+
+        """
+        a = self.array
+        a[0, :] = a[self.next - 1, :]
+        self.next = 1
+
 
 if __name__ == '__main__':
 
     import sys
     from CADrawer import PyplotDrawer
 
-    def main(script, rule, n):
+    def main(script, rule, n, m):
         rule = int(rule)
         n = int(n)
-        ca = CircularCA(rule, n)
+        m = int(m)
+        ca = CircularCA(rule, n, m)
         ca.start_single()
         ca.loop(n - 1)
 
diff -r d4d9650afe1e -r 039249efe42f ch6ex2_4.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch6ex2_4.py	Sun Jan 13 16:24:00 2013 -0600
@@ -0,0 +1,73 @@
+"""Chapter 6, exercise 2 in Allen Downey's Think Complexity book.
+
+4. Implement a Rule 30 CA on a ring with a few hundred cells, run it for as many
+   time steps as you can in a reasonable amount of time, and output the center
+   column as a sequence of bits. Test it using DieHarder.
+
+We'll take a slightly different tact. We will create a program that will
+continually output the center column as a bit stream. Once we reach the end of
+the time steps, we'll copy the last row to row 0 and start again. This way we
+can feed the data into dieharder over a pipe without it exhausting our stream.
+
+"""
+import sys
+
+from CircularCA import CircularCA
+
+
+def main(script, bytes_wanted):
+
+    bytes_wanted = int(bytes_wanted)
+
+    # Create a circular CA that is 257 columns; it is odd so that we have a true
+    # "center" column. Our CA will have 8192 steps. This will give us 8192
+    # / 8 == 1024 bytes of pseudo-random (we hope) data using rule 30. Once
+    # we've reached the end of the time steps, we'll copy the last row to the
+    # first and start over.
+
+    rows = 8193
+    cols = 257
+    mid = cols // 2
+    ca = CircularCA(30, rows, cols)
+    ca.start_single()
+
+    iters = 0
+    bytes_produced = 0
+    while True:
+        ca.loop(rows - 1)
+
+        iters += 1
+        if iters == 1:
+            # don't use the first iteration as the first few rows will have 0's
+            # until it fills up
+            ca.wrap()
+            continue
+
+        a = ca.get_array(mid, mid + 1)
+
+        # output the bit stream a byte at a time
+        x = 0
+        i = 0
+        for n, item in enumerate(a):
+            # don't use the first bit because it is a repeat from the previous
+            # iteration
+            if n == 0:
+                continue
+
+            x <<= 1
+            x |= item[0]
+            i += 1
+            if i == 8:
+                sys.stdout.write(chr(x))
+                x = 0
+                i = 0
+                bytes_produced += 1
+                if bytes_produced >= bytes_wanted:
+                    return  # we're done
+
+        # now start the CA over:
+        ca.wrap()
+
+
+if __name__ == '__main__':
+    main(*sys.argv)