三流プログラマの戯言

プログラミング初心者が気になったことを書き綴るだけ。主にc#

AtCoder Brainfuck Contest 参加記

概要

有志の方がAtCoderのバーチャルコントテストで brainfuck 向けの問題でバチャコンを開いてくれたのでそれに参加しました。 全部まとめて提出用としたところ、ペナを出しました。恥ずかしいです。
というわけで、問題の解説を行っていきたいと思います。
コンテストリンク


目次


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-else2 回書けばいいです。
上記コードでは、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 用意すれば十分なように思います。
ここまでの話を否定するようですが、私は 11 byte を採用しています。
上記の問題の具体的な解決方法は後述します。

各変数の前後に何 byte の余裕を持たせるか

変数間の空きは変数の端を検出するだけでなく、二項演算の処理のワーキングメモリにすることもできます。
変数の端を検出するためには、1 桁当たりの byte 数以上の空きを用意する必要があります。
私は、3 byte を採用しています。

負数をどうするか

負数をどうするかもいくつか方法があります。

  • 補数表現
  • 絶対値表現
  • 実装しない

補数表現はそのままで、実質符号なし整数と同じようにアンダーフローを実装して、一定以上なら負数とみなす方法です。
絶対値表現は、符号と絶対値による表現です。
実装しないは、動作未定義もしくは、負数は全て 0 にする方法です。
実際は、未定義にするのが楽ですが、汎用性を考えると実装したいです。
絶対値表現もいいのですが、条件分岐がめんどくさくなるため、 私は補数表現を採用しました。
また、補数表現も、1 の補数と 2 の歩数がありますが、2 の補数を採用しています。
ちなみに、簡単のため、最上位が 0 なら正それ以外なら負として扱っています。
負数の方が数字を多く表現できることになりますが、基本的に数桁余裕を持ってコードを書くため、09 以外を取らないことになります。

設計方針のまとめ

  • 10 進数
  • 可変長
  • 1 桁に対して 1 byte を割り当て
  • 各変数の前後に3 byte の余裕
  • 負数を補数表現で実装

11 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
    AtCoderbrainfuck やってる人には有名な問題です。AtCoder での色々な裁定を知っていれば、9 byte で解くことができます。
    しかし、ここまでの知識を駆使すれば裁定を知らなくても解くことができます。
    ただし、AtCoder では 10000 文字をメモリに展開できないので気を付けてください。


次回

次回こそは、大小比較書きたいですね。


記事一覧

brainfuck 入門:リンクまとめ - 三流プログラマの戯言


brainfuck 入門:if 文と bool 演算

概要

今回は、if 文とそれに伴う bool 演算について解説します。等価、不等価も説明しますが、大小比較に関しては別記事で書こうと思っています。


目次


if

if

brainfuck は条件により分岐するのはループ文しかありません。そこで、ループ分を利用して if 文を構築します。ただし、 0false それ以外を true とします。

[[-] code ]

ループ内でデクリメントを行う代わりに、初期化を行うとで ループ回数を1 回にすることができます。

if-else

else 句を付ける場合はフラグを用いる必要があります。

>+<[[-]>-< if ]>[- else ]<

else 句では初期化ではなくデクリメントしてますが、フラグは 01 しかとらないので、問題ないです。(もちろん初期化をしても問題ないです。)フラグ管理は Not の項目を見てください。


bool 演算

bool 代数として、 0false 、それ以外を true とします。 ただし、brainfuck では true,false を使用できるわけではないので、false0true1 として表現することが多いです。この記事ではそのように表現することとします

bool 化 ((bool)value)

00 、 それ以外を 1 に変換するコードです。if 文で実現できます。

[[-]>+<]

変換結果は次のメモリに格納されます。

真理値反転 (!value)

Notif を利用して実装を行います。 具体的には、あらかじめフラグを立てておいて、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 かどうかの判別は

>++++[-<----->]<[[-]>+<]

と書くことができます。(この例では結果は次のメモリに格納されます。)


問題例


次回

次回は、大小比較書きたいですね。


記事一覧

brainfuck 入門:リンクまとめ - 三流プログラマの戯言


brainfuck 入門:値の移動とコピーと初期化と準非破壊ループ

概要

brainfuck を書く上で基本となる、値の移動、値のコピー、値の初期化および、準非破壊な繰り返し文の説明をします。

目次

構文解説

値の移動

brainfuck では、どのメモリに値があるかが重要になることが多々あります。そのため、望む位置に値を移動させることが重要となってきます。 値の移動は以下のコードで実現できます。

[->+<]

上記コードは一つ右に移動させます。ただし、移動先の初期値が 0 である必要があります。
また、>< を適切に変更することで任意の位置に値を移動させることができます。ただし、ループの開始と終了でポインタの位置が変化しないように気を付ける必要があります。

値のコピー

brainfuck では基本的に破壊的命令が多いです。そのため、一つの数値を使いまわすためには値をコピーすることが必要となります。値のコピーは以下のコードで実現できます。

[->+>+<<]

上記コードは値を次とその次のメモリに複製します。値の移動と同様に複製先の初期値が 0 である必要があることに気を付けてください。
また、最初に値があったポインタは 0 になることに気を付けてください。
最初の位置に値を復元したい場合は、値のコピーの後、値の移動を行う必要があります。

[->+>+<<]>>[-<<+>>]<<

これは、次のメモリに値をコピーするコードです。

値の初期化

値の移動やコピーで述べた通り、brainfuck の構文はいくつかのメモリが 0 となっている必要があることがあります。もちろん、メモリは 0 初期化されていますが、いくつかのコードの実行後に 0 であることが保証されないことも少なくありません。そこで、メモリの初期化をする必要が出てきます。以下のコードで実現できます。

[-]

メモリの値が 0 になるまで、デクリメントするだけです。

準非破壊ループ

完全に非破壊なループを組むことはできませんが、あらかじめ値のコピーを行うことでループ回数を保持したままループを行うことができます

[->+>+<<]>>[-<<+>>]<< >[- code]

ただし、値のコピーをループ文を一つにまとめることができます。

[->+ code <]>[-<+>]<

このコードを見てもらうとわかりますが、値の複製も、順非破壊ループを使用しているとも言えます。

問題例

今回の説明は基本的なため、特に問題例はありません。

次回

次回は、bool 演算と if 文を書きたいですね。

記事一覧

brainfuck 入門:リンクまとめ - 三流プログラマの戯言

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.は少し違った方法で実現しています。

問題例

次回

次回は今度こそ基本構文の話しようと思います。

記事一覧

brainfuck 入門:リンクまとめ - 三流プログラマの戯言

brainfuck 入門:リンクまとめ

はじめに

この記事はあくまで brainfuck 入門であり、プログラミング入門ではありません。 今回は言語仕様編ということで、brainfuck の言語仕様および、解説で使用する環境の話をします。 すでに AtCoderbrainfcuk を書いてるような人は見なくてもいいような内容です。

この記事のシリーズの目的

AtCoderbrainfuck を使えることを受けて、brainfuckを書いてみたいけどわからない。という人向けに構文を紹介していきたいと思います。ついでにその記事の内容を利用して解ける問題を紹介していきたい思います。

記事一覧

入門編

閑話