Brainfuckでfizzbuzzをする

皆さん、fizzbuzzしてますか。
私はたまにしてます。
fizzbuzzはループや条件分岐、算術演算などプログラミングをする上で必要となる基礎知識を簡単に確認できます。

fizzbuzzを分析する

さて、fizzbuzzをBrainfuckで書くためにまずはfizzbuzzを分析してみます。

fizzbuzzことfizzbuzzゲームは以下のようなプログラムだと定義します。

• fizzbuzzゲームでは数を使う
• fizzbuzzゲームの数は1からスタートする
• fizzbuzzゲームの数は1ずつ増える
• 数が3の倍数ではfizzを表示する
• 数が5の倍数ではbuzzを表示する
• 数が15の倍数ではfizzbuzzを表示する
• それ以外(3の倍数でも5の倍数でもない)ではその数を表示する。

今回はプログラムの終了条件については設けず、ターミナルで^Cとかしない限り止まらないやつにします。

とりあえずソースコードのファイル名はfizzbuzz.bfとでもして、中身を考えていきましょう。
さて、皆様にあらかじめ謝っておきますが、難しいです。

それでは考えていきます。
まず、Brainfuckは複雑になればなるほど構造が大切になります。
だから、初めは構造から考えていきます。

まず初めにこのプログラムは際限なく動くことが要求されます。
つまり、値が増え続けるわけです。
しかしながら、Brainfuckの配列はbyte配列でそれぞれの要素には00~FFまでの値しか入れることができません。
つまり、それ以上の情報を保持するためには、数値を記憶する部分を可変長にする必要があります。
そして、配列は右方向に十分長いので右方向に伸びるようにしていきます。

また、要素に入っている数字を二桁の数字にするのは簡単ではありません。(一桁の数字の場合は簡単です、安心してください。)
なのでそれぞれの要素には10進数の1桁の数字00~09が入ることが望ましいです。

さらに、ポインタが移動するわけなのでポインタの周囲には常に計算スペースが欲しいです。
計算スペースはプログラムの規模によってどの程度用意するかは変わりますが、今回は値の確認と桁あがりに関する計算くらいだと思うのでそれぞれの間に値がはっきりしたスペースを1つ分用意したらいいでしょう。

今回は桁上がりを行うといった別の構造プログラムが含まれています。
だから桁上がりに必要な構造を考えていきましょう。

桁上がりを分析する。

桁上がりの定義ですが、たとえば0Aなら値を00にして、適当な位置に桁上がりをしたことを示すキャリーフラグを設けたら良いでしょう。
ただしBrainfuckで条件分岐ができる命令は[,]に限られています。
さらに条件は値が00かそれ以外かです。

とりあえず、あらかじめ00~0Aまでの適当な値が入ってると仮定してコードを書いていきます。

{初期状態で値は不明}
----------

このように書くことで元のポインタの指す値が0Aの時だけ00になり、分岐を行うことができます。

が、そうするとポインタの指す値が00なので[と]の間のコードはスキップされてしまいます。
それではこの問題はどのように解決しましょうか。
そう、notですね。

ではnotの構造を考えていきましょうか！

notの構造

notに関してなのですが、notする対象の値を再利用することを考えて、元の値の形をある程度残した形で実現したいと思います。
要するに、notする対象とは別の場所に結果を出力したいわけです。

ZZ = 00 ~ FF
fg = 00 , 01
|NN|fg|
こんな感じ？

さて、ここである面白い構造を紹介します。

[>]

これはポインタの指す値が00でない限り際限なく右へとポインタを移動させるコードです。
この構造には、実行開始時点のポインタ位置と終了時のポインタ位置が必ずしも一致しないという欠点はあるものの、条件分岐が可能な[,]も含まれており、使えそうです。
では、終了位置を一致させるにはどうしたら良いでしょうか。
そうです、開始位置から終了位置までに00がないことを保証した上で、終了させたい位置に意図的に00となる要素を配列に用意したら良いわけです。

|A1|B3|72|82|00|
  ^[>]

|A1|B3|72|82|00|
              ^ 

さて、以上を踏まえてnotの構造を考えていきましょう。

ZZ = 00 ~ FF
...|ZZ|...
     ^

まず、[>]を使うと仮定して(使わないと値を直接いじる手段以外になくなり元の値を保持できません)、ループを同じところに止めるための00を用意します。

ZZ = 00 ~ FF
...|ZZ|00|...
     ^

これにより[>]を使って値を揃える準備はできました。
しかしながら、それではZZの値が00の時に[>]が動きません。
そんな時で+か-で00では無い値にしてしまいましょう。

でも待ってください、今この状態ですよね。

ZZ = 00 ~ FF
...|ZZ|00|...
     ^

ここで値を加減算してしまうとZZが00では無い場合でも影響が出てしまいます。
さて、どうしましょうか。

「ZZが00では無い場合」に影響が出たら困るんですよね。
それなら[<]を使えばいいのです。
[<]を使うのであれば動作を止めるためのストッパー、00が左にも欲しいですね。

...|00|ZZ|00|...
        ^

さて、以上を以下のコードを考えてみます。

[<]+[>]

これが終わった後の状態はそれぞれ以下の通りです。

ZZ = 00の場合
...|00|01|00|...
           ^

ZZ = 00以外の場合
...|01|ZZ|00|...
           ^

ここでZZの動きに注目すると、ZZが00な場合を除いてZZの値をそのまま保持できています。
ZZが00の場合はいずれにせよ条件分岐し、分岐するということはその値が00なのは明らかであり、分岐の内側で「もともとここは00だった」という点に注意さえしたら良いです。

ただ、今のままだとZZが01となっているので最後に<<-をくっつけましょう。

[<]+[>]<<-

そうするとこのコードの終了時の状態は以下のようになります。

ZZ = 00の場合
...|FF|01|00|...
     ^

ZZ = 00以外の場合
...|00|ZZ|00|...
     ^

一応FFでも条件分岐はできますがどうせなら01になるようにしましょう。

[<]-[>]<<+

コード終了時の状態は以下の通りです。

ZZ = 00の場合
...|01|00|00|...
     ^

ZZ = 00以外の場合
...|00|ZZ|00|...
     ^

さて、notができました。
桁上がの構造に戻りましょう。

notは両サイドに00が必要な構造でした。

その機能を要求する桁上がりも同様に最低でも両サイドに00が必要な構造になります。

一桁の桁上がり(0から9までのカウンター)

それではとりあえず01から09までをカウントアップし、その値を出力するカウンターを作りましょう
この時、0Aに到達した段階で繰り上がりが発生し、値が00となり、カウンターが終了するものとします。

期待する出力はこんな感じです。

1234567890

このような出力を満たすプログラムを考えていきましょう。

{ループ条件を設定}
+
[
{ポインタの移動}
>>
{カウンタの値を加算}
+
{ポインタの指す値が0Aなら00になる}
----------
{00なら分岐}
[<]-[>]<<+[
->+
{分岐した値が0Aであったことに着目し、分岐後に00となるように辻褄を合わせる}
----------
{ループ条件を00に変更}
<<->>
<]>
{減算してた値を復元}
++++++++++
{文字表示用に値を加算}
++++++++++++++++++++++++++++++++++++++++++++++++
.
{加算してた値を元に戻す}
------------------------------------------------
{ポインタを移動}
<<
]

コメントや><や+-などの無駄なコードを除くと、このようになります。

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

これが桁上がりの基本形となり、今回のfizzbuzzの鍵をも握ります。
カウンタの値から数値が3の倍数や5の倍数であることを確認するのは難しいですが、10進数のカウンターと連動するような3進数、5進数のカウンターを作り、その値が00となる時にその数値の倍数と見做してfizzやbuzzを出力させたら良いのです。

{とりあえず64までの数字で試す}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[
{カウントダウン}
-
>>
{3の倍数}
--
[<]-[>]<<+[->--<]>
+++
>>
{5の倍数}
----
[<]-[>]<<+[->----<]>
+++++
<<
{n mod 3の表示}
++++++++++++++++++++++++++++++++++++++++++++++++
.
------------------------------------------------
>>
{n mod 5を表示}
++++++++++++++++++++++++++++++++++++++++++++++++
.
------------------------------------------------
<<<
{ここには本来00が入ってるので、ここを利用して改行を表示させる}
++++++++++
.
----------
<
]

出力はこんな感じです。

11
22
03
14
20
01
12
23
04
10
21
02
13
24
00
11
22
(以下略)

ここまできたら何となくfizzbuzzができそうに見えますよね。

可変長の桁上がりを分析する

fizzbuzzを始める前に桁上がりのコードは書きました。
しかし、可変長の桁上がりの実装はできていません。

それを実装するにはいくつかの手段があるように思いますが

とりあえずBrainfuckの配列がこのような構造であると期待して考えていきます。

ZZ = 00 ~ FF
|00|00|01|ZZ|01|ZZ|01|ZZ|...|01|ZZ|01|00|00|00|...
  ^

これは桁上がりのしゅりのためにZZの値が00である必要があるといったものに矛盾しているように感じますが、桁上がり処理を行う時にZZの両端が00になればいいだけなので適当な場所で-を行ってしまえば問題はありません。

そして、このZZの周りにある01が続く場所まで桁数があると期待します。

それではコードを書いていきましょう。

{ループに入るためのフラグ}
+
[
{フラグが邪魔なので一時的に除去}
-
>>
{1の位のZZの左側を01にする}
+
{ZZの左側のフラグを確認、01なら桁上がり計算に組み込む。}
[
{ZZの左側の01を00に変更}
-
>>
{ZZの右側を00に設定(普段は01だが桁上がりの時だけ00)}
[-]
<
{ZZの値で桁上がり処理}
---------
[<]-[>]<<+[->--------->
{桁上がりフラグ(ZZの右側)}
+
<<]>
++++++++++
{ZZの左側の01を復元}
<+>>
]
{ZZの左隣は01なのでそれに再設定}
+
{可変長桁上がり処理で一番高い位の値ZZの左側の値01へと移動する}
[>>]<<<<
{ZZの左側の値が01である限りは可変長桁上がり処理の内部なので数値を高い位から順に出力}
[>++++++++++++++++++++++++++++++++++++++++++++++++
.
------------------------------------------------<<<]
{桁上がりの先頭のZZの}左側は最初は01ではなく00だったのでその辻褄を合わせる
>>-<<
{改行表示}
++++++++++
.
----------
{フラグを再設定}
+
]

結果だけ載せるとこんな感じになります。

(省略)
96
97
98
99
100
101
102
103
104
(省略)

このコードはいくつか効率的ではない箇所がありますが、その点に関しては気にしないでください。

その他の部分

fizzとbuzzを表示するコードはこの通りです。

fizz.bf

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++.+++.+++++++++++++++++..

buzz.bf

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++.+++++++++++++++++++.+++++..

fizzbuzzを出力する場合でも最初にfizzか否かを評価してbuzzか否かを順に評価することで結果的にはfizzbuzzと表示できるでしょう。

あとはこれらをがっしゃんこするだけです。
自分の目で確かめてください。

一応下に答えのコードを載せてはいますが、一つ一つ理解しないと動作を追うのは難しいと思います。
自分で書いていて満足のfizzbuzzができたら確認してみてください。

答えのコード

fizzbuzz.bf

{改行コード兼ループフラグ}
++++++++++
[
    >>>>
    {3の倍数判定}
    --[<]-[>]<<+[->--<<+>]>+++
    >>
    {5の倍数判定}
    ----[<]-[>]<<+[->----<<<<<+>>>>]>+++++
    >>>
    {桁上がりフラグ}
    +
    [
        {フラグ関係を一度除去}
        [-]>>[-]<
        {桁上がり}
        ---------[<]-[>]<<+[->--------->+<<]>++++++++++
        <+>>
    ]
    {フラグ修正}
    +
    {先頭に戻る}
    [<<]<<<<
    {フラグ修正}
    +
    {fizzを表示}
    <[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++.+++++++++++++++++..-------------------------------------------------------------------------------------------------------------------------->[-]<]
    {buzzを表示}
    <[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++.+++++..-------------------------------------------------------------------------------------------------------------------------->>[-]<<]
    {fizzとbuzzのどちらも行われなかった場合、数字を表示}
    >>[->>>>>>->>[>>]<<[<++++++++++++++++++++++++++++++++++++++++++++++++.------------------------------------------------<]<<<<<<]<<<
    {改行を表示}
    .
]

コメントなし

fizzbuzz.bf

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