Brainfuckというプログラミング言語をご存じですか？

なんと基本命令が8個しかないのに、他のプログラミング言語で実現可能なことは理論的にはすべて実現可能という、恐ろしく厨二心がくすぐられる言語です！

やってみたいな～とは思いつつなかなか手が出せていなかったのですが、LiKafさんの記事に感化され、ついにBrainfuckerへの道を歩み始めることにしました。

AtCoderの具体的な問題について、素朴な実装からshortestまでの改良もまとめているので、ぜひ一緒に指を動かしながら楽しんでいってください。

はじめに

最初に少し述べた通り、基本命令を8個しか持たないプログラミング言語です。

入門的な記事は冒頭で述べたLiKafさんのものを筆頭に、いろんな方が解説してくれているので今回は省かせていただきます。

そのぶん、具体的なAtCoderの問題を解く上でのテクニックの話を多めに入れています。

自分なりのテクニックをドンドン開拓して、ドンドン問題を解いていきましょう！

今回のテクニック

ループ

ある番地の値を、100増やしたいとします。

+++++…+++++と100個書いても良いですが、shortestを狙うなら、より短く書けると嬉しいです。

実は、次のようなループを使うことでかなり短縮することができます。

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

100増やしたい番地をA番地としたとき、右隣を10にしておいて、
・右隣りを1減らして、A番地を10増やす
という処理を右隣りが0になるまで繰り返します。

値を増やすだけではなく、特定の回数だけ何かの処理を繰り返したいときは、このループが使えそうです。

こちらのようなブラウザの実行環境で実行すると、ループしている様子が見えて楽しいです！

改行まで読み込みながら展開

Brainfuckでは、普段何気なく行っている「1行入力」をするにも少し工夫が必要です。
「改行」のASCIIコードは10なことを考えると、

1. 入力して10を引いてみる

2. 0になっていれば終わり

3. 0じゃなければ10足して（元に戻して）ポインタを右に進める

を繰り返すことで、改行までの入力をすべてメモリに展開できそうです！
具体的には

//入力して10引いてみる
,----------

//0じゃなければ10を足してポインタを右に進め、また入力して10を引く
[++++++++++>,----------]

というコードで実現できます。
1行バージョンはこちら

,----------[++++++++++>,----------]

だんだんBrainfuckの楽しさがわかってきました！！！！

AtCoderの問題に挑戦！

テクニックが揃ってきたところで、ABC068のA問題に挑戦してみます！
問題はこちら

方針1　まずは素朴に考えてみる（66byte）

今までの知識を組み合わせて考えると、こんな感じになります。

//1番地に'A'を保存（AのASCIIコードは65なので、「13増やす」を5回やっている）
+++++[->+++++++++++++<]

//ポインタを1番地に移動
>

//'A'と'B'と'C'を表示
.+.+.

//ポインタを2番地に移動
>

//改行までよみこみながら表示
,----------
[++++++++++.>,----------]

1行にまとめるとこんな感じ。

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

ん～～～～～～たのしい！！！！！！
この一見わやくちゃな記号列が、ちゃんと意味を持って機能していると思うと感動です。

しかし、これではまだスマートではありません。
ドンドン短くしていきましょう！！

方針2　入力が3桁という制限を利用（36byte）

改行まで入力していましたが、問題文を見ると今回の入力は3桁固定なことがわかります。これを利用すると、大幅に短くできます！

//1番地に'A'を保存（AのASCIIコードは65なので、「13増やす」を5回やっている）
+++++[->+++++++++++++<]

//ポインタを1番地に移動
>

//'A'と'B'と'C'を表示
.+.+.

//ポインタを2番地に移動
>

//3行分読み込んで表示
,.,.,.

一行ver

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

方針3　ループの回し方を考える（35byte）

13増やすのを5増やすと、これだけで13+5=18文字使ってしまいます。
ピッタリ65増やさなくても、64増やしてから1増やすことを考えると、
8*8=64なので、8+8+1=17で1文字分節約できます！

//1番地に'A'を保存（いったん64増やし、'A'を表示する前に1足している）
++++++++[->++++++++<]

//ポインタを1番地に移動
>

//'A'と'B'と'C'を表示（'A'を表示する前に1増やす）
+.+.+.

//ポインタを2番地に移動
>

//3行分読み込んで表示
,.,.,.

一行ver

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

方針4　使うポインタを削減（34byte）

1番地でA,B,Cを表示した後、2番地に移動する必要がないことに気づき1byte節約

//1番地に'A'を保存（いったん64増やし、'A'を表示する前に1足している）
++++++++[->++++++++<]

//ポインタを1番地に移動
>

//'A'と'B'と'C'を表示（'A'を表示する前に1増やす）
+.+.+.

//3行分読み込んで表示
,.,.,.

一行ver

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

方針5　65増やす部分をさらに省略（29byte）

どうやらAtCoder上のコンパイラでは、各メモリのサイズは1byteで、128から1増やすと-127、-127から1減らすと128になるようです。

この仕様を逆手に取ると、0の状態から4ずつ引いていってまた0になるまでに64回引くことになります！！！（256 / 4 = 64）

//1番地に'A'を保存（いったん64増やし、'A'を表示する前に1足している）
---->+<[---->+<]

//ポインタを1番地に移動
>

//'A'と'B'と'C'を表示（'A'を表示する前に1増やす）
+.+.+.

//3行分読み込んで表示
,.,.,.

1行ver

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

方針6　最初の[を省略（21byte）shortestタイ！

更にAtCoderコンパイラの仕様を逆手に取ります。
AtCoderコンパイラでは、] に来た時、対応する [ が無ければプログラムの一番初めに巻き戻ります。

これによって最初のループに対してのみdo whileのようなことができて

//1番地に'A'を保存（いったん64増やし、'A'を表示する前に1足している）
---->+<]

//ポインタを1番地に移動
>

//'A'と'B'と'C'を表示（'A'を表示する前に1増やす）
+.+.+.

//3行分読み込んで表示
,.,.,.

一行ver

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

と書くことができます。

お疲れさまでした、ついにたどり着きました。

これが、現在のshortestタイ記録です！！！！！

おわりに

今回は、ロマンあふれるプログラミング言語、Brainfuckに触れてみました。
通常のプログラミングも論理パズルの様ですが、それ以上にパズル的な楽しさがあり、今後も新米BrainfuckerとしてAtCoderの解説記事を書いていければと思います。

最後までお付き合いいただきありがとうございました！