brainfuck 入門：言語仕様編
今回の主軸
今回は、 brainfuck の言語仕様と環境依存の挙動について解説します。
目次
brainfuck とは
Hello World.
言葉で説明するよりも、コードを見てもらったほうが早いのではないかと思います。
下に示すのはプログラミングでよく最初に書かれる Hello World. と出力するプログラムです。
++++++++++[->++++++++++>+++>++++++++++++>+++++>+++++++<<<<<] >>>>>++.<<<<+.+++++++..+++.>++.>-.<<.+++.------.--------.>>>----.
概要
brainfuck はプログラミング言語の一つで、コンパイラおよびインタプリタのサイズが小さくなるように設計されています。
よく勘違いされますが、人がプログラミングしにくいように作られた言語ではありません。
また、fuck という単語は良くないということで、
brainf*ck や brainfxxk などといった表記がされることがあります。この記事では特別な場合を除き brainfuck で統一しています。
予約語
brainfuck には以下の8個の予約語のみが与えられ、それ以外の文字はすべてコメントとして扱われます。
+-><[],.
また、それぞれの命令の内容は以下の通りとなっています。
| 予約語 | 命令内容 | Cの相当コード |
|---|---|---|
+ |
現在の値をインクリメント | *ptr++; |
- |
現在の値をデクリメント | *ptr--; |
> |
ポインタをインクリメント | ptr++; |
< |
ポインタをインクリメント | ptr--; |
[ |
現在の値が 0 なら対応する ] に移動 |
while(*ptr){ |
] |
現在の値が 1 なら対応する [ に移動 |
} |
, |
入力を1文字受け取り現在の値をその文字コードにする | *ptr = getchar(); |
. |
現在の値を文字コードとする文字を出力する | putchar(*ptr); |
メモリ仕様
brainfuck には変数というものは存在しておらず代わりに最低 30000 byte の 0 で初期化されたのメモリを有しており、
そのメモリの位置を指し示すポインタを移動させることにより任意のメモリにアクセスできるようになっています。
未定義動作
brainfuck には未定義動作がいくつか存在します。そのうち重要なものを紹介します。
- 最大値に対するインクリメント
- 最小値に対するデクリメント
- メモリ領域外アクセス
これらの動作は一般的に動作が実行環境ごとに設定されていることが多いです。
実行環境による裁量
上記の未定義動作以外にも実行環境による裁量で変化しているものもあります。 以下にそのいくつかを紹介します。
- 値の最小値
- 値の最大値
EOF(入力の末端)
今回の記事に用いる実行環境
今回の記事で用いる環境は AtCoder という競技プログラミングを行うサービルで使われいてる実行環境に準拠します。
AtCoder での環境は以下の通りです。
- 値は
byte型 (0 ~ 255) 0に対するインクリメントは255255に対するインクリメントは0EOFは-1(= 255)- 対応する
]のない[はエラー - 対応する
[のない]はジャンプ時に先頭に戻る メモリは9999 byte( ※言語仕様を満たしません )- メモリの領域外アクセスはエラー
※メモリの byte 数は言語アップデートにより 30000 以上になりました。実際のサイズは確認していませんが、メモリオーバーすることはないと思って問題だけの数があります。
この記事で登場するコード例では、
[ と ] との対応はすべて取っており、メモリも仕様も 9999 を超えることがないように作成されています。
実行環境例
brainfuck のコードは実際に動かしてみるとわかりやすいです。こちらのサイトで簡単に実行できるので気になるコードは実際に動かして試してみてもいいかもしれません。
オンラインBrainf*ckデバッガ
問題例
いろはちゃんコンテスト Day1 A - 一問目
言わずと知れたbrainfuck向けの問題です。ABC 085 A - Already 2018
BACの中で最もbrainfuck向けの問題です。
次回
次回は基本構文の話しようと思います。
文字出力の話しました。
brainfuck 入門：ループ文と定数生成と文字出力 - 三流プログラマの戯言
記事一覧
AtCoderで茶色になるまでにやったこと/あったこと
先日(2019/09/21 )のAGC083にてついに茶色になることができました。
AtCoder界隈では色変したらブログを書く慣習があるようなので書いてみます。
茶色でこの記事を書くのは自分ぐらいだと思います。
茶色になったわけですが、使用言語はbrainf*ckです。ratedにはbrainfu*ckでしか出ていません。
なので、この記事はbrainf*ckの記事になりますし、普通の人には参考になりません。
目次
やったこと/あったこと
時系列に近い形で、やったこと(とあったこと)を記述します。
開発環境を整える
AtCoderやってる人なら当然ではありますが、開発環境を整えるのは結構重要だと思います。
AtCoderのコードテストでも可能ではありますが、やはり貧弱なので良い開発環境を整えたいところです。
brainf*ckはネット上で実行できる環境もありますが、どれもイマイチに感じます。
理由としては、ブレイクポイントを設置できない というところです。
デバッグ用にステップ実行できるものがほとんどですが、コード長が長くなるとステップ実行しないといけない量もかなり多いのでそれだけで時間を取られることになります。
そこで、開発環境を自作しました。
過去問を解く
過去問を解くことにより自分の引き出しの数を増やしていきます。
普通の言語以上に引き出しの数が重要となる言語なので、茶色でも要求される引き出しの数は多いです。
ライブラリを整理する
レートを上げるためには早解きも重要になってきます。
brainf*ckでは一般的な言語で簡単なことでも、コードが複雑になりがちです。
また、少しでも間違っていると、遠い場所で結果がおかしくなることも少なくないので、ライブラリを作ることは大切です。
ライブラリといっても高度なものではなく、入出力、積算、剰余などです。
Twitterで強い人と仲良くなると色々と嬉しいです。
ほかの言語とかだとわからないですが、brainf*ckは人口が少ないので、「brainf*ckをやってる」ってだけで、brainf*ckの強い人と絡めるのは大きいです。いろいろ話を聞けたりします。
また、brainf*ckをやっていない人でも、いいねをくれたりして自己顕示欲をみたせるのでとてもいいです。
囲ってもらえますし。
brainfuck縛りで茶色になりました。囲ってください https://t.co/4MQtdPzh78
— あんでぃ@量産型テ徒/-500/+300/+300 (@unidentifiedexe) September 21, 2019
マルチバイト変数のライブラリを整理
AtCoderで採用されているbrainf*ckの実行環境ではメモリの数値は255までしか格納できません。
しかし、当然のごとく255以上の整数を扱える必要があるので実装しました。
実装した項目は、インクリメント、デクリメント、加算減算、入出力、比較あたりです。
一応、積算と剰余計算も実装はしました。
煽る
直接関係ないですが、Twitterで仲良くなった人を煽りました。
早く入水して
— あんでぃ@量産型テ徒/-500/+300/+300 (@unidentifiedexe) September 8, 2019
煽られる
直接関係ないですが、Twitterで仲良くなった人に煽られました。
頑張ってる…
— ねころこ (@roko_TT) September 8, 2019
次茶色になって
茶色になって
茶色になって特に何か変かするわけではありません。
ただし、茶色になる過程で、brainf*ckの language owner になったり、AC数が500になったりしました。
また、brainf*ckでは数列の要素数が10,000を超えるとかなり厳しくなるために、簡単なB問題でも解けない場合があるので、
実はABCよりもAGCの方がレートが上がりやすかったりします。(というか新ABCになってレートが上がりにくくなってないですか？)
謝辞
無事茶色になることがで来ました。
これもひとえに、いろいろ教えてくださったbrainf*ckの上位陣(主に現在2~4位のお三方)、
brainf*ck自体はやっていないものの、自分の精進を陰ながら見守ってくださった、チョコラスクさんけんちょんさんを始めとする方々、
brainf*ckに興味を持って、自分に絡んでくださってる方々、
その他大勢の人のおかげでここまでこれました。
応援ありがとうございます。
今後について
brainf*ckで茶色になることと language owner になることを目標に頑張ってたので、今は目標がないです。
brainf*ckで緑を目指すのはただの苦行だと思うので、やる気にはなれないです。
一応ABC後に茶色になるまではbrainf*ckで行こうとは決めているのですが、そのあとは別言語(難解プログラム言語ではない)にも手をだそうかと思います。
ただ、コンテストでbrainf*ckで解けそうなな問題はbrainf*ckで解いていきたいなとは思っています。
あと、いい加減、brainf*ckの基本的な記事と、マルチバイト変数の記事を書きたいと思っています。
後書き
毎回虚無の記事を生成してすみません…
コメントとかもらえると喜びます。
AtCoderGrandContest038 を brainfu*ckで挑戦
初めに
AGC038が終わりました。Aのみの1完ではありましたが700点はbrainf*ckでは無理なので、満足いく結果です。
ABC140二続き解説記事を書きました。 ABC141？いえ、知らない子ですねぇ。
目次
注意
今回、コンテストに出るにあたって、言語はbrainf*ckを使用しています。
言語仕様などの細かい説明は今回も行いません。
A - 01 Matrix
概要と設計指針
指定の模様が作れるかどうかという問題ですね。結論から言ってしまうと、どのような場合でも作ることができます。
証明はしていませんが、AC出たので間違いないでしょう。
この手の問題は、入力例がすべて達成できている場合は、必ず達成出来ると思っています。
具体的な目的達成手法としては、1行辺り1がA個、0がW-A個の行要素を用意して、それをB行連続で表示、その後、0と1を反転させた行要素をH-B行連続で表示すれば達成できます。
また、その行要素の0と1の順番は任意であるために1がA個連続したあとに0がW-A個並ぶような行要素を作成することにします。
例によってH,W,A,Bは255を超えうるためにマルチバイトで変数をとります。
マルチバイトの話もいずれ記事にしたいとは思っています。
概要とコード
以下にコードを載せますが、長いので折りたたんでおきます。
（クリックで展開）
>>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< > #endregion >>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< > #endregion >>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< > #endregion < #region Multi_IsTrue // note 非ゼロ判定します //start ___{ a*}___ //resilt ___{ a*}_x_ //x : 0 if 0 1 if not 0 [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> [ - >>>[>]++[<]<<<< #region Multi_DecrimentIfPuls [-[>[+++++++++>]>]+<]>-<< >>>[<+[>]>>]<<< #endregion [<]<<< #region Multi_DecrimentIfPuls [-[>[+++++++++>]>]+<]>-<< >>>[<+[>]>>]<<< #endregion >>>>[>]< #region Multi_IsTrue [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> ] <<[<]<<< #region Multi_IsTrue [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> [ - >>[>]>> >>[>]+[<]<<<< [<]<<< #region Multi_DecrimentIfPuls [-[>[+++++++++>]>]+<]>-<< >>>[<+[>]>>]<<< #endregion #region Multi_IsTrue // note 非ゼロ判定します [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> ]
解説
今回、必要になる数値は順にA,W-A,B,H-Bとなります。入力順は H,W,A,Bなので、最初にAまで読み取って、必要になったらBを読み取ってます。
今回の処理の流れを以下に示していきます。
H,W,Aの読み取り- メモリに
2をA個追加しつつWをA回デクリメント 2の先に1をW-A個追加2と1で構成される行要素のメモリに対してそれぞれ47を足して2,1を1の文字コード及び0の文字コードの変換Bの読み取りB回行要素を出力しつつ、Hをデクリメント- 行要素から
47を引く - 行要素の
2と1を反転 - 行要素に
47を加算 H-B回行要素を出力
以上となります。
X回繰り返すという作業は「Xが0かどうかを確認して0でないなら、指定動作を行い、Xをデクリメントする」によって実現できます。
(これはシングルバイトで見ればbrainfu*ckでの基本構文になります。)
先に述べたとおりマルチバイト変数の話は長くなるので省略して、ここでは、2,3,4,8について書いていきます。
メモリの末端に2,1を追加
該当コードはこの部分です。
[>] //終端に移動 ++ //値の追加 [<] //始端に移動
コメント以上のことはしていないので詳しい説明は割愛します。++にするか+にするかで 2か1かが変わります。
ここで、1,0ではなく2,1を用いてるのは、終端に上手く移動してくれないからという理由になってます。
行要素に47を加算
この部分の該当コードはこの部分です。
++++++[->--------<]>+ // 47の負数生成 [[>]<[+<]>] // 47の負数が 0 になるまで全ての要素を加算
47の負数という回りくどい書き方をしていますが、-47のことです。
本来の言語仕様では0に対するデクリメントは未定義ですが、AtCoderで採用されているコンパイラは255になると定義されてるのでありがたく使用しています。
普通に47を生成して、繰り返すこともできるのですが、-47を生成したほうがコードが短くなるので自分はこちらを好んで使います。
コード長的には誤差の範囲ではあるんですけど
ちなみに、47生成する場合は以下のコードで実現できます。
>++++++[-<++++++++>]<- [->>[+>]<[<]<]>
行要素の2と1を反転
2と1を反転と書いていますが、2と1は順に連続しているだけなので、2が続く限りその要素をデクリメントその後1が続く限りインクリメントというプログラムで実現できます。
該当コードはこの部分です
[-[>-]] // 2 である限りデクリメント + // 最初の 1 もデクリメントしてしまうのでインクリメント [+>] // 1 が続く限りデクリメント <[<] // 始端に移動
これも普段brainf*ckを書かない人だとわかりにくいと思いますが、コメント以上のことはしていません。
ちなみに記事書いてた時に気がついたんですが、1行目は-[>-]でいいと思います。
あとがき
一応今回のコードはGithubに上げました。
github.com
質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
ところで、こんな記事見る人いるんですかね…(定型文)
AtCoder Beginner Contest 140
初めに
ABC140が終わりました。自分は残念ながらABCの3完でレートは下がりました。
（といっても、元が低いので、そこまで低くはなっていないですが。
コンテスト終了して8分ほどあとにDをACしました。時間内に出せていたらと思うと悔しいです。
せっかく時間オーバーとはいえ4完したので、解説記事を書きました。
目次
注意
今回、コンテストに出るにあたって、言語はbrainf*ckを使用しています。
言語仕様などの細かい説明は今回行いません。
A - Password
1からNまでの3桁のパスワードが何通りあるかという問題です。
順当にn*n*n をすればいいです。ただし、最大で9*9*9 = 729 となり、メモリの最大値(255)を超えるので、工夫が必要です。今回は、自作のマルチバイト変数を使用しました。(詳細は省きます)
以下bfのコードです。（クリックで展開）
>> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >>> >>+ [-<,----- -----[ >++++[-<----->]<-- [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<] +>[-<->]< [- /* */ > ]>+< ]>]< < [->+>+<<] >> [-<[-<+<+>>]<[->+<]>>] <<<[->>>+<<<]>>> [-<[-<+ <<<<{[[-<+>[[>>]>]]<[->+<]<]<}>>>> >]<[->+<]>>] <<<<<< <+>[<<]> >[<+>>[<<-<[<<]<]>] >[->>] >>>[<+>>>] ++++++++++[-<+++++>]<--- <<->> [[+<<]>>[>>]<+<--] <<[<<]>>[.>>] >+[-<<<[<<]>>[->>]>]
B - Buffet
B問題はB問題にしては難しかったように感じます。
入力が3つの配列になってますが、Nが高々100で、A,B,Cも高々50なので結構楽です。
ただし、答えは255を超えうるのでここはマルチバイト変数の出番です。
具体的には、3つの配列をメモリに展開して、A配列を前から順番に見て行って、
そのインデックスに該当する番目のBの配列の要素をsumに加算、直前のインデックスと比較して、1大きいならインデックスに該当C配列の要素をsumに加算します。これを、Aの配列の末端まで繰り返せば正解できます。ただし、Cは配列長が短いことを考慮しないといけません。
直前のインデックスの初期値は-1相当の225にしました。また、簡単のためにCの要素の足し算を先に行っています。
配列のi番目の要素の取得方法の説明は省略します。
以下bfのコードです。（クリックで展開）
,[,----------] >> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >>> >>> >>+ [-<,----- -----[ >++++[-<----->]<-- [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<] +>[-<->]< [- /* */ > ]>+< ]>]< >>>> >>+ [-<,----- -----[ >++++[-<----->]<-- [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<] +>[-<->]< [- /* */ > ]>+< ]>]< >>>> >>+ [-<,----- -----[ >++++[-<----->]<-- [>++++[-<---->]<<[->>+<<]>>[-<<++++++++++>>]<[-<+>]>+<] +>[-<->]< [- /* */ > ]>+< ]>]< <[<]<<<<[<]<<<<[<] <<->> > [ -[ [>]>>>[>]> [-<+>]>[>] >>> [>]> [-<+>] <[<]<<<[<]<[<]<<<[<] <+<->>>- ] <<+< [[-]>>-<<]+>>+ [ >>[>]>>>>[>]>[>]>>>[>]< [ [<]<<<[<]<<[<]<<<[<]<[<]<<< [[-<+>[[>>]>]]<[->+<]<]< >>>>[>]>[>]>>>[>]>[>]>>>[>]< - ]+ [<]<<<[<]<[<]<<<[<]<[-] ] >> [>]>>>[>]> [ - <<[<]<<<[<] <<[<]<<< [[-<+>[[>>]>]]<[->+<]<]< >>>>[>]>>[>]>>>[>] > ] + [>]>>>[>] <[[->+<]<] <<<[<] <[[->+<]<] <<<[<]> ] <<< [<]<<< <+>[<<]> >[<+>>[<<-<[<<]<]>] >[->>] >>>[<+>>>] ++++++++++[-<+++++>]<--- <<->> [[+<<]>>[>>]<+<--] <<[<<]>>[.>>] >+[-<<<[<<]>>[->>]>]
C - Maximal Value
C問題は、ぱっと見難しそうですが、Nも高々100ですし、入力を前から処理していけばいいので、比較的楽です。
答え自体は、B0 + Σ_0..n-2 Min( Bi , Bi+1) + Bn-1で求まります。(数式が見にくくてすみません。)
Bはもちろん、255以上を取りうるので、マルチバイト変数を用いて計算します。
また、Min( a , b )を求めるのはめんどくさいので、
a -= b; if(a > 0) a = 0; a += b;
という計算方法で実装しています。
この実装はもちろん遅いのですが、Nが高々100なので時間は十分に間に合います。
数列の末端判断は、数列が読み込めたかどうかで実現していますが、正直、Nをカウントした方が楽だったと思います。
以下bfのコードです。（クリックで展開）
>>>> ++++++++++ -[[>]+[<]>-]+[>]< >>> ,[,----------] > +>+>+>+>+>+>+>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->] < [ [<]<<[<]<[->+<] >[>]>>[>]>+<< -[ [<]<<[<]>+[>]>>[>]>+<<- ]< ] >>>[[-<<+>>]>]<<<[<]> <<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ <+>[->+<]>----------< ]]]]]]]]]]]< ] >>[[-<<+>>]>]>[>]< > >>> +>+>+>+>+>+>+>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[++<-[+<-]]+>[->] < [-[+[>]>]+<] <[[<]<]>>[>]> [ [-] <<- [ [w<]<[->+<] >+++++++++[>]>>[>]>+<< -[ [<]<<[<]>-[>]>>[>]>+<<- ]< ] >>>[[-<<+>>]>]<<<[<]> <<< + [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ <+>[->+<]>----------< ]]]]]]]]]]]< ] >>[-[+<]] >[[-<<+>>]>] <<<[<]> -[[-]<->]<+ [ [-] >>[[-]+>]<[<]---------< ] >++++++++++[>]>>>[>]< [ [<]<<[<]<[->+<] >[>]>>[>]>+<< -[ [<]<<[<]>+[>]>>[>]>+<<- ]< ] >>>[[-<<+>>]>]<<<[<]> <<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ <+>[->+<]>----------< ]]]]]]]]]]]< ] >>[[-<<+>>]>]> <<<< [<] <<[>>>[-]<<]>>>[>]< [ [<]<<[<]<[->+<] >[>]>>[>]>+<< -[ [<]<<[<]>+[>]>>[>]>+<<- ]< ] >>>[[-]<<+>>>]<<<[<]> <<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ <+>[->+<]>----------< ]]]]]]]]]]]< ] >>[[-<<+>>]>]> [>]>>>[>]< [ [<]<<[<]<[->+<] >[>]>>[>]>+<< -[ [<]<<[<]>+[>]>>[>]>+<<- ]< ] >>>[[-]<<+>>>]<<<[[-]<]> <<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ <+>[->+<]>----------< ]]]]]]]]]]]< ] >>[[-<<+>>]>]> +>+>+>+>+>+>+>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[++<-[+<-]]+>[->] < [-[+[>]>]+<] <[[<]<]>>[>]> ] <<[<]<<< [ [<]<<[<]<[->+<] >[>]>>[>]>+<< -[ [<]<<[<]>+[>]>>[>]>+<<- ]< ] >>>[[-<<+>>]>]<<<[<]> <<< [ [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[ <+>[->+<]>----------< ]]]]]]]]]]]< ] >>[[-<<+>>]>]>[>]< [<]<<< +[<]>[-[+[>]]<+>>] ++++++[-<-------->]<+<--> [[<]>[+>]<]<[<]>[.>]
D - Face Produces Unhappiness
D問題はぱっと見難しそうに見えますが、1回行うごとに幸福な人が最大2人増えます。
ただし、幸福な人は最大でもN-1人しかそんざいできません。
また、1回の試行で幸福な人が2人増やせない場合もありますが、その時は、N-1が答えになるので、
現在幸福な人 + 2*KとN-1の最小値を取ればいいです。
現在幸福な人は、前後が同じ向きである組み合わせの数なので、入力を前から処理していけば問題なく行えます。
以下bfのコードです。（クリックで展開）
>> >+> >+> >+> >+> >+> >+> >+> //桁数分移動(桁識別用の1を加算) >+[-<,----------[----------------------[---------------[<<]>>[[-<<+>>]>>]<+<]]>]<< [<[-<<]<]>>[-<+>>>]<<<[-[-<+>]>++++++++++<<[->+>-<<]<]>>>[>>]<< >>-<< [>>+<<<[->+[>>]]>[-[-<+>]]<<]< >>[>+[>>]]<< >>>> >> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >++++++++++> >>> >> >+> >+> >+> >+> >+> >+> >+> //桁数分移動(桁識別用の1を加算) >+[-<,----------[----------------------[---------------[<<]>>[[-<<+>>]>>]<+<]]>]<< [<[-<<]<]>>[-<+>>>]<<<[-[-<+>]>++++++++++<<[->+>-<<]<]>>>[>>]<< >>>> ,---------->+++++++++++[-<------>]<[[-]>+<]>[-<+>]< > ,---------- [ >+++++++++++[-<------>]< [[-]>+<] <[->+<]>>[-<-<+>>]+ <[//NEqal -[+] >-< ] > [ <<<<<< [<<] <<<<< [[-<+>[[>>]>]]<[->+<]<]< >> >>>>>[>>]>>> >- ] < ,---------- ] <[-] <<<< [ <[->< << << << << << << << // 桁数分表記 <<<<< > [[-<+>[[>>]>]]<[->+<]<]< >> >>>>> [>>] < ] < ] >>[<++++++++++>[-<->>+<]>[-<+>]>]<<//Revert [ <[->< << << << << << << << // 桁数分表記 <<<<< > [[-<+>[[>>]>]]<[->+<]<]< >> >>>>> [>>] < ] < ] >>[<++++++++++>[-<->>+<]>[-<+>]>]<<//Revert [<<]<<<<< [ <[->< << << << << << << << // 桁数分表記 <<<<< > >>-<< [>>+<<<[->+[>>]]>[-[-<+>]]<<]< >>[>+[>>]]<< >> >>>>> [>>] < ] < ] >>[<++++++++++>[-<->>+<]>[-<+>]>]<<//Revert [<<]<<<<<[<<] >> -[ +[<[->+<]>>>] ] <[>+[>>]<]< >>>>>>>[>>]<< [ <[->< << << << << << << << // 桁数分表記 <<<<< > [[-<+>[[>>]>]]<[->+<]<]< [[<<]<]>>>[>>]<< >> >>>>> [>>] < ] < ] <<<<< <+>[<<]> >[<+>>[<<-<[<<]<]>] >[->>] >>>[<+>>>] ++++++++++[-<+++++>]<--- <<->> [[+<<]>>[>>]<+<--] <<[<<]>>[.>>]
あとがき
一応今回のコードはGithubに上げました。
github.com
質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
ところで、こんな記事見る人いるんですかね…
CPSCO2019 Session1 B問題をbrainf*ckで解く(後編)
前編では、配列の作成まで書きましたが、 後編では、それらの値がすべて等しいかどうかを判別していきます。
前編を読んでない人は先にそちらを読んでください。
一般の言語だと、配列の先頭から見て、0でなければ記録されている数と一緒かどうかを見ていって、
異なる数値があらわれた場合は no そうでないならyes とすればいいわけです。
C++で書くとこんな感じでしょうか
int num = 0; bool isAllEqal = true; for(int i = 0; i< 26; i++){ if(data[i] != 0){ if(num == 0) num = data[i]; else if( data[i] != num){ isAllEqal = false; break; } } }
brainf*ckでの実装もこれでもよかったのですが、多少面倒そうだったので、以下の方式で行いました。
int first = 0; for(int i = 0; i < 26; i++){ if(data[i].Count == 0) data[i].IsEmpty == true; } for(int i = 0; i < 26; i++){ if(data[i].Count != 0) { first = i; break; } } while(data[first].Count !=0){ data[first].Count--; for(int i= first +1; i < 26; i++){ if(data[i].IsEmpty == true) continue; data[i].Count--; } }
ここで for(int i = 0; i < 26; i++) が複数回登場するため、前編で書いたようなindexアクセスを毎回行うのは無駄なので、
for(int i = 0; i < 26; i++){ data[pos].PtrMarker = 1; }
として配列であることを示すマークを入れて、
int i = 0 ; while(data[pos].PtrMarker == 1){ //ここに処理を記述 pos++; }
といったコードで処理を簡略化します。
そしてほかにも細かいところを、Brainf*ckで書きやすいように変更して、出来上がったbrainf*ckコードがこれです。
++++++++++ ++++++++++ ++++++ [- > >>>[>>>]+[<<<]<] //for(int i = 0;i<26;i++) data[pos].PtrMarker =1; > >>> [<<[>>>]>>[<+<]>>>>>] //for(int i = 0;i<26;i++) // if(data[i].Count == 0) // data[i].IsEmpty == true; <<<[>>>>>]<<<<< //} [ <[<<<] // 一番末尾にある有効な要素に移動 <[[-<[<[<<<]>[<<->]<<]]>>>[<<<<+>]<[->] >>>[>>>]] // 有効要素のCountを1減らす >>[>>>] <<< [>>>]<< // 配列の末尾に移動 ] < [<[<<<] // 配列の末尾から有効要素を探索 <[ //見つかった有効要素のcntが0かどうかを判別 [-] // cnt != 0 の場合 "No"を出力 ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++. ++++++++++ ++++++++++ ++++++++++ ++ +.[-] >[-]>[-]+< //ループを繰り返さないための処理 ]< ] >> <+>[[-]<->] < //Noが出力されていないことを検知 [ //Noが出力されていない場合はYesを出力 [-] //Output Yes ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +++++++++. + ++++++++++ +. ++++++++++ ++++. [-] ]
うわぁ、説明が雑。 (どうせ細かいところを見てる人なんていないでしょう)
ちなみに、C++のコードでは先頭から見て行っていますが、コードの関係上、末尾から見て行っています。
特に深い意味はなく、直前の動作で、ポインタが末尾に近いかったからです。
また、普通の言語ですと、ループ内ですべて等しいかの確認を行い、それをbool型の変数に入れるのが普通だと思いますが、 めんどくさかったので、Noの場合はその場で出力しました。（else句を書くのは意外と面倒なんですよね。）
ここまで読んでくださった方が何人いるかはわかりませんし、上記のプログラムを(こんな雑な説明で)理解できた人はまずいないでしょう。
でも、brainf*ckという言語がどういう言語なのかを少しは感じることができたのではないでしょうか。
brainf*ckについて少しでも興味を持ってもらえると嬉しいです。
それではこれで。
CPSCO2019 Session1 B問題 をbrainf*ckで解く(前編)
こんにちは、先日はにーまさん主催の初心者向け競プロ合宿CPSCOに参加してきました。 主催してくれたはにーまさんには感謝しています。
細かいSessionの話とかはほかの人に任せて、今回はSession1のB問題に関して書いていきます。
使用言語はBreakbrainf*ckです。
brainf*ckの言語に関して下ない人向けに、ざっくり説明すると。
「コンパイラのサイズが最小になるように作られた言語」です。
以下はbrainf*ckの予約語一覧です。
| 予約語 | C++ の対応コード | 説明 |
|---|---|---|
+ |
array[ptr]++; |
現在のポインタが指す値をインクリメントする |
- |
array[ptr]--; |
現在のポインタが指す値をデクリメントする |
> |
ptr++; |
ポインタをインクリメントする |
< |
ptr--; |
ポインタをデクリメントする |
[ |
while(array[ptr]){ |
現在のポインタが指す値が0なら対応する]に飛ぶ |
] |
} |
現在のポインタが指す値が0でないなら対応する[に飛ぶ |
, |
array[ptr] = readchar(); |
標準入力から1文字を受け取りそのASCII文字コードを現在のポインタに格納 |
. |
putchar(array[ptr]); |
現在のポインタが指す値をASCII文字コードとして出力する |
わかりやすさのためにC++に置換したときの対応コードを書いておきました。
細かい仕様とか知りたい方は適当にググってもらえればと思います。（brainf*ckの基礎的な話もまとめたいなと思わなくはない。)
さて、本題の問題に関してですが、 a~zの各文字が何回出てくるかを見て、0でない要素がすべて同じであればOKとなります。（解説のまんま） 普通の言語であれば入力を文字列で受け取ってから処理しますが、brainf*ckだとめんどくさいので(そもそも配列が面倒)、 1文字ずつ受け取りながら処理をしていきます。
C++でこういうイメージです。
unsigned char letter = getchar(); letter -='\n'; // -=10 while(letter){ letter -= ('a'-'\n'); // -= 87; data[letter]++; letter = getchar(); letter -='\n'; }
これをもとにbfainf*ckで書きます。
ただし、制約の関係上256以上の値をとる可能性はありますが、brainf*ckで256以上を扱うのは非常に面倒なため、
今回は気にしないことにしました。
具体的に言うと、256nは存在しない文字と同列として扱われ、256n+a (0<a<256) は a と同じ文字数として扱われます。
テストケースによってはWAが生えますが、無いと信じて実装しました。(実際になかったです。)
, // letter = getchar(); ---------- // letter -= 10; [ // while(letter){ ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ------- // letter -= 87; [- > >>>[>>>]+[<<<]<]> >>>[>>>]<<+>> <<<[-<<<] < // data[letter]++; , // letter = getchar(); ---------- // letter -= 10; ] // }
上記のコードはコメントっぽく書いてる部分の予約語にも反応するため、コピペしただけではうまくいきません。 (コメントを削除するとうまく動きます)
data[letter]++; 以外の部分は何となく理解できるのではないかと思います。
data[letter]++; 部分の細かい説明ですが、まず前提条件として、「brainf*ckで配列の操作は容易ではない」ものがあります。
理由としては、指定数ポインタを移動させることができないので、「ポインタを１移動させる」を指定数行うことになります。 ここで登場するのが「for文」となります。(余談ですが、brainf*ckにおいてfor文は最も基礎的な構文です。)
そして 、brain*ckのfor文の欠点として、 for分の内部の処理が終わった段階で、初期位置(繰り返し回数が格納されているポインタ)まで戻ってくる必要があるため、for分でのポインタを指定数ずらすという命令は不可能になります。
そこで、data配列を以下のような構造体をで定義することを想定します。
struct Cnt { unsigned char Count; bool IsEmpty; bool PtrMarker; }; struct Cnt data[26];
(IsEmptyは前編では使用していません。)
そして、data[n].Count++;を行うコードを以下のように想定します。
while(n > 0){ n--; int pos = 0; while(data[pos].PtrMarker) pos++; data[pos].PtrMarker =1; while(data[pos].PtrMarker) pos--; pos++; } while(data[pos].Count++) pos++; data[pos].Count ++; while(data[pos].PtrMarker){ data[pos].PtrMarker = 0; pos --; }
ここでposはポインタを示すので、実際にどこかに値が格納されることはないです。
また、ループの終わりに0になっている必要があり、このコードではそれを実現しています。
また、察しのいい人は気づくかもしれませんが data[-1]の領域を参照しますが、data[-1]相当のメモリも存在しているので、参照しても、エラーも何も起きません。
これをbrainf*ckで書くと
[ //while(n > 0){ - // n--; > // int pos = -1; ( data[-1].PtrMarker 相当の場所にポインタを移動) >>> // pos = 0; ( data[0].PtrMarker 相当の場所にポインタを移動) [>>>] // while(data[pos].PtrMarker) pos++; + // data[pos].PtrMarker =1; [<<<] // while(data[pos].PtrMarker) pos--; < // ( ループカウンタの部分にポインタを戻す ) ] //} > // int pos = -1; ( data[-1].PtrMarker 相当の場所にポインタを移動) >>> // pos = 0; ( data[0].PtrMarker 相当の場所にポインタを移動) [>>>] // while(data[pos].PtrMarker) pos++; <<+>> // data[pos].Count =1; <<< // ( data[pos-1].PtrMarker 相当の場所にポインタを移動 ) [ // while(data[pos].PtrMarker){ - // data[pos].PtrMarker = 0; <<< // pos --; ] // } < // ( ループカウンタの部分にポインタを戻す )
このコードの条件として、繰り返し回数が格納されているのは data[-2].PtrMarker相当の場所で、 data[-1]相当の場所は全て0になっています。
この説明で理解できるかどうかはわかりませんが（きっと理解できる人はひと握りしかいない)、理解したものとして進めます。
ここまでのコードで、各文字が何文字あるかを配列に格納することができました。
前編はここまでにします。
すべての文字数が同じかどうかの判別は後編としていつか書きます。
書きました。
響ちゃんスイッチのメニューデータの管理について
先日投稿した、響ちゃんスイッチですが、今日はそのメニューデータの管理方法について、自分のメモとして記事にしておきます。
わかりやすいようにとか、機能説明とか特にしないので、見る意味は皆無です。
また、後でメモリ管理に関しては仕様を変更する予定で、その前に旧仕様を忘れかけなので思い出すついでに書きます。
まず、メニューファイルのデータ構造に関して
| データ名 | データ型 | データ長(byte長) | 値 | 備考 |
|---|---|---|---|---|
| FileType | char[4] | 4 | "men2" | Ver2なので末尾が２ |
| Offset | uint16_t | 2 | 6 | 有効データまでのオフセット |
| MenuNum | uint16_t | 2 | n | メニューの数 |
| DataPtrs | uint32_t | 4*n | 50 | Pathの長さ |
| 個別データ | 後述 | n * x | 個別のメニュー情報 | |
また、個別データは以下の形式
| データ名 | データ型 | データ長(byte長) | 値 | 備考 |
|---|---|---|---|---|
| DataLength | uint32_t | 4 | 自身を含まない個別データの長さ | |
| PathLength | uint16_t | 2 | 現在は50固定 | メニュー先のファイルパスの長さ |
| Path | char[PathLength] | PathLength | メニュー先のファイルパス | |
| FontBitHeight | uint8_t | 1 | ビット単位でのフォントの高さ | |
| FontByteHeight | uint8_t | 1 | バイト単位でのフォントの高さ | |
| FontWidth | uint16_t | 2 | フォント情報の幅 | |
| FontData | byte[] | フォントデータ |
ここで、フォントデータは各文字の個別の情報ではなく、画面に表示するためのメニューの表記文字列を一まとめに持ってます（伝われ
このデータをメモリに配置するためのプログラムがこれ
int offset = 6; _dataFile.seek(offset); _dataFile.read(_dataReadTempBuf, 2); uint32_t dataPtrDataOffset = _dataFile.position(); uint16_t menuContextCount = *(uint16_t*)(_dataReadTempBuf); uint16_t dataPtrDataLength = menuContextCount * 4; byte* fontDataBuf = _dataReadTempBuf + dataPtrDataLength; uint16_t writePos = SramManageWrapperClass::GetNestDataLastAddless() + 2 * (menuContextCount + 1); _dataFile.read(_dataReadTempBuf, dataPtrDataLength); for (uint16_t i = 0; i < menuContextCount; i++) { _dataFile.read(fontDataBuf, 4);//個別データのデータ長の読み取り uint32_t dataLen =*(uint32_t*)(fontDataBuf + 0); _dataFile.read(fontDataBuf, dataLen); uint32_t fontPosInLocal = 2 + *(uint16_t*)(fontDataBuf) + 1 + 1;//フォントの幅とフォントデータのみを記録する; uint32_t writeLength = dataLen - fontPosInLocal; if (writePos + writeLength >= SRAM_ADDRESS_NUM) break; SramWriteBytes(writePos, fontDataBuf + fontPosInLocal, writeLength); SramWriteBytes(SramManageWrapperClass::GetNestDataLastAddless() + 2 * i, (uint8_t*)(&writePos), 2); writePos += writeLength; } SramWriteBytes(SramManageWrapperClass::GetNestDataLastAddless() + 2 * menuContextCount, (uint8_t*)(&writePos), 2); _dataFile.close();
ってわけで、内部メモリ的にはこう配置してるはず…はず…
| データ名 | データ型 | データ長(byte長) | 値 | 備考 |
|---|---|---|---|---|
| MenuNum | uint16_t | 2 | n | メニューの数 |
| FontDataPtr | uint32_t | 4*(n+1) | フォントデータが入っているポインタ | |
| *FontWidth | uint8_t | 1? | フォントの幅 | |
| *FontData | byte | フォントデータ |
これ以上は眠いのでここで終わり…
