LL Ringのキミならどう書く 2.0 ROUND 2。 鍋あり谷ありとか、Rubyによる回答が既に出ていたので昨日は別の言語で書いてしまったけど、ふと思い付いたのでやっぱりRubyで書いてみる。
そこでブロックですよ、ブロック。Rubyらしく、「非関数らしく」。
問題文の言い替えと、副作用の話
出題では、「ステップ数」という形で、つまり関数fに対する副作用のような形でgが定義されているから、そこを数学的に読みかえないといけない。それで、要は移した先が1になるまでの回数を数えればいいんでしょ、とやるのが「ふつう」だやな。
例えばこんな風になる。
- Collatz予想
-
自然数n ≥ 1に対して次の数列ckを定義する。
- c1 = n
- ci+1 =
- 1 if ci = 1
- ci/2 if ci is even
- 3ci + 1 if ci is odd
このとき、数列ckは必ず1に収束すると予想されている。
- 問題
-
あるnに対して、ck = 1となる最小のkをg(n)とする。
1からnまでの自然数の中で、g(k)を最大とするような自然数kをh(n)とする。
このとき、h(100)を求めよ。
こんな感じか。
Rubyによる「言い替えない」実装
でも、折角Rubyで、ALGOL系の記述ができるんだから、読みかえなくても副作用は副作用のままに書けてほしいよね。で、ブロックだ。イテレータをちょっと捻って見てみれば、関数値の計算過程で随時副作用を呼び起こすためのものと言ってもいいよね。
たぶん、オリジナルの問題文の言い回しに一番忠実な、素朴な実装はこんな感じになると思う。これは純粋関数型言語だと書くの難しいんじゃない?*1 ここで書いた関数fは、今はブロック付きで読んでるけどブロックなしで呼べば本当に問題文どおりの計算をする副作用が無い関数になるっていうのもうれしいところ。
Pythonだとgeneratorでもう少し綺麗に書けるのかもわからないけれど、でもRubyらしさ(=ブロック)を活かすとこうなるんじゃない? Rubyにはブロックがあって、関数型計算ではどうせ関数型言語には叶わないから、せめて、ALGOL系らしく。
def f(n,&proc)
image =
if n == 1
1
elsif n%2 == 0
f(n/2, &proc)
else
f(3*n+1, &proc)
end
proc.call image if proc
image
end
def g(n)
step = 0
f(n) do
step += 1
end
step
end
def h(n)
g_values = (1..n).map{|i| [i, g(i)]}
# [BUG] Enumerable#sort is unstable
# max_value = g_values.sort{|x,y| x[1] <=> y[1]}.last[0]
g_values.max {|x, y|
order = (x[1] <=> y[1])
order = (y[0] <=> x[0]) if order.zero?
order
}
end
puts h(ARGV.shift.to_i)
数学的変換とか要求しない「普通の人のための言語、Ruby」。だから、Rubyistはブロックですよ、ブロック。
2006-07-13追記: Enumerable#sortが不安定ソートなのを忘れてた。g(18) = g(19) = 21なので、h(19)とか計算させるとどちらが返るか不定だった。御指摘感謝。
- *1
関数型では難しかろうという挑戦にlethevertさんが「Concurrent Clean : L.L.Ring : Collatz予想の収束」で答えてくださった。流石、Concurrent Cleanの解はエレガント。そのエレガントさに飲まれて一瞬「やられた! 完敗」と思った。でも、今落ち着いて見てみたら「fで移して1になるところまでの回数を答えればいいんでしょ?」という「言い替えた」実装だ。
少なくとも私は純粋関数言語で「言い替えない」実装は書けないので、スーパーハカーの挑戦求む。
