カメヲラボ

主にプログラミングとお勉強全般について書いてます

バイバイマンを数えよう【解説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);}