Zenn
🧠

Brainf**k講座(番外編) Brainf**k golfでのコード短縮例～PPSP～

2024/12/01に公開
esolang
codegolf
Brainfuck
golf
codeiq
tech

はじめに

※本記事は、2016/12/9にHatenaBlogに投稿した記事( Esolang Advent Calendar 2016、9日目の記事 ) と、その続編 ( 10日目 ) をつなげて移行したものです。

久しぶりに、以前のBrainf**k講座(最終の第8回はこちら)の番外編です。
CodeIQで出題されたPPSPでBrainf**k golfが一部?盛り上がりを見せたこともあり、今回は趣向を変えて、コードを縮めていく過程を紹介したいと思います。

※CodeIQは既にサービス終了しているため、オリジナルのコンテンツは残っていません。Webアーカイブはこちらになります

問題と解の例

次のような問題でした。

  • 標準入力から、4つのプログラム言語名がカンマ区切りで、最後に改行も込みで入力される。
  • 各言語名はSnakeCase ( 英小文字の塊をアンダースコアで連結した形式 ) である。
  • 入力に従い、次の2行からなる出力を行う。
    • 1行目は各プログラム言語名の先頭を大文字化して連結した4文字
    • 2行目は、各プログラム言語名をPascalCase化して連結した文字列 ( カンマは取り除く )
    • PascalCase化とは、先頭とアンダースコア直後の文字を大文字化した形式 ( アンダースコアは取り除く )

例えば、ruby,java_script,python,cという入力に対しては、RJPCとRubyJavaScriptPythonCを出力します。

Brainf**k以外の言語であれば、例えば次のPerl(51)が解となります。

$_=",".<>;print s/,(.)\w*/\U$1/gr,s/[,_](.)/\U$1/gr

Brainf**kでの実装

まずは素直に

まずは素直な実装例 ( 145文字 ) からです。

->+>,+[-
 * 除数32のセット
 >++++[->++++++++<]
 ** memory layout: qc_d (q:直前の商 c:入力文字 d:32) **
 * 32によるdivmod
 <[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]
 ** memory layout: q_cDrq (c:入力文字のバックアップ q:商)**
 * 1文字前の商qを見て文字種判別 ( 1と2 だけ分岐に入る )
 <[---[+
  * 1文字前 ( カンマ/アンダースコア ) のクリア
  <<<[-]>>>
  * 大文字化 ( マイナス32 )
  >++++[->--------<]
  * 1文字前がカンマの場合は大文字化したものを出力
  <[+>>.<<]
 ]]
>>>>>>,+]
* 最後の改行文字を出力 ( かつマーク付け ) し、先頭のマークまで移動
<<<<.,<+[-<+]
* 各文字 ( クリアしてないもの ) を出力 
>>>+[-[.,+]>>>>>+]

全体的な流れとしては、全部の文字を読んで保存後、先頭に戻って文字列を出力する、というものになります。
ただし、カンマ・アンダースコアだけは次のように扱いが変わります。

  • 直後の文字を大文字化する
  • カンマの場合は更にその大文字化したものを先に出力する
  • カンマ・アンダースコア自身は後で出力しない ( クリアしておく )

そのため、割り算により文字種を判別し、かつ1文字前の情報を残しておく必要があります。その際、元の文字を残しておかないと後で出力できませんから、アルゴリズム集にあるdivmodの最初のバージョンを使います。

今回、32で割った商が、改行は 0、カンマは 1、アンダースコアは 2、英小文字は 3 と綺麗に分かれます。逆に言うと、文字コード95のアンダースコアと97の小文字aが近接していることから32以外では難しい所です。

なお、最初の入力文字は無条件で大文字化となりますが、そこだけ特別扱いするのは面倒なので、カンマ検出時と同じ情報 ( 商 1 ) をダミーで入れておくことで吸収します。

少し改善

上の実装は綺麗ですが、どうしても見逃せない点があります。それは、割り算に使う32、大文字化のために引く32を個別に作っている点です。それぞれ20文字程度消費しますから結構馬鹿になりません。

そこで、共通で1度だけ作ってどちらにも使おうとするわけですが、少し困ったことが起ります。それは、割り算と大文字化を同時に行えないということです。
ただ、ラッキーなことに、カンマやアンダースコアは2連続しないことが問題文から読み取れますから、大文字化の時には文字種の判別が要らない、つまり割り算が省けます。

ということで、次の135文字の実装が出来ます。

->+>,+[-
 * 32の生成
 >++++[->++++++++<]
 ** memory layout: q_c_d (q:直前の商 c:入力文字 d:32 )
 * qが1か2の時のみ分岐
 <<[---[+
   * 1文字前のc(3つ前にあるはず)のクリア
   <<<[-]>>>
   * 大文字化とカンマの場合出力
   >>>[-<<->>]<<<[+>.<]
   * 出る場所をずらすことで次の割り算を回避
   >>
 ]]
 ** memory layout: c! ( 大文字化した場合 ) !c_d ( その他 ) ( !は現在地 ) **
 * 32によるdivmod
 >[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]
 * 余り等のクリア
 >>[-]>[-]
>>,+]
* 最後の改行の出力
<<<<.
* 先頭のマークへ戻るとともに途中プラス1による橋掛け
+[<+]
* 橋掛けした中で元非0の所だけ出力
>[-[.,+]>]

なお、もはや読み込む文字を等間隔には保持していないので、最後は開き直って全部スキャンします。途中の割り算で出る不要な余り等をクリアする必要がありますが、一度に大きな移動をしなくなるため、出力部分を大幅に省力化することができます。

思い切って構成変更

しかし、実装を考えていた当時、既に133文字が記録されていました。

https://twitter.com/jrainf__k/status/802645401002119169

ということで上の実装では叶いません。そこで思い切って構成変更することを考えました ( もっと正確に言うと並行して考えていたアイデアの方が結果的に縮んだ、ですが )。何となく無駄に思えるのが、カンマ、アンダースコアを前に戻ってクリアしているところ、ここを次の文字による上書きで兼ねられないか、という考えたのです。

そうすると、カンマ、アンダースコアの判定は直ぐに行わなければなりません。そこで判定と大文字化を分離します。

それによりできたのが次の129文字です。

->++>,+[-
 >>++++[-<++++++++>]
 ** memory layout: qcd **
 * 大文字化、カンマの場合は出力 ( 今度はカンマがプラス2 )
 <<<[->>[-<->]<<[->.<]>>]
 * 変形の割り算
 >[->-[>+>>>]>[+[-<+>]>->>>]<<+<<<<]
 ** memory layout: cd → _Drqc **
 >[-]>[-]
 * qの値を見て、カンマ、アンダースコアの場合は位置をずらす
 >[+++[<<]]
 * ずれた場合はcが上書きされる
>>>,+]
<<.+[<+]>[-[.,+]>]

カンマ、アンダースコアの場合に位置をずらしてクリアと入力を兼ねている所もそうですが、次のループでq,cの位置が隣接するように割り算を変形しています。
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]と[->-[>+>>>]>[+[-<+>]>->>>]<<+<<<<]を見比べてみて下さい。被除数のバックアップは何も元の位置の隣でなくても良いのです。また、商は敢えて負にしています。次の+++で正に持っていくためです。Brainf**kの場合、システム的な制約が無ければ、入出力の時を除いて、正負どちらの値にするのも自由なのです。

初回提出版

上で129文字版ができました。しかし、提出したのは次の125文字でした。

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

これは最後の出力を[-[.,+]>]から[-.>]に替えたものです。そうすると、途中のNUL文字 ( 文字コード 0 ) も全て出力することになってしまうのですが、ideoneをバックエンドにしているCodeIQの場合NUL文字はなかったことにされるようなのです。そのことに気付いて4文字縮めることができたのでした。まあ「短いは正義!」です。

…とは言え、これ良いんだ…、という感じではありました。

https://twitter.com/angel_p_57/status/803075791114280961

もっと短いコードを!

しかし、その後あっさり120文字で抜き返されます。まだまだ無駄は省かねばなりません!!

で、実はもやもやしていたのは、32を予め作って置くところ。確かに一度で済んではいるのですが、大文字化の際に作った32を引き算で移しています。実質コピー分の無駄ができているのです。

そこでもっと考えを押し進めて、32を作る時にそもそも場所を調整することで、カンマ、アンダースコアの直後なら直接マイナス32に、そうでなければ除数の32 ( 実際は-32 ) を作るようにしました。これならコピーの分の無駄は生じません。
この工夫により、一気に次の118文字に縮めることができました。

->>++>,+[-
 * カンマ、アンダースコアの場合は1ずらす
 <[-<]
 ** memory layout: !qc ( ずらした場合 ) !c ( その他 ) ( ! は現在地 ) **
 * 大文字化のマイナス32または除数のマイナス32の作成
 ++++[->>--------<<]
 ** memory layout: !qc ( ずらした場合 ) !cd ( その他 ) ( ! は現在地 ) **
 * カンマ(qに1残り)と大文字化なしの場合は直ぐに区別できないためワンクッション
 >[-[+
   * 32での割り算
   [->+[>+>>>]>[+[-<->]>->>>]<<+<<<<]
  <]
  * カンマの場合でもそうでなくても ( NULなので ) 構わずホイホイ出しちまうんだぜ
  >.
 <]
 >>[+]>[-]
 >[+++[<<]]
>>>,+]
<<.+[<+]>[-.>]

なお、ずらすのは良いのですが、カンマの直後で q に ( 直前の-1の後 ) 1 残っている状況と、ずらしがない状況はすぐには区別できません。いずれも右隣に非0マスが2個連なっている状態だからです。
そこで、ワンクッション挟みます。qに1残りの状況であれば、マイナス1することでふるい分けられるからです。問題はカンマの場合の大文字出力ですが、if-elseの制御を行わず構わず行います。割り算をした場合残っているのはNUL文字なので、先ほどと同じく問題にならないのです。

最終形

先ほどの118文字で既に大幅に縮んではいるのですが、細かく無駄があるところを縮めて115文字が最終形となりました。

->>++>,+[
 <[-<]
 * 32の代わりに33
 +++[->>-----------<<]
 >[-[
   [->+[>+>>>]>[[-<->]>->>>]<<+<<<<]
  <]
  * 割り算の後の余り等のクリアも分岐の中に入れる
  >.>[+]>[-]>[+++[<<]]
 ]
>>>,+]
<<.+[<+]>[-.>]

一つは、割り算の余りのクリア等の処理を、カンマ・割り算の分岐にまとめてしまうことです。これにより出力の前後で往復していた2文字分が縮みます。

もう一つは細かい所ですが、入力ループの最初の-1の省略です。これはどうせ割り算に入る直前で-1が入るからそちらで兼ねてしまおうということです。
ただそうすると、32の代わりに33を作る必要があり、ここで2文字増えてしまいトントンに見えます。しかし、割り算の所で1文字縮めることができるのです。
[->+[>+>>>]>[+[-<->]>->>>]<<+<<<<]が[->+[>+>>>]>[[-<->]>->>>]<<+<<<<]と、+が1文字減っています。

実は、÷32が÷33に変わったことでそのままでは商の値が狂ってしまうのですが、割り算のループにおける除数の回復を手抜きすることで調整することができるのです。
例えばアンダースコア95が被除数の場合、通常であれば、95と32を比較→63と32を比較→31と32を比較と進む所、95と33を比較→62と32を比較→30と31を比較、というように、除数の所を1ずつ減らすようにして辻褄を合わせているということです。

いやもう、流石にこれ以上縮めるネタは思い浮かびませんでした。多分これが一番短いと思います。

終わりに(仮)

最後まで読んで頂き有難うございます。かなりのボリュームになりましたが如何でしょうか。
普段、公開される最終形だけでは見え辛い、途中でどこら辺に着目しどのような発想で縮めたかという点、参考になれば、そしてBrainf**kのgolfを楽しんで頂ければ幸いです。

続き

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

真・最終形

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

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

https://twitter.com/angel_p_57/status/807003097817968640

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

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

短縮前：115文字版

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

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

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

しかし真の最短は…

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

https://twitter.com/jrainf__k/status/807077512530407424

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

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

+<<,+[-
 ** 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は様々な発想があることに刺激を受けますね。

Discussion