Edited at

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

More than 1 year has passed since last update.


前書き

この文章は、競技プログラミングで、Brainf*ckが少し使えた気になった話の続編にあたるものです。

前回の文章が前提になっていますので、お読みになられていない方は、こちらを先にどうぞ。

というわけで、今回は続編として、ショートコーディングにチャレンジします。

そこまで賢いことができた訳ではありませんが、ログとして残しておくことにします。


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

前回のコードは以下のようなものでした。


メモリモデル

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



answer.bf

>>++<<        # nine_count = 2 

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

これを改行やコメントを抜いて文字列長を計算すると、298Bになります。

ここからどんどん文字を削っていきましょう。


Yes,No表示を短くする


冗長な文字列生成を削除する1

これは投稿した後に気づいたことなのですが、putchar("¥n")がなくとも、解答として認識されることがわかったので、putchar("¥n")に当たる部分を削ります。

また、この解法では、すべての文字を0から作り直していますが、文字列を作る際にメモリの数字を使いまわして、差分だけ加減算してやれば良いはずです。

よって、YesならYを生成->eとの差分を加算->sとの差分を加算というように、連続する文字の加算を工夫します。

そうすれば、無駄に[-]をしてコードを長くする必要もありません。

書き換えてみます。


answer2.bf

[                  # while nine_count > 0:

>>+++++++++[>++++++++++<-]>-. # putchar("Y")
++++++++++++. # putchar("e")
++++++++++++++.[-]< # putchar("s")
<<>-< # false_flag--
[-]]
# while nine_count > 0: nine_count--
>[ # while false_flag > 0:
>>++++++++[>++++++++++<-]>--. # putchar("N")
<+++[>+++++++++++<-]>.[-] # putchar("o")
<[-]] # while false_flag > 0: false_flag--

これで216Bになりました。


冗長な文字列生成を削除する2+false_flagの除去

さて、先ほどはYesとNoの間の加算を削りました。

そうすれば、もちろん次はYとNの生成の一部を共通化することを思い浮かべます。

ここで、2つテクニックを追加します。

YとNの共通部を生成するために、あらかじめ大きな数字をchrに作っておきます。

すると、「false_flagはそのchr(1以上)の数字を持って代用できる」というテクニックが使えます。

前回の説明で>+<としてfalse_flagを作る、という話をしました、それをchrで代用するのです。

また、逆に[]ループから抜けるためにわざわざ変数を0へ減算しなくとも「0の場所へ移動すれば良い」、というテクニックも成り立ちます。

それを踏まえた上で、コードを見ると早いと思うので、以下に示します。


メモリモデル2

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



answer3.bf

>>            # nine_countの場所へ移動

>+++++++++[>++++++++++<-]< # putchar用の変数90兼false_flag
[ # while nine_count > 0:
>>-. # putchar("Y")
++++++++++++. # putchar("e")
++++++++++++++. # putchar("s")
>] #0の場所まで移動
>> #9がある場合には更に端の0へ、ない場合はputchar用の90へ
[ #putchar用の90を踏んでこのループに入る
------------. # putchar("N")
>+++[<+++++++++++>-]<. # putchar("o")
>] #0の場所まで移動

このコードで182Bまでコードを削ることができます。


Yes,No表示を短くしたコード全体像


answer4.bf

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


182Bであることが確認できると思います。


9の判定部分を短くする


57("9")減算のループ化

減算のループ化を適用します。

ループ用の変数を導入するために、メモリモデルを少し書き換えます


メモリモデル3

[count][number_chr][roop][nine_count][chr_tmp][chr]



answer5.bf

>>>++<<<      # nine_count = 2 

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

これで155Bまで縮まりました。


nine_countの位置の補正

nine_countを初めに加算していますが、そこまでの移動が面倒なので、後方に持ってきます。

それだけで移動距離を短縮できるので、コード長が縮まります。


answer6.bf

++            # count = 2

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

これで6B削れて149Bです。


9の判定部分を短くしたコード


answer7.bf

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



後日ご指摘いただいた補正を加える

いろいろ変更して心が折れていたところ、知人からの指摘で以下の最適化を追加しました。

「chrとして90を作るのではなく、88を作りに行った方がコードが短い」


answer8.bf

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


これで2文字削れて、147Bとなります。

ご指摘ありがとうございました!


追記分

ここから先は、記事投稿後の追記分を記す。


小文字生成の9判定への組込み ※2017/12/13追記


基本方針

小文字生成は、とても数字が大きい割に作るのが大変なので、最初に生成しておきたい。

ここで9の判定のループの中に小文字生成を組み込むと55*2=110が生成できる。

詳しくはコードを見てほしい。


コード


メモリモデル4

[count][number_chr][loop][loop][nine_count][large_chr][small1_chr][small2_chr][loop]



answer9.bf

++   # count++

[>, # number_chr = getchar()
>+++++ # first loop
[>+++++++++++ # second loop
[<<- # number_chr--
>>>>>+ # small1_chr++
>+ # small2_chr++
<<<<-] # end of second loop
<-] # end of first loop
<-- # number_chr -= 2
[>>>-<<<[+]] # nine_flag--
<-] # 文字数分繰り返す
>>>>++ # nine_flagの正規化
<++++++++[>>+++++++++++<<-] # make large chr
> # if nine_flag != 0
[>+.>---------.>+++++.>] # puts("Yes")
> # if nine_flag == 0
[----------.>+.>>] # puts("No")

これで140Bまで短くなりました。


さらに大文字生成も組み込む

もう解説はしませんが、大文字生成も組み込んだ


answer10.bf

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


これで132Bまで削ることができた。


実は3文字生成するより大文字小文字の2文字生成が短い ※2017/12/14追記


answer11.bf

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


これで130Bまで削ることができた。

アルゴリズム変えるとここまで縮まる。

経験値だが、ループ位置の入れ替えは、そんなに効果がないように見える。

結局のところ目的の変数まで移動しないといけない。

重要なのは、同一ループでいかにたくさんの仕事をするか。

場所を利活用して、いかに移動を少なくするか。のように思える。


変数の最適化


answer12.bf

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


ループ変数を一部最適化して、126B、ついに130Bを切る事ができた。


あとがき

という訳で、147B126Bまで短くなりました。

元のコードからすれば、約半分の長さとなっています。


  • ループを抜けるために0の場所へ移動

  • 作っておいた変数をflagに利用する

  • 文字列の差分生成

  • ループ変数の最適化

  • ループの多目的活用(追記分)

などのテクニックを身に付けることができて、なかなか良い取り組みでした。

賢くやれば、もうちょっと最適化の余地はありそうですが、良いところまでは来たのだと思っています。

143を切るには、アルゴリズムの改変が必要かなぁというのが感想です。

BF面白いので、気が向いたらもうちょっと方向を変えて続けるかもしれません。