元ネタはこれ。
3ヶ月以上前の話題なので今更すぎるのだけど、2〜3日前に知ったばかりなのでしょうがない*1。
迷路の最短経路を求める問題。迷路のデータはテキストファイルに書かれていて、実行時に読み込む。迷路データのバリデーションは不要。OSや言語は問わず、3時間以内に実装できれば足きりをクリアしたことになるらしい。
どうやら問題はメールで送られきて、解答のソースをメールで送付したらしい。おそらく応募者は自分のやり易い開発環境で挑戦できたと思われる。
ということで、試しにRubyで挑戦してみた。CプログラマなのにRubyで書いたのは、C言語といっても実質的にANSI C89の範囲でしか書いたことがないので*2、時間内に完成させる自信が無かったからだ。
#!/usr/bin/ruby -w # #= Poderosaを開発している某社の入社試験。迷路の最短経路を求める。 # #author:: eel3 @ TRASH BOX #date:: 2010/05/02 # #== 関連情報 # - http://okajima.air-nifty.com/b/2010/01/post-abc6.html # #== 動作確認環境 # - ruby 1.8.7 (2009-06-12 patchlevel 174) [i386-mswin32] @ Windows XP Pro SP3 # def find_point(maze, val) x = nil y = maze.index do |line| x = line.index(val) x != nil end {:x => x, :y => y} end def load_maze maze = readlines.map {|line| line.chomp.unpack('C*') } start = find_point(maze, ?S) goal = find_point(maze, ?G) {:maze => maze, :start => start, :goal => goal} end $track_log = {:dump => nil, :count => nil} def dump_out_maze(maze) maze.map {|line| line.map {|ch| sprintf("%c", ch) }.join }.join("\n") end def track(maze, goal, pt, count) return if (pt[:y] < 0 || pt[:y] >= maze.size) return if (pt[:x] < 0 || pt[:x] >= maze[pt[:y]].size) unless $track_log[:count] == nil if count >= $track_log[:count] return end end if pt[:x] == goal[:x] && pt[:y] == goal[:y] $track_log[:count] = count $track_log[:dump] = dump_out_maze(maze) # debug print #puts $track_log[:dump] #puts $track_log[:count] #puts '' return end return unless maze[pt[:y]][pt[:x]] == ?\s maze[pt[:y]][pt[:x]] = ?$ track(maze, goal, {:x => pt[:x]-1, :y => pt[:y] }, count+1) track(maze, goal, {:x => pt[:x], :y => pt[:y]+1}, count+1) track(maze, goal, {:x => pt[:x]+1, :y => pt[:y] }, count+1) track(maze, goal, {:x => pt[:x], :y => pt[:y]-1}, count+1) maze[pt[:y]][pt[:x]] = ?\s end def main maze = load_maze puts dump_out_maze(maze[:maze]) p maze[:start] p maze[:goal] puts '' track(maze[:maze], maze[:goal], {:x => maze[:start][:x]-1, :y => maze[:start][:y] }, 1) track(maze[:maze], maze[:goal], {:x => maze[:start][:x], :y => maze[:start][:y]+1}, 1) track(maze[:maze], maze[:goal], {:x => maze[:start][:x]+1, :y => maze[:start][:y] }, 1) track(maze[:maze], maze[:goal], {:x => maze[:start][:x], :y => maze[:start][:y]-1}, 1) puts $track_log[:dump] puts $track_log[:count] end main
3時間弱で完成。力任せにしらみつぶしに経路を求める方法なので、効率は悪い。それでも、ゴールまでの暫定の最短距離を保持しておき、その距離を越えそうになったら処理を打ち切るようにしているので多少はマシかもしれない。
「しらみつぶしに経路を求める」という方法は問題を見た瞬間に思いついたのだが、結構時間がかかった。その要因の半分は不慣れなRubyを使用したことで発生していて、例えばハッシュリテラルを「{:x => x}」と書くところを「{x: x}」と書いて動かなくて悩むとか、そんなおバカなことで時間を食っていた*3。
それでもC言語（ANSI C89オンリー）では時間内に満足のいくものを実装できる自信がなかったので*4、Rubyを使ったことに対する後悔はない。
ちなみに時間がかかった要因の残り半分は、迷路のデータを管理する2次元配列（のようなもの）にアクセスする部分のほぼ全てでx軸とy軸を取り違えて添字を書いてしまい、且つその凡ミスに気づかず延々と悩んでいたことだ。は、恥ずかしすぎる……。
