迷路を解くRubyスクリプト

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
を解いてみた。一番得意な言語ってわけでは無いが、最近仕事で使っているので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