Solver of Grid Search Problems

grid-explorer.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

# grid-explorer.rb : Solver of Grid Search Problems
#   by takehikom (http://d.hatena.ne.jp/takehikom/)

if RUBY_VERSION < "1.9"
  $KCODE = "u"
end

require "optparse"

module GridExplorer
  class Field
    def initialize(h)
      @opt = h
      set_field
      set_goal_len
      set_charset
    end

    def display(seq = nil)
      if seq
        puts "No.#{seq}"
      end
      @height.times do |y|
        @width.times do |x|
          print @charset[look(x, y)]
        end
        puts
      end
      puts
    end
    alias :to_s :display

    def explore
      search(1)
      search(2)
      search(3)
      search(4)
    end
    alias :start :explore

    private

    def set_field
      @width  = @opt[:width]
      @height = @opt[:height]
      @field = Hash.new(0)
      @x = @y = 0
      @len = 0
      @solution_count = 0
    end

    def set_goal_len
      if @opt[:prob] == 1
        @goal_len = @width + @height - 2
      else
        @goal_len = @width * @height - 1
      end
    end

    def set_charset
      @@charset_a ||= {
        0 => " RLDU*".split(//u),
        1 => " ><v^*".split(//u),
        2 => "　右左下上＊".split(//u),
        3 => "　→←↓↑＊".split(//u)
      }
      @charset = @@charset_a[@opt[:char] || 0]
    end

    def field_key(x, y)
      "#{x},#{y}"
    end

    def look(x, y)
      @field[field_key(x, y)]
    end

    def place(x, y, val)
      @field[field_key(x, y)] = val
    end

    def displace(x, y)
      @field.delete(field_key(x, y))
    end

    def push(x_new, y_new, val)
      @len += 1
      place(@x, @y, val)
      @x = x_new
      @y = y_new
    end

    def pop(x_old, y_old)
      @x = x_old
      @y = y_old
      displace(@x, @y)
      @len -= 1
    end

    def search(dir)
      x_new = @x + (dir == 1 ? 1 : 0) - (dir == 2 ? 1 : 0)
      y_new = @y + (dir == 3 ? 1 : 0) - (dir == 4 ? 1 : 0)
      x_old = @x
      y_old = @y

      return if x_new < 0 || x_new >= @width ||
        y_new < 0 || y_new >= @height ||
        look(x_new, y_new) != 0 ||
        @len >= @goal_len

      push(x_new, y_new, dir)

      if @x == @width - 1 && @y == @height - 1 &&
          (@opt[:prob] == 2 || @len == @goal_len)
        place(@x, @y, 5)
        @solution_count += 1
        display(@solution_count)
        displace(@x, @y)
      else
        search(1)
        search(2)
        search(3)
        search(4)
      end

      pop(x_old, y_old)
    end
  end

  class Solver
    def initialize(h = {})
      @opt = h
      @width    = h[:width]  ||= 7
      @height   = h[:height] ||= 5
      @opt_prob = h[:prob]   ||= 0
      @opt_char = h[:char]   ||= 0

      @gef = GridExplorer::Field.new(@opt)
    end

    def start
      @gef.explore
    end
  end
end

if __FILE__ == $0
  opt = OptionParser.new
  h = {}
  opt.on("-b", "--problem=VAL", "problem type") {|v|
    h[:prob] = v.to_i
  }
  opt.on("--allonce", "find traversable paths (-b0, default)") {
    h[:prob] = 0
  }
  opt.on("--shortest", "find the shortest paths (-b1)") {
    h[:prob] = 1
  }
  opt.on("--allroute", "find any paths (-b2)") {
    h[:prob] = 2
  }
  opt.on("-c", "--print=VAL", "character set") {|v|
    h[:char] = v.to_i
  }
  opt.on("--print-eng", "print by capital letters (-c0, default)") {
    h[:char] = 0
  }
  opt.on("--print-sym", "print by symbols (-c1)") {
    h[:char] = 1
  }
  opt.on("--print-jpn", "print by kanji character (-c2)") {
    h[:char] = 2
  }
  opt.on("--print-dir", "print by arrow letters (-c3)") {
    h[:char] = 3
  }
  opt.on("-x", "--width=VAL", "width of field") {|v|
    h[:width] = v.to_i
  }
  opt.on("-y", "--height=VAL", "height of field") {|v|
    h[:height] = v.to_i
  }
  opt.on("-s", "--side=VAL", "width and height of field") {|v|
    h[:width] = h[:height] = v.to_i
  }
  opt.parse!(ARGV)
  if !h.key?(:width) && ARGV.first.to_i > 0
    h[:width] = ARGV.shift.to_i
    if !h.key?(:height) && ARGV.first.to_i > 0
      h[:height] = ARGV.shift.to_i
#    else
#      h[:height] = h[:width]
    end
  end

  GridExplorer::Solver.new(h).start
end