某社のプログラミング問題の解答例にコメントを付けてみた

id:eel3:20100502:1272780085 のコードにコメントを付けただけ。あと変数名を少しだけ変えてある*1。

#!/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
#

#=== 迷路 _maze_ の中から、値が _val_ である座標を返す（最初に発見したもののみ）
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, :hop => nil}

#=== 迷路 _maze_ を文字列にダンプする
def dump_out_maze(maze)
  maze.map {|line|
    line.map {|ch| sprintf("%c", ch) }.join
  }.join("\n")
end

#=== 最短経路を探す（しらみつぶし）
def track(maze, goal, pt, hop)
  # 迷路の外に出てしまったらNG
  return if (pt[:y] < 0 || pt[:y] >= maze.size)
  return if (pt[:x] < 0 || pt[:x] >= maze[pt[:y]].size)

  # 最短ホップ数に到達していたら、処理を打ち切る
  unless $track_log[:hop] == nil
    if hop >= $track_log[:hop]
      return
    end
  end

  # ゴールにたどり着いた場合は、ログを残しておく
  if pt[:x] == goal[:x] && pt[:y] == goal[:y]
    $track_log[:hop] = hop
    $track_log[:dump] = dump_out_maze(maze)
    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]  }, hop+1)
  track(maze, goal, {:x => pt[:x],   :y => pt[:y]+1}, hop+1)
  track(maze, goal, {:x => pt[:x]+1, :y => pt[:y]  }, hop+1)
  track(maze, goal, {:x => pt[:x],   :y => pt[:y]-1}, hop+1)
  maze[pt[:y]][pt[:x]] = ?\s
end

#=== メインルーチン
def main
  maze = load_maze
  puts dump_out_maze(maze[:maze])
  print 'start: '; p maze[:start]
  print 'goal : '; 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]
  print 'hop count: ', $track_log[:hop], "\n"
end

main

しかし、コメントが無いと分かりにくい部分があるってことは*2、まだまだ未熟者だということか。精進しないと。

*1:countをhopに変更。

*2:特にメソッドtrack。