迷路を解くRubyスクリプト
人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか
を解いてみた。一番得意な言語ってわけでは無いが、最近仕事で使っているのでRubyを使用。
正答を出せるまでが40分、ブラッシュアップに10分ってところか。
この方法は有名どころで、ユニット型シミュレーションゲームの移動範囲表示にも使われてたような。
class Maze def initialize(inputs) @width = inputs[0].length - 1 @height = inputs.length @maze = [] inputs.each do |input| linemaze = [] input.split("").each do |c| next if c == "\n" @start = {:x => linemaze.length, :y => @maze.length } if c == "S" @goal = {:x => linemaze.length, :y => @maze.length } if c == "G" c == " " ? linemaze.push(@width * @height) : linemaze.push(c) end @maze.push(linemaze) end end def solve history = [] move(@start[:x], @start[:y], history) @answerHistory.each do |foot| next if ["S", "G"].include?(@maze[foot[:y]][foot[:x]]) @maze[foot[:y]][foot[:x]] = "$" end end def move(x, y, history) history.push({:x => x, :y => y}) return if @maze[y][x] == "*" return if @maze[y][x] == "S" && history.length > 1 if @maze[y][x] == "G" then if @answerHistory == nil || history.length < @answerHistory.length then @answerHistory = history.clone end return end if @maze[y][x].kind_of?(Numeric) then return if @maze[y][x] <= history.length @maze[y][x] = history.length end move(x - 1, y, history) history.pop move(x + 1, y, history) history.pop move(x, y - 1, history) history.pop move(x, y + 1, history) history.pop end def to_s str = "" str << @maze.map do |line| line.map do |c| c.kind_of?(Numeric) ? " " : c end.join("") end.join("\n") str << "\n" str << "start = #{@start[:x]}, #{@start[:y]}\n" str << "goal = #{@goal[:x]}, #{@goal[:y]}\n" end end if ARGV.length == 0 then puts "Usage: solvemaze.rb filename" exit end inputs = File.open(ARGV[0]).readlines maze = Maze.new(inputs) puts maze puts "--------------------------------" puts " Now solving......" puts "--------------------------------" maze.solve puts maze
実行結果
e:\Ruby\SolveMaze>ruby solvemaze.rb "input.txt" ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** start = 1, 1 goal = 22, 8 -------------------------------- Now solving...... -------------------------------- ************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * ************************** start = 1, 1 goal = 22, 8
e:\Ruby\SolveMaze>ruby solvemaze.rb "input2.txt" ************************** *S* * * * * * * * ***** *** ** * * * * **** *** *** * * * * * ***** * ************* **** **** *** **** **** ** ********* **** *** **** * * *G * * ** *********** * * * * ***** ******* * **** * * ************************** start = 1, 1 goal = 22, 8 -------------------------------- Now solving...... -------------------------------- ************************** *S* * $$$$ *$$$$$ * *$* *$$* $*****$***$** * *$* $$* $$****$***$*** * *$$$$* $$$$$$ *$$$ * ***** * *************$**** **** *** ****$$$$$**** ** ********* ****$*** **** * *$$$$$$$$$$ *G$ * * ** $$ *********** *$ * * * $***** ******* $$ * **** $$$$$$$$$$$$$$$$* * ************************** start = 1, 1 goal = 22, 8
e:\Ruby\SolveMaze>ruby solvemaze.rb "input3.txt" ************************** * * * S * * * * * * * * * * * * * * * * G * * * ************************** start = 3, 2 goal = 21, 10 -------------------------------- Now solving...... -------------------------------- ************************** * * * S$$$$$$$$$$$$$$$$$$ * * $ * * $ * * $ * * $ * * $ * * $ * * $ * * G * * * ************************** start = 3, 2 goal = 21, 10