Ruby練習初日

きっかけ

Rubyを覚えようと思い、簡単なプログラムを作ってみた。以前受けた試験の問題に、単純なんだけど基本的(っぽい)アルゴリズムの問題があったのでそれをネタにしてみた。こういうアルゴリズムは自分で一から考えて作れといわれても、すぐには作れないんじゃないんじゃないかな。

#! /usr/bin/ruby
#
# 平成20年度秋期 基本情報技術者 午後 問題
#
# http://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2008h20_2/2008h20a_fe_pm_qs.pdf
#
# 問4で説明されているアルゴリズムの実装
#
class ShortestLengh
    # 仮想無限大
    INF = 0x7ffffff 

    #
    #_input_ :: グラフの情報。先頭の行に地点の数。
    #           以降の行に接続されている地点と地点の番号とその間の距離がカンマ区切りになっている。
    def initialize (input)
        items = input.split("\n")
        @n    = items.shift.to_i
        @dt   = Array.new(@n) {
                    Array.new(@n) { INF }
                }
        items.each { |item|
            i, j, len = item.split(',').map { |x| x.to_i}
            @dt[i - 1][j - 1] = len
        }
        @sd = Array.new(@n) { INF }
        @pe = Array.new(@n) { false }
    end

    # 全ての地点で最短距離の算出が終わっているか？
    def is_all_visited?
        !@pe.include?(false)
    end

    # 次に処理する地点を求める
    def get_next_node
        min  = INF 
        node = 0
        @n.times { |i|
            if @pe[i] == false
                if @sd[i] < min
                    min  = @sd[i]
                    node = i
                end  
            end
        }
        return node
    end

    # 最小値を返す
    def min(sd1, sd2)
        sd1 > sd2 ? sd2 : sd1
    end

    # 最短経路を求める
    def get_length
        until is_all_visited?
            node      = get_next_node
            @pe[node] = true
            @dt[node].each_with_index { |len, i|
                unless len == INF
                    sdv = @sd[node] == INF ? 0 : @sd[node]
                    @sd[i] = min(@sd[i], sdv + len)
                end
            }
        end
        return @sd.last
    end
end

p ShortestLengh.new(DATA.read).get_length
__END__
6
1,2,10
1,4,20
1,5,30
2,3,40
2,5,10
3,6,30
4,5,20
5,3,10
5,6,30

感想

• 二次元配列の初期化でハマった。一つの要素の値を変更したと思っていたら、変更されたのは一つだけじゃなかった。...参照先が同じだから一つといえば一つなんだけど。

#! /usr/bin/ruby
ary1 = [1, 2]
ary2 = [ary1, ary1]
ary2[0][0] = 100
# => ary2[0][0]だけが100になるのを期待したけど
#    ary2[0]とary2[1]は同じオブジェクトを参照しいるので
#    ary2[1][0]も100になってしまう

• 比較するときに文字列と数値の比較をすると ArgumentError が発生。意外に型にうるさい。PHPばかり触っていて文字列から数値への暗黙の変換に慣れてしまっていたので新鮮。というか、PHPの方が異端なのか？

#! /usr/bin/ruby
str = "1"
num = 10
p str > num ? str: num # => このままではエラー。str.to_i とすればOK

• 条件分岐で、偽の場合に実行したい処理がある場合は unless を使った方がいい？ せっかく用意されているんだし。