どうも、小野氏です。

今週はさぼらずに更新できました。

ただプログラミングをあまりやっていない影響か、普段より実装に時間がかかってしまいました。

週1のプログラミングだと成長しないなと身をもって実感しております。

さて、今回もプログラム脳を鍛える数学パズルの問題を解いていきたいと思います。

今週は本書のQ14についてRubyで実装したので、そちらについて紹介いたします。

Q14 W杯出場国しりとり

問題

2014年W杯出場国でしりとりを行うとき、最も長く続けられる場合の使用国数を答えよ(ただし、どの国名も一度しか使えないこととする)

書くのがめんどくさいのでW杯出場国の記載は省きます。気になる方はWikiを確認してください。

探索処理なので再帰処理を使いますが、再帰の変数代入のところで躓いてしまいました。

かなり初歩的なミスですが、デバッグまでしたので紹介します。

(逆に言うとデバッグしないと原因がわからなかったです。。。)

自分で考えた後、回答を見ながら修正したものが以下のものです。

簡単にアルゴリズムを解説いたします。

国名の配列と、すでに国名を使用したかの状態を格納する配列を宣言
- 配列自体を破壊的に書き換えていく方法もあると思いますが、再帰でそれをやるのが怖かったので今回は回避しました。
国名の冒頭の文字と、国名の最後の文字が一致していることを確認するsearch関数を定義
- 再帰的に探索する前に使用済みのフラグをたて、再帰処理が終わった際にフラグを元に戻している。
  - 再帰処理の中で使った国名については、再帰処理が終われば再度使えるため。
- 探索木の葉ノードである場合loop_countの中身をmax_loop_count変数に格納するため、is_last変数をつかって葉ノードにあたるか確認している
それぞれの国名に対して、search関数を呼び出している。

使用済みのフラグを立てるタイミング・外すタイミングについては、再帰に慣れていないとパっと回答できないような気がします。

今回は、私がトラブルシュートに時間がかかった点について説明いたします。

(アルゴリズムについては、特に一般的な再帰処理以上のことをしていないので解説を省きます)

私がはじめに作成したコードは以下の通りです。

回答のコードと違う点は、loop_count変数のカウントアップのタイミングです。

私のコードはif文の中の処理としてカウントアップしておりますが、回答のコードは関数を呼び出すときにカウントアップをしております。

この処理の違いが、メモリの状態に以下のような差を生みます。

f:id:kugelmulai:20200524175049p:plain

私のコードだと関数を呼び出す前にカウントアップをしているので、正答の場合と比べてloop_count変数が1つ大きくなります。

こちらは1回目の探索時には問題は発生しませんが、2回目以降の探索処理時に問題が発生します。

メモリ上でsearch関数の処理が終わった際、each_with_indexのループの中にもどるので、次の変数(国名)に対して比較処理を行います。

その際のメモリ上のデータを見ると、正答のほうはloop_count変数の値が変わっていないのに対し、私の回答のコードだとloop_count変数の値が大きくなります。

search処理が終わり呼び出し元に戻る際には、探索が進んでいないので、loop_count変数が大きくなるのは誤りです。そのため、正答のコードのように再帰処理を呼び出す際にcount変数を変更するのが正しいです。

メモリの状態を気にしないとできないデバッグだったので時間がかかってしまいましたが、再帰処理は呼び出しと変数のカウントアップを同時にしないと想定外のカウントアップが行われる可能性があることを身をもって理解できました。

私は以下のコードを作成したのちに、どこが間違っているのかがわからずに1時間程度調べておりました。
- そもそもデバッガを使ったのが2年ぶりくらいで、ステップイン等の用語定義を調べるのに時間がかかりました。
問題を解くことに限界を感じてきました。(n回目)
- アルゴリズムを勉強しないと。。。