"""
Deterministic Turing Machine
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This is a turing machine written in python. This code closely follows code from
chapter 5 of the book _Understanding Computation_ by Tom Stuart.
This is basically a Finite State Machine with a tape.
"""

import collections


LEFT = 'left'
RIGHT = 'right'
BLANK = '_'


Rule = collections.namedtuple('Rule', [
    'state',
    'head',
    'next_state',
    'write',
    'move'])


def rule_applies(rule, state, tape):
    """Determine whether a rule applies to a state."""
    correct_state = rule.state == state
    correct_read = rule.head == tape.head
    return correct_state and correct_read


def follow_rule(rule, state, tape):
    """Follows the current rule."""
    if rule_applies(rule, state, tape):
        state = rule.next_state
        tape.middle = rule.write
        tape.move(rule.move)

    return rule, state, tape


class Tape(object):
    """Represents the tape in a turing machine."""
    def __init__(self, left=None, middle=None, right=None, blank=BLANK):
        """Initialize and show initial state."""
        self.left = left or []
        self.right = right or []

        self.middle = middle
        if self.middle is None:
            self.middle = blank

        self.blank = blank

    def move_right(self):
        """Move tape one unit right, add blanks as needed."""
        self.left = self.left + [self.middle]
        if self.right:
            self.middle = self.right.pop(0)
        else:
            self.middle = self.blank

    def move_left(self):
        """Move tape one unit left, add blanks as needed."""
        self.right = [self.middle] + self.right
        if self.left:
            self.middle = self.left.pop()
        else:
            self.middle = self.blank

    @property
    def head(self):
        return str(self.middle)

    def move(self, direction):
        """Move tape left or right."""
        if not direction in [LEFT, RIGHT]:
            raise RuntimeError('Unrecognized direction "%s"' % direction)

        if direction == LEFT:
            return self.move_left()

        if direction == RIGHT:
            return self.move_right()

    def __repr__(self):
        """Tape state with current head in parens, like _12(3)4."""
        out = '{}({}){}'.format(
            ''.join(map(str, self.left)),
            self.middle,
            ''.join(map(str, self.right)))
        return out


class DeterministicTuringMachine(object):
    """This is a turing machine."""
    def __init__(self, state, tape, accept_states, rules):
        """
        Initialize machine
        :state: - integer - that represents the current state of the machine
        :tape: - Tape - the machine's tape
        :accept_states: - [integer] - represents states when the machine has
                                      exited successfully
        :rules: - [Rule] - list of rules for the machine to follow
        """
        self.state = state
        self.tape = tape
        self.accept_states = accept_states
        self.rules = rules

    @property
    def accepting(self):
        return self.state in self.accept_states

    @property
    def stuck(self):
        """Stuck when we have no next rule."""
        return not self.next_rule

    @property
    def working(self):
        """Working when not done and we still have rules to apply."""
        return not (self.accepting or self.stuck)

    @property
    def next_rule(self):
        """Get next rule."""
        rules = self._find_rules()

        if rules:
            return rules[0]

        return rules

    def _find_rules(self):
        """Find a rules we can apply."""
        applicable_rules = [rule for rule in self.rules
                            if rule_applies(rule, self.state, self.tape)]

        return applicable_rules

    def step(self):
        """Apply any rules we can find."""
        _, self.state, self.tape = follow_rule(
            self.next_rule, self.state, self.tape)

    def run(self):
        while self.working:
            self.step()