「マヨイドーロ問題」とは
タイトルの通りですが、CodeIQ「マヨイドーロ問題」の解答期限が過ぎたということで、提出コードを公開してみたいと思います。この問題は「数学ガール」シリーズでおなじみ(?)の結城浩先生による出題で、正解者のうち10名に最新刊『数学ガールの秘密ノート／ベクトルの真実』がプレゼントされるという企画でした。ものがもらえるかもしれないという期待と、先生の知名度および高邁なお人柄が影響してか、挑戦人数が700名を超えるというすごい事態になっていました。
さて実際の問題ですが、どうやら後日CodeIQMagazineあたりで、解説記事とともに公開されるようなので、ここでは一応伏しておきます。公開後覚えていればリンクを張り付けておきます。まあ広大なネットの海を探せば見つかるとか見つからないとか……。
2015/12/24追記:
結城先生ご本人による解説記事が公開されていました。というと今さっき知ったみたいですが、実は前に知っていたものの、ここに追記するのを忘れていたという……。
https://codeiq.jp/magazine/2015/12/35521/
提出コード
以下はわたしが実際に提出し、無事合格となったソースコードです。使用言語はRuby。たぶん一発合格だったはずです。
N = gets.to_i
# インデックスが現在地と方向、要素が次の地点となる配列
# (a, b , c) = (0, 1, 2)
# (y, z) = (3, 4)
# (left, right) = (0, 1)
@table = [
[3, 1],
[0, 2],
[1, 4]
]
# 現在地s、方向d、残り回数n : @memo[s][d][n] = f(s, d, n)
@memo = Array.new(5){Array.new(2){Array.new(N + 1)}}
# yにたどり着くルートの総数Pを返す
# s : 現在地(0, 1, 2, 3, 4)
# d : 方向(0, 1)
# n : 方向を変えることができる回数(0..Nを満たす整数)
def f(s, d, n)
@memo[s][d][n] ||= case
when s == 3 then 1 # yにたどり着いた
when s == 4 then 0 # zにたどり着いた
when n == 0 then f(@table[s][d], d, n) # 方向を変えられない場合はそのまま進む
else f(@table[s][d], d, n) + f(@table[s][1 - d], (1 - d), n - 1) # そのまま進む + 方向を変えて進む
end
end
# == main ==
# スタート地点 : 1 (b)
# 方向 : 1 (right)
# 方向を変えることができる回数 : N
p f(1, 1, N)
どうやらフィボナッチ数列や漸化式を利用することが求められていたようですが、これを書いている人は頭からっぽ系男子なためにまったく思いつきませんでした……。そこで再帰(正確にはメモ化再帰)で何とかしています。ただこれも場合によっては悪手で、N=2000程度だから無事合格だったものの、Nの値がもっと大きくなるとstack too deepあたりを起こして、にっちもさっちもいかなくなる可能性があります。動的計画法などを利用して、再帰からふつうのループに書き換えるべきでした。もっとも再帰を使うととてもソースコードがすっきりするので、見栄えは非常に良くなるのですが……。
それはともかくわたしの提出コードで行っていることは実に単純。「今どこにいるのか」「どちらを向いているのか」「あと何回方向転換できるのか」。もとめる道のりの総数Pはこの3つのファクターによって決まります。よってこれらを変数とする関数(returnはもちろんP)を作ってやり、動点の動き方に合わせて、関数を組み合わせてやるだけです。ただしそのまま組み合わせるだけだと、単純な再帰になってしまい、非常に効率が悪いというか、同じ計算を何度もしてしまいます。そこで1度計算した値を覚えておくことで、効率化を図っています。
こんな記事よりも……
というわけで、わたしの方法論はさほどほめられたものではありません。とりあえず解けたというだけです。それよりももっとよいコードを参加者の皆さんが公開しており、ありがいことに出題者の結城先生自らそれをまとめてくださっています。そちらをご参考のほどに。