バイバイマンを数えよう【解説2】
本稿はCodeIQで2016年1月28日～同年2月18日に出題された「バイバイマンを数えよう」という問題の解法に関する記事です。
バイバイマンを数えよう【解説2】コードゴルフ編
◆注意
本エントリの解説は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。
◆コードゴルフ編
一般解法編で説明した方法で十分のように思えるかもしれませんが、コードゴルファーにとって十分ではありません。
ここからは、さらに簡潔に書く方法を簡単に説明します。少し数学の知識が必要になりますが、中学～高校1・2年生程度の知識があれば問題ありません。数学が得意な方にとっては回りくどい説明の箇所もありますが、ご了承ください。
◆ゴルファー的解法
ある日(k日目)のバイバイマンの数を、型毎に文字で表します。A, B, C, D, E型のバイバイマンの数を、それぞれa, b, c, d, eとすると、(K+1)日目以降のバイバイマンの数は次のように表すことができます。
足し合わせる計算を繰り返しますから、合計を表す式は常に1次式になっています。ここで、A型のバイバイマンについて注目します。
k日目はa体、(k+1)日目は(d+e)体で、(k+5)日目は(a+2d+2e)体です。a+2d+2e = a+2(d+e)ですから、k日目の数と(k+1)日目の数を2倍した数の和と等しいことがわかります。k日目のA型バイバイマンの数をA[k]とすれば、A[k] = A[k-5] + 2A[k-4]のように表すことができます。
また、他の型のバイバイマンについても同じように考えることができます。
A～E型すべてのバイバイマンの数について、同じ形で表すことができるということは、それらを合計した値も、やはり同じように表すことができます。つまり、k日目のバイバイマンの総数をS[k]とすると、S[k] = S[k-5] + 2S[k-4]のように計算できるということになります。
ただし、このような計算方法は単なる1例であって、さまざまな形に変形することができます。もう少し詳しい説明や上記とは異なる式・解法が気になる方は、以下の解説(挑戦者の方々の記事です)を参照してください。
m.ukaiさん http://d.hatena.ne.jp/m-ukai/20160219
れのあさん http://renor.hatenablog.jp/entry/2016/02/20/210614
eijitさん http://qiita.com/eijit/items/36f1a72f10bd8973ef0d
あいべくうさん http://ibeckuu.hatenablog.com/entry/2016/02/19/011840
angelさん http://ange1.hateblo.jp/entry/2016/02/18/144326
matarilloさん https://gist.github.com/matarillo/8c37857f974fd73fec11
Yasu.Hara.さん http://yas.tea-nifty.com/blog/2016/02/post-8211.html
◆神コード集
お待たせしました！ここからは、言語別の最短コードをご紹介します。全言語通じて最短コードはなんと『29B』！とんでもない記録になりました。
Perl6(29B)
antimon2さん・rotary-oさん
(1 xx 4,*+*-*+*...7e10)>>.say
両者とも全く同じコードでした。rotary-oさんがコードについてコメントを付けてくださっています。 https://ideone.com/Mnq31t
perl6のバージョンによっては、(1,1,1,1)というリストを(1 xx 4)のように書けない場合もあるようですが、CodeIQの採点システム上では問題内容です。「*」を含んだ部分が少しわかりにくいかもしれませんが、これは
(a, b, c, d, a+b-c+d, ... , 7e10)
のように、直前の4要素を用いて再帰的に計算するリストを表しています。先に紹介した計算式とは異なり、S[k] = S[k-4] + S[k-3] – S[k-2] + S[k-1]という形の計算式を用いています。
100日目のバイバイマンは62010148240体ですので、「7e10(70000000000)」という値にはなりませんが、こちらもバージョンによっては7e10を超えない範囲までのリストが得られる場合があります。
さらに、「>>」という演算子(Hyper method call operatorと言います)を用いることで、リストの各要素に「.say」を付加することができます。つまり、コードは
(1.say,1.say,1.say,1.say,2.say,3.say,...)
のように展開されます。sayはprintと異なり、自動的に改行文字が入りますので、リストの各要素を出力し、改行を入れることができます。
Ruby(37B)
chatさん
n=0;100.times{$*<<n+2*n=p($*[-4]||1)}
「$*」は組み込み定数を用いて配列の初期化を避けています。CodeIQの自動採点システムでは実行時に引数が与えられないので、この変数は空の配列になっています。
最初の4日は、バイバイマンの数がすべて1ですから、配列が空（nil）の間はnの値が1になるように、「||1」としています。言語別では最も挑戦者数の多かったRubyで単独1位、すばらしいですね！
Perl(41B)
tailsさん
print$$_=${$_-5}+${$_-4}*2||1,$/for-99..0
前回のコードゴルフ問題「シンプル・ライフゲーム」に続き、Perlでの最短コードはtailsさんでした。Perlゴルフのスーパーテクニックは https://codeiq.jp/magazine/2015/12/34740/ を参照してください。
以下、コードのみ紹介します。
bc(44B)
m-ukaiさん
for(r=1;r<4^17;p=z){z=s-q;s+=r;s;r=q;q=p};u=
Bash(46B)
tailsさん
eval 'set $['{0..99}'<4|$5+$40/5] $@;echo $1;'
Groovy(48B)
gmkさん
(a=[1]*99+2g).each{println w=a[-5];a+=w+2*a[-4]}
Falcon(49B)
angelさん
a=[-5,3,-1,1,0];for i=0 to 99:>a[i%5]+=a[-~i%5]*2
Python(50B)
notogawaさん・ebicochinealさん・だいじゅさん
3名共にほぼ同じコードでしたので、代表してnotogawaさんのコードを紹介します。
a=b=c=d=1;exec'print a;a,b,c,d=b,c,d,a+b-c+d;'*100
JavaScript (rhino)(51B)
Mattsunさん・Theodoreさん・hogeover30さん・mbspさん
4名共にほぼ同じコードでしたので、代表してMattsunさんのコードを紹介します。
for(a=[i=0];i++<100;)print(a[i]=a[i-4]*2+a[i-5]||1)
ebicochinealさん
a=b=c=d=1;for(;b%37;a=b,b=c,c=d,d+=x+a-b)print(x=a)
JavaScript (spidermonkey)(51B)
chatさん・Mattsunさん・Theodoreさん・ebicochinealさん・hogeover30さん・mbspさん
JavaScript (rhino)のコードと同じですので省略します。
PHP(51B)
PINさん
"<?for(;$i++<100;)echo$$i=${$i-5}+2*${$i-4}?:1,"" "";"
Python 3(53B)
notogawaさん・ebicochinealさん・だいじゅさん
3名共にほぼ同じコードでしたので、代表してnotogawaさんのコードを紹介します。
a=b=c=d=1;exec('print(a);a,b,c,d=b,c,d,a+b-c+d;'*100)
AWK (gawk)(55B)
todaemonさん
{for(a=1;$0--;d=x){print f+=a;x=c;c=b;b=a+e;a=d+e;e=d}}
Haskell(56B)
notogawaさん・henkmaさん・koyama41さん
3名共にほぼ同じコードでしたので、代表してnotogawaさんのコードを紹介します。
main=mapM print x;x=1:1:1:1:[(0:x)!!i+2*x!!i|i<-[0..95]]
yetterbiumさん・antimon2さん 2名共にほぼ同じコードでしたので、代表してyetterbiumさんのコードを紹介します。
f=1:1:1:1:[2*f!!n+(0:f)!!n|n<-[0..95]];main=mapM print f
Node.js(57B)
chatさん・Theodoreさん
2名共にほぼ同じコードでしたので、代表してchatさんのコードを紹介します。
for(a=[n=0];n++<100;)console.log(a[n]=a[n-4]*2+a[n-5]||1)
ebicochinealさん
a=b=c=d=1;for(;b%37;a=b,b=c,c=d,d+=x+a-b)console.log(x=a)
PARI/GP(63B)
gmkさん
a=[2,1,1,1,1];for(n=1,input,print(w=a[5]);a=concat(w+2*a[4],a))
Octave(63B)
あしぇるさん
v=[1;1;1;1;2];for i=6:100v(i)=2*v(i-4)+v(i-5);end;dlmwrite(1,v)
R(63B)
gmkさん
a=c(2,rep(1,99));for(i in a){write(a[5],"");a=c(a[5]+2*a[4],a)}
Lua(64B)
gmkさん
a={1,1,1,1,2};for i=1,100 do print(a[i]);a[i+5]=a[i]+2*a[i+1]end
ebicochinealさん
a,b,c,d=1,1,1,1;for i=0,99 do print(a);a,b,c,d=b,c,d,d-c+b+a end
AWK (mawk)(64B)
todaemonさん
{for(a=1;$0--;d=x){printf"%.0f\n",f+=a;x=c;c=b;b=a+e;a=d+e;e=d}}
☆特別編☆
上位20言語ではありませんが、個人的な好みでCのコードのみ紹介させていただきます。
C(69B)
y_konishiさん
double*x=&x;main(){for(;*x<2e10;)printf("%.f\n",x[5]=*x+++*x*2+!*x);}
