与えられた迷路の最短経路を求める(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)
の部分に特に気をつけてコードを読んでみて下さい。ちなみに、この shift
を pop
に替えるだけで深さ優先探索になりますよ。これでも解は求められますが、一般に最短経路になりません。一行替えるだけでのちがい、やってみるとおもしろいと思います。
なお、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 * * * *********** * * * * ******* * * * * * **************************