Ruby

Railsアプリの引っ越し

Flask アプリの引っ越しが完了したので、apostrophe (Ubuntu 14.04 LTS) で動いているもうひとつの WEB アプリ（Rails 製）を wplj (Ubuntu 16.04 LTS) に引っ越す。

下準備

このアプリはファイルを貯めこむタイプなので、事前に tar コマンドと scp コマンドを使って /media/aysheaia/wallpapers 以下にファイルを配置しておいた。

専用ユーザの作成

takatoh@wplj $ sudo adduser tonzlr
[sudo] takatoh のパスワード: 
ユーザー `tonzlr' を追加しています...
新しいグループ `tonzlr' (1002) を追加しています...
新しいユーザー `tonzlr' (1002) をグループ `tonzlr' に追加しています...
ホームディレクトリ `/home/tonzlr' を作成しています...
`/etc/skel' からファイルをコピーしています...
新しい UNIX パスワードを入力してください: 
新しい UNIX パスワードを再入力してください: 
passwd: パスワードは正しく更新されました
tonzlr のユーザ情報を変更中
新しい値を入力してください。標準設定値を使うならリターンを押してください
	フルネーム []: 
	部屋番号 []: 
	職場電話番号 []: 
	自宅電話番号 []: 
	その他 []: 
以上で正しいですか? [Y/n] Y
takatoh@wplj $ sudo gpasswd -a tonzlr sudo
ユーザ tonzlr をグループ sudo に追加

Railsアプリの配置

ここからは上で作ったユーザで作業。
GitHub からクローンする。

tonzlr@wplj:~$ git clone https://github.com/takatoh/Tonzlr.git tonzlr

ディレクトリを移動して、依存パッケージをインストール。

tonzlr@wplj:~$ cd tonzlr
tonzlr@wplj:~/tonzlr$ bundle install
プログラム 'bundle' はまだインストールされていません。 'bundle' を利用するために、コンピュータの管理者に 'ruby-bundler' をインストールすることを相談してください

bundler がインストールされてなかった。インストール。

tonzlr@wplj:~/tonzlr$ sudo gem install bundler
[sudo] tonzlr のパスワード: 
tonzlr は sudoers ファイル内にありません。この事象は記録・報告されます。

あれ？なんでだ？
仕方がないので、takatoh ユーザに戻ってインストール。

takatoh@wplj $ sudo gem install bundler

もう一度 tonzlr ユーザで。

tonzlr@wplj:~/tonzlr$ bundle install --path vendor/bundle
Fetching gem metadata from https://rubygems.org/..........
Fetching version metadata from https://rubygems.org/..
Fetching dependency metadata from https://rubygems.org/.
Installing rake 10.4.2
Installing i18n 0.7.0
Installing json 1.8.1 with native extensions
Installing minitest 5.5.0
Installing thread_safe 0.3.4
Installing builder 3.2.2
Installing erubis 2.7.0
Installing rack 1.5.2
Installing mime-types 1.25.1
Installing polyglot 0.3.5
Installing arel 5.0.1.20140414130214
Installing coffee-script-source 1.8.0
Installing execjs 2.2.2
Installing thor 0.19.1
Installing hike 1.2.3
Installing multi_json 1.10.1
Installing libv8 3.16.14.3 (x86_64-linux)
Using bundler 1.14.6
Installing tilt 1.4.1
Installing ref 1.0.5
Installing sass 3.2.19
Installing spring 1.2.0
Installing sqlite3 1.3.10 with native extensions
Installing will_paginate 3.0.7
Gem::Ext::BuildError: ERROR: Failed to build gem native extension.

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
/usr/bin/ruby2.3 -r ./siteconf20170304-4815-1cena5t.rb extconf.rb
mkmf.rb can't find header files for ruby at /usr/lib/ruby/include/ruby.h

extconf failed, exit code 1

Gem files will remain installed in
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1 for inspection.
Results logged to
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/extensions/x86_64-linux/2.3.0/json-1.8.1/gem_make.out

An error occurred while installing json (1.8.1), and Bundler cannot
continue.
Make sure that `gem install json -v '1.8.1'` succeeds before bundling.

む、なんかエラーが。ヘッダファイル ruby.h が見つからないのか？
再び takatho ユーザで。ああもう、いちいちめんどくさいな。

takatoh@wplj $ sudo apt install ruby-dev

tonzlr に戻ってもう一度。今度はどうだ。

tonzlr@wplj:~/tonzlr$ bundle install --path vendor/bundle
Fetching gem metadata from https://rubygems.org/..........
Fetching version metadata from https://rubygems.org/..
Fetching dependency metadata from https://rubygems.org/.
Using rake 10.4.2
Using i18n 0.7.0
Installing json 1.8.1 with native extensions
Using minitest 5.5.0
Using thread_safe 0.3.4
Using builder 3.2.2
Using erubis 2.7.0
Using rack 1.5.2
Using mime-types 1.25.1
Using polyglot 0.3.5
Using arel 5.0.1.20140414130214
Using coffee-script-source 1.8.0
Using execjs 2.2.2
Using thor 0.19.1
Using hike 1.2.3
Using multi_json 1.10.1
Using libv8 3.16.14.3 (x86_64-linux)
Using bundler 1.14.6
Using tilt 1.4.1
Using ref 1.0.5
Using sass 3.2.19
Using spring 1.2.0
Installing sqlite3 1.3.10 with native extensions
Using will_paginate 3.0.7
Gem::Ext::BuildError: ERROR: Failed to build gem native extension.

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
/usr/bin/ruby2.3 -r ./siteconf20170304-5824-26t94o.rb extconf.rb
creating Makefile

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
make "DESTDIR=" clean

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
make "DESTDIR="
compiling generator.c
In file included from generator.c:1:0:
../fbuffer/fbuffer.h: In function ‘fbuffer_to_s’:
../fbuffer/fbuffer.h:175:47: error: macro "rb_str_new" requires 2 arguments, but
only 1 given
     VALUE result = rb_str_new(FBUFFER_PAIR(fb));
                                               ^
../fbuffer/fbuffer.h:175:20: warning: initialization makes integer from pointer
without a cast [-Wint-conversion]
     VALUE result = rb_str_new(FBUFFER_PAIR(fb));
                    ^
Makefile:239: ターゲット 'generator.o' のレシピで失敗しました
make: *** [generator.o] エラー 1

make failed, exit code 2

Gem files will remain installed in
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1 for inspection.
Results logged to
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/extensions/x86_64-linux/2.3.0/json-1.8.1/gem_make.out

An error occurred while installing json (1.8.1), and Bundler cannot
continue.
Make sure that `gem install json -v '1.8.1'` succeeds before bundling.

まだエラーが！
ググってみるとこのページに
　cf. https://github.com/flori/json/issues/253
libgmp3-dev をインストールすればいい、みたいに書いてある。

takatoh@wplj $ sudo apt install libgmp3-dev

tonzlr@wplj:~/tonzlr$ bundle install --path vendor/bundle
Fetching gem metadata from https://rubygems.org/..........
Fetching version metadata from https://rubygems.org/..
Fetching dependency metadata from https://rubygems.org/.
Using rake 10.4.2
Using i18n 0.7.0
Installing json 1.8.1 with native extensions
Using minitest 5.5.0
Using thread_safe 0.3.4
Using builder 3.2.2
Using erubis 2.7.0
Using rack 1.5.2
Using mime-types 1.25.1
Using polyglot 0.3.5
Using arel 5.0.1.20140414130214
Using coffee-script-source 1.8.0
Using execjs 2.2.2
Using thor 0.19.1
Using hike 1.2.3
Using multi_json 1.10.1
Using libv8 3.16.14.3 (x86_64-linux)
Using bundler 1.14.6
Using tilt 1.4.1
Using ref 1.0.5
Using sass 3.2.19
Using spring 1.2.0
Installing sqlite3 1.3.10 with native extensions
Using will_paginate 3.0.7
Gem::Ext::BuildError: ERROR: Failed to build gem native extension.

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
/usr/bin/ruby2.3 -r ./siteconf20170304-7573-1jyzrko.rb extconf.rb
creating Makefile

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
make "DESTDIR=" clean

current directory:
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1/ext/json/ext/generator
make "DESTDIR="
compiling generator.c
In file included from generator.c:1:0:
../fbuffer/fbuffer.h: In function ‘fbuffer_to_s’:
../fbuffer/fbuffer.h:175:47: error: macro "rb_str_new" requires 2 arguments, but
only 1 given
     VALUE result = rb_str_new(FBUFFER_PAIR(fb));
                                               ^
../fbuffer/fbuffer.h:175:20: warning: initialization makes integer from pointer
without a cast [-Wint-conversion]
     VALUE result = rb_str_new(FBUFFER_PAIR(fb));
                    ^
Makefile:239: ターゲット 'generator.o' のレシピで失敗しました
make: *** [generator.o] エラー 1

make failed, exit code 2

Gem files will remain installed in
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/gems/json-1.8.1 for inspection.
Results logged to
/home/tonzlr/tonzlr/vendor/bundle/ruby/2.3.0/extensions/x86_64-linux/2.3.0/json-1.8.1/gem_make.out

An error occurred while installing json (1.8.1), and Bundler cannot
continue.
Make sure that `gem install json -v '1.8.1'` succeeds before bundling.

まだダメだ。最後のメッセージのように json をインストールしてみる。

takatoh@wplj $ sudo gem install json -v '1.8.1'
Fetching: json-1.8.1.gem (100%)
Building native extensions.  This could take a while...
ERROR:  Error installing json:
	ERROR: Failed to build gem native extension.

    current directory: /var/lib/gems/2.3.0/gems/json-1.8.1/ext/json/ext/generator
/usr/bin/ruby2.3 -r ./siteconf20170304-7998-r1om93.rb extconf.rb
creating Makefile

current directory: /var/lib/gems/2.3.0/gems/json-1.8.1/ext/json/ext/generator
make "DESTDIR=" clean

current directory: /var/lib/gems/2.3.0/gems/json-1.8.1/ext/json/ext/generator
make "DESTDIR="
compiling generator.c
In file included from generator.c:1:0:
../fbuffer/fbuffer.h: In function ‘fbuffer_to_s’:
../fbuffer/fbuffer.h:175:47: error: macro "rb_str_new" requires 2 arguments, but only 1 given
     VALUE result = rb_str_new(FBUFFER_PAIR(fb));
                                               ^
../fbuffer/fbuffer.h:175:20: warning: initialization makes integer from pointer without a cast [-Wint-conversion]
     VALUE result = rb_str_new(FBUFFER_PAIR(fb));
                    ^
Makefile:239: ターゲット 'generator.o' のレシピで失敗しました
make: *** [generator.o] エラー 1

make failed, exit code 2

Gem files will remain installed in /var/lib/gems/2.3.0/gems/json-1.8.1 for inspection.
Results logged to /var/lib/gems/2.3.0/extensions/x86_64-linux/2.3.0/json-1.8.1/gem_make.out

ダメだな。詰んだか？
……というところで時間切れ。今日はここまで。

takatoh@wplj $ sudo apt install ruby

takatoh@wplj $ ruby -v
ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]

おお、2.3だ。

Python

takatoh@wplj $ sudo apt install python
パッケージリストを読み込んでいます... 完了
依存関係ツリーを作成しています                
状態情報を読み取っています... 完了
python はすでに最新バージョン (2.7.11-1) です。
python は手動でインストールしたと設定されました。
アップグレード: 0 個、新規インストール: 0 個、削除: 0 個、保留: 432 個。

あれ、入ってる？

takatoh@wplj $ python -V
Python 2.7.11+

入ってた。

デーモンとして動かすSinatraアプリにユーザーのインストールしたRubyを使わせる

以前作った Sinatra アプリ（フォトビューワー）をデーモンとして動かそうとしてハマった記録。
Sinatra アプリをデーモン化したことは前にもやったことがあるので、基本的にはその時のエントリを見ながらやったんだけど、一つだけ、ハマりどころがあった。それはアプリが Ruby 2.0 以降（だっけ？）にサポートしているキーワード引数を使って書いてあるのに対して、システムにインストールされているのは Ruby 1.9.3 だってこと。ユーザーは rvm でインストールした 2.3.0 を使っているのでテスト中は動くけど、いざ本番になってみるとシステムの 1.9.3 が使われるので動かない。
どうにかしてデーモンにも rvm でインストールした 2.3.0 を使わせたい。
探し方が悪いのか、ググっても情報が出てこない。結局解決策を見つけたのは、自分のエントリだった。

つまり、起動スクリプトで GEM_PATH と GEM_HOME に rvm のパスを設定して export すればいいようだ。書いた起動スクリプトがこれ：

#!/bin/sh

PATH=/home/potov/.rvm/rubies/ruby-2.3.0/bin:/home/potov/.rvm/gems/ruby-2.3.0/bin:/sbin:/bin:/usr/bin
GEM_PATH=/home/potov/.rvm/gems/ruby-2.3.0
GEM_HOME=/home/potov/.rvm/gems/ruby-2.3.0
export PATH
export GEM_PATH
export GEM_HOME

POTOV_ROOT=/home/potov/potov

case "$1" in
start)
cd ${POTOV_ROOT}
unicorn -c unicorn.conf -D
;;
stop)
PID=`cat ${POTOV_ROOT}/unicorn.pid`
kill -QUIT ${PID}
;;
*)
echo "Usage: potov {start|stop}"
exit 1
;;
esac

exit 0

当然 PATH も rvm の Ruby のパスを設定している。
ともあれ、これで無事起動するようになった。

Windows 10環境のrubygemsでSSLエラーが発生した場合の対処法

新しい PC のセットアップ中、rubygems でエラーが発生した。環境は次の通り。

Windows 10 Home
Ruby 2.3.1 (RubyInstaller)
gem 2.5.1

発生したエラーは：

^o^ > gem install acm
ERROR:  Could not find a valid gem 'acm' (>= 0), here is why:
          Unable to download data from https://rubygems.org/ - SSL_connect returned=1 errno=0 state=SSLv3 read server certificate B: certificate verify failed (https://api.rubygems.org/specs.4.8.gz)

どうも、SSLのエラーらしい。

で、いろいろとググりながら試した結果、次の手順でうまく回避できたのでメモしておく。

rubygemsのアップデート

普通なら gem コマンドでアップデートできるけど、それが使えないので rubygems.org からダウンロードしてアップデートする。
　cf. rubygems-update 2.6.8
上のリンクから、rubygems-update の最新版 2.6.8 をダウンロード、インストールする。

^o^ > gem install rubygems-update-2.6.8.gem --local
Successfully installed rubygems-update-2.6.8
Parsing documentation for rubygems-update-2.6.8
Installing ri documentation for rubygems-update-2.6.8
Done installing documentation for rubygems-update after 39 seconds
1 gem installed

^o^ > gem -v
2.5.1

インストールしただけではアップデートされないので、update_rubygems コマンドでアップデートする。

^o^ > update_rubygems
RubyGems 2.6.8 installed
Parsing documentation for rubygems-2.6.8
Installing ri documentation for rubygems-2.6.8
（以下略）

長々とメッセージが出るけど、これでアップデートできた。

^o^ > gem -v
2.6.8

確認

これで、正常に使えるようになったはず。

^o^ > gem install acm
Fetching: thor-0.19.1.gem (100%)
Successfully installed thor-0.19.1
Fetching: acm-0.4.2.gem (100%)
Successfully installed acm-0.4.2
Parsing documentation for thor-0.19.1
Installing ri documentation for thor-0.19.1
Parsing documentation for acm-0.4.2
Installing ri documentation for acm-0.4.2
Done installing documentation for thor, acm after 2 seconds
2 gems installed

OK。

参考ページ

　cf. Ruby distros, RubyGems, and SSL—Oy vey!

九九表のすべてのマスの和

前回から時間が開いてしまった。本当は Text.Parsec の話題を書こうと思ってるんだけど、今日も時間がないので小ネタ、しかも他人のネタ。

　cf. 九九表のすべてのマスの和 – 無駄と文化

詳しくはリンク先を見て。いくつかの言語でやってるんだけど、Ruby と Scheme がなかったのでやってみた。

まずは Ruby。

# encoding: utf-8

def sum_of_kuku
  a = (1..9).to_a
  a.product(a).map{|x,y| x * y}.inject(:+)
end

puts sum_of_kuku

takatoh@apostrophe $ ruby sum_of_kuku.rb
2025

１〜９までの配列の直積をとって、それぞれを掛けあわせて、最後に全部足してるだけ。

Scheme でも同じ考え方。でもリストの直積を取る手続きが見当たらなかったので direct-product を自作した。

(use srfi-1)

(define direct-product
  (lambda (lis1 lis2)
    (append-map
      (lambda (x) (map (lambda (y) (list x y)) lis2))
      lis1)))

(define sum-of-kuku
  (lambda ()
    (let ((l1 '(1 2 3 4 5 6 7 8 9))
          (l2 '(1 2 3 4 5 6 7 8 9)))
      (apply + (map (lambda (x) (apply * x)) (direct-product l1 l2))))))

(print (sum-of-kuku))

takatoh@apostrophe $ gosh sum-of-kuku.scm
2025

逆関数法で指数分布する乱数を生成する

[0,1)区間の一様乱数から、指数分布にならう乱数を生成するには、逆関数法というのが使える。
指数分布の密度関数は、パラメータをτとすると：
$$ f(\tau)=\lambda e^{-\lambda\tau} $$
であり、分布関数 g(τ) は：
$$ g(\tau)=\int^\tau_{-\infty}{\lambda e^{-\lambda\tau}}d\tau=1-e^{-\lambda\tau} $$
となる。g(τ)は 0～1 の値をとるので、この逆関数：
$$ \tau=-\frac{1}{\lambda}log(1-g(\tau)) $$
の g(τ) の代わりに一様乱数を入力してやれば、τ は指数分布する乱数になる。

じゃあ Ruby でやってみよう。

# encoding: Windows-31J

class RandExpon
  def initialize(lamda)
    @lamda = lamda
    @r = Random.new
  end

  def rand
    -1.0 / @lamda * Math.log(1 - @r.rand)
  end
end

expon = RandExpon.new(0.5)
  10000.times do |i|
  puts expon.rand
end

λ=0.5とし、10000個の乱数を発生させている。
これを Excel でグラフ化したのがこれ。

「指数分布」の曲線は、上に書いた密度関数の曲線を、スケールを合わせるために8000倍して描いている。乱数はちゃんと指数分布になっているようだ。

参考にしたページ：
　cf. http://www.ishikawa-lab.com/montecarlo/4shou.html

Box-Muller法で正規分布する乱数を生成する

一様分布する乱数から、正規分布に従う乱数を生成する方法に、Box-Muller法というのがある。
Wikipediaによれば、(0,1) 区間の一様分布乱数2つ（X,Y）から、下の式で2つの正規分布乱数 $ Z_1 $ と $ Z_2 $ が得られる。

$$
Z_1=\sqrt{-2log{X}}\cos{2\pi{Y}}
Z_2=\sqrt{-2log{X}}\sin{2\pi{Y}}
$$

$ Z_1 $ と $ Z_2 $ は標準正規分布となるので、これらに標準偏差 σ をかけて平均 μ を足してやれば、任意の正規分布に従う乱数が得られる。

Ruby で 10000個の乱数を発生させるスクリプトを書いてみた。ここでは平均 μ=1.0、標準偏差 σ=0.2 とした。

# encoding: Windows-31J

class BoxMuller
  def initialize(mu, sigma)
    @mu = mu
    @sigma = sigma
    @r = Random.new
    @z2 = nil
  end

  def rand
    if @z2
      z1 = @z2
      @z2 = nil
    else
      x = @r.rand
      y = @r.rand
      z1 = Math.sqrt(-2.0 * Math.log(x)) * Math.sin(2 * Math::PI * y)
      @z2 = Math.sqrt(-2.0 * Math.log(x)) * Math.cos(2 * Math::PI * y)
    end
    @sigma * z1 + @mu
  end
end

bm = BoxMuller.new(1.0, 0.2)
10000.times do |i|
  puts bm.rand
end

結果を Excel でグラフ化してみた。水色の点が 0.1 単位のヒストグラム。黄緑の線が Excel に用意されている NORM.DIST 関数で描いたもの（スケールを合わせるために NORM.DIST 関数の値は 1000 倍している）。

こうしてみると、ほぼぴったりと正規分布になっているようだ。

ちなみに Excel で平均値と標準偏差を求めたら、それぞれ μ=0.997、σ=0.201 となった。

Windowsマシンで動かしているSinatraアプリにほかのマシンからアクセスできなくてハマった

おおよその事情はタイトルの通り。
Windows マシンで Sinatra アプリを動かす。

^o^ > rackup config.ru

ポート 9292 で待機するので、ほかのマシンからアクセスするも繋がらない。ローカルホストからだとちゃんと繋がるので、アプリのせいではない……と思ったら、これが大間違いだった。

最初、ファイアウォールのせいだと思って Norton Internet Security のポート開放方法とかをググって試してみたけど、どうやっても繋がらない。
さんざんやったあげく、ふと Sinatra で同じ目にあってる人がいるかと思って「ruby sinatra ポート」でググったら、次のページを見つけた。

　cf. Sinatraがデフォルトでは外部から繋がらなくなってたよ – Qiita

なんてこった。Sinatra 1.4.0 から development 環境ではデフォルトでローカルホストからしかアクセスを受け付けなくなったようだ。
ともあれ、原因と解決法が分かった。次のようしてどのホストからのアクセスも受け付けるようにすればいい。

^o^ > rackup -o 0.0.0.0 config.ru

これで無事OK。

ダイクストラ法

ダイクストラ法とは、グラフ上の最短経路問題をとくアルゴリズム。↓このページに詳しいアルゴリズムの説明がある。

　cf. ダイクストラ法（最短経路問題） – deq notes

Ruby でやってみた。
例題は、上のページにもあるこのグラフ（ただしノードにつけた番号のせいか上下が逆になっている）。

円（ノード）に番号がふられ、ノードをつなぐ辺（エッジ）にはそこを通るときのコスト（距離とも時間とも解釈できる）が付されている。この中の任意の 2 つのノードをつなぐ最短経路とコストを求めるのが最短経路問題だ。
今回は 0 番のノードをスタートし 5 番のノードをゴールとする最短経路とそのコストを求めてみる。

#!/usr/bin/env ruby
# encoding: utf-8

class Node

  attr_reader :name
  attr_accessor :done, :cost, :from

  def initialize(name)
    @name = name
    @edges = []
    @done = false
    @cost = nil
    @from = nil
  end

  def add_edge(edge)
    @edges << edge
  end

  def each_edge
    @edges.each{|e| yield(e) }
  end

end

Edge = Struct.new(:dest, :cost)

def make_edge(nodes, a, b, cost)
  nodes[a].add_edge(Edge.new(b, cost))
  nodes[b].add_edge(Edge.new(a, cost))
end

nodes = []
0.upto(5) do |i|
  nodes << Node.new(i)
end

edges = [
  [0, 1, 2],    # [node_a, node_b, cost]
  [0, 2, 4],
  [0, 3, 5],
  [1, 2, 3],
  [2, 3, 2],
  [1, 4, 6],
  [2, 4, 2],
  [4, 5, 4],
  [3, 5, 6]
]
edges.each do |a, b, cost|
  make_edge(nodes, a, b, cost)
end

start = 0
goal = 5

start_node = nodes[start]
start_node.cost = 0
start_node.done = true
start_node.each_edge do |edge|
  n = nodes[edge.dest]
  n.cost = edge.cost
  n.from = start_node.name
end

while true do
  done_node = nil
  nodes.each do |node|
    if node.done || node.cost.nil?
      next
    else
      node.each_edge do |e|
        n = nodes[e.dest]
          if n.cost.nil?
          n.cost = node.cost + e.cost
          n.from = node.name
        else
          if node.cost + e.cost < n.cost
            n.cost = node.cost + e.cost
            n.from = node.name
          end
        end
      end
      if done_node.nil? || node.cost < done_node.cost
        done_node = node
      end
    end
  end
  done_node.done = true
  break if nodes.all?{|n| n.done }
end

puts nodes[goal].cost
route = [goal]
begin
  node = nodes[route.first]
  route.unshift(node.from)
end
until route.first == start

 puts route.map(&:to_s).join(" -> ")

実行結果：

takatoh@nightschool $ ruby dijkstra.rb
10
0 -> 2 -> 4 -> 5

というわけで、最短経路は 0 -> 2 -> 4 -> 5、コストは 10 という答えが得られた。これは上のリンク先の答えと同じなので、あっていると思っていいだろう。

カテゴリー: Ruby

Railsアプリの引っ越し(2)とりあえず動いた編