#!/usr/bin/ruby

def show_debug_info state, memory, pointer, last_value
  0.upto pointer-1 do
    print " "
  end
  puts "\\/"
  print " "
  0.upto last_value do |i|
    print memory[i]
  end
  puts " " + state
end

unless ARGV[0]
  puts "First argument must be tape length!"
  exit
end

program = Hash.new
STDIN.each_line do |line|
  line.chomp!
  break if line == "."
  begin
    left, right = line.split "->"
    left_state, left_value = left.split ","
    program[left_state] = Hash.new unless program[left_state]
    program[left_state][left_value] = right.split ","
  rescue
    puts "Error at line:\n" + line
    exit
  end
end

state = "q0"
length = ARGV.shift.to_i
memory = Array.new length, "B"
pointer = 1

require 'set'
require 'digest/md5'
signatures = Set.new

ARGV.each do |parameter|
  parameter.split(//).each do |c|
    memory[pointer] = c
    pointer += 1
  end
  pointer += 1
end

last_value = pointer
pointer = 1

while state != "qf"
  show_debug_info state, memory, pointer, last_value

  unless program[state] && program[state][memory[pointer]]
    puts "Undefined state: " + state + "," + memory[pointer]
    exit
  end

  instruction = program[state][memory[pointer]]
  memory[pointer] = instruction[0]
  state = instruction[2]

  case instruction[1]
  when "L"
    pointer -= 1
  when "R"
    pointer += 1
  when "_"
  else
    puts "Undefined instruction: " + instruction[1]
    exit
  end
  if pointer < 0 || pointer >= length
    puts "Out of memory range"
    exit
  end
  last_value = pointer if pointer > last_value

  signature = Digest::MD5.hexdigest(memory.inspect + "\t" + state + "\t" + pointer.to_s)
  if signatures.include? signature
    puts "Endless loop."
    exit
  end
  signatures.add signature
end

show_debug_info state, memory, pointer, last_value