はじめに
この記事はBrainfuck Algorithms - Esolang Wikiの内容を翻訳したものです。このWikiはCC0に基づいて提供されています。
Brainfuck Algorithms
この記事では、Brainfuckで使用できるいくつかのアルゴリズムを紹介します。
汎用性の為に、アルゴリズム部分では<と>の代わりに変数名を用います。一時的に用いるセルはtempと表記します。あるセルが入力と出力の両方で使用される場合、入力を含む場合は{セル名}、出力を含む場合は{セル名}'と表記されます。プログラム内でアルゴリズムを使用する際には、ポインタを目的のセルに配置するため、変数名を適切な回数の<または>命令に置き換えてください。
例 :
もしaがセル1で、bがセル4であり、ポインタがセル0にある場合、これが
a[b+a-]
こうなります。
>[>>>+<<<-]
特定のアルゴリズムがセル値の循環1を必要とする場合、その旨が注記されます。循環無し版が判明している場合は、それも併記されます。「一時的なメモリセルがすでに0である」、「計算に使用される変数を0のままにしておける」等とは仮定されません。したがって、正確な条件が判明している場合、いくつかの最適化を施すことができます。
コメントループ
セル値が0だと判明している場合、ループ命令をブロックコメントとして使用できます。これは有用で、句読点としてよく使用される,や.のようなbrainfuckの命令に含まれる文字を自由に使うことができます。唯一の制約は、[と]はループ命令として解釈されるため、両方の数を一致させなければならないことです。
プログラムの始めに書けばヘッダーコメントになります。
[comment]code
初期セル値について一切の仮定を置かないようにするには、まずセル値をクリアしてください。
code[-][comment]code
ループは現在のセルが0の場合にのみ終了するため、他のループの後ろには安全にコメントを配置することができます。
code,[.,][comment]code
このコメントの書き方は、値が0の(または0にした後で復元できる)セルに戦略的に配置しないと、内部コメントとしてうまく機能しません。
全ての文字をメモリに読み込む
,[>,]
改行またはその他の文字まで読み込む
----------[++++++++++>,----------]++++++++++
マッチさせる文字コードに合わせて+/-の数を調整してください。最後の+を全て削除することで、終端の文字を削除できます。循環が必須です。
複数の文字のいずれかまで読み込む
+>[
>,
(-n1)[(+n1)[>+<-]]>[<+>-]<
(-n2)[(+n2)[>+<-]]>[<+>-]<
etc
]
(+/-n1)ではその+/-をn1回繰り返します。n1、n2、etcはマッチさせたい文字コードです。文字コードごとに一行ずつ記述してください。
x = 0
循環あり
x[-]
循環なし
帰属 : User:quintopia
これは無制限・符号付きの実装において、セルの符号に関係無くセルを初期化します。
temp[-]†
>[-]†
x<[-]>[†
temp>-[x+temp+>+]
x[temp>]
<[+[x-temp>-<-]x<]
>
]
temp[-]
>[+]
† temp、tempの右隣、xの左隣のセルがそれぞれ負の値を含む場合、各行の+/-を反転させる必要があります。
tempの二つのセルを単に初期化するだけでなく、xの符号に基づいて条件付けすることもできます。
帰属 : JungHwan Min
x
>[-]
>[-]
<<
[
>+[-<+>>+<]
<[>]>
[
+[-<+<->>]
<[->+<]
]
>[-<+>]
<<
]
>[-]<
xと右隣の2つのセルを使用します。
元々のコードはCode Golf Stack Exchangeに投稿されています。
x = y
temp0[-]
x[-]
y[x+temp0+y-]
temp0[y+temp0-]
x´ = x + y
循環あり
temp0[-]
y[x+temp0+y-]
temp0[y+temp0-]
y[-x+y]x
x´ = x - y
循環あり
temp0[-]
y[x-temp0+y-]
temp0[y+temp0-]
x´ = x * y
temp0[-]
temp1[-]
x[temp1+x-]
temp1[
y[x+temp0+y-]temp0[y+temp0-]
temp1-]
x´ = x * x
帰属 : Softengy(talk) 2020/4/7 15:44(UTC)
$x * x = \displaystyle \sum_ {i=0} ^ {x - 1} 2 \times i + 1$に基づいています。
x[temp0+x-]
temp0[-[temp1+x++temp0-]x+temp1[temp0+temp1-]temp0]
x´ = x / y
帰属 : Jeffry Johnston
temp0[-]
temp1[-]
temp2[-]
temp3[-]
x[temp0+x-]
temp0[
y[temp1+temp2+y-]
temp2[y+temp2-]
temp1[
temp2+
temp0-[temp2[-]temp3+temp0-]
temp3[temp0+temp3-]
temp2[
temp1-
[x-temp1[-]]+
temp2-]
temp1-]
x+
temp0]
循環あり
帰属 : Softengy(talk) 2020/4/7 17:06(UTC)
このアルゴリズムはx / yを計算し、xに余りを、qに商を格納します。
x[
temp1+[
y[x-[temp1+†]temp1-temp0+y-]
temp0[y+temp0-]q+temp1
]
]
x[y[temp0+x+y-]temp0[y+temp0-]q-†]
† 値が0の任意のセルに移動します。
x´ = x ^ y
帰属 : chad3814
temp0[-]
x[temp0+x-]
x+
y[
temp1[-]
temp2[-]
x[temp2+x-]
temp2[
temp0[x+temp1+temp0-]
temp1[temp0+temp1-]
temp2-]
y-]
xとyの交換
temp0[-]
x[temp0+x-]
y[x+y-]
temp0[y+temp0-]
循環あり
x[-temp0+y-x]
y[-x+y]
temp0[-y+x+temp0]
x = -x
循環あり
temp0[-]
x[temp0-x-]
temp0[x-temp0+]
循環なし
signxが0の時は正、1の時は負とします。
temp0[-]
signx[temp0-signx-]
temp0[signx+temp0-]
x´ = not x (ビット単位)
循環あり
temp0[-]
x-
[temp0-x-]
temp0[x+temp0-]
別バージョン
x-[[-]+y](y-1)
yはポインタ配置のためだけにあります。xをx番目(x >= 1)とし、yがxより大きいことを忘れないでください。
循環なし
8ビットセルでの回答を出力します。他のセルサイズではtemp1を2 ^ ビット数 - 1にセットしてください。
temp0[-]
temp1[-]+++++++++++++++[temp0+++++++++++++++++temp1-]
x[temp0-x-]
temp0[x+temp0-]
0のセルまで移動
右
[>]
左
[<]
0以外のセルまで移動
帰属 : Epsilon
右
+[>[<-]<[->+<]>]>
左
+[<[>-]>[-<+>]<]<
ポインタの開始セルが0であることを前提としています。0以外では問題が発生します。
ポインタをx個先の(空の)セルに移動
帰属 : Kman
ポインタをxの回数だけ右か左に移動させます。(循環なし)
右
(ポインタはxを指しています)
>++[-[+>]+[<]>-]>[[-]>]
左
(ポインタはxを指しています)
<++[-[+<]+[>]<-]<[[-]<]
-
xから±xまでのセルは[[-]>]の[-]の部分によって0になります。もし[-]を削除すれば、それらのセルはインクリメントされるようになります。 -
xからx ± (x + n)までのセルの間にn個の0でないセルがある場合、それらのセルはスキップされます(再帰に注意してください)。 - (右/左に移動した際)
xセルの前後が0であることを確かめてください。そうしないと、次のセルが新たなxセルとなります。 - もし最低1セル移動するのを期待するなら、先頭の
>++/<++を削除してください。そうすれば、ポインタはx- 1だけ移動します(見て分かる通り、x> 1の時だけ動作します)。
x(y) = z (一次元配列) (配列要素ごとに2セル)
帰属 : Jeffry Johnston
x、temp0、temp1は連続しなければならず、xが最も左、temp1が最も右、その直後に配列用の十分なメモリが続く必要があります。配列の要素はそれぞれ2セルを必要とします。ポインタはxで終了します。
temp0[-]
temp1[-]
temp2[-]
y[temp1+temp2+y-]temp2[y+temp2-]
z[temp0+temp2+z-]temp2[z+temp2-]
x>>[[>>]+[<<]>>-]+
[>>]<[-]<[<<]
>[>[>>]<+<[>>]>-]
>[>>]<<[-<<]
-]+までのコードの処理により1が並んだ経路が作成されます。後続のループはこの経路を利用して、目的のセルを見つけます。そのセルは「データセル、1セル」としてグループ化されます。目的のセルは「データセル、0セル」なので、[>>]は適切な位置で停止します。xは常に0であり、[<<]の停止位置として機能します(最初のループでtemp1は初期化されますが、ループの末尾の+によって経路の最初の1セルに変換されることに注意してください)。次に、経路を辿り、[-]が目的のセルを初期化します。これで配列の準備は整ったので、temp0[dest+temp0]という形式の加算ループを用いてtemp0の値を目的のセルに移動させます。最後に、1の経路を前方に辿り、戻り際にそれらを初期化しながら、左側の停止位置であるxで停止します。配列に必要な連続したメモリの数は$3 + 2 * 配列の要素数$です。
x = y(z) (一次元配列) (配列要素ごとに2セル)
帰属 : Jeffry Johnston
y、temp0、temp1は連続しなければならず、xが最も左、temp1が最も右、その直後に配列用の十分なメモリが続く必要があります。配列の要素はそれぞれ2セルを必要とします。ポインタはyで終了します。
x[-]
temp0[-]
temp1[-]
z[temp1+temp0+z-]temp0[z+temp0-]
y>>[[>>]+[<<]>>-]+[>>]<[<[<<]>+< (pointer is at y)
x+
y>>[>>]<-]<[<<]>[>[>>]<+<[<<]>-]>[>>]<<[-<<]
x(y) = z (一次元配列) (配列要素ごとに1セル)
帰属 : Tritonio
space、index1、index2、dataは連続、かつ0で初期化されている必要があります。spaceが最も左、dataが最も右、その直後に配列用の十分なメモリが続く必要があります。配列の要素はそれぞれ1セルを必要とします。ポインタはspaceで終了します。index1、index2、dataは最後に初期化されます。
z[-space+data+z]space[-z+space]
y[-space+index1+y]space[-y+space]
y[-space+index2+y]space[-y+space]
>[>>>[-<<<<+>>>>]<[->+<]<[->+<]<[->+<]>-]
>>>[-]<[->+<]<
[[-<+>]<<<[->>>>+<<<<]>>-]<<
このアルゴリズムの仕組みについてはこちらの記事をお読みください。
x = y(z) (一次元配列) (配列要素ごとに1セル)
帰属 : Tritonio
space、index1、index2、dataは連続、かつ0で初期化されている必要があります。spaceが最も左、dataが最も右、その直後に配列用の十分なメモリが続く必要があります。配列の要素はそれぞれ1セルを必要とします。ポインタはspaceで終了します。index1、index2、dataは最後に初期化されます。
z[-space+index1+z]space[-z+space]
z[-space+index2+z]space[-z+space]
>[>>>[-<<<<+>>>>]<<[->+<]<[->+<]>-]
>>>[-<+<<+>>>]<<<[->>>+<<<]>
[[-<+>]>[-<+>]<<<<[->>>>+<<<<]>>-]<<
x[-]
data[-x+data]
x´ = x == y
循環あり
帰属 : Jeffry Johnston
このアルゴリズムは0(false)か1(true)を返し、yを変更しません。
temp0[-]
temp1[-]
x[temp1+x-]+
y[temp1-temp0+y-]
temp0[y+temp0-]
temp1[x-temp1[-]]
xまたはyを保持しない場合、以下の方法を用いれば、一時的なセルを必要とせずに実行できます。0(false)か1(true)を返します。
x[-y-x]+y[x-y[-]]
このアルゴリズムはz = x xnor yに似ています。
x´ = x != y
帰属 : Jeffry Johnston
このアルゴリズムは0(false)か1(true)を返します。
temp0[-]
temp1[-]
x[temp1+x-]
y[temp1-temp0+y-]
temp0[y+temp0-]
temp1[x+temp1[-]]
このアルゴリズムはz = x xor yに似ています。
帰属 : Yuval Meshorer
x == yの時は1を、それ以外は0をxに格納します。
x[
y-x-]
y[[-]
x+y]
x´ = x < y
帰属 : Ian Kelly
xとyに符号はありません。temp1は三つ連続した一時的なセルの最初のセルです。このアルゴリズムは0(false)か1(true)を返します。
temp0[-]
temp1[-] >[-]+ >[-] <<
y[temp0+ temp1+ y-]
temp0[y+ temp0-]
x[temp0+ x-]+
temp1[>-]> [< x- temp0[-] temp1>->]<+<
temp0[temp1- [>-]> [< x- temp0[-]+ temp1>->]<+< temp0-]
x´ = x <= y
帰属 : Ian Kelly
xとyに符号はありません。temp1は三つ連続した一時的なセルの最初のセルです。このアルゴリズムは0(false)か1(true)を返します。
temp0[-]
temp1[-] >[-]+ >[-] <<
y[temp0+ temp1+ y-]
temp1[y+ temp1-]
x[temp1+ x-]
temp1[>-]> [< x+ temp0[-] temp1>->]<+<
temp0[temp1- [>-]> [< x+ temp0[-]+ temp1>->]<+< temp0-]
z = x > y
帰属 : User:ais523
このアルゴリズムはバランスのとれたループのみを使用し、循環ありの実装が必須になります(ビット数が多い場合は非常に遅くなりますが、それ以外は問題ありません)。一時変数とxは0になります。yにはy - xが格納されます。(xの値を保持したいなら、ループ内でインクリメントする別の一時変数を用意し、xの値をコピーしておく方法もあります。)
temp0[-]temp1[-]z[-]
x[ temp0+
y[- temp0[-] temp1+ y]
temp0[- z+ temp0]
temp1[- y+ temp1]
y- x- ]
z = sign(x - y)
帰属 : User:quintopia
このアルゴリズムは循環なしの実装における二つの数値の比較です。二つの数値の符号は判明している必要があります。このアルゴリズムの一部は、ある数値とそれの符号が反転した数値の両方が判明している場合、未知の数値の符号を特定するためにも使用できます。zとその右側の4つのセルは空でなければならなりません(アルゴリズムの実行後にも再び空になります)。これは循環なしの実装において必要は仮定です。なぜなら、このアルゴリズムは、これらのセルをクリアするための方向を判断できないからです。括弧で示されるコードブロックには、比較結果に依存するコードが含まれている可能性があります。しかし、実際にはzの値が{ -1, 0, 1 }のいずれかになるまで待つ特別な理由はありません。
x[z>>+>-x-]†
y[z>>->+y-]†
z+>>
[->-[>]<<]
<[
(y>=x)
-
>>[
(y>x)
<<+>>[+]
]<
]
>>[
(x>y)
[+]
]
<<<
(y=xの場合にコードを実行する {if 0, then do} アルゴリズムをここに記述する)
† xとyが負ならば、これらの行の符号を反転させる必要があります。
x´ = not x (真偽値、論理値)
帰属 : Jeffry Johnston
このアルゴリズムは0(false)か1(true)を返します。
temp0[-]
x[temp0+x[-]]+
temp0[x-temp0-]
帰属 : Sunjay Varma
xを消費できるならば、このバージョンが使えます。また、xは0か1であると仮定します。xを消費したくない場合でも、このアルゴリズムは使用できます。xを別のセルにコピーしてから、操作を適用するだけです。このアルゴリズムは0(false)か1(true)を返します。
temp0[-]+
x[-temp0-x]temp0[x+temp0-]
上記Sunjay版の修正版
temp0[-]+
x[[-]temp0-x]temp0[-x+temp0]
この版に問題はありません。x > 1の場合、結果はx = 1と同じになります。
帰属 : Yuval Meshorer
xを消費する別のバージョンです。`x‘が1(true)の場合は0(false)を、0の場合は1を返します。
temp0[-]
x[temp0-x-]temp0+
帰属 : User:A
これはx = x == yを基にしており、yを0にしています。
y+x[-y-x]+y[x-y[-]]x
帰属 : User:tommyaweosme
右の1セルを使用します。
->+<[>+<[-]]>[<+>-]<-
帰属 : User:Waso
右の1セルを利用する、より効率的なアルゴリズムです。
-[>+<+]>[-<+>]<
y = not x (真偽値、論理値)
帰属 : FSHelix
理解しにくいバージョンです。xを保持し、合計3つの連続したセルを必要とします。
"y = not x"を計算するのにこのアルゴリズムを使う必要はありません。しかし、場合によっては、この考え方は非常に役立つでしょう。
実際、この考え方はこのページの他のコードにも反映されています。
# これらのセルをx, y=0, t=0と定義
x>y[-]+>t[-]<<x
[>y[-]]>[>t]
x == 0かどうかによって、[]ループ内でポインタの位置が変化するため、2つの異なる実行モードがあります。
以下は2行目の処理です。"*"はポインタの場所を示します。
If x==0: If x!=0:
x y t x y t
*0 1 0 *1 1 0
[>y[-]] *0 1 0 [>y[-]] 1 *0 0
[>y[-]]> 0 *1 0 [>y[-]]> 1 0 *0
[>y[-]]>[>t] 0 1 *0 [>y[-]]>[>t] 1 0 *0
x´ = x and y (真偽値、論理値)
帰属 : Jeffry Johnston
このアルゴリズムは0(false)か1(true)を返します。
temp0[-]
temp1[-]
x[temp1+x-]
temp1[
temp1[-]
y[temp1+temp0+y-]
temp0[y+temp0-]
temp1[x+temp1[-]]
]
z = x and y (真偽値、論理値) (循環あり)
帰属 : Sunjay Varma
このアルゴリズムはxとyを消費し(終了時に0にします)、結果をzに格納します。短絡評価のために、xまたはyは使用される直前まで評価しないでください。
このアルゴリズムは0(false)か1(true)を返します。
z[-]
x[
y[z+y-]
x-
]
y[-]
帰属 : Yuval Meshorer
xとyを消費し、xandyが1の場合はzに1を、それ以外では0を格納します。
z[-]
x[
-y[-z+y]
x]
| INPUT | OUTPUT | ||||
|---|---|---|---|---|---|
| x | y | x | y | z | |
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 0 | 1 | |
z = x nand y (真偽値、論理値)
帰属 : FSHelix
xとyを消費し、xとyが1の場合はzに0を、それ以外では1を格納します。
z[-]
x[
y[z-y-]
x-
]
y[-]
| INPUT | OUTPUT | ||||
|---|---|---|---|---|---|
| x | y | x | y | z | |
| 0 | 0 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 1 | |
| 1 | 0 | 0 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 0 | |
x´ = x or y (真偽値、論理値)
循環あり
帰属 : Jeffry Johnston
このアルゴリズムは0(false)か255(true)を返します。
temp0[-]
temp1[-]
x[temp1+x-]
temp1[x-temp1[-]]
y[temp1+temp0+y-]temp0[y+temp0-]
temp1[x[-]-temp1[-]]
帰属 : Yuval Meshorer
xまたはyが1の場合、1(x = 1)を返します(それ以外の場合は0)。
x > 1もしくはy > 1の時に使う場合、オーバーフローしないように注意してください。
例えば、x = 1、y = 255のとき、このアルゴリズムは0を返します。
x[
y+x-]
y[
x+y[-]
]
z = x or y (真偽値、論理値)
帰属 : Sunjay Varma
このアルゴリズムはxとyを消費し(終了時に0にします)、結果をzに格納します。短絡評価のために、xまたはyは使用される直前まで評価しないでください。
短絡評価を考慮しない場合、temp0は削除できます。temp0が削除され、xとyが1の場合、zには1ではなく2が格納されます。これは通常では0でないので問題ありませんが、留意はしておくべきです。
また、修正する方法として、これらのコードを末尾に追加してください。
z[x+z[-]]
x[z+x-]
このアルゴリズムは0(false)か1(true)を返します。
z[-]
temp0[-]+
x[
z+
temp0-
x-
]
temp0[-
y[
z+
y-
]
]
y[-]
帰属 : Yuval Meshorer
xとyを消費します。一時的なセルを使用しません。xかyが1の時はzに1を、それ以外では0を格納します。
z[-]
x[y+x-]
y[[-]
z+y]
必要な構造 :
0 0 x y
^
カーソルがxを指している状態のとき、論理演算x or yの結果が最も左のセルに格納されます。xとyの値は保持されます。
[<<->]<+[<]+>[-<->>+>[<-<<+>>]<[-<]]>
短縮版 :
[<<+>]>[<<[>]<[-]+>]<[>>]
| INPUT | OUTPUT | |||||
|---|---|---|---|---|---|---|
| x | y | x | y | z | temp0 | |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 0 | 1 | 0 | |
x´ = x nor y (真偽値、論理値)
帰属 : FSHelix
2xとyを消費し、両方とも1の時は0を、それ以外では1を出力します。なお、x = x or yで述べたようなオーバーフローの問題を回避するために、追加のセルzを用いています。
x[z+x[-]]
y[z+y[-]]
z[x+z[-]]
| INPUT | OUTPUT | |||
|---|---|---|---|---|
| x | y | x | y | |
| 0 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 0 | |
z = x xor y (真偽値、論理値)
帰属 : Yuval Meshorer
xとyを消費し、xとyが等しくない場合はzに1を、それ以外では0を格納します。ポインタはyで終了します。
z[-]
x[y-
x-]
y[z+
y[-]]
| INPUT | OUTPUT | ||||
|---|---|---|---|---|---|
| x | y | x | y | z | |
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 1 | |
| 1 | 0 | 0 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 0 | |
z = x xnor y (真偽値、論理値)
帰属 : FSHelix
xとyを消費し、xとyが等しい場合はzに1を、それ以外では0を格納します。ポインタはyで終了します。
z[-]+
x[
y-
x-
]
y[
z-
y[-]
]
| INPUT | OUTPUT | ||||
|---|---|---|---|---|---|
| x | y | x | y | z | |
| 0 | 0 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 0 | 1 | |
z = MUX(a, x, y) (真偽値、論理値)
帰属 : Yuval Meshorer
aが1の場合、zにyが格納されます。aが0の場合、zにxが格納されます。処理が完了した場合、a、x、yは初期値に関係なく0になります。例 : IN: = 0, y = 1, a = 1 OUT: x = 0, y = 0, a = 0, z = 1
z[-]
y[
a[z+a-]
y-]
x[
a-[
[-]z[-]+
a]
x-]
a[-]
| INPUT | OUTPUT | |||
|---|---|---|---|---|
| a | x | y | z | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 1 | |
while (x) { code }
帰属 : Sunjay Varma
whileループを実装するためには、ループの前とループ本体の最後に条件xを評価する必要があります。
evaluate x
x[
code
evaluate x again
x
]
帰属 : Morgan Barrett
もし条件式が十分に複雑であれば、次のように一度だけ評価するだけで済ませることができます。
temp0[-]+[
temp0-
evaluate x[
code
temp0+
†
]
temp0
]
† 値が0の任意の場所に移動します。
breakとcontinue
帰属 : Sunjay Varma
ループ内でbreak文とcontinue文を実装するには、以下の二つの疑似コードが機能的に同等であると考えてください。
while (foo) {
if (bar == foo) {
if (x > 2) {
break;
}
else {
// do staff
}
// do staff
}
// 次のイテレーションのためにfooを更新
}
// break文無しの同等の文
while (foo) {
shouldBreak = false
if (bar == foo) {
if (x > 2) {
shouldBreak = true
}
else {
// do staff
}
// break後はループ内のコードを評価しない
if (!shouldBreak) {
// do staff
}
}
if (shouldBreak) {
// ループの停止用
foo = 0
}
else {
// 次のイテレーションのためにfooを更新
}
}
break文とcontinue文を実装するためには、それらの概念を用いて、好きな組み合わせを作ることができます。brainfuckのコードにおいて、break文やcontinue文は「脱糖」する必要のある「糖衣構文」であると考えることができます。
do { code } while (x)
帰属 : None1
temp[-]+[
code
evaluate x
x
]temp-
このプログラムは一時的なセルを一つ使用し、初期化します。ポインタはxで停止し、1ループ毎に1回評価されます。
if (x) { code }
temp0[-]
temp1[-]
x[temp0+temp1+x-]temp0[x+temp0-]
temp1[
code
temp1[-]]
または
temp0[-]
x[
code
temp0
]x
または、もうxが必要ない場合は
x[
code
x[-]
]
if (x == 0) { code }
下のセクションのコード例はif (x) { code1 } else { code2 }において有用です。code1を空にしておくだけです。
帰属 : User:GolferHome
x
temp0[-]
temp1[-]
temp2[-]
temp2[temp1+temp2-]+
x[temp1-temp0+x-]
temp0[x+temp0-]
temp1[temp2-temp1[-]]
temp2[
code
temp2
[-]
]
注記 : これはJeffry Johnstonのx == yを用いています。
用いない場合、ただそのビットを複製、反転し、評価するだけです。
帰属 : User:Frog
temp0[-]
temp1[-]
x[temp0+temp1+x-]
temp1[-x+temp1]
temp0[temp1+temp0[-]]+
temp1[temp0-temp1-]
temp0[
code
temp0[-]
]
if (x) { code1 } else { code2 }
帰属 : Jeffry Johnston (39 OPs)
temp0[-]
temp1[-]
x[temp0+temp1+x-]temp0[x+temp0-]+
temp1[
code1
temp0-
temp1[-]]
temp0[
code2
temp0-]
帰属 : Daniel Marschall (33 OPs)
temp0[-]+
temp1[-]
x[
code1
temp0-
x[temp1+x-]
]
temp1[x+temp1-]
temp0[
code2
temp0-]
帰属 : Ben-Arba (25 OPs)
別のアプローチです。xをコピーする必要がないため効率的ですが、メモリ上でtemp0とtemp1がxの後に連続して配置される必要があります。
temp0[-]+
temp1[-]
x[
code1
x>-]>
[<
code2
x>->]<<
switch (x) { case 1: code1, case 2: code2 }
flag[-]+
x
[ case 1
------
[ case 2
-----
[default case]
flag
[case 1:
[-] empty the flag
code1
]
x
]
flag
[case 2:
[-] empty the flag
code2
]
x
]
動作原理としては、与えられたxからケースの値を減算し、flagを確認します。もしflagがまだあるなら、ケース内のコードを実行します。空の場合(最低一つのケース内コードが実行された場合)、何もしません。その後、xとflagを初期化します。
x = 疑似乱数
帰属 : Jeffry Johnston
このアルゴリズムには、次の形式の線形合同法を用います。
V = (A \times V + B) \bmod M
ここでは、
A = 31821, B = 13849, M = 周期 = 65536, V = 初期シード値
AとBの値は次の本から引用しました。
Texas Instruments TMS320 DSP DESIGNER'S NOTEBOOK Number 43 Random Number Generation on a TMS320C5x, by Eric Wilbur
8ビットセルを前提としています。コードの実行後、変数xには0～255の疑似乱数(前述のVの上位ビット)が格納されます。変数randomhとrandomlは内部乱数シードです。乱数生成中は変更しないでください。
temp0[-]
temp1[-]
temp2[-]
temp3[-]
temp4[-]
temp5[-]
randomh[temp0+randomh-]
randoml[temp1+randoml-]
temp3+++++++[temp2+++++++++++@temp3-]
temp2[
temp0[randomh+temp3+temp0-]
temp3[temp0+temp3-]
temp1[randomh+temp3+temp4+temp1-]
temp4[temp1+temp4-]
temp3[
randoml+[temp4+temp5+randoml-]
temp5[randoml+temp5-]+
temp4[temp5-temp4[-]]
temp5[randomh+temp5-]
temp3-]
temp2-]
++++++[temp3++++++++temp2-]
temp3-[
temp1[randomh+temp2+temp1-]
temp2[temp1+temp2-]
temp3-]
temp0[-]temp1[-]+++++[temp0+++++temp1-]
temp0[
randoml+[temp1+temp2+randoml-]
temp2[randoml+temp2-]+
temp1[temp2-temp1[-]]
temp2[randomh+temp2-]
temp0-]
++++++[randomh+++++++++temp0-]
randomh[x+temp0+randomh-]
temp0[randomh+temp0-]
帰属 : User:Cinnamony
,[>++<-]>++++<,>[<+>-]
このシンプルなスクリプトは二つの入力とxの次のセルを受け取り、それに基づいて疑似乱数を生成します。
- 入力を要求
- 2倍して
x+1に格納 -
x+1に4を加算 -
xに戻り、入力を要求 -
xとx+1を加算
アスキーコードの87と96を入力した場合、274となり、循環して19になります。
Divmod
除算と剰余を同時に計算する巧妙なアルゴリズムです。
# >n 0 d
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]
# >0 n d-n%d n%d n/d
nを保持する必要が無い場合、このバージョンを使用してください。
# >n d
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
# >0 d-n%d n%d n/d
このアルゴリズムは除数が0または1の場合、機能しません。
以下の画像は、このアルゴリズムの効率性を直感的に表しています。
 |
 |
帰属 : FSHelix
上記の修正版です。
# >n d
[->[->+>>]>[<<+>>[-<+>]>+>>]<<<<<]
>[>>>]>[[-<+>]>+>>]<<<<<
# >0 d-n%d n%d n/d
これはn >= 1の場合でも動作しますが、nを保持しません。n = 0～255、d = 1～255の場合について、極端なデータも含めて動作確認を行いました。
帰属 : FSHelix
nを保持しない別のバージョンです。計算に7セル以上を使用し、二層のIf-Else文が含まれています(将来的に最適化される可能性があります)。
ただし、このバージョンはn、d = 0～255の範囲を対処可能です。d = 0の場合、n / d = 0とn % d = nが返されることに注意してください。全ての入力に対して動作確認済みです。
# >n 1 d 1 0 0 0
>+>>+<<<
[
[
->->>>>>+<<<<-[>-]>[
>>+>[-<<<<+>>>>]<<
]<[-]+<<
]>>>[>]<<<[-]+<
]
# >0 1 d-n%d 1 0 n/d n%d
以下の画像は、このアルゴリズムの効率性を直感的に表しています。前述のアルゴリズムより明らかに早くなっています。バージョン2の最大演算回数は、このバージョンの2.30倍です。
 |
 |
修正版
# >n d 1 0 0 0
[->-[>+>>]>[[-<+>]+>+>>]<<<<<]
# >0 d-n%d n%d+1 n/d 0 0
全てのセル値で動作します。0除算はセル最大値+1との除算として扱われます。
剰余
商を計算する必要が無い場合、以下の方法はdivmodアルゴリズムよりも短くなります。
# 0 >n d 0 0 0
[>->+<[>]>[<+>-]<<[<]>-]
# 0 >0 d-n%d n%d 0 0
セルxの数値を数字として出力 (8ビット)
帰属 : itchyny、Stack Overflowより
x >>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-
<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++
<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<
x >>++++++++++<< // nを10にセット: 0' {x} 0 n '2
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<] // divmod; 結果を格納: 0' 0 n {0} n%d n/d '4
>>[-] 0 10 0 e0 e1&2
>>>++++++++++< // nを10にセット
[->-[>+>>]>[+[-<+>]>+>>]<<<<<] // divmod; 結果を格納: 3' e0 _ {0} e1 e2 '7
>[-]
>> // 全ての数字を分割: 0' x _ e0 _ _ e1 {e2} '7
[ // if e2 then:
>++++++[-<++++++++>] 48を加算 (アスキーコードで0)
<. e2を出力
<<+ _ {_} e1 に1を加算 (e2が0でなかったことを示すためのフラグ)
>+ e1に1を加算
>[-] e2を初期化
]
<
[ // if e1 || e2 then: (e2が処理された時にe1に1が加算されている)
<[->-<] フラグがセットされているならe1から1を減算
++++++[->++++++++<] 48を加算 (アスキーコードで0)
>. e1を出力
[-] e1を初期化
]
<<
++++++[-<++++++++>] // 48を加算 (アスキーコードで0)
<. // e0を出力 (常に出力)
[-] // e0を初期化
<<[-<+>] // xを'1から'0に移動
< // {x} (8セル使用)
1~nの合計
帰属 : Yuval Meshorer
n - 1をnの右隣にコピーし、n - 2をその右隣にコピーする、というのを0まで繰り返します。次に、1からnまでを合計します。nの右隣の、n + 3個のセルを使用します。
[>+<-]>
[[>+>+<<-]>>[-<<+>>]<-]<[[>[<+>-]]<<]
>[<+>-]
帰属 : User:A
1からyまでの合計(両端含む)をzに格納します。xは1である必要があります。
x[-]+y[x[-z+temp0+x]temp0[-x+temp0]x+y-]
セルxの数値を数字として出力 (任意のビット 例：8ビット、100000ビット、etc)
更新された除算ルーチンを使用した改良版です。使用するセルは全て実行前後で初期化されます。このコードは以前よりも少し高速化されており、非常に大きな値で動作確認済みです。しかし、BFの命令数が出力される数値に比例して肥大するため、20億を超える数値に関しては、[->-[>+>>]>[[-<+>]+>+>>]<<<<<]をdivmodとして認識できるインタプリタが必要になります(前提条件が満たされていることを確認してください)。
// 数値の出力
// 使用セル: V Z n d 1 0 0 0
// Vは印刷する値であり、変更されません
// Zは値が0の一時的な番兵値です
// Zより右の全てのセルはこのルーチンによって初期化されます
>[-]>[-]+>[-]+< // ループ開始のためにnとdに1を格納
[ // 'n'からループ開始
>[-<- // 最初のループで
<<[->+>+<<] // VをN(とZ)にコピー
>[-<+>]>> // ZからVを復元
]
++++++++++>[-]+>[-]>[-]>[-]<<<<< // 10で除算するための初期化
[->-[>+>>]>[[-<+>]+>+>>]<<<<<] // 除算の実行
>>-[-<<+>>] // 余りをnに格納
<[-]++++++++[-<++++++>] // アスキーコードに変換後、dを初期化
>>[-<<+>>] // 商をdに移動
<< // セルの入れ替え。新しいnは元のdの位置になり、
// 古いnは出力用の数値になる
] // nが0の場合にループ終了
<[.[-]<] // Zの位置まで移動し、
// Zが見つかるまで数値を出力
< // Vに戻る
この代替案は、BFの命令数が4分の1少なく、かつ短いです。しかし、通常、最適化を行うインタプリタではほぼ同じ速度で実行されます。これは、初期化済みのセルが先ほどの三倍要求されます。そのうち二つは出力対象のセルの左に位置しています。出力される値を含む全てのセルは実行後に初期化されます。
>> x
>+
[[-]<
[->+<
[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<
[->[-]>>+>+<<<]
]]]]]]]]<
]>>[>]++++++[-<++++++++>]>>
]<<<[.[-]<<<]
少数の入力
帰属 : Urban Müller (1993)
値は現在のセルに格納され、さらに三つの右のセルが使用されます。数値の終端は改行またはeofです。数字以外の文字も全て数字と同じように扱われます。多倍長のセルでも問題なく動作します。
[-]>[-]+ // 合計値を初期化
[[-] // 最初の一時的セルでループを開始
>[-], // eofまたは入力の終了を検知するために入力バッファを初期化
[
+[ // eofで-1であることをチェック
-----------[ // 改行をチェック
>[-]++++++[<------>-] // 38を減算し、0-9の数値を得る
<--<<[->>++++++++++<<] // 既存の値を10倍する
>>[-<<+>>] // 新たなcharの追加
<+>]
]
]
<]
<
// 現在のセルは入力された場所
帰属 : User:tommyaweosme
,>++++++++[<------>-]<
48を減算し、入力を一桁の数値に変換します。
帰属 : User:tommyaweosme
,>++++++++[<------>-],>++++++++[<------>-],>++++++++[<------>-]<<[>>++++++++++<<-]<[>>>>++++++++++<<<<-]>>>>[>++++++++++<-]>[<<+>>-]<<<[>+<-]>[<<<+>>>-]
入力を三桁の数値に変換します。
yから無限までxずつカウントアップ
x[[-y+temp+x]temp[-y+x+temp]x]
while (c = getchar() != X)
getchar-untilの停止条件となる文字を表すためにXを使用します。TIO3においてはオーバーフロー、アンダーフローが必要です。t1に結果(等しい場合は0、等しくない場合は1)を格納します。xとyを保持します。
yXx+[,[-t1+t3+x]y[-t2+t4+y]t1[-x+t1]t2[-y+t2]t3[-t4+t3]t4[++t3]t4[-t1+t4]t1]
x == 0
(修正が必要？)このコードはX == 0を判定します。三つのセルを使用します。一つ目のセルは判定対象の数値、二つ目のセルは一時的に使用、三つ目のセルはフラグです。ポインタはxからスタートします。
>[-]>[-]+<<[[->+<]>>-<<]>[-<+>]>
関連項目
- Brainfuck
- Brainfuck constants
- Brainfuck bitwidth conversions
- BrainClub (スタックベースのプログラミングに使用できるアルゴリズムが含まれています。Forthの知識があるならば理解できるかもしれません)
- FBP これらのアルゴリズムを用いたC++での実装です
- BFFuck これらのアルゴリズムを用いたBrainfuckへコンパイルされる高水準言語です(コンパイラはPython)
- Brainfuck Enterprise Solutions' str.bf (文字列操作アルゴリズム集です)