ダイクストラ法

なんか、すごいプログラマの人が出したという迷路を解く問題http://okajima.air-nifty.com/b/2010/01/post-abc6.htmlをいまさらRubyで行った。
ダイクストラ法の勉強で2時間
それをコードに落とすのに2時間
「Oh! No! 動かなーい」で3時間
結果を表示するのに1時間

制限時間の3時間を大幅に越えている。
参考にさせてもらったURL http://www.sousakuba.com/Programming/algo_root.html

穢いプログラムも一応のせておこう。Rubyって難しい・・・・
JavaScriptのつもりでテキトーに変数使ってエラい目にあった。
うんこくさいグローバル変数の前には$をつけろですよ
しかし、へたくそなrubyプログラムと言うのは縦に伸びるなあ。

#!/usr/bin/ruby

$start  = nil
$goal = nil


class Dikstr_node
    def initialize(x, y, cost, prev)
      @px = x;
      @py = y;
      @prev_node = prev;
      @cost_before = cost + (prev ? prev.cost_before : 0)
    end
    attr_accessor :px, :py, :prev_node, :cost_before
end


def parse_maze( f )
    ret = [];
    x = y = 0
    f.each do |line|
        line.strip!
        l = Array.new
        x = 0
        line.each_byte do |b|
            if (b == 42)  # * 
              l.push :wall;
            elsif (b == 32)  # :space
              l.push nil;
            elsif (b == 83)
print "start1 =#{$start}\n"
              $start = Dikstr_node.new(x, y, 0, nil)
print "start2 =#{$start}\n"
              l.push $start
            else  (b == ?G)
              $goal = Dikstr_node.new(x, y, 100000000, nil)
              l.push $goal
            end
            x += 1
        end
        y += 1;
        ret.push l
    end
    ret
end

def next_node(m, direct, cur)
    x = cur.px
    y = cur.py
    case direct
    when :up
       y -= 1;
    when :down
       y += 1;
    when :right
       x += 1;
    when :left
       x -= 1;
    end
    # p "m[#{y}][#{x}] = #{m[y][x]}"
    if (m[y][x] == nil )
        m[y][x] = Dikstr_node.new(x, y, 1, cur) ;
    elsif (m[y][x] != :wall)
        if (m[y][x].cost_before > cur.cost_before + 1) 
           m[y][x].prev_node = cur;
           m[y][x].cost_before = cur.cost_before + 1;
        else 
           return :already
        end
    end
    abort("nil???") if m[y][x] == nil
    m[y][x]
end

def next_nodes_list(m, cur)
  l = [];
  directs = [:up, :down, :right, :left];
  directs.each do |d|
      l.push next_node(m, d, cur);
  end
  l
end


def insert_min(a, node)
   i = 0
   while(i < a.length)  
     p "a[#{i}] is null length = #{a.length}" if a[i] == nil
     break if a[i].cost_before > node.cost_before
     i += 1
   end
   a.insert(i, node);
end

def disp_result( m )
  l = []
  m.each do |line|
    str = ""
    i = 0
    line.each do |x|
      if (x == :wall)
        str[i] = ?*
      else
        str[i] = 32.chr
      end
      i += 1
    end
    l.push str
  end
  l[$goal.py][$goal.px] = ?G
  l[$start.py][$start.px] = ?S
  cur = $goal.prev_node
  while (cur != $start)
    # print "(#{cur.px} #{cur.py})"
    l[cur.py][cur.px] = ?$ 
    #break if (cur == $start)
    #print "->"
    cur = cur.prev_node
  end
  #print "\n"
  l.each {|line| puts line}
end

def resolve_maze( m )
    # cur = $start 
    x_max = m[0].length - 1;
    y_max = m.length - 1;
    print "m.length = #{m.length} \n"
    print "m[0].length = #{m[0].length} \n"

    q = []
    q.push $start

#p m
    # q から一件取り出す
    count = 0
    while(true)
      count += 1
      cur = q.shift
    # 取り出したデータからnext_nodes_listを実行
      if (count > 200) 
        #p m
        exit
      end
    # nodeが Dikstr_nodeで、$goalじゃなかったら 入れる。
    # $goalだったら終了。
      # p cur
        abort ("cur is nil") if (cur == nil)
      l = next_nodes_list(m, cur);
      l.each do |n|
         # p "#{n} :  #{n.class}"
         if (n == $goal)
           p "ok"
           disp_result m
           exit
         end
         abort ("n is nil") if (n == nil)
         if (n != :wall && n != :already && n != $goal)
             # p "#{n.px} : #{n.py} : #{n.cost_before}"
             insert_min(q, n)
         end
      end
    end
end

m = nil
if ARGV[0] then
  File.open(ARGV[0]) do |f|
      m =  parse_maze f
  end
else
   m =  parse_maze $stdin
end
#p m
print "start =#{$start} #{$start.px} #{$start.py}\n"
print "goal = #{$goal} #{$goal.px} #{$goal.py} \n" 
resolve_maze m

実行結果

**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$   *$$$$$$$$G       *
*  *$$$$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************