CodeIQというサイトにて結城浩先生が「マヨイドーロ問題」というものを出題されました。
※現在は残念ながら挑戦受付は終了しています。

挑戦して無事初回100点を取ったので考え方と実際のコードを公開します。
なお、本記事は手も足も出なかった人に対して、あんまり数学的にキレイじゃないけど1歩1歩進んだらこうなってどうにかなったよ、ということを伝える目的で書いています。

問題内容

記載していいのかわからないためここでは控えます。

回答に至る道筋

問題の場合分け

最初のスタート時は「AB区間」に「右向き」でいて「残りn回曲がれる」状態です。

この後、B地点で曲がった場合は「AB区間」に「左向き」でいて「残り(n - 1)回曲がれる」状態へと遷移します。
一方でB地点で曲がらなかった場合は「BC区間」に「右向き」でいて「残りn回曲がれる」状態へと遷移します。
これら2つの事象は漏れもダブりもない事象です。*1

スタート時からこのどちらかの事象が必ず起き、かつそれらの事象は重複して起きることがありません。
そのため「スタート地点からYへと出る曲がり方」は「スタート地点からBで曲がってAB地点左向き、残りn - 1回曲がれる状態からYへと出る曲がり方」と「スタート地点からBで曲がらず、BC地点右向き、残りn回曲がれる状態からYへと出る曲がり方」の和であることがわかります。「地点」と「向き」と「残り回数」という状態、そして「次に曲がるかどうか」という観点から解いていきます。

ここである関数を考えます。地点2通り(AB区間・BC区間)と向き2通り(右向き・左向き)の組み合わせ、4通りの位置情報についてそれぞれ、 曲がれる回数nを引数にとり、そこからYから出る曲がり方の数を返す 関数を考えます。

場合分けと関数

具体的には以下の4つの問いに答えることができる関数について考えます。

「AB区間」に「右向き」でいるとして、曲がれる回数がnだった場合、Yから出る曲がり方は何通り？
「AB区間」に「左向き」でいるとして、曲がれる回数がnだった場合、Yから出る曲がり方は何通り？
「BC区間」に「右向き」でいるとして、曲がれる回数がnだった場合、Yから出る曲がり方は何通り？
「BC区間」に「左向き」でいるとして、曲がれる回数がnだった場合、Yから出る曲がり方は何通り？

関数名は上から順に abr, abl, bcr, bclとします。区間名(ab or bc)と向き(r or l)の合成です。

例えば、最初の状態は「AB区間」に「右向き」でいて「残りn回曲がれる」状態であるため、「Yから出る曲がり方」はabr(n)となりますね。

この後、B地点で曲がった場合は「AB区間」に「左向き」でいて「残り(n - 1)回曲がれる」状態へと遷移します。一方でB地点で曲がらなかった場合は「BC区間」に「右向き」でいて「残りn回曲がれる」状態へと遷移します。
これら2つの事象は漏れもダブりもない事象です

上記の記述から abr(n) の定義を以下のように書くことが可能です。

def abr(n)
  bcr(n) + abl(n - 1)
end

おっと、これは「もう曲がれないとき」を考慮しておいたほうがよさそうですね。
abrは「右向き」のときの関数なのでn < 1が成立するならば必ずZから出ることになります。
そうすると0を返すのが正しいですね。

def abr(n)
  n < 1 ? 0 : bcr(n) + abl(n - 1)
end

これを同じように「次のA, B, C地点で曲がるかどうか」という場合分けで関数 abl, bcr, bclも定義していきます。

def abl(n)
  n < 1 ? 1 : 1 + abr(n - 1) # 曲がらなかったときYに到達するので1
end

def bcr(n)
  n < 1 ? 0 : 0 + bcl(n - 1) # 曲がらなかったときZに到達するので0
end

def bcl(n)
  n < 1 ? 1 : abl(n) + bcr(n - 1)
end

できました！これで完成です。

求めるべき答えはabr(n)ですので標準入力から受け取ったものを渡してやれば答えが出ます。実際にPDFに書いてあるテストケースは全て通ります。やったー！

高速化

って結城先生の問題がこれで終わるわけがありませんね。
例えばn = 100とかで解いてみると返ってきません。
高速化をはかりましょう。

何個かnを具体的にいれて確かめて見ればわかりますが、関数を同じ数字で呼び出す回数が多くなります。
こういうときの高速化はメモ化が有効そうな気がしてきます。

メモ化とは、「特定の引数をもらったときの初回の計算結果を覚えておき、2回目以降の実行時には実際には評価しないようにすること」です。
(参考: メモ化 - Wikipedia )
Rubyでは||=で代入するとキレイにかけます。

memo = []
def factorial(n)
  return 1 if n < 1
  memo[n] ||= n * factorial(n - 1)
end

メモ化を適用するには4つの関数は多いので関数を絞りましょう。

関数bcrのインライン化

関数bcrがn < 1である場合0、そうでない場合にbcl(n - 1)ときれいに書き換えられるのでbcrをインライン化します。
関数のインライン化とかは結城先生のリファクタリング入門とか見るといいんじゃないでしょうか(露骨な宣伝)

def abr(n)
  return 0 if n < 0
  n < 1 ? 0 : bcl(n - 1) + abl(n - 1)
end

def abl(n)
  return 0 if n < 0
  n < 1 ? 1 : 1 + abr(n - 1)
end

def bcl(n)
  return 0 if n < 0
  n < 1 ? 1 : abl(n) + bcl(n - 2)
end

bcl(n - 2)というnが突然マイナスになり得るパターンが出てきたのでif n < 0の条件を入れています。

関数abrのインライン化

上と同様に、今度はabrを置き換えました。
置き換え対象は、インライン化が簡単そうだったのでabrにしています。

def abl(n)
  return 0 if n < 0
  n < 1 ? 1 : 1 + bcl(n - 2) + abl(n - 2)
end

def bcl(n)
  return 0 if n < 0
  n < 1 ? 1 : abl(n) + bcl(n - 2)
end

特に特別なことはやっていません。

再帰処理を展開

nが十分に大きいときbcl(n)は以下のように展開されていきます。

bcl(n) = abl(n) + bcl(n - 2)
bcl(n) = abl(n) + abl(n - 2) + bcl(n - 4)
bcl(n) = abl(n) + abl(n - 2) + abl(n - 4) + bcl(n - 6) ...

すなわちnから2ずつ引いて関数ablが呼び出されています。

この数列をnumsとすると*2以下のように展開できます。

def abl(n)
  return 0 if n < 0
  n < 1 ? 1 : 1 + bcl(n - 2) + abl(n - 2)
end

def bcl(n)
  return 0 if n < 0
  return 1 if n < 1
  nums(n).map { |e| abl(e) }.inject(:+)
end

def nums(n)
  ((n + 2) / 2).times.map { |e| n - e * 2 }
end

メモ化 x 2

まあ2つくらいならメモ化しておいてもいいでしょう(妥協)
これ以上、式変形するとそろそろ変になりそうなので……。

クラス化しておしまいにしておきます。

module CodeIQ
  module HYuki
    class Mayoi
      def solve(n)
        @memo_abl = [1]
        @memo_bcl = [1]
        return 0 if n < 1
        bcl(n - 1) + abl(n - 1)
      end

      def abl(n)
        return 0 if n < 0
        @memo_abl[n] ||= 1 + bcl(n - 2) + abl(n - 2)
      end

      def bcl(n)
        return 0 if n < 0
        @memo_bcl[n] ||= nums(n).map { |e| abl(e) }.inject(:+)
      end

      def nums(n)
        ((n + 2) / 2).times.map do |e|
          n - e * 2
        end
      end
    end
  end
end

puts CodeIQ::HYuki::Mayoi.new.solve(gets.to_i)

途中から雑になってしまった……。

*1:こういうのなんていうんだっけ……?

*2:いい名前が思いつかなかった

Smoky God Express

マヨイドーロ問題感想