バイバイマンを数えように挑戦しました ( CodeIQ )
はじめに
CodeIQ というところで開催していたコードゴルフ問題、「バイバイマンを数えよう」に挑戦しました。
出題者ozyさんの上記集計記事にある通り、Brainf**kとFalconでは1位で、神バッジは確保できたのですが…。Perlは上手い縮め方を見つけられず断念。Rubyはトップに4文字足らず。最短のPerl6に至っては「何それ美味しいの??」状態でした。なかなか切ない。
問題
1日毎に次の規則で増える「バイバイマン」の数を、1日目～100日目 ( 固定 ) 分、1行毎に出力する、というものでした。
※使う必要は ( まあBrainf**kや…せめてPerl? 以外では ) ありませんが、100という入力も与えられます。
- 全てのバイバイマンにはサイズが規定されている
- 1日目はサイズ1のバイバイマンが1匹いる
- 1日たつと、全てのバイバイマンはサイズが倍になる
- ただし、サイズが10を超えるバイバイマンは、その10,1の位の数値をサイズとするバイバイマン1匹ずつに分裂する
この増え方は バイバイマンの増え方 - Cozy Ozy に図解があります。
解説
数学的に
まず、何日分かシミュレートしてみると分かるのですが、登場するバイバイマンは、サイズ1,2,4,8,6の5種類しかいません。なおかつ、次の日の数がどうなるかが、それぞれの種類のバイバイマンの数の線形和 ( 要するに1次式 ) になることは自明です。
そのため、サイズ1,2,4,8,6のバイバイマン、それぞれn日目の数を $a_n,b_n,c_n,d_n,e_n$ とした場合、漸化式は行列・ベクトル積の形で書き表すことができます。具体的には次の通り。
$$ \begin{pmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \\ d_{n+1} \\ e_{n+1} \\ \end{pmatrix}=\begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ b_{n} \\ c_{n} \\ d_{n} \\ e_{n} \\ \end{pmatrix} $$
ということで、各一般項は行列のべき乗を使って表すことができます。 $$ \begin{pmatrix} a_{n} \\ b_{n} \\ c_{n} \\ d_{n} \\ e_{n} \\ \end{pmatrix}=\begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}^{n-1}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} $$
ただ、求めるべきは全種類のバイバイマンの数の合計です。これを$s_{n}$とすると、次のようになります。 $$ s_{n}=\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}^{n-1}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ \end{pmatrix}^{n-1}\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{pmatrix} $$
なぜ転置しているかというと、こちらの方が扱いやすいからですね。どういうことかというと、 (a,b,c,d,e)→(b,c,d,a+e,a+b) という変化を繰り返すベクトル ( 初期値(1,1,1,1,1)、バイバイマンの総数は先頭の要素 ) の表現式とみなせるからです。実際、この計算を元に組んだコードを最初提出したのですが、行列を変形することでもうちょっと楽な形にすることができると気付きました。
$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 0 & 1 \\ \end{pmatrix}=\begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 2 & 0 & 0 & 0 \\ \end{pmatrix} \\ s_{n}=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 2 & 0 & 0 & 0 \\ \end{pmatrix}^{n-1} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{pmatrix} \\ \Rightarrow \\ s_{n}=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 2 & 0 & 0 & 0 \\ \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 2 \\ \end{pmatrix} \\ $$
何をしているかと言うと、逆行列の関係にある基本変形行列 ( ある行/列の定数倍を別の行/列に足す ) を挟むようにかけているわけです。行列で書くとちょっとものものしく見えるかもしれませんが。
最終的に得られた形は、初期値 $s_1=s_2=s_3=s_4=1,s_5=2$ である $s_{n}$に関する隣接6項間漸化式 $s_{n}=2s_{n-4}+s_{n-5}$ の表現式に他なりません。おそらく、これが一番使いやすい形になると思います。
※この漸化式の固有方程式は解-1を持つため、分解して $s_{n}=s_{n-1}-s_{n-2}+s_{n-3}+s_{n-4}$ という隣接5項間漸化式にもできますが…。なお、他の固有値はとても計算できないため、一般項を綺麗な式で表すのは諦めました。
えっ…? こんな面倒くさい行列計算やってたやつはいねーよ…?
提出コード
ということで提出したコードですが、$s_{n}=2s_{n-4}+s_{n-5}$ という漸化式を素直に実装したものに過ぎません…。といっても、言語によって細部をどうするかはかなり工夫の余地があるようですね。
Ruby
Ruby(41)です。トップの37には4文字も足らず…(ぐぬぬ)
q=[1]*4<<2
100.times{q<<q[-4]*2+p(q[-5])}
出力を司るpの返り値は引数そのままなので、初期5項を入れた数列qをそのまま拡張していくだけで済みます。
Falcon
Falcon(49)です。一応トップ ( というかやってる人が少ない )。
a=[-5,3,-1,1,0] for i=0 to 99:>a[i%5]+=a[-~i%5]*2
これは、5要素の配列 a をサイクリックに利用している実装です。漸化式の適用と出力を同時に行うため、漸化式を遡って作り出した値を初期5項に使用しています。
Brainf**k
Brainf**k(267)です。ぶっちぎりのトップ…。…。参加者、増えてほしいなあ…。
一応コメント入れているんですが、後から自分で見ても良く分かりません。が、基本アルゴリズムはRubyと同じです。ただし、古い項は残さず、最新の5項 ( コード中のa,b,c,d,e ) のみを残します。
Brainf**kはネイティブでBCDなのですが、桁ごとに5項をパックして配置し、ステップ毎に全体がずれていくようにしています。面倒なのはキャリーの扱いと桁数拡張の判断でしょうか。工夫している点としては、入力の文字コードを活用してカウンターの100を作り出している点 ( 0から作ると高くつくんや… )、桁に48を足して文字コードを作った後、更に2を追加してから割り算をしてキャリーに使っている所、位ですかね。
終わりに
取り敢えずPerl6の29文字を見て口があんぐりしました。またCodeIQ Magazineでまとめが出ると思いますが、現場からは以上です。
