本稿は2023年9月版です。
2011年9月の初版（入力を受け付けず繰り返し回数を固定値 100 とした版）はこちらにあります。
FizzBuzz を Brainfuck で書いてみました。ソースコード
1から順に数え上げていき、3の倍数のとき “Fizz”, 5の倍数のとき “Buzz”, 15の倍数のとき “FizzBuzz” と言うゲームです。
「なるべく短く書く」「難解な言語で書く」など、屡々プログラミング技術を競うのに使われたりします。
本稿では、以下ようなプログラムを書くことにします。
十進法で表現した正整数値 N
末尾に改行等は付けず、EOF で終端する。
文字コードは ASCII とする。
100
1 から N までの整数を昇順に走査し、各整数についてその値に応じて以下に定める文字列を出力する。
文字列同士の間は空白文字で区切る。
文字コードは ASCII とする。
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz
たった8つの命令 + - > < [ ] . , だけで記述するプログラミング言語です。
命令は8つだけですが、これでもチューリング完全（普通のコンピュータで実行できるプログラムは全て記述できる）です。
| 命令 | C言語での表現 | 操作 |
|---|---|---|
| + | (*ptr)++; | ポインタの指す値に1を加える |
| - | (*ptr)--; | ポインタの指す値から1を減ずる |
| > | ptr++; | ポインタを右に1つ進める |
| < | ptr--; | ポインタを左に1つ進める |
| [ | while(*ptr){ | ポインタの指す値が 0 ならば、対応する ] までの間の命令を読み飛ばす |
| ] | } | ポインタの指す値が 0 以外ならば、対応する [ まで戻る |
| . | putchar(*ptr); | ポインタの指す値を出力する |
| , | *ptr = getchar(); | 入力を1バイト読んでポインタの指す先に格納する |
Brainfuck のプログラムは処理系に依って挙動が異なる点があります。
本稿では、以下の挙動を前提とします。（そうでない処理系については補足に記載します）
最初に、入力値 N を読み取ってメモリに格納しましょう。
入力値 N は、メモリ上に下図のような形で格納することにします。
ここでは例として N = 724 の場合を示しています。
各メモリ位置の値の意味は次の通りです。
| 位置 | 内容 |
|---|---|
| count | その桁の値です。（数字を表す ASCII コードではなく、整数値です） |
| next | 入力を読み込む際に、「次の1文字を読み込む」フラグ（読み込む場合は 1, 終了する場合は 0）として使用します。 |
| tmp | 計算の過程で一時的に使う変数です。使っていないときの値は 0 です。 |
入力値（上図で背景色を付けた部分）の桁数は可変なので、番兵を置いて入力値の範囲の両端を示します。
UFフラグについては次節で説明します。
入力値を読み込んで上図の形に格納する処理は、次の擬似コードの要領で行います。
function read_int(){
UFフラグ = 1
番兵A.count = 1
番兵A.next = 1
/* EOF に達するまで桁を進めつつ入力を読む */
for (現在の桁 = 1桁目; 前の桁.next == 1; 現在の桁 = 次の桁){
前の桁.next = 0
現在の桁.count = getchar() + 1 /* 入力が EOF のときに値が 0 になるように「+ 1」を付ける */
if (現在の桁.count != 0){ /* EOF でない */
現在の桁.count = 現在の桁.count - 1 - '0' /* 数字を整数値に変換 */
現在の桁.next = 1
}
}
/* 番兵Bをセット */
現在の桁.count = 1 /* この時点の「現在の桁」が番兵B */
}
これを Brainfuck で書くと、次のようになります。
（ソースコード中に現れる for や if 等の文字列は単なるコメントであり、Brainfuck の処理系には無視されます）
function read_int(){
+ /* UFフラグ = 1 */
>>+ /* 番兵A.count = 1 */
>>+ /* 番兵A.next = 1 */
/* EOF に達するまで桁を進めつつ入力を読む */
for [ /* この時点でポインタは「前の桁.next」を指している */
- /* 前の桁.next = 0 */
>>>,+ /* 桁を進め、一時的に「現在の桁.next」に getchar() + 1 を読み込む */
[-<+<+>>] /* next の値を count と tmp にコピー（next の値は 0 に戻る） */
if <[ /* tmp の値が 0 でないならば */
>+ /* next に 1 を立てる */
<[-] /* tmp を破壊する（こうしないとループから抜け出せない） */
<-------------------------------------------------> /* count から 49 (= 1 + '0') を減ずる */
]> /* この時点でポインタは「現在の桁.next」を指している */
]
/* 番兵Bをセット */
<<+
}
入力値 N の回数だけ繰り返し処理を行うため、「あと何回処理を行うのか」を数えておく必要があります。
本稿では、これを数えておくためのカウンタをイテレータと呼ぶことにします。
前節でメモリに格納した入力値 N の領域を、そのままイテレータとして使うことにします。（下図）
各メモリ位置の値の意味合いは前節とは若干異なります。
| 位置 | 内容 |
|---|---|
| count | その桁の値です。（数字を表す ASCII コードではなく、整数値です） |
| next | イテレータの各位を走査する際に、「次の位まで走査を進める」フラグ（進める場合は 1, 打ち切る場合は 0）として使用します。 |
| tmp | 計算の過程で一時的に使う変数です。使っていないときの値は 0 です。 |
上図で基準のポインタ位置として示しているのは、「毎回の繰り返し処理の開始/終了時には必ずこの位置にポインタを戻す」という位置です。
未使用領域は、後で使うために空けておきます。
イテレータは、「繰り返し処理の度に1ずつ減じて、0になったら繰り返し処理を止める」という使い方をします。
まずは、イテレータの値を1つ減ずる（デクリメント）方法を示します。
イテレータのデクリメントは、次の擬似コードの要領で行います。
まず「値が0でない最小の位」を探して1を減じ、それより下の各位（値が 0 である位）は全てその値を 9 にすれば OK です。
function decrement_iterator(){
/* 値が 0 でない最小の位までポインタを進める */
イテレータの1の位.next = 1
for (現在の位 = イテレータの1の位; 現在の位.next == 1; 現在の位 = 1つ上の位){
現在の位.next = 0
1つ上の位.next = 1
if (現在の位.count != 0){
1つ上の位.next = 0
}
}
/* 値が 0 でない最小の位の値を 1 つ減ずる */
現在の桁.count--
/* 番兵Bまでポインタを戻しつつ、途中の各位の値を 9 にする */
現在の位.next = 1
for (現在の位 = 1つ下の位; 1つ上の位.next == 1; 現在の位 = 1つ下の位){
1つ上の位.next = 0
現在の位.next = 1
if (現在の位.count != 0){ /* これが真となるのは「現在の位」が番兵Bであるときに限られる */
現在の位.next = 0
}
現在の位.count = 9
}
/* 番兵Bの値が破壊されたので修正する */
番兵B.count = 1
}
これを Brainfuck で書くと、次のようになります。
function decrement_iterator(){
/* 値が 0 でない最小の位までポインタを進める */
<<<<<<<<<<<+ /* イテレータの1の位.next = 1 */
for [ /* この時点でポインタは「現在の位.next」を指している */
- /* 現在の位.next = 0 */
<<[->+>+<<]>>[-<<+>>] /* count を tmp にコピー（途中 next に退避） */
<<<+ /* 1つ上の位.next = 1 */
if >>[ /* 現在の位.tmp != 0 ならば */
<<- /* 1つ上の位.next = 0 */
>>[-] /* 現在の位.tmp = 0（こうしないとループから抜け出せない） */
]<<
]
/* 値が 0 でない最小の位の値を 1 つ減ずる */
>-
/* 番兵Bまでポインタを戻しつつ、途中の各位の値を 9 にする */
>>+ /* 現在の位.next = 1 */
for [ /* この時点でポインタは「1つ上の位.next」を指している */
- /* 1つ上の位.next = 0 */
>>>+ /* 現在の位.next = 1 */
if <<[ /* 現在の位.count != 0 ならば */
>>- /* 現在の位.next = 0 */
<<- /* 現在の位.count = 0（こうしないとループから抜け出せない） */
]
+++++++++ /* 現在の位.count = 9 */
>>]
/* 番兵Bの値が破壊されたので修正する */
<<[-]+
/* ポインタを基準の位置に戻す */
>>>>>>>>>>
}
これを実行すると、724 だった値が 723 に更新されます。
続いて、イテレータの値が0に達したか否かを判定する方法を示します。
「判定の結果、0でなければ繰り返し処理をもう一度行う」という動作をさせたいので、判定結果は以下のように基準のポインタ位置にセットすることにします。
イテレータの値が既に0に達しているとき、デクリメント処理と同様に「値が0でない最小の位」を下位から順に探していくと、全ての位を素通りして番兵Aのところで止まります。
番兵Aの先には、最初にメモリの一番左に置いておいたUFフラグがあるので、これが立っていることを以て「イテレータの値は0である」と判定できます。
イテレータのゼロ判定は、次の擬似コードの要領で行います。
function detect_underflow(){
/* 値が 0 でない最小の位までポインタを進める */
イテレータの1の位.next = 1
for (現在の位 = イテレータの1の位; 現在の位.next == 1; 現在の位 = 1つ上の位){
現在の位.next = 0
1つ上の位.next = 1
if (現在の位.count != 0){
1つ上の位.next = 0
}
}
/* tmp の値（イテレータの値が 0 のときはUFフラグ）を上から順にコピーしていく */
1つ下の位.next = 1
for (現在の位 = 1つ下の位; 1つ上の位.next == 1; 現在の位 = 1つ下の位){
1つ上の位.next = 0
現在の位.next = 1
if (現在の位.count != 0){ /* これが真となるのは「現在の位」が番兵Bであるときに限られる */
現在の位.next = 0
}
現在の位.tmp = 1つ上の位.tmp
}
/* 番兵B.tmp の値の否定を基準のポインタ位置にセットする */
基準のポインタ位置 = 1
if (番兵B.tmp == 1){
基準のポインタ位置 = 0
}
}
これを Brainfuck で書くと、次のようになります。
function detect_underflow(){
/* 値が 0 でない最小の位までポインタを進める */
<<<<<<<<<<<+ /* イテレータの1の位.next = 1 */
for [ /* この時点でポインタは「現在の位.next」を指している */
- /* 現在の位.next = 0 */
<<[->+>+<<]>>[-<<+>>] /* count を tmp にコピー（途中 next に退避） */
<<<+ /* 1つ上の位.next = 1 */
if >>[ /* 現在の位.tmp != 0 ならば */
<<- /* 1つ上の位.next = 0 */
>>[-] /* 現在の位.tmp = 0（こうしないとループから抜け出せない） */
]<<
]
/* tmp の値（イテレータの値が 0 のときはUFフラグ）を上から順にコピーしていく */
+ /* 現在の位.next = 1 */
for [ /* この時点でポインタは「1つ上の位.next」を指している */
- /* 1つ上の位.next = 0 */
>>>+ /* 現在の位.next = 1 */
if <<[ /* 現在の位.count != 0 ならば */
>>- /* 現在の位.next = 0 */
<<- /* 現在の位.count = 0（こうしないとループから抜け出せない） */
]
<<[->>>+<<<] /* 現在の位.tmp = 1つ上の位.tmp */
>>>>]
/* 番兵B.tmp の値の否定を基準のポインタ位置にセットする */
>>>>>>>>+ /* 基準のポインタ位置 = 1 */
if <<<<<<<<<[ /* 番兵B.tmp == 1 ならば */
->>>>>>>>>-<<<<<<<<< /* 基準のポインタ位置 = 0 */
]>>>>>>>>>
}
ここまでで見てきたイテレータのデクリメント処理とゼロ判定処理は、共に「1の位から辿って値が0でない最小の位を探し、そこから下の位に戻りつつ値を書き換えていく」という形をしていました。
似たような処理を別々に行うのは無駄なので、両方同時に行うようにします。
function decrement_iterator_and_detect_underflow(){
/* 値が 0 でない最小の位までポインタを進める */
<<<<<<<<<<<+ /* イテレータの1の位.next = 1 */
for [ /* この時点でポインタは「現在の位.next」を指している */
- /* 現在の位.next = 0 */
<<[->+>+<<]>>[-<<+>>] /* count を tmp にコピー（途中 next に退避） */
<<<+ /* 1つ上の位.next = 1 */
if >>[ /* 現在の位.tmp != 0 ならば */
<<- /* 1つ上の位.next = 0 */
>>[-] /* 現在の位.tmp = 0（こうしないとループから抜け出せない） */
]<<
]
/* 値が 0 でない最小の位の値を 1 つ減じ、同時に上の位から tmp の値をコピーする */
>- /* 現在の位.count-- */
<<[->>>+<<<]>> /* 現在の位.tmp = 1つ上の位.tmp */
/* 番兵Bまでポインタを戻しつつ、途中の各位の値を 9 にする、同時に上の位から tmp の値をコピーする */
>>+ /* 現在の位.next = 1 */
for [ /* この時点でポインタは「1つ上の位.next」を指している */
- /* 1つ上の位.next = 0 */
>>>+ /* 現在の位.next = 1 */
if <<[ /* 現在の位.count != 0 ならば */
>>- /* 現在の位.next = 0 */
<<- /* 現在の位.count = 0（こうしないとループから抜け出せない） */
]
+++++++++ /* 現在の位.count = 9 */
<<[->>>+<<<]>> /* 現在の位.tmp = 1つ上の位.tmp */
>>]
/* 番兵Bの値が破壊されたので修正する */
<<[-]+>>
/* 番兵B.tmp の値の否定を基準のポインタ位置にセットする */
>>>>>>>>+ /* 基準のポインタ位置 = 1 */
if <<<<<<<<<[ /* 番兵B.tmp == 1 ならば */
->>>>>>>>>-<<<<<<<<< /* 基準のポインタ位置 = 0 */
]>>>>>>>>>
}
さて、FizzBuzz の肝は整数の数え上げです。
整数を 1, 2, 3, ... と数え上げるためのカウンタは、次のような形で表現することにします。
上の図では、カウンタには 123 という値が格納されています。
各メモリ位置の値の意味は次の通りです。
| 位置 | 内容 |
|---|---|
| 数字 | その桁に格納されている数字の ASCII コード ('0' (48) ～ '9' (57)) を表します。 中身は '1' → '2' → … → '9' → '0' → '1' → … と遷移します。 |
| count | その桁の数字と足して9になるような整数値を格納しています。 8 → 7 → … → 1 → 0 → 9 → 8 → … と遷移します。 |
| carry | インクリメントの際に、前の桁からの繰り上がりの有無（有れば 1, 無ければ 0）を表します。 |
| tmp1 ～ tmp4 | 計算の過程で一時的に使う変数です。使っていないときの値は 0 です。 |
なお、carry, tmp1, tmp3 や tmp2, tmp4 はそれぞれ同一のメモリ位置を使用していますが、これはメモリ領域の節約のためです。
（本当は別々のメモリ位置を割り当てた方が判り易いのですが、ポインタの移動が増えるとその分ソースコードが長くなってしまうので、これを避けるために同一の位置を複数の意味で使用しています）
こうして構成したカウンタの値をインクリメントする（1増やす）ことを考えます。
インクリメントは、次の擬似コードの要領で行います。
function increment_counter(){
カウンタの1の位.carry = 1
/* carry が 1 である位をインクリメント */
for (現在の位 = カウンタの1の位; 現在の位.carry == 1; 現在の位 = 1つ上の位){
現在の位.carry = 0
if (現在の位.数字 != 0){ /* 未使用領域でない */
if (現在の位.count != 0){ /* 現在の位.数字は '9' でない */
現在の位.数字 = 現在の位.数字 + 1
現在の位.count = 現在の位.count - 1
} else { /* 現在の位.数字は '9' */
現在の位.数字 = '0'
現在の位.count = 9
次の位.carry = 1
}
} else { /* 未使用領域 */
現在の位.数字 = '1'
現在の位.count = 8
}
}
/* 初期ポインタ位置に戻す */
while (現在の位.数字 != 0){
現在の位 = 1つ下の位
}
}
これを Brainfuck で書くと、次のようになります。
function increment_counter(){
>>>>>>+ /* ポインタを カウンタの1の位.carry に移動し、値を 1 にする */
/* carry が 1 である位をインクリメント */
for [
- /* carry を 0 に戻す */
<<[->>+>+<<<]>>>[-<<<+>>>] /* 数字 を tmp1 にコピー（途中 tmp2 に退避） */
+ /* tmp2 にフラグを立てる */
if <[ /* tmp1 (= 数字) が 0 でないのなら if 節を実行 */
[-]>- /* tmp1 も tmp2 も 0 にする */
<<[->+>+<<]>>[-<<+>>] /* count を tmp3 にコピー（途中 tmp4 に退避） */
+ /* tmp4 にフラグを立てる */
if <[ /* tmp3 (= count) が 0 でないのなら if 節を実行 */
[-]>- /* tmp3 も tmp4 も 0 にする */
<<<+>-> /* 数字 のインクリメントと count のデクリメント */
] else >[ /* tmp4 のフラグが立っていれば else 節を実行 */
- /* フラグを降ろす */
<<<--------- /* 数字を '0' にする */
>+++++++++ /* count を 9 にする */
>>>>>+<<< /* 次の位.carry を 1 にする */
]<
] else >[ /* tmp2 のフラグが立っていれば else 節を実行 */
- /* フラグを降ろす */
<<<+++++++++++++++++++++++++++++++++++++++++++++++++ /* 数字を '1' にする */
>++++++++>> /* count を 8 にする */
]
>>>] /* ポインタを 次の位.carry に移動 */
/* 初期ポインタ位置に戻す */
<<<<<<[<<<<]
}
これを実行すると、123 だった値が 124 に更新されます。
こうして数え上げのできるカウンタができた訳ですが、内容を表示できなければ意味がありません。
内容の表示は、次の要領で行います。
function print_counter(){
/* 一番上の桁まで移動 */
for (現在の位 = カウンタの1の位; 現在の位.数字 != 0; 現在の位 = 1つ上の位);
/* 上の桁から順に表示 */
for (現在の位 = 前の位; 現在の位.数字 != 0; 現在の位 = 1つ下の位){
putchar(現在の位.数字)
}
}
これを Brainfuck で書くと、次のようになります。
function print_counter(){
/* 一番上の桁まで移動 */
>>>>[>>>>]
/* 上の桁から順に表示 */
<<<<[.<<<<]
}
ここまでに構成した部品を用いて、以下の流れで 1 から N までの整数を順々に数え上げるプログラムが書けます。
これを Brainfuck で書くと、次のようになります。
function count_up(){
/* 入力値 N 読み込む */
read_int() /* 本当はここに上記プログラム read_int() の内容を書く */
/* 空白文字の文字定数 '␣' を用意する */
>>>>>>>>
++++++++++++++++++++++++++++++++
>>
/* イテレータの値をデクリメントし、基準のポインタ位置に「ゼロ判定」の結果をセットする */
decrement_iterator_and_detect_underflow()
/* 本当はここに上記プログラム decrement_iterator_and_detect_underflow() の内容を書く */
/* 繰り返し */
for [
- /* 「ゼロ判定」の結果をクリア */
increment_counter() /* 本当はここに上記プログラム increment_counter() の内容を書く */
print_counter() /* 本当はここに上記プログラム print_counter() の内容を書く */
decrement_iterator_and_detect_underflow()
/* 本当はここに上記プログラム decrement_iterator_and_detect_underflow() の内容を書く */
<<.>> /* 空白文字の出力 */
]
}
これを実行して入力として
200
を与えると、次のような出力が得られます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
実行途中のメモリの遷移を表したものが下図です。
最後に、“Fizz” と “Buzz” の処理を加えれば完成です。
“Fizz” と “Buzz” の処理のためにメモリの使い方をまた少し拡張し、今まで「未使用領域」としていたメモリ領域に定数や変数を追加します。
| 位置 | 内容 |
|---|---|
| Fizz | “Fizz” を出力するための制御変数です。 3 → 2 → 1 → 3 → 2 → 1 → … と遷移します。 |
| Buzz | “Buzz” を出力するための制御変数です。 5 → 4 → 3 → 2 → 1 → 5 → 4 → 3 → 2 → 1 → … と遷移します。 |
| FB | カウンタの値が3の倍数か5の倍数のとき非 0, それ以外のとき 0 です。 |
| tmp1, tmp2 | 計算の過程で一時的に使う変数です。使っていないときの値は 0 です。 |
| 文字定数 | 文字定数 'F' (70), 'i' (105), 'B' (66), 'u' (117), 'z' (122), '␣' (32) を格納しておきます。 |
これらを用いて、FizzBuzz の計算は次の要領で実現できます。
このうち「カウンタの値に応じて "Fizz", "Buzz", "FizzBuzz" または数値を出力する」の部分は、次の要領で実現できます。
function print_fizz_buzz(){
/* Fizz の処理 */
Fizz--
if (Fizz == 0){
Fizz = 3
print("Fizz")
FB++
}
/* Buzz の処理 */
Buzz--
if (Buzz == 0){
Buzz = 5
print("Buzz")
FB++
}
/* 数値の出力 */
if (FB != 0){
FB = 0
} else {
print_counter()
}
}
これを Brainfuck で書くと、次のようになります。
function print_fizz_buzz(){
/* Fizz の処理 */
>- /* Fizz-- */
[-<<+>+>]<[->+<] /* Fizz を tmp1 にコピー（途中 tmp2 に退避） */
+ /* tmp2 にフラグを立てる */
<[[-]>-<] /* tmp1 (= Fizz) が 0 でないのなら tmp1 も tmp2 も 0 にする */
if >[ /* tmp2 のフラグが立っていれば if 節を実行 */
- /* フラグを降ろす */
>+++ /* Fizz = 3 */
<<<<<<<<.>.>>>.. /* "Fizz" と表示 */
>>>>>>+<<< /* FB++ */
]
/* Buzz の処理 */
>>- /* Buzz-- */
[-<<<+>+>>]<<[->>+<<] /* Buzz を tmp1 にコピー（途中 tmp2 に退避） */
+ /* tmp2 にフラグを立てる */
<[[-]>-<] /* tmp1 (= Buzz) が 0 でないのなら tmp1 も tmp2 も 0 にする */
if >[ /* tmp2 のフラグが立っていれば if 節を実行 */
- /* フラグを降ろす */
>>+++++ /* Buzz = 5 */
<<<<<<<.>.>.. /* "Buzz" と表示 */
>>>>>>+<<< /* FB++ */
]
/* 数の表示 */
<+ /* tmp1 にフラグを立てる */
if >>>>[ /* FB が 0 でなければ if 節を実行 */
[-]<<<<->>>> /* FB = tmp1 = 0 */
] else <<<<[ /* tmp1 のフラグが立っていれば else 節を実行 */
-> /* フラグを降ろす */
print_counter() /* 本当はここに上記プログラム print_counter() の内容を書く */
<
]>
}
以上を全部纏めると、ソースコードの全体像は次のようになります。
function FizzBuzz(){
/* 入力値 N 読み込む */
read_int(){
+
>>+
>>+
for [
-
>>>,+
[-<+<+>>]
if <[
>+
<[-]
<------------------------------------------------->
]>
]
<<+
}
/* 文字定数 'F', 'i', 'B', 'u', 'z', '␣' を用意する */
>>
>++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++
>++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ +++++++++
>++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++
>++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ +++++++++
>++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++++++++++++ ++
>++++++++++++ ++++++++++++ ++++++++
/* 制御変数 Fizz, Buzz を初期化する */
>>>+++
>+++++
<<
/* イテレータの値をデクリメントし、基準のポインタ位置に「ゼロ判定」の結果をセットする */
decrement_iterator_and_detect_underflow(){
<<<<<<<<<<<+
for [
-
<<[->+>+<<]>>[-<<+>>]
<<<+
if >>[
<<-
>>[-]
]<<
]
>-
<<[->>>+<<<]>>
>>+
for [
-
>>>+
if <<[
>>-
<<-
]
+++++++++
<<[->>>+<<<]>>
>>]
<<[-]+>>
>>>>>>>>+
if <<<<<<<<<[
->>>>>>>>>-<<<<<<<<<
]>>>>>>>>>
}
/* 繰り返し */
for [
-
/* カウンタの値をインクリメントする */
increment_counter(){
>>>>>>+
for [
-
<<[->>+>+<<<]>>>[-<<<+>>>]
+
if <[
[-]>-
<<[->+>+<<]>>[-<<+>>]
+
if <[
[-]>-
<<<+>->
] else >[
-
<<<---------
>+++++++++
>>>>>+<<<
]<
] else >[
-
<<<+++++++++++++++++++++++++++++++++++++++++++++++++
>++++++++>>
]
>>>]
<<<<<<[<<<<]
}
/* カウンタの値に応じて "Fizz", "Buzz", "FizzBuzz" または数値を出力する */
print_fizz_buzz(){
>-
[-<<+>+>]<[->+<]
+
<[[-]>-<]
if >[
-
>+++
<<<<<<<<.>.>>>..
>>>>>>+<<<
]
>>-
[-<<<+>+>>]<<[->>+<<]
+
<[[-]>-<]
if >[
-
>>+++++
<<<<<<<.>.>..
>>>>>>+<<<
]
<+
if >>>>[
[-]<<<<->>>>
] else <<<<[
->
print_counter(){
>>>>[>>>>]
<<<<[.<<<<]
}
<
]>
}
/* イテレータの値をデクリメントし、基準のポインタ位置に「ゼロ判定」の結果をセットする */
decrement_iterator_and_detect_underflow(){
<<<<<<<<<<<+
for [
-
<<[->+>+<<]>>[-<<+>>]
<<<+
if >>[
<<-
>>[-]
]<<
]
>-
<<[->>>+<<<]>>
>>+
for [
-
>>>+
if <<[
>>-
<<-
]
+++++++++
<<[->>>+<<<]>>
>>]
<<[-]+>>
>>>>>>>>+
if <<<<<<<<<[
->>>>>>>>>-<<<<<<<<<
]>>>>>>>>>
}
/* 空白文字 '␣' を出力する */
<<.>>
]
}
このうち削っても問題の無い部分を削り、動作を変えずにより短い形に書き換えられる部分を書き換えると、最終的なソースコードは次のようになります。
function FizzBuzz(){
/* 入力値 N 読み込む */
read_int(){
+
>>+
>>+
for [
-
>>>,+
[-<+<+>>]
if <[
>+
<[-]
+++++++[-<------->]
]>
]
<<+
}
/* 文字定数 'F', 'i', 'B', 'u', 'z', '␣' を用意する */
>>
++++++++++++
[->++++++>+++++++++>+++++>++++++++++>++++++++++>+++<<<<<<]
>-->--->++++++>--->++>----
/* 制御変数 Fizz, Buzz を初期化する */
>>>+++
>+++++
<<
/* イテレータの値をデクリメントし、基準のポインタ位置に「ゼロ判定」の結果をセットする */
decrement_iterator_and_detect_underflow(){
<<<<<<<<<<<+
for [
-
<<[->+>+<<]>>[-<<+>>]
<<<+
if >>[
<<-
>>[-]
]<<
]
>-
<<[->>>+<<<]>>
>>+
for [
-
>>>+
if <<[
>>-
<<-
]
+++++++++
<<[->>>+<<<]>>
>>]
<<[-]+>>
>>>>>>>>+
if <<<<<<<<<[
->>>>>>>>>-<<<<<<<<<
]>>>>>>>>>
}
/* 繰り返し */
for [
-
/* カウンタの値をインクリメントする */
increment_counter(){
>>>>>>+
for [
-
<<[->>+>+<<<]>>>[-<<<+>>>]
+
if <[
[-]>-
<<[->+>+<<]>>[-<<+>>]
+
if <[
[-]>-
<<<+>->
] else >[
-
<<<---------
>+++++++++
>>>>>+<<<
]<
] else >[
-
<<<+++++++++++++++++++++++++++++++++++++++++++++++++
>++++++++>>
]
>>>]
<<<<<<[<<<<]
}
/* カウンタの値に応じて "Fizz", "Buzz", "FizzBuzz" または数値を出力する */
print_fizz_buzz(){
>-
[-<<+>+>]<[->+<]
+
<[[-]>-<]
if >[
-
>+++
<<<<<<<<.>.>>>..
>>>>>>+<<<
]
>>-
[-<<<+>+>>]<<[->>+<<]
+
<[[-]>-<]
if >[
-
>>+++++
<<<<<<<.>.>..
>>>>>>+<<<
]
<+
if >>>>[
[-]<<<<->>>>
] else <<<<[
->
print_counter(){
>>>>[>>>>]
<<<<[.<<<<]
}
<
]
}
/* イテレータの値をデクリメントし、基準のポインタ位置に「ゼロ判定」の結果をセットする */
decrement_iterator_and_detect_underflow(){
<<<<<<<<<<+
for [
-
<<[->+>+<<]>>[-<<+>>]
<<<+
if >>[
<<-
>>[-]
]<<
]
>-
<<[->>>+<<<]>>
>>+
for [
-
>>>+
if <<[
>>-
<<-
]
+++++++++
<<[->>>+<<<]>>
>>]
<<[-]+>>
>>>>>>>>+
if <<<<<<<<<[
->>>>>>>>>-<<<<<<<<<
]>>>>>>>
}
/* 空白文字 '␣' を出力する */
.>>
]
}
コメントを全部取り除いた最終的なソースコードは、次の通りです（895バイト）。
+>>+>>+[-> >>,+[-<+<+ >>]<[>+<[- ]+++++++[- <------->] ]>]<<+>>++ ++++++++++ [->++++++> +++++++++> +++++>++++
++++++>+++ +++++++>++ +<<<<<<]>- ->--->++++ ++>--->++> ---->>>+++ >+++++<<<< <<<<<<<<<+ [-<<[->+>+ <<]>>[-<<+
>>]<<<+>>[ <<->>[-]]< <]>-<<[->> >+<<<]>>>> +[->>>+<<[ >>-<<-]+++ ++++++<<[- >>>+<<<]>> >>]<<[-]+> >>>>>>>>>+
<<<<<<<<<[ ->>>>>>>>> -<<<<<<<<< ]>>>>>>>>> [->>>>>>+[ -<<[->>+>+ <<<]>>>[-< <<+>>>]+<[ [-]>-<<[-> +>+<<]>>[-
<<+>>]+<[[ -]>-<<<+>- >]>[-<<<-- ------->++ +++++++>>> >>+<<<]<]> [-<<<+++++ ++++++++++ ++++++++++ ++++++++++
++++++++++ ++++>+++++ +++>>]>>>] <<<<<<[<<< <]>-[-<<+> +>]<[->+<] +<[[-]>-<] >[->+++<<< <<<<<.>.>> >..>>>>>>+
<<<]>>-[-< <<+>+>>]<< [->>+<<]+< [[-]>-<]>[ ->>+++++<< <<<<<.>.>. .>>>>>>+<< <]<+>>>>[[ -]<<<<->>> >]<<<<[->>
>>>[>>>>]< <<<[.<<<<] <]<<<<<<<< <<+[-<<[-> +>+<<]>>[- <<+>>]<<<+ >>[<<->>[- ]]<<]>-<<[ ->>>+<<<]> >>>+[->>>+
<<[>>-<<-] +++++++++< <[->>>+<<< ]>>>>]<<[- ]+>>>>>>>> >>+<<<<<<< <<[->>>>>> >>>-<<<<<< <<<]>>>>>> >.>>]
これを実行して入力として
200
を与えると、次のような出力が得られます。
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz 101 Fizz 103 104 FizzBuzz 106 107 Fizz 109 Buzz Fizz 112 113 Fizz Buzz 116 Fizz 118 119 FizzBuzz 121 122 Fizz 124 Buzz Fizz 127 128 Fizz Buzz 131 Fizz 133 134 FizzBuzz 136 137 Fizz 139 Buzz Fizz 142 143 Fizz Buzz 146 Fizz 148 149 FizzBuzz 151 152 Fizz 154 Buzz Fizz 157 158 Fizz Buzz 161 Fizz 163 164 FizzBuzz 166 167 Fizz 169 Buzz Fizz 172 173 Fizz Buzz 176 Fizz 178 179 FizzBuzz 181 182 Fizz 184 Buzz Fizz 187 188 Fizz Buzz 191 Fizz 193 194 FizzBuzz 196 197 Fizz 199 Buzz
前節で FizzBuzz のプログラムとしては完成していますが、出力の末尾に余計な空白文字 '␣' (32) が付いている点に若干美しくなさを感じるので、代わりに改行文字 '\n' (10) を出力するようにします。
「UFフラグが立っていたらメモリ上の '␣' を '\n' に書き換える」という動作を追加すれば良いので、decrement_iterator_and_detect_underflow の最後の
if <<<<<<<<<[
->>>>>>>>>-<<<<<<<<<
]
の部分を
if <<<<<<<<<[
->>>>>>>-->+++++[-<---->]>-<<<<<<<<<
]
に書き換えれば OK です。
こうした場合、ソースコードは次の通りとなります（911バイト）。
+>>+>>+[-> >>,+[-<+<+ >>]<[>+<[- ]+++++++[- <------->] ]>]<<+>>++ ++++++++++ [->++++++> +++++++++> +++++>++++
++++++>+++ +++++++>++ +<<<<<<]>- ->--->++++ ++>--->++> ---->>>+++ >+++++<<<< <<<<<<<<<+ [-<<[->+>+ <<]>>[-<<+
>>]<<<+>>[ <<->>[-]]< <]>-<<[->> >+<<<]>>>> +[->>>+<<[ >>-<<-]+++ ++++++<<[- >>>+<<<]>> >>]<<[-]+> >>>>>>>>>+
<<<<<<<<<[ ->>>>>>>>> -<<<<<<<<< ]>>>>>>>>> [->>>>>>+[ -<<[->>+>+ <<<]>>>[-< <<+>>>]+<[ [-]>-<<[-> +>+<<]>>[-
<<+>>]+<[[ -]>-<<<+>- >]>[-<<<-- ------->++ +++++++>>> >>+<<<]<]> [-<<<+++++ ++++++++++ ++++++++++ ++++++++++
++++++++++ ++++>+++++ +++>>]>>>] <<<<<<[<<< <]>-[-<<+> +>]<[->+<] +<[[-]>-<] >[->+++<<< <<<<<.>.>> >..>>>>>>+
<<<]>>-[-< <<+>+>>]<< [->>+<<]+< [[-]>-<]>[ ->>+++++<< <<<<<.>.>. .>>>>>>+<< <]<+>>>>[[ -]<<<<->>> >]<<<<[->>
>>>[>>>>]< <<<[.<<<<] <]<<<<<<<< <<+[-<<[-> +>+<<]>>[- <<+>>]<<<+ >>[<<->>[- ]]<<]>-<<[ ->>>+<<<]> >>>+[->>>+
<<[>>-<<-] +++++++++< <[->>>+<<< ]>>>>]<<[- ]+>>>>>>>> >>+<<<<<<< <<[->>>>>> >-->+++++[ -<---->]>- <<<<<<<<<]
>>>>>>>.>> ]
或いは、出力の区切り文字 '␣' を全部 '\n' としてしまうのも手かもしれません。
その場合、ソースコードは次の通りとなります（891バイト）。
+>>+>>+[-> >>,+[-<+<+ >>]<[>+<[- ]+++++++[- <------->] ]>]<<+>>++ ++++++++++ [->++++++> +++++++++> +++++>++++
++++++>+++ +++++++>+ <<<<<<]>- ->--->++++ ++>--->++> -- >>>+++ >+++++<<<< <<<<<<<<<+ [-<<[->+>+ <<]>>[-<<+
>>]<<<+>>[ <<->>[-]]< <]>-<<[->> >+<<<]>>>> +[->>>+<<[ >>-<<-]+++ ++++++<<[- >>>+<<<]>> >>]<<[-]+> >>>>>>>>>+
<<<<<<<<<[ ->>>>>>>>> -<<<<<<<<< ]>>>>>>>>> [->>>>>>+[ -<<[->>+>+ <<<]>>>[-< <<+>>>]+<[ [-]>-<<[-> +>+<<]>>[-
<<+>>]+<[[ -]>-<<<+>- >]>[-<<<-- ------->++ +++++++>>> >>+<<<]<]> [-<<<+++++ ++++++++++ ++++++++++ ++++++++++
++++++++++ ++++>+++++ +++>>]>>>] <<<<<<[<<< <]>-[-<<+> +>]<[->+<] +<[[-]>-<] >[->+++<<< <<<<<.>.>> >..>>>>>>+
<<<]>>-[-< <<+>+>>]<< [->>+<<]+< [[-]>-<]>[ ->>+++++<< <<<<<.>.>. .>>>>>>+<< <]<+>>>>[[ -]<<<<->>> >]<<<<[->>
>>>[>>>>]< <<<[.<<<<] <]<<<<<<<< <<+[-<<[-> +>+<<]>>[- <<+>>]<<<+ >>[<<->>[- ]]<<]>-<<[ ->>>+<<<]> >>>+[->>>+
<<[>>-<<-] +++++++++< <[->>>+<<< ]>>>>]<<[- ]+>>>>>>>> >>+<<<<<<< <<[->>>>>> >>>-<<<<<< <<<]>>>>>> >.>>]
本稿で前提としていた Brainfuck 処理系の挙動は以下の通りでした。
Brainfuck 処理系に依っては、以下のような挙動を示すものもあります。
このような処理系の場合、read_int を以下のように書き換えれば OK です。
（この場合、負数が現れないので wrap-around は問題となりません）
function read_int(){
+ /* UFフラグ = 1 */
>>+ /* 番兵A.count = 1 */
>>+ /* 番兵A.next = 1 */
/* EOF に達するまで桁を進めつつ入力を読む */
for [ /* この時点でポインタは「前の桁.next」を指している */
- /* 前の桁.next = 0 */
>>>, /* 桁を進め、一時的に「現在の桁.next」に getchar() を読み込む */
[-<+<+>>] /* next の値を count と tmp にコピー（next の値は 0 に戻る） */
if <[ /* tmp の値が 0 でないならば */
>+ /* next に 1 を立てる */
<[-] /* tmp を破壊する（こうしないとループから抜け出せない） */
<------------------------------------------------ > /* count から 48 (= '0') を減ずる */
]> /* この時点でポインタは「現在の桁.next」を指している */
]
/* 番兵Bをセット */
<<+
}
この場合、最終的なソースコードは次のようになります（894バイト）。
+>>+>>+[-> >>, [-<+<+ >>]<[>+<[- ]++++++++[ -<------>] ]>]<<+>>++ ++++++++++ [->++++++> +++++++++> +++++>++++
++++++>+++ +++++++>++ +<<<<<<]>- ->--->++++ ++>--->++> ---->>>+++ >+++++<<<< <<<<<<<<<+ [-<<[->+>+ <<]>>[-<<+
>>]<<<+>>[ <<->>[-]]< <]>-<<[->> >+<<<]>>>> +[->>>+<<[ >>-<<-]+++ ++++++<<[- >>>+<<<]>> >>]<<[-]+> >>>>>>>>>+
<<<<<<<<<[ ->>>>>>>>> -<<<<<<<<< ]>>>>>>>>> [->>>>>>+[ -<<[->>+>+ <<<]>>>[-< <<+>>>]+<[ [-]>-<<[-> +>+<<]>>[-
<<+>>]+<[[ -]>-<<<+>- >]>[-<<<-- ------->++ +++++++>>> >>+<<<]<]> [-<<<+++++ ++++++++++ ++++++++++ ++++++++++
++++++++++ ++++>+++++ +++>>]>>>] <<<<<<[<<< <]>-[-<<+> +>]<[->+<] +<[[-]>-<] >[->+++<<< <<<<<.>.>> >..>>>>>>+
<<<]>>-[-< <<+>+>>]<< [->>+<<]+< [[-]>-<]>[ ->>+++++<< <<<<<.>.>. .>>>>>>+<< <]<+>>>>[[ -]<<<<->>> >]<<<<[->>
>>>[>>>>]< <<<[.<<<<] <]<<<<<<<< <<+[-<<[-> +>+<<]>>[- <<+>>]<<<+ >>[<<->>[- ]]<<]>-<<[ ->>>+<<<]> >>>+[->>>+
<<[>>-<<-] +++++++++< <[->>>+<<< ]>>>>]<<[- ]+>>>>>>>> >>+<<<<<<< <<[->>>>>> >>>-<<<<<< <<<]>>>>>> >.>>]