Poderosaで有名な某社の入社試験で出たプログラミング問題を今更解いてみた

元ネタはこれ。

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オンリー)では時間内に満足のいくものを実装できる自信がなかったので*4Rubyを使ったことに対する後悔はない。

ちなみに時間がかかった要因の残り半分は、迷路のデータを管理する2次元配列(のようなもの)にアクセスする部分のほぼ全てでx軸とy軸を取り違えて添字を書いてしまい、且つその凡ミスに気づかず延々と悩んでいたことだ。は、恥ずかしすぎる……。

*1:そう思いたい……が、アンテナの感度が低いことは否めない。

*2:就業先内のライブラリやミドルウェアなら使うけど……。

*3:というか、その書き方はJavaScriptのObjectのリテラル表現だ……。

*4:適当なサイズの固定配列を使い、迷路のデータがその配列に収まる大きさであると決めうちしてもよいのなら、時間内に書けると思う。だけど実際には動的メモリを使うべきで、その辺りのコードを書くのが面倒。