Brainf**k講座(番外編) Brainf**k golfでのコード短縮例 おまけ
Esolang Advent Calendar 2016、10日目の記事です。
続き
昨日「最終形になりました」と書いたばかりだったのに…。スマンありゃウソだった。
※経緯については昨日の記事をご覧ください。
真・最終形
記事を書き上げて投稿予約して、いよいよ問題締め切りが迫った時。ふと、ある考えが浮かびました。そう言えば、構成変更した時に「判定と大文字化を分離」としたけど、本当に分けて置かないとダメなんだろうか…、と。
ということで、115文字+1文字 ( 除数を32のままにしている ) バージョンを元に、分離を取りやめたところ…。
あれえっと。BF(113)に縮んだ…。もう記事書いちゃったんだけど→PPSP https://t.co/gU9qcY012S @codeiqさんから
— angel as ㌵㌤の猫 (@angel_p_57) 2016年12月8日
ということで土壇場で単独最短になったのでした。
最終的に、除数を32から33にすることでもう1文字短縮しています。短縮前後のコードは次の通りです。
短縮前：115文字版
->>++>,+[ * 前の文字がカンマ、アンダースコアの場合ずらす <[-<] +++[->>-----------<<] >[-[ [->+[>+>>>]>[[-<->]>->>>]<<+<<<<] <] >.>[+]>[-] * カンマ、アンダースコアの場合次の入力で文字をクリアするようずらす >[+++[<<]] ] >>>,+] <<.+[<+]>[-.>]
短縮後：112文字(最終)版
->>->,+[ * 位置ずらしと前の文字のクリアを同時に行う <[+++[-<[-]]] +++[->>-----------<<] >[-[ [->+[>+>>>]>[[-<->]>>->>]<<<+<<<] <] >.>[+]>[-] ] >>>,+] <<.+[<+]>[-.>]
しかし真の最短は…
しかし記事公開後、無慈悲なtweetが…
あれ？？入力に改行入ってたんだ？？
— じゅんや (@jrainf__k) 2016年12月9日
というわけで(?)、BF(107)になりました。https://t.co/jaEsMjhEO5 #ppsp_codeiq
拝見したところ、自分とは発想が大分違うのですね。最短を奪取されて悔しいので後学のために、どんな処理をやっているか解析してみます。
次がそのコードです。適宜コメントを追加しています。
+<<,+[-
** memory layout: cUC **
** (c:入力文字、U:直前がアンダースコアならマイナス24、C:直前がカンマなら正) **
* cをマイナス32(大文字化)すると同時にUにプラス24
>>>++++++++[<<+++<---->>>-]
* Cが正なら大文字化したものを出力、UCをクリア
<[<<.>[[-]>]]
* アンダースコアの次 ( Uがクリアされている ) でなければ、
* cをさらにマイナス12、Cに24をセット
<[<->>++<--]
* カンマの場合はcがクリアされており分岐に入らない ( Cの24が残る )
<[
* 以下、アンダースコアの次の場合、何も起こらない
* cを更にマイナス48、Uにマイナス24をセットして分岐する
>>[<-<-->>-]<[
* アンダースコアでない場合に分岐 ( アンダースコアだとUが残る )
<---[
* Uを使って入力された小文字に戻す
->[<++++>+]
]
]
]
,+]
* 最後の改行を出力して先頭に戻って全部出力
<.[<]>[.>]
実はdivmodを使った文字判別を行わないで、巧みにゼロ・非ゼロのセルを操ることで、各状況に対応しているのですね。それぞれの動きを図示すると、次のようになります。
一文字一文字を連続したセルに保持できるところ、NUL文字出力も必要ないところがまた良いですね。
終わりに
自分のコードだと、divmodの負荷 ( 特に残った余りの処理 ) があるのでこれ以上は無理があると思います。しかし、他の人のコードも見てみると、特にBrainf**kは様々な発想があることに刺激を受けますね。
