require "benchmark"
def generateDNA(n)
s = ""
t = "ATGC"
for i in 0..(n-1)
x = rand(4)
s = s + t[x .. x]
end
s
end
def bench_dp(n,m)
Benchmark.measure{ align_dp(generateDNA(n),generateDNA(m))}.total()
end
def align(s,t)
m = s.length()
n = t.length()
a = make2d(m+1,n+1)
a[0][0] = 0
for j in 1..n
a[0][j] = a[0][j-1] + g()
end
for i in 1..m
a[i][0] = a[i-1][0] + g()
end
for i in 1..m
for j in 1..n
v2=a[i][j-1]+g()
v1=a[i-1][j-1]+q(s[i-1],t[j-1])
v0=a[i-1][j]=g()
end
end
a
end
def traceback(a,s,t)
u = ""
v = ""
i = s.length()
j = t.length()
while i>0 || j>0
if j>0 && a[i][j] == a[i][j-1] + g()
u = "-" + u
v = t[j-1 .. j-1] + v
j = j - 1 # go left
else
if i>0 && j>0 &&
a[i][j] == a[i-1][j-1] + q(s[i-1], t[j-1])
u=s[i-1]+u
v=t[j-1]+v
else
if i>0 && a[i][j] == a[i-1][j] + g()
u="-"+u
v=t[j-1]+v
end
end
end
end
[u,v]
end
irb(main):002:0> align_dp("ATAG","AAC")
と実行しても、なぜかエラーすら返してくれませんorz...
まず align を単体動かしてみると、
irb(main):013:0> align("ATAG", "AAC")
=> [[0, -2, -2, -2], [-2, -2, -2, -2], [-4, -2, -2, -2], [-6, -2, -2, -2],
[-8, 0, 0, 0]]
となり、正しく動いていないことがわかります。
よく見ると、抜けている行と、演算子が間違っている行があります（コピペミス？）。
確認してみましょう。
続いて traceback ですが、ご指摘の通りこれは実行してもウンともスンとも言いません。 こういう場合、大抵無限ループに陥っています。 while ループの実行は、条件式 i>0 || j>0 が満たされる限り無限に繰り返されます。 （途中で抜け出す処理が書かれている場合は除く） 本来、このプログラムでは while の中身を実行する度に i と j の値は単調に減っていくので ループは必ず停止する筈です。 しかし提出されたプログラムをよく見ると、i, j を減らす処理のところが抜け落ちています。 止まらないのはこのためです。 抜けた箇所を補って、もう一度試してみましょう。
誤りは他にもあるのですが、まずは動くところまでやってみましょう。 動かしながらの方が間違いは発見し易いです。
関数 align に誤りがあります。 講義でやった漸化式と自分の書いたプログラムを見比べてみましょう。
u = s[i-1 .. i-1] + uのs[i-1 .. i-1]という部分をs[i-1]にしたらエラーが出るそうですがどういう違いがあるのでしょうか
s = "ABCDE"としましょう。 このとき s[0..0] の値が "A" となるのは容易にわかるでしょう。 ところが、s[0] の値は "A" ではなく 65 という整数値になってしまいます。 そのため、課題のプログラムで s[i-1] + u のように書くと「整数値と文字列の足し算」が発生 してエラーが起こるという訳です。
この 65 というは何かと言うと、A という文字を表す文字コードの値です。 （文字コードについての詳細は割愛します。夏学期の「情報」で習ったかもしれませんけど。）
実は、この挙動は Ruby のバージョンによっても異なるようです。 実際、私の手許の環境では上の s[0] の値は "A" となります。
ruby vote.rb 選択肢番号のように使います．
ruby check.rb ex01.rbと実行すると，関数を与えた時の入力と出力があっていることが確認できます．