(2015年までの)odaillyjp blog

イベント参加記録とプログラミング系の雑記

第23回オフラインリアルタイムどう書くにへなちょこな感じで参加しました

『オフラインリアルタイムどう書く』というプログラミング勉強会があります。

オフラインリアルタイムどう書く | 横浜へなちょこプログラミング勉強会

たまに『オフラインリアルタイムどう書く』で過去に出題された問題を家でちまちまと解いていたのですが、第23回にして初めてオフラインリアルタイム(現地)で参加しました。

問題

第23回の問題はこちらです。

くねくね増加列〜 横へな 2014.7.5 問題

どう解いた?

再帰深さ優先探索を使って解こうとしたのですが、間違った再帰の使い方をしていて、時間内に解くことができませんでした。帰宅してから30分ほど時間を使ってコードを書き直して、なんとかサンプルデータをクリアすることができました。私の解答は以下になります。

どう書く# 23 http://nabetani.sakura.ne.jp/hena/ord23sn ...

コードを大雑把に説明します。このコードは問題を解くためのメソッド(solve)、インスタンス変数を初期化するメソッド(init_numbers_field と init_memo)、深さを探索するメソッド(count_depth)で構成されています。メインとなる処理は count_depth メソッドです。count_depth メソッドは「マス目(x, y)から探索を始めたとき、一番長く辿ることができる経路のマス目の数」を返します。例えば、以下の表の一番左上のマス目から探索を始めるとします。

f:id:Shindo_Masaya:20140709234145j:plain:w400

この場合、経路は以下の2つがあります。

  • 経路1(青):「0, 1, 2, 6, 7, 9」
  • 経路2(赤):「0, 1, 2, 5, 7」

f:id:Shindo_Masaya:20140709234235j:plain:w400

経路1が6マスで一番長いので、一番左上のマス目に対して count_depth メソッドを呼び出したときは「6」を返します。この count_depth メソッドをすべてのマス目に対して呼び出してみて、最終的に一番長く辿ることができた経路のマス目の数を返すのが solve メソッドです。

細かいこと

  • クラスを作っておいて、クラスの initialize メソッドに初期化の処理を持っていっても良かったのですが、時間の都合上やっていません。
  • 時間を短縮するためにテストケースを動的に定義しています。(この勉強会によく参加されている方はサンプルデータからテストケースを簡単に作成するスクリプトなどをあらかじめ用意しているそうです。次回は真似しようと思います。)
  • 二次元配列は[x][y]の形で値を取れるようにしたほうがわかりやすいかと思い、transpose メソッドを使いました。([x][y]と[y][x]のどちらがわかりやすい?)
  • 最初は番兵なしで書いていたのですが、if の条件文がややこしくなりましたので、最終的には番兵を使いました。
  • count_depth メソッドはメモ化を実装済みです。

どう失敗した?

最初は今まで辿った経路を配列に格納するような実装をしていました。

どう書く# 23 最初のリビジョン

しかし、再帰処理の中で元の関数に戻るときに配列の中身がリセットされませんので、辿った経路情報が配列に残ってしまい、期待した通りに動いてくれませんでした。失敗でした。再帰を使うときは副作用がないように実装するのが基本ですので、考え方を間違えていました。この間違えさえなければ時間内で解けていたと思います。

感想

初心者、初参加者に優しいイベントでした。久しぶりにピュアなRubyを書くことができて楽しかったです。また参加させていただきます。

備忘録

リアルタイムで解けなかったのは再帰に慣れていなかったからだと思いますので、自戒のために再帰を使うときの注意点を書き留めておきます。

再帰を使うときの注意点

  • 再帰の終了条件を忘れずに実装する
  • 再帰が呼び出されるたびに問題が徐々に単純化されるように実装する
  • 副作用がないように実装する