読者です 読者をやめる 読者になる 読者になる

Brainf**k講座(番外編) Brainf**k golfでのコード短縮例 おまけ

Brainf**k コードゴルフ CodeIQ

Esolang Advent Calendar 2016、10日目の記事です。

続き

昨日「最終形になりました」と書いたばかりだったのに…。スマンありゃウソだった。

※経緯については昨日の記事をご覧ください。

真・最終形

記事を書き上げて投稿予約して、いよいよ問題締め切りが迫った時。ふと、ある考えが浮かびました。そう言えば、構成変更した時に「判定と大文字化を分離」としたけど、本当に分けて置かないとダメなんだろうか…、と。

ということで、115文字+1文字 ( 除数を32のままにしている ) バージョンを元に、分離を取りやめたところ…。

ということで土壇場で単独最短になったのでした。

最終的に、除数を32から33にすることでもう1文字短縮しています。短縮前後のコードは次の通りです。

短縮前:115文字版

->>++>,+[
 * 前の文字がカンマ、アンダースコアの場合ずらす
 <[-<]
 +++[->>-----------<<]
 >[-[
   [->+[>+>>>]>[[-<->]>->>>]<<+<<<<]
  <]
  >.>[+]>[-]
  * カンマ、アンダースコアの場合次の入力で文字をクリアするようずらす
  >[+++[<<]]
 ]
>>>,+]
<<.+[<+]>[-.>]

短縮後:112文字(最終)版

->>->,+[
 * 位置ずらしと前の文字のクリアを同時に行う
 <[+++[-<[-]]]
 +++[->>-----------<<]
 >[-[
   [->+[>+>>>]>[[-<->]>>->>]<<<+<<<]
  <]
  >.>[+]>[-]
 ]
>>>,+]
<<.+[<+]>[-.>]

しかし真の最短は…

しかし記事公開後、無慈悲なtweetが…

拝見したところ、自分とは発想が大分違うのですね。最短を奪取されて悔しいので後学のために、どんな処理をやっているか解析してみます。

次がそのコードです。適宜コメントを追加しています。

+<<,+[-
 ** 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を使った文字判別を行わないで、巧みにゼロ・非ゼロのセルを操ることで、各状況に対応しているのですね。それぞれの動きを図示すると、次のようになります。

f:id:ange1:20161210153337p:plain

一文字一文字を連続したセルに保持できるところ、NUL文字出力も必要ないところがまた良いですね。

終わりに

自分のコードだと、divmodの負荷 ( 特に残った余りの処理 ) があるのでこれ以上は無理があると思います。しかし、他の人のコードも見てみると、特にBrainf**kは様々な発想があることに刺激を受けますね。