ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。CodeIQはじめに久しぶりの講座ネタとして、最近締め切りを迎えた、CodeIQの「あしあと」を題材に、Brainf**kでのコードを設計し実装するまでを解説してみたいと思います。※なお、Brainf**k講座本編に関しては、最後の第8回をご覧ください。codeiq.jp問題この問題は、次のような内容でした。9×9のマス目の上を、入力に従って動く時、最終的な状態を出力する。入力は、最後の改行以外は^v<>の4種類の文字からなり、それぞれ上下左右の1マス移動を表す。移動の順序は入力の順番そのまま。開始地点は1行1マス目、とする。移動によってマス目外に出ることは考慮しなくて良い。マス目の状態の出力は、1行9文字、9行で行い、一度でも通ったマスはY、それ以外はxに置き換える。>>>>>>>>vvvvvvvv<<<<<<<<^^^^^^^^という入力であれば、外周をぐるりと一周する動きを表しますから、出力は次のようになります。文字の判別さて、それではどのような実装にするかまずは設計を行うのですが、何を最初に気にするかというと、実は文字の判別だったりします。)Brainf**kでは,によって、1文字分の文字コードがセルに保存されます。そこから判別すべき文字に対応する数値を引いてゼロ/非ゼロによって判別しても良いですが、流石にそこそこ大きな数を都度引くのには抵抗があります。よって場合分けを行うことを考えます。94,118,60,62,10、実は余りでの判別という意味ではあまりよろしくありません。割る数を色々工夫しても、どうしても余りが被りがちだからです。ここは商も活用します。改行は文字コードが小さいので、商も必然的に小さくなります。今回5で割り算すれば改行以外は余りで判別できますから、大きな数の判断が不要になります。続いてセルの配置です。今回の問題は、入力を全部処理しないと、たとえ一部であっても出力内容が決まりません。そのため、9×9のマスの状態をセルに保持する必要があります。そこでメジャーな言語だと、2次元配列に相当するものを使うことを考えられるところですが、Brainf**kにあるのは1次元のセルの並びだけです。必然的に1次元配列化して考えます。ついでに、出力時の改行を処理しやすいように、行と行の間の区切り要素を設けておきます。これにより、行間移動は10要素の移動に置き換えることができます。問題は、この配列の中でのポインタ移動です。このセル領域にいるところで文字入力、割り算、余りの判断とやるには、配列の間隔を5~6セル確保する必要があり、無駄に領域が広くなります。移動前の要素にマーク付けして一旦領域外に出て入力を処理し、マーク付けしたところまで戻って相対移動すれば十分です。いうことで、配列要素は最小限の2セル構成とします。最小限と言ってるのは、Brainf**kで配列を扱う場合、どうしても移動を管理するために1セルずつ空ける必要があるからです。次の図のようにざっくりセルの配置が決まりました。マスの移動を処理するときに端の存在は気にしなくて良いのですが、後で出力する時に終わりが分かった方が良いので、終端も設けます。処理の流れさてでは、処理の流れを考えます。大体次のような流れにすれば、無理なく組むことができそうです。Brainf**kの場合、距離を動的に計算しての移動は、実行時間的にも処理の複雑さ的にもなかなか厳しいのですが、決まった場所に移動するのは、マーク付けの管理を行えば十分です。実装では実際に実装を見ていきます。これをベースに説明を加えていきます。領域のセットアップ最初は領域のセットアップです。90要素180セルの終端を設ける必要がありますから、指定移動距離を使います。>>+<-<<<<<処理が終わった時のセルの状態は、次のようになっています。入力処理~マス目移動~マスへの足跡付けということで、いよいよメインの入力処理です。改行で処理は終わりなのですが、EOF検出の方が処理としては書き易いので、5行目~23行目のように、EOF(-1)検出のループを組みます。<<,+]で、文字を入力したら直ぐに割り算に移ります。ここではあくまで文字が判別できれば良いので、5で割った余りそのものが要るわけではありません。スタンダードなアルゴリズムよりも1セル少なくて済むものを採用します。改行の時の商2以外で、マス目の分岐に入ります。]さて、ここで4種の文字に応じて分岐があるわけですが、どこまで処理を共通化し、どこから分岐で処理を分けるか、を考えます。後に分岐するのは大変です。分岐のための条件が移動したその場にある必要があり、ということは割り算で出た端数を持ち運ぶことになるからです。こなす所までは確定です。3.以降はまとめることができそうです。分岐を抜けた後に他の分岐に入らないように注意して次のように分岐します。抜けたら、最後は出力のみです。終端が設定されているので、1セル置きに配置されている要素を辿っていくのみです。どこかにマークが残っていて邪魔になる可能性があるので、逐一クリアしていきます。値としては、改行の2、Yの1、xの3種類です。と11をベースに構成します。if-else型で分岐を組むのはelseの制御が面倒になるので避け、当てはまった分岐以降の処理を全て通る形にしています。>>>+]これで、実装が全て完了しました。終わりにいかがでしたでしょうか。実際にBrainf**kでコードを組む時の参考として、Brainf**k案件等実務に役立てて頂ければ幸いです。気が向いたら、ちょくちょく番外編を書くかも知れません。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。