Brainf**k ゴルフ事例解説-FizzBuzz(214)

はじめに

この記事は、Brainf*ck Advent Calendar 2019の23日目の記事です。
※なぜQiitaのAdvent Calendarじゃないんだというツッコミはご遠慮ください

概要

Brainf**kでのFizzBuzzのゴルフで、(cheatを除いた)トップの209文字にはまだ若干届かないものの、それまでの自己記録244文字を大幅に塗り替え、214文字へと記録を伸ばすことができたため、せっかくなので解説することにします。

予備知識

• Brainf**k
  この記事読む人に説明要らないよね? 実践的な話はBrainf**k講座(リンク)をどうぞ。
• ゴルフ
  コードゴルフの略。なるべく短い文字数でプログラムを組む競技。この記事で紹介しているゴルフ場 ( 競技を行う場 ) は、Anarchy Golf( 通称「アナゴル」 ) です。
• FizzBuzz
  技術者としての最低限の力量を試すために書かされる ( らしい ) 有名なプログラム。
  1～100の各数値に対して、15の倍数にはFizzBuzz、5の倍数にはBuzz、3の倍数にはFizz、その他は数字そのものを、それぞれ改行付きで出力させる。
• cheat
  この場合、処理系のバグを利用してコードの文字数を縮めるテクニックを指します。今回は対象外です。

環境

このゴルフ場での Brainf**k実行環境は bfi ですが、cheat を用いてないので、機能的には ideone の bff でも同じです。

あじさん(Azicore氏)謹製のブラウザ版インタプリタを利用する場合は、オプションでバッファの型を「4バイト符号付き整数」、終端を「-1」と設定してください。

各処理系の違いに興味がある方はうさぎ小屋:各種サービスにおけるbrainfuck処理系についてをどうぞ。

コード概要

コード全体

まずはコード全体を紹介します。解説のためコメントを入れていますが、提出版は+-<>[],.だけの214文字に絞ってます。
※Brainf**k処理系はコメントをスルーするので、どっちの版でも同じように動きます。

fizzbuzz.bf

 1: ** FizzBuzz(214) **
 2: ** memory layout: d_YXgbft__nzhF **
 3: 
 4: ** initialize **
 5: f++++[-
 6:  f>>>>n[->z+++>h++>F+<<<n]
 7:  n+>z->h++>F+[+++++++++<]
 8:  <<t,--
 9:  t<<<g,<X+Y<+[+++++++++++>]
10: >f]
11: 
12: ** main loop **
13: f<<g[
14:  g>b++[
15:   b>f+++++[-
16:    f<<<<Y+            ** increment **
17: 
18:    ** begin core part **
19:    Y>>>>>t+[
20:     t+++<f[
21:      f[<]<d[>]>>XY?[.<]  ** print number **
22:     ]
23:    ]
24: 
25:    ?>>[>]?>[n
26:     n>>>F.<h+.-<z..   ** print Fizz **
27:    z<<]
28: 
29:    <<t---<f[>]?>[t
30:     t>>>>z->>F[----.++++<<]>>z+..  ** print Buzz **
31:    z<<]
32:    ** end core part **
33: 
34:    >n.                ** newline **
35:   n<<<<f]
36:  <-b]
37:  ** carry ( move up ) operation **
38:  <<X+Y<----------<<d,
39: >>>>g-]

コードのコンセプト

Brainf**kでなるべく文字数を節約するための一般的な方針も含みますが、今回のコンセプトは次のようになります。

• 出力用変数の事前準備
  特に数値をdivmodで処理して動的に桁数分出力するのはエレガントですが、都度文字を用意するコードは意外と文字数コストがかさみます。
  そこで初期化の時に必要な分を全て用意して使いまわします。
• 出力用変数の節約
  出力する文字は B,F,i,u,z と数字(2桁)、改行とありますが、全てを個別のセルに用意するのは、処理中のセル間移動距離も、用意するためのコード量も不利になります。
  そこで、B,F、u,z を同じセルでまかない、変数を節約することにします。文字の違いは、都度値を増減させて対応させることにします。
  ※改行については、値として10にすぎないので都度作る選択肢もあるのですが、今回は初期化の中で値を作っておくことにします。
• 制御の単純化
  FizzBuzzで求められる制御変数は、最低限5つです。
  それは、「3の倍数か判定する周期3のカウンタ」「5の倍数か判定する周期5のカウンタ」「5の倍数の時繰り上がりが発生するか判定用」「出力する数字が1桁か2桁かの判定用」「終了判定用」
  これを、10×2×5 の3つのカウンタによる3重ループをベースとした管理にすることで、制御の単純化を、更に結果的にコード量の削減を図ります。
  ※周期3のカウンタはこの3重ループとは独立に管理します。

メモリレイアウト

以上を踏まえて、メモリレイアウト ( どのセルをどのような変数として扱うか ) は、コード2行目のコメントのようにします。

コメント抜粋

 2: ** memory layout: d_YXgbft__nzhF **

この d,Y,X,g,b,f,t,n,z,h,F がそれぞれ変数を表します。これは、各コードの中で「今どのセルにいるか」を示すコメントとしてもたびたび現れます。それぞれ次の役割です。

変数	役割	詳細
d	数字の出力桁数判定用	ゼロなら1桁、非ゼロの場合は2桁出力
X,Y	数字出力用の各桁	Xが10の位、Yが1の位の数字のASCIIコードに対応
g,b,f	3重ループのカウンタ	gがトップレベル(周期10)、bが繰り上がり判定用(周期2)、fが5の倍数判定用(周期5)
t	3重ループと独立したカウンタ	3の倍数判定用(周期3)、負数でカウントアップさせて使う
n,z,h,F	数字以外出力用	n,z,h,F がそれぞれ改行,"z","h","F"のASCIIコードに相当、必要に応じて増減させて出力に用いる

初期化が済んだ状態で、次のような状態になっている想定です。
※ループカウンタb,fは、各ループの開始時に都度初期値をセットする。

コード詳細

全体の制御

では、コードの詳細ですが、まずは全体の制御からです。
初期化部分および、3重ループの最内部分のコアの処理 ( "begin core part" から "end core part" ) を除くと以下のようになっています。

コード全体像

 4: ** initialize **
…
12: ** main loop **
13: f<<g[
14:  g>b++[
15:   b>f+++++[-
16:    f<<<<Y+            ** increment **
17: 
18:    ** begin core part **
…
32:    ** end core part **
33: 
34:    >n.                ** newline **
35:   n<<<<f]
36:  <-b]
37:  ** carry ( move up ) operation **
38:  <<X+Y<----------<<d,
39: >>>>g-]

この構造は以下のような単純な処理を盛り込んだものになっています。

• gの初期値10に対し、ループ開始時にそれぞれb=2,f=5をセットして、10×2×5の3重ループを行う
• ループの最内では、最初にYのインクリメント ( 2桁の数値の1の位の増加 ) を、最後にnの出力 ( 改行 ) を行う
• 最外ループの最後では、桁の繰り上がりの処理として、Xの増加(繰り上がり)、Yの減少(また"0"に戻す)、そして d の非ゼロ値のセット ( 2桁出力フラグの有効化 ) を行う

ちなみに細かいところですが、g,bのカウンタのデクリメントはループの末尾、fはループの先頭になっています。
これは、ループ処理中g,bは非ゼロ値に保って利用したい反面、fは5の倍数判定のためにゼロ値が必要になるという違いから来ています。

数字出力

では、最内ループのコアな処理から、まずは数字出力部分です。

数字出力部分

19:    Y>>>>>t+[
20:     t+++<f[
21:      f[<]<d[>]>>XY?[.<]  ** print number **
22:     ]
23:    ]

3周期のカウンタ t をインクリメント ( 負のカウンタなので ) すると同時に、条件分岐で「3の倍数でない(t!=0)、かつ5の倍数でない(f!=0)時」だけ数値を出力します。

数値出力は、最初のうちは1桁、途中から2桁に変わるわけですが、そこは d で調整します。
出力ループ [.<] を開始するセルが、直前の d[>]>> で決まるわけですが、d がゼロなら Y 開始に、非ゼロなら1つずれて X 開始になる、その違いです。
出力時のセル移動イメージは次の例を参考にしてください。

なお、t,f の条件判定のところで else条件 ( t=0 や f=0 ) については全くケアしていませんので、23行目で処理を抜けた時のセル位置は3通りズレが出ます。そのケアは次の Fizz出力で行います。

あと細かいところですが、20行目で t を3増加させてるのは、後 (29行目) の 3減少と辻褄を合わせるためです。

Fizz出力

次に、3の倍数の場合のFizz出力の処理です。

Fizz出力部分

25:    ?>>[>]?>[n
26:     n>>>F.<h+.-<z..   ** print Fizz **
27:    z<<]

上で「セル位置は3通りズレが出ます」と書いた通り、この処理に入るときは次のようにセル位置が変わります。

• 3の倍数の場合
  t=0のため t のセルにそのままとどまっている
• 3の倍数ではないが5の倍数の場合
  f=0のため、数字出力の分岐に行けず、f のセルにとどまっている
• 3の倍数でも5の倍数でもない場合
  数字の出力を行って、Y の左隣のセルに来ている

そこを ?>>[>]?> によって、3の倍数の場合のみ非ゼロセルである n に移動させます。
イメージとしては次図の通りです。灰色のセルは、値は分かりませんが非ゼロと分かっているところです。

今更な話ですが、t,n 間に2個のゼロセルを用意しているのは、こういった調整ができるように、という意図があります。※経験上、2個あれば大抵なんとかなる

Fizz の出力そのものは特記すべきことはありません。ただ、出力が終わった後は n の隣に出て、そこで3の倍数かどうかでズレていたセル位置を合わせます。

Buzz出力

そして、最内ループのコアの最後はBuzzの出力です。

Buzz出力部分

29:    <<t---<f[>]?>[t
30:     t>>>>z->>F[----.++++<<]>>z+..  ** print Buzz **
31:    z<<]

これは、f=0 かどうかの判定になるので、一度 f[>] で非ゼロ時には場所をズラしておいて、次の ?>[ で、非ゼロの t のセルで分岐に入ります。
最初に t を3減少させているのは、0 になったループカウンタ t を巻き戻すためです。これによって、t は必ず非ゼロ ( -1～-3 ) に戻りますので、3の倍数で一旦 t=0 ってなっていたとしても Buzz 出力用の分岐に使うことができます。

なお、出力用の文字 B,u はそれぞれ F,z から作ります。先に z を 1減らして 121(y) にしておいてから、

• F: 70(F) → 4減少して66(B)にして出力 → 4増加して元に戻す
• z: 121(y) → 4減少して117(u)にして出力 → 4増加して元に戻す

このように同じパターンで処理できるため、F[----.++++<<]でまとめて若干の文字数節約にしています。

初期化の工夫

順序が前後しますが、最後に初期化部分についてです。

一般的な話として、[+++…+<]をループに組み込んで複数の値をまとめて作る方法をよくつかいます。
例えば ++++[->>A+>B++>C+++[++++++<]<] とすると、A=4×(1+6)、B=4×(2+6)、C=4×(3+6) と複数の値をセットすることができ、かつ単純な ++++[->A+++++++>B++++++++>C+++++++++<<<] に比べると、共通の +6 をくくりだすことができている分文字数がお得です。

しかし、これは連続した位置に値をつくるという前提になりますし、作る値の大小がマチマチだとあまり意味がありません。
そこで今回ちょっとした工夫を考えだしました。

初期化部分

 5: f++++[-
 6:  f>>>>n[->z+++>h++>F+<<<n]
 7:  n+>z->h++>F+[+++++++++<]
 8:  <<t,--
 9:  t<<<g,<X+Y<+[+++++++++++>]
10: >f]

7行目の n+>z->h++>F+[+++++++++<] は、通常通りのまとめて値を作るパーツです。
ここの部分で、n: +1+9 (+10)、z: -1+9 (+8)、h: +2+9 (+11)、F: +1+9 (+10) の効果があり、そのままなら 4×10, 4×8, 4×11, 4×10 が作られるだけです。
しかし、6行目の処理 n[->z+++>h++>F+<<<n] によってループの前回分でセットされた n の +10 を増幅して配ります。ループ毎に z: +10×3、h: +10×2、F: +10×1 の効果です。

これにより、次のように大きさがマチマチな値を効果的に作ることができました。
※122のような、何かの倍数としてキリのいい数字でないものを直接作れるのもメリットです。

• n: 最後のループでセットされた +10 のみが残る
• z: 毎ループの +8 に加え、初回以外の +10×3、合計 8×4+10×3×3=122
• h: 毎ループの +11 に加え、初回以外の +10×2、合計 11×4+10×2×3=104
• F: 毎ループの +10 に加え、初回以外の +10×1、合計 10×4+10×1×3=70

なお、9行目の処理 g,<X+Y<+[+++++++++++>] はほぼ通常通りの組み方です。
ただ、g の位置では毎ループ , で強制的に EOF の -1 をセットするため、ループ回数による増幅効果がありません。そのことで逆に、g=10 という小さい値を一緒に作るのに役立っています。

終わりに

一位を奪取できたわけではないのが若干弱いところですが、それなりに文字数が縮んだのでネタにしてみました。工夫がはまればごっそり文字数が減るのが、Brainf**kのゴルフの気持ちいい点ですので、やったことない方も一度なにかゴルフ問題に挑戦してみるとよいのではないでしょうか。