« 20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』 | トップページ | 「ルート・パワー問題」の高度じゃないコード »

2015年12月21日 (月)

「マヨイドーロ問題」の高度じゃないコード

最近、CodeIQというサイトに嵌ってます。出題される問題を、好きなプログラム言語で解くコードを作成して挑戦するというものです。ただ、ほとんどの問題は、その問題やコードについてブログ等で公開することは禁じられているんですが、時々、挑戦期間終了後に限り、それが許可された問題があります。「マヨイドーロ問題」はそのような問題の1つです。

結城浩の「マヨイドーロ問題」解説

今回の問題は自動採点といって、使用言語を選択してコードを入力すれば、サーバー側でコンパイル・実行し、自動的にテスト数値が入力されそれに対する出力をチェックし、全部のテスト数値について答えが合っていたら正解となります。まずは、いつも挑戦に使っているC言語で書いてみました。今回の問題には、出題されるテスト数値の上限が書かれていないので、結果がどれぐらいの値になるか不明ですが、今までの例だと、32bit整数だとオーバーフローして、64bit整数だとOKなことが多かったので、64bit整数でコーディングしました。

ところが、100までの数値では正解を出せましたが、その次のいきなり10倍になった1000であえなく死亡。しかも、その後にはラスボス2015というとんでもない数値の化け物が控えていました。仕方ないので、32bit符号なし整数を連結して多倍長計算するようにコーディングしました。といっても、必要だったのは、連結整数同士の加算と10進表示の2つぐらいです。

さらに、一度計算した値はメモしておき、同じ計算を何度もしないようにしないとすぐタイムオーバーとなります。私のやり方では、1つの値に対して、位置2×方向2=合計4通りのメモが必要なので、メモだけで最低2015×4個分の連結整数が必要です。また、連結整数も32bit符号なし整数をいくつ連結しないとダメなのか不明なので、とりあえず、最大入力値5000にして32bit符号なし整数を100個まで連結できるようにして提出しました。でも、これだと、メモだけでに5000×4×100×4バイトで8MBも必要なことになり、他も合わせると10MBもメモリーを使ってしまいます。ところが、実際に2015の入力で必要な連結数は44個だったので、最大入力値と連結数をそれぞれ半分の2500・50にしたものを以下に示します。まぁ、それでも、4MB以上食っているわけですが・・・。

その後、Rubyなら、こんな面倒なことをしなくてもいいと知り、付け焼刃で勉強しつつ作りました。終わってみると、予想通り圧倒的にRubyを使って挑戦し正解した方が多かったようで、既に多くの素晴らしいコードが公開されているので、私のお粗末なコードは恥ずかしくて公開できません。じゃあ、上のCのコードは恥ずかしくないのかと聞かれれば、やっぱり恥ずかしいのは同じですが・・・。

なお、正解した人に提示されるという「解説編PDF」には、挑戦期間が終了するまで気が付きませんでした。なので、そのPDFや他の方の話に出てくる「フィボナッチ数列」であることなど思いもしなかったです。ていうか、「フィボナッチ数列」って名前だけ聞いたことあるけど、内容は全く知らなかったので、そうであることに気付けるはずもないですね。

ということで、ウィキペディアでフィボナッチ数を調べてみました。なるほど、マヨイドーロ問題の答えはフィボナッチ数列の奇数番目から1を引いたものになっているということですね。そして、それを利用すれば、メモなど使わずとも、単なるループで処理できます。

話を簡単にするため、オーバーフローを考えない式で示してみます。まず、0番目、1番目のフィボナッチ数を d0, d1 とします。初期値は共に1なので、d0=d1=1; で初期化できます。次にループの中身の処理ですが、n番目, n+1番目のフィボナッチ数を d0, d1 とすれば、n+1番目, n+2番目への更新は、Rubyでは {d0,d1=d1,d0+d1} と書けばいいようですが、Cだと {tmp=d0; d0=d1; d1+=tmp;} のように tmp に一度入れるか、{d0=(d1+=d0)-d0;} または括弧を取って1文字短くするなら、{d0=-d0+d1+=d0;} のようにする必要があります。ここで、必要なのは奇数番目だけなので、2回分の更新をまとめてやってみます。n番目, n+1番目のフィボナッチ数を d0, d1 とすれば、2回更新した n+2番目、n+3番目のフィボナッチ数は、d0+d1, d1+(d0+d1) となります。つまり、{d0+=d1; d1+=d0;} ということになり、まとめると {d1+=d0+=d1;} とすっきりします。最後に、得られた d1 から1を引いたものが求める答えとなります。残念ながらCだと、多倍長計算が必要なので {d1+=d0+=d1;} とはいきませんが、これを利用して、上記のソースを書き直したものがこれです。連結整数から1を引く処理を追加してます。

もし、Rubyでコードgolf(少しでも短いコードで書く競争)をするなら、ループの中は、1つ毎に更新の場合は {a,b=b,a+b} や {a=-a+b+=a}、2つ毎の更新の場合は {b+=a+=b} が最短なのかな?いずれにせよ、上記のCと同じことを全部で50文字足らずで実現できるわけですからすごいことです。

|

« 20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』 | トップページ | 「ルート・パワー問題」の高度じゃないコード »

コメント

後から考えると、入力される数値が奇数の場合と、それより1増えた偶数の場合は同じ答えになるので、初めのコードでもメモの数は半分でいいわけですね。やっぱり、無駄多すぎ・・・。

投稿: Yasu.Hara. | 2015年12月21日 (月) 09時48分

ちなみに、私の頭では、「マヨイドーロ問題」のRubyのコードgolfはこんな感じです。

p~0.step(gets.to_i-a=b=1,2){b+=a+=b}+b

または

p~0.step(gets.to_i-a=1,b=2){b+=a+=b}+a

フィボナッチ数列の初期値が1つずれているのと、最終的に使用する変数が異なるだけで、やっていることは同じです。

投稿: Yasu.Hara. | 2015年12月21日 (月) 11時41分

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/62908949

この記事へのトラックバック一覧です: 「マヨイドーロ問題」の高度じゃないコード:

« 20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』 | トップページ | 「ルート・パワー問題」の高度じゃないコード »