🧠
Brainf**k講座(番外編) Baconian Cipher

2024/12/01に公開
esolang
 はじめに※本記事は、2016/7/16にHatenaBlogに投稿した記事を移行したものです

講座そのものは第8回で終わっているのですが、Brainf**kのgolfに挑戦した問題として、Baconian Cipherを取り上げ、解説したいと思います。

もともとは、しえるさんのこのtweetがきっかけでした。
https://twitter.com/cielavenir/status/689365119449473024
単純な問題ではありますが、短く組むための課題が色々あり、なかなかに面白い問題でした。

 問題問題の原文は、https://www.hackerrank.com/challenges/baconian-cipher をご覧ください。概要としては次の通りです。
アルファベット小文字からなる文字列と改行が入力される
入力のアルファベットを変換し、それぞれ5文字のコードと改行を出力する
変換の規則は次の通り
“a”～“z”を 0 ～ 25 に対応させる
その数値を5桁の2進数 00000～11001 に変換する
2進数の桁の 0 を“-”に、1 を“*”に変換する

例えば、“abc(NL)”という入力に対しては、“-----(NL)----*(NL)---*-(NL)”( (NL)は改行 ) という出力になります。

 解説先に注意点ですが、2016/7/16現在、得点表にある通り、トップが98.46点 (77文字) に対し、私のコードは98.28点(86文字)であり、まだまだ縮む余地があります ( 縮める実力があるかは別問題 )。あくまで as-is のコードに対して、ということでご了承ください。( いやまあ、トップのコードもう見れるんですけど )

 問題点実は、この問題の制限として、実行環境が bf というソフトで、しかも制限があります。特徴としては次の通りであり、講座で取り扱っていた bff とは少し異なります。
セルのサイズが1バイト ( 最大値 2^8-1 )

,でEOFだった場合の値は 0
開始セルより左には移動できない ( 実行時エラーになる )
wrap-around禁止 ( 最大値からの+や、0 からの-は実行時エラーになる )
厄介な点は3.と4.で、セルに端があるということは、スライド型のループを自在には使えなくなるということですし、また wrap-around禁止にされると、予め負の数をセットしておくことができなくなりますので、-1終端のジャンプや、逆順の引き算 ( x-1 の代わりに -1+x を計算するもの ) が使えません。
この辺を踏まえて実装を考える必要があります。

 ポイントの整理さて、実装するにあたってポイントがいくつかあります。
改行の検出

EOF検出ではなく改行検出で処理する必要があります。一般的には、1文字先読みのEOF検出 ( 次の1文字はストックしておいて、ループの次で使う ) という方法もあるのですが、ループのスライドに制限があるため、非常に使いづらくなっています。かと言って naive に,----------[ 処理 ,----------]として改行を検出するのでは、2度の-10の分がそれないりに長いです。そのため、どのように効率良く改行を検出できるか、がカギとなります。
出力文字のコード

出力するのが“-”(45)と“*”(42) です。2進数の桁 0,1 からの変換をどのように共通化できるか、また、大きさが逆転しているところ、どのように効率的に対処できるか、が問題です。 ( 負の値を使えないところが地味に効いてきます )
divmod 2 演算

2進数への変換のため、divmod 2 を繰り返すわけですが、典型的な実装は汎用的ではあるものの、少し長くなってしまいます。ここをどのようにカスタマイズするか、が重要です。

 実装次のBrainf**k(86文字、コメントを除く)を実装しました
** memory layout:
*   init       : si 
*     s  start cell
*     i  input character
*   divmod loop: snrq_
*                s_rnrq_~
*     n  number to divmod by 2
*     r  remainder
*     q  quotient
*     
*   output loop: sororororor
*     o  output character code
**
** input loop **
s>i,[i
 ** divmod loop **
 in--[++
  n[n-[n->r]>rq?+>[q+>_]_<<<n]
  n>r+
 r>q--n (slide)]
 ** slide to the last remainder ( or blank if a newline )
 n<-r[->_]
 ** output if not a newline comes
 <<r?[
  ** output loop **
  r[
  r+++++++++++++
   r[-<o+++>r]
   r<o.[-]
  o<r(slide)]
  ** newline and next character **
  s>i++++++++++.,
 i<s]
s?>i?]

 実装上のポイント
 divmod 2 のカスタマイズポイントの整理で挙げたように、2進数の桁と出力する文字のコードは、大きさが逆転しています。かといって、できた桁を引き算していたのでは無駄があります。そこで、元から逆転した形で余りを出すように、かつ短く実装したのが次の divmod 2 です。
  n[n-[n->r]>rq?+>[q+>_]_<<<n]
  n>r+
これは、n→n%2,n/2 を計算するものではなく、n→n%2,(n+1)/2 を計算するものです。そして、元の数を i-97 ではなく、i そのままで用いることで、2進数の桁を逆転させています。すなわち、
naiveなdivmod2: 0→(0,0), 0→(0,0), 0→(0,0), 0→(0,0), 0→(0,0)
カスタマイズ版: 97→(49,1), 49→(25,1), 25→(13,1), 13→(7,1), 7→(4,1), …
なお余りについては、出力のループで 0 終端での走査を行うため、1 加算して 1,2 にしています。

 改行の検出上で紹介した divmod 2 を使った場合、商・余り( (n+1)/2, n%2 )が最後どのように推移するかというと、次のようになります。
一般のアルファベット ( 文字コード97～122 )

…→(2,0)→(1,0)→(1,0)→…
改行 ( 文字コード10 )

…→(2,1)→(1,0)→(1,0)→…
放っておくと、(1,0)を延々繰り返して終わりません。が、divmod loopの打ち切りを商が 2 の時にして、かつ最後の余りを見れば、適切に終了させて、かつ、アルファベットと改行を見分けることができます。
実際には、divmod loopを--[++ 処理 --]の形にすることで商 2 で打ち切り、出力ループの前にn<r-[r->_]を入れることで、改行の場合はブランクセルにずらす ( 結果出力ループに入らない ) ようにしています。

 その他その他、特筆すべきところは余りないのですが…。
文字コードの生成については、各余り ( +1 ) の 2,1 に 13 を加算した上で、×3 によって 45,42 を作ります。出力後、セルの再利用を行うため、[-]によってクリアします。
改行の出力については、他から流用できるものがないため、素直に++++++++++.で出力します。ただし、クリアして再利用する代わりに、,によって次の文字で上書きすることで、若干短くしています。

 終わりにアルゴリズム集等を参照して、各処理をパーツにして組み合わせて行けば、取り敢えず動かす分にはできるのですが、コードを短くするためには、セルの配置や処理のカスタマイズ等、細かく考えていかなければなりません。しかしながら、そこが醍醐味であるとも言えますので、興味を持たれた方は、Brainf**kのgolfにも挑戦されてはいかがでしょうか。
はじめに

問題

解説

問題点

ポイントの整理

実装

実装上のポイント

divmod 2 のカスタマイズ

改行の検出

その他

終わりに

Discussion
