#!/usr/bin/python -tt

import sys

class Turing:
    state = '1'             # The current state of the machine
    cp = 0                  # current position of the head
    transistion_count = 0   # number of times the head executed a command
    running = False         # flag to stop the machine

    def __init__(self):
        self.running = True

    def IsRunning(self):
        return self.running

    def QuitWithError( self, error, tape, rule ):
        print error
        print "Rule :", rule
        print "State :", self.state
        print "Head position :", self.cp
        print "Transistion Count :", self.transistion_count
        print "Tape :", tape

        sys.exit(0)

    def GetTransistionCount(self):
        return self.transistion_count

    def Step (self, tape, transistion_table ):
        state = self.state
        cp = self.cp

        # get the character under the the current position on the tape
        head = tape[cp]

        # the '#' character is a signal to stop the machine
        if state == "#":
            self.running = False

        # loop through the program table, and determine what action needs to be done
        for t in transistion_table:
            rules = t.split()
            if rules[0] == state:
                if rules[1] == head:
                    self.state = rules[2]

                    self.transistion_count += 1

                    # this simple replaces a character in the tape string with what ever is under
                    # rules[3] - yes its ugly, but im ashamed to admit I don't know how else to do it
                    tmp = list(tape)
                    tmp[cp] = rules[3]
                    tape = ''.join(tmp)

                    # determine which direction to move the head
                    if rules[4] == "R": self.cp+=1
                    if rules[4] == "L": self.cp-=1


                    # simple error checking that stop the program if the current position is out
                    # of bounds of the string
                    if self.cp == -1:
                            self.QuitWithError( 'Head moved out of bounds of tape < Start', tape, t )

                    if self.cp == len(tape):
                            self.QuitWithError( 'Head moved out of bounds of tape > End', tape, t )


                    return tape

                #self.QuitWithError( 'Can not find a valid rule' , tape, transistion_table ) # This is on the wrong line... TODO FIXME
        return tape

    def MakeTable(self):
		# program syntax ( "State Character NewState NewCharacter Movement")
		# Program commands are seperated by a blank whitespace character to make a 5 tuple command string

		# In english, the turing Step code performs this:

		# If current state is 'State' and character under head is 'Character' then
		# change current state to 'NewState' and print 'NewCharacter' under the head,
		# then move the head position across by 'Movement'
        table = []
        table.append ("1 _ 2 : R")
        table.append ("2 A 3 _ R")
        table.append ("2 B 4 _ R")
        table.append ("2 _ 7 _ L")
        table.append ("3 A 3 A R")
        table.append ("3 B 3 B R")
        table.append ("3 _ 5 _ L")
        table.append ("4 A 4 A R")
        table.append ("4 B 4 B R")
        table.append ("4 _ 6 _ L")
        table.append("5 A 11 _  L")
        table.append("5 B 12 _  L")
        table.append("5 _ 7 _  L")
        table.append("6 A 12 _  L")
        table.append("6 B 11 _  L")
        table.append("6 _ 7 _  L")
        table.append("7 _ 7 _  L")
        table.append("7 : 8 _ R")
        table.append("8 _ 9 Y R")
        table.append("9 _ 10 E R")
        table.append("10 _ # S R")
        table.append("11 A 11 A  L")
        table.append("11 B 11 B  L")
        table.append("11 _ 2 _ R")
        table.append("12 A 12 _  L")
        table.append("12 B 12 _  L")
        table.append("12 _ 12 _  L")
        table.append("12 : 13 _ R")
        table.append("13 _ 14 N R")
        table.append("14 _ # O R")
        return table

def main():

    turing = Turing()

    # the tape is simple a string, using the underscore character to represent a blank space
    tape = '_ABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBAABBBA__'
    # load the program
    table = turing.MakeTable()

    print "Running Program..."
    while turing.IsRunning():
        tape = turing.Step( tape, table )
        #print tape # warning this is really slow

    print tape
    print "Transistion Count :", turing.GetTransistionCount()



if __name__ == "__main__":
    main()