# Universal TM
# Author: ## YOUR NAME HERE ##
# Boston University CS 332

# This file contains starter code to help you design a program that 
# 1) Prompts the user for a string encoding a TM M and a binary string w
# 2) Prints the sequence of configurations M enters when run on w, as well as whether M accepts or rejects on input w
#
# Your job is to implement the function simulate_TM that simulates running M on w and outputs the list of configurations it enters
#
# Our autograder will run two types of tests:
# (1) Visible tests for debugging: It will tell you what machine/input is being fed and whether your simulator ran correctly. If the output of your code does not match the expected output, it will tell you what went wrong.
# (2) Tests that will be published after grade release: You will be able to see your score for these when you submit, but you won't be able to see what the tests are until we publish the grades. 
# Our autograder prunes all trailing blank spaces from configurations before comparing, so you do not need to worry about how many such blank spaces your code produces.

import re

class UniversalTM(object):
   
    # Parse an encoded TM into a list of transitions
    def encoding_to_transitions(self, encoded_TM):
        
        # Use regular expression(!) to split string encoding transition function into list of 5-tuples]
        list_transitions = re.findall(r'(\w+,\w+,\w+,\w+,\w+)', encoded_TM)
        
        # Convert list of transitions into dictionary
        transitions = {}    # initialize empty dictionary
        for tuple in list_transitions:
            tuple_list = tuple.split(",")
            transitions[(tuple_list[0], tuple_list[1])] = (tuple_list[2], tuple_list[3], tuple_list[4])
            
        return transitions
        
    # Convert a configuration (state + tape contents + head location) to a string
    # Input: String state (e.g., "q1"), list tape (e.g., ["1", "_", "0"]), index head (e.g., 1)
    # Output: String config (e.g., "1 q1 _0")
    def config_to_string(self, state, tape, head):
        result = tape.copy()  # don't modify the input tape
        result.insert(head, " " + state + " ")
        return "".join(result)

######################################################
######## DON'T TOUCH THE CODE ABOVE THIS LINE ########
######################################################
    
    # Input: 
    # -----------------
    # In general, a TM is described by a 7-tuple (Q, Sigma, Gamma, delta, q0, qa, qr). To make everything simpler, we will assume that the input alphabet Sigma = {0, 1} and the tape alphabet
    # Gamma = {0, 1, _}. We will also simplify the encoding of the TM by representing the state set Q implicitly in the description of the transition function, and assuming that the 
    # start state, accept state, and reject state are always labeled q0, qa, qr, respectively.
    #
    # The input is a string encoded_TM encoding a TM under the above assumptions
    # The format of the encoding for a TM is a #-separated list of 5-tuples representing the transition function
    # Each 5-tuple should be formatted (<current state>, <current symbol>, <new symbol>, <direction>, <new state>)
    # Here, <direction> is either l, r, or s for move left, move right, or stay put, respectively
    #
    # Example: encoded_TM = "(q0,0,_,r,1o)#(q0,1,_,r,1i)#(q0,_,_,s,qa)#(1o,_,_,l,2o)#(1o,0,0,r,1o)#(1o,1,1,r,1o)#(1i,_,_,l,2i)#(1i,0,0,r,1i)#(1i,1,1,r,1i)#(2o,0,_,l,3)#(2o,_,_,s,qa)#(2o,1,1,s,qr)#(2i,1,_,l,3)#(2i,_,_,s,qa)#(2i,0,0,s,qr)#(3,_,_,s,qa)#(3,0,0,l,4)#(3,1,1,l,4)#(4,0,0,l,4)#(4,1,1,l,4)#(4,_,_,r,q0)" 
    # encodes a TM testing whether its input is a binary palindrome (this example is from morphett)
    # input_string = "1001001" specifies a binary input to the above TM
    #
    # Output:
    # ----------------
    # Return a list of configurations the TM enters when processing input_string, followed by whether the TM accepts or rejects
    # Example: transcript = [' q0 1001001', '_ 1i 001001', '_0 1i 01001', '_00 1i 1001', '_001 1i 001', '_0010 1i 01', '_00100 1i 1', '_001001 1i _', '_00100 2i 1_', '_0010 3 0__', '_001 4 00__', '_00 4 100__', '_0 4 0100__', '_ 4 00100__', ' 4 _00100__', '_ q0 00100__', '__ 1o 0100__', '__0 1o 100__', '__01 1o 00__', '__010 1o 0__', '__0100 1o __', '__010 2o 0__', '__01 3 0___', '__0 4 10___', '__ 4 010___', '_ 4 _010___', '__ q0 010___', '___ 1o 10___', '___1 1o 0___', '___10 1o ___', '___1 2o 0___', '___ 3 1____', '__ 4 _1____', '___ q0 1____', '____ 1i ____', '___ 2i _____', '___ qa _____', 'accept']
    def simulate_TM(self, encoded_TM, input_string):
        transitions = self.encoding_to_transitions(encoded_TM)
        transcript = []
        
        ## OPTIONAL STUFF:
        ## You may want to uncomment some of the code snippets below to get a feel for the syntax of the various components output by the parser

        ## transitions is a dictionary (set of key-value pairs). Keys are pairs (<current state>, <current symbol>) and values are triples (<new symbol>, <direction>, <new state>)

        # print(transitions)
        # print(transitions[("q0", "0")])
        
        #
        # YOUR CODE HERE
        #
            
        return transcript


######################################################
######## DON'T TOUCH THE CODE BELOW THIS LINE ########
######################################################

    def prompt(self):
        # Prompts the user for an encoded TM and a string, and simulates the TM on that string
        encoded_TM = input("Enter your TM: ")  
        input_string = input("Enter your string: ")  
        transcript = self.simulate_TM(encoded_TM, input_string)
        for str in transcript:
            print(str)


if __name__ == "__main__":
    universal_TM = UniversalTM()
    universal_TM.prompt()