ratio - rational - irrational

LL Ringのキミならどう書く 2.0 ROUND 2。 鍋あり谷ありとか、Rubyによる回答が既に出ていたので昨日は別の言語で書いてしまったけど、ふと思い付いたのでやっぱりRubyで書いてみる。

そこでブロックですよ、ブロック。Rubyらしく、「非関数らしく」。

問題文の言い替えと、副作用の話

出題では、「ステップ数」という形で、つまり関数fに対する副作用のような形でgが定義されているから、そこを数学的に読みかえないといけない。それで、要は移した先が1になるまでの回数を数えればいいんでしょ、とやるのが「ふつう」だやな。

例えばこんな風になる。

Collatz予想

自然数n ≥ 1に対して次の数列c_kを定義する。

• c₁ = n
• c_i+1 =
  • 1            if c_i = 1
  • c_i/2        if c_i is even
  • 3c_i + 1  if c_i is odd

このとき、数列c_kは必ず1に収束すると予想されている。

問題

あるnに対して、c_k = 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になるところまでの回数を答えればいいんでしょ?」という「言い替えた」実装だ。

少なくとも私は純粋関数言語で「言い替えない」実装は書けないので、スーパーハカーの挑戦求む。