pacman.rb

#!/usr/bin/env ruby
# works on Ruby 1.9.2 (maybe on Ruby 1.9.1, too)

class Loc
  def initialize(x, y)
    @x = x
    @y = y
  end

  attr_reader :x, :y

  def ==(p)
    @x == p.x && @y == p.y
  end

  alias_method :eql?, :==

  def hash
    @x * 1000 + @y
  end

  def -(p)
    self.class.new(@x - p.x, @y - p.y)
  end

  MOVEMENTS = {
    down: Loc.new(0, 1),
    left: Loc.new(-1, 0),
    up: Loc.new(0, -1),
    right: Loc.new(1, 0),
  }

  def move(dir)
    m = MOVEMENTS[dir]
    self.class.new(@x + m.x, @y + m.y)
  end
end

class Mover
  def initialize(loc, prev = nil)
    @loc = loc
    @prev = prev
  end

  attr_reader :loc, :prev

  def move_to?(x, y)
    MAP[y][x]
  end

  def move?(dir)
    d = Loc::MOVEMENTS[dir]
    move_to?(@loc.x + d.x, @loc.y + d.y)
  end

  private

  def all_moves
    cx = @loc.x; cy = @loc.y
    [[cx - 1, cy], [cx, cy - 1],
     [cx + 1, cy], [cx, cy + 1] ].find_all do |x, y|
      move_to?(x, y)
    end
  end
end

class Jiki < Mover
  def initialize(loc, prev = nil)
    @hist = []
    super(loc, prev)
  end

  def move_to_loc(loc)
    self.class.new(loc, self)
  end
end

class Enemy < Mover
  def move_next(jiki)
    self.class.new(next_loc(jiki), self)
  end

  def next_loc(jiki)
    if @prev
      m = all_moves
      if m.size == 1            # deadend
        Loc.new(m[0][0], m[0][1])
      elsif m.size == 2         # way
        n = m.find {|e| !(e[0] == @prev.loc.x && e[1] == @prev.loc.y) }
        Loc.new(n[0], n[1])
      else                      # cross
        next_loc_cross(jiki)
      end
    else                        # 1st step
      next_loc_cross_base(jiki)
    end
  end

  def next_loc_cross_base(jiki)
    @loc.move([:down, :left, :up, :right].find {|dir| move?(dir) })
  end

  def to_char
    self.class.to_s[-1]
  end

  private

  def turn_l2r
    d = @loc - @prev.loc
    x = d.x <=> 0; y = d.y <=> 0
    [[y, - x], [x, y], [- y, x]] # left, ahead, right
  end

  def turn_r2l
    d = @loc - @prev.loc
    x = d.x <=> 0; y = d.y <=> 0
    [[- y, x], [x, y], [y, - x]] # right, ahead, left
  end
end

class EnemyV < Enemy
  def next_loc_cross(jiki)
    d = jiki.loc - @loc
    if d.y > 0 && move?(:down)
      @loc.move(:down)
    elsif d.y < 0 && move?(:up)
      @loc.move(:up)
    elsif d.x > 0 && move?(:right)
      @loc.move(:right)
    elsif d.x < 0 && move?(:left)
      @loc.move(:left)
    else
      next_loc_cross_base(jiki)
    end
  end
end

class EnemyH < Enemy
  def next_loc_cross(jiki)
    d = jiki.loc - @loc
    if d.x > 0 && move?(:right)
      @loc.move(:right)
    elsif d.x < 0 && move?(:left)
      @loc.move(:left)
    elsif d.y > 0 && move?(:down)
      @loc.move(:down)
    elsif d.y < 0 && move?(:up)
      @loc.move(:up)
    else
      next_loc_cross_base(jiki)
    end
  end
end

class EnemyL < Enemy
  def next_loc_cross(jiki)
    turn_l2r.each do |dx, dy|
      nx = @loc.x + dx; ny = @loc.y + dy
      if move_to?(nx, ny)
        return Loc.new(nx, ny)
      end
    end
    raise "No Way: (#{@loc.x}, #{@loc.y}, #{turn_l2r}"
  end
end

class EnemyR < Enemy
  def next_loc_cross(jiki)
    turn_r2l.each do |dx, dy|
      nx = @loc.x + dx; ny = @loc.y + dy
      if move_to?(nx, ny)
        return Loc.new(nx, ny)
      end
    end
    raise "No Way: (#{@loc.x}, #{@loc.y}, #{turn_l2r}"
  end
end

class EnemyJ < Enemy
  def initialze
    @flag = true
    super
  end

  def next_loc_cross(jiki)
    ary = @flag ? turn_l2r : turn_r2l
    @flag = !@flag
    ary.each do |dx, dy|
      nx = @loc.x + dx; ny = @loc.y + dy
      if move_to?(nx, ny)
        return Loc.new(nx, ny)
      end
    end
    raise "No Way: (#{@loc.x}, #{@loc.y}, #{turn_l2r}"
  end
end

MAP = []

class State
  def parse_file(file)
    @jiki = nil
    @enemies = []
    @dots = {}
    @points = 0
    @hist = []
    @next_link = nil
    @visited = false
    open(file) do |io|
      @life = io.gets.chomp.to_i
      io.gets                   # just skip field size
      io.each_line.with_index do |s, y|
        MAP << s.chomp.split(//).map.with_index {|c, x| char2item(c, x, y)}
      end
    end
    self
  end

  attr_reader :life, :hist, :points, :prev, :next_link, :visited

  def to_s
    m = MAP.map.with_index do |row, y|
      row.map.with_index do |col, x|
        col ? (@dots[Loc.new(x, y)] ? '.' : ' ') : '#'
      end
    end
    @enemies.each {|e| m[e.loc.y][e.loc.x] = e.to_char }
    m[@jiki.loc.y][@jiki.loc.x] = '@'
    "#{@life.to_s}:#{@points}\n" + m.map {|row| row.join }.join("\n")
  end

  def next_states
    tmpl = dup.step
    @visited = true
    link = self
    cx = @jiki.loc.x; cy = @jiki.loc.y
    [[cx, cy, '.'], [cx - 1, cy, 'h'], [cx, cy - 1, 'k'],
     [cx + 1, cy, 'l'], [cx, cy + 1, 'j'] ].find_all do |x, y, c|
      @jiki.move_to?(x, y) or next
      st = tmpl.dup.move_jiki(Loc.new(x, y), c)
      unless st.eaten?
        link = st.check_dot.set_next_link(link)
      end
    end
    link
  end

  def eaten?
    @enemies.any? do |e|
      e.loc == @jiki.loc ||
        (e.prev && e.prev.loc == @jiki.loc && e.loc == @jiki.prev.loc)
    end
  end

  def dot_complete?
    @dots.empty?
  end

  KEY2MOVE = {
    'j' => Loc.new(0, 1),
    'h' =>  Loc.new(-1, 0),
    'k' =>  Loc.new(0, -1),
    'l' => Loc.new(1, 0),
    '.' => Loc.new(0, 0),
  }

  def play(c)
    m = KEY2MOVE[c]
    loc = @jiki.loc
    dup.step.move_jiki(Loc.new(loc.x + m.x, loc.y + m.y), c).check_dot
  end

  protected

  def step
    @enemies = @enemies.map {|e| e.move_next(@jiki) }
    @life -= 1
    self
  end

  def move_jiki(loc, c)
    @jiki = @jiki.move_to_loc(loc)
    @hist = @hist.dup << c
    self
  end

  def check_dot
    p = @jiki.loc
    if @dots[p]
      @dots = @dots.dup
      @dots.delete(p)
      @points += 1
    end
    self
  end

  def set_next_link(link)
    @next_link = link
    self
  end

  private

  CHAR2ENEMY = {
    'V' => EnemyV, 'H' => EnemyH, 'L'=> EnemyL, 'R' => EnemyR, 'J' => EnemyJ,
  }

  def char2item(c, x, y)
    case c
    when '.'
      @dots[Loc.new(x, y)] = true
    when '@'
      @jiki = Jiki.new(Loc.new(x, y))
    when 'V', 'H', 'L', 'R', 'J'
      @enemies << CHAR2ENEMY[c].new(Loc.new(x, y))
    end
    c != '#'
  end
end

if __FILE__ == $0
  require 'optparse'

  opt = OptionParser.new
  $auto_play_str = nil
  $debug_mode = false
  $report_timeover = false
  opt.on('-d', 'debug mode') {|v| $debug_mode = v }
  opt.on('-t', 'report timeover') {|v| $report_timeover = v }
  opt.on('-p STR', 'auto play mode') {|s| $auto_play_str = s }
  opt.parse!(ARGV)
  filename = ARGV[0]

  def puts_message(st, msg = nil)
    puts "#{st.points}: #{msg ? msg + ': ' : ''}#{st.hist.join}"
  end

  st =  State.new.parse_file(filename)

  if $auto_play_str
    puts st
    $auto_play_str.split(//).each do |c|
      st = st.play(c)
      if st.eaten?
        puts 'eaten!'
        break
      end
      puts "> #{c}"
      puts st
    end
  else
    while st
      puts_message(st) if $debug_mode
      if st.dot_complete?
        puts_message(st, 'got all dots!')
        break if st.eaten?
        st = st.next_link
      elsif st.life == 1          # time over
        puts_message(st, 'timeover!') if $report_timeover
        st = st.next_link
      elsif st.visited
        st = st.next_link
      else
        if link = st.next_states
          st = link
        else
          st = st.next_link
        end
      end
    end
  end

end