Brainf*ckで九九表に載っているか判定するプログラム
TSG Advent Calendar 2019 18日目です。
17日目：
Brainf*ck Advent Calendar 2019 18日目です。
17日目：
まえがき
Szkieletorと申します。
Brainf*ckという変わった言語でのプログラミングに初挑戦したので、記録を残しておきます。
いきなりですがちょっと脱線して、きっかけについて。
学祭とTSG LIVE!とコードゴルフ
私が所属するサークルTSGでは、"TSG LIVE!"という「ライブプログラミングショー」を学祭でやっており、その中の一つに「ライブコードゴルフ大会」というものがあります。
コードゴルフは簡単に言うと「コード長をできるだけ縮める」という遊びです。TSG LIVE!では、言語が書かれたマスを陣取りで取り合います。
特徴的なのは、RubyやC、Pythonといった汎用言語だけでなく、Brainf*ckを始めとしたesolang(難解プログラミング言語)のマスがいくつもあるという点です。
今回五月祭・駒場祭の両方でこのコードゴルフ大会に少しだけ関わって、なにかesoを書いてみたいなあと思い、一番有名なのはBrainf*ckだな！ ということで書いてみることにしました。
ちなみにコードゴルフ大会は動画があがっています。
- 五月祭Day1(実況をやりました。アドベントカレンダーに寄稿しているうらさんが駒場チームのプレイヤーをしています)
- 五月祭Day2
- 駒場祭(これもうらさんがプレイヤー)
Brainf*ckとは？
TSG LIVE! ライブコードゴルフ大会で定番になりつつある言語でもあります。
駒場祭の前に各esolangでTwitterで検索をかけたんですが、Brainf*ckはesoの中でもにぎわいがあっていいですね。
今回のお題
駒場祭2019 ライブコードゴルフ大会で出題されたものと同じ、九九判定のプログラムを書きました。
お題：2桁の整数が100個改行区切りで与えられるので，それぞれについて九九表に存在する数のとき1，そうでないとき0を出力せよ
上のリンクに詳しいルール、入出力例等があります。安心してゴルフしてください。
やったこと
Pythonでプログラムを書く
汎用言語で書いてそれをアルゴリズムそのままにBrainf*ckに移植すればいいんじゃないかな、と思い、まずPythonで書きました。
ちなみに私はPythonもほぼ書いたことがありません。for-elseなどググりながら書きました。
for i in range(100): number = int(input()) for j in range(10): for k in range(10): if number == j*k: print "1", break else: continue break else: print "0",
単純に、九九を1から81まで計算し、入力と比較して合っていたら二重ループを抜けて"1"を出力、81までのどれともマッチしなかったら"0"を出力、という方針です。
ゴルフ的にはもっとよいアルゴリズムがあると思いますが、未知の言語に移植するということを念頭に置いて、簡単そうだという理由で愚直な方法を。
あとは移植だ！ ということで、ところどころ方針を変えつつBrainfuckを書いていきます。
できたBrainf*ckプログラム
先に完成したコードを見せておきます。
>++++++++++[<++++++++++>-]<[>,>,>++++++++++++++++++++++++++++++++++++++++++++++++[->+>+<<]>[-<<<->>>]>[-<<<->>>]<<<>++++++++++<<[->>[-<+>]++++++++++<<]>>----------<<>>>+++++++++>+++++++++<[>[<[->>+>+<<<]>>[-<<+>>]<[->+>>+<<<]>>>[-<<<+>>>]<<[->>+<<]>[-<>>[->+>+<<]<<>>>>[-<<+>>]<<<<>>>[-<<<+>>>]<<<>]<>>[-]<<<<<<[->>>>>>>>>+>+<<<<<<<<<<]>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]<[-<<<<<->>>>>]+<<<<<[>>>>>-<<<<<[-]]>>>>>>>[>+>+<<-]>[<+>-]+>[<->[-]]<[<<<[->>+<<]>>>-]<<<<<<<<<-]+++++++++<-]>[-]<>>>>>>>>>>++++++++++++++++++++++++++++++++++++++++++++++++[-<+>]<.[-],[-]<<<<<<<<<<<<<-]
……はい。訳が分からないと思うので、コメント付きのプログラムも載せますね。
ちなみに処理系は apt で入れたbfを使いました。
>
+++++ +++++ initialize cell #1 to 10
[ use loop to set 100 to cell #0
< +++++ +++++ add 10 to cell #0
> -
]
<
[
> , store the input (10th place) to cell #1
> , store the input (1st place) to cell #2
> +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++
set 48
[->+>+<<] clone to #4 and #5
>[-<<<->>>] #1 sub #4
>[-<<<->>>] #2 sub #5
<<< move #2
> +++++ +++++ set 10 to cell #3
<<[->>[-<+>]++++++++++<<]
compute decimal and store it to cell #2
>>----------<<
>>> +++++ ++++ set 9 to cell #4
> +++++ ++++ set 9 to cell #5
< move #4
[>
[
< move #4
[->>+>+<<<] #6:7 add #4
>> move #6
[-<<+>>] #4 add #6
< move #5
[->+>>+<<<] #6/#8 add #5
>>>[-<<<+>>>] #5 add #8
<< move #6
[->>+<<] #8 add #6
>[-< while #7 do {decr #7
>>[->+>+<<]<< #9/#10 add #8
>>>>[-<<+>>]<<<< #8 add #10
>>>[-<<<+>>>]<<< #6 add #9
>]< end
and prod stored to #6
>>[-]<< delete #8
<<<<[->>>>>>>>>+>+<<<<<<<<<<]
#11/#12 add #2
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]
#2 add #12
<[-<<<<<->>>>>]+<<<<<[>>>>>-<<<<<[-]]
#11=#11==#6
>>>>>>> move #13
[>+>+<<-]>[<+>-]+ if(#13)
>[<->[-]] (#13=1 so do nothing)
<[
<<<[->>+<<] (#13=0 so #13 add #11)
>>>-
]
<<<<<<<<<-] move #5 and decrement
+++++ ++++ set 9 in #5
<-] decrement #4
>[-]< reinitialize #5
>>>>>>>>> move #13
> +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++
set 48 to #14
[-<+>] #13 add #14
<. output #13
[-],[-] set 0 to #13 and read newline
<<<<<<<<<<<<< back to #0
-
]
#がついているものはセルの番号です。
手順の解説
単体で説明されても理解できないかと思いますが、デバッガ（これとか）で過程を一緒に目で追うとわかるかと。
1. 入力が100行のため100回ループを回す準備をする
>
+++++ +++++ initialize cell #1 to 10
[ use loop to set 100 to cell #0
< +++++ +++++ add 10 to cell #0
> -
]
<
2.100回のループに入る。入力(#1, #2)を文字列から整数に変換する
1バイトずつしか読み込んでくれず、さらに文字列になるため、変換する必要があります。変換後の整数、すなわち入力をxとします。
文字(1~9)から数字への変換は、48(ASCIIコードの0)を引くとできます。
[
> , store the input (10th place) to cell #1
> , store the input (1st place) to cell #2
> +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++
set 48
[->+>+<<] clone to #4 and #5
>[-<<<->>>] #1 sub #4
>[-<<<->>>] #2 sub #5
<<< move #2
> +++++ +++++ set 10 to cell #3
<<[->>[-<+>]++++++++++<<]
compute decimal and store it to cell #2
>>----------<<
3.九九を1個ずつ計算する
まず、9をふたつセット(#4, #5)。
>>> +++++ ++++ set 9 to cell #4
> +++++ ++++ set 9 to cell #5
4.2重ループに入り、二つの数字それぞれを、ループを回す用と掛け算用にコピーして増やす。
#6と#7を掛け算のために使うことにします。
< move #4
[>
[
< move #4
[->>+>+<<<] #6:7 add #4
>> move #6
[-<<+>>] #4 add #6
< move #5
[->+>>+<<<] #6/#8 add #5
>>>[-<<<+>>>] #5 add #8
5.掛け算をする
積をyとします。
#8,#9,#10を一時的に使います。
<< move #6
[->>+<<] #8 add #6
>[-< while #7 do {decr #7
>>[->+>+<<]<< #9/#10 add #8
>>>>[-<<+>>]<<<< #8 add #10
>>>[-<<<+>>>]<<< #6 add #9
>]< end
and prod stored to #6
>>[-]<< delete #8
6.x=(x==y) xとyが等価かどうか比較し、その値を#11に入れる
#2の値(input)は保存する必要があるため、コピーして二つに増やしています。
<<<<[->>>>>>>>>+>+<<<<<<<<<<]
#11/#12 add #2
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]
#2 add #12
<[-<<<<<->>>>>]+<<<<<[>>>>>-<<<<<[-]]
#11=#11==#6
7.#13を結果を入れるセルとし、これまで0でいま1になった場合のみ書き換える
Pythonで書いたようないわゆる break の方法が思いつかず、ループを81周しています。ただ書き換えるだけだと#13が1になったあとで0で書き換えられる事態が発生するので、条件分岐させています。
>>>>>>> move #13
[>+>+<<-]>[<+>-]+ if(#13)
>[<->[-]] (#13=1 so do nothing)
<[
<<<[->>+<<] (#13=0 so #13 add #11)
>>>-
]
8.ループ変数をデクリメント
<<<<<<<<<-] move #5 and decrement
+++++ ++++ set 9 in #5
<-] decrement #4
9.#13にあわせて0か1を出力
文字列に変換する必要があるため、今度は48を足しています。48を作るのは手抜きしました。
>[-]< reinitialize #5
>>>>>>>>> move #13
> +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++
set 48 to #14
[-<+>] #13 add #14
<. output #13
[-],[-] set 0 to #13 and read newline
<<<<<<<<<<<<< back to #0
-
]
できました。574byteです。
あとがき
実際はこれをスムーズに書けたわけではなく、あちこちつまづきながら苦しんで実装していました。記事が長くなってしまったので、それは「Brainfuckに初挑戦して完成させるまでの記録」として明日書こうと思います。
明日の記事:
