ウバベストシーズン

初稿：2004-11-15

著者: 池上大介 <ikegami at madscientist.jp>

はじめに

ウバと言えば、スリランカ産紅茶のなかでも深いコクと独特の苦みが知られる世界3大銘茶のひとつである。しかし、パズル好きプログラマにとってのウバとは Problem Set Archiveを言う。

ウバのサイトを初めて訪れた方は、画面右側のリンクを読んでいただきたい。

ウバは、プログラムを書いて解くパズル/問題を集めたサイトである。パズルは答えがわかってしまうと陳腐化してしまうが、ウバでは多くのボランティアスタッフに支えられて、プログラマを楽しませる新しい問題が投稿され続けている。

ウバの特徴は、問題の数や面白さ、新鮮さだけではなく、プログラムを投稿して腕試しできることにある。投稿されたプログラムはウバ側で実際に実行され(!)、制限時間内に仕様通りの答えを返すかどうかを検査される。そこで、単に答えを正確に出すだけでなく、スピードの早さや、計算に必要なメモリーの少なさ、移植性も試されることになる。

しかし、残念なことに、投稿できるプログラムは C/C++/Pascal/Java で書かれたものに限られる。ウバに登録された優れた問題たちがこの 4 つの言語ユーザにしか知られないのは大変残念なので不祥、筆を取った次第である。

Ruby でウバ

前章に書いたように、Ruby で書いたプログラムをウバで自動検査してもらうことはできない。しかし、我々には

UnitTest ライブラリ
BenchMark ライブラリ

がある。そこで、(厳密ではないが)、ウバの要求「正確に速く動け」に近いテストを我々の手もとでも出来るのだ。問題を解くときは、紳士的に振る舞い、満足するまで追求することを誓おう。

Problem 1. http://acm.uva.es/p/v1/100.html

(出題者: 匿名 (University of Valladolid))

ウバの記念すべき第 1 問目は 3n + 1 問題である。

この問題は Collatz 予想など、さまざまな別名で呼ばれ、古くから知られている難予想である。http://mathworld.wolfram.com/CollatzProblem.html に詳しい。

ウバで提示されている問題の説明に入る前に、この問題の背景についてざっと眺めよう。次のコードを見てほしい。

 def collatz_len(n)       # n は非負整数
   len = 1
   while n != 1
     len += 1
     if n % 2 == 1
       n = 3 * n + 1  # でかまれっ!
     else
       n = n / 2      # ちぢめれっ!
     end
   end
   len
 end

collatz_len の引数には正の整数を入れることにする。引数が正の整数であるかどうかの検査は簡単であるが省略した。(n が Integer であるかどうか、および n > 0 かどうかを最初に確かめればよい) collatz_len の while ループの中で n は次のように変化する:

n が(3以上の)奇数なら n = 3n + 1
n が偶数なら n = n / 2

ループ中で n が 1 になったらループから脱出する。たとえば、n = 6 のときは

 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (n = 1 になったのでここまで)

となる。変数 len はこの列の長さを表しており (この場合は 9) 、collatz_len は len、つまり n に対するこの操作の列の長さを返す。

collatz_len がどんな n に対しても必ず停止するか? (つまり操作を繰り返していつか n = 1 になるか?) は今のところ誰にもわかっていない。

問題

次の仕様を満たすプログラムを書け。ただし、「n のサイクル長」は、上記説明で用いたメソッド collatz_len の返り値 len を指すものとする。 (Hint: なぜサイクルと呼ぶんだろう?)

 入力: 0 以上 10,000 以下の整数 i, j
 出力: (i, j) と、i と j の間にある数のうち最大のサイクル長

 入力例
   1   10
   100 200
   201 210
   900 1000
 出力例
   1 10 20
   100 200 125
   201 210 89
   900 1000 174

仕様要求

次の Unit Test に合格しなさい

    あなたが作ったメソッドの名前を仮に cmaxlen(i, j) とした

     require 'runit/testcase'
     require 'runit/cui/testrunner'
     require 'benchmark'
     include Benchmark

     class TestUnit < RUNIT::TestCase
       def setup
         # for test 1.
         c = 10
         tw = 100
         @tiny_data = (1..c).map {
           s = rand(1000)
           [s, s + tw]
         }

         # for test 2.
         limit = 10000
         @huge_data = [[rand(100), limit]]
         @time_limit = 1
       end

       # test1. 正確さ
       def bf_cmaxlen(i, j) # brute forcing method
         i, j = j, i if i > j
         (i..j).map { |n| collatz_len(n) }.max  # collatz_len は既出
       end
       def test_acculacy
         @tiny_data.map { |i, j|
           assert_equal(cmaxlen(i, j), bf_cmaxlen(i, j))
         }
       end

       # test2. 速さ
       def test_efficiency
         t = realtime do
           @huge_data.map { |i, j|
             cmaxlen(i, j)
           }
         end
         assert(t < @time_limit, 'TIMEOUT!')
       end
     end

     # Unit Test の実行
     RUNIT::CUI::TestRunner.run(TestUnit.suite)

研究問題

ウバのオリジナルの問題では、入力のサイズは

      入力: 0 以上 100,000,000 以下の整数 i, j

となっている。

あなたの書いたプログラムはこれだけ大きな入力を与えても、満足の行く時間で答えが求まるだろうか。求まらなかったとしたら、それは何が原因で、何を改良すればいいだろう?

おまけ

2 つのプログラムの同一仕様検査の難しさ

読者の中には、

 def same?(f, g)
   if (f と g が同じプログラム)
     return true
   else
     return false
   end
 end

のようなプログラムを作れるのではないか、と想像したことがある人もいるだろう。しかし、残念ながらこのようなプログラムを書くことは難しいし、仮に書けたとしても、same?(f, g) が止まらないような (f, g) が存在することが Turing 機械の議論から導ける。 (興味のある人は調べてみよう。)

では、全ての f と g について same? を作るのではなく、

 def try_same?(f, g)
   if (f と g が "簡単な"アルゴリズムでできている)
     same?(f, g)
   else
     raise "あきらめます"
   end
 end

というプログラムなら作れるだろうか。そこで、 3 n + 1 問題について考えてみる。

 def collatz(n)
   while n != 1
     if n % 2 == 1
       n = 3 * n + 1
     else
       n = n / 2
     end
   end
   n
 end

 def one(n)
   1
 end

collatz は while と if と簡単な四則演算のみから成り立っている。そこで、

 same?(collatz, one)

は成り立つだろうか?ということを考えてみよう。しかし、3 n + 1 問題は(前に述べたように)昔から知られた数学上の難問であり、 same?(collatz, one) が true または false を返したということは、この難問の証明を与えたことに他ならない。仮にアルゴリズムが簡単であっても二つのプログラムの同一性を調べるのは難しいのである。

もし、あなたが仕事でプログラムを書いていて、上司から「簡単なプログラムのはずなのに、仕様を満たしているかどうかがどうしてわからないのかね?」と怒られたときには、「作ったプログラムが仕様を満たしているかどうかを確かめることは、仕様が簡単かどうか、あるいは、プログラムが簡単であるかどうかとは無関係なんですよ」と答えることができるだろう。

停止性判定の難しさ

同じ様な発想で、プログラムが停止するかどうかの判定が難しいこともわかる。

 def collatz(n)
   while n != 1
     if n % 2 == 1
       n = 3 * n + 1
     else
       n = n / 2
     end
   end
   n
 end

collatz が全ての n に対して計算が止まるためには、 while ループを脱出しなければならない。つまり、いつかは n が 1 にならなければならない。しかし、どんな入力 n に対しても collatz が止まるかどうかを調べることは、結局、難問 3n+1 問題の証明を与えることに他ならない。

もし、あなたが仕事でプログラムを書いていて、上司から「簡単なプログラムのはずなのに、どうして停止するかどうかがわからないのかね?」と怒られたときには、「作ったプログラムが停止するかどうかを確かめることは、プログラムが簡単であるかどうかとは無関係なんですよ」と答えることができるだろう。

停止性判定の難しさはTuring 機械を用いることにより精密に議論できる。 http://en.wikipedia.org/wiki/Halting_problem

ruby 1.8 の再帰関数のパフォーマンス

(注意: この節を読むとパズルを解く際の試行錯誤の楽しみが損なわれるおそれがある)

ruby 1.8 では、再帰関数のパフォーマンスは再帰を用いない関数と比べると悪いようだ。階乗を計算する 2 つの関数について、実験してみた結果は以下の通り:

 require 'benchmark'
 include Benchmark

 def fact(n)
   result = 1
   n.times do |i|
     result *= (i + 1)
   end
   return result
 end

 def fact_rec(n)
   if n == 0
     return 1
   else
     return n * fact_rec(n - 1)   # 帰納段階
   end
 # not reached
 end

 def test(test_num)
   t1 = realtime do
     fact(test_num)
   end

   t2 = realtime do
     fact_rec(test_num)
   end

   return [t1, t2]
 end

 # result(sec)
 #  test_num  fact      fact_rec
 #  100       0.000422  0.002412
 #  200       0.000893  0.005157
 #  300       0.001407  0.014468
 #  400       0.002067  0.016710
 #  500       0.015325  --------
 # test_num = 500 で SystemStackError: stack level too deep

こういう時に再帰関数の効率をあげるテクニックとして、「末尾再帰(tail recursion)」という方法がある。末尾再帰とは一言で言うと帰納段階に現れる return 文を工夫して自分自身の呼び出しにすることである。

 def fact_tail_rec(n, buf=1)
   if n == 0
     return buf
   else
     return fact_tail_rec(n - 1, n * buf)  # 帰納段階
   end
   # not reached
 end

 # result(sec)
 #  test_num  fact      fact_rec  fact_tail_rec
 #  100       0.000422  0.002412  0.002008
 #  200       0.000893  0.005157  0.006876
 #  300       0.001407  0.014468  0.016565
 #  400       0.002067  0.016710  0.025663
 #  500       0.015325  --------  0.021403
 #  600       0.020847  --------  0.041130
 #  700       0.005984  --------  0.065781
 #  800       0.021661  --------  --------
 # test_num = 800 で fact_tail_rec も SystemStackError: stack level too deep

末尾再帰を用いると、用いないときよりも大きな数について計算できるが、やはり再帰の回数には限界があり、SystemStackError になってしまう。

今回のパズル 3n+1 問題も、問題が再帰的なので再帰的にプログラムを書く方が素直に書ける(と私は思う)のだが、スタックが溢れるために n が大きくなると実行できなくなってしまう。

ruby に対する末尾再帰の最適化は ruby そのものをもてあそぶ人の興味の対象になっており、今後のバージョンによっては速度の改善や SystemStackError が起きにくくなるような改善が施されるかもしれない。 (と期待する)

ちなみに python 2.3 で末尾再帰版 fact を計算したところ、 n = 900 までは計算でき、 n = 1000 でスタックが溢れた。

 # python における末尾再帰版 fact
 def fact_tail_rec(n, buf=1):
   if n == 0:
     return buf
   else:
     return fact_tail_rec(n-1, buf * n)

再帰関数を効率良く計算できる関数型言語では、 n = 10000 でも計算できる。 (オブジェクト指向言語とは言語仕様と実装が大きく異なるので、この比較は公平ではない。)

 -- Haskell における末尾再帰版 fact
 fact n = fact_ n buf
   where
     fact_ n buf =
       if n == 0
       then buf
       else fact_ (n-1) (n * buf)

なお、テストに用いた環境は

Mac OS X 10.3.6
プロセッサ 1.33GHz PowerPC G4
メモリ 256MB

であり、別の環境では結果が異なってくるだろう。

最後に

ウバに登録されている約 2000 問のプログラムパズルがあなたの挑戦を待ち受けている。

筆者は、Tanaka 氏の日記経由でウバの面白さを知った。

解答例

Ruby プログラミング入門 (原信一郎著) p. 202 「オブジェクト指向フィボナッチ数列!?」より、フィボナッチ数列を計算する例の 3n+1 版。

 def (CollatzLen = {1 => 1}).[](n)
   super || ( if n % 2 == 1
                m = 3 * n + 1
              else
                m = n / 2
              end
              CollatzLen[n] = CollatzLen[m] + 1)
 end
 def cmaxlen(i, j)
   (i..j).map {|n| CollatzLen[n]}.max
 end

これは Ruby のオブジェクト指向言語の特徴(特異メソッド)を使った面白いコードで、同じ計算を繰り返さない工夫がされている。しかし、再帰的なプログラムなので、大きな n に対して計算するとスタックが溢れるという問題がある。

この CollatzLen について少し補足しよう。CollatzLen の目的は、計算した結果をできるだけ覚えておいて、再度計算することを防ぐというものである。たとえば、3n+1 問題で n = 4 について

 4 → 2 → 1

の計算に着目すると、n=6 についての計算の途中で

 6 → 3 → 10 → 5 → 16 → 8 → 4

4 が再び現れて、その列の続きは n = 4 の計算と同じことになる。そこで、n を key、 n に対するサイクル長を value とするような Hash を作り、 key に対する value が得られたら計算を止めることにすれば、同じ計算をしなくて済む分効率が上がるはずだ。(その代わりにメモリを必要とする)

CollatzLen は定数で Hash である。CollatzLen の key は 3n+1 問題の n で、 CollatzLen の value は key n に対するサイクル長を指すものとしている。 CollatzLen は最初は {1 => 1} なのだが、CollatzLen[n] を評価する際に CollatzLen[n] が nil のときに限り CollatzLen[n] を過去に行った計算 CollatzLen[m] を使うようにしている。

今回提出したパズルでプログラムの効率を上げ、かつ大きな数字に対しても cmaxlen を計算するためには、

Ruby で再帰的な問題を解くには、どの方法が良いか
3n+1 問題に特有の性質を使って、どうやって効率を上げるか

について取り組む必要がある。

バックナンバー