Project Euler Problem 16 - 20

Project Euler Problem 11 - 15

Project Euler Problem 1 - 10

ノイマンの自然数の生成の話

もう一発小ネタです。

#数学の問題 #プログラミング
ノイマンの方法で非負整数を作る。
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
…
あなたの好きなプログラミング言語で作ってみよう！

— 結城浩 (@hyuki) May 17, 2016

これがなかなか手こずりました。
いや、アルゴリズムが、って意味じゃなくって計算速度がなかなか上がらんキッツい問題だな、と言う意味です。

さて、これは定義上は、見かけはビックリするんですが、実は実装的にはPythonのrange関数(あるいはSchemeのSRFI-1のiota)の再実装みたいなモンです。
つまり、入力nに対して何を返すのか、と言うと実は

1を入力 -> [0]を返す
2を入力 -> [0, 1]を返す
3を入力 -> [0, 1, 2]を返す

ってのと全く同じ事をしてるんですね。ただ、最初に0を[]と定義してるだけ、なんで仕組みは簡単なんです。
仮に、Schemeでこういう、ちょっとダウングレードなカンジのrangeなりiotaを実装するのは鼻クソでしょう。





ところが、です。
これが0を空リスト、と定義したらちと厄介な事になる。





末尾再帰で書いてるんですが、問題に書かれてるn = 0〜3付近の数ならイイんですが、一方、nが10、20、30と増えていくと、計算がどんどん時間かかっていって、100辺りになると終わらないんですね〜。
ロジック的にはどっちも同じなのに計算時間が物凄くかかる、ってのは、後者は空リストのconsを生成してるだけなんだけど、それで膨大な、恐らくヒープを消費してニッチもサッチもいかなくなってくる、って事です。要するに巨大なガベージを生成してるに他なりません。

実は最初は、遅延評価で書けばどうなんだ、とか思って書いてたんですが、これもnが増大するととんでもない事になっていきます。






多分「定義のクールさ」って意味ではこの遅延評価版が一番カッコイイでしょう。見た目も綺麗ですし。マトモに定義通りに返してくれますし。






ところがさすがの遅延評価版でもnが100とかなると計算が終わりません。やはりどっかで大量のconsを扱うのが大変になるんですね〜。

さて、だったらメモ化はどうだ、って話になるんですが。
通常の高階関数のメモ化を利用して・・・ってのはこの場合は上手くないんです。
基本的に、n = 100を計算する時、n = 100の答えがあったらそいつをハッシュから持ってくる、ってのがメモ化の極意なんですが、生憎、フツーに実装したら今回のような「n = 100の状態を計算する為にはn = 99が必要」のケースだと上手く計算を省略してくれないんですよね。
理想的には再帰的にnを探ってくウチに得た値を利用して計算を行う、と言うちょっとした手動的な最適化が施されてないと、結局毎回新たな値を与える度にn=0まで到達してしまう。
今回のノイマンのモデルだと、どっちにせよnは順番に並んでますし、例えばn = 10を何の情報も無い状態で計算した際にn = 0〜10までのハッシュを全部記録して、n=11の計算の際にn=10「だけ」利用すれば11がすぐ得られる、と言う最適化を施しておいた方が良いわけです。
また、n=11まで計算した後で、n=15を計算するとn=12〜14までの情報は無いわけですが、ハッシュを手繰っていって、n=11の値が見つかった際にそこから計算をスタートしてn=12〜14までをハッシュに埋めつつn=15を返す、ってカタチにしておけば、0まで戻る無駄は省けるわけです。






今回はSRFI-69のハッシュテーブルを利用しています。
ローカル関数のgetはnが与えられた時、nに対応するvalueがハッシュ内にあるかどうか検索します。nが見つからなかった時にはn-1を検索、それでも見つからない場合は・・・と小さいキーを順次検索していって、valueが見つかった時、そのキーを返します。
ローカル関数putは逆に、あるキーからnに向けて計算した数値を逐次ハッシュに記録していって、キーがnと同じになった時にvalueを返して脱出します。
この2つのローカル関数で、ノイマンの定義を最適化するように試みてるんですが・・・・・・。
それでもやっぱn=100とかだと計算時間かかりすぎて、っつーかやっぱどうもヒープ食いつぶして上手い具合にいかないですねぇ。
ハッキリ言って、この問題は、「計算スピードの省略」じゃどうにもならなくって、どっちかっつーとメモリ容量との戦いの模様です。
なかなかconsは手強いですよ。

ズンドコキヨシ with Python

小ネタです。

Javaの講義、試験が「自作関数を作り記述しなさい」って問題だったから
「ズン」「ドコ」のいずれかをランダムで出力し続けて「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ！」って出力した後終了って関数作ったら満点で単位貰ってた

— てくも (@kumiromilk) March 9, 2016

クソ、面白いネタなんだけど、知らんかった(笑)。
何せ、3月初頭までパソコン壊れてたんで、知る機会が無かったんですよねぇ。残念。

さて、ちと問題を読み替えてみます。
単純に確率$p=0.5$で出る「ドコ」を成功、「ズン」を失敗として捉えると「ズンズンズンズンドコ」と言う文字列が出現する確率は

失敗×失敗×失敗×失敗×成功 = 0.5×0.5×0.5×0.5×0.5 = 3.125%

になります。そしてこの文字列が出現した「後」に「キ・ヨ・シ!」を繋げてやれば良い。
なお、問題の要請としては、例えば一回「失敗」が多い

ズンズンズンズンズンドコ

の後でも「キ・ヨ・シ!」が出ても良い模様です。
つまり、この場合、文字列が要素「ズン」と「ドコ」の複合体と見た場合、5つ以上の長さの場合「キ・ヨ・シ!」を繋げる、そうじゃない場合はそのまま出力する、と言う問題として読み替える事が出来るのです。
ちなみに、こういう「失敗を何度か続けた後に成功する」と言う確率分布モデルがあって、それを幾何分布と言います。

$\mathrm{Pr}\left( k\right) :=p\,{\left( 1−p\right) }^{k−1}$

そうすると、要素数自体がこの幾何分布に従う確率変数となって、これで一気に文字列を生成する事が可能となります。

上の写真で言うと、Number of Failures until Success(成功するまでの失敗の数)が4以上の時に「キ・ヨ・シ!」を出力してそれより小さい場合は「キ・ヨ・シ!」を出力しなければ題意が満たせます。
さて、このロジックでプログラムを実装しますが、使用する言語はPython(2.7)、あとは幾何分布に従う確率変数を用いる為、Numpyを利用します。




一応、マイブームなんで、問題の要件とは若干違いますが、ジェネレータで実装しています(笑)。
次のようにして遊びます。






これがなかなか、目的の文字列が出ないんですよね(笑)。
ちなみに、フツーに実装しようが、今回みたいに幾何分布を利用して実装しようが結果は(理論的には)変わりません。
基本的に「ズンズンズンズンドコ キ・ヨ・シ!」が成立する確率は計算上、これ以上に「ズン」の部分が長い文字列の場合と合わせて、実は6.25％しかなく、反面、「ズン」の連続が4回に満たない文字列の出現確率は93.75％もあります。
つまり、このジェネレータを回しても10回に1回は出ない、って事なんですね。