"""
 yvtm.py - yaml virtual turing machine

 Usage:

   $ python yvtm.py busybeaver3.yvtm
     <0> : one
      1 <0> : two
      1  0 <0> : three
      1 <0> 1  : three
     <1> 1  1  : three
     <0> 1  1  1  : one
      1 <1> 1  1  : two
      1  1 <1> 1  : two
      1  1  1 <1> : two
      1  1  1  1 <0> : two
      1  1  1  1  0 <0> : three
      1  1  1  1 <0> 1  : three
      1  1  1 <1> 1  1  : three
      1  1 <1> 1  1  1  : one
      1  1  1 <1> 1  1  : HALT
     ** HALT **  (No matching rule)    

   $ python yvtm.py -help
    yvtm.py : YAML Virtual Turing Machine in python 
    Usage: python yvtm.py [-quiet] [-help] [tape=...] filename.yvtm 

   $ python yvtm.py -quiet busybeaver3.yvtm 
      1  1  1 <1> 1  1  : HALT
    
   $ python yvtm.py -tape=foo busybeaver3.yvtm 
     <f> o  o  : one
     ** HALT **  (No matching rule)
      
 See the comments in ./busybeaver3.yvtm for the YAML machine specification.
 
 Tested with python 2.7.12.

 History
   2016-10-03  first working version
   2016-10-10  added -tape option
     
 Jim Mahoney | MIT License
"""
import sys, yaml

def tape_state_string(tape, position, state):
    """ Return a string representation of current turing machine status """
    line = "  "
    for i in range(len(tape)):
        if i == position:
            line += "<{}>".format(tape[i])
        else:
            line += " {} ".format(tape[i])
    line += " : {}".format(state)
    return line

def run(turing, verbose=True):
    """ Simulate a Turing machine,
        printing each step if verbose is True. """

    offset = {'right': 1, 'left': -1, 'stay': 0}
        
    # Initialize the machine.
    state = turing['start']          # e.g. 'start'
    tape = list(turing['tape'])      # e.g. ['0', '0', '1']
    position = 0                     # position of read head on tape

    # Convert the machine table into a more convenient dictionary form.
    rules = {}
    for rule in turing['machine']:
        try:
            assert len(rule) == 5
        except AssertionError:
            print "Oops - the rule {} doesn't have 5 parts.".format(rule)
            return
        rule = map(str, rule)
        (this_state, read_symbol, next_state, write_symbol , move) = rule
        if not rules.has_key(this_state):
            rules[this_state] = {}
        rules[this_state][read_symbol] = {'next': next_state,
                                          'write': write_symbol,
                                          'move': move }

    # Run the machine.
    while True:
        
        if verbose:
            print tape_state_string(tape, position, state)
                        
        if state in turing['accept']:
            if verbose:
                print "  ** Accept **"
            break
        
        if state in turing['reject']:
            if verbose:
                print "  ** Reject **"
            break
        
        try:
            update = {}
            symbol = tape[position]
            for what in ('next', 'write', 'move'):
                update[what] = rules[state][symbol][what]
                
        except KeyError:
            if verbose:
                print "  ** HALT **  (No matching rule)"
            break

        try:        
            state = update['next']
            tape[position] = update['write']
            position += offset[update['move']]
        except KeyError:
            if verbose:
                print "  ** HALT ** (Movement {} not recognized)".format(
                    update['move'])
            break
        
        while position < 0:            # moved off left edge of tape
            tape = [ turing['blank'] ] + tape
            position += 1
            
        while position >= len(tape):   # moved off right edge of tape
            tape = tape + [ turing['blank'] ]

    if not verbose:
        print tape_state_string(tape, position, state)

def get_options():
    """ Return (file, verbose, tape) from command line invocation
        where tape=None if it isn't set there.
        Or print the help message and exit if -help or no filename.
    """
    help = " yvtm.py : YAML Virtual Turing Machine in python \n" + \
           " Usage: python yvtm.py [-quiet] [-help] [tape=...] filename.yvtm "
    verbose = True
    tape = None
    for arg in sys.argv:
        if arg[:2] == '-h':    # i.e. -help
            print help
            sys.exit()
        if arg[:2] == '-q':    # i.e. -quiet
            verbose = False
        if arg[:2] == '-t':    # i.e. -tape=00110
            tapestring = arg.split('=')
            if len(tapestring) == 2:
                tape = tapestring[-1]
    if len(sys.argv) < 2:
        print help
        sys.exit()
    return (sys.argv[-1], verbose, tape)
        
def main():
    (filename, verbose, tape) = get_options()
    turing = yaml.load(open(filename))
    if tape != None:
        turing['tape'] = tape
    run(turing, verbose)
    
if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()