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

まずは元ネタ:

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

これを解いてみました．

久し振りにRubyを書いたので，かなり微妙．
さらにいくつかまずいと思う部分があるけど，無視してガーっと書いたので，突っ込み大歓迎です:

def parse_input(io)
  io.read.split("\n").map {|row| row.split(//)}
end

def size_of_maze(maze)
  [maze.size, maze[0].size]
end

def find_position(maze, char)
  row_p = maze.find_index {|row|
    row.include?(char)
  }
  col_p = maze[row_p].find_index {|elm|
    elm == char
  }
  [row_p, col_p]
end

def init_cstr_mat(size_of_maze, pos_goal, maze)
  cost_mat = Array.new(size_of_maze[0]) {|i|
    Array.new(size_of_maze[1]) {|j|
      size_of_maze[0]*size_of_maze[1]
    }
  }
  cost_mat[pos_goal[0]][pos_goal[1]] = 0
  maze.each_with_index {|row, i|
    row.each_with_index {|elm, j|
      if elm == "*"
        cost_mat[i][j] = nil
      end
    }
  }
  cost_mat
end

def do_arounds(i, j, &p)
  [[i, j - 1],
   [i + 1, j],
   [i, j + 1],
   [i - 1, j],
  ].each {|pos|
    yield pos
  }
end

def update(i, j, current_turn, cost_mat, maze)
  do_arounds(i, j) {|ni, nj|
    if cost_mat[ni]
      if cost_mat[ni][nj]
        if cost_mat[ni][nj] > current_turn + 1
          cost_mat[ni][nj] = current_turn + 1
        end
      end
    end
  }
end

def search(maze, cost_mat, pos_goal)
  current_turn = 0
  loop {
    maze.each_with_index {|row, i|
      row.each_with_index {|elm, j|
        if cost_mat[i][j] == current_turn
          update(i, j, current_turn, cost_mat, maze)
        end
      }
    }
    break if current_turn > 1000
    current_turn += 1
  }
end

def path_extract(maze, cost_mat, pos_start)
  cur_pos = pos_start
  cur_cost = cost_mat[cur_pos[0]][cur_pos[1]]
  loop {
    do_arounds(cur_pos[0], cur_pos[1]) {|ni, nj|
    if cost_mat[ni]
      if cost_mat[ni][nj]
        if cost_mat[ni][nj] < cur_cost
          return if maze[ni][nj] == "G"
          maze[ni][nj] = "$"
          cur_pos = [ni, nj]
          cur_cost = cost_mat[ni][nj]
        end
      end
    end      
    }
  }
end

def main
  maze = parse_input($stdin)
  maze_size = size_of_maze(maze)
  pos_goal = find_position(maze, "G")
  cost_mat = init_cstr_mat(maze_size, pos_goal, maze)
  search(maze, cost_mat, pos_goal)
  pos_start = find_position(maze, "S")
  path_extract(maze, cost_mat, pos_start)
  puts maze.map{|row| row.join }.join("\n")
end

main

長いことRubyを書くことが無かったので，かなり変な(Ruby好きからすると「らしくない」？)感じになっていると思います．
それにアルゴリズムとして見ても，かなりオーダーがひどいでしょう．

しかし，問題を解くコードを速く書くのならば，こんな感じで十分でしょう．

しかし…見れば見る程，改善の余地があるな…これ…