# 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

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()