Project Euler 83

http://projecteuler.net/index.php?section=problems&id=83

ダイクストラ法というアルゴリズムがあるのを知ったので、その方法で解きました。
ただ、実装の具体例などは全く見ていないためかなり独自実装です。

適当に毎回全ノードを探索して、最短ルートを探すようにしたため、計算量は、約 80^4 / 2 = 20480000 くらいです。
その方法が間違えているのかどうか知りませんが、Ruby では結構時間がかかってしまいました。

72秒でした。

いかがなものかと思い、C++ でも実装してみたところ、5.08秒でした。
うかつにも C++ にときめきました。

Project Euler を始めて薄々感づいているのですが、Ruby って単純にループするだけでも結構コストがあるような気がしています。

前のエントリーでも計測しましたが、この前は each と inject だったので、今回は times を使って計測しなおしました。

irb> start = Time.now; 10000000.times{};puts Time.now - start
1.828148

うーん、やっぱりたった1000万のループで何もしないのに2秒近くかかるんですよね。

とはいっても Ruby の簡便さは大好きなので困らないかぎり Ruby で続けるつもりです。

以下、ちょー適当コードですが気が向いたので晒しておきます。
ちなみにC++も全くと言っていいほど同じ構造です。

def problem83
  matrix_file = "problem82.txt"
  imax = 80
  jmax = 80
  #matrix_file = "problem82_test.txt"
  #imax = 5
  #jmax = 5
  
  matrix = []
  File.foreach(matrix_file) do |line|
    matrix << line.chomp.split(",").map {|t| t.to_i}
  end
  
  tansaku = []
  0.step(imax-1) do |i|
    tansaku << [nil]*jmax
  end
  tansaku[0][0] = matrix[0][0]
  
  calccount = 0
  loop do
    saitan = []
    0.step(imax-1) do |i|
      0.step(jmax-1) do |j|
        if tansaku[i][j].nil?
          lst = []
          if i-1 >= 0 && tansaku[i-1][j] != nil
            lst << tansaku[i-1][j]
          end
          if j-1 >= 0 && tansaku[i][j-1] != nil
            lst << tansaku[i][j-1]
          end
          if i+1 < imax && tansaku[i+1][j] != nil
            lst << tansaku[i+1][j]
          end
          if j+1 < jmax && tansaku[i][j+1] != nil
            lst << tansaku[i][j+1]
          end
          if lst.size > 0
            saitan << [lst.min + matrix[i][j], i, j]
          end
          calccount += 1
        end
      end
    end
    
    min = saitan.min_by {|t| t[0]}
    tansaku[min[1]][min[2]] = min[0]
    
    puts "#{calccount} #{min[0]}" if calccount % 1000 == 0
    
    break unless tansaku[imax-1][jmax-1].nil?
  end

  tansaku[imax-1][jmax-1]
end