ブルートフォース癖

ガウスがちっちゃい頃の逸話で、先生が算数の時間に、生徒達に１から100までの合計を計算させて、その間に雑用か何かを片付けようとしてたら、ガウスが101 * 50 = 5050と瞬時に答えをだしたので先生が驚いたってのを聞いたことがある。

プログラマたるもの大いに見習わなきゃならんなと常々思っていたけど、最近、Project Euler を始めてみて、かなり自分にブルートフォース癖があるのに気づいて反省。

例えば Problem 169 の以下のような問題がある（それほど難しくないと言われている）。

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.

For example, f(10)=5 since there are five different ways to express 10:

    1 + 1 + 8
    1 + 1 + 4 + 4
    1 + 1 + 2 + 2 + 4
    2 + 4 + 4
    2 + 8

What is f(10^25)?

これを解くのに、可能な手をそれぞれ試行してからルールに合わないものをふるい落とすなんてやり方（試行回数を減らす工夫はしてるつもりだけど）だと、いつまで経っても終わらない。

途中の計算結果をキャッシュでもしてみようかとも思ったけど、もうそんなのは止めておこうと思い至り、初めから再考する事にした。

で、改めてよく考えてみると、「1」を使わない部分の合計を x としたとき、n が奇数ならば必ず「x + 1」の形になる。ここで x 部分のバリーション数は f (n div 2) で、これが即ち f(n)と等しいということが分かる。

次に n が偶数のときを考えると、表記法のバリエーションは「x」か「x + 1 + 1」のいずれかのパターンに分類され、前者の表記法の数は f (n div 2) で、後者は f ((n-2) div 2)となるから、f (n) = f (n div 2) + f ((n-2) div 2)となる。

ここまでを問題文にある f(0)=1 を考慮してまとめると以下の様になる。

n = 0     ⇒ f(n) = 1
n ∈ odd  ⇒ f(n) = f(n')
n ∈ even ⇒ f(n) = f(n') + f(n'-1)
※ n' = n div 2

うん、本当は、この辺りまで公式化してから、さて実装はどうしようかと考えるべきなんだよなあ。

改めて「分析」ってやっぱ大事だなと思う。実際の開発現場では、重量プロセスで必死になって大量にドキュメントを書いてるくせして、「分析」が全然なされてなされてなかったりするし、下手糞なアジャイルもどきの開発でも、「後でなんぼでもリファクタできるから」的なノリで実装を進めて、変な方向にはまり込んで引き返せなくなったりもする。ちゃんと分析しようやと。

話を戻すと、実は上の公式をそのまんま実装しても、二重再帰が含まれてるのでものすごく遅い。だから、ここからが実装の話になるけど、これを防ぐには、一回の f(n) の計算で f(n) とf(n-1)の両方を返すようにすれば良い。以下の表を観察すると規則性が見えてくる。

	1	2	3	4	5	6	7	8	9	10	11	12
f(n)	1	2	1	3	2	3	1	4	3	5	2	5
f(n-1)	1	1	2	1	3	2	3	1	4	3	5	2

n が奇数のとき f(n-1) は f(n')+f(n'-1) になっていて、偶数ならば f(n-1) は f(n'-1)になっている。例えば、f(9-1)=f(8)=f(4)+f(4-1)で、f(10-1)=f(9)=f(5)+f(5-1)。ここまで分かれば、f(n) と f(n-1)を同時に返して末尾再帰させるコードを簡単に書ける。自分書いた4行ばかりの Haskellコードは、実行すると瞬時に正答が算出された（二重再帰版は未だに帰ってこない）。