Edited at
武蔵野Day 10

競技プログラミングで、Brainf*ckが少し使えた気になった話

More than 1 year has passed since last update.


前書き

この記事は、武蔵野 Advent Calendar 2017 の10日目の記事です。

新しい言語に触ってみたい!でもアプリケーションを作るにはいろいろ調べ物があって大変…という時はありませんでしょうか。

そんな時にお勧めするのが、競技プログラミングメソッドです。

競技プログラミングとは、指定の入力に対して解を計算し出力するプログラムを作って、テストを走らせてそのプログラムの正当性を評価する、というゲームです。

国内ではAtcoderというサイトが有名です。

このサイトでは、問題と、自動ジャッジのシステムが動作していて、自分の作ったプログラムの解を評価してくれます。

簡単な処理から始められる問題が多数あり、言語の入門にお勧めです。

今回は、このAtcoderの問題を解いてみることで、かの有名な難読プログラミング言語「Brainf*ck」を学習したいと思います。

言語仕様に関しては、Wikipediaをご覧ください。

仕様に関しては既知のものとして話を進めます。適時Wikiを読みながら補完してください。

Wikiを読んでも全く感覚がつかめませんが、問題を解くと、見えるものがあります。


解いてみる問題

https://abc073.contest.atcoder.jp/tasks/abc073_a

入力として、2桁の数字が与えられます。その2桁の数字に"9"が含まれていたら"Yes"、そうでなければ"No"を出力するという問題です。


解の方針

まずは解答をご覧ください。


answer.bf

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


今は全く読めないと思います。

記事を読み進めるにつれてだんだんコードが読めていくことに感動するでしょう。

解答は大きく分けて2つのパートに分かれます。


  • 文字を受け取って"9"が含まれているかを判定しフラグを立てるパート

  • フラグの結果より"YES","NO"を出力するパート

ここで、メモリ上にどのようなデータがどのように配置されているかを示します。

各セルの意味に関しては、以降のパートの中で解説していきますので、変数が出てくるたびにここに戻ってくると良いでしょう。


メモリ

 1Byte  2Byte       3Byte      4Byte       5Byte    6Byte

[count][number_chr][nine_count][false_flag][chr_tmp][chr]


文字を受け取って"9"が含まれるかを判定するパート

ここでは、重要な構文、whileを学習することができます。

2回の文字入力と判定をwhile文で回す手法をとります。

疑似コードは以下のようにしています。

nine_count = 2

count = 2

while count:
number_chr = getchar()
if number_chr == "9":
nine_count--
count--

これに当たるコードが

>>++<< #nine_count = 2

++ #count = 2
[ #while count:
>, #number_chr = getchar()
---------------------------------------------------------[ #if number_ch == "9"
>-< # nine_count--
[+]] #if文から抜ける為の後処理
<-] #count--

なんとなく、読めるようになってきたのではないでしょうか。

"9"との一致判定と、if文から抜ける為の処理の部分が少し曲者です。

まず、"9"との一致判定は読み込んだ文字から"9"のascii codeである57を減算し

0との比較を行って判定しています。

「0でない = "9"でない」場合は、flagを減算しますが、それを[]構文によって行っているため

if文から抜ける為に[+]を実行しています。

やってくる文字はascii code上必ず57より小さいのでnumber_chrは負になっています。

それを0まで戻すことで、if文から抜けることが出来ます。


フラグの結果より"YES","NO"を出力するパート

ここでは、重要な構文、ifを学習することができます。

Brainf*ckにはifに相当する制御文がありません。

よって、while文を駆使して、if文を以下のようにwhile文に書き換えます。


if文

if flag:

#True時の処理
else:
#False時の処理


書き換え後のwhile文

false_flag = 1

while flag:
#True時の処理
false_flag = 0
while false_flag:
#False時の処理

疑似コードは以下のようになります。

false_flag = 1

while nine_count > 0:
putchar("Y")
putchar("e")
putchar("s")
putchar("¥n")
false_flag--
while nine_count > 0:
nine_count--

while false_flag > 0:
putchar("N")
putchar("o")
putchar("¥n")
while false_flag > 0:
false_flag--

これをBrainf*ckのコードに書き換えると

>>  #nine_countの場所へ移動

>+< #false_flag = 1
[ #while nine_count > 0:
>>+++++++++[>++++++++++<-]>-.[-]< #putchar("Y")
++++++++++[>++++++++++<-]>+.[-]< #putchar("e")
+++++++++++[>++++++++++<-]>+++++.[-]< #putchar("s")
++++++++++.[-] #putchar("¥n")
<<>-< # false_flag--
[-]] #while nine_count > 0: nine_count--

>[ #while false_flag > 0:
>>++++++++[>++++++++++<-]>--.[-]< #putchar("N")
+++++++++++[>++++++++++<-]>+.[-]< #putchar("o")
++++++++++.[-]< #putchar("¥n")
<[-]] # while false_flag > 0: false_flag--

となります。先ほどよりは読みやすくなってきているのではないでしょうか。

細かいテクニックはputcharの部分でしょう。ascii codeの数だけ+して出力しても良いのですが

もう少し工夫して、ループを使って10個の+をn回実行して、コード長を減らし、可読性を上げています。

chr_tmpとchrがそれぞれループ用変数と、文字コードそのものを示しています。

while文が役に立っていますね。先の"9"=57の減算処理も同じように文字数を減らすことができます。

説明の都合上、コードをわざと冗長にしています。


まとめ

さて、先ほどのプログラムはきちんとした解答を出力できたのでしょうか。



おっと、この記事を書いている時間がばれてしまいましたね。しかし、無事解答できたようです。よかったです。

少し工夫すれば、もっとコードは短くなりますが、ここではやめておきましょう。

この問題を通して、さまざまな気づきもありました。あるメモリを0にしないままポインタを移動することは、後々バグを埋め込みやすい、GCは大事、という基礎を振り返る機会にもなりました。

さて、プログラミングにおいて重要な構文であるwhile文、if文を学習しました。Brainf*ckにはまだまだ深遠な世界が広がっていますが、この構文を習得できたことは、「少し使えた」というには充分ではないでしょうか。もっと深く勉強したい!という方にはこの資料が良いと思います。みなさんも是非Atcoderで問題を解くことで、Brainf*ckを学習していきましょう。


あとがき

やっぱりもっと高級な言語の方がいい、Cに、pythonに、最近業務で使っているJavaScriptに感謝しようと思う。

console.log()で簡単にprintf debugできることに、255を超える数値を簡単に加算できることに感謝を捧げながらコードを書くことができるようになった気がする。