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で配列の操作は容易ではない」ものがあります。
理由としては、指定数ポインタを移動させることができないので、「ポインタを1移動させる」を指定数行うことになります。 ここで登場するのが「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なので末尾が2 |
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 | フォントデータ |
これ以上は眠いのでここで終わり…
響ちゃんスイッチ
皆さん、艦これは好きですか。
皆さん、駆逐艦は好きですか。
皆さん、六駆は好きですか。
皆さん、銀髪幼女は好きですか。
皆さん、響ちゃんは好きですか。
私は好きです!(響ちゃんが)
響ちゃんが好きで、ボタンを押すと響ちゃんのボイスが流れる装置を作るぐらいには響きちゃんが好きです。
と言って、この装置のアイディアは自分で出したわけではなく、とある年のNT京都で雪風スイッチというものを見てつくろうと思った次第であります。
画像とかその他もろもろは私のTwitterとかに上がってたりするのでブログの方では省略します。
(単純にめんどいだけ)
この記事は殆ど自分の防備録なので許してね。
細かい機能はさておき、ボタンを押すと音声が流れるという機能が主なわけですが、
数種類のボイスの中から、ランダムに選択されたボイスを再生する為、
元々は、
・ボイスの数、ボイスが存在するディレクトリパスを記したtxtファイル
・連番が与えられたwavファイル郡
を用いて下のコードで呼び出してました。
ちなみにArduinoを使用しています。
void VoiceRandomPlayMenu(char* dirName, char* viewFileName, byte numMax) { LcdUpdateByFile(viewFileName); char* fileNamePtr = _dataReadStr3; while (*dirName != NULL)*fileNamePtr++ = *dirName++; *fileNamePtr++ = '/'; while (1) { byte state = GetSwitchState(); if (state & SwitchState::Center) { randomSeed(millis()); byte num = random(20000) % numMax; sprintf(fileNamePtr, "%02d.wav", num); PlayMusic(_dataReadStr3); } else if (state) { return; } } }
Arduinoはほぼc++ですがc++に慣れてないので汚いコードに…
やってることは、ファイル数未満の数をランダムに生成し、[数字].wavのファイルを再生する というだけです。
でも、先述のとおり、これだとファイル数が多くなります、また、いろいろなキャラを入れようと思うと、キャラごとにディレクトリを造らない時計ないというめんどくささ…
だから、単一ファイルで音声データを管理するために以下のような読み込みおプログラムを作成
boolean VoiceRandomPlayMenuBySingleFile(char* fileName) { {//ファイルタイプの確認 char type[5] = "----"; if (!(_dataFile = SD.open(fileName, FILE_READ))) { ErrorLog::WriteToLogFile("file Open Error <", false); ErrorLog::WriteToLogFile(fileName, false); ErrorLog::WriteToLogFile(">"); LedBlink(Leds::LeftLed, 200); return false; } // error opening file _dataFile.read((byte*)type, 4); if (!IsSame(type, "vlst")) { _dataFile.close(); ErrorLog::WriteToLogFile("file type Is Not vlst <", false); ErrorLog::WriteToLogFile(fileName, false); ErrorLog::WriteToLogFile(">"); LedBlink(Leds::LeftLed, 200); return false; } _dataFile.read((byte*)_dataReadTempBuf, 2);//Read offset _dataFile.seek(*((int*)_dataReadTempBuf)); } //重要データの抽出 _dataFile.read((byte*)_dataReadTempBuf, 4 + 4);//Read ImgPtr And SoundPtr auto imagePtr = *(uint32_t*)_dataReadTempBuf; auto soundNum = *(uint32_t*)(_dataReadTempBuf + 4); auto soundPosesPtr = _dataFile.position(); {//サムネ画像の出力 if (imagePtr == 0) { LcdClear(); UpdateText(" No Image.", 4); } else { _dataFile.seek(imagePtr); _dataFile.read(_imgBuffer[1], 52 * 120); SendBufferDataBy52Length(_imgBuffer[1], 0, 120); _dataFile.read(_imgBuffer[1], 52 * 120); SendBufferDataBy52Length(_imgBuffer[1], 120, 120); } } //音声出力 uint32_t turgetPos[2]; while (1) { byte state = GetSwitchState(); if (state & SwitchState::Center) { randomSeed(millis()); byte num = random(20000) % soundNum; _dataFile.seek(soundPosesPtr + (4 + 4) * num); _dataFile.read(turgetPos, 4 * 2); PlayMusicByFilePlace(&_dataFile, turgetPos[0], (int32_t)turgetPos[1]); } else if (state) { return true; } } }
ざっくり言うと、各ボイスの開始のデータ位置と各データの長さをどこかに記録しておいて、その都度その場所のデータを再生するという感じ。
また、ファイル形式は下のようにしてる。
フィールド名:byteサイズ (値)
Type : 4 ("vlst") Offset :2 (6) imagePtr: 4 Sound num:4 Sound ptrs and length: (4+4)*n Image data :x Sound datas :y
とりあえず画像データは抜きで動作することは確認済。
実は、このファイル生成プログラム(旧形式からの変換プログラム)は書いてないので、今回用いたテストファイルは自力でバイナリエディタで書いた。何してるんだ自分は。