"""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.

1. Start with a copy of CA.py named TM.py. Add attributes to represent the
   location of the head, the action table and the state register.

2. Override step to implement a Turing machine update.

3. For the action table, use the rules for a 3-state busy beaver.

"""
import numpy

# Tape head direction constants; None is also a legitimate value to indicate
# no movement:

LEFT, RIGHT = range(2)


class TapeError(Exception):
    """Raised when the tape head goes out of our array bounds."""
    pass


class TM(object):
    """
    A Turing Machine based upon the cellular automaton (CA.py) in Think
    Complexity.

    The tape is divided into cells where each cell can contain a symbol from
    a finite alphabet. We use unsigned 8-bit integers, where 0 is the special
    blank symbol.
    The tape head can read & write symbols onto the tape at its current
    position. The tape head can be moved according to the action table.
    A state register stores the machine's current state. A state value of None
    indicates the machine should halt.
    An action table controls how the machine operates. Each entry in the table
    is of the form:
        (state, input) => (write_symbol, direction, new_state)

    where:
        state: current machine state
        input: current symbol under the machine's tape head
        write_symbol: the symbol to write onto the tape; None means don't write
            anything
        direction: the direction to move the head; can be either LEFT, RIGHT, or
            None to indicate no movement.
        next_state: the new state to transition to

    """
    def __init__(self, init_state, actions, n=100, m=50):
        """Parameters:

        init_state : the initial state of the machine

        actions : the action table dictionary:
            the keys are of the form (state, input)
            the values are a tuple of the form (write_symbol, direction,
            next_state)

        n : the number of rows in the numpy array
        m : the number of columns in the numpy array

        The caller is free to intialize the first row in the array and/or move
        the head prior to calling loop() or step(). Otherwise the tape will be
        all blanks and the head placed in the middle.

        """
        # We use a numpy array to store the state of the tape at each step.
        self.n = n
        self.m = m
        self.array = numpy.zeros((n, m), dtype=numpy.int8)

        # the head is initially in the center of the first row
        self.next = 1               # the next row to update
        self.head = m / 2           # head position
        self.actions = actions      # action table
        self.state = init_state     # state

    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.

        Returns the number of steps executed.

        """
        actual = 0      # actual number of steps executed
        for i in xrange(steps):
            if self.state is None:
                break       # machine has halted
            self.step()
            actual += 1

        return actual

    def step(self):
        """Executes one time step by computing the next row of the array."""
        i = self.next - 1   # the previous state of the tape
        j = self.next       # the row to write
        self.next += 1

        a = self.array
        a[j, :] = a[i, :]   # copy previous state of the tape to next row

        # read the symbol on the tape at the head position
        symbol = a[j, self.head]

        # see what we are supposed to do
        write_symbol, direction, next_state = self.actions[self.state, symbol]

        # write a new symbol
        if write_symbol is not None:
            a[j, self.head] = write_symbol

        # move the head
        if direction == LEFT:
            if self.head > 0:
                self.head -= 1
            else:
                raise TapeError("ran out tape moving LEFT")
        elif direction == RIGHT:
            if self.head < self.m - 1:
                self.head += 1
            else:
                raise TapeError("ran out tape moving RIGHT")

        # change state
        self.state = next_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.
        """
        if start==0 and end==None:
            return self.array
        else:
            return self.array[:, start:end]


if __name__ == '__main__':
    # Test the Turing Machine with the rules for a 3-state, 2 symbol busy beaver

    A, B, C = range(3)

    actions = {
        (A, 0): (1, RIGHT, B),
        (B, 0): (1, LEFT, A),
        (C, 0): (1, LEFT, B),
        (A, 1): (1, LEFT, C),
        (B, 1): (1, RIGHT, B),
        (C, 1): (1, RIGHT, None),
    }

    n = 15
    m = 10
    tm = TM(A, actions, n, m)

    count = tm.loop(n - 1)
    print count
    print tm.array