実践brainfuck fizzbuzzを書く
brainfuckでfizzbuzzを書く工程を丁寧に解説
ひとまずc言語で書かれたものを用意し、変形しながらbrainfuckで記述する。
#include <stdio.h>
int main(void) {
int i;
for (i = 1; i <= 100; ++i) {
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);
}
}
return 0;
}
準備
まず、以下の固定文字列の出力を考える。
printf("fizzbuzz\n");
printf("fizz\n");
printf("buzz\n");
適当な言語を用いて対応するascii codeを求める。改行は環境によって違うので各自で適当にする。以下はpythonの例。
>>> list(map(ord, "fizzbuzz\n"))
[102, 105, 122, 122, 98, 117, 122, 122, 10]
そして、
a = 102;
putchar(a);
a = 105;
putchar(a);
...
とすることで目的の文字列を出力できる。
次に、数値の剰余算及び出力の行を考える。
printf("%d\n", i);
この文が実行されるときiは1から98の間にあるので、多少の省略ができる。つまり、
a = i / 10;
b = i % 10;
if (a) {
putchar(a + '0');
}
putchar(b + '0');
が書ければ十分であり、これは上で議論したものを用いて記述できる。
何か別な高級言語を通してbrainfuckを記述する場合にはこれで十分であるが、手で直接brainfuckを記述する場合には未だ面倒が大きい。そこで、
int i, a, b, fz, bz;
a = 0; b = 1;
fz = 3; bz = 5;
for (i = 100; i != 0; --i) {
if (fz == 0 and bz == 0) {
...
fz = 3;
bz = 5;
} else if (fz == 0) {
...
fz = 3;
} else if (bz == 0) {
...
bz = 5;
} else {
putchar(a + '0');
putchar(b + '0');
printf("\n");
}
fz -= 1;
bz -= 1;
if (b != 9) {
b += 1;
} else {
a += 1;
b = 0;
}
}
と変形し、さらにif文部分を
if (fz) {
if (bz) {
...
} else {
...
bz = 5;
}
} else {
if (bz) {
...
} else {
...
bz = 5;
}
fz = 3;
}
と変形する。
a, b, fz, bzはそれぞれもともとのloop変数の10の位と1の位、3で割った余りと5で割った余りを表す。
構成
以上を元にbrainfuckを構成していく。
まず、
int i, a, b, fz, bz;
a = 0; b = 1;
fz = 3; bz = 5;
for (i = 100; i != 0; --i) {
...
}
は、
>++++++++++[<++++++++++>-]< i = 10 * 10;
>>+>+++>+++++<<<< a = 0; b = 1; fz = 3; bz = 5;
[ for (; i != 0; --i) {
{A} ...
-] }
となる。p[0]からp[4]はi, a, b, fz, bzに対応させている。
aからbzの更新部分は、
fz -= 1;
bz -= 1;
if (b != 9) {
b += 1;
} else {
a += 1;
b = 0;
}
であり、
>>>->-<<<< fz -= 1; bz -= 1;
>>[>>>+>+<<<<-]>>>[<<<+>>>-]> p[6] = b;
--------- p[6] -= 9;
<+>[ if (p[6]) with p[5] {
<<<<+>>>> b += 1;
[-]<->]<[> } else {
<<<<<+>[-]>>>> a += 1; b = 0;
<-]> }
<<<<<<
となる。pは前後で不変であるが、if文の中では6だけずれている。
また、この3行目ではunderflowが発生することがある。処理系によってはこれを禁止しているので、p[5]を使って、
[<+>-]+++++++++<[>-<-]> p[6] = 9 - p[6];
としておく。
分岐部分は、
if (fz) {
if (bz) {
...
} else {
...
bz = 5;
}
} else {
if (bz) {
...
} else {
...
bz = 5;
}
fz = 3;
}
なので、まず、
if (fz) {
...
} else {
...
fz = 3;
}
の部分は、
>>>[>>+>+<<<-]>>[<<+>>-]> p[6] = fz;
<+>[[-]<-> if (p[6]) with p[5] {
{A}
]<[-> } else {
{B}
<<<+++>>> fz = 3;
<]> }
<<<<<<
である。{A}, {B}の直前では共にp[5], p[6]は0であり、終了時に0である限り自由に使える。
また、{A}, {B}を埋めることとなる
if (bz) {
...
} else {
...
bz = 5;
}
の部分は、p[6]を中心にして、
<<[>+>+<<-]>[<+>-]> p[6] = bz;
<+>[[-]<-> if (p[6]) with p[5] {
{A}
]<[-> } else {
{B}
<<+++++>> bz = 5;
<]> }
となる。
固定文字列の出力は、進入時のdata pointerをqとしたときq[0], q[1]が0と仮定するとそれぞれ、
>++++++++++[<++++++++++>-]<++. q[0] = 102; // f
+++. // i
+++++++++++++++++.. // zz
[-]++++++++++. // \n
[-]
>++++++++++[<++++++++++>-]<--. q[0] = 98; // b
+++++++++++++++++++. // u
+++++.. // zz
[-]++++++++++. // \n
[-]
>++++++++++[<++++++++++>-]<++. q[0] = 102; // f
+++. // i
+++++++++++++++++.. // zz
------------------------. // b
+++++++++++++++++++. // u
+++++.. // zz
[-]++++++++++. // \n
[-]
数値の出力は
putchar(a + '0');
putchar(b + '0');
printf("\n");
であるので、p[6]を中心とすると、
<<<<<[>>>>+>+<<<<<-]>>>>[<<<<+>>>>-]> p[6] = a;
[ if (p[6]) {
>++++++[<++++++++>-]< p[6] += 48;
. // a
[-]] }
<++++++[<<<++++++++>>>-]> b += 48;
<<<<.>>>> // b
<++++++[<<<-------->>>-]> b -= 48;
++++++++++.[-] // \n
である。
結合
上で作った各部分を結合する。
>++++++++++[<++++++++++>-]< i = 10 * 10;
>>+>+++>+++++<<<< a = 0; b = 1; fz = 3; bz = 5;
[ for (; i != 0; --i) {
>>>[>>+>+<<<-]>>[<<+>>-]> p[6] = fz;
<+>[[-]<-> if (p[6]) with p[5] {
<<[>+>+<<-]>[<+>-]> p[6] = bz;
<+>[[-]<-> if (p[6]) with p[5] {
<<<<<[>>>>+>+<<<<<-]>>>>[<<<<+>>>>-]> p[6] = a;
[ if (p[6]) {
>++++++[<++++++++>-]< p[6] += 48;
. // a
[-]] }
<++++++[<<<++++++++>>>-]> b += 48;
<<<<.>>>> // b
<++++++[<<<-------->>>-]> b -= 48;
++++++++++.[-] // \n
]<[-> } else {
>++++++++++[<++++++++++>-]<--. p[6] = 98; // b
+++++++++++++++++++. // u
+++++.. // zz
[-]++++++++++. // \n
[-]
<<+++++>> bz = 5;
<]> }
]<[-> } else {
<<[>+>+<<-]>[<+>-]> p[6] = bz;
<+>[[-]<-> if (p[6]) with p[5] {
>++++++++++[<++++++++++>-]<++. p[6] = 102; // f
+++. // i
+++++++++++++++++.. // zz
[-]++++++++++. // \n
[-]
]<[-> } else {
>++++++++++[<++++++++++>-]<++. p[6] = 102; // f
+++. // i
+++++++++++++++++.. // zz
------------------------. // b
+++++++++++++++++++. // u
+++++.. // zz
[-]++++++++++. // \n
[-]
<<+++++>> bz = 5;
<]> }
<<<+++>>> fz = 3;
<]> }
<<<<<<
>>>->-<<<< fz -= 1; bz -= 1;
>>[>>>+>+<<<<-]>>>[<<<+>>>-]> p[6] = b;
[<+>-]+++++++++<[>-<-]> p[6] = 9 - p[6];
<+>[ if (p[6]) with p[5] {
<<<<+>>>> b += 1;
[-]<->]<[> } else {
<<<<<+>[-]>>>> a += 1; b = 0;
<-]> }
<<<<<<
-] }
右側の注釈を削る。commentとして残したい場合はbrainfuckの命令と衝突する文字を除去する必要がある。
>++++++++++[<++++++++++>-]<
>>+>++>++++<<<<
[
>>>[>>+>+<<<-]>>[<<+>>-]>
<+>[[-]<->
<<[>+>+<<-]>[<+>-]>
<+>[[-]<->
<<<<<[>>>>+>+<<<<<-]>>>>[<<<<+>>>>-]>
[
>++++++[<++++++++>-]<
.
[-]]
<++++++[<<<++++++++>>>-]>
<<<<.>>>>
<++++++[<<<-------->>>-]>
++++++++++.[-]
]<[->
>++++++++++[<++++++++++>-]<--.
+++++++++++++++++++.
+++++..
[-]++++++++++.
[-]
<<+++++>>
<]>
]<[->
<<[>+>+<<-]>[<+>-]>
<+>[[-]<->
>++++++++++[<++++++++++>-]<++.
+++.
+++++++++++++++++..
[-]++++++++++.
[-]
]<[->
>++++++++++[<++++++++++>-]<++.
+++.
+++++++++++++++++..
------------------------.
+++++++++++++++++++.
+++++..
[-]++++++++++.
[-]
<<+++++>>
<]>
<<<+++>>>
<]>
<<<<<<
>>>->-<<<<
>>[>>>+>+<<<<-]>>>[<<<+>>>-]>
[<+>-]+++++++++<[>-<-]>
<+>[
<<<<+>>>>
[-]<->]<[>
<<<<<+>[-]>>>>
<-]>
<<<<<<
-]
以上でfizzbuzzの完成である。
実践brainfuck fizzbuzzを書く
- Fri Nov 27 23:04:20 JST 2015
- 数値のunderflowを許可しない処理系でも動作するよう修正