与えられた迷路の最短経路を求める(Ruby)

人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。

さて試験問題です。
内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。

 
おもしろそうなので Ruby で解いてみました。もともとはここで知ったものです。
僕はまだまだ不勉強で A* も dijkstra も知りませんが(そのうちお勉強する予定)、ふつうに幅優先探索ですよね。

というわけでやってみました。先に出力を載せておきます。

$ time ruby solve_maze.rb
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

real	0m0.164s
user	0m0.072s
sys	0m0.012s

こんな感じで解けました。


コードは以下。上に書いたとおり、単純な幅優先探索です。もちろん幅優先探索は最短経路を与えます。
solve_maze.rb

class SolveMaze
  class Step
    def initialize(x, y)
      @x, @y = x, y
      @parent = nil
    end
    attr_accessor :x, :y, :parent
    
    [:up, :down, :left, :right].each_with_index do |mt, i|
      define_method(mt) do
        a = [Step.new(x, y - 1), Step.new(x, y + 1),
             Step.new(x - 1, y), Step.new(x + 1, y)][i]
        a.parent = self
        a
      end
    end
  end
  
  def initialize
    @map = DATA.readlines
  end
  
  def get(st)
    @map[st.y][st.x]
  end
  
  def set(st, ch)
    @map[st.y][st.x] = ch
  end
  
  def go
    stack = [Step.new(1, 1)]
    
    while (a = stack.shift)
      [a.up, a.down, a.left, a.right].each do |nxt|
        case get(nxt)
        when "G" then finish(a)
        when " "
          set(nxt, "@")
          stack.push(nxt)
        end
      end
    end
  end
  
  def finish(a)
    @map.map! {|x| x.gsub(/@/, " ")}
    while a.parent
      set(a, "$")
      a = a.parent
    end
    @map.each {|x| puts x}
    exit
  end
end

SolveMaze.new.go

__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

メインループは SolveMaze#go の while 文です。SolveMaze#finish は回答を出力して終了します。それぞれのステップをクラス(Step クラス)にするまでもなかったかも知れませんが、まあいいんじゃないでしょうか。

DRY原則を満たすためにちょっとだけメタプログラミングを使っている以外は、素直なコードではないかと思います。

僕などがいうまでもないのですが、幅優先探索が気になる方は、while (a = stack.shift)stack.push(nxt) の部分に特に気をつけてコードを読んでみて下さい。ちなみに、この shiftpop に替えるだけで深さ優先探索になりますよ。これでも解は求められますが、一般に最短経路になりません。一行替えるだけでのちがい、やってみるとおもしろいと思います。


なお、Ruby コミッターの「まめめも」さんのコードはすごいです。え、こんなに短いの、という感じ。自分などはまだまだですね。

 

別解

別様に解いてみました(2018/12/12)。上の半分ほどの行数になっています。

solve_maze1.rb

Position = Struct.new(:x, :y, :parent)

field = DATA.readlines
start = Position.new
field.each_with_index {|l, i| start.x, start.y = (l.index("S") or next), i}
stack = [start]

# solve
finish = loop do
  po = stack.shift
  break po if field[po.y][po.x] == "G"
  [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
    nx, ny = po.x + dx, po.y + dy
    a = field[ny][nx]
    field[ny][nx] = "@" if a == " "
    stack << Position.new(nx, ny, po) if a == " " or a == "G"
  end
end

# 結果の表示
field.map! {|l| l.gsub("@", " ")}
prev = finish.parent
until prev == start
  field[prev.y][prev.x] = "$"
  prev = prev.parent
end
puts field

__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************