AtCoder Brainfuck Contest 参加記
概要
有志の方がAtCoderのバーチャルコントテストで brainfuck
向けの問題でバチャコンを開いてくれたのでそれに参加しました。
全部まとめて提出用としたところ、ペナを出しました。恥ずかしいです。
というわけで、問題の解説を行っていきたいと思います。
コンテストリンク
目次
- 概要
- 目次
- A. 1問目
- B. ABCxxx
- C.Diagonal String
- D.12/22
- E.お茶
- F.
- G. September 9
- H.Restricted
- I.Ringo's Favorite Numbers
- J.Welcome to AtCoder
- 総評
- あとがき
A. 1問目
問題概要
入力文字列の 1
文字目を出力するだけです。
コード
.,
解説
言語仕様を理解していれば解くことができます。
B. ABCxxx
問題概要
ABC
を出力して、そのあとにエコープログラムを
書くだけです。
コード
++++++++[->++++++++<]>+.+.+. ,----------[++++++++++.,----------]
解説
A
の文字コードは 65
なので、8*8+1
で数値を生成できます。そのあとは、インクリメントしながら出力すれば、ABC
と出力することができます。
エコープログラムは、改行コード (=10)
まで読み込んで出力すればいいです。
C.Diagonal String
問題概要
対角線上の文字を順に出力するだけです。
コード
,.,,,,,.,,,,,.
解説
1
文字目、6
文字目、11
文字目を順に出力すればいいです。(改行も文字に含まれることに注意してください。)
,
は現在の値を上書きするので、値の初期化の必要はありません。
D.12/22
問題概要
4
桁の数字の 2
の数を数える問題です。
コード
,---------- [ >+++++[-<-------->]< >>+<< [ [-] >>-<< ] ,---------- ] >++++++[->++++++++<]>.
解説
読み込みを 4
回してもいいのですが、ループで回すとコード量を削減できます。2
の数を数えるだけです。
2
以外を数えて 4
から引くのでも構いません。
E.お茶
問題概要
文字列の最後が T
かどうかを判断するだけです。
コード
,---------- [ > ,---------- ] ++++++++[-<--------->]< -- >+< [ [-]>[-]< No ++++++++++[->+++++++++++>++++++++<<]>>--.[-]<+.[-]< ] > [ [-] Yes ++++++++++[->+++++++++<]>-.++++++++++++.++++++++++++++.[-]< ]
解説
改行コードが来るまで、現在の値をどこかのメモリに格納ということもしてもいいですが、すべての値をメモリに順に入れて、最後の要素を確認する方が楽です。(入力文字列はメモリに充分乗るので。
あとは、T
かどうかの判断を行い if-else
を書けば良いです。
F.
問題概要
入力文字列が並び替えると abc
になるかどうかを判断します。
コード
,---------- [ >++++++++++[-<--------->]<+++ >+< [-[-[- ]>[- >>>+<<<]< ]>[- >>+<<]< ]>[- >+<]< ,---------- ] >> [[-]<+>]> [[-]<+>]> [[-]<+>]> <<[-<+>]<[-<+>] +< --- [ [-]>[-]< Yes ++++++++++[->+++++++++++>++++++++<<]>>--.[-]<+.[-]< ] > [ [-] No ++++++++++[->+++++++++<]>-.++++++++++++.++++++++++++++.[-]< ]
解説
入力は例によってループで処理してます。
3
つの入力が異なるかどうかの判別によって解く方法と
a,b,c
がそれぞれ存在するかを確認する方法があります。
上記コードは後者の解放になってます。
めんどくさいので解説はしません
G. September 9
問題概要
二桁の数字に 9
が含まれるかどうかを判別するだけです。
コード
, +++>++++++[-<---------->]< >+< [ >-< , +++>++++++[-<---------->]< >+< [ [-]>-< ++++++++++[->+++++++++++>++++++++<<]>>--.<+.[>]> ] ] > [ > ++++++++++[->+++++++++<]>-.++++++++++++.++++++++++++++.[>] ]
解説
今回は入力が 2
文字なので、if-else
を 2
回書けばいいです。
上記コードでは、Yes
の出力はひとつのコードで行えるように工夫をしています。
H.Restricted
問題概要
A+B
を出力するだけです。ただし、10
を超える場合はerror
を出力します。
コード
>>,<,> [--<---<--->>] <[-<+>]< [->+>>+<<<] >>> >+++++++++< [[->]<[<]>]<< //比較 [ > ++++++++++[->++++++++++<]>+.+++++++++++++..---.+++.[>]>>>> ] << [>++++++[-<++++++++>]<.>] ,.
解説
文字コードを数字に変換する際に、空白を利用することでコード長を削減しています。
比較は、[[->]<[<]>]<<
で行っています。
これの解説をすると長くなるので、そういうものだと思ってください。
比較ができたら、あとは if-else
を書くだけです。
I.Ringo's Favorite Numbers
問題概要
概要は問題を見てください。一言で説明するのは面倒ですので。
コード
>,+>>,[--<+++<--->>]> ,----------[++++++++++>,----------] <<<[>>+<<<] 100 の場合は1の位をインクリメント >>>[<]>[.>] 数値の出力 <[<]<<[<] 位置修正 >-[->..<] 0 を出力
解説
数字は改行まで読み込んで、'3' 桁あれば、 1
の位をインクリメントすればいいです。 100
の時のみなので、繰り上がりは考慮しなくていいです。
ただし、入力長に応じて、位置が変わるのでそれを修正するコードが必要になります。
J.Welcome to AtCoder
問題概要
3
つの数の和を出力しエコープログラムを書けば良いです。
256
を超えるので brainfuck
には難しいです。
コード
>>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< #endregion > >>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< #endregion #region Multi_AddToPrev 0 //start ___{ a }___{ b*}___ //resilt ___{res}___{ b*}___ [ [<]<[<]<<[->>+<<]>>[>]>[>]>+<<- [ [<]<[<]>+[>]>[>] >+<<- ] < ] <[<]<<[<]> [[-<+>]>]>>[[-<<<+>>>]>]<<<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ [->+<]>----------< <[+>]>[<] ]]]]]]]]]]]< ] >>[>]>>>>>[[-<<+>>]>]<<< #endregion [[-]<]> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< #endregion #region Multi_AddToPrev 0 //start ___{ a }___{ b*}___ //resilt ___{res}___{ b*}___ [ [<]<[<]<<[->>+<<]>>[>]>[>]>+<<- [ [<]<[<]>+[>]>[>] >+<<- ] < ] <[<]<<[<]> [[-<+>]>]>>[[-<<<+>>>]>]<<<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ [->+<]>----------< <[+>]>[<] ]]]]]]]]]]]< ] >>[>]>>>>>[[-<<+>>]>]<<< #endregion [<]<<< #region Multi_WriteNum +[<]>[-[+[>]]<+>>] ++++++[-<-------->]<+<--> [[<]>[+>]<]<[<]>[.>] >++++++[-<++++++++>]<- [[<]>[->]<]<[<]<[[->+<]<]>>[>]< //数値復帰部 #endregion [-]>[-]< ++++++++++[->+++<]>++.[>] ,+[-.,+]
解説
マルチバイト変数を利用しているので、解説は省略します。
総評
全体的に brainfuck
向けの良い問題ばかりが集められていると思います。
あとがき
コンテスト中に記事を書いたのでだいぶ雑です。すみません。
皆さん、これを期に、ぜひ brianfuck
を初めて見てはどうでしょうか。
brainfuck 閑話:マルチバイト変数 設計編
概要
今回はマルチバイト変数(多バイト長整数)について書いていきます。
簡単に言うと、256
の数値を扱う方法です。
本当はもっと後に書く予定でしたが、知りたいという方がいたので前倒しで書きました。
今は閑話としてカテゴライズして、後でもう一度まとめようと思います。
目次
マルチバイト変数の概要
brainfuck
ではマルチバイト変数は自分で作るしかありません。
しかし、これといったセオリーがあるものではなく、
- 命令の実行時間はどうか
- 命令のコード長はどうか
- 自身が扱いやすいかどうか
なとどいった重要要素が多くあるので、これといったセオリーがあるわけではありません。
なので、今回は私が作成したマルチバイト変数を紹介しつつ、設計方法の説明をしていきたいと思います。
もちろん、私が紹介したコードをそのまま使用してもらっても構いませんし、
私のコードを改変して使用してもらっても構いません。
データ格納方法の検討
マルチバイト変数と一括りに行ってしまっても、その設計方法は様々です。設計の上で検討するべき項目を以下に示します。
- 何進数を採用するか
- 固定長か可変長か
1
桁に対して何byte
を割り当てるか- 各変数の前後に何
byte
の余裕を持たせるか - 負数をどうするか
それぞれ詳しい説明をしていきます。
何進数を採用するか
数字がいくつになった場合に桁上がりが発生するか、です。
進数が小さければ小さいほど、使用メモリが多くなり、大きれば大きいほど、様々な演算処理が重くなる印象です。
以下は実装を検討しても良いであろう進数を書きます。
1
進数8
進数10
進数16
進数256
進数
1
進数は桁上がりなどは簡単ですが、メモリ量が膨大なためおすすめはしません。
256
進数はメモリ的には最良ですが、桁上がりなどがめんどくさそうなのと、計算の実行速度が遅くなりそうです。
8
進数、16
進数は bit
演算と相性が良さそうですが、入出力がめんどくさいという欠点があります。
10
進数は、bit
演算と相性が悪いという欠点がありますが、入出力が簡単です。
以上より、私は 10
進数を採用しています。
余裕がああれば、10
進数と、8
または 16
真数の両方作ってもいいかもしれませんね。
固定長か可変長か
固定長は計算が楽になり、可変長はメモリ使用量が少なくなります。
私は、固定長で実装しています。
1
桁に対して何 byte
を割り当てるか
1
桁に対して複数 byte
を用意するのは不思議かもしれませんが、理由はあります。
まずは、そのメモリが、桁として有効かどうかを示す必要があることです。
具体的には、0
が格納されているメモリが、「変数の末端(変数の領域外)なのか、0
という数値が格納されているのか」
という問題を解決するために、桁に使用されているメモリであることを明示する必要があります。
桁数をハードコーディングしてもいいですが、桁数ごとに加算などの桁数を変更しないといけないという欠点があります。
また各桁に対して空きメモリを用意することで、各桁に対する演算を行うためのワーキングメモリとして役立つことも多いです。
基本的には 3 byte
用意すれば十分なように思います。
ここまでの話を否定するようですが、私は 1
桁 1 byte
を採用しています。
上記の問題の具体的な解決方法は後述します。
各変数の前後に何 byte
の余裕を持たせるか
変数間の空きは変数の端を検出するだけでなく、二項演算の処理のワーキングメモリにすることもできます。
変数の端を検出するためには、1
桁当たりの byte
数以上の空きを用意する必要があります。
私は、3 byte
を採用しています。
負数をどうするか
負数をどうするかもいくつか方法があります。
- 補数表現
- 絶対値表現
- 実装しない
補数表現はそのままで、実質符号なし整数と同じようにアンダーフローを実装して、一定以上なら負数とみなす方法です。
絶対値表現は、符号と絶対値による表現です。
実装しないは、動作未定義もしくは、負数は全て 0
にする方法です。
実際は、未定義にするのが楽ですが、汎用性を考えると実装したいです。
絶対値表現もいいのですが、条件分岐がめんどくさくなるため、
私は補数表現を採用しました。
また、補数表現も、1
の補数と 2
の歩数がありますが、2
の補数を採用しています。
ちなみに、簡単のため、最上位が 0
なら正それ以外なら負として扱っています。
負数の方が数字を多く表現できることになりますが、基本的に数桁余裕を持ってコードを書くため、0
か 9
以外を取らないことになります。
設計方針のまとめ
10
進数- 可変長
1
桁に対して1 byte
を割り当て- 各変数の前後に
3 byte
の余裕 - 負数を補数表現で実装
1
桁 1 byte
の実現方法
先ほど説明したとおり、「変数の末端(変数の領域外)なのか、0
という数値が格納されているのか」を判別する必要があります。それを 1 byte
で表現するために、 各桁の値に 1
足した値を採用しています。
例えば、固定長 6
桁で 129
を表現する場合
{0} {0} {0} {1} {1} {1} {2} {3} {10} {0} {0} {0}
となります。
まぁ、今では 2 byte
用意しても良かったのとは思っています。
実装する演算
マルチバイト変数の設計方針がある程度固まったらあとは様々な演算等を実装していくだけです。
個人的に思う優先度ごとにわけて記述します。
必要演算
ほぼ必須となる演算や処理です。 * 入力 * 出力 * インクリメント * デクリメント
高優先度演算
必須演算で代用することもできますが、計算量の関係で実装しておいたほうがいい演算が主です。
- 加算
- 減算
- 比較
- 非零判定
- 正負判定
あると嬉しい演算
高優先度演算で実装できるが実装しておいたほうが計算量が削減できるものと、時々必要になる演算が主です。
- 比較
- スワップ
- 絶対値
- 符号反転
- シングルバイト変数との積算
- シングルバイト変数での剰余算
無くても良い
必要になる機会はありますが、実装がめんどくさい演算です。
- マルチバイト変数同士の積算
- マルチバイト変数同士の剰余算
次
実際の実装は別記事にまとめようと思います。
brainfuck
記事一覧
brainfuck 入門:リンクまとめ - 三流プログラマの戯言
brainfuck 入門:文字列の受け取り
概要
今回は文字の入力に関して説明します。数値の入力ではないです。ごめんなさい。
目次
文字列読み込み
1
行読み込み
brainfuck
では 1
行読み取るという高度なことはできないので、改行文字まで読み取るということをします。ここで改行コードは \n (=10)
とします。
,---------- [ ++++++++++ code ,---------- ]
読み取った値から 10
引いて 0
であれば処理を抜けるというコードになります。
3行目で 10
を足していますが、これは元の文字コードに戻す処理なので、文字数を数える場合などでは不必要となります。
また、メモリに展開したい場合は、
,---------- [ ++++++++++ > ,---------- ]
と書くことができます。
スペースまでの読み取り
時々、スペースまでを読み取りたい時があります。そういった場合には、 1
行読み取りの\n
の代わりに空白 (=32)
で判断することができます。
,>++++[-<-------->] [ ,>++++[-<++++++++>] code ,>++++[-<-------->] ]
インクリメント、デクリメントを 32
回行う代わりに、ループで処理しています。
改行またはスペースまでの読み取り
改行とスペースの両方の区切り文字で読み取りを終了を行いたい場合、一方のみの時と比べてめんどくさいコードになります。
>+ [ -< ,----- ----- [ >++++[-<----->]<-- [ >++++[-<++++++++>]< code [-]>[-]+< ] ]> ]<
読み取りを行うメモリの右側を区切り文字以外が入力されたかどうかをフラグ管理しています。
問題例
- ABC 072 B - OddString
AtCoder
でbrainfuck
やってる人には有名な問題です。AtCoder
での色々な裁定を知っていれば、9 byte
で解くことができます。
しかし、ここまでの知識を駆使すれば裁定を知らなくても解くことができます。
ただし、AtCoder
では10000
文字をメモリに展開できないので気を付けてください。
次回
次回こそは、大小比較書きたいですね。
記事一覧
brainfuck 入門:リンクまとめ - 三流プログラマの戯言
brainfuck 入門:if 文と bool 演算
概要
今回は、if
文とそれに伴う bool
演算について解説します。等価、不等価も説明しますが、大小比較に関しては別記事で書こうと思っています。
目次
if
文
if
文
brainfuck
は条件により分岐するのはループ文しかありません。そこで、ループ分を利用して if
文を構築します。ただし、 0
を false
それ以外を true
とします。
[[-] code ]
ループ内でデクリメントを行う代わりに、初期化を行うとで ループ回数を1
回にすることができます。
if-else
文
else
句を付ける場合はフラグを用いる必要があります。
>+<[[-]>-< if ]>[- else ]<
else
句では初期化ではなくデクリメントしてますが、フラグは 0
か 1
しかとらないので、問題ないです。(もちろん初期化をしても問題ないです。)フラグ管理は Not
の項目を見てください。
bool
演算
bool
代数として、 0
を false
、それ以外を true
とします。
ただし、brainfuck
では true,false
を使用できるわけではないので、false
を 0
、 true
を 1
として表現することが多いです。この記事ではそのように表現することとします
bool
化 ((bool)value)
0
を 0
、 それ以外を 1
に変換するコードです。if
文で実現できます。
[[-]>+<]
変換結果は次のメモリに格納されます。
真理値反転 (!value)
Not
は if
を利用して実装を行います。
具体的には、あらかじめフラグを立てておいて、if
句でフラグを下げることで、そのフラグ値が Not
の結果となります。
>+<[[-]>-<]
演算の結果はひとつ右のメモリに格納されます。
不等価演算 (!=)
c++
における !=
演算です。 以下の例では、0
番地と 1
番地の値を比較しています。
[->-<]>[[-]<+>]<
また別の機会に説明しようと思いますが [->-<]
は引き算を行います。
ただし、0
に対するデクリメントが 255
になる環境でのみ使用できます。0
に対するデクリメントが許可されない環境での不等価はまた別の機会に説明したいと思います。
等価演算 (==)
c++
における ==
演算です。 以下の例では、0
番地と 1
番地の値を比較しています。不等価演算と Not
の組み合わせで実現できます。
[->-<]+>[[-]<->]<
不等価演算と同様に 0
に対するデクリメントが 255
となる環境でのみ使用できます。
if
文と bool
演算の組み合わせ
bool
演算の項目で、0,1
に変換する構文を書いてきましたが、実際には 0,1
に変換することなく if
文につなげることも多いです。
例えば不等価の時に処理したいときは、
[->-<]>[[-] code ]<
というように書くことができます。
ただし、等価時に指定のコードを実行したい場合は、
[->-<]+>[[-]<->]<[- code ]
という風に Not
をとる必要がどうしても出てきます。
臨機応変に対応しましょう。
固定値との比較
比較対象が固定値であり、ハードコーディングできる場合は、直接数値を引くことができます。
例えば、20
かどうかの判別は
>++++[-<----->]<[[-]>+<]
と書くことができます。(この例では結果は次のメモリに格納されます。)
問題例
- ABC 070 A - Palindromic Number
等価比較を行うことでACすることが可能です。
次回
次回は、大小比較書きたいですね。
記事一覧
brainfuck 入門:リンクまとめ - 三流プログラマの戯言
brainfuck 入門:値の移動とコピーと初期化と準非破壊ループ
概要
brainfuck
を書く上で基本となる、値の移動、値のコピー、値の初期化および、準非破壊な繰り返し文の説明をします。
目次
構文解説
値の移動
brainfuck
では、どのメモリに値があるかが重要になることが多々あります。そのため、望む位置に値を移動させることが重要となってきます。
値の移動は以下のコードで実現できます。
[->+<]
上記コードは一つ右に移動させます。ただし、移動先の初期値が 0
である必要があります。
また、>
と <
を適切に変更することで任意の位置に値を移動させることができます。ただし、ループの開始と終了でポインタの位置が変化しないように気を付ける必要があります。
値のコピー
brainfuck
では基本的に破壊的命令が多いです。そのため、一つの数値を使いまわすためには値をコピーすることが必要となります。値のコピーは以下のコードで実現できます。
[->+>+<<]
上記コードは値を次とその次のメモリに複製します。値の移動と同様に複製先の初期値が 0
である必要があることに気を付けてください。
また、最初に値があったポインタは 0
になることに気を付けてください。
最初の位置に値を復元したい場合は、値のコピーの後、値の移動を行う必要があります。
[->+>+<<]>>[-<<+>>]<<
これは、次のメモリに値をコピーするコードです。
値の初期化
値の移動やコピーで述べた通り、brainfuck
の構文はいくつかのメモリが 0
となっている必要があることがあります。もちろん、メモリは 0
初期化されていますが、いくつかのコードの実行後に 0
であることが保証されないことも少なくありません。そこで、メモリの初期化をする必要が出てきます。以下のコードで実現できます。
[-]
メモリの値が 0
になるまで、デクリメントするだけです。
準非破壊ループ
完全に非破壊なループを組むことはできませんが、あらかじめ値のコピーを行うことでループ回数を保持したままループを行うことができます
[->+>+<<]>>[-<<+>>]<< >[- code]
ただし、値のコピーをループ文を一つにまとめることができます。
[->+ code <]>[-<+>]<
このコードを見てもらうとわかりますが、値の複製も、順非破壊ループを使用しているとも言えます。
問題例
今回の説明は基本的なため、特に問題例はありません。
次回
次回は、bool
演算と if
文を書きたいですね。
記事一覧
brainfuck 入門:ループ文と定数生成と文字出力
今回の主軸
今回は、文字出力の行い方を解説します。 プログラミング的には後でもいいんですけど、AtCoderをやるうえでは、かなり重要となるので、初めに説明しておきます。 また文字出力に必要となるループ文と定数生成の説明をしたいと思います。
目次
ループ (繰り返し)文
いきなりループかと思われるかもしれませんが、brainfuck
ではこれが最も基本的な構文となります。
掛け算や割り算、果ては加算減算ですら、ループ文が使用されます。
[- code ]
現在の値の回数だけ code
を実行します。-
はcode
の前でも後でも問題ないです。場合によって使い分けでください。
ただし、終了時に、繰り返し回数を格納していたメモリは 0
となります。
また、 code
の開始時と終了時にポインタの位置が同じである必要があります。
定数の生成
brainfuck
では定数の生成を行う場合は、値を定数回インクリメントします。以下は10
を生成するコードです
++++++++++
ただし、この方法で100
といった大きい数字を生成しようとした場合は多くの+
を書かないといけないことになります。
そこでそれを回避するために、ループ文を使用して生成します。
以下は100
を生成するコードです。
++++++++++[->++++++++++<]>
ただし、この方法で100
といった大きい数字を生成しようとした場合は多くの+
を書かないといけないことになります。
そこでそれを回避するために、ループ文を使用して生成します。
以下は100
を生成するコードです。
++++++++++[->++++++++++<]>
定数の変更
定数の生成を行うときに、すでにある定数を変更することによって新たな定数とすることができます。以下は、
まず、41
を生成して、その後80
にして、そのあと57
にするというプログラムです。
+++++[->++++++++<]>+ 41を生成 <+++++[->++++++++<]>- 80に変更 (40を足して1を引く) <+++++[->------<]>--- 57に変更 (20を引いて3を引く)
文字出力
一文字の出力
brainfuck
では文字は文字コードを生成して出力を行います。 例えば H
という文字を出力しようとした場合、H
の文字コードは 72 (=8x9)
なので、
++++++++[->+++++++++<]>.
とすることで H
を出力することができます。
複数文字の出力
複数の文字を出力する場合は毎回文字コードを生成するのは面倒なので、前回の値に増減させて表示を行うことがあります。
以下は Hello
を出力するプログラムです。 Hello
文字コードは順に、72,101,108,108, 111
です。
++++++++[->+++++++++<]>. <+++++[->++++++<]>-. +++++++.. +++.
ちなみに、言語仕様編 に記載されている Hello World.
は少し違った方法で実現しています。
問題例
- いろはちゃんコンテスト Day3 J - Go to Heaven
文字列を出力するだけでACが取れる問題もあります。
次回
次回は今度こそ基本構文の話しようと思います。