More than 3 years have passed since last update.

Brainfckのコードを出力するBrainfckのコードを書く

Brainf*ck

Last updated at 2022-02-01Posted at 2021-12-18

はじめに

Brainf*ckは，><+-.,[]の8つの文字のみを使って書いていく言語です。そのほかの文字はコメントとして扱われます。流れのイメージとしては，すべて0で初期化されている配列とその要素のどれかを指すポインタがあって，ポインタやポインタの指す値を操作しながらやりたいことを行っていきます。このあたりの詳しいことについては参考文献のところに貼ったWikipediaのやつがわかりやすいと思いますので，ここでは省きます。

さて，Brainfckの文法はとても覚えやすいのですが，書くのも読むのも非常に難しいです。そこで，Brainfckを書くときの支援として，入力に基づき自動でBrainfckのコードを生成してくれるコードをC++やPythonなどで書いて愛用している人も多いでしょう。そこで，この記事ではタイトルの通り，こういった支援をしてくれるコードをBrainfckで書いてみたいと思います。これで，Brainf*ckを書く労力が軽減されることでしょう。

規格とか

今回はAtCoderさんが採用している処理系を使うことにします。その中で重要なやつをあげます。

1つの要素は8bitで，0以上255以下の整数を扱える
255をインクリメントすると0になる
0をデクリメントすると255になる
EOFは-1（すなわち255）

また，説明の都合上本記事では，プログラムの実行中に使っている配列を$A$とし，$A_x$でその$x$番目（0-indexed）の要素を表すものとします。

やりたいこと

標準入力から文字列が与えられます。

Hello, world!

これに対して，この文字列を出力するようなBrainf*ckのコードを出力することが目標です。例えば，このような感じのコードが出力できればよいです。なお，コメントを//で書いていますが，><+-.,[]以外は無視されるのでどう書いてもよく，改行やインデントも自由です。

>++++++++[<+++++++++>-]<.			// H
>++++[<+++++++>-]<+.				// e
+++++++.							// l
.									// l
+++.								// o
>++++++[<----------->-]<-.			// (comma)
------------.						// (space)
>+++++++[<++++++++++++>-]<+++.		// w
--------.							// o
+++.								// r
------.								// l
--------.							// d
>++++++[<----------->-]<-.			// !

実際にこのコードを実行してみると

Hello, world!

と出力されます。これを見てもわかるように，Brainf*ckは文字列を出力するだけでも一苦労です。他の一般的な言語であればprint("Hello, world!")などのように，何らかの形でコードにHello, world!が登場するのが普通ですが，そうはいきません。例えばHを出力しようと思ったら，その要素を72にしてあげてから.で出力する必要があります。このコードでは$A_0$を出力する値にして，各文字ごとの差分だけインクリメント/デクリメントしています。また，差分が大きいときは+や-をたくさん並べるのがちょっと大変なので，$A_1$をfor文のカウンタ変数のように使ってループを回すことで，少しでもコードを簡潔にしています。

序章

入力が1文字の時を考えてみる

文字列から考えるのは難しいので，1文字のみが与えられることにして考えてみます。例えばHが入力されたとしましょう。,で入力を読み取ったとき，これは72として読まれます。出力するときはある要素を72にして.で出力すればいいので，+を72回出力して.を出力すればよさそうです。今後のために，Brainf*ckで使う文字.><[]+-をこの順で$A_0, A_1, \cdots ,A_6$に詰めておきます（入力読み取りの,は使わないので省略）。なお，コード中にコメントのつもりで.などを書いてしまうと命令として解釈されてしまうので，periodなどの名称で書くことにします。

>+++++[<+++++++++>-]<+>			// period
>++++++[<++++++++++>-]<++>		// greater than
>++++++[<++++++++++>-]			// less than
>+++++++[<+++++++++++++>-]		// left square bracket
>+++++++[<+++++++++++++>-]<++>	// right square bracket
>++++++[<+++++++>-]<+>			// plus
>+++++[<+++++++++>-]			// minus

, // 入力を受け取ってfor文のカウンタ変数にする
[
<<.>> // plusを出力
-]
<<<<<<<. // periodを出力

入力

出力

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

この出力のコードを実行すると確かにHと出力されます。

文字列で考えてみる

あとはEOFまで読み取ってこの処理を繰り返せばよさそうです。まず，EOFまで読み込むのは，+[,+]でできます。最初は適当にインクリメントをしてループの中に入り込みます。次に，入力を受け取ってインクリメントし，これが0かどうかを判定して，0であれば抜ける，そうでなければループの先頭に戻ります。インクリメントして0になるのは-1，すなわちEOFですので，EOFが来たらループを抜けられます。これで，EOFまで読み込むことができます。
あとはちょっとdo-whileみたく最初の1回だけ,+を外に出してあげて，ループの中身にさっきのコードを突っ込めばよさそうです。また，次の文字に移るときには，ポインタが指す要素の値が0である必要があるので，ポインタを次の要素に移すために.のあとに>も出力することにします。

>+++++[<+++++++++>-]<+>			// period
>++++++[<++++++++++>-]<++>		// greater than
>++++++[<++++++++++>-]			// less than
>+++++++[<+++++++++++++>-]		// left square bracket
>+++++++[<+++++++++++++>-]<++>	// right square bracket
>++++++[<+++++++>-]<+>			// plus
>+++++[<+++++++++>-]			// minus

,+
[- // EOF判定のためにインクリメントした分を戻す
[<<.>>-] // plusをこの文字の分だけ出力
<<<<<<<.>.>>>>>> // periodとgreater thanを出力
,+] // 入力を読み込みインクリメントして0になればEOF

入力

Hello, world!

出力

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++.>

この出力のコードを実行すると確かにHello, world!と出力されました。ここで当初の目的は達成できたので終わってしまってもよいのですが，なんかこう，ほしい。もっとほしい。Brainfck感がもっとほしい。出力されたコードを見ると，+ばっかりで，正直Brainfck感がないです。Brainf*ckというからには，[]とかを使ってあげないと負けた感じがします。

本題

差分を計算してみる

ということで，さらなるBrainf*ck感を求めてコードを書くことにします。いきなりfor文を使うとなるとちょっと難しいので，まずは差分を計算して前の結果を利用することで，少しでも簡潔にしようと試みてみます。
ここからは，表を使って説明していきます。表の見方は，以下の通りです（折りたたんでいます）。

表の見方

列名は，プログラムで使われる配列の要素を表しています。
見やすさの関係上，0は「-」と表記しています。特に0を強調したいときは0と書くこともあります。
ポインタが指している要素は「[]」で囲っています。
行名の#xというのは，状態の番号です。一列がある瞬間での状態を表しており，上から下に遷移していくイメージです。この状態の番号は，このあとの説明やコード内でのコメントと対応しています。

まず，前述の通り.><[]+-がこの順で$A_0, A_1, \cdots ,A_6$に入っているため，$A_7$から考えています。今の文字に加えて，1つ前の文字を保存しておく必要があるため，$A_7$に1つ前の文字を保存しておいて，これを$c'$とします。そして，$A_8$を指した状態で,で読み込んで，これを$c$とします。

	$A_7$	$A_8$	$A_9$	$A_{10}$
#0	$c'$	[$c$]	-	-

ここで，1つ前の文字に対して今の文字の増分だけインクリメントしたいので，$d:=c-c'$を計算したいです。それは，$c$に対して$c'$回デクリメントを行うことで求められますが，この際$c$を消費してしまうのでいったん$A_9$と$A_{10}$に移します。一般的に，Brainf*ckでは破壊的な代入や演算しか行うことができないので，このようなコピーを多用することが多いです。

	$A_7$	$A_8$	$A_9$	$A_{10}$
#1	$c'$	[-]	$c$	$c$

ここで，上表において[-]が一部のBrainf*ckerにはゼロクリアに見えるかもしれませんが，ここではポインタの指している要素が0であることを表しています。
コピーができたので，ポインタを$A_7$の$c'$に移し，これをfor文のカウンタ変数にして$A_9$をデクリメントします。

	$A_7$	$A_8$	$A_9$	$A_{10}$
#2	[-]	-	$c-c'$	$c$

$A_{10}$の$c$を$A_7$に移し，のちの$c'$にします。

	$A_7$	$A_8$	$A_9$	$A_{10}$
#3	$c$	-	$c-c'$	[-]
#4	$c$	-	[$d$]	-

これで差分が$A_9$に入っているので，これを利用してこの回数だけ+を出力します。

	$A_7$	$A_8$	$A_9$	$A_{10}$
#5	$c$	-	[-]	-
#6	$c$	[-]	-	-

そして$A_8$にポインタを戻し，ここで,で入力を受け取ると，#6は$c'$を$c$と見た#1に相当するため，うまくループできることがわかると思います。

>+++++[<+++++++++>-]<+>			// period
>++++++[<++++++++++>-]<++>		// greater than
>++++++[<++++++++++>-]			// less than
>+++++++[<+++++++++++++>-]		// left square bracket
>+++++++[<+++++++++++++>-]<++>	// right square bracket
>++++++[<+++++++>-]<+>			// plus
>+++++[<+++++++++>-]			// minus

>,+[-
# 0
[>+>+<<-] // cをコピー
# 1 
<[>>-<<-] // cの位置でc'回デクリメントする（cからc'を引く）
# 2
>>>[<<<+>>>-] // cを移動（のちのc'）
# 3
< // ポインタをdに合わせる
# 4
[<<<<.>>>>-] // d回plusを出力する
# 5
<<<<<<<<<. // periodを出力する
>>>>>>>>,
# 6
+]

入力

Hello, world!

出力

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

出力結果が+と.で埋め尽くされました。差分が負のところは，255まで行ってさらにインクリメントして0になってさらにインクリメントしてというように一周することで，インクリメントのみで実現できます。
ここで，いやどこが進歩したんだ，余計にコードが長くなったじゃないかと言いたくなると思いますが，ここから着実に進歩していこうと思います。

ループを回してみる

さて，差分が計算できたわけですが，一周するところや大文字から小文字への移動などでどうしても差分が大きくなってしまうので，+がとても連続してしまいあまり見栄えが良くないです（なによりBrainf*ck感が欲しいですし）。そこで，ループを回してみます。例えば，29回インクリメントがしたかったら，$29=4\times7+1$と考えて，>++++[<+++++++>-]<+とすることでできます。よって，インクリメントしたい回数（例でいう29）を$d$，ループ回数（例でいう4）を$k$とすると，このように書けます。

\text{>}
\underbrace{\text{++}\cdots\text{+}}_{k\text{個}}
\text{[<}
\underbrace{\text{++}\cdots\text{+}}_{\left\lfloor \frac{d}{k}\right\rfloor\text{個}}
\text{>-]<}
\underbrace{\text{++}\cdots\text{+}}_{d \bmod k\text{個}}

すると$d$を$k$で割った時の商と余りがわかればいいので，非負整数の除法ができればよいことがわかります。では，ここからは非負整数の除法の実装方法について考えていきます。

割り算というのは結局，$d$から$k$ずつ取っていったときに何個取れて何個余るかということを考えてやればよいので，大まかに言えば，$d$から回数を記録しながら$k$を引いていって，0になったらそこでやめるみたいな感じにすればよさそうです。もう少しBrainf*ckの側に歩み寄ると，$d$から1ずつ引いていって$k$回終えるごとにどこかをインクリメントしておいて，0になったら終了のようにすればよさそうです。したがって，$A_9$に$d$が入っている#4の状態から以下のようなことを考えます。

まず$A_8$に$k$をセットします。そして，$A_9$のdをカウンタ変数としてループを回します。これによって，$A_9$が0になるまで繰り返されます。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#4	-	[$d$]	-	-	-	-	-
#5	$k$	[$d$]	-	-	-	-	-

kを$A_{10}$にコピーします。この操作は一度にはできないので$A_{11}$をtmpとして使います。具体的には，$A_{8}$を$A_{10}$と$A_{11}$に移して，その後$A_{11}$を$A_8$に移すことで実現できます。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#6	$k$	$d$	[$k$]	$0$	-	-	-

$A_{10}$をカウンタ変数として，ループを回します。これで，現在$A_10$と$A_9$をカウンタ変数として二重ループを回しています。カウンタ変数$k$（$A_{10}$）と$d$（$A_{9}$）をデクリメントして，$A_{11}$（ここで余りを記録することにします）をインクリメントします。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#7	$k$	$d-1$	[$k-1$]	$1$	-	-	-

この過程において，デクリメントをしていっている$d$（$A_9$）が0になったら直ちにこのループを抜けたいので，このとき$A_9$が0になっているかどうかの判定を行います。すなわち，if(!A[9])ができればよいということです。ひとまず，Brainf*ckは破壊的な演算が基本なので$A_{13}$にコピーします（$A_{14}$をtmpとして使用）。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#8	$k$	$d-1$	$k-1$	$1$	-	[$d-1$]	-

ポインタが$A_x$を指しているときに[hoge]を実行するということは，まさにif (A[x]) { hoge }を表していますから，otherwiseを判定するには，真偽を反転させる必要があります。そのため，あらかじめ$A_{14}$を1にしておき（表では，わかりやすいようにtrue/falseで書いています）（#9），dが0でなければ$A_{14}$を0にします（#10）。こうすることによって，$A_{14}$は$A_{13}$の真偽を反転させたものになっていますから，これで判定をすればよいです（#11）。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#9	$k$	$d-1$	$k-1$	$1$	-	[$d-1$]	true
#10	$k$	$d-1$	$k-1$	$1$	-	$0$	[false]
#11	$k$	$d-1$	[$k-1$]	$1$	-	$0$	false

$A_9$が0でなければ，そのままループの先頭に戻り，これを繰り返します。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#7	$k$	$d-1$	[$k-2$]	$2$	-	-	-
...
#11	$k$	$d-1$	[$0$]	$k$	-	$0$	false

やがて，#11のように$A_{10}$が0になり，ここで回していたループが終了します。これは，$d$から$k$を1つ取ったとことを意味するので，$A_{12}$（ここで商を記録することにします）をインクリメントします。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#12	$k$	[$d-1$]	$0$	$k$	$1$	$0$	false

また，これで余りはリセットされたので，$A_{11}$を0にします。$A_9$で回しているループの先頭であるところの#5から繰り返します。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#5	$k$	[$d-1$]	-	$0$	$1$	-	-
#6	$k$	$d-1$	[$k$]	$0$	$1$	-	-
#7	$k$	$d-2$	[$k-1$]	$1$	$1$	-	-
...
#9	$k$	$0$	$k-r$	$r$	$m$	[$0$]	true

やがて，#9で判定していた$A_9$が0に等しいかどうかの判定が真になるときが訪れます。このとき，直ちにこの二重ループを抜けたいので，$A_{10}$をゼロクリアします。

	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$
#10'	$k$	$0$	$k-r$	$r$	$m$	$0$	[true]
#11'	$k$	$0$	[$0$]	$r$	$m$	$0$	$0$
#12'	$k$	[$0$]	$0$	$r$	$m+1$	$0$	$0$

最終的に#12'で$A_{11}が$余り，$A_{12}$が商（正確には商と余りらしきものですが，これは後で調整することにします）となって求めることができました。

さて，これで割り算ができたように思えます（実際に実行してみるとほとんどケースで正しいです）が，実はよく考えるとまだ不十分です。それは，以下の2つの場合です。

$r$が$0$ではなく$k$になってしまう
$d$が$0$のとき，商が$-1$（すなわち$255$）になってしまう

まず1つめの問題点は，最後に$d$から引いた回数を記録しているので，ちょうど引き切ったとき，余り$k$と判定されてしまうことです。これは，この余りを$k$と比較して等しかったら余りを0とし，商をインクリメントすればよいです。数値の比較は，先ほど#8～#11でやったときと同様にすればよいです。$r$をコピーして一方を比較用とします。そこから$k$回デクリメントして，真偽を反転させて，これが0でないかを判定すればよいです。

2つめの問題点は，$d$が0であるときはそもそもループを通らないので，商が1だけ増えないため余分にデクリメントされてしまうことにより$-1$となってしまうことです。これは，商が0のときは，ループ部分を出力しない（実装上は，商が0でないときにループ部分を出力する）ことにします。また，商が0（$A_{12}=1$）のときも，ループ部分を出力する意味がないので出力しないことにします。

ここまで来てしまえば，もはや勝ったも同然です。$k$，$\left\lfloor \frac{d}{k}\right\rfloor$，$d \bmod k$すべて求まっているので，ポインタを動かしながら，for文の形になるように文字を出力していくだけです。また，$k$を変動させることができますが，これを変えても苦労のわりに出力されるコードの見た目があまり変わらないので，$k=5$で固定することにします。

>+++++[<+++++++++>-]<+>			// period
>++++++[<++++++++++>-]<++>		// greater than
>++++++[<++++++++++>-]			// less than
>+++++++[<+++++++++++++>-]		// left square bracket
>+++++++[<+++++++++++++>-]<++>	// right square bracket
>++++++[<+++++++>-]<+>			// plus
>+++++[<+++++++++>-]			// minus

>,+[-
	[>+>+<<-]
	<[>>-<<-]
	>>>[<<<+>>>-]
	<
	# 4 割り算ここから
	<+++++> // kをセットする
	[
		>>[-]<< // 前の余りの結果が残っているのでリセット
		# 5
		<[>>+>+<<<-]	// kをA10とA11に移す
		>>>[<<<+>>>-]<	// A11をA8に移す
		# 6
		[
			<->>+<- // ループ変数をデクリメント 余りをインクリメント
			# 7
			<[>>>>+>+<<<<<-]	// dec(d)をA13とA14に移す
			>>>>>[<<<<<+>>>>>-]	// A14をA9に移す
			<
			# 8
			>+<			// A14のフラグをたてる
			# 9
			[>-<[-]]>	// 0でないならA14のフラグをしずめる
			# 10
			[ // ここに来ればdec(d)は0
				<<<<[-]>>>>[-] // kを0にする
			]
			<<<<
			# 11
		]
		>>+<<< // 商をインクリメント
		# 12
		// dからkを1回分引いた
	]
	// 割り算ここまで
	// 余りの調整開始
	>>[<+<+>>-]		// rをA9とA10に移す
	<<<[>>->+<<<-]	// k回A10をデクリメントしつつ A11をインクリメント（A11に移す）
	>>>[<<<+>>>-]	// A11をA8に移す（kをもとの位置に戻す）
	+				// A11のフラグをたてる
	<[ // 余りからkを引いたものが0でないならばここに来る
		>-<			// A11のフラグをしずめる
		[+]			// 余りからkを引いたものを0にする（負なのでインクリメントした方がはやい）
	]
	>[ // A11のフラグがたっていればここに来る
		<<[-]		// 余りを0にする
		>>[-]		// フラグをしずめる
		>+<			// 商をインクリメントする
	]
	<<[>>+<<-]	// 移した余りをもとに戻す
	// 余りの調整完了
	>>>[-[ // 商が0（A12が0か1）でないならループ部分を出力
		<<<
		<<<<<<<<.			// greater than
		>>>>>>>[<<<.>>>-]	// plus*k
		<<<<<.				// left square bracket
		<.					// less than
		>>>>>>>>>>[<<<<<<<.>>>>>>>-]	// plus*(d/k)
		<<<<<<<<<<<.		// greater than
		>>>>>.				// minus
		<<.					// right square bracket
		<<.					// less than
		>>>>>>>>>> // 位置をループ前と合わせる
	]]
	<[<<<<<<.>>>>>>-]		// plus*(d%k)
	<<<<<<<<<<<.>>>>>>>>	// period
,+]

では，これを実行してみます。
入力

Hello, world!

出力

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

これを実行すると確かにHello, world!と出力されました。かなりBrainf*ck感があっていい感じですね。

デクリメントもしてみる

先ほどのコードの出力結果，かなりBrainf*ckしていてよかったのですが，一周しなければならないところに関して，ちょっと+が多すぎる気がします。そこで，253回インクリメントするよりは3回デクリメントした方が明らかに短く書けるので，デクリメントも考えてみることにします。すなわち，$d$回のインクリメントだけでなく，$-d$回のデクリメントも考えてみるということです。どちらが短く書けるかと言われれば，ほとんどの場合で$d$と$-d$のうち小さい方を選ぶのがよいでしょう（$k$の値によっては128周辺で多少ずれることがあるかもしれないですが，無視することにします）。

$-d$を作るのは0から$d$回デクリメントをすればいいので，造作もないことです。問題は，大小比較です。そこで，次のように考えてみます。
まず，$d$を$A_{10}$に移動したのち，このdをカウンタ変数としてループを回して，$A_9$と$A_{12}$に$d$，$A_8$と$A_{13}$に$-d$を作ります。$A_8$と$A_9$はこのまま残しておいて，$A_{12}$と$A_{13}$を使って大小判定をしていきます。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#4	$c$	-	[$d$]	-	-	-	-	-	-	-
#A	$c$	-	-	[$d$]	-	-	-	-	-	-
#B	$c$	$-d$	$d$	[$0$]	-	$d$	$-d$	-	-	-

大小判定の概要としては，$d$と$-d$からデクリメントしていったとき，先に0になった方が小さい方（厳密には大きくない方）なので，これによって判定します。
まず，ポインタをdに合わせ，これをカウンタ変数としてループを回します。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#C	$c$	$-d$	$d$	$0$	-	[d]	$-d$	-	-	-

$d$と$-d$をともにデクリメントし，$A_{11}$に判定用のフラグをたてます。このとき，$A_{12}$（$d$側）が0になっていれば#Cで始めたループを抜けてくれるので，これが0かどうかの判定はする必要がなく，$A_{13}$（$-d$側）が0かどうかの判定だけして，0になっていたらその旨をどこかに記録しておき，ループを抜ければよいです。どちらが先に0になったかというこの判定は今後も使いたいので，贅沢に$A_{16} \cdots A_{19}$の4つに記録しておき，ここがfalseであれば，$d$の方が小さく，trueであれば$-d$の方が小さいということにします。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#D	$c$	$-d$	$d$	$0$	true	$d-1$	[$-d-1$]	-	-	-

では，$A_{13}$が0かどうかの判定をします。いつものように破壊的な演算を行うので，$A_{13}$を$A_{14}$と$A_{15}$に移しておきます。そして，$A_{15}$が0でなければ$A_{11}$を沈めるとともに$A_{15}$をゼロクリアします。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#E	$c$	$-d$	$d$	$0$	true	$d-1$	[-]	$-d-1$	$-d-1$	-
#F	$c$	$-d$	$d$	$0$	true	$d-1$	-	$-d-1$	[$-d-1$]	-
#G	$c$	$-d$	$d$	$0$	false	$d-1$	-	$-d-1$	[$0$]	-

$A_{14}$を$A_{13}$に移します。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#H	$c$	$-d$	$d$	$0$	false	$d-1$	$-d-1$	[$0$]	-	-

これで，$-d$側が0であれば$A_{11}$のフラグはtrueに，0でなければfalseになっているはずです。よってこれを確認して，trueになっていれば$A_{16} \cdots A_{19}$のフラグをたててきてループを抜けます。今回はfalseになっているので何も起こりません。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#I	$c$	$-d$	$d$	$0$	[false]	$d-1$	$-d-1$	-	-	-
#J	$c$	$-d$	$d$	$0$	[false]	$d-1$	$-d-1$	-	-	-
#K	$c$	$-d$	$d$	$0$	false	[$d-1$]	$-d-1$	-	-	-

ここでデクリメントが無事に1回終わったので，カウンタ変数を$A_{12}$として回しているループの先頭であることろの#Dに戻ります。このループは$A_{12}$か$A_{13}$のどちらかかが0になるまで続きます。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#D	$c$	$-d$	$d$	$0$	true	[$d-2$]	$-d-2$	-	-	-
...
#K	$c$	$-d$	$d$	$0$	false	[$d-2$]	$-d-2$	-	-	-
...
#D	$c$	$-d$	$d$	$0$	true	[$d-(-d)$]	$0$	-	-	-

ここで，上の#Dのように，$-d$側が先に0になったとしましょう。すると，#Iに来た時点で$A_{11}$がtrueになっているはずです。そこで，この$A_{11}$がtrueであれば，$A_{16} \cdots A_{19}$のフラグをたててきて（#J'），ループを抜けるために$A_{12}$を0にします（#K'）。

	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$	$A_{16 \cdots 19}$
#F	$c$	$-d$	$d$	$0$	true	$d-(-d)$	$0$	$0$	[$0$]	-
...
#I'	$c$	$-d$	$d$	$0$	[true]	$d-(-d)$	$0$	-	-	-
#J'	$c$	$-d$	$d$	$0$	[false]	$0$	$0$	-	-	true
#K'	$c$	$-d$	$d$	$0$	-	[$0$]	$0$	-	-	true

これで，このループを抜けた時点で，どちらが小さいかが$A_{16} \cdots A_{19}$に記録された状態になっているはずです。

では，ここからの動作を考えます。ひとまず，$d$が先に0になった場合，$A_{13}$には$-d$の残骸が残ってしまっているので，ゼロクリアしておくことにします。ここで，将来的には$A_9$の値を採用して割り算していくので，$A_{16} \cdots A_{19}$のフラグがたっていた場合，ここを$-d$でもって乗っ取ってしまえばよいです。よって，$A_{19}$のフラグをここで消費することにし，$A_{19}$が0でなければ，$A_9$を0にして$A_8$の$-d$を$A_9$に移せばよいです。これで乗っ取り完了です。あとは，$A_8$をゼロクリアしてやれば，見事に小さい方のみを$A_9$に残すことができ，かつ，どちらが小さかったかのフラグを$A_{16} \cdots A_{19}$に残すことができました。

あとは出力するときに，$d$を選んだのであれば+を，$-d$を選んだのであれば-を出力すればよいです。ここでif-elseが必要になってきましたが，贅沢に3つも用意しているので，そのまま判定するやつ，デクリメントしてから判定するやつ，複製用の3つに役割を分けることにします。そのまま判定して引っかかれば$-d$を採用したので-を，デクリメントしてから判定して引っかかれば$d$を採用したので+を出力してやればよいです。

なお，コメント中に-dやd-1などと書くと-が命令として認識されてしまうので，それぞれd'，dec(d)と書くことにします。

>+++++[<+++++++++>-]<+>			// period
>++++++[<++++++++++>-]<++>		// greater than
>++++++[<++++++++++>-]			// less than
>+++++++[<+++++++++++++>-]		// left square bracket
>+++++++[<+++++++++++++>-]<++>	// right square bracket
>++++++[<+++++++>-]<+>			// plus
>+++++[<+++++++++>-]			// minus

>,+[-
	[>+>+<<-]
	<[>>-<<-]
	>>>[<<<+>>>-]
	<
	# 4 デクリメント検証開始
	[>+<-]>		// dをA10に移す
	# A
	[<<->+>>>+>-<<<-]	// A9とA12にd A8とA13にd' として移す
	# B
	>>
	# C
	[
		<+			// フラグをたてる
		>->-		// dとd'をデクリメント
		# D
		[>+>+<<-]	// dec(d')をA14とA15に移す
		# E
		>>
		# F
		[ // ここにくればdec(d')は0でない
			<<<<->>>>	// フラグをしずめる
			[-]			// 判定に使ったdec(d')をクリア
		]
		# G
		<[<+>-]		// dec(d')をA13に移す
		# H
		<<<
		# I
		[ // ここにくればdよりd'の方が小さかった
			>>>>>+>+>+>+	// A16～A19のフラグをたてる
			<<<<<<<[-]		// dec(dec(…d…))があるA12をクリア
			<[-]			// フラグをクリア
		]
		# J
		>
		# K
	]
	>[-]	// dの方が大きかった時に残るd'の残骸をクリア
	>>>>>>[	// ここにくればdよりd'の方が小さかった
		<<<<<<<<<<[-]	// dがあるA9をクリア
		<[>+<-]>		// d'があるA8をA9に移す
		>>>>>>>>>>[-]	// フラグをクリア
	]
	<<<<<<<<<<
	<[-]>	// A8をクリア
	// デクリメント検証終わり
	// 割り算ここから
	<+++++>
	[
		>>[-]<<
		<
		[>>+>+<<<-]
		>>>[<<<+>>>-]
		<
		[<->>+<-
			<[>>>>+>+<<<<<-]
			>>>>>[<<<<<+>>>>>-]
			<
			>+<
			[>-<[-]]>
			[
				<<<<[-]>>>>[-]
			]
			<<<<
		]
		>>+<<<
	]
	// 割り算ここまで
	// 余の調整開始
	>>[<+<+>>-]
	<<<[>>->+<<<-]
	>>>[<<<+>>>-]
	+<[>-<[+]]
	>[<<[-]>>[-]>+<]
	<<[>>+<<-]
	// 余の調整完了
	>>>[-[ // 商が0（A12が0か1）でないならループ部分を出力
		<<<
		<<<<<<<<.			// greater than
		>>>>>>>[<<<.>>>-]	// plus*k
		<<<<<.				// left square bracket
		<.					// less than
		>>>>>>>>>>[
			>>>>[	// ここにくればd'の方を採用した
				<<<<<<<<<<.	// minus
				>>>>>>>>>>[-]
			]
			>-[		// ここにくればdの方を採用した
				<<<<<<<<<<<<.	// plus
				>>>>>>>>>>>>[+]	// 255になっているのでインクリメントでクリアした方がはやい
			]
			>[<+<+>>>+<-]	// A18に残ったフラグをA16 A17 A19に移す
			>[<+>-]<<		// A19をA18に移す
			<<<<<-
		]	// (plus or minus)*(d/k)
		<<<<<<<<<<<.		// greater than
		>>>>>.				// minus
		<<.					// right square bracket
		<<.					// less than
		>>>>>>>>>> // 位置をループ前と合わせる
	]]
	>>>>[	// ここにくればd'の方を採用した
		<<<<<[<<<<<.>>>>>-]	// minus*(d%k)
		>>>>>[-]
	]
	>-[		// ここにくればdの方を採用した
		<<<<<<[<<<<<<.>>>>>>-]	// plus*(d%k)
		>>>>>>[+]
	]
	>[-]	// A18に残ったフラグをクリア
	<<<<<<<
	<<<<<<<<<<<.>>>>>>>>	// period
,+]

入力

Hello, world!

出力

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

ということで，完成です。出力結果も簡潔にまとまっており，ちゃんとBrainf*ckしてますね。これだけ（一般的な言語から見れば）単純なことしか行っていませんが，Hello, world!を入力として与えた場合，実行ステップ数は$2\times10^6$回くらいかかるようです。参考文献のところに貼ったインタープリタを使う場合は，警告を出す実行ステップ数を多めに設定しておくことをお勧めします。
最後に，コメントをすべて削除したコードを載せておきます。843byteのようです。

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

余談

コードを介さずにそのまま出力

入力された文字列をそのまま出力するだけなら，これだけで終わりです。print(input())よりもはるかに簡単ですね。

,+[-.,+]

EOFまで読み込んで順次そのまま出力です。

非ASCIIの入出力

これまでHello, world!しか入力してこなかったので，非ASCIIも突っ込んでみます。
入力

色は匂へど散りぬるを我が世誰ぞ常ならむ有為の奥山今日越えて浅き夢見じ酔ひもせず

出力

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

これを実行すると，確かに入力した文章が出力されます。これだけ長い文章を入力すると，$2.3\times 10^7$回ものステップ数がかかっているようです。Brainf*ckは0から255までの整数しか扱うことができませんが，入出力の際に複数のバイトに分けることで対応しているようです。例えば「色」であれば232，137，178の3バイトに分けて入出力が行われており，これはUTF-8のE889B2に対応しています。この動作は，AtCoderさんのコードテストおよび参考文献のところに貼ったビジュアライザで動作することを確認しています。

ゴルフ

ネットをさまよっていると，今回のと全く同じお題がゴルフの問題になっているのを発見しました（Brainfuck Golf: results）。どうやらshortestは49byteのようです。その文字までインクリメントして，出力して，0までデクリメントして，を繰り返しているようです。確認したところ，このコンテストでのEOFは0だったので気をつけてください。序章のやり方に近いですが，文字を切り替えるときにポインタの移動ではなくデクリメントにすることで文字数を少なくしているものだと推察されます。+と-は2つしか離れていないので，切り替えが短く書けるのでしょう。

おわりに

ということで，最後まで読んでいただきありがとうございました。Brainfckについてはまだまだ自分の理解が足りない部分はあると思うので，冗長なコードを書いていたり至らない点があるかもしれませんが，少しでもBrainfckの理解の手助けになれば幸いです。

参考文献など

参考文献

Brainf*ckのビジュアライザ

Brainf**k インタープリタ

オプションもいろいろいじれてデバック出力ができるので，とても便利でした。ありがとうございます。ここで，このビジュアライザのEOFの既定値は0になっているので注意してください。EOFの設定を間違えるとたいてい無限ループになってしまいます。EOFを-1として実行したい場合は，右上の「+オプション」から255（＝-1）に変更してください。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Brainf*ckのコードを出力するBrainf*ckのコードを書く