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

はじめに

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

もともとは、しえるさんのこのtweetがきっかけでした。

単純な問題ではありますが、短く組むための課題が色々あり、なかなかに面白い問題でした。

問題

問題の原文は、Programming Problems and Competitions :: HackerRankをご覧ください。概要としては次の通りです。

  • アルファベット小文字からなる文字列と改行が入力される
  • 入力のアルファベットを変換し、それぞれ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. セルのサイズが1バイト ( 最大値 28-1 )
  2. ,でEOFだった場合の値は 0
  3. 開始セルより左には移動できない ( 実行時エラーになる )
  4. wrap-around禁止 ( 最大値からの+や、0 からの-は実行時エラーになる )

厄介な点は3.と4.で、セルに端があるということは、スライド型のループを自在には使えなくなるということですし、また wrap-around禁止にされると、予め負の数をセットしておくことができなくなりますので、-1終端のジャンプや、逆順の引き算 ( x-1 の代わりに -1+x を計算するもの ) が使えません。

この辺を踏まえて実装を考える必要があります。

ポイントの整理

さて、実装するにあたってポイントがいくつかあります。

  1. 改行の検出
    EOF検出ではなく改行検出で処理する必要があります。一般的には、1文字先読みのEOF検出 ( 次の1文字はストックしておいて、ループの次で使う ) という方法もあるのですが、ループのスライドに制限があるため、非常に使いづらくなっています。かと言って naive に,----------[ 処理 ,----------]として改行を検出するのでは、2度の-10の分がそれないりに長いです。そのため、どのように効率良く改行を検出できるか、がカギとなります。
  2. 出力文字のコード
    出力するのが“-”(45)と“*”(42) です。2進数の桁 0,1 からの変換をどのように共通化できるか、また、大きさが逆転しているところ、どのように効率的に対処できるか、が問題です。 ( 負の値を使えないところが地味に効いてきます )
  3. 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にも挑戦されてはいかがでしょうか。