CodeIQでの結城浩さんのマヨイドーロ問題。自分のCodeを公開してみる。

　久しぶりのCodeIQでの結城浩さんの問題でワクワクドキドキ楽しめました。それにしてもマヨイドーロ問題，これまでの問題って確か英語で書かれてたような。今回は日本語（カタカナ表記）なんだけど何故かなぁ。

毎度の事ですが，お気楽極楽で，組合せや順列も簡単なrubyで遊びました。

最初に組んだのがこんな感じです。

rtl=["Y","A","B","C","Z","X"]
n=3

def mayoidoro(rl,ps,dr,nn)
if (ps==0) or (ps==4)
rl
elsif ps==-1
mayoidoro([rl[0]+[2]],2,1,nn)
else
if nn==0
nxtlst=[]
rl.each{|x|
nxtlst=nxtlst+mayoidoro([x+[ps+dr]],ps+dr,dr,nn)
}
nxtlst
else
nxtlst=[]
rl.each{|x|
nxtlst=nxtlst+mayoidoro([x+[ps+dr]],ps+dr,dr,nn)+mayoidoro([x+[ps-dr]],ps-dr,-dr,nn-1)
}
nxtlst
end
end
end
#while str = STDIN.gets
for i in (1..20)
str=i.to_s
n=str.to_i
po=-1
dirct=1
mlst=[[po]]
ansl=mayoidoro(mlst,po,dirct,n).delete_if{|x| x[-1]==4}
print ansl.size.to_s
end
# 〜------------------------------------ results 21:14:05 u
22772020545414314337637698698625832583676467641771017710

コピペするとインデントが消えちゃいました。分かりにくいかな？でもとってもストレートなプログラムなので、読んでみると面白いかも。

いつものようにファイルからの読み込み？標準入出力ってのがよく分からずに多少戸惑いましたが。

そして当然このストレートな回答だと，時間が溢れるという返答が帰ってきたので数日空けて再度組み直したのがこちら。

...って無い。確か提出したのに。プログラムが無い。もしかしてweb上で適当に打ったのか俺？

少し焦ったけどCodeIQのマイページに行って解答済みの問題の「あなたの解答」で確認！！

def mayoidoro(n)
if n==0
0
elsif n==1
2
else
br=[0,2]
bl=[1,1]
for i in (2..n)
br << 1+br[i-2]+bl[i-1]
bl << 1+br[i-1]+bl[i-2]
end
br[-1]
end
end

while str = STDIN.gets
print mayoidoro(str.to_i).to_s
end

いやぁシンプル。ってかどこにもXもYもZも出てこない。こんなんで良いのか？ってでもね、実直にシミュレートさせると時間足りんわけ。仕方ないから「数学的」に解いた次第。解析して漸化式立てて。

それでもとても面白かった。解読はお任せしましょう。