BrainFuck で FizzBuzz - にせねこnotes

BrainF*ck で FizzBuzz を出力するプログラムを書いた。
簡単の為に100までで、"001, 002, Fizz, 004, …(中略)…, 98, Fizz, Buzz, "
という感じに出力されるようにして、コードは以下。あまり洗練されてないのはご愛嬌ということで。
バッファオーバーラン／アンダーランを使ってないので処理系にもやさしい。

コード

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

出力

001, 002, Fizz, 004, Buzz, Fizz, 007, 008, Fizz, Buzz, 011, Fizz, 013, 014, FizzBuzz, 016, 017, Fizz, 019, Buzz, Fizz, 022, 023, Fizz, Buzz, 026, Fizz, 028, 029, FizzBuzz, 031, 032, Fizz, 034, Buzz, Fizz, 037, 038, Fizz, Buzz, 041, Fizz, 043, 044, FizzBuzz, 046, 047, Fizz, 049, Buzz, Fizz, 052, 053, Fizz, Buzz, 056, Fizz, 058, 059, FizzBuzz, 061, 062, Fizz, 064, Buzz, Fizz, 067, 068, Fizz, Buzz, 071, Fizz, 073, 074, FizzBuzz, 076, 077, Fizz, 079, Buzz, Fizz, 082, 083, Fizz, Buzz, 086, Fizz, 088, 089, FizzBuzz, 091, 092, Fizz, 094, Buzz, Fizz, 097, 098, Fizz, Buzz,

実際に実行してみたい人はこちらにJavascript インタプリタがあります。

BrainF*ck についてはこちらに、 FizzBuzz についてはこちらに詳しいので知らない方は参照してね。
また、 BrainFuck プログラムのテクニックはこちらやこちらに詳しいので詳しく勉強したい人にはおすすめ。

以下能書き

さて、 FizzBuzz では、数をカウントアップすることと、その数が3の倍数か、5の倍数であるかを判定することが必要。倍数の判定には、剰余を使うと便利だけど、 BrainF*ck にはそんな気の利いた命令は無いので、「2、1、0、2、1、0、2、1、0、…」とか「4、3、2、1、0、4、3、2、1、0、…」と数えて、0の時に Fizz または Buzz を出力するようにしてみた。

変数に名前を付ける

初めにプログラムするときに分かりやすいように配列に名前を付けておく(プログラムしながら決めたりもする。)
(Counter)(buf1)(buf2)(flag)(cdown3)(cdown5)(fbflag)(1の位)(10の位)(100の位)
それぞれ、配列の1、2、3、4、5、6、7、8、9番目に対応する。以下名前にて表記。
ポインタを移動したとき等適宜変数の名前を書いて、コードを追いやすくした(これがないと無理…)。
(Counter)が全体を100回繰り返す為のもの。(buf1)、(buf2)は数値の比較等に使う。(flag)は数値を比較する際にフラグとして使い、(cdown3)、(cdown5)はそれぞれ3、5の倍数の判別用。(fbflag)は、3の倍数でも5の倍数でもない時に数字を出力する為。あとは見て分かるよね。という感じ。

まず、100回繰り返すところを作る

//100回繰り返し
(Counter)>(buf1)++++++++++[<(Counter)++++++++++>(buf1)-]   //(Counter) = 100;
/*ここで初期化*/
<(Counter)[            //(Counter)が0になるまで繰り返す

    /*ここにプログラム*/

(Counter)-]            //(Counter)から1引く

これで /*ここにプログラム*/ 部分が100回繰り返されるようになる
最後の(Counter)の所は直前でポインタがずれるかもしれないので、適宜調整する必要あり。

擬似コードで書くと

for(Counter = 100; Counter != 0; Counter--){ /*ここにプログラム*/ }

という感じ。

次にカウントアップするとこを作る

//(1の位)に1足し、(1の位)が10になったら(1の位)を0にして(10の位)に1足す。要するに繰り上がり。
    >>>>>>>(1の位)+                  //(1の位)に1足す

    //(1の位)を(buf1)にコピーする。
    (1の位)[<<<<<(buf2)+<(buf1)+>>>>>>(1の位)-]    //(1の位)を(buf1)、(buf2)に移す
    <<<<<(buf2)[>>>>>(1の位)+<<<<<(buf2)-]         //(buf2)を(1の位)に移す

    //(1の位)からコピーした(buf1)が10であるか判定。
    //(buf2)=10から(buf1)だけ引いて0であるかを調べる
    (buf2)++++++++++                 //(buf2)=10
    <(buf1)[>(buf2)-<(buf1)-]        //(buf2) = (buf2) 引く (buf1)

    //もし(buf2)が0なら、(1の位)を0にし(10の位)に1足す
    //0以外なら角括弧内を実行、というものなので、0の時実行させるには反転させる必要がある
    >>(flag)+                        //(flag)=1
    <(buf2)[>(flag)[-]<(buf2)[-]]    //if (buf2)!=0 then (flag)=0
    >(flag)[

        //(1の位)が10だった時の操作。

        >>>>(1の位)[-]                    //(1の位)=0
        >(10の位)+                        //(10の位)足す1

    <<<<<(flag)-]

擬似コードだと

(1の位)++;
if (1の位)==10 { (1の位)=0; (10の位)++; }

(10の位)が10になって繰り上がりが必要かもしれないので処理をする
だいたい(1の位)と同じなのでコピペしてポインタの関係だけ調整すればいい

//(10の位)が10だったら(10の位)を0にして(100の位)に1足して繰り上げる

    //(10の位)を(buf1)にコピーする。
    >>>>>(10の位)[<<<<<<(buf2)+<(buf1)+>>>>>>>(1の位)-]    //(10の位)を(buf1)、(buf2)に移す
    <<<<<<(buf2)[>>>>>>(10の位)+<<<<<<(buf2)-]             //(buf2)を(10の位)に移す

    //(10の位)からコピーした(buf1)が10であるか判定。
    //(buf2)=10から(buf1)だけ引いて0であるかを調べる
    (buf2)++++++++++                     //(buf2)=10
    <(buf1)[>(buf2)-<(buf1)-]            //(buf2) = (buf2) 引く (buf1)

    //もし(buf2)が0なら、(1の位)を0にし(10の位)に1足す
    >>(flag)+                            //(flag)=1
    <(buf2)[>(flag)[-]<(buf2)[-]]        //if (buf2)!=0 then (flag)=0
    >(flag)[

        //(1の位)が10だった時の操作。
        >>>>>(10の位)[-]                 //(10の位)=0
        >(100の位)+                      //(100の位)足す1

    <<<<<<(flag)-]

擬似コードは

if (10の位)==10 { (10の位)=0; (100の位)++; }

100までなのでこれで問題なし。

3の倍数なら Fizz 、5の倍数なら Buzz を出力

3の倍数や5の倍数を判別するために、プログラムの最初に
(cdown3)=3; (cdown5)=5;
となるように初期化。全体の100回の繰り返しの /*ここで初期化*/ の所に

>>>(cdown3)+++
>(cdown5)+++++
<<<<
<||
といれる。

以下、3の倍数であるかの判定
>||
    //3の倍数でも5の倍数でもないとき数字を出力するためにフラグ(fbflag)を立てる
    >>>(fbflag)+           //(fbflag)=1


    //3の倍数のとき
    //2、1、0、2、1、0、…と数える。0のとき3の倍数。
    <<(cdown3)-            //(cdown3)から1引く

    //もし3の倍数なら( (cdown3)==0 なら)、 Fizz を出力し、 (fbflag)を0にする
    //(cdown3)を(buf1)にコピー
    (cdown3)[<<(buf2)+<(buf1)+>>>(cdown3)-]        //(cdown3)を(buf1)、(buf2)に移す
    <<<(buf1)[>>>(cdown3)+<<<(buf1)-]              //(buf1)を(cdown3)に移す

    //(buf2)の値が0でないなら(flag)=1
    >>(flag)+                            //(flag)=1
    <(buf2)[>(flag)[-]<(buf2)[-]]        //(buf2)!=0ならflag=0
    >(flag)[            //(flag)=0なら(cdown3)を3にしてFizz出力

        >(cdown3)+++            //(cdown3)=3
                                //Fizz出力、(buf1)(buf2)を使う。(buf1)は最後に0にする
        <<(buf2)+++++++[<++++++++++>-]<.>+++++[<+++++++>-]<.>+++[<+++++>-]<++..(buf1)[-]
        >>>>>(fbflag)[-]        //(fbflag)=0

    <<<(flag)-]

擬似コード

(fbflag)=1;
(cdown3)--;
if (cdown3)==0 { print("Fizz"); (fbflag)=0; }

5の倍数であるかの判定も同様に

    //5の倍数のとき
    //4、3、2、1、0、4、3、2、1、0、…と数える。0のとき5の倍数。
    >>(cdown5)-                //(cdown5)から1引く

    //もし3の倍数なら( (cdown5)==0 なら)、 Fizz を出力し、 (fbflag)を0にする
    //(cdown5)を(buf1)にコピー
    (cdown5)[<<<(buf2)+<(buf1)+>>>>(cdown5)-]    //(cdown3)を(buf1)、(buf2)に移す
    <<<(buf2)[>>>(cdown5)+<<<(buf2)-]            //(buf2)を(cdown5)に移す


    //(buf1)の値が0でないなら(buf5)=1
    >(flag)+                                //(flag)=1
    <<(buf1)[>>(flag)[-]<<(buf1)[-]]        //(buf2)!=0ならflag=0
    >>(flag)[            //(flag)=0なら(cdown5)を5にしてBuzz出力
        >>(cdown5)+++++            //(cdown5)=5
                                   //Buzz出力、(buf1)(buf2)を使う。
        <<<(buf2)++++++++[<++++++++>-]<++.>++++++[<++++++++>-]<+++.+++++..(buf1)[-]
        >>>>>(fbflag)[-]           //(fbflag)=0
    <<<(flag)-]

擬似コード

(cdown5)--;
if (cdown5)==0 { print("Buzz"); (fbflag)=0; }

もし3の倍数でも5の倍数でもない( (fbflag)==1 )場合、数字を出力する

    >>>(fbflag)[
        //数字0〜9に48を加えることでASCIIコードの0〜9にできる。
        >>>(100の位)
        ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++.    //数字を出力
        ---------- ---------- ---------- ---------- --------     //もとに戻す
        <(10の位)
        ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++.
        ---------- ---------- ---------- ---------- --------
        <(1の位)
        ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++.
        ---------- ---------- ---------- ---------- --------
    <(fbflag)-]

擬似コード

if (fbflag)==1{
    putchar( (100の位) + 48 );
    putchar(  (10の位) + 48 );
    putchar(   (1の位) + 48 );
    fbflag = 0;
}

区切りの文字を出力

    //コンマとスペースを使う。
    //コンマが44、スペースが32。(buf1) (buf2)を使って出力
    <<<<(buf2)++++[<(buf1)+++++++++++>(buf2)-]<(buf1).>(buf2)+++[<(buf1)---->(buf2)-]<.[-](buf1)

擬似コード

print(", ");

これであと調整して…

できた！

//100回繰り返し
(Counter)>(buf1)++++++++++[<(Counter)++++++++++>(buf1)-]   //(Counter) = 100;
>>>(cdown3)+++
>(cdown5)+++++
<<<<<(Counter)[            //(Counter)が0になるまで繰り返す

//カウントアップ部分
//(1の位)に1足し、(1の位)が10になったら(1の位)を0にして(10の位)に1足す。要するに繰り上がり。
    >>>>>>>(1の位)+                   //(1の位)に1足す

    //(1の位)を(buf1)にコピーする。
    (1の位)[<<<<<(buf2)+<(buf1)+>>>>>>(1の位)-]    //(1の位)を(buf1)、(buf2)に移す
    <<<<<(buf2)[>>>>>(1の位)+<<<<<(buf2)-]         //(buf2)を(1の位)に移す

    //(1の位)からコピーした(buf1)が10であるか判定。
    //(buf2)=10から(buf1)だけ引いて0であるかを調べる
    (buf2)++++++++++                 //(buf2)=10
    <(buf1)[>(buf2)-<(buf1)-]        //(buf2) = (buf2) 引く (buf1)

    //もし(buf2)が0なら、(1の位)を0にし(10の位)に1足す
    //0以外なら角括弧内を実行、というものなので、0の時実行させるには反転させる必要がある
    >>(flag)+                        //(flag)=1
    <(buf2)[>(flag)[-]<(buf2)[-]]    //if (buf2)!=0 { (flag)=0 }
    >(flag)[

        //(1の位)が10だった時の操作。

        >>>>(1の位)[-]               //(1の位)=0
        >(10の位)+                   //(10の位)足す1

    <<<<<(flag)-]


//(10の位)も必要なら繰り上げる
//(10の位)が10だったら(10の位)を0にして(100の位)に1足す

    //(10の位)を(buf1)にコピーする。
    >>>>>(10の位)[<<<<<<(buf2)+<(buf1)+>>>>>>>(1の位)-]   //(10の位)を(buf1)、(buf2)に移す
    <<<<<<(buf2)[>>>>>>(10の位)+<<<<<<(buf2)-]            //(buf2)を(10の位)に移す

    //(10の位)からコピーした(buf1)が10であるか判定。
    //(buf2)=10から(buf1)だけ引いて0であるかを調べる
    (buf2)++++++++++                     //(buf2)=10
    <(buf1)[>(buf2)-<(buf1)-]            //(buf2) = (buf2) 引く (buf1)

    //もし(buf2)が0なら、(1の位)を0にし(10の位)に1足す
    >>(flag)+                            //(flag)=1
    <(buf2)[>(flag)[-]<(buf2)[-]]        //if (buf2)!=0 then (flag)=0
    >(flag)[

        //(1の位)が10だった時の操作。
        >>>>>(10の位)[-]                 //(10の位)=0
        >(100の位)+                      //(100の位)足す1

    <<<<<<(flag)-]

//3の倍数なら Fizz 、5の倍数なら Buzz を出力
    //3の倍数でも5の倍数でもないとき数字を出力するためにフラグ(fbflag)を立てる
    >>>(fbflag)+           //(fbflag)=1

    //3の倍数のとき
    //2、1、0、2、1、0、…と数える。0のとき3の倍数。
    <<(cdown3)-            //(cdown3)から1引く

    //もし3の倍数なら( (cdown3)==0 なら)、 Fizz を出力し、 (fbflag)を0にする
    //(cdown3)を(buf1)にコピー
    (cdown3)[<<(buf2)+<(buf1)+>>>(cdown3)-]        //(cdown3)を(buf1)、(buf2)に移す
    <<<(buf1)[>>>(cdown3)+<<<(buf1)-]              //(buf1)を(cdown3)に移す

    //(buf2)の値が0でないなら(flag)=1
    >>(flag)+                            //(flag)=1
    <(buf2)[>(flag)[-]<(buf2)[-]]        //(buf2)!=0ならflag=0
    >(flag)[            //(flag)=0なら(cdown3)を3にしてFizz出力

        >(cdown3)+++            //(cdown3)=3
                                //Fizz出力、(buf1)(buf2)を使う。(buf1)は最後に0にする
        <<(buf2)+++++++[<++++++++++>-]<.>+++++[<+++++++>-]<.>+++[<+++++>-]<++..(buf1)[-]
        >>>>>(fbflag)[-]        //(fbflag)=0

    <<<(flag)-]


    //5の倍数であるかの判定も同様に
    //4、3、2、1、0、4、3、2、1、0、…と数える。0のとき5の倍数。
    >>(cdown5)-                //(cdown5)から1引く

    //もし3の倍数なら( (cdown5)==0 なら)、 Fizz を出力し、 (fbflag)を0にする
    //(cdown5)を(buf1)にコピー
    (cdown5)[<<<(buf2)+<(buf1)+>>>>(cdown5)-]    //(cdown3)を(buf1)、(buf2)に移す
    <<<(buf2)[>>>(cdown5)+<<<(buf2)-]            //(buf2)を(cdown5)に移す


    //(buf1)の値が0でないなら(buf5)=1
    >(flag)+                                //(flag)=1
    <<(buf1)[>>(flag)[-]<<(buf1)[-]]        //(buf2)!=0ならflag=0
    >>(flag)[            //(flag)=0なら(cdown5)を5にしてBuzz出力
        >>(cdown5)+++++            //(cdown5)=5
                                   //Buzz出力、(buf1)(buf2)を使う。
        <<<(buf2)++++++++[<++++++++>-]<++.>++++++[<++++++++>-]<+++.+++++..(buf1)[-]
        >>>>>(fbflag)[-]           //(fbflag)=0
    <<<(flag)-]

//3の倍数でも5の倍数でもない( (fbflag)==1 )場合、数字を出力する
    >>>(fbflag)[
        //数字0〜9に48を加えることでASCIIコードの0〜9にできる。
        >>>(100の位)
        ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++.    //数字を出力
        ---------- ---------- ---------- ---------- --------     //もとに戻す
        <(10の位)
        ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++.
        ---------- ---------- ---------- ---------- --------
        <(1の位)
        ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++.
        ---------- ---------- ---------- ---------- --------
    <(fbflag)-]

//区切りの文字を出力
    //コンマとスペースを使う。
    //コンマが44、スペースが32。(buf1) (buf2)を使って出力
    <<<<(buf2)++++[<(buf1)+++++++++++>(buf2)-]<(buf1).>(buf2)+++[<(buf1)---->(buf2)-]<.[-](buf1)

<(Counter)-]        //(Counter)から1引く

これからコメントやインデント等を取って整形すると冒頭のものになります。

擬似コード

(cdown3) = 3;
(cdown5) = 5;
for(Counter = 100; Counter != 0; Counter--){
    (1の位)++;
    if  (1の位)==10 {  (1の位)=0;  (10の位)++; }
    if (10の位)==10 { (10の位)=0; (100の位)++; }
    (fbflag) = 1;
    (cdown3)--;
    if (cdown3)==0 { print("Fizz"); (fbflag)=0; }
    (cdown5)--;
    if (cdown5)==0 { print("Buzz"); (fbflag)=0; }

    if (fbflag)==1{
        putchar( (100の位) + 48 );
        putchar(  (10の位) + 48 );
        putchar(   (1の位) + 48 );
        fbflag = 0;
    }
}

擬似コードだけ見れば分かりやすいんだけどなー。(笑)

これを、数字の先頭の0を出力しないように改良したりするともっと良いと思うけど、飽きたので、もういいや。