Journal InTime

_ 日記

RDで日記を書くためのスクリプトを作ったので日記を書くことにした。 (何か話が逆のような気もするけれど。)

_ コーヒーの木

コーヒーの木が安かった(百円台だったかな)ので、婚約者が買って、 僕の部屋で育てることになった。 葉っぱが何枚か枯れてるので、ちゃんと育つかちょっと心配。

でも部屋に緑があるというのも悪くないですね。 今の時期ならクリスマスツリーになるし。(ならないか。)

_ 僕

「僕」ってT-Codeで直接入力できないことに気付いた。 「ぼく」とか「私」にしようかなあ。

_ bsd style

EmacsをupgradeしたらCCモードの"bsd"スタイルのc-basic-offsetが8になっていた。

なんか納得行かないけど、スタイル定義にc-basic-offsetを追加。

(c-add-style
 "mystyle"
 '("bsd"
   (c-basic-offset . 4)
   (c-offsets-alist
    (label . 2)
    )))

labelのoffsetを変えてるのはcaseのラベルと区別するため。 (defualt:対策)

ちなみに、Rubyのソースをいじる時は、以下のようなスタイルを使うと便利です。

(c-add-style
 "ruby"
 '("bsd"
   (c-basic-offset . 4)
   (c-offsets-alist
    (case-label . 2)
    (label . 2)
    (statement-case-intro . 2)
    (statement-case-open . 2)
    )))

_ 累積分布関数

Rubyで累積分布関数を扱う方法を調べてみた。 ぐぐったところSciRubyのstatsampleライブラリを使えばいいらしい。

ドキュメントがあまり見当たらないけど、サンプルのhistogram.rbとかを見るとこんな感じで使えばよいようだ。

require "statsample"

# テスト用に平均値40、標準偏差10のデータを1000個生成
v = Statsample::Shorthand::rnorm(1000, 40, 10)

# 最小値から最大値まで0.5ずつループ
v.min.step(v.max, 0.5) do |x|
  # 値xと、xにおける累積分布値をカンマ区切りで出力
  puts [x, Distribution::Normal.cdf((x - v.mean) / v.sd)].join(",")
end

Normalのところを変えると正規分布以外も扱えるらしい。

LibreOfficeのNORMDIST()関数の結果と比べると一致したのでたぶん合ってると思うけど、使い方が間違ってたら教えてください。

_ 松江Ruby会議08

今年も松江Ruby会議に参加してきた。

食後のコーヒーを飲んでいたらLTを聞き逃したが、その他のセッションはどれも楽しめた。松田さんの講演でdisられたけど。

吉岡さんに言われて参加したプログラミングコンテストでは一般部門1位でMisocaさん提供のAmazon Dash Button 1万円分（つまりボタン20個）をいただいた。

最終計測では2位のsimanさんと4msec差だったそうなので、測定誤差のような気がする。

同じようなプログラムをたくさん応募したのでどれが1位になったのかはっきりしないが、バイト数的にたぶん以下のプログラムだと思う。

m=$<.read;v=m.tr($/,?#).unpack"C*";g=/G/=~m;q=[s=/S/=~m];while(i=q.pop)!=g;v[i]=35;[1,-1,s,-s].each{|d|v[j=i+d]!=35&&q<<j&&$:[j]=i}end;m[i]=?:while(i=$:[i])!=s;$><<m

各変数は以下のような意味をもつ。

• m -> map = マップ情報
• v -> visited = 探索済みノード情報（兼壁情報）
• s -> start = スタート位置
• q -> queue = キュー（最終的にスタックになってしまった）
• i -> 探索中ノードのインデックス
• j -> 隣接ノードのインデックス
• $: -> 経路情報(最終的にマップ上に:と出力）

一文字変数のわりにわかりやすい（自画自賛）。

その後さらに削って

q=[i=s=/S/=~m=$<.read];v=m.tr$/,?#;[1,-1,s,-s].each{|d|v[j=i+d]!=(v[i]=?#)&&q<<j&&$:[j]=i}while/G/!~v[i=q.pop];m[i]=?:while(i=$:[i])!=s;$><<m

こんなのや

m=$<.read;q=[i=s=/S/=~v=m.dup];[1,-1,s,-s].each{|d|v[i]=$/;/#|
/!~v[j=i+d]&&q<<j&&$:[j]=i}while/G/!~v[i=q.pop];m[i]=?:while(i=$:[i])!=s;$><<m

こんなのも応募（ブラウザからだと改行がCRLFになってしまうので、Net::HTTPで送信）したが、文字数節約のため探索済みノードのマーク(v[i]=?#)を無駄にeachの中に押しこんだり、vが配列ではなく文字列になったりしている分遅かったかもしれない。

最初はマップによっては速くなるかもしれないと思ってA*で書いていたが、

• ヒューリスティック関数で常に0を返すようにしても本番のマップだとタイムが変わらないのでダイクストラに修正。
• 隣接ノードへの移動コストはすべて1なので単純なBFSに（priority queueやsorted arrayがいらない）。
• DFSに変更しても本番のマップ5つすべてクリアできることに気付きDFSに（shiftよりpopの方が短い）。

という感じ修正して、今回の条件だと単純な実装が一番速いという結果に。 たぶんマップが小さくて経路も少なく、A*が有利になるようなマップ（スタート・ゴールが偏っていて経路が直線的なのとか）もなかったのだろう。

工夫した点は

• マップや探索済みノードの情報を二次元配列（というかjagged array）で持つとコストが大きいので、一次元配列を採用。 座標(x, y)をx + マップ幅 * yというインデックスに変換して扱うが、単純なBFS/DFSでは座標を意識する必要すらなかったので低コストにできた。
• スタート・ゴール以外は壁で囲まれていることを利用して、インデックスが範囲外かどうかのチェックを省略。
• ただし、スタートから左に移動すると壁がないため、改行($/)を壁(#)に置換。
• 探索済みノードの情報を上記の壁情報と共通化。
• すべてのマップでスタート位置が同じで二行目先頭だったため、マップ幅の計算をスタート位置で代用。

といったところ。

変数のスコープ的にwhile修飾子が使いにくいことを実感したので何か言語仕様の変更を提案しようかとも思ったが、ゴルフとかでしか使わなさそうだ（し自分はゴルファーじゃない）からやっぱりいいか。