Brainf**k講座(3) スライド型ループ

はじめに

既に基本機能をマスターされたことと思われますBrainf**k講座、ループ処理の幅を広げるために、実践的なコードに触れていきたいと思います。

講座一覧

1. Hello, BF!
   導入およびシンプルなループによる数値生成
2. 数値入力と簡単なループ
   ,による入力と数値解釈、簡単なループの実例
3. スライド型ループ
   ループ継続の判断を行うセルの位置をずらしていくループ

   実行環境

4. ideone
   オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。
5. [Brainf**kインタープリタ(http://azisava.sakura.ne.jp/js/bf/)
   あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。
   ※オプションで「バッファの型」を「4バイト符号付き整数」、「標準入力の終端」を「-1」と設定すると、bffと同じ挙動になります。

今回の話題

スライド型ループ

さて、今までのループでは、いずれかのセルを固定してカウントダウンすることで、ループ制御変数として使用するものでした。
すなわち、[でループに入る時と、]でループ終了判定を行う時は同一のセルにいる、ということです。

しかしながら、Brainf**kとしては、このように[, ]で同じセルにいなければならないという決まりはありません。あくまで、「現在のセルが0かどうか」で挙動を変えるのみです。むしろ、異なるセルを使うことで、例えば不定長の文字列等の処理に対応できるようになるなど、ループ処理の幅が広がります。これを便宜的にスライド型ループと呼ぶことにします。

実例1:parindrome生成

では実例を挙げて、スライド型ループがどのように使われるか見ていきたいと思います。
ここでは、このような問題を考えます。

• 0でない数字 ( 桁数不明 ) が入力されるとき、元の数の後ろに、元の数の桁を反転した数をくっつけた、倍の桁数の回文 ( parindrome ) になる数字を出力する
  ※これ実は、CodeForcesで実際にあった問題だったりします。

さて。「元の数の桁を反転」ということは、入力された数字を全て覚えておく必要があるということです。入力に改行がない場合、Rubyで敢えて1文字毎のループで書くと次のようになります。

a=[]
while c=$<.getc
  putc c
  a.push c
end
a.reverse_each do |c|
  putc c
end

ではこれをBrainf**kで書くとどうなるでしょうか。文字列を保存する部分と、文字列を逆順に辿る部分と、2つのループが必要です。これらは、それぞれスライド型のループで実装することができます。

スライド型ループ1: 文字列の保存

では、文字列を ( 出力しながら ) 保存するコードを見てみます。

i,+[
 i-.>n
n,+i]

,+[～,+]の形は、EOF検出まで文字を読み込むループとして、前回でも出た形です。しかし、違うところとしては、ループ内で>によってセルを移動することで、[,各]実行時のセル位置がずれていくことです。図示すると次のようになります。

これにより、不定長の入力文字列を出力しながら、セルに保存していくことができました。
なお、ループ内で-によって 1 減らしているのは、入力時に+で増やした分を元に戻すためです。また、ずれていく場合は、セルの役割をコメントで書きづらいのですが、ここでは n が入力後に i にずれることを n,+iのように表しています。

スライド型ループ2: セルの走査

では今度は、セルに保存された各値を逆順に走査して出力していく部分です。

もし桁数が固定であれば、.による出力と、<による移動を、特定の回数繰り返せば済むのですが、今回桁数は不定長になっています。そこで、「数字が途切れるところまで」という形でスライド型のループを実装します。コードとしては次のようになります ( 先ほどの続きです )。

<c[c.<nc]

セルに保存されている入力文字列の左隣は、初期状態のセルで値が 0 となっていますから、そこまで移動したところでループから抜けることになります。図示すると次のようになります。

スライド型ループ2の応用例

• マーカージャンプ
  上の例では 0 という特定の値まで走査するため、[ 処理 <]という形のコードになっていますが、0 以外の値、例えば -1 でも +[ 処理 <+]という形にすることで ( + によって -1 が 0 になるため ) 対応できます。
  そのため、値が0のままのセルも含めて、-1 をマーカーとしてそこまでジャンプするコードは次のように書けます ( 左向き移動の場合 )。

+[-<+]

• 複数の値を作る場合の短縮
  第1回の“Hello, BF!”コードで、複数の値を作るために、ループ中に複数のセルで加算していく処理がありましたが、それぞれが大きい値の場合コードが長くなってしまいます。そこで、ループ制御変数と各操作セルの間にゼロの堀を作って置いて、共通の値を足すようにするコードが考えられます。A～Fでの+5,+7,+11,+12,+17,+18を行う代わりに、一旦-4,-2,+2,+3,+8,+9で非ゼロの値をセットしておいて、一括で+9させる、というコードです。

** before **
X++++++[-
 >A+++++
 >B+++++++
 >C+++++++++++
 >D++++++++++++
 >E+++++++++++++++++
 >F++++++++++++++++++
<<<<<<X]

** after **
X++++++[-
 >
 >A----
 >B--
 >C++
 >D+++
 >E++++++++
 >F+++++++++
 [+++++++++<]
<X]

実例2:i番目の文字

さて、2つ目の例として次の問題を挙げてみます。

• 文字列 s と数値 i が1行ずつ入力される時、s の i番目の文字を出力する
  ※これはAtcoder Beginner Contest 041 のA問題です

先ほどは「特定の値」を走査するコードがありましたが、今度は「指定の文字数」であり、性質が異なっています。

前処理

まずは、入力を処理する所までを実装します。

** input ( until a newline ) **
,----------[++++++++++ >> ,----------]
** move back to the left end **
<<[<<]
** input number **
,----------[
 * x10
 >[-<++++++++++>]
 * convert ( minus 38 )
 ++++++[-<------>]<--
 * move back
 [->+<]
,----------]

これは、主に次の3つの処理から構成されています。

• 改行までの文字列入力 ( 今回のスライドループ1 )
• 文字列の先頭への移動 ( 今回のスライドループ2 )
• 複数桁対応の数値解釈 ( 前回 )

なお、EOFではなく改行を検出する必要があるため、,+[ 処理 ,+]の代わりに,----------[ 処理 ,----------]と、入力コードを-10するようにしています。また、文字列の保存は1セルおきに行うため、移動は2セルずつで行います。
s=“abcdefg”, i=4 の場合、この前処理が終わった段階で、各セルの状況は次の図のようになります。

スライド型ループ3:指定距離移動

では、i文字目というのはどのように考えれば良いでしょうか。

次の図は、各 i の値に応じて、出力すべきコードの保存されたセルをオレンジで色付けしたものです。

それぞれ緑のゼロ値セルの隣と見れば、$2(i -1)$の距離のセル移動と考えることができます。そのため、制御変数を使ったループにスライド型の性質を盛り込むことで対応することができます。コードとしては次のようになります。

i-[
 i-[->>n+<<i]
>>ni]
>c.

これは、[ 処理 >>]のように、2セル単位でずれていくスライド型のループになっています。が、中にある-[->>+<<]という、制御変数をデクリメントしつつ2セル隣に移すという処理によって、ずれた先でも制御変数を見続けることができるようになっています。図示すると次のようになります。

Brainf**kというのは、あくまで「その場」のセルを使って、条件判断も含め処理を行う必要がありますから、セルの位置がずれていく処理では、常に使う値はこのように運ぶことになるのです。

まとめ

• 対になる[と]で、セルの位置を合わせる必要はない
• [と]でセルの位置を変えていく、スライド型のループがある
• スライド型ループの例としては、次のようなものがある
  • 文字列の保存
  • セルの走査
  • 指定距離移動

終わりに

今回までで、主だったループ処理を紹介しました。次回からは if文相当の条件分岐の話題に移りたいと思います。