Help us understand the problem. What is going on with this article?

FizzBuzzのcodegolfを世界一分かりやすく解説!#c言語

はじめに

codegolf ShortCodingと聞くと、「何してるかわかんない」「見にくい」「意味ない」等マイナスなイメージが付きがちですが、そんなことはありません!
確かに見にくいのは事実。通常であれば誰もが理解出来るコードを書くべきです。(自分も普段はそう書いてます。)
しかしコードを短くすることは簡単ではありません。ただ見にくくすれば良いわけではありません。
データ構造・アルゴリズム・処理の観点から探求し、コードを短くするためにありとあらゆる知識を使います。
コードを短くするには想像以上の知識、そして発想力が求められるのです。
日々の生活等に役に立つかと言われたら微妙です、ですが考え方や言語への理解、そして熱き精神が必ずあなたを成長させます。
今までの先入観を捨て是非楽しんでいってください。
あくまでも遊びの一つです、実際のコードでは見やすく分かりやすく書いてください。

短縮する元のコード

Wikipediaを参照してください。
https://ja.wikipedia.org/wiki/Fizz_Buzz
今回はこのWikipediaのサンプルコードを短くしていきます。

280byte
#include <stdio.h>
int main(void) {
    int i;
    for (i = 1; i <= 100; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            printf("FizzBuzz\n");
        } else if (i % 3 == 0) {
            printf("Fizz\n");
        } else if (i % 5 == 0) {
            printf("Buzz\n");
        } else {
            printf("%d\n", i);
        }
    }
    return 0;
}

最終的にはこうなります。順を追って短くして行きましょう!

74byte
main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":0:"Fizz",i);}

実際に短くしてみよう

codegolfをするにあたりErrorを大量に吐きますが、動けば問題無いので無視してOKです。
短くするためならセキュリティ面も気にしなくていいのでgets等の関数も積極的に使っていきましょう。
バージョンはgcc version 6.3.0です。

gccを使おう

c言語でcodegolfをするならgccがおすすめです。
gccは破茶目茶なコードを書いても無理やりバイナリを生成してくれるので、例外はありますが基本的に1番短くなります。

基本的な削りから

それでは削れるところから削っていきます。
まず簡単なところから、

スペースを詰める

改行は後から削った方が理解しやすいので、いつも後回しにしています。

return 0;を削ります。

C99はmain関数でreturn文を省略すると自動的に0を返すので必要ありません。

#include <stdio.h>を削ります。

#includeを省略するとErrorを吐きますが動きます。おまけに型の判定がゆるくなります。

int main(void)を削ります。

mainというシンボルさえ定義されていれば動きます。
なのでmain()で動きます。

int iの場所を工夫する

gccではグローバル変数の型を省略するとint型になります。
さらにグローバル変数の初期値を省略すると0になります。

省略出来る場所を消すだけでこんなに短くなります

198byte
i;main(){
    for(i=1;i<=100;i++){
        if(i%3==0&&i%5==0){
            printf("FizzBuzz\n");
        }else if(i%3==0){
            printf("Fizz\n");
        }else if(i%5==0){
            printf("Buzz\n");
        }else{
            printf("%d\n",i);
        }
    }
}

ちょっと頭をひねってみる

3かつ5で割れる時、実質15で割れる時なのでそこをまとめます。

Before
if(i%3==0&&i%5==0){
After
if(i%15==0){

条件式を変える

i<=100i<101にすると1byte省略されます

インクリメントと条件式をまとめる

i<101;i++++i<101にするとまずインクリメントされてから条件判断します。
ちなみにi++<101にすると条件判断した後にインクリメントをします。この使い分けが出来ると1byte減ったりするので完全に理解しましょう。
条件判断の前にインクリメントするので初期値は0になります、gccでグローバル変数の初期値を省略すると0になるので、初期値設定を省略出来ます。

10byte以上短くなる

186byte
i;main(){
    for(;++i<101;){
        if(i%15==0){
            printf("FizzBuzz\n");
        }else if(i%3==0){
            printf("Fizz\n");
        }else if(i%5==0){
            printf("Buzz\n");
        }else{
            printf("%d\n",i);
        }
    }
}

codegolferはforを使う

for文の中を書かなくても動きます。むしろ別の式をぶっこめるのでwhileは使っては行けません、forを使いましょう。

Before
printf("Hello, World");
for(;i<10;){
    printf("Hello, World");
}
after
for(printf("Hello, World");i<10;printf("Hello, World"));

forwhileのbyte数も同じです。

byte数が一緒
while()
for(;;)
無限ループならforのが短い
while(1)
for(;;)

ifは使わない

codegolfする際にif文は使いません。三項演算子か論理演算子の二択です。
この2種類を場合によって使い分けましょう。

三項演算子とは

条件式 ? true文 : false文;なのでif文と対して変わりません、ただし三項演算子は式だということを忘れないでください。
三項演算子は式なので結果を代入したり、printfの中にぶっこんだり出来ます。そこが最大の強みです。
ちなみに三項演算子のtrue文のところは()が入りません、覚えておくと役に立ちます。

全て同じ結果
if(i==5){puts("true");}else{puts("false");}
i==5?puts("true"):puts("false");
puts(i==5?"true":"false");

論理演算子の仕様

論理演算子は左を判断したあとに右を判断します。
AND演算子は左側がfalseの時、右側を評価しません。
OR演算子は左側がtrueの時、右側を評価しません。
なのでif文と同じ使い方が出来ます。

イコールの時
if(i==5){puts("true");}
i==5&&puts("true");
ノットイコールの時
if(i!=5){puts("false");}
i==5||puts("false");

遂に100byteを切る

今回はif文を三項演算子に変更します。

139byte
i;main(){
    for(;++i<101;){
        i%15==0?printf("FizzBuzz\n")
            :i%3==0?printf("Fizz\n")
            :i%5==0?printf("Buzz\n")
            :printf("%d\n",i);
    }
}

さらにprintfの中に式をぶっこみます。
for文は一行ならブレースが要らないのでそこも省略し、改行を消します。

99byte
i;main(){
    for(;++i<101;)
        printf(i%15==0?"FizzBuzz\n":i%3==0?"Fizz\n":i%5==0?"Buzz\n":"%d\n",i);
}
94byte
i;main(){for(;++i<101;)printf(i%15==0?"FizzBuzz\n":i%3==0?"Fizz\n":i%5==0?"Buzz\n":"%d\n",i);}

100byteを切りましたね!まだまだ詰めていきます。

ド・モルガンの法則、true falseについて

ド・モルガンの法則

ド・モルガンの法則
!(P || Q) == !P && !Q
!(P && Q) == !P || !Q

ド・モルガンの法則ってどう使うの?と思ったあなた。

全て同じ
!(P != 0 && Q != 0)
!(!(P == 0 || Q == 0))
P == 0 || Q == 0

ド・モルガンの法則を使用するとコードがスッキリするので普段使いも出来ます!

条件式の仕様について

条件式は0ならfalse!0ならtrue
P!=5とは、P5以外ならtrue、要するにP5ならfalse
P-500false、要するにP!=5P-5が同じ。

全て同じ
P==5&&puts("")
P!=5||puts("")
P-5||puts("")
全て同じ
P==0?true:false
P!=0?false:true
P?false:true

このようにド・モルガンの法則を利用したり、条件式の仕様を理解する事でコードが短くなります。

今回のコードでは

printf(i%15==0?"FizzBuzz\n":i%3==0?"Fizz\n":i%5==0?"Buzz\n":"%d\n",i);

中の三項演算子でド・モルガンの法則をしてみます。
一旦、理解し難いのでif文に戻します。

if (i % 15 == 0) {
    printf("FizzBuzz\n");
} else if (i % 3 == 0) {
    printf("Fizz\n");
} else if (i % 5 == 0) {
    printf("Buzz\n");
} else {
    printf("%d\n", i);
}

ド・モルガンの法則でnotにしてみます。

if (i % 15 != 0) {
    if (i % 3 != 0) {
        if (i % 5 != 0) {
            printf("%d\n", i);
        } else {
            printf("Buzz\n");
        }
    } else {
        printf("Fizz\n");
    }
} else {
    printf("FizzBuzz\n");
}

!=00じゃない場合はtrue、なので!=0を消しても動きます。

if (i % 15) {
    if (i % 3) {
        if (i % 5) {
            printf("%d\n", i);
        } else {
            printf("Buzz\n");
        }
    } else {
        printf("Fizz\n");
    }
} else {
    printf("FizzBuzz\n");
}

三項演算子に戻します。

i%15?i%3?i%5:printf("%d\n",i):printf("Buzz\n"):printf("Fizz\n"):printf("FizzBuzz\n")

printfに入れ直します。

printf(i%15?i%3?i%5?"%d\n":"Buzz\n":"Fizz\n":"FizzBuzz\n",i);

更に減ったコード

85byteまで減りました。

85byte
i;main(){for(;++i<101;)printf(i%15?i%3?i%5?"%d\n":"Buzz\n":"Fizz\n":"FizzBuzz\n",i);}

1byte減らすのに頭を使う

ここから先はとても分かりにくく、難しくです。
むしろ、ここからが本番です。頑張りましょう。

15ではなくす

最初の方に3かつ5で割れる時、実質15で割れる時と言いました。
確かに&&を使うなら15にしたほうが短いです、ですが下のようにするとどうでしょう?

3で割れて5で割れるFizzBuzz
3で割れて5で割れないFizz
3で割れずに5で割れるBuzz
3で割れずに5で割れない数字。

こうすると15&&使ってないので1byte短く出来ます!

アルゴリズムを作り直す

同じく理解し難いのでif文に戻します。

if (i % 15) {
    if (i % 3) {
        if (i % 5) {
            printf("%d\n", i);
        } else {
            printf("Buzz\n");
        }
    } else {
        printf("Fizz\n");
    }
} else {
    printf("FizzBuzz\n");
}

並び替えます。

if (i % 3) {
    if (i % 5) {
        printf("%d\n", i);
    } else {
        printf("Buzz\n");
    }
} else {
    if (i % 5) {
        printf("Fizz\n");
    } else {
        printf("FizzBuzz\n");
    }
}

三項演算子に戻し、printfに入れ直します。

printf(i%3?i%5?"%d\n":"Buzz\n":i%5?"Fizz\n":"FizzBuzz\n",i);

1byte減りました

84byte
i;main(){for(;++i<101;)printf(i%3?i%5?"%d\n":"Buzz\n":i%5?"Fizz\n":"FizzBuzz\n",i);}

別解

改行するのに通常\nを使いますが、putsは自動的に改行をしてくれるので、putsで何も出力しなければただ改行します。
printfをしたあとにputsで何も出力しなければ、printfのなかでわざわざ\nを4回も書かなくて済みます。
今回はbyte数が同じですが、場合によっては短くなります。

84byte
i;main(){for(;++i<101;puts(""))printf(i%3?i%5?"%d":"Buzz":i%5?"Fizz":"FizzBuzz",i);}

FizzBuzzを省略したい

printf(i%3?i%5?"%d\n":"Buzz\n":i%5?"Fizz\n":"FizzBuzz\n",i);

FizzBuzzが2回書いてあるのを省略したくありませんか?
頑張って省略してみます。

2回出力にしてFizzBuzzを分割する

if文に戻します。

if (i % 3) {
    if (i % 5) {
        printf("%d\n", i);
    } else {
        printf("Buzz\n");
    }
} else { // ← ここ
    if (i % 5) {
        printf("Fizz\n");
    } else {
        printf("FizzBuzz\n");
    }
}

ここのelseで分割出来そうじゃないですか?
分割してみます。

if (i % 3) {
    if (i % 5) {
        printf("%d", i);
    } else {
        printf("");
    }
} else {
    printf("Fizz");
}

if (i % 5) {
    puts("");
} else {
    puts("Buzz");
}

1回目のifFizzの方の処理をしていて、2回目のifBuzzの方の処理をしています。
詳しく説明します。

各パターンでの流れです。

FizzBuzzの場合

1回目のifでは、3で割れるのでFizzを出力します。
2回目のifでは、5で割れるのでBuzzを出力します。

Fizzの場合

1回目のifでは、3で割れるのでFizzを出力します。
2回目のifでは、5で割れないのでなにも出力しません。
putsで何も出力しないので改行だけされます。

Buzzの場合

1回目のifでは、3で割れなくて5で割れるのでなにも出力しません。
printfなので改行しません。
2回目のifでは、5で割れるのでBuzzを出力します。

数字の場合

1回目のifでは、3で割れなくて5で割れないので数字を出力します。
2回目のifでは、5で割れないのでなにも出力しません。

何も出力しないのを挟むことで、2回に出力を分割出来ました。

コードに戻してみる

まずは三項演算子に戻します。

i%3?i%5?printf("%d",i):printf(""):printf("Fizz");
i%5?puts(""):puts("Buzz");

次にprintf putsに入れ直します。

printf(i%3?i%5?"%d":"":"Fizz",i);
puts(i%5?"":"Buzz");

ほぼほぼ完成系

for(;;puts(i%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz",i);

forの間に入れることで;を1つ省略しています。

76byte
i;main(){for(;++i<101;puts(i%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz",i);}

極限まで減らす

もう減らせる場所がなさそうですが実はまだあります。

printf(0);

printf(0);とやると何も表示されません。
ですが何も出力していないから何も表示されていないのではなく、エラーが起きています。
実はprintfには戻り値があります。戻り値は出力された文字数で、エラーの場合は負の値が返されます。

int i = printf("abc\n");
printf("%d\n", i); // 4

int j = printf(0);
printf("%d\n", j); // -1

int k = printf(0, "abc\n");
printf("%d\n", k); // -1

printf_error.PNG

なので今回は""0に変えます、これで1byte。

Before
printf(i%3?i%5?"%d":"":"Fizz",i);
After
printf(i%3?i%5?"%d":0:"Fizz",i);

iのインクリメント

グローバル変数の型を省略するとint型になり、初期値を省略すると0になるというのは、先程説明しました。
実は初期値を1にする方法もあります。

main(i){printf("%d",i);} // 1

mainの第1引数はargcです。argcはコマンドラインに記述されたパラメータの数を格納します。
プログラム自体も数えられるので、引数を渡さない場合1になります。
初期値が1で行けるなら下のほうが1byte短いです。

初期値が0
i;main(){}
初期値が1
main(i){}

引数の数を増やすとargcの数が増えます。

main(i){printf("%d",i);}

argc.PNG

今まではiの初期値が0で、インクリメントしたあとに条件判断でした、なのでiの初期値を1にして、条件判断した後にインクリメントすれば、1byte短く出来ます。
++i<101i++<101にしてもprintfの中身でiを使用しているので駄目です、全ての処理をした後にインクリメントしなければなりません。
printfputsを分割したのでputsの条件判断の後にインクリメントすれば、全ての処理をした後にインクリメント出来ます!

Before
i;main(){for(;++i<101;puts(i%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz",i);}
After
main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz",i);}

完成

お疲れ様です。
長い戦いがこれで終了です。
今までを振り返りながら見ると完成したコードは自明です。

74byte
main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":0:"Fizz",i);}

最少は73byteなんですが自分の環境では自分の環境だと上手く動きませんでした。(gcc version 6.3.0)

73byte
main(i){for(;i<101;puts("Buzz"-i*i++%5))printf(i%3?i%5?"%d":0:"Fizz",i);}

最後に

1つ1つ丁寧に説明したらとても長くなってしまいました。
これをきっかけに是非codegolfに挑戦してみて下さい。
色んなFizzBuzzのcodegolfが見れるのでこちらの記事も是非見て下さい。
FizzBuzzを1byteで実装する

参考文献

ShortCoding職人達の技法

smicle
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away