Python sol'n to QOTW#24/Turing Machine

I've cleaned up my TM code and removed the Tape class I was using.
It's now about twice as fast.

This solution uses a dictionary for the tape.  It's pretty
much the same solution others have posted, except in Python.


#!/usr/bin/env python

# "Turing Machine"
# A Python solution to the Perl Quiz of the Week #24
#
# Andrew Dalke, 9/18/2004
# Contributed to the public domain

import re


# Blank line, possibly with comment
ignore = re.compile(r"^\s*(#.*)?$").match

parse_codeline = re.compile(r"""
\s*
   (?P<at_state>\w+)\s+
   (?P<read_char>\w)\s+
   (?P<new_state>\w+)\s+
   (?P<write_char>\w)\s+
   (?P<dir>[RL])
   (\s*(\#.*)?)?   # optional trailing spaces and comment
$""", re.X).match

def read_program(program):
     """program = <Turing program as a string>

     Parse it and return the initial state and state table
     """
     state_table = {}
     initial_state = None
     for lineno, line in enumerate(program.split("\n")):
         if ignore(line):
             continue
         m = parse_codeline(line)
         if not m:
             raise SystemExit("Syntax error, line %d: %r" %
                              (lineno+1, line))
         if initial_state is None:
             initial_state = m.group("at_state")
         new_entry = (m.group("at_state"), m.group("read_char"))
         if new_entry in state_table:
             raise SystemExit("Duplicate start state, line %d: %r" %
                              (lineno+1, line))

         if m.group("dir") == "L":
             dir = -1
         else:
             dir = 1
         state_table[new_entry] = (
             m.group("new_state"), m.group("write_char"), dir)

     return initial_state, state_table

def make_tapestr(tape):
     """Tape as dictionary -> tape as string"""
     items = tape.items()
     items.sort()
     return "".join([item[1] for item in items]).strip("_")

def compute(program, tape, state = None):
     initial_state, state_table = read_program(program)
     if state is None:
         state = initial_state

     head = 0
     while 1:
         c = tape.get(head, "_")
         try:
             state, write_c, dir = state_table[(state, c)]
         except KeyError:
             break
         tape[head] = write_c
         head += dir

     return tape, state, c


def usage(outfile):
     print >>outfile, """Usage: turing.py <state-filename> [initial tape]
Example: turing.py stackm.tm 11111P11PD
"""

def main():
     import sys
     if not (2 <= len(sys.argv) <= 3):
         usage(sys.stderr)
         sys.exit(1)
     filename, tapestr = (sys.argv[1:] + [""])[:2]

     # the 'tape' is actually a dictionary
     # the key is the index, value is the character.
     # make it from the input tape string
     tape = dict(enumerate(tapestr))

     compute(open(filename).read(), tape)

     print make_tapestr(tape)

if __name__ == "__main__":
     main()


					Andrew
					dalke-DxsMES/F/[email protected]