🧠
Brainf**k講座(応用編) 効率のよいアルゴリズム

2024/12/11に公開
AtCoder
 はじめに
 背景本記事は、Qiitaのesolang Advent Calendar 2024 の、11日目の記事です。

今回は、Brainf**k講座の応用編ということで、コード長や使用するセル数の面で効率のよいアルゴリズムを幾つか紹介したいと思います。

 実行環境今回は特に実行環境を指定しません。8bitセルでも32bitセルでも同じように使えるコードを紹介します。ただし、wrap-around禁止だと使えなくなるものも一部あります。また、一部事例紹介として、8bitセルのatcoderで実行したコードを取り上げています。

 アルゴリズム
 大小比較ではまずは大小比較のアルゴリズムからです。単純ながら使用頻度も高く、また差の計算や最大値/最小値の取得等、応用範囲も広いアルゴリズムです。

※記事「Brainf**k講座(応用編) atcoderでの頻出処理」の「複数の数値の入力」の章 では、その応用形も活用しています。

 基本形2セルおいて、A,B ( 位置をa,bとする ) という非負の数値が保存されている状態で、2数の大小およびその差を計算する形態が基本形となります。a の方が左だとして、a の右隣 ( f とする ) には初期値 1 を、更に右隣 ( bの左隣 ) はゼロだとして、コードは次のようになります。
大小比較コード
a[>>>b[-<]<<af?-]
処理としては、a のセルをループの制御に使い、a,b ともに1ずつ減らしていくようになっています。これで、a が先にゼロになればそのままループから抜けますが、b が先にゼロになった場合、初期値を 1 とした f でループを終えるように仕掛けがしてあります。

つまり、大小関係によって次のように結果に、特に終了位置に違いが出ます。

コメントを抜くと [>>>[-<]<<-] という非常に短いコードで大小比較・差分計算ができるということでかなりシンプルで美しい実装だと思います。

なお、上の図の通り終了位置に違いが出るため、「終了セルの右隣りが 1 かどうか」で分岐するところまでセットで考えます。典型的には、次のような形になります。
大小比較・分岐テンプレート
** 比較・差分計算 **
a[>>>b[-<]<<<af?-]
** 分岐 **
>[f-
 >>b : 差分D保存位置
 ** A le B の場合の処理 **
<]
<<a[ : 差分D保存位置
 ** A gt B の場合の処理 **
a[-]]a
なお、A = B と A \lt B を区別したい場合は、A \le B の分岐 ( 前半 ) で、b の位置の差分 D がゼロかどうかを見て更に分岐させます。
蛇足ながら、上のコードは a の方が左にあるパターンで組んでますが、左右逆なら <> を入れ替えたコードで対応できます。

また A,B の値が非負でなく非正の場合は、f の初期値を -1 にした上で、- の処理を + に置き換えて対応することができます。

※分岐が A \ge B と A \lt B、差分 D が非負となるというように、結果でも正負逆転が起こるのでその点注意が必要です。

 色々な形さて、上では基本形として a,b が2セル間に挟んだ位置関係のものを取り上げたわけですが、aの右にf(初期値1)とゼロ、bの左にゼロという5セル分が確保できていれば、基本形以外でも同じように大小比較を行うことができます。

特にコードの長さだけで言えば、a,bが左右逆でかつ隣り合う、図中の「逆転版」の方が短かったりもします。しかし、基本形は a の2つ右隣のゼロと b の左隣のゼロをオーバーラップして4セルだけで処理できるため、セルの消費という面でもっともコンパクトな形になっています。

※ f の右隣のゼロは、ループ処理そのものには影響ありませんが、その後の分岐の時に必要になってきます。

 値の保存これまでのコードでは、差分が結果として残るものの、元の A,B の値が捨てられてしまう実装になっていました。そこで、もう1セル使って復元が可能なように値を保存する実装も考えられます。保存するセル( s とする )を、a の左に置くか、b の右に置くかの2通りが考えられます。
大小比較(値の保存に対応)
** aの左に保存 **
a[a<s+>>>>b[-<]<<af?-]

** bの右に保存 **
a[a>>>b[>s+<-<]<<af?-]
と言っても、左・右というのは s として使える一番近いセルがそこになるという話であって、s は別にどこを使ってもよく、違いとして重要なのは「値の保存を内部の [] の中でやるかどうか」という点です。それにより、A \gt B のケースで、s の変化量に +1 の違いが出ます。
なお、s の初期値がゼロである必要はありません。そのため、上の図では変化量の形で s の値を表しています。初期値をゼロにしておけば、s の値は min(A,B) として使うことができます。( +1 の差が出るケースは別途要対応 )

更に、D の値を加算すれば max(A,B) も作り出すことができます。

 剰余算・除算続いては剰余算・除算です。これは既に典型的でかつ効率的なアルゴリズムが知られていますが、アレンジすることで状況によって更に効率を上げることができます。

 基本形のおさらいまずは基本形のおさらいです。詳細についてはBrainf**k講座(7) divmodアルゴリズムと数値出力に載せています。
剰余算・除算の基本形
** 剰余算(商なし) **
n[n->d-[>r+>]>?[r+[-<d+>]>>]<<<<n]

** 剰余算・除算(商あり) **
n[n->d-[>r+>>]>?[r+[-<d+>]>q+>>]<<<<<n]
商なしの場合は、被除数 n ( 値N )、除数 d ( 値D ) の2セルに対して、余り r と2つのゼロセルの計5セルで、商ありの場合はさらに商 q を追加した6セルでの N\div D の処理となります。

処理自体は n を制御変数とするループで、d,r の和を一定 ( D ) に保つように調整されており、商ありの場合は周期 D 毎に q を増やしていくという感じになっています。この2バージョンの違いは q を増やす処理の有無だけなので、商なしの方を基本として見るのが良いと思います。

いずれも、d の位置には正数 D-R が残るようになっており、こちらはあまり使わないのでゴミになることが多いです。
なお、N\div D の代わりに N\div(D+1) を計算するバージョンもあり、1文字だけコードが短くなります。コードの違いは d-[>r+～ の - が d[->r+～ と分岐の内側に移動している点と、>?[r+[-<d+>]>～ の r から d への書き戻しの時の + が無くなっている点です。

※d の位置に残るのは\div Dの場合と違って (D+1)-R ではなく D-R であり、値がゼロとなる可能性があります。
除数がD+1になるバージョン
** 剰余算(商なし) **
n[n->d[->r+>]>?[r[-<d+>]>>]<<<<n]

** 剰余算・除算(商あり) **
n[n->d[->r+>>]>?[r[-<d+>]>q+>>]<<<<<n]

 ÷1のケアさて、通常は上の基本形を使っていて困ることはあまり無いのですが、1つだけ「除数が2以上」という制約があります。つまり \div 1 の計算には対処できません。

※条件としては、最初に挙げた基本形だと D\ge 2、除数がD+1 になるバージョンの場合は D\ge 1 となります。

その理由は、商ありなら q を増やすタイミングである >?[r～ の分岐のところで、除数が2以上なら r が非ゼロで分岐に入れるところ、除数 1 では r がゼロのままで分岐に入れないからです。
そこで、この分岐を r で判定せずに、非ゼロの数値が残っている n で判定することで \div 1 のケアができるようになります。それが次のコードになります。
÷1をケアしたバージョン
** 剰余算(商なし) **
n[n>d-[>r+>>]<?[n>>r+[-<d+>]>]<<<n-]

** 剰余算・除算(商あり) **
n[n>d-[>r+>>>]<?[n>>r+[-<d+>]>q+>]<<<<n-]
なお、判定時に n が非ゼロで残っている必要がありますので、n を減らす処理はループ末尾に持ってくる必要があります。

※オリジナル版は、ループ先頭でも末尾でもどちらで n を減らしても良い。
こちらの方で\div 1のケアもできるのであれば、常にこちらを使えばいいじゃないかという意見もあるかも知れませんし、実際それでも良いと思いますが、コード長は1文字長くなります。

なお、こちらも \div(D+1) のバージョンを基本形の場合と同じように組むことができますが、詳細は割愛します。

 固定の除数用の実装続いては、思い切った割り切りをすることで効率化を図る例を紹介します。
基本形には「除数 ( D または D+1 ) が事前に分からない場合でも同じコードで対応できる」という強みがありますが、実際剰余算・除算をする場合、除数は固定になってることも多々あります。典型的には数値の10進数展開です。加えて「余りを計算することで場合分けにつなげる」ような場面では、余りそのものでなく、余りと連動した別の数値を求める計算でも十分だったりします。

そこで、N だけをセルに保存している状況で、除数はコードに埋め込んだ次のようなコードが有用な場合があります。

※「コードに埋め込んだ」というのは、\div 6 の除数 6 に対し、ループ内部の分岐での + の数を1少ない5個連ねるように組むことを言っています。
固定の除数用実装(÷6の例)
** 剰余算(商なし) **
n[n>r[->>]<?[n>r+++++(5)>]<<n-]

** 剰余算・除算(商あり) **
n[n>r[->>>]<?[n>r+++++(5)>q+>]<<<n-]
大きなメリットとしては ( D の数値の準備も込みで考えると ) コードが簡素化できていることと、d のセルが不要になっていることです。

ただし、次の図にあるように、基本形とは計算結果に違いが出るため注意が必要です。

\div 6 の計算で幾つかの N で実際に計算結果の違いを表にすると次のようになります。

N の増加につれ、R が 0→1→2→… と周期的に増えていくのに対し R' が 5→4→3→… と逆に減っていく点、Q'に変化の現れるNが1つずれている点が大きなところです。


N

基本形のR

基本形のQ


固定除数のR'

固定除数のQ'



0

0
0

0
0

1

1
0

5
1

2

2
0

4
1

3

3
0

3
1

4

4
0

2
1

5

5
0

1
1

6

0
1

0
1

7

1
1

5
2

8

2
1

4
2

さて、この実装を用いることで、「Brainf**k講座(7) divmodアルゴリズムと数値出力」の「数値出力」の章で行っていたようなスライドループによる十進数展開を置き換えることができます。
固定除数での十進数展開
n[ n+[>r[+>>>]<[n>r---------(9)>q+>]<<<n-] >r->q-n]
計算結果の違いは次のように対応します。

Q'の変化のタイミングの違いを吸収するため、N の代わりに N+1 を使用する。

R'の変化がNの変化と逆方向になるのに対応するため、r の位置の処理の +- を反転させる

(  R' の値が 0～9 ではなく -9～0 になる )
ループの終了判定を Q'=1 で行い、継続する場合は Q' を次の N として使用する。
実際に、123 を対象としてこの十進数展開を実行した場合のセル状況の推移は次のようになります。

なくても構いませんが、剰余算・除算終了後に r で - を実行しているのは、桁の値を -10～-1 とし、非ゼロであることを確定させるためです。この後、各セルを +58 することで数値出力用のASCIIコードに変換することができます。


 二進数展開最後に紹介するのは二進数展開です。ただ、前の章で剰余算・除算の延長で十進数展開を実装しているのと同じようにして、既に二進数展開を行う方法は分かっています。

しかし、ここでは実は、二進数展開に特化したもっと効率の良い実装があるため、それを紹介します。

 効率の良い二進インクリメント・デクリメントということで効率の良い二進数展開ですが、それは、末尾が 011…1 となっている二進数を1増加したら、同じ部分が 100…0 と単に0,1の反転となることを利用した効率の良いインクリメントの繰り返しを行う方法です。

典型的には、次のような実装になります。( 右側が上位桁とします )
効率の良いインクリメントの繰り返し
** nが二進数の桁と隣接する場合 **
n[[>]++[-<]>n]

** nが二進数の桁と離れている場合 **
n[->>>l[>]++[-<]<<n]
前提として、隣接のケースでは n の左隣に、遠隔のケースでは l (二進数の最下位桁) の左隣にゼロセルが必要となります。セルの状況の変化は次のような感じになります。

なお、あくまでインクリメントを繰り返しているだけなので、既にある二進数への加算としても使用できるのも良い所です。逆に、少し実装を変えればデクリメントによる減算も実現できます。こちらは末尾 10…00 を 01…11 に置き換える処理になります。
効率の良いデクリメントの繰り返し
** nが二進数の桁と隣接する場合 **
n[>-[++>-]<[<]>n-]

** nが二進数の桁と離れている場合 **
n[->>>l-[++>-]<[<]<<n]
これらの処理ですが、まずインクリメントによって最上位桁がどこになるかはこの処理だけでは不明なので、別途取り扱うデータから桁数を見積もって最上位桁を探る必要がある点と、デクリメントにより結果が負になるようだと暴走を引き起こすため、ゼロを下回らない範囲でのみ使うか、上位桁におまけを足しておくよう工夫する等の仕掛けが必要になる点、これらに注意が必要となります。

 活用例ではここで、丁度最近のatcoder ABC383 A問題で、実際に二進数を用いた実装を組んだ事例がありますので紹介します。

問題の詳細については割愛しますが、次のような計算を行うことで解くことができます。
Rubyでの解法疑似コード
def nextint()
  # 区切り文字(空白/改行)までのトークンを数値として読み込み、EOFでnil
  # 実装は割愛
end
gets     # 先頭行はスキップ
s = false  # 偶数番目のトークンでtrue
h = pt = 0   # H および前回のT用
while (n = nextint())
  if s
    h += n  # nをV値と見てH値に加算
  else
    h += pt  # 前回のT値をH値に加算
    h -= n   # nを今回のT値と見てH値から減算
    pt = n   # T値を退避
    h = 0 if h < 0  # 負値になっていたらゼロに戻す
  end
  s = !s  # s 反転
end
puts h  # 最終的にH値が答え
ここで、トークンの数値 n は高々100という前提になっているので1セルに収まりますが、h はこの問題の場合1万程度になる可能性があり、複数セルでの管理が必須になります。そこで、最後十進数に変換する手間がかかるものの、加算・減算が効率よく行えるよう、h を二進数管理にしたのが今回の実装です。

以下、実際に提出した379B版実装を、コメント付きに整理したものです。
ABC383-A問題379B版実装
** 先頭行スキップ **
+[,----------]
** hの最上位桁をセットアップ **
>>>>>>>>->+>>>>>>>>>>>>>>>>>>>
** 入力ループ **
c,+[
 ** 数字判定 **
 c++>>f+>-[----<<<[->]>>-]
 <[f- ** 数字の場合は蓄積している数値を更新 **
  <<<n[->c++++++++++<]>c[-<n+>]
 >]
 >>[[-]# ** 区切り文字 **
  <<<<<s[- ** 行後半(偶数個目トークン) **
   ** V値加算 **
   >n[n-<<<<l[<]++[->]>>>n]
  <]
  >[n ** 行前半(奇数個目トークン) **
   ** 前回のT値加算 **
   <<p[p-<<l[<]++[->]>p]
   ** 今回のT値減算および退避 **
   >>n[n-<<p+<<l-[++<-]>[>]>>>n]
   ** 最上位桁へ移動 **
   <<<-<+[-<+]-
   ** 最上位桁が立ってなければ減算の結果が負値と判断し値クリア **
   >m[+[->+]>>>]
   <[>+>+[[-]>+]>>]
  s+>n]
 >>>>]
<<<c,+]
** 二進数→十進数変換 **
<<<<-<+[-<+]->-
>+[-
 <<<<<<<<<<+[-
  [-[-[-[-[<+>-----[->++<]]>++<]>++<]>++<]>++<]
 >>+]
 >->[-<<<+>>>]
>+]
** 先頭桁検出 **
<<<<<<<<<+[,
 <[<<]>[+]
>>+]
** 数値出力 **
<+[
 <-[----->+<]
 >----.
>>+]
入力ループの部分が処理のメインとなっていますが、区切り文字によってトークンの数値が確定した時の分岐において、V値加算、前回のT加算でインクリメントによる加算を、今回のT値減算でデクリメントによる減算を行っています。

※上の説明とは逆に左の方を上位桁としているため、<> の対応が逆になっています。
実際の計算として、減算によってH値が負になる可能性があるため、二進数の最上位桁に予め 1 を足しておいて、これがゼロになるかどうかで負になったかの判断をしています。

セル位置を示すアルファベットおよび、途中でのセル状況は次の通りです。( 問題での入力例2に対応しています )


 おわりにということで、今回3つのカテゴリで効率の良い実装を紹介しました。こういった実装を蓄積しておいて適切に組み込めるようになると、自然と全体もコンパクトな実装になっていくのではないかと思います。golfで頑張りたい場合もそうですが、競技プログラミング的な場面でも是非ご活用下さい。