# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1358626632 21600
# Node ID 1804f09a7adbe5caff0ad0c6462796dc3988b61d
# Parent  362d4ec7e7948dfd049ec55bcf48c8fd774de0e6
Chapter 6, exercise 4, part 4. A Turing Machine drawer.

diff -r 362d4ec7e794 -r 1804f09a7adb TM.py
--- a/TM.py	Wed Jan 16 21:44:02 2013 -0600
+++ b/TM.py	Sat Jan 19 14:17:12 2013 -0600
@@ -79,6 +79,9 @@
         self.actions = actions      # action table
         self.state = init_state     # state
 
+        # keep a history of head position & state tuples
+        self.history = []
+
     def loop(self, steps=1):
         """Attempts to execute the given number of steps. May exit early if the
         machine is already halted or halts during execution.
@@ -97,6 +100,11 @@
 
     def step(self):
         """Executes one time step by computing the next row of the array."""
+
+        if len(self.history) == 0:
+            # record initial head position & state
+            self.history.append((self.head, self.state))
+
         i = self.next - 1   # the previous state of the tape
         j = self.next       # the row to write
         self.next += 1
@@ -129,6 +137,9 @@
         # change state
         self.state = next_state
 
+        # record what happened in our history
+        self.history.append((self.head, self.state))
+
     def get_array(self, start=0, end=None):
         """Gets a slice of columns from the array, with slice indices
         (start, end).  Avoid copying if possible.
@@ -160,3 +171,17 @@
     count = tm.loop(n - 1)
     print count
     print tm.array
+
+    from TMDrawer import TMDrawer
+
+    tape_colors = {0: 0, 1: 40}
+    state_colors = {
+        A: 10,
+        B: 20,
+        C: 30,
+        None: 40
+    }
+
+    drawer = TMDrawer(tape_colors, state_colors, cmap='spectral')
+    drawer.draw(tm)
+    drawer.show()
diff -r 362d4ec7e794 -r 1804f09a7adb TMDrawer.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TMDrawer.py	Sat Jan 19 14:17:12 2013 -0600
@@ -0,0 +1,70 @@
+"""Chapter 6, exercise 4 in Allen Downey's Think Complexity book.
+
+The goal of this exercise is to implement a Turing machine.
+See http://en.wikipedia.org/wiki/Turing_machine.
+
+4. Write a class named TMDrawer that generates an image that represents the
+   state of the tape and the position and state of the head. For one example of
+   what that might look like, see
+   http://mathworld.wolfram.com/TuringMachine.html.
+
+"""
+import matplotlib.pyplot as pyplot
+import numpy
+
+from CADrawer import Drawer
+
+
+class TMDrawer(Drawer):
+    """Implementation of Drawer using matplotlib for Turing Machines.
+
+    We visualize the tape and machine head/state by drawing the tape state as
+    a row, then adding a row underneath that for the head & state. The tape head
+    is drawn as a solid square whose color represents the state.
+
+    """
+    def __init__(self, tape_colors, state_colors, cmap=None):
+        self.tape_colors = tape_colors
+        self.state_colors = state_colors
+        self.cmap = cmap if cmap else 'spectral'
+
+    def draw(self, tm, start=0, end=None):
+        """Draws the TM using pyplot.pcolor."""
+        tape = tm.get_array(start, end)
+        rows, cols = tape.shape
+
+        # create a new array that has twice as many rows
+        steps = rows
+        rows *= 2
+        a = numpy.zeros((rows, cols), dtype=numpy.int8)
+
+        # copy the tape state into the array at every other row
+        for i in xrange(steps):
+            for j in xrange(cols):
+                #a[n, j] = self.tape_colors[tape[i, j]]
+                c = self.tape_colors[tape[i, j]]
+                a[i * 2, j] = c
+
+        # copy the head position & state into every other row
+        n = 1
+        for pos, state in tm.history:
+            a[n, pos] = self.state_colors[state]
+            n += 2
+
+        # flipud puts the first row at the top;
+        pyplot.pcolor(numpy.flipud(a), cmap=self.cmap)
+        pyplot.axis([0, cols, 0, rows])
+        pyplot.colorbar()
+
+        # empty lists draw no ticks
+        pyplot.xticks([])
+        pyplot.yticks([])
+
+    def show(self):
+        """display the pseudocolor representation of the CA"""
+        pyplot.show()
+
+    def save(self, filename='tm.png'):
+        """save the pseudocolor representation of the TM in (filename)."""
+        pyplot.savefig(filename)
+