2018-04-28

プログラミング言語★裏選挙―愛の風車【解説】

本稿はCodeIQで2014年10月2日～2014年10月23日に出題された「プログラミング言語★裏選挙―愛の風車」 という問題の結果・解説です。

プログラミング言語★裏選挙―愛の風車【解説】

f:id:Ozy:20180428145747j:plain

順位表

最終的な順位は、次のようになりました。

順位	有効得票数	言語
1位	17	JavaScript
2位	16	PHP
3位	14	Perl
4位	12	Python
5位	9	Scala
6位	7	Bash, C++11
8位	6	AWK
9位	4	Go, VB.NET
11位	3	D
12位	2	Clojure, Erlang, Octave, R, Scheme, SQL, Whitespace
19位	1	A, Brainfuck, Common Lisp, Egison, F#, Fortran, Groovy, Lua, Objective-C, Pascal, なでしこ

僅差でJavaScriptが1位となりました！ PHPは惜しかったですね。 Perlは最近挑戦者数が減ってきているように感じていましたが、まだまだ人気ですね。 Pythonは本選に残る人気でしたから、今回はあえて使用しなかった方が多かったのかもしれませんが、なんとか4位に滑り込みました。 5位以下では、Scalaが健闘しました。総選挙のときも、関数型言語ではHaskellに次ぐ人気で、今後が楽しみですね。 BashやAWKが結構上位に来たのも興味深いです。 C++11は意外に伸びませんでした。問題の内容が簡単でしたから、わざわざ使おうという気になりにくかったのかもしれませんね。総選挙のときと違いideone縛りを無くしたこともあってか、言語の種類は29種と非常に多かったです。

解説と優秀・おもしろ解答

素敵な風車の描き方(1)

風車なんだから、くるくる回転してナンボでしょ！ということで、羽の左上だけ生成し、それを回転させることで風車全体を作るようにするという方法が考えられます。

【Muさんのコード(Octave)】

for i = 5:7
  a = char(tril(ones(i))*('*'-' ')+' ');
  b = horzcat(a, rot90(a,-1));
  disp( vertcat(b,rot90(b,2)));
endfor

Octaveという言語は行列の操作が簡単にできるのが特徴で、まずa = …の部分で三角行列を作ることによって羽の左上を生成しています。次の行で、最初に作った羽を右に90度回転させ、最初に作った羽と連結しています。 rot90関数の第2引数は回転させる回数で、-1ということは右に1回回転させるという意味になります。これで風車の上半分ができました。これをさらに180度回転させると下半分もできるので、簡単に風車が完成しました。美しいですね。

素敵な風車の描き方(2)

羽を1枚だけ生成し、それを回転させるためには配列を用意しなければなりません。配列を使わずに、2重ループでまとめて描いてしまうという方法もあります。羽が4枚ありますから、xy平面上を4分割し、各領域で’*’を表示するか’ ‘を表示するかの条件分岐をすると、8つも分岐しなければなりません。それはそれで何をやっているのかわかりやすいという利点もありますが、if文をたくさん並べることなく、簡潔でカッコよく書きたい！と思うのも人情です。というわけで、「コイツはカッコいいぜ！！」と私が感じたコードを紹介しておきます。 【ぶんさんのコード(VB.NET)】

Imports System

Public Class Test

    Public Shared Sub Main() 

        Dim n,x,y As Integer

        For n = 5 To 7

            For x= -2*n+1 To 2*n-1 Step 2

                For y= -2*n+1 To 2*n-1 Step 2

                    System.Console.Write(IIF((x/y<=y/x),"*"," "))

                Next y

                System.Console.Writeline("")

            Next x

        Next n

        End

    End Sub

End Class

【haruyaさんのコード(Python)】

import sys
for a in [9, 11, 13]:
    for y in range(a, -a - 2, -2):
        for x in range(-a, a + 2, 2):
            sys.stdout.write(' ' if ((x + y * 1j) ** 4).imag > 0 else '*')
        print

両者の共通点として、羽のサイズNの風車を書く際、単純に0..2N-1の範囲でループせずに、-2N+1..2N+1の範囲で2ステップしているコードになっています。これは、xy平面を4象限に分割しつつ、座標の絶対値を対称にするためです。座標が0になってしまう箇所を避けることもでき、余計な分岐を無くすことができます。わかりやすいように、N=5の場合を図にしてみましょう。ぶんさんのコードで、(x/y<=y/x)となっている部分を調べるために、各座標に対応する(x/y – y/x)を計算してみます。

f:id:Ozy:20180428150252p:plain

上記のように羽の部分(‘*’を表示する部分)の値は0以下になり、1つの不等式できちんと判別できています。 haruyaさんのコードでは、複素数平面を利用していて、複素数(x + yi)を4乗すると、虚部はxy(y² – x²)という式になります。これは、先程の(x/y – y/x)という式に(xy)²を掛けたものと一致するので、判定方法としては同じです（ただし、両者のコードはx, yの向きが異なっていますので注意してください）。風車の左上と右下・右上と左下では羽の向きを判定する式が共通化でき、2領域の区別はx, y座標を乗除したときの正負で判定できるというところがポイントです。

おもしろ解答

個性的な解答が多数ありましたが、すべてをご紹介することはできませんので、130のコードのうち特に印象に残ったものをご紹介いたします。

【hcmiyaさんのコード(Bash)】

for i in {5..7}
do 
    hane1="$(head -c$i /dev/zero |tr '\0' ' ' |sed ':j;H;s/ /*/;t j;x'|tail -n+3)"
    hane2="$hane1
$(rev <<<"$hane1")"
    rev <<<"$hane2" |tac |paste -d '' <(cat <<<"$hane2") -
done

sedで羽を1枚作り、tacやrevで回転させるタイプのコードで、様々なコマンドを上手に使いこなしている感と、それによって非常に簡潔なコードに仕上がっている点に惹かれました。

【カニ戯（ryさんのコード(Bash)】

for x in 5 6 7
do
    echo $x | \
    sed \
     -e ':0;x;s/^.*$/&\*/;x;y/987654321/876543210/;/0/!b0' \
     -e 's/.*//;g;s/^./@/;y/@*/* /;G;s/\n//;h;s/.*//;x;h' \
     -e ':1;/^\** *$/!{;s/\* /\*\*/' \
     -e 's/^\(.*\)\(\*\*\)\( *\)$/\1\* \3/;H;b1}' \
     -e 's/\(^\**\)\( *$\)/\2\1/;H;s/ \*\*\*/\*\* \*/;H' \
     -e ':2;/^\*/!{;s/ \*/  /2;s/ \*/\*\*/;H;b2};g'
done

こちらはsedだけですべての羽を作っているコードで、パッと見た感じだけでお腹いっぱいなのですが、コードを順に追っていくとsedプログラミングがよくわかります。 sedゴルフに興味があるけどよくわからないという方は、これで勉強してみてはいかがですか？パターンスペース・ホールドスペースという2つのバッファをうまく使うのがポイントです。

【みけCATさんのコード(A言語)】

AtSnc:c\ArSnc:+*n++n-1-%cn/cn\AfSnc:+*n/cn++n-1-%cn\AgSnc:?>%cn/cnS \\:S*\\:\
Ri3PAn+5iRy*2nPRx*2nPAv%ynPAu%xnOFgnF?<xnt:r:nF?<ynt:f:n+*nvuOMc10

なんじゃこら！というか、A言語って何ですか！という感じですが、 https://github.com/snukent/a から処理系が手に入るようです。素敵な風車の描き方(2)で解説したアルゴリズムを使って書くと、

Rn3PAk+n5Ri*k2PAy+1*2+i-kPRj*k2PAx+1*2+j-kO?</xy/yxS \:S*\:OMc10

のような感じで、かなり短く書くことができます。興味のある方は試してみてください。

【KTazakikさんのコード(Brainfuck)】

[-]>[-]+++++++[-<++++++>]<>[-]>[-]++++++++[-<++++>]<>[-]++++++++++<<
 .>....<.....>>.<<
 ..>...<....>.>.<<
 ...>..<...>..>.<<
 ....>.<..>...>.<<
 .....><.>....>.<<
>....<.><.....>>.<<
>...<..>.<....>>.<<
>..<...>..<...>>.<<
>.<....>...<..>>.<<
><.....>....<.>>.<<
 .>.....<......>>.<<
 ..>....<.....>.>.<<
 ...>...<....>..>.<<
 ....>..<...>...>.<<
 .....>.<..>....>.<<
 ......><.>.....>.<<
>.....<.><......>>.<<
>....<..>.<.....>>.<<
>...<...>..<....>>.<<
>..<....>...<...>>.<<
>.<.....>....<..>>.<<
><......>.....<.>>.<<
 .>......<.......>>.<<
 ..>.....<......>.>.<<
 ...>....<.....>..>.<<
 ....>...<....>...>.<<
 .....>..<...>....>.<<
 ......>.<..>.....>.<<
 .......><.>......>.<<
>......<.><.......>>.<<
>.....<..>.<......>>.<<
>....<...>..<.....>>.<<
>...<....>...<....>>.<<
>..<.....>....<...>>.<<
>.<......>.....<..>>.<<
><.......>......<.>>.<<

ソースコード自体が風車っぽくてステキですね。 ‘\n’, ‘*’, ‘ ‘をセットしただけでほぼベタ書きじゃないかー！という突込みはナシで^^; 他にも面白いコード（WhitespaceとかSQLとか！！）をたくさんいただきましたが、これくらいにしておきます。

最後に

単純な問題ではありましたがどれも個性的で、読んでいて楽しいコードがたくさんありました。同時に、ものすごく似た感じのコードもあり、それらを大量に見た感想を書いておきます。まず、次のようなコードをご覧ください。

void kazaguruma( int n )
{
  for (int y = 0; y < 2 * n; ++y) {
    for (int x = 0; x <  2 * n; ++x) {
      if ( y < n ) {
        if ( x < n ) {
          if ( y >= x ) {
            printf( "*" );
          } else {
            printf( " " );
          }
        } else {
          if ( y + x < 2 * n ) {
            printf( "*" );
          } else {
            printf( " " );
          }
        }
      } else {
        if ( x < n ) {
          if ( y + x >= 2 * n - 1 ) {
            printf( "*" );
          } else {
            printf( " " );
          }
        } else {
          if ( y <= x ) {
            printf( "*" );
          } else {
            printf( " " );
          }
        }
      }
    }
    printf( "\n" );
  }
}

羽のサイズnを受け取り、左上・右上・左下・右下の順で分岐して羽を書くコードです。好き嫌いで言えば、いかにも冗長な感じで、私はあまり好きなタイプのコードではありません。ただ、同じようなコードをたくさん見ていると、そんなに悪いコードでもないように思えてきます。このような形が書かれていれば、コードの中身を読まずともその内容がすぐにわかるからです。平面的に文字を描画する場合、“左から右に向かって”、“上から下に向かって”、という順序は最も素直で、よほど捻くれたプログラマでない限りはこの順序で条件分岐も書くでしょう。

つまり、このようなコードはシルエットを一目見ただけで、どのようなコードかが理解できます。私は子どもの頃から視力が弱いので、ぼんやりとモノを見る癖がついてしまっていますし、そういうコードの見方をしている人にとってはこれ以上わかりやすい記述はありません。それでは自分が普段このようなコードを書くのかというと、書きません。一応、頭の中では上記のようなイメージ（文字通り画像のような“絵”）がパッと浮かびます。次に何をするのかというと、その絵を見ながら、文句を言うわけです。「printfが9個もあるじゃないか！！！」それで、次のようなコードに書き替えてみたりします。

void draw( bool a )
{
  printf( a ? "*" : " " );
}

void kazaguruma( int n )
{
  for (int y = 0; y < 2 * n; ++y) {
    for (int x = 0; x < 2 * n; ++x) {
      if ( y < n ) {
        if ( x < n ) {
          draw( y >= x );
        } else {
          draw( y + x < 2 * n );
        }
      } else {
        if ( x < n ) {
          draw( y + x >= 2 * n - 1 );
        } else {
          draw( y <= x );
        }
      }
    }
    printf("\n");
  }
}

改行用のprintfは仕方なしということで、条件式を引数に、drawという関数を新たに作りました。 8つのprintf関数が1つになったことと、ifブロックのネストが減ってだいぶスッキリしました。まあ、これくらいのコード量ならよいよね？
しかし、drawという短い記述の関数を作ってしまったが故に、短くしたはずのkazaguruma関数が比較的冗長に見えてきてしまいました。それなら、ネストの一番内側にある、左右の条件式の部分をもうちょっとまとめておこうか。

void draw( bool a )
{
  printf( a ? "*" : " " );
}

void drawLR( int n, int x, bool l, bool r )
{
  draw( x < n ? l : r );
}

void kazaguruma(int n)
{
  for (int y = 0; y < 2 * n; ++y) {
    for (int x = 0; x < 2 * n; ++x) {
      if ( y < n ) {
        drawLR( n, x, y >= x, y + x < 2 * n );
      } else {
        drawLR( n, x, y + x >= 2 * n - 1, y <= x );
      }
    }
    printf("\n");
  }
}

なんだかコードもスッキリしたし、関数化して細かく切り分けとかしてコンパクトに書ければ「ステキ！抱いて！！」ってなるんじゃね？じゃあ上下段も思い切って、切り出そうかな。

void draw( bool a )
{
  printf( a ? "*" : " " );
}

void drawLR( int n, int x, bool l, bool r )
{
  draw( x < n ? l : r );
}

void drawUDLR( int n, int y, int x, bool ul, bool ur, bool dl, bool dr )
{
  y < n ? drawLR( n, x, ul, ur ) : drawLR( n, x, dl, dr );
}

void kazaguruma(int n)
{
  for (int y=0; y<2*n; ++y) {
    for (int x=0; x<2*n; ++x) {
      drawUDLR( n, y, x, y >= x, y + x < 2 * n, y + x >= 2 * n - 1, y <= x );
    }
    printf("\n");
  }
}

…なんだか横に伸びてきちゃった。ちょっと空白減らして、nもグローバルでいいかな？

int n;

void draw(bool a)
{
  printf(a ? "*" : " ");
}

void drawLR(int x, bool l, bool r)
{
  draw(x<n ? l : r);
}

void drawUDLR(int y, int x, bool ul, bool ur, bool dl, bool dr)
{
  y<n ? drawLR(x, ul, ur) : drawLR(x, dl, dr);
}

void kazaguruma()
{
  for(int y=0;y<2*n;++y){
    for(int x=0;x<2*n;++x){
      drawUDLR(y, x, y>=x, y+x<2*n, y+x>=2*n-1, y<=x);
    }
    printf("\n");
  }
}

このような思考がエスカレートするのは、いわゆる（コード）ゴルフ脳という状態で、自分でブレーキを掛けなければなりません。この辺りまでで我慢ができれば、正常なプログラマではないかと思います。上記のような関数への切り出しも、比較的短めのコードなので見栄えがしますが、何十万行もあるコードでこれをやっていくと、ものすごく読みにくくなってしまいます。全体を見渡して、「まあこれくらいが自然かな」という感覚をある程度持っておくと、他人にコードを提供したりする場合に、相手にとって読みやすいコードを書くのが上手になります。

ベテランのプログラマと、若いプログラマ、もちろん十把一絡げに考えることはできないのですが、ひとつの傾向として、ベテランプログラマで「この人は仕事できるな」って感じるの人は、シチュエーションに合わせたコーディングができるという特長があるように思います。どのように書くかは、良く言えば美学、悪く言えば自己満足で、趣味の世界ならどこまでもこだわってよいと思います。しかし、他人と何らかのかかわりを持って、仕事として書くなら、自分より上級のプログラマに迷惑をかけることなく、なおかつ自分よりスキルの劣るプログラマを包み込めるようなバランス感覚を身に付けると、仕事もしやすくなるのではないでしょうか。

…と、一応転職向けのサイトということで無理やり仕事の話に結び付けましたが、ちょっと無理やり過ぎましたね。兎も角も、ある程度コードが書けるようになったら、他人のコードをたくさん読んで、コードから書き手のスキルレベルを感じ取る経験は、きっと役に立ちます。特に若い人は、いろんな人が書いた、いろんな言語のコードに触れてみてください。

2018-04-28

CodeIQ過去問集51：プログラミング言語★裏選挙～愛の風車

CodeIQ過去問集

本稿はCodeIQで2014年10月2日～2014年10月23日に出題された 「プログラミング言語★裏選挙―愛の風車」 という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

プログラミング言語★裏選挙―愛の風車

【問題】

素敵な風車を、標準出力に出力してください。

f:id:Ozy:20180428143128p:plain

これは羽のサイズが4の風車です。この形状で、サイズが5・6・7の風車を順に出力してください。羽の部分は’*’で、空白部分は半角スペースとします。改行コードは問いません。

*    *****
**   **** 
***  ***  
**** **   
******    
    ******
   ** ****
  ***  ***
 ****   **
*****    *
*     ******
**    ***** 
***   ****  
****  ***   
***** **    
*******     
     *******
    ** *****
   ***  ****
  ****   ***
 *****    **
******     *
*      *******
**     ****** 
***    *****  
****   ****   
*****  ***    
****** **     
********      
      ********
     ** ******
    ***  *****
   ****   ****
  *****    ***
 ******     **
*******      *

見た目がこのようになっていればOKです（心配な方は、kazaguruma.txt をダウンロードしてdiffを取ってみてください）。出力結果をそのままソースコード内に埋め込むような解答を禁止はしませんが、プログラミング愛があれば、そんなコードは書きませんよね？

【使用可能言語】

先日行われた『CodeIQ　プログラミング言語★総選挙』で本選に残らなかった言語を対象とします。つまり、

C / C++
C#
Haskell
Java
Python3
Ruby

は禁止（Python2とC++11は使用可能）です。基本的に、Ideone.com(http://ideone.com/credits)でテストしたいと考えておりますが、ここに無い言語や、コンパイラのバージョンが気に入らない等、他の環境をご希望の方は、解答ファイルに実行環境を明記していただければ、可能な限り対応いたします。フリーの処理系を使用する場合、導入方法をコメント内にご記入ください。無料でない実行環境の場合、対応できない可能性がございますのでご了承ください。また、Ideone.com上で使用可能な言語については以下のルールで集計します。

Assembler(nasm-2.10.01)・Assembler(gcc-4.8.1)は“Assembler”として統一
AWK (gawk)・AWK (mawk)は“AWK”として統一
COBOL・COBOL 85は“COBOL”として統一
JavaScript (rhino)・JavaScript (spidermonkey)・Node.jsは“JavaScript”として統一
Pascal (fpc)・Pascal (gpc)は“Pascal”として統一
Prolog (gnu) ・Prolog (swi) は“Prolog”として統一
Textはプログラミング言語とは呼べないので不可

【投票】

ご提出いただいたコードを実行し、実行結果が正しく得られたものを有効票とします。これを元にランキングを生成し、1位～4位の言語は、次のキャラクターに擬人化され、彼らのバッジが付与されます。かわいい女の子は架空の存在です。現実を見ましょう。

f:id:Ozy:20180428144955p:plain

【提出方法】

本問はすでに終了した問題ですので、提出することはできません。個人で楽しみましょう。

【結果・解説】

2018-04-27

作文ゴルフじゃなくてゴルフ作文

今更感が半端ないですが、半年くらい前にこの動画↓（55秒くらい）に現れる小ネタの作文を書きました。

f:id:Ozy:20180427171133p:plain

<body style="font-family:monospace;"><script>for(i=228;i--;)for(j=4;j--;document.write(i%19|j?s:s+"<br>"))s="□■"["AAAAAAAAAAAAAAAAAPAHEPAMDIBBPAOBIHAMACEMIBDMADJBBDCGIBGAGEEABBIACBACAECABCAEEEAJAABMJPDPHCACBAIEEAJAABEJBCDEOACBAIEEAJAABCBBBCCAACBAIPEAJAABBBOAMBAACDAIEAAABIAABAAAACABCAAEAAADMAABAAAAMIBGAEAAAAMDAABAAAAIHAMADAAAAAAAABAAAAAAAAPB".charCodeAt(i)-65>>j&1]</script>

ブラウザに貼り付けて開くとこんな感じになります。 f:id:Ozy:20180427170631p:plain

400バイトもあると頑張らなくても収まってしまうので、作文として書きやすいように圧縮データ部分は全部アルファベットで済むようにしました。余裕があるので等倍フォントを指定してます。

…まさかコードゴルフの仕事依頼が来るとは！！

2018-04-26

階段ピョンピョン1・2・3！【解説】

本稿はCodeIQで2014年2月3日～2月24日・2015年1月19日～3月2日に出題された 「コード銀行：階段ピョンピョン1・2・3！」 という問題の解答例と簡単な解説です。
本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ！」とか、「こう書いた方がわかりやすいよ！」とか、「他の言語で書いてみたよ！」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

階段ピョンピョン1・2・3！【解説】

◆基本的な考え方

n段目(n>3)に到達するとき、

[1] (n-1)段目まで上ったあと1段上がる
[2] (n-2)段目まで上ったあと2段上がる
[3] (n-3)段目まで上ったあと3段上がる

の3通りあるので、これらを再帰的に足し合わせるコードを書きます。

def count(n)
  return count(n-1) + count(n-2) + count(n-3)
end

という感じですね。もちろんnが負になってしまってはいけませんので、

if n < 0
  return 0

みたいな処理は必要です。nがちょうど0の場合は少し考える必要があります。

◆n = 0の場合の定義

たとえばnが2の場合を考えると、

[1] (2-1=1)段目まで上ったあと1段上がる
[2] (2-2=0)段目まで上ったあと2段上がる
[3] (2-3=-1)段目まで上ったあと3段上がる

[1]は明らかに1通りです。[3]は段数が負になるので0通りとしましょう。2段の上がり方は、実際には

・1段 + 1段
・一気に2段

の2通りです。したがって、[2]は1通りと数えた方が都合が良くなりますので、count(0)は1と定義しておきましょう。

◆メモ化

単純な再帰の場合は計算量がO(n³)でかなり遅いので、メモ化を行います。

def count(n)
  if memo[n]が存在
    return memo[n]
  endif
  
  memo[n] = count(n-1) + count(n-2) + count(n-3)
  return memo[n]
end

のような感じですね。memo[n]が存在するかどうかの判定には、memo[n]を0で初期化しておいて、0より大きいときは存在するということにしておきましょう。つまり、

memo = [1, 0, 0, 0, ... , 0 ]

のような初期値を持ったリストを用意するということです。先程count(0)は1と定義しましたので、memo[0]の値のみ1で初期化しておきます。

◆コード例

以上を踏まえて、Python3でコードの例を書いておきました。

import sys
from operator import add
from functools import reduce

n = int(sys.argv[1]) # 段数はARGVから取る
memo = [1] + [0] * n # memo[0]は1で初期化、memo[1..n]は0で初期化
step = [1, 2, 3] # ステップは3種類

def count(n):
    if memo[n] > 0: return memo[n]
    memo[n] = reduce(add, [count(n-k) for k in step if n-k >= 0])
    return memo[n]

print(count(n))

n=30で実行すると、

53798080

という出力が得られます。

2018-04-26

コード美人【解説】

本稿はCodeIQで2014年2月6日～同年2月24日に出題された「コード美人」という問題の解説です。

問題文はこちら

コード美人【解説】

◆基本的な考え方

1, 3, 9, 27, 81, 243, 729, …と、3の累乗になっている数を、3進法で表します。

  1: 00000001
  3: 00000010
  9: 00000100
 27: 00001000
 81: 00010000
243: 00100000
729: 01000000

これらの値をいくつか足し合わせても、3進数の各位は0か1しか現れません。つまり、2進数のように見えます。これを利用して、2進数を小さい順に並べ、それを3進数とみなし、3進→10進の変換を行えば、必要な数列が得られます。

たとえば、Rubyでコードを書くと次のようになります。

1.upto(100){|n|
  puts n.to_s(2).to_i(3)
}

「1から100までの数を、2進表現にして、それを3進数とみなし、10進数に変換する」

基数変換がしやすい言語なら、この方法を用いて、簡潔でわかりやすいコードを書くことができます。もちろん、この方法が最も美しいかといえば、はっきりYESと言うことはできません。他の方法を考えてみましょう。

◆アルゴリズムのパターン

n進法の変換が容易な言語を使った場合は、前述のコードで十分かもしれませんが、それ以外にも、アルゴリズムにいくつかのパターンがあります。

とりあえず3進法で表してみる方法

1から順に3進法で表してみると、

のようになりますが、該当する値は前述の通り2進っぽく見えなければなりません。つまり、このような変換をしたときに、1か所でも2が出現したら、それは出力しないという考え方をすると、目的の数列が得られるということですね。2が含まれるかどうかを調べるだけですから、正規表現を使って書くこともできそうなアルゴリズムです。

2進っぽく3進数を生成する

まず、1のみが入ったリストを用意します

[1]

ここから1を取り出し、3倍したもの、3倍して1足したものを、リストの末尾に加えます。

[1] <- 取り出した値のリスト
[3, 4] <- 追加する値のリスト

次に、リストの先頭にある3を取り出し、先程と同様に3倍したものと3倍して1足したものを、リストの末尾に加えます。

[1, 3] <- 取り出した値のリスト
[4, 9, 10] <- 追加する値のリスト

これを繰り返すと、目的の数列が得られます。

[1, 3, 4] <- 取り出した値のリスト
[9, 10, 12, 13] <- 追加する値のリスト

3倍するという操作は、3進表現したときの桁上りを意味します。また、1を足す操作しかしないことで、3進表現の中に2が現れないようにするのです。このような方法は、再帰的なコードを書きやすいですから、関数型言語等を用いれば非常に美しいコードになります。

まとめて足しちゃう

わかりやすいように、ある程度大きくなったリストで説明します。

[1, 3, 4, 9, 10, 12, 13, 27]

このリストは、3³が出現するまでを表していますが、この続きは簡単に生成することができます。27を、その直前まで(1から13まで)のすべての値に足していけば、続きの数列が得られます。

[ 1,  3,  4,  9, 10, 12, 13, 27]
[28, 30, 31, 36, 37, 39, 40]

全部足したら、27に3を1回かけたもの（81）を、リストの要素すべてに加えていけば、続きのリストが得られます。これも再帰的に処理しやすいので、美しいコードが書けそうですね。

どの方法も、本質的には同じですが、言語の特性にうまくマッチする方法を選ぶことができれば、非常に美しいコードになるでしょう。

◆挑戦者の解答集

正統派美人

挑戦者244名、提出数283の大量のコードを見て、私が個人的に心惹かれたコードです。

antimon2さん

Haskellで書かれたコードです。パッと見ただけで、fnの定義部分に自然に目が動きます。特別高度なテクニックを使っているわけでもなく、非常に素直なコードで、だからこそ非常にわかりやすい。関数型言語をよく知らない人間が見ても理解できそうな、すばらしいコードだと思いました。

-- define series
series = 
    let fn n
            | n < 2     = 1
            | odd n     = (+ 1) $ fn $ n - 1
            | otherwise = (* 3) $ fn $ n `div` 2
        construct_stream n = fn n : construct_stream (n + 1)
    in  construct_stream 1

-- define output
output stream n =
    let print_each = mapM_ print
    in  print_each $ take n stream

-- run
main = output series 100

ほかにも良いコードはたくさんありましたが、見た瞬間私の心を打ち抜いた、このコードのみご紹介ということにさせていただきます。

おもしろ解答

採点作業は非常に大変だったのですが、ときどき現れるおもしろ解答に癒され、最後まで採点することができました。変わった言語での挑戦はある程度覚悟していましたが、変わったコードを書く方に限って、恐ろしいほどにドキュメント・コメントが良いんですよね。相手への気遣いが強く感じられます。そりゃそうですよね。変わった解答をするには、相応のスキルが必要です。高いスキルがあって余裕があるからこそ、おもしろいコードが書けるわけですし、それをするだけのエネルギーを持っているわけですから。

ビジュアル系美人

みけCATさん

Pietという、プログラミング言語での解答です。画像データの色によってプログラムが表現されています。普通に書くだけでも結構大変なのですが、写真の画像データに仕込む形で見た目も美しく仕上げてあります。これはスゴイ！

この画像をPietインタープリタで動かすと、正しい解が出力されます。

http://www.bertnase.de/npiet/からダウンロードできますので、興味のある方は是非チャレンジしてみてください。

カワイイ系美人

amamaさん

CodeIQに住みついている謎の電脳生物ですね。正直このキャラクターってちょっと【自主規制】だと思うんですが、AAにすると意外とカワイイ…気がしてきました（´Д｀;）

         int co(char*);d(int i);
     char Code['IQ']="0000000",I,Q;
  #include                    <stdio.h>
 #include                      <stdlib.h>
long  int   main      (int i)    {for(;i<
'e'; i++)    {for       (I=0;I    <'o'-'d'
;I++)/**/    d(i)      ;printf    ("%d\n",
co(Code))                        ;}return
0,"Code",         ("");}         int  co(
char*e){          return         strtol(e
 ,0,3);}int        d(i)        {Code[10-
   I]=(i>>I)                 %2?'1':'0'
      ;return 0;}/*思ったより短くなっ
        てしまったので感想書きます．                 美しい
                ->絵画->AAだ！となってAAにしました．AAの題材
                には    某サイトのキャラを選びました．初めは
               golf      も考えたのですがやったことのない
                code     でAAに挑戦しよう
                          と思い    書きました．
                           言語は     Cです．顔
                            だけ見て
                             もそれなり
                              にコードに
                               見える筈*/

自称系美人

変数・関数名に「美」に関係する名前をつけるタイプのコードはいくつかありましたが、その中でも比較的クオリティが高かったものを紹介します。

simanmanさん

なんて押しつけがましい美なのでしょう。

class Object
  def 美
    @counter ||= 0
    @counter += 1
  end

  def し
    p @counter
  end

  def method_missing(name, *args)
    name.to_s.chars do |ch|
      if ['美','し'].include?(ch)
        send(ch.to_sym)
      end
    end
  end
end

美しい美美しい美しい美美美美美しい美しい美美しい美しい美美美美美美美
美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美しい美
しい美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美し
い美しい美美美美美美美美美美美美美美しい美しい美美しい美しい美美美美
美しい美しい美美しい美しい美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美し
い美しい美美しい美しい美美美美美しい美しい美美しい美しい美美美美美美
美美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美しい
美しい美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美
しい美しい美美美美美美美美美美美美美美しい美しい美美しい美しい美美美
美美しい美しい美美しい美しい美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美しい美しい美美しい美しい美美美美美しい美しい美美しい美しい
美美美美美美美美美美美美美美しい美しい美美しい美しい美美美美美しい美
しい美美しい美しい美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美しい美しい美美しい美しい美美美美美し
い美しい美美しい美しい美美美美美美美美美美美美美美しい美しい美美しい
美しい美美美美美しい美しい美美しい美しい美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美
美美美美美美しい美しい美美しい美しい美美美美美しいいいいいいいいいい

hogeover30さん

IOCCCなんかでありそうなコードですね。

#define BijiN main
#define Bijin a[
#define bijiN ]
#define bIjin i
#define BIJIN {
#define bijin }
#define BIjin for
#define biJIN printf
#define biJin ;
#define BiJin ,
#define bijIN (
#define BIJin )
#define BIjIN 100
bIjin BiJin Bijin BIjIN bijiN biJin BijiN bijIN BIJin BIJIN BIjin bijIN
biJin bIjin++<BIjIN biJin  BIJin biJIN bijIN"%d\n" BiJin Bijin bIjin
bijiN=bIjin%2?Bijin bIjin-1 bijiN+1:Bijin bIjin/2 bijiN*3 BIJin  biJin bijin
//i,a[];main(){for(;i++<100;)printf("%d\n",a[i]=i%2?a[i-1]+1:a[i/2]*3);}

数字だ系

数の問題なんだから数で表現！という美学のコードです。

KTazakikさん

大きな整数部分を16進数に変換して2文字ずつ区切るとASCIIコードが得られるので、それをコードとして復元している感じですね。

at_exit {
  lst = Array.new
  ObjectSpace.each_object(Bignum).each do |v|
    s = [v.to_s(16)].pack("H*")
    next unless s =~ /^B:(\d+):(.*)$/
    lst.push([$1.to_i, $2])
  end
  lst.sort!{|a,b| a<=>b}
  lst.each do |v|
    eval(v[1])
  end
}

2373316440976457250197918761860105244459294325385303762620305085053253870070907368572077419160528092491364
155537702111748977192310430882078850619243054765155014640320252081585639835766783353761046199169094798851534436
607569288858065828278660803295971603713646320948985194399297827967374839831543760925478916117332928938471012
343872110370846088544574445068496937

短さの美

notさん

スクリプト言語を使えばもっと短く書けますが、このCのコードはショートコーディングテクニックがぎっしり詰まっています（57バイト）。

i;main(j){for(;i=~i%3?i/3?:~!printf("%d\n",j):++j%982;);}

アルゴリズムとしては、1から順に3進表現し、「どこにも2が現れなければ表示する」という考え方を用いています。このアルゴリズムで素直にコードを書こうとすると、次のような2重ループになります。

#include <stdio.h>

int main()
{
  // 100番目の値が981であることを事前に調べておく
  // 普通に書く場合はカウンタ用の変数を用意する
  for(int n = 1; n <= 981; ++n){
    int k = n;
    for(; k != 0; k /= 3){
      if( k % 3 == 2 ) break;
    }
    // kが0ということは、
    // 3進表現したときに2が一度も現れなかったということ
    if( k == 0 ) printf("%d\n", n);
  }

  return 0;
}

ここからnotさんのコードに持っていくのがいかに大変か、是非挑戦してみてください。

個性派美人

変わった言語や、あまり他の人が使わなかった言語での挑戦者を晒しあげ…じゃなくて紹介します。個人的にはたいへん楽しませていただきました。ありがとうございます。

美白系美人

美白…いるとは予想していましたが、やはりいましたWhitespace（´ω｀）

NeoCatさん

simbelmynさん

オンリーワン美人

マイナーな言語ばかりというわけではなさそうですね。

KAZAMAI_NaruToさん：SQL

tailsさん：Bash, sed

ゆうふーるさん：Pascal

ももんちょさん：Kuin

grails使いさん：Groovy

Azicoreさん：GolfScript

pocketberserkerさん：F#

electrolysisさん：D

Mi_Sawaさん：Anko C++

ytominoさん：Ada

manmanさん：VBA

kazkaz613さん：VB.NET 　

◆統計情報

参加者数244名

正解者数229名

使用言語

言語名	人数
C/C++	67
Ruby	43
Java	30
Python	22
JavaScript	16
Haskell	9
PHP	9
Perl	8
C#	7
Scala	7
R	2
Whitespace	2
Ada	1
Anko C++	1
Bash	1
D	1
F#	1
GolfScript	1
Groovy	1
Kuin	1
Pascal	1
Piet	1
Sed	1
SQL	1
VB.NET	1
VBA	1

◆最後に

美しさ

出題しておいて何も語らないというのも少しズルい気がしますので、最後に個人的な考えを記します。

そのコードに美しさが見えるとき、おそらくそれはコード自体が美しいというより、アルゴリズムの美しさが自然にコードで表現されているのだと思います。「再帰的なコードは美しい」とか、「コメントが必要ないコードが美しい」のような台詞はよく耳にするような気がしますが、それは単なる要因の一つに過ぎません。部分的・限定的な要因を、それがすべてであるように信仰すればするほど、表現されるコードは歪なものとなり、『美しい。思っているのは、自分だけ』ということになりかねません。

深さ優先探索を行うなら再帰的なコードを書く場合が多いでしょうし、幅優先探索を行う場合はwhile文を書くでしょう。扱うプログラミング言語にパワーが足りなければ、なぜそう書くのか、そう書くと何が良いのか、ということをコメントで書いたって良いでしょうし、言語にパワーがあれば、あえてコメントを書く必要もないでしょう。

「ワンライナーで書いた！」それが自然なコードであれば、美しいと思います。けれども、無理やり1行で書いた、100文字以上もあるワンライナーは、きっと美しくありません。

こうしたから美しい、なんてことは何一つ決まっていなくて、何かあるとすれば、さまざまな要因の調和ということでしょうね。自分の理解の程度、問題の種類、扱う言語、その時のコーディングルール、総合的に見て、無理をしないコーディングを心掛ければ、それほどひどいコードにはならないはずです。いつも少しだけ背伸びして、いろんな人のコードを読んで、確かに良いと思えるものを素直に受け入れる。そんなコード美人でありたいものです。

出題・採点を終えて

結構な方が、「これは美しくないコードです」みたいなコメントを入れてらっしゃったのですが、全くそんなことはなくて、変数名だとか、空白文字、改行も非常に読みやすいように考えられているものが多かったです。通常の採点と比較すると、圧倒的に読みやすいコードの割合が高くて、たくさんお気遣いいただいたのだなぁと感じております。何らかの組織に所属していると、決して美しいとは思えないようなコーディングスタイルを強要され、嫌な思いをすることもたくさんあると思いますが、だからと言って自分の美学をなくしてしまう必要はないわけですから、自信を持ってやってほしいですね。美しさと共に、愛を感じた採点でした。

2018-04-26

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

2018-04-26

バイバイマンを数えよう【解説1】

本稿はCodeIQで2016年1月28日～同年2月18日に出題された「バイバイマンを数えよう」という問題とその解法に関する記事です。

問題文はこちら

バイバイマンを数えよう【解説1】一般解法編

◆バイバイマンの数え方

List<バイバイマン>のようなデータ構造で素直に実装したいところですが、実際にやってみるとバイバイマンの数は爆発的に増えてしまいます。バイバイマンの種類とその発生条件を確認しておきましょう。

◆バイバイマンの種類

バイバイマンの大きさはさまざまですが、全部で何種類存在するでしょうか。

【A型】

最初のバイバイマンはサイズが「1」です。これを『A型』のバイバイマンとします。

【B型】

A型のバイバイマンは次の日にサイズが「2」になります。これを『B型』のバイバイマンとします。

【C型】

B型のバイバイマンは次の日にサイズが「4」になります。これを『C型』のバイバイマンとします。

【D型】

C型のバイバイマンは次の日にサイズが「8」になります。これを『D型』のバイバイマンとします。

【E型】

D型のバイバイマンは次の日にサイズが「16」になり、分裂が起こります。それぞれのサイズは「1」と「6」ですので、1体はA型で、もう1体は初めて出現します。これを『E型』のバイバイマンとします。

E型のバイバイマンは次の日にサイズが「12」になり、分裂が起こります。それぞれのサイズは「1」と「2」ですので、いずれもすでに定義されたバイバイマン（A型とB型）になり、新しいタイプのバイバイマンはこれ以上生まれないことになります。

以上から、バイバイマンは5種類ということが確認できました。

◆バイバイマンの発生条件

次に、各種バイバイマンの発生条件を確認します。

【A型】

最初から存在するもの以外では、D型とE型が成長し分裂することで出現します。

【B型】

A型が成長する場合と、E型が成長し分裂する場合に出現します。

【C型】

B型が成長することで出現します。

【D型】

C型が成長することで出現します。

【E型】

D型が成長し、分裂することで出現します。

◆アルゴリズム

バイバイマンの発生条件を元に、疑似コードを書いてみます。バイバイマンのタイプごとに、日数を添え字とした配列を用意します。

# 1日目はA型1体のみ
A[1] = 1
B[1] = 0
C[1] = 0
D[1] = 0
E[1] = 0


loop {
  
  print A～E[k]の和
  
  if (k = 100) {
    break
  }
  
  # バイバイマンの発生条件に従って、k日目の状態から(k+1)日目の状態を計算する
  A[k+1] = D[k] + E[k]
  B[k+1] = A[k] + E[k]
  C[k+1] = B[k]
  D[k+1] = C[k]
  E[k+1] = D[k]
  
}

簡潔な記述で、高速なコードになります。1日目から順に出力するだけなら、配列を使わず省メモリで書いても良いですね。

【解説2】