Re: [QUIZ] The Turing Machine (#162)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thanks for the fun quiz. For fun I over-egged the solution:

tape.rb:

# Turing machine tape.
class Tape

   def initialize(string='')
     @string = string.length.zero? ? '_' : string.dup
     @offset = 0
   end

   def read
     return @string[@offset].chr
   end

   def write(one_char_string)
     @string[@offset] = one_char_string[0]
     return
   end

   def move_head_left
     if @offset == 0
       @string.insert(0, '_')
     else
       @offset -= 1
     end
     return
   end

   def move_head_right
     @offset += 1
     if @offset == @string.length
       @string.insert(-1, '_')
     end
     return
   end

   def content
     return @string.dup
   end

   attr_reader :offset
end

turing.rb:

class Turing
   def initialize(lines)
     @action, @initial_state = load(lines)
   end

   def run(tape)
     state = @initial_state
     while action = @action[state][tape.read]
       state = do_action(tape, state, *action)
     end
   end

   def do_action(tape, current_state, next_state, write, move)
     tape.write(write)
     case move
     when "L" then tape.move_head_left
     when "R" then tape.move_head_right
     end
     return next_state
   end

   def load(lines)
     action = Hash.new { |h,k| h[k] = {} }
     initial_state = parse(lines) do |current_state, read, next_state,  
write, move|
       action[current_state][read] = [next_state, write, move]
     end

     return action, initial_state
   end

   # Make sure that the lines we are loading are all valid.  Raise a  
runtime error
   # if we suspect that garbage is being passed in.  As each line is  
parsed we yield
   # the validated information.  The return value is the first  
current_state mentioned
   # in the lines passed in.
   #
   # The spec of the quiz maps neatly to a regex, so we'll go with the
   # terse "parsing" and generic error message (we could keep track of  
line
   # number in future if we wanted to be helpful)

   def parse(lines)
     initial_state = nil
     lines.each_line do |line|
       # deal with comments and blank lines
       instructions = line.sub(/\s*#.*/, '')
       next if instructions =~ /^\s*$/

       unless instructions =~ /^ \s* (\w+) # current state => $1
                                 \s+ (\w)  # read char => $2
                                 \s+ (\w+) # next state => $3
                                 \s+ (\w)  # char to write => $4
                                 \s+ (L|R) # tape head move direction  
=> $5
                                 \s* $
                              /x
         raise RuntimeError, "bad line '#{line}'"
       end

       current_state, read, next_state, write, move = $1, $2, $3, $4, $5
       initial_state ||= current_state;
       yield current_state, read, next_state, write, move
     end

     return initial_state
   end
end

Having Turing::run call Turing::do_action let me play with  
Console::ANSICode for fun:

tm.rb:

#!/usr/bin/env ruby
#
# Ruby quiz 162
#
# usage:
#
# tm.rb [-d] program_file tape1 [tape2 [...]]

require 'turing'
require 'tape'

class DisplayTuring < Turing
   require 'rubygems'
   require 'facets/ansicode'
   include Console::ANSICode
   def do_action(tape, current_state, next_state, write, move)
     content = tape.content
     offset = tape.offset
     puts blue{ current_state } + "\t" +
         blue{ content[0, offset]      || '' } +
         black{ on_cyan { content[offset, 1]      || '' } }  +
         blue{ content[offset+1 .. -1] || '' }
     super
   end
end

machine_type = Turing
if ARGV.length > 0 && ARGV[0] == '-d'
   machine_type = DisplayTuring
   ARGV.shift
end

if ARGV.length < 2
   raise RuntimeError, "bad args on command line"
end

t = machine_type.new(File.open(ARGV.shift))
ARGV.each do |tape_content|
   tape = Tape.new(tape_content)
   t.run(tape)
   puts tape.content.tr('_', ' ').strip
end


- --

Mike Stok <[e-mail]>
http://www.stok.ca/~mike/

The "`Stok' disclaimers" apply.




-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Darwin)

iEYEARECAAYFAkgneKsACgkQnsTBwAWZE9qfPgCeJ+jNl2Rk9baHPSfAqvOZJ3Ih
R3EAniCupYipgp9OtejcQ/b+ddBfG3ND
=pA5K
-----END PGP SIGNATURE-----