#!/usr/bin/env python
# coding: utf-8

# # Turing Machine as a Python Generator

# This is a simulator of a Turing machine with a singly-infinite tape. You can run this notebook interactively using [IPython notebook](http://ipython.org/notebook.html). Refer to [this instructions](http://eecs.io/python-environment-for-scientific-computing.html) if you don't have Python or IPython installed.

# In[34]:


import logging

from itertools import islice


# In[35]:


class TuringMachine:
    """Turing machine with a singly-infinite tape.

    A machine is instantiated with transitions, start, accept and reject states
    and a blank symbol. We assume that the input and the tape alphabet can be
    deducted from the transitions.

    :param dict transitions: a mapping from (state, symbol) tuples to (state,
    symbol, direction) tuple. Note that in theory δ is a transition *function*
    (in the sense of mathematical functions), but we expect a mapping, not a
    callable. Directions are either 'L' (for left) or 'R' (for right).

    :param start_state: the initial state of the machine.

    :param accpet_state: the accept state.

    :param reject_state: the reject state.

    :blank_symbol: the special symbold that marks the tape cell to be empty.

    We don't really care what the input alphabet Σ and the tape alphabet Γ are
    for the purpose of this implementation. For a particular run of the machine,
    the tape alphabet is the union of the input, symbols used in transitions and
    the blank symbol.

    The input on the tape is not part of a Turing machine, so it's not required
    on a Turing  machine instantiation. To execute a particular machine use the
    .run() instance method.

    """

    def __init__(self, transitions, start_state='q0', accept_state='qa', reject_state='qr', blank_symbol=''):
        self.blank_symbol = blank_symbol
        self.transitions = transitions
        self.start_state = start_state
        self.reject_state = reject_state

        self.states_to_actions = {
            accept_state: 'Accept',
            reject_state: 'Reject',
        }

    def run(self, input_):
        """Exectute the Turing machine for a particular input.

        :param input_: the input that is written on the tape. It's can be a list
        of strings. Or just a string, in which case each letter is treated as a
        symbol.

        Given an input a machine can run forever or stop after a number of
        steps. So it would be great if we could write a function that
        potentially runs forever and it's up the the caller to decide how many
        steps are executed. Actually, we should not even bother with this. On
        the other side, ^C is not the best way for a user to tell us to stop.
        Instead we give the user control to execute us one step at a time. This
        is what Python generators are (partially) for. The yield expression
        suspends us and gives controll to the caller until he or she decides to
        resume our execution. Have a look to [1] to get familliar with the yield
        keyord and generators, and hopefully never, ever write something like::

            result = []
            for i in range(len(other_items)):
                item = other_items[i]

                result.append(item * 3)

        At each step the generator yields a (action, configuration) tuple.

        The action is either 'Accept', 'Reject' or None. 'Accept' and `Reject`
        are self explanatory and signal that the input is either accepted or
        rejected the machine stops in these states. None is returned in case the
        machine needs to continue running.

        Configuration is a dictionary with the following keys:
        - 'state' the current state,
        - 'left_hand_side': the symbols on the left hand side of the
          current position.
        - 'symbol': the current symbol,
        - 'right_hand_side': the symbols on the right hand side of the
          current position.

        [1] http://www.jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/

        """
        state = self.start_state

        # Theory doesn't say how to implement the tape, so we store the symbols
        # on the tape the way that is most suitable for us. We get two lists to
        # store the symbols from left and right hand sides of the current
        # symbol.
        #
        # Initially, there is the blank symbol on the left. Note, that the
        # element at 0 position is the *closest* to the head.
        left_hand_side = [self.blank_symbol]
        if not input_:
            # In case input is empty, pretend that it consists of a blank.
            input_ = [self.blank_symbol]
        # Consume the right most symbol of the input and make it the current
        # symbol, everything else is stored in a list for the right side
        # symbols.
        symbol = input_[0]
        right_hand_side = list(input_[1:])

        while True:
            # Share our state with the caller.
            # Also give them a chance to control our execution.
            action = self.states_to_actions.get(state)
            yield (
                action,
                {
                    'state': state,
                    'left_hand_side': left_hand_side,
                    'symbol': symbol,
                    'right_hand_side': right_hand_side,
                }
            )

            # Check whether we need to stop the execution.
            if action is not None:
                break

            # Do the transition.
            state, symbol, direction = self.transitions.get(
                (state, symbol),
                (self.reject_state, symbol, 'R'),  # All other transitions are to the reject state.
            )

            if direction == 'R':
                left_hand_side.insert(0, symbol)

                try:
                    symbol = right_hand_side.pop(0)
                except IndexError:
                    # Pretend that we always have a blank symbol on the right.
                    symbol = self.blank_symbol

            elif left_hand_side:
                # Move to the left only if there is a symbold to move.
                right_hand_side.insert(0, symbol)
                symbol = left_hand_side.pop(0)

            else:
                assert direction in 'LR', 'L (left) and R (right) are the only correct directions to move.'
                logging.warning('An attempt to move left from the leftmost cell! The machine stays put.')

    def accepts(self, input_, step_limit=100):
        action = list(islice(self.run(input_), step_limit))[-1][0]

        if action is not None:
            return action == 'Accept'
        else:
            logging.warn(
                'The step limit of %s steps  is reached!',
                step_limit,
            )

    def rejects(self, input_, **kwargs):
        accepts = self.accepts(input_, **kwargs)

        if accepts is not None:
            return not accepts

    def debug(self, input_, step_limit=100, colored=False):
        for action, configuration in islice(self.run(input_), step_limit):
            print(
                '{state:<30} {left}{b}{symbol}{f}{right}'.format(
                    left=''.join(reversed(configuration['left_hand_side'])),
                    right=''.join(configuration['right_hand_side']),
                    b='\x1b[47;1m' if colored else '[',
                    f='\x1b[0m' if colored else ']',
                    **configuration
                )
            )


# # One hash

# In[36]:


one_hash = TuringMachine(
    {
        ('q0', '#'): ('saw_#', '#', 'R'),
        ('saw_#', ''): ('qa', '', 'R'),
    }
)


# In[37]:


execution = one_hash.run('#')


# In[38]:


next(execution)


# In[39]:


next(execution)


# In[40]:


next(execution)


# In[41]:


one_hash.accepts('#')


# In[42]:


assert one_hash.accepts('#')


# In[43]:


assert one_hash.rejects('##')


# In[44]:


assert one_hash.rejects('')


# In[45]:


assert one_hash.accepts('#', step_limit=1) is None


# # Two hashes

# In[46]:


two_hashes = TuringMachine(
    {
        ('q0', '#'): ('saw_#', '#', 'R'),
        ('saw_#', '#'): ('saw_##', '#', 'R'),
        ('saw_##', ''): ('qa', '', 'R'),
    }
)


# In[47]:


assert two_hashes.accepts('##')


# In[48]:


assert two_hashes.rejects('#')


# In[49]:


assert two_hashes.rejects('###')


# # Two same words separated by # (w#w)

# In[50]:


w_hash_w = TuringMachine(
    {
        ('q0', '#'): ('End', '#', 'R'),
        ('End', ''): ('qa', '', 'R'),

        ('q0', '0'): ('FindDelimiter0', 'X', 'R'),
        ('FindDelimiter0', '#'): ('Check0', '#', 'R'),
        ('Check0', '0'): ('FindLeftmost', 'X', 'L'),

        ('q0', '1'): ('FindDelimiter1', 'X', 'R'),
        ('FindDelimiter1', '#'): ('Check1', '#', 'R'),
        ('Check1', '1'): ('FindLeftmost', 'X', 'L'),

        ('FindLeftmost', '0'): ('FindLeftmost', '0', 'L'),
        ('FindLeftmost', '1'): ('FindLeftmost', '1', 'L'),
        ('FindLeftmost', 'X'): ('FindLeftmost', 'X', 'L'),
        ('FindLeftmost', '#'): ('FindLeftmost', '#', 'L'),
        ('FindLeftmost', ''): ('FindNext', '', 'R'),
        
        ('FindNext', 'X'): ('FindNext', 'X', 'R'),
        ('FindNext', '0'): ('FindDelimiter0', 'X', 'R'),
        ('FindNext', '1'): ('FindDelimiter1', 'X', 'R'),
        ('FindNext', '#'): ('End', '#', 'R'),
        
        ('FindDelimiter0', '0'): ('FindDelimiter0', '0', 'R'),
        ('FindDelimiter0', '1'): ('FindDelimiter0', '1', 'R'),
        ('FindDelimiter1', '0'): ('FindDelimiter1', '0', 'R'),
        ('FindDelimiter1', '1'): ('FindDelimiter1', '1', 'R'),
        
        ('Check0', 'X'): ('Check0', 'X', 'R'),
        ('Check1', 'X'): ('Check1', 'X', 'R'),
        
        ('End', 'X'): ('End', 'X', 'R')
    }
)


# In[51]:


assert w_hash_w.accepts('#')


# In[52]:


assert w_hash_w.accepts('0#0')


# In[53]:


assert w_hash_w.accepts('1#1')


# In[54]:


assert w_hash_w.accepts('0000000000000#0000000000000', step_limit=10000)


# In[55]:


assert w_hash_w.accepts('1001#1001')


# In[56]:


assert w_hash_w.rejects('10#1')


# In[57]:


assert w_hash_w.rejects('1#01')


# In[58]:


assert w_hash_w.rejects('1#1#')


# In[59]:


assert w_hash_w.rejects('1##1')


# In[60]:


w_hash_w.debug('11#110', colored=True)


# # Moving left

# In[61]:


move_left = TuringMachine(
    {
        ('q0', ''): ('q0', '', 'L'),
    }
)


# In[62]:


execution = move_left.run('')


# In[63]:


assert next(execution) == (
    None,
    {
        'left_hand_side': [''],
        'right_hand_side': [],
        'state': 'q0',
        'symbol': '',
    },
)


# In[64]:


for _ in range(3):
    assert next(execution) == (
        None,
        {
            'left_hand_side': [],
            'right_hand_side': [''],
            'state': 'q0',
            'symbol': '',
        },
)


# In[65]:


from IPython.display import HTML

HTML(
    """
    <div id="disqus_thread"></div>
    <script type="text/javascript">
        /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
        var disqus_shortname = 'notebookcomments'; // required: replace example with your forum shortname

        /* * * DON'T EDIT BELOW THIS LINE * * */
        (function() {
            var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
            dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        })();
    </script>
    <noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
    """
)



# In[ ]: