checkioが意外と楽しい

プログラミング言語は使わないと忘れるので、時間があるときにcheckioというサイトでコーディングの練習？をしています。

checkio.org

PythonとJavaScriptが選べて、課題に挑戦してクリアすると、他の人が同じ課題のために書いたコードが見れて、あ、こんな風に書けば良いのねという勉強になって、何かと楽しい。もちろん？やっているのはPythonの方ね。

最近やったのは、こんな課題。

Ken_m solution of task Making Change https://t.co/86zVgwshS5 via @PlayCheckiO 暇つぶしにやってる。結構楽しい。

— Kem / けむ (@Deutschina) April 6, 2018

金額と硬貨の組み合わせが与えられていて、金額を支払うのに何枚の硬貨を使うのが最小か？というような問題。この手のアルゴリズムの問題をまともに取り組んだことなかったので、結構ドハマりして、ものすごい遅いコードを書いてなんとかクリアして、他の人の書いたコードを試してみたらサクッと動く。それを参考にして、自分なりにもう1回コードを書き直してみたのがリンク先ね。

恥をさらして、このアルゴリズムを理解するまでの苦節を残しておきます。

だいたい、どのコードを見ても金額+1個の箱を用意しているというのは共通していて、入っている数字も、一部Noneを使うか無限大(int('inf')を使っていることを除いて同じ。例えば、12円を1円玉、3円玉、5円玉の組み合わせで支払うと、箱はこんな感じで埋まって、最後の箱に入った4が最小のコインの数としての答えになっている。

箱の中の数字が全体的にはカウントアップされているけど、8とか10みたいに前の箱から数字が減ってるところもあって、多分ここら辺にヒントがあるだろうなと思いつつ、正解として表示された内包表記でおしゃれに書かれたコードを分解して書き直しているうちにようやく理解。

8円の箱を例にすると、この箱に対して1,3,5円を順に当てはめようとしているんだね。

最初は1円。ここに1円を入れるということは、前のステップで7円地点にいたことになる。つまり、8円目を1円玉で払うと7円の時点で使っていた3枚に1枚プラスして4枚目のコインを使うことになる。

次に3円玉を使おうとすると、前のステップは5円だから、5円の時点の1枚プラスさらに1枚なので2が入る。5円玉も同じ要領で3円から1枚の追加で到達できるので同じく2となる。

言い換えると8円に到達するための最小のコイン数は、3円玉+5円玉または5円玉+3円玉の計2枚ということになる。1円玉だと4枚目投入になるのでダメ。というようなことを12円まで繰り返すと、問の答え(4枚)が得られるわけだね。

と、ここまで書いて、これって昔ちろっとかじった最短距離を求める問題に似ている、というか同じだねと気づく。

ということで、ボケ防止(早いかw)に時々取り組もうと思ってます。

エレガントな問題解決 ―柔軟な発想を引き出すセンスと技

アルゴリズムパズル ―プログラマのための数学パズル入門