三流プログラマの戯言

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

AtCoderで Forth 入門

AtCoder Forth

概要

今回はプログラミング言語の Forth について書きます。
この記事は刺身タンポポ同好会のアドベントカレンダーの記事です。
刺身タンポポ同好会についてはこちら
昨日の記事はこちら
明日の記事はこちら

目次


Forth とは

言語概要は wikipediaの記事 でも読んでみてください。
とてもざっくり説明すると、逆ポーランド気法を用いるスタック型の言語です。
ちなみに、いわゆる難解プログラミング言語ではなく、れっきとした実用言語みたいです。
ただし、私は難解プログラミングに近いものを感じました。 型という概念はないですが、形式上浮動小数がなかったり、入出力がめんどくさいイメージです。(もしかしたら私のリサーチ不足で実際にはあるのかもしれません。)

所感

この言語は実用言語ということもあり、関数を作成することができます。
普段書いている brainfuck には関数がないのでとてもうれしいです。 また、- も関数名に使える珍しい言語なので、せっかくなのでケバブケースでコードを書いていきます。

命令一覧

難解プログラミング言語ではないので、結構多いです。
こちらのサイトに一覧があるので参考にしてください。 今回の肝になる命令をいくつか挙げておきます。

  • 関数宣言
    : name ... ; で関数を宣言できます。関数と書きましたが関数以外にも使えます。
  • ループ
    begin ... until や begin ... while ... then などでループが書けます。
  • スタック操作命令　　 dup, swap, drop 等があります。
  • 算術命令 四則演算や比較演算です。

AtCoder で利用してみる

導入

この言語はAtCoderで使えるので問題を解くことを考えていきましょう。 幸い、AtCoderの問題の多くは整数のみで解くことができます。

入力

数値の入力を行う必要があります。 数値の入力は簡単で、1 文字ずつ数字にパースし既存の値を 10 倍して足すを繰り返すだけです。

: read-number 0 0 begin swap 10 * + key 48 - dup 0 < until drop ;

出力

数値の出力を行う必要もあります。 数値の出力は 正負の判定を行った後、10 の商と余りを求めて余りをスタックに積んでいきます。それを商が0になるまで繰り返し、スタック上の数値を順に出力すればいいです。 もちろん、スタック上のすべてを出力すると数値出力で積まれた数値以外も出力してしまいますので、マーカーとして 0 をあらかじめスタックに積むなどを行う必要があります。

: write-pure ( d --  ) 
dup 0<> if dup 0< if ." -" negate then -1 swap begin dup 0 <> while 10 /mod repeat drop begin dup -1 <> while 48 + emit repeat drop else ." 0" then ;

実際の問題を解く。

今回は簡単な問題として、ABC007-A 植木算 を解きます。 この問題は入力の数値から 1 引いた数値を出力することで達成できます。

: read-number 0 0 begin swap 10 * + key 48 - dup 0 < until drop ;
dup 0 <> while 10 /mod repeat drop begin dup -1 <> while 48 + emit repeat drop else ." 0" then ;
: write-cr ( d --  ) write-pure cr ;
 
read-number
1- 
write-cr

以上で解けました。 実際の提出はこちらです。

終わりに

この記事を見た人のほとんどが「ちゃんと解説を書け」と思うことだと思います。
私も思います。ただ、どうせ丁寧に書いてもほとんどの人は斜め読みしかしないでしょうし、本当に読みたいと思う人は、自力で解読すると思ってます。
もっと言うと、これを見て自力で書いてみたいという殊勝な人は元から難解プログラミング言語にあるていど触れており、この記事に書かれているコードなら自力で作成できる人だと思ってます。
なのでそれを言い訳にあまり丁寧には書きませんでした。 マインクラフトをしていたら記事を書く時間が無くなったとか、Forth をそもそもだいぶ忘れていたとかではありせん。決して。 この記事を見て万が一気になったという人はぜひ使ってみてください。


brainfuck でも三角関数がしたい【ABC168C-: (Colon) を解く】

AtCoder Brainf*ck

初めに

この記事は普通の問題解説ではないので、普通の解説が見たい方は別の方の記事をご覧ください。


目次


概要

今回は ABC168 の C 問題の 「: (Colon)」を brainfuck で解いたので、軽い解説を書いていきます。

atcoder.jp


解法

今回はコンテスト後にトレンドにも上がった、余弦定理を使っていきます。
余弦定理は c=\sqrt{a ^ 2+b ^ 2-2ab\cos\theta} です。


時針と分針の角度を求める

少数でやるのは嫌なので、可能な限り整数で計算します。
12 時間は 720 分なので 720 で一周となるように時針と分針の角度を求めます。
時針と分針の角度は、それぞれ

\theta_h = 60 \times h + m\\ \theta_m = 12 \times m

と表せます。
また、0 時をまたぐ側が短い場合もあるので、

\theta = Min( | \theta_h - \theta_m |, 720 - | \theta_h - \theta_m |)

として角度を出します。
ここから、弧度法に直すのですが、\cos を求めるときに計算します。


三角関数 (cos) の実装

もちろん、brianfuck には三角関数を導出するような標準関数はない(そもそも関数がない)ので 自前で実装します。
具体的には、マクローリン展開を使います。
\cos のマクローリン展開は以下のようなります。

\displaystyle{\cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} ...}

ここでべき乗や階乗が出てきますが、それらの計算はめんどくさいので少し工夫をします。
上記の式を下記のように変形します。

\displaystyle{\cos x = 1 + \sum_{i = 1}^{n} (-1)^i \frac{x^2i}{2i!} = 1 + \sum_{i = 1}^{n} (-1)^i f(i)}

ここで f(i) は

\displaystyle{f(i) = f(i-1) \times \frac{x^2}{2i(2i-1)} } ( i \geq 2)

となります。
また、2i(2i-1) は、

g(i) = g(i-1) + 8i - 6

と表せます。

上記を踏まえ、\cos のマクローリン展開を書くと以下のようなコードで実現できます。

double Cos(double x, int degree)
{
    double sqX = x * x;
    double divisor = 2;  // g
    double term = sqX / 2; // f
    double ret = 1 - term;
    bool isMinus = false;
    for(int i = 2; i <= degree; i++)
    {
        term *= sqX;
        divisor += 8 * i - 6;
        term /= divisor;

        if(isMinus)
            ret -= term;
        else
            ret += term;
    }
    return ret;
}

ここで、 x そのものは使用せず、x ^ 2 のみを使用しています。
なので、 角度を弧度法に変換する際に、

\displaystyle{x = \theta \times \frac{\pi}{360}}

とするのではなく、

\displaystyle{x^2 = \theta^2 \times \left(\frac{\pi}{360} \right)^2}

とします。
\theta ^ 2 は整数で計算が可能で、 \left(\frac{\pi}{360} \right) ^ 2 は定数なので、あらかじめ計算をしておくことができ、誤差を抑えることができます。

マクローリン展開のコードは書くのはしんどいですが、見た目ほどは難しくは内容に感じます。
(それでも数時間かけて書きましたが。)


平方根を求める

余弦定理を用いた辺の長さを求めるのに必要な数値は揃ったのであとは、 c ^ 2 を求めて、平方根を出すだけで終わりです。
平方根を求めるのは、開平法をやるだけです。 brainfuck での開平法の実装方法はここでは説明しません。
個人的意見としては、除算のコードよりも楽だった印象があります。

以上で問題を解くことができます。


ところで精度は足りますか？

実はこの問題、制度が結構厳しくて 10 ^ {-9} となっています。
通常、相対誤差が重要ですが、固定少数点を使う関係上、絶対誤差の方が重要になります。
また、最終的に平方根をとるので、 少数点以下 20 桁あったほうが良いと思います。
そのため、マクローリン展開等の誤差も考えて、小数点以下 32 桁でマクローリン展開を行いました。
また、 計算上出てくる最大の数値は、4000000 なので 整数部分も 7 桁は必要になります。
それを加味して、 最終的に、整数部分 13 桁、少数部分が 32 桁の合計 45 桁で計算を行いました。
実際、マクローリン展開の計算を考えると、これでも精度が足りていない気がするのですが、実際に AC できているので良しとしましょう。
(コーディング中はずっと「精度足りない気がするなぁ」と言いながら書いてました。)


実際の提出

実際の提出はこちら


あとがき

今回は brainfuck でも三角関数の計算はできるということを見せるためにコーディングをしましたが、三角関数の実装はもうやりたくないですね。
助長な部分も多いというのもありますが、以前紹介したオセロプログラムの行数を大幅に超えました。

次は、Grid Compression について書きたいなと思ってるんですが、果たして筆は進むのか…


質問とかあれば、ここにコメントするか Twitter　でリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
それでは良い brainfuck ライフを。



自作の brainfuck の開発環境の紹介

初めに

今回は Brainf*ck Advent Calendar 2019 の 16 日目の記事です。 adventar.org

前日の記事はこちら
明日の記事はこちら

目次

概要

そんなわけで今回は、自分がどんな環境で brainfuck のコーディングをしているかを書いていきます。
自作の環境を自慢したいだけです。

機能紹介

エディタ機能

当然、開発環境ですから、エディタの機能は最低限は実装しています。
以下が実装している昨日です。
* シンタックスハイライト
* [ 入力時に、対応する ] の補完
* 対応する [,] の表示
* 自動インデント
* コードの折りたたみ
* コードスニペットの実装

シンタックスハイライト

命令の種類ごとに色分けをされています。
具体的には、
* +,- : 白
* >,< : 水色 * [,] : 赤
* ,,. : 黄色
* その他 : 緑
となっています。
(これらの色は現在暫定なので、今後変更の可能性があります。)

[ 入力時の ] の補完

[ を入力時、その直後に ] がない場合は、自動で ] が挿入されます。
また、直後が ] の場合は、] が入力されても、既に入力されている ] が上書きされ、新たに挿入されないようになっています。

対応する [,] の表示

[ または ]の直後にカーソルを合わせることで、カーソルを合わせた [,] と対応する ],[ が薄い青色でハイライトされます。

自動インデント

[ , ] に応じて自動でインデントが入ります。インデントは半角スペースが 2 文字挿入されます。
連続する [] の間にカーソルがある状態で、Enter を入力した場合、間にインデントされた空行が挿入されます。
また、] が入力された際に、対応する [ 以下のコードが自動でインデントされます。
対応する [ がない場合には、コードの初めから自動インデントが行われます。

コードの折りたたみ

対応する [,] をひとつのセクションとして、折りたたむことができます。
また、#region,#endregion をひとつのセクションとして折りたたむことができます。

コードスニペットの実装

あらかじめ登録しておいたコードをキーワードを打ち込むことで、コードに反映させることができます。
詳しい説明は後述します。

実行機能

エディタとして書くだけでなく、実行環境を整えています。
実行環境としては、現在 AtCoder で利用可能な実行環境に寄せています。
* セルは符号なし 1 byte (0 ~ 255)
* 0 に対するデクリメントは 255
* 255 に対するインクリメントは 0
* セル数上限は無し
* 負番地へのアクセスはエラー
* EOF は -1
* 対応のない [ 及び ] は構文エラー(実行前エラー)

デバッガ機能

プログラムを実行して、結果を見るだけでは、厳しいので、デバッグ機能を実装しています。
* ステップ実行
* 1 行実行
* ブレイクポイントの設置
* 現在のメモリ状況の表示
* メモリ状況の書き換え

ステップ実行

次の命令を実行して、その後動作を一時停止します。

1 行実行

別の行に移るまで命令を実行して、その後動作を一時停止します。
ループにより、実行前よりも戻った場合にも一時停止します。

ブレイクポイントの設置

特定の位置にブレイクポイントを設置して、その命令が実行される直前に動作を一時停止します。

現在のメモリ状況の表示

プログラムを一時停止した場合に、現在のポインタの位置とメモリの数値を見ることができます。
また、マウスオーバーすることにより、その数字に対応する文字と 16 進数での表記を表示します。

メモリ

一時停止中はメモリを書き換えることができます。
また、16 進数や文字での入力も可能です。

動画

文章だとわかりにくいと思ったので、動画にしました。
動画見ればわかるので、この記事の存在意義は実質皆無です。


brainf*ckのコーディング環境

あとがき

今回紹介した開発環境を試したいという方がいましたら、声かけて下されば zip ファイルを投げつけます。( Windows 以外は動作しない可能性が高いですが。)
また、質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
それでは良い、brainfuck ライフを。

brainfuck でオセロを書く（後編）

初めに

今回は Brainf*ck Advent Calendar 2019 の 13 日目の記事です。 adventar.org

前日の記事はこちら
明日の記事はこちら


目次


概要

今回は、brainfuck オセロ後編ということで、実際に盤面処理をするコードを紹介していきます。
前編がまだの方はこちらを見てください。
コードは長くなりがちなので、折りたたんでいます。


無限ループ

終了判定は行わず、無限ループで対応してます。 以下は、位置調整と無限ループの外枠のコードです。

（クリックで展開）

>>>              //Move to PlacePointer 
[-]+
[//位置の入力により石を置く（メインループ）

  /*
   * メインループのコード
   */

  [-]+//繰り返しフラグを立てる
]//End of 石を置くメインループ

次の項目から、メインループの中身について書いていきます。

入力の読み取り

概要

置きたい場所の位置の入力を受け取ります。 y 座標 x 座標 Enter(\n) の 3 文字を受け取ります。
4c の様に入力し、 それを配列にアクセスするための index に変換します。
配列の本体は 8x8 ではなく、10x10 となっているため、 index は y * 10 + x で計算されます。
また、無効な入力に対するエラーチェックは行っていません。

コード

（クリックで展開）

[-]>[-]>[-]<<                // メモリクリア
++++++[->++++++++<]>         // 一つ目の入力のオフセットを設定
>,                           // 一つ目の入力を得る
<[->-<]>                     // オフセットを引く
<<++++[->++++<]>[-<++++++>]< // 二つ目の入力のオフセットを設定
>,                           // 一つ目の入力を得る
<[->-<]>                     // オフセットを引く
>[-<<++++++++++>>]<[-<+>]<   // 番地を計算する(Add{ buf2*10_buf1 } )
>,[-]<                       // 改行コードを読み取る


_ かどうかの確認

概要

置く目標の場所が _ でなければ、コマは必然的に置けないので、その確認をしています。

コード

（クリックで展開）

// *****'_'かどうかの確認******
>[-]>[-]<<[->>+<<]>>[-<+<+>>]<<         //位置メモリのbuf0をbuf1にコピー
>[-< <<< <<< [<<<] >+< >>>[>>>]>>> > ]< //位置メモリのbuf1を始点メモリのbuf1に移動
<<< <<< [<<<]                           //始点メモリにポインタを移動
>[-<+>]<                                // buf0に値を移動

[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動
>++++++++[->++++++++++++<]>-<<          // make '_' to  buf2 (use buf1)
[->+>-<<]>[-<+>]<                       //　Cal buf2 minus val (use buf1)
>[-]>
[[-]+<]<[>]<                            // cast to Bool (1 or 0)
>[-]>-
[[+]+<]<[>]<                            // Get Not 
>>[-< <<< [<<<] >+ < >>> [>>>] < >>]<<  //始点ポインタに結果の移動
> <<< [<<<]<                            //始点ポインタに移動　　
>>                                      //置けるかどうかの判定結果が格納されているbuf2に移動
[
  [-]
  /** 置ける時の処理 **/
]


コマをひっくり返す

_ かどうかの確認しかしていませんが、以降は、実際にひっくり返してみて、ひっくり返せたコマが存在するかどうかで、実際にひっくり返せたかどうかを判断します。

サーチ方向の確保

概要

オセロはひっくり返せるかどうかの判断を 8 方向に行わないといけません。 ここで、方向を index の変化量としてとらえると、 -11,-10,-9,-1,1,9,10,11 の 8 方向になります。
しかし、正負を同一のコードで行うのは大変なため、1,9,10,11の 4 方向に対してそれぞれ正負で判定を行います。 以降は正方向のコードを例に説明していきます。

コード

（クリックで展開）

// *** 方向の値を代入
<<                                    //位置調整
>>> [>[[-]>>>]>>]
>>> >>> >>> >>>                       //方向ポインタに移動
[-]+          >                       // 　 1をセット
[-]+++++++++  >                       // 　 9をセット
[-]++++++++++ >                       // 　10をセット
[-]+++++++++++>                       // 　11をセット
// ***方向の値の代入終了
<
[
  /*** 判定ループ ***/
]


初めて相手の色が出なくなったマスに移動

概要

その方向のひっくり返す駒があるかどうかは、 相手の駒が出なくなるまで、移動を行い、 最終的なマスが、自分の色である必要があります。
加えて裁定でも一回は相手の色である必要があります。
以下のコードは、相手の駒が出なくなるまでの移動を行うコードです。
コードの説明は、めんどくさいので省略します。
コメント読んでください。

コード

（クリックで展開）

[<]<< <<< <<<                          //位置メモリに移動
>[-]>[-]<<[->>+<<]>>[-<+<+>>]<<        //位置メモリのbuf0をbuf1にコピー
>[-< <<< <<<[<<<]>+< >>>[>>>]>>> >]<   //位置メモリのbuf1を始点メモリのbuf1に移動
<<< <<< [<<<]                          //始点メモリにポインタを移動
>[-<+>]<                               // buf0に値を移動
[ - > >>> [+>>>]+ [<<<]< ]             //ターゲットの位置をセット　(初期ポインタに移動)
>>+                                    //初期ポインタのフラグ管理(buf2)に移動
[                                      //相手の色の石が出なくなるまで繰り返す
  [-]                                  //フラグ値をゼロにする
  << >>> >>>[>>>] >>> >>> >>> >>>[>]<  //方向ポインタの末尾に移動
  [->+>+<<]>>[-<<+>>]>+                //対象の方向値をコピーする
  [<<-<[<]>[<<<]<<<[<<<] >+< >>>[>>>] >>> >>> >>> >>>[>]>] //対象の方向値を開始ポインタに移動
  <<[<]>[<<<]<<<[<<<]                  //初期ポインタに移動
  >[-<+>]<                             // buf0に値を移動
  
  [ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動
  >[-]>[-]<<[->+>+<<]>[-<+>]           //ターゲットの値をbuf2にコピー
  <<< [<<<]<                           //始点ポインタに移動　
  >>> [>>>] >>> >>> >>>                //相手色ポインタに移動
  >[-]>[-]<<[->>+<<]>>[-<+<+>>]        //相手色の値をbuf1にコピー
  <[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
  <[<<<] <<< [<<<]                     //始点ポインタに移動
  >[-<+>]<                             // buf0に値を移動
  [-> >>> [>>>] > - < <<< [<<<] < ]    //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
  > >>> [>>>] >                        //ターゲットポインタのbuf2に移動
  [[-]<]<[>>]<[>>+<]                   //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
  >[ < <<< [<<<] >+< >>> [>>>] ]<[>]   //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
  <<< [<<<]                            //始点ポインタbuf1に移動
  >                                    //始点ポインタbuf2に移動
]


ストップ位置が自分の色かの判定

概要

ストップ位置が自分の色かの判定を行います。
良く見るとわかるのですが、ここ以降は、ほぼコピペ見たいなコードが複数回出てきます。

コード

（クリックで展開）

// ***ストップ位置が自分の色かの判定***
<<                                     //始点ポインタbuf0に移動　
> >>> [>>>]<                           //ターゲットの位置(buf0)に移動
>[-]>[-]<<[->+>+<<]>[-<+>]             //ターゲットの値をbuf2にコピー(buf1に移動)
<<< [<<<]<                             //始点ポインタに移動　
>>> [>>>] >>> >>>                      //自分色ポインタに移動
>[-]>[-]<<[->>+<<]>>[-<+<+>>]          //自分色の値をbuf1にコピー
<[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
<[<<<] <<< [<<<]                       //始点ポインタに移動
>[-<+>]<                               // buf0に値を移動
[-> >>> [>>>] > - < <<< [<<<] < ]      //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
> >>> [>>>] >                          //ターゲットポインタのbuf2に移動
[[-]<]<[>>]<[>>+<]                     //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
>[[-] < <<< [<<<] >+< >>> [>>>] ]<[>]  //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
<<< [<<<]                              //始点ポインタbuf1に移動

// ***End of ストップ位置が自分の色かの判定***


実際にひっくりかえせる石のフラグを立てる

概要

実際にひっくりかすのは後でやるので、ここではひっくり返すフラグを立てておきます。

コード

（クリックで展開）

>                                      //始点ポインタのbuf2に移動
[                                      //ひっくり返せるなら
  [-]                                  //フラグ値をゼロにする
  >[>>[+>>>]>] <<< [<<<] >>            //ひっくり返すフラグをインクリメント
]

<< >>> >>>[>>>] >>> >>> >>> >>>[>]<    //方向ポインタの末尾に移動
[->+>+<<]>>[-<<+>>]>+                  //対象の方向値をコピーする
[<<-<[<]>[<<<]<<<[<<<] >+< >>>[>>>] >>> >>> >>> >>>[>]>] //対象の方向値を開始ポインタに移動
<<[<]>[<<<]<<<[<<<]                    //初期ポインタに移動
>[-<+>]<                               // buf0に値を移動

[ - > >>> [->>>] <<< <<< [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動 
>
+[[-]<<<]                              //buf1のデータを初期化

>>[>>[->>>]>] <<< [<<<]>               //ひっくり返すフラグをデクリメントし正規のひっくり返る位置のみフラグを立てる
>>[>>[+>>>]>]                          //ひっくり返すフラグをインクリメントし、終点ポインタに移動

>>> >>> >>> >>> [>]<                   //方向ポインタの最終ポインタに移動

負方向の判定

概要

負方向も同様に判定します。

コード

（クリックで展開）

/**************
* 負方向の判定 *
**************/
[<]<< <<< <<<                    //位置メモリに移動
>[-]>[-]<<[->>+<<]>>[-<+<+>>]<<  //位置メモリのbuf0をbuf1にコピー
>[-< <<< <<< [<<<] >+< >>>[>>>]>>> > ]< //位置メモリのbuf1を始点メモリのbuf1に移動
<<< <<< [<<<]                          //始点メモリにポインタを移動
>[-<+>]<                               // buf0に値を移動
[ - > >>> [+>>>]+ [<<<]< ]             //ターゲットの位置をセット　(初期ポインタに移動)

>>+                                    //初期ポインタのフラグ管理(buf2)に移動
[                                     //相手の色の石が出なくなるまで繰り返す
  [-]                                 //フラグ値をゼロにする
  << >>> >>>[>>>] >>> >>> >>> >>>[>]< //方向ポインタの末尾に移動
  [->+>+<<]>>[-<<+>>]>+               //対象の方向値をコピーする
  [<<-<[<]>[<<<]<<<[<<<] >+< >>>[>>>] >>> >>> >>> >>>[>]>] //対象の方向値を開始ポインタに移動
  <<[<]>[<<<]<<<[<<<]                 //初期ポインタに移動
  >[-<+>]<                            // buf0に値を移動
  
  [ - > >>> [->>>]<<< <<< [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動
  >[-]>[-]<<[->+>+<<]>[-<+>]           //ターゲットの値をbuf2にコピー
  <<< [<<<]<                           //始点ポインタに移動　
  >>> [>>>] >>> >>> >>>                //相手色ポインタに移動
  >[-]>[-]<<[->>+<<]>>[-<+<+>>]        //相手色の値をbuf1にコピー
  <[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
  <[<<<] <<< [<<<]                     //始点ポインタに移動
  >[-<+>]<                             // buf0に値を移動
  [-> >>> [>>>] > - < <<< [<<<] < ]    //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
  > >>> [>>>] >                        //ターゲットポインタのbuf2に移動
  [[-]<]<[>>]<[>>+<]                   //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
  >[ < <<< [<<<] >+< >>> [>>>] ]<[>]   //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
  <<< [<<<]                            //始点ポインタbuf1に移動
  >                                    //始点ポインタbuf2に移動
]


// ***ストップ位置が自分の色かの判定***
<<                                     //始点ポインタbuf0に移動　
> >>> [>>>]<                           //ターゲットの位置(buf0)に移動
>[-]>[-]<<[->+>+<<]>[-<+>]             //ターゲットの値をbuf2にコピー(buf1に移動)
<<< [<<<]<                             //始点ポインタに移動　
>>> [>>>] >>> >>>                      //自分色ポインタに移動
>[-]>[-]<<[->>+<<]>>[-<+<+>>]          //自分色の値をbuf1にコピー
<[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
<[<<<] <<< [<<<]                       //始点ポインタに移動
>[-<+>]<                               // buf0に値を移動
[-> >>> [>>>] > - < <<< [<<<] < ]      //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
> >>> [>>>] >                          //ターゲットポインタのbuf2に移動
[[-]<]<[>>]<[>>+<]                     //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
>[[-] < <<< [<<<] >+< >>> [>>>] ]<[>]  //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
<<< [<<<]                              //始点ポインタbuf1に移動

// ***End of ストップ位置が自分の色かの判定***

>                                      //始点ポインタのbuf2に移動
[                                      //ひっくり返せるなら
  [-]                                  //フラグ値をゼロにする
  >[>>[+>>>]>] <<< [<<<] >>            //ひっくり返すフラグをインクリメント
]

<< > >>> [>>>]                         //ターゲットの位置に移動 
+[[-]<<<]                              //buf1のデータを初期化
>>[>>[->>>]>] <<< [<<<] >              //ひっくり返すフラグをデクリメントし正規のひっくり返る位置のみフラグを立てる
>>[>>[+>>>]>]                          //ひっくり返すフラグをインクリメントし、終点ポインタに移動

>>> >>> >>> >>> [>]<                   //方向ポインタの最終ポインタに移動

>>>[-]<<<                              //フラグに使ってたメモリをクリア
[-]<


ひっくり返す駒が存在するかどうか

概要

ひっくり返す駒にフラグを立てているので、フラグが立っている駒があるかどうかを判断します。

コード

（クリックで展開）

> <<< [<<<]                              //終点ポインタに移動
<<<
[<                                       //ひっくり返すフラグが立っている場所を探す
  [                                      //フラグが立っていれば　　　　　　　　　
    <<[<<<]                              //初期ポインタに移動
    >+                                   //buf1に結果を格納
    >                                    //調整のためbuf2に移動
  ]
<<
]　　　　　　　　　　　　　　　　         　//終点は初期ポインタ


駒をひっくり返す

概要

実際にひっくりかえせた場合は、ひっくり返します。
この時、ひっくり返せたかどうかは、後でも使用するので、もう一度再格納します。

コード

（クリックで展開）

>
[                                        //ひっくり返せるとき(buf1)
  [-]      
  < >>> [>>>]                            //終点ポインタに移動
  >>>                                    //配置位置ポインタに移動  
  >[-]>[-]<<[->>+<<]>>[-<+<+>>]<<        //位置メモリのbuf0をbuf1にコピー
  >[-< <<< <<< [<<<] >+< >>>[>>>]>>> > ]< //位置メモリのbuf1を始点メモリのbuf1に移動
  <<< <<< [<<<]                          //始点メモリにポインタを移動
  >[-<+>]<                               // buf0に値を移動
  [ - > >>> [+>>>]+ [<<<]< ]             //ターゲットの位置をセット　(初期ポインタに移動)
  > >>> [>>>]                            //ターゲット位置に移動
  > [-]+                                 //ターゲット位置のひっくり返すフラグを立てる
  <+[[-]<<<] <                           //ターゲット位置情報をクリアしつつ初期位置に戻る
  >>> [>>[<<[-]+>]>[>]< ]                //ひっくり返すフラグがある位置の色情報を1にする
  >                                      //終点ポインタに移動

  >>> >>>                                //自分の色ポインタに移動
  [->>+<<] >> [-<+<+>>]                  //buf1にコピー
  <-                                     // 値コピー用の数字を１引いておく(既に１は加算されているため)
  [-                                     //自分の色をひっくり返る位置にコピー
    < <<< <<< <<< [<<<]                  //始点ポインタに移動
    >>> [>>[<<+>]>[>]< ]                 //ひっくり返すフラグがある位置の色情報をインクリメント
    >                                    //終点ポインタに移動
  >>> >>> >                              //自分の色ポインタのbuf1に移動
    
  ]
  < <<< <<< <<< [<<<] >                  //始点ポインタBuf1に移動
  [-]
  >[-]+<                                 //buf2にひっくり返せたことを格納する
]
>[[-]<+>]<                               //buf2(ひっくり返したか)をbuf1に移動
>[-]                                     //条件分岐を合わせるためにbuf2に移動後クリア


置けた場合の処理

概要

駒を置けた場合は、盤面の再描画を行い、手番をプレーヤの石の色を入れ替えます。

コード

（クリックで展開）

[-]+                                //buf2にTrueを代入
<                                   //buf1に移動
[                                   //ひっくり返えしたとき
                                    // ****手番プレーヤーを入れ替える
　< >>> [>>>] >>> >>> >>>           //相手プレイヤーポインタに移動
  [-<<+>>]                          //手番プレイヤーポインタのbuf1にデータを移動
  <<<                               //手番プレイヤーポインタに移動
  [->>>+<<<]                        //相手プレイヤーポインタにデータを移動
  >[-<+>]                           //相手プレイヤーポインタのbuf1をbuf0に移動 
  <                                 //相手プレイヤーポインタに移動

  <<< <<< <<< <<< [<<<]             //始点ポインタに移動
  
  >>>[>[-]>[-]++++++++[-<++++>]<.[-]<.>>>]//Print Stage
  >>> [>>>] >>>>>>>                 //文字列メモリの先頭に移動
  <                                 //文字メモリの先頭のひとつ前に戻る
  <
]                                   //End of 返えしたとき


置けなかった場合の処理

概要

駒を置けなかった場合は、エラーメッセージを出します。

コード

（クリックで展開）

>
[                            //ひっくり返せなかったとき
　<< >>> [>>>]               //終点ポインタに移動
  >>> [>>>] >>>>>>>          //文字列メモリの先頭に移動
  [>]> [>]> [>]>             //3(4)文目に移動
  [.>]                       //print(can't put here)
  <[<] <[<] <[<] <[<]        //文字メモリの先頭のひとつ前に戻る
]


共通メッセージの表示

概要

置けたか置けないかにかかわず、次の入力を促すメッセージを出力します。

コード

（クリックで展開）

// ****ポインタ＝文字メモリの先頭のひとつ前
共通メッセージの描画
>[.>]                                  //Print(It's ')
<[<]<<<<<< <<< <<< . >>> >>> >>>>>>>[>]//Print(手番石)
>[.>]                                  //Print(' turn_)
>[.>]                                  //Print(Prease Input place_)
<.                                     //改行を出力
[<]<[<]<[<]
<<< <<< <<< <<< <<<                    //位置ポインタに移動


全体のコード

オセロの全体のコードを載せておきます。実際に動かしたい場合はこのコードをコピペしてください。

（クリックで展開）

>>>++++++++[->>>++++++++++++>>>++++++<<< <<<]>>>- //ptr ==2 {0}{0}{95}{32}
// **** Make '_' pattern ***
[
  -
  >>> >>> >>> >>> >>> >>> >>> >>> >>>
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //1
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //2
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //3
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //4
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //5
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //6
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //7
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //8
  
  <<< <<<
  [[<<<]<<< <<< <<<]
  <<< <<< <<< <<< <<< <<<
]
// **** End of Make '_' pattern ***
>>>
// **** Make '1'to'9' pattern ***
>>> >>> >>> >>> >>> >>> >>> >>>+//1
[>>>]>>>++//2
[>>>]>>>+++//3
[>>>]>>>++++//4
[>>>]>>>+++++//5zz
[>>>]>>>++++++//6
[>>>]>>>+++++++//7
[>>>]>>>++++++++//8
<<< <<<
[[<<<]<<<]
<<< <<< <<< <<< <<< <<<
[-
  >>> >>> >>> >>> >>> >>> >>> >>>
  [+[>>>]>>>]
  <<< <<<
  [[<<<]<<<]
  <<< <<< <<< <<< <<< <<<
]
// **** End of Make '1'to'9' pattern ***
<<< <<< <<<
// **** Make 'A'to'H' pattern***
>>>++++++++[-<<<++++++++>>>]
>>>+        //A
>>>++       //B
>>>+++      //C
>>>++++     //D
>>>+++++    //E
>>>++++++   //F
>>>+++++++  //G
>>>++++++++ //H
[<<<]<<<
[-
  >>> >>>[+>>>]
  <<<[<<<]<<<
]
// **** End of Make 'A'to'H' pattern***
// **** Make first ' '  ***
++++++++[->>>++++<<<]
// **** End of Make  first ' ' ***
>>>
// **** Make '\n' pattern (Ignore last2 line '\n'***
  >>>[<<<++++++++++[>>>]>>>]
  
// **** End of Make '\n' pattern ***
// ****Make Last Line ' ' pattern***
++++++++[-<<<++++>>>]<<<
[
  -
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+
  <<< <<< <<< <<< <<< <<< <<< <<< <<<
]
++++++++++
[>>>]++++++++++
// ****End of Make Last Line ' ' pattern***
// **** Set first stones ****
[<<<] // Back to fiest Pointer
// **set 'o' to 4D
>++++++++++[-<++++>]<++++ //Set 4D
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
> <<< [[-]<<<]< //Reset
// **set 'o' to 5E
>++++++++++[-<+++++>]<+++++ //Set 5E
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
> <<< [[-]<<<]< //Reset
// **set 'x' to 5D
>++++++++++[-<+++++>]<++++ //Set 5D
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->++++++<]>[-<+++++>]< // Set 'x'
> <<< [[-]<<<]< //Reset
// **set 'o' to 5E
>++++++++++[-<++++>]<+++++ //Set 4E
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->++++++<]>[-<+++++>]< // Set 'x'
> <<< [[-]<<<]< //Reset
>>> [ >>> ] // 末尾に移動
// **** End of Set first stones ****
>>> //位置ポインタに移動
+               //ダミーの設置
>>>             //Move to TrunPlayerStone Pointer 
// **** Set StornColor to TrunStonePointer ****
[-]++++[->++++++<]>[-<+++++>]<  // Set 'x'
>>> 
[-]++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
>>>
// **** End of Set first stones ****
// **** Set const chars ****
>>>> >>>                          //方向メモリの確保
// ************Set sering "It's '_' turn_\n\0"    (length:16) ※_の部分は0が代入されている
>>>>>>>>>>>>>>>+++++++++++++++++++
[<<<<<<<<<<<<<<<+++>++++++>++>++++++>+>++>>++>+>++++++>++++++>++++++>+++++>++>>-]
<++++++++++<++++++++<+++++++++++++++<<+++<++<+++++++++++++<+<<+<+++++++++++++<+<+<++<++++++++++++++++[>]>[>]
>
// **************Set sering "Plese input place_\n\0"(length:20)
>>>>>>>>>>>>>>>>>>>++++++++++++++++
[<<<<<<<<<<<<<<<<<<<+++++>++++++>++++++>+++++++>++++++>++>++++++>++++++>+++++++>+++++++>+++++++>++>+++++++>++++++>++++++>++++++>++++++>++>>-]
<++++++++++<++++++++++++++<+++++<+++<+<++++++++++++<<<++++<+++++<<++++++++++++++<+++++++++<<+++++<+++<+++++<++++++++++++<[>]
>
// *********************Set sering "Can't put here_\n\0"   (length:17)
>>>>>>>>>>>>>>>>++++++++++++++++
[<<<<<<<<<<<<<<<<++++>++++++>++++++>++>+++++++>++>+++++++>+++++++>+++++++>++>++++++>++++++>+++++++>++++++>++>>-]
<++++++++++<++++++++++++++<+++++<++<+++++<++++++++<<++++<+++++<<<++++<+++++++<++++++++++++++<+<+++[>]
<[<]<[<]<[<]<[<]
<< <<<<< << 
// **** End of Set const chars ****
<<< <<< <<< <<< //Move to Last pointer of field
// ************************End of setUp
// *** Print stage and text ***
[<<<] >>>[>[-]>[-]++++++++[-<++++>]<.[-]<.>>>]<<<//Print Stage
>>> >>> >>> >>> >>>
>>>>>>> 
[.>]//Print(It's ')
<[<]<<<<<< <<< <<< . >>> >>> >>>>>>>[>]//Print(手番石)
>[.>]//Print(' turn_)
>[.>]//Print(Prease Input place_)
<[<]<[<]<[<]
<<<<<< 
<<< <<< <<< <<< //Move to Last pointer of field
// *** End of Print stage and text ***
// *********************************************

// *********************************************
>>>              //Move to PlacePointer 
[-]+
[//位置の入力により石を置く（メインループ）
  [-]>[-]>[-]<<                // メモリクリア
  ++++++[->++++++++<]>         // 一つ目の入力のオフセットを設定
  >,                           // 一つ目の入力を得る
  <[->-<]>                     // オフセットを引く
  <<++++[->++++<]>[-<++++++>]< // 二つ目の入力のオフセットを設定
  >,                           // 一つ目の入力を得る
  <[->-<]>                     // オフセットを引く
  >[-<<++++++++++>>]<[-<+>]<   // 番地を計算する(Add{ buf2*10_buf1 } )
  >,[-]<                       // 改行コードを読み取る
  // ********************************************
  // *****'_'かどうかの確認******
  >[-]>[-]<<[->>+<<]>>[-<+<+>>]<<  //位置メモリのbuf0をbuf1にコピー
  >[-< <<< <<< [<<<] >+< >>>[>>>]>>> > ]< //位置メモリのbuf1を始点メモリのbuf1に移動
  <<< <<< [<<<]                          //始点メモリにポインタを移動
  >[-<+>]<                               // buf0に値を移動
  
  [ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動
  >++++++++[->++++++++++++<]>-<<          // make '_' to  buf2 (use buf1)
  [->+>-<<]>[-<+>]<                       //　Cal buf2 minus val (use buf1)
  >[-]>
  [[-]+<]<[>]<                            // cast to Bool (1 or 0)
  >[-]>-
  [[+]+<]<[>]<                            // Get Not 
  >>[-< <<< [<<<] >+ < >>> [>>>] < >>]<<  //始点ポインタに結果の移動
  > <<< [<<<]<                            //始点ポインタに移動　　
  >>                                      //置けるかどうかの判定結果が格納されているbuf2に移動
  [                                       //もし置けるのであれば
    [-]
    // *** 方向の値を代入
    <<                                    //位置調整
    >>> [>[[-]>>>]>>]
    >>> >>> >>> >>>                       //方向ポインタに移動
    [-]+          >                       // 　 1をセット
    [-]+++++++++  >                       // 　 9をセット
    [-]++++++++++ >                       // 　10をセット
    [-]+++++++++++>                       // 　11をセット
    // ***方向の値の代入終了
    <
    [                                     //すべての方向に関してのサーチ 
      /**************
      * 正方向の判定 *
      **************/
      [<]<< <<< <<<                          //位置メモリに移動
      >[-]>[-]<<[->>+<<]>>[-<+<+>>]<<        //位置メモリのbuf0をbuf1にコピー
      >[-< <<< <<<[<<<]>+< >>>[>>>]>>> >]<   //位置メモリのbuf1を始点メモリのbuf1に移動
      <<< <<< [<<<]                          //始点メモリにポインタを移動
      >[-<+>]<                               // buf0に値を移動
      [ - > >>> [+>>>]+ [<<<]< ]             //ターゲットの位置をセット　(初期ポインタに移動)
      >>+                                    //初期ポインタのフラグ管理(buf2)に移動
      [                                      //相手の色の石が出なくなるまで繰り返す
        [-]                                  //フラグ値をゼロにする
        << >>> >>>[>>>] >>> >>> >>> >>>[>]<  //方向ポインタの末尾に移動
        [->+>+<<]>>[-<<+>>]>+                //対象の方向値をコピーする
        [<<-<[<]>[<<<]<<<[<<<] >+< >>>[>>>] >>> >>> >>> >>>[>]>] //対象の方向値を開始ポインタに移動
        <<[<]>[<<<]<<<[<<<]                  //初期ポインタに移動
        >[-<+>]<                             // buf0に値を移動
        
        [ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動
        >[-]>[-]<<[->+>+<<]>[-<+>]           //ターゲットの値をbuf2にコピー
        <<< [<<<]<                           //始点ポインタに移動　
        >>> [>>>] >>> >>> >>>                //相手色ポインタに移動
        >[-]>[-]<<[->>+<<]>>[-<+<+>>]        //相手色の値をbuf1にコピー
        <[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
        <[<<<] <<< [<<<]                     //始点ポインタに移動
        >[-<+>]<                             // buf0に値を移動
        [-> >>> [>>>] > - < <<< [<<<] < ]    //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
        > >>> [>>>] >                        //ターゲットポインタのbuf2に移動
        [[-]<]<[>>]<[>>+<]                   //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
        >[ < <<< [<<<] >+< >>> [>>>] ]<[>]   //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
        <<< [<<<]                            //始点ポインタbuf1に移動
        >                                    //始点ポインタbuf2に移動
      ]
  
  
      // ***ストップ位置が自分の色かの判定***
      <<                                     //始点ポインタbuf0に移動　
      > >>> [>>>]<                           //ターゲットの位置(buf0)に移動
      >[-]>[-]<<[->+>+<<]>[-<+>]             //ターゲットの値をbuf2にコピー(buf1に移動)
      <<< [<<<]<                             //始点ポインタに移動　
      >>> [>>>] >>> >>>                      //自分色ポインタに移動
      >[-]>[-]<<[->>+<<]>>[-<+<+>>]          //自分色の値をbuf1にコピー
      <[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
      <[<<<] <<< [<<<]                       //始点ポインタに移動
      >[-<+>]<                               // buf0に値を移動
      [-> >>> [>>>] > - < <<< [<<<] < ]      //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
      > >>> [>>>] >                          //ターゲットポインタのbuf2に移動
      [[-]<]<[>>]<[>>+<]                     //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
      >[[-] < <<< [<<<] >+< >>> [>>>] ]<[>]  //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
      <<< [<<<]                              //始点ポインタbuf1に移動
      
      // ***End of ストップ位置が自分の色かの判定***
  
      >                                      //始点ポインタのbuf2に移動
      [                                      //ひっくり返せるなら
        [-]                                  //フラグ値をゼロにする
        >[>>[+>>>]>] <<< [<<<] >>            //ひっくり返すフラグをインクリメント
      ]
  
      << >>> >>>[>>>] >>> >>> >>> >>>[>]<    //方向ポインタの末尾に移動
      [->+>+<<]>>[-<<+>>]>+                  //対象の方向値をコピーする
      [<<-<[<]>[<<<]<<<[<<<] >+< >>>[>>>] >>> >>> >>> >>>[>]>] //対象の方向値を開始ポインタに移動
      <<[<]>[<<<]<<<[<<<]                    //初期ポインタに移動
      >[-<+>]<                               // buf0に値を移動
     
      [ - > >>> [->>>] <<< <<< [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動 
      >
      +[[-]<<<]                              //buf1のデータを初期化
      
      >>[>>[->>>]>] <<< [<<<]>               //ひっくり返すフラグをデクリメントし正規のひっくり返る位置のみフラグを立てる
      >>[>>[+>>>]>]                          //ひっくり返すフラグをインクリメントし、終点ポインタに移動
  
      >>> >>> >>> >>> [>]<                   //方向ポインタの最終ポインタに移動
  
  
      /**************
      * 負方向の判定 *
      **************/
      [<]<< <<< <<<                    //位置メモリに移動
      >[-]>[-]<<[->>+<<]>>[-<+<+>>]<<  //位置メモリのbuf0をbuf1にコピー
      >[-< <<< <<< [<<<] >+< >>>[>>>]>>> > ]< //位置メモリのbuf1を始点メモリのbuf1に移動
      <<< <<< [<<<]                          //始点メモリにポインタを移動
      >[-<+>]<                               // buf0に値を移動
      [ - > >>> [+>>>]+ [<<<]< ]             //ターゲットの位置をセット　(初期ポインタに移動)
  
      >>+                                    //初期ポインタのフラグ管理(buf2)に移動
      [                                     //相手の色の石が出なくなるまで繰り返す
        [-]                                 //フラグ値をゼロにする
        << >>> >>>[>>>] >>> >>> >>> >>>[>]< //方向ポインタの末尾に移動
        [->+>+<<]>>[-<<+>>]>+               //対象の方向値をコピーする
        [<<-<[<]>[<<<]<<<[<<<] >+< >>>[>>>] >>> >>> >>> >>>[>]>] //対象の方向値を開始ポインタに移動
        <<[<]>[<<<]<<<[<<<]                 //初期ポインタに移動
        >[-<+>]<                            // buf0に値を移動
        
        [ - > >>> [->>>]<<< <<< [<<<]< ] > >>> [>>>]< //ターゲットの位置に移動
        >[-]>[-]<<[->+>+<<]>[-<+>]           //ターゲットの値をbuf2にコピー
        <<< [<<<]<                           //始点ポインタに移動　
        >>> [>>>] >>> >>> >>>                //相手色ポインタに移動
        >[-]>[-]<<[->>+<<]>>[-<+<+>>]        //相手色の値をbuf1にコピー
        <[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
        <[<<<] <<< [<<<]                     //始点ポインタに移動
        >[-<+>]<                             // buf0に値を移動
        [-> >>> [>>>] > - < <<< [<<<] < ]    //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
        > >>> [>>>] >                        //ターゲットポインタのbuf2に移動
        [[-]<]<[>>]<[>>+<]                   //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
        >[ < <<< [<<<] >+< >>> [>>>] ]<[>]   //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
        <<< [<<<]                            //始点ポインタbuf1に移動
        >                                    //始点ポインタbuf2に移動
      ]
  
  
      // ***ストップ位置が自分の色かの判定***
      <<                                     //始点ポインタbuf0に移動　
      > >>> [>>>]<                           //ターゲットの位置(buf0)に移動
      >[-]>[-]<<[->+>+<<]>[-<+>]             //ターゲットの値をbuf2にコピー(buf1に移動)
      <<< [<<<]<                             //始点ポインタに移動　
      >>> [>>>] >>> >>>                      //自分色ポインタに移動
      >[-]>[-]<<[->>+<<]>>[-<+<+>>]          //自分色の値をbuf1にコピー
      <[-<[<<<] <<< [<<<] >+< >>> [>>>] >>> >>> >] //相手色の値を始点ポインタのbuf1に移動
      <[<<<] <<< [<<<]                       //始点ポインタに移動
      >[-<+>]<                               // buf0に値を移動
      [-> >>> [>>>] > - < <<< [<<<] < ]      //相手色とターゲットマスの色の差をターゲットポインタのbuf2に格納
      > >>> [>>>] >                          //ターゲットポインタのbuf2に移動
      [[-]<]<[>>]<[>>+<]                     //Notをとる(buf0がTrueでbuf1がfalseであることを利用)(buf1に移動する)
      >[[-] < <<< [<<<] >+< >>> [>>>] ]<[>]  //演算結果を始点ポインタのbuf2にコピー(buf1に移動)
      <<< [<<<]                              //始点ポインタbuf1に移動
      
      // ***End of ストップ位置が自分の色かの判定***
  
      >                                      //始点ポインタのbuf2に移動
      [                                      //ひっくり返せるなら
        [-]                                  //フラグ値をゼロにする
        >[>>[+>>>]>] <<< [<<<] >>            //ひっくり返すフラグをインクリメント
      ]
  
      << > >>> [>>>]                         //ターゲットの位置に移動 
      +[[-]<<<]                              //buf1のデータを初期化
      >>[>>[->>>]>] <<< [<<<] >              //ひっくり返すフラグをデクリメントし正規のひっくり返る位置のみフラグを立てる
      >>[>>[+>>>]>]                          //ひっくり返すフラグをインクリメントし、終点ポインタに移動
     
      >>> >>> >>> >>> [>]<                   //方向ポインタの最終ポインタに移動
      
      >>>[-]<<<                              //フラグに使ってたメモリをクリア
      [-]<
  
    ]//End of すべての方向へのサーチ
    > <<< [<<<]                              //終点ポインタに移動
    <<<
    [<                                       //ひっくり返すフラグが立っている場所を探す
      [                                      //フラグが立っていれば　　　　　　　　　
        <<[<<<]                              //初期ポインタに移動
        >+                                   //buf1に結果を格納
        >                                    //調整のためbuf2に移動
      ]
    <<
    ]　　　　　　　　　　　　　　　　         　//終点は初期ポインタ
    >
    [                                        //ひっくり返せるとき(buf1)
      [-]      
      < >>> [>>>]                            //終点ポインタに移動
      >>>                                    //配置位置ポインタに移動  
      >[-]>[-]<<[->>+<<]>>[-<+<+>>]<<        //位置メモリのbuf0をbuf1にコピー
      >[-< <<< <<< [<<<] >+< >>>[>>>]>>> > ]< //位置メモリのbuf1を始点メモリのbuf1に移動
      <<< <<< [<<<]                          //始点メモリにポインタを移動
      >[-<+>]<                               // buf0に値を移動
      [ - > >>> [+>>>]+ [<<<]< ]             //ターゲットの位置をセット　(初期ポインタに移動)
      > >>> [>>>]                            //ターゲット位置に移動
      > [-]+                                //ターゲット位置のひっくり返すフラグを立てる
      <+[[-]<<<] <                          //ターゲット位置情報をクリアしつつ初期位置に戻る
      >>> [>>[<<[-]+>]>[>]< ]               //ひっくり返すフラグがある位置の色情報を1にする
      >                                     //終点ポインタに移動
  
      >>> >>>                               //自分の色ポインタに移動
      [->>+<<] >> [-<+<+>>]                 //buf1にコピー
      <-                                    // 値コピー用の数字を１引いておく(既に１は加算されているため)
      [-                                    //自分の色をひっくり返る位置にコピー
        < <<< <<< <<< [<<<]                   //始点ポインタに移動
        >>> [>>[<<+>]>[>]< ]               //ひっくり返すフラグがある位置の色情報をインクリメント
        >                                     //終点ポインタに移動
      >>> >>> >                                //自分の色ポインタのbuf1に移動
        
      ]
      < <<< <<< <<< [<<<] > //始点ポインタBuf1に移動
      [-]
      >[-]+<//buf2にひっくり返せたことを格納する
    ]
    >[[-]<+>]<//buf2(ひっくり返したか)をbuf1に移動
    >[-]//条件分岐を合わせるためにbuf2に移動後クリア
  ]//End of 
  [-]+//buf2にTrueを代入
  <//buf1に移動
  [//ひっくり返えしたとき
    // ****手番プレーヤーを入れ替える
  　< >>> [>>>] >>> >>> >>> //相手プレイヤーポインタに移動
    [-<<+>>]//手番プレイヤーポインタのbuf1にデータを移動
    <<< //手番プレイヤーポインタに移動
    [->>>+<<<] //相手プレイヤーポインタにデータを移動
    >[-<+>]    //相手プレイヤーポインタのbuf1をbuf0に移動 
    <          //相手プレイヤーポインタに移動
  
    <<< <<< <<< <<< [<<<] //始点ポインタに移動
    
    //盤面の再描画
  
    >>>[>[-]>[-]++++++++[-<++++>]<.[-]<.>>>]//Print Stage
    //終点ポインタに移動している
    
    >>> [>>>] >>>>>>> //文字列メモリの先頭に移動
    <//文字メモリの先頭のひとつ前に戻る
    <
  ]//End of 返えしたとき 
  >
  [//ひっくり返せなかったとき
  　<< >>> [>>>] //終点ポインタに移動
    >>> [>>>] >>>>>>> //文字列メモリの先頭に移動
    [>]> [>]> [>]> //3(4)文目に移動
    [.>]//print(can't put here)
    <[<] <[<] <[<] <[<] //文字メモリの先頭のひとつ前に戻る
  ]
  // ****ポインタ＝文字メモリの先頭のひとつ前
  共通メッセージの描画
  >[.>]//Print(It's ')
  <[<]<<<<<< <<< <<< . >>> >>> >>>>>>>[>]//Print(手番石)
  >[.>]//Print(' turn_)
  >[.>]//Print(Prease Input place_)
  <.   //改行を出力
  [<]<[<]<[<]
  <<< <<< <<< <<< <<< //位置ポインタに移動
  [-]//位置ポインタの値を初期化
  +//繰り返しフラグを立てる
]//End of 石を置くメインループ


あとがき

途中から説明を放棄していますが、どこまで詳しく説明すればいいのかわからないのと、実際に動かしたほうが理解が早いと思ってるので、省略しました。
実はこのコードは数年前に書いたコードなので、自分でもわからないというのも大きいです。
また、結構助長な部分と蚊もありますが、これだけの規模なので、実行速度よりも、可読性と取っています。
あと、純粋に、当時の自分があまり brainfuck をきれいに書けなかったのもあると思います。
それでも、ここまでコメントを残していたのはいい点だとほめたいですね。


質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
それでは良い、brainfuck ライフを。

brainfuck でオセロを書く(前編)

初めに

今回は Brainf*ck Advent Calendar 2019 の 10 日目の記事です。 adventar.org

前日の記事はこちら
明日の記事はこちら


目次


概要

今回、カレンダーが空いていたので適当な記事で埋めました。
本当は、最後まで書こうと思ったのですが、
記事が長くなりそうなのと、疲れてきたのと、時間がないのとで、今回は前編ということで、
初期セットアップと盤面の表示のコードだけ書いて逃げようと思います。

続きは明日かもしくはもっと先に公開する予定です。


メモリ配置

コードの説明に入る前に、どういうメモリの取り方をしているかを説明します。

盤面情報

盤面を管理するために 配列を用いて管理します。また、ランダムアクセスをすることを考慮しないといけません。
ランダムアクセスに関しては、以前記事を書きました。
今回は、アクセスの速さと一時メモリの確保も兼ねて、1 要素 3 セルで要素を確保しています。
今回は、盤面の状態として、黒を x 白を o 何も置かれてない状態を _ とすることにします。

また、出力のことや、境界値判定のことも考えて、メモリに以下のように配置することにします。

 * A B C D E F G H 
 1 _ _ _ _ _ _ _ _ 
 2 _ _ _ _ _ _ _ _ 
 3 _ _ _ _ _ _ _ _ 
 4 _ _ _ _ _ _ _ _ 
 5 _ _ _ _ _ _ _ _ 
 6 _ _ _ _ _ _ _ _ 
 7 _ _ _ _ _ _ _ _ 
 8 _ _ _ _ _ _ _ _

2 次元として表現していますが、実際には、1 次元的に格納しています。
また、終端には改行文字も入れています。
また、文字としては書かれませんが、8 の行の次にスペースで構成されたメモリ配列が取られています。
また、配列の前後には、3 セルの空白が挿入されています。

入力情報および石情報

盤面の直後に入力情報と石情報が配置されています。
入力情報は入力直後に、盤面位置のインデックスに変換されます。
その続きに、ターンプレイヤーの石、非ターンプレイヤーの石と続きます。
先手手番か後手手番かの判断は、ターンプレイヤーの石と非ターンプレイヤーの石を入れ替える形で行っています。

固定文字列

入力情報と石情報のあとに、空白セルが　6 セルあり、 そのあとに、繰り返し登場する固定文字列がメモリに展開されています。
具体的には

  • It's _ turn.
  • Plese input place.
  • Can't put here.
    の三つです。

メモリ図

メモリの配置を簡単に示すと以下のようになっています。

_{...field...}_{index}{myStone}{enemyStone}__{texts}

field は盤面情報、
index は位置情報、
myStone は手番プレイヤーの石、
enemyStone は相手プレイヤーの石、
texts は固定文字列です。

texts 以外の情報は、 3 セルを 1 セットとして、データ格納に用いています。3 セルのうちの 2 セルは、配列のランダムアクセスや、計算時の一時メモリとして使われます。


初期セットアップ

フィールドの作成

コード

上記のメモリをコードに表現するのコードを以下に列挙します。

これで、盤面の周囲全てに何かしらの値が入っていることになり、境界値判定が容易になります。 （厳密には、境界値判定ではなく、ポインタの移動のしやすさです。）

_ のセット

（クリックで展開）

>>>++++++++[->>>++++++++++++>>>++++++<<< <<<]>>>- //ptr ==2 {0}{0}{95}{48}
// **** Make '_' pattern ***
[
  -
  >>> >>> >>> >>> >>> >>> >>> >>> >>>
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //1
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //2
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //3
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //4
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //5
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //6
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //7
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //8
  
  <<< <<<
  [[<<<]<<< <<< <<<]
  <<< <<< <<< <<< <<< <<<
]
// **** End of Make '_' pattern ***

1 ~ 9 のセット

（クリックで展開）

>>>
// **** Make '1'to'9' pattern ***
>>> >>> >>> >>> >>> >>> >>> >>>+//1
[>>>]>>>++//2
[>>>]>>>+++//3
[>>>]>>>++++//4
[>>>]>>>+++++//5zz
[>>>]>>>++++++//6
[>>>]>>>+++++++//7
[>>>]>>>++++++++//8
<<< <<<
[[<<<]<<<]
<<< <<< <<< <<< <<< <<<
[-
  >>> >>> >>> >>> >>> >>> >>> >>>
  [+[>>>]>>>]
  <<< <<<
  [[<<<]<<<]
  <<< <<< <<< <<< <<< <<<
]
// **** End of Make '1'to'9' pattern ***

A~H のセット

（クリックで展開）

<<< <<< <<<
// **** Make 'A'to'H' pattern***
>>>++++++++[-<<<++++++++>>>]
>>>+        //A
>>>++       //B
>>>+++      //C
>>>++++     //D
>>>+++++    //E
>>>++++++   //F
>>>+++++++  //G
>>>++++++++ //H
[<<<]<<<
[-
  >>> >>>[+>>>]
  <<<[<<<]<<<
]
// **** End of Make 'A'to'H' pattern***

* および \n のセット

（クリックで展開）

++++++++[->>>++++<<<]
// **** End of Make  first ' ' ***
>>>
// **** Make '\n' pattern (Ignore last2 line '\n'***
  >>>[<<<++++++++++[>>>]>>>]
  
// **** End of Make '\n' pattern ***

最終行のスペースのセット

（クリックで展開）

// ****Make Last Line ' ' pattern***
++++++++[-<<<++++>>>]<<<
[
  -
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+
  <<< <<< <<< <<< <<< <<< <<< <<< <<<
]
++++++++++
[>>>]++++++++++

// ****End of Make Last Line ' ' pattern***


初期石の配置

オセロに必要な初期石を配置します。 ここでも、配列のランダムアクセスを利用しています。 (固定値なので、ランダムアクセスする意味が薄いですが。)

コード（クリックで展開）

// **** Set first stones ****
[<<<] // Back to fiest Pointer
// **set 'o' to 4D
>++++++++++[-<++++>]<++++ //Set 4D
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
> <<< [[-]<<<]< //Reset
// **set 'o' to 5E
>++++++++++[-<+++++>]<+++++ //Set 5E
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
> <<< [[-]<<<]< //Reset
// **set 'x' to 5D
>++++++++++[-<+++++>]<++++ //Set 5D
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->++++++<]>[-<+++++>]< // Set 'x'
> <<< [[-]<<<]< //Reset
// **set 'o' to 5E
>++++++++++[-<++++>]<+++++ //Set 4E
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->++++++<]>[-<+++++>]< // Set 'x'
> <<< [[-]<<<]< //Reset
>>> [ >>> ] // 末尾に移動
// **** End of Set first stones ****

手番石変数の初期化

コード（クリックで展開）

// **** End of Set first stones ****
>>> //位置ポインタに移動
+               //ダミーの設置
>>>             //Move to TrunPlayerStone Pointer 
// **** Set StornColor to TrunStonePointer ****
[-]++++[->++++++<]>[-<+++++>]<  // Set 'x'
>>> 
[-]++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
>>>
// **** End of Set first stones ****

位置ポインタはランダムアクセスの位置を示す index を入れるメモリです。
今後位置ポインタは常に値が入ってる前提となるので、一度ダミーとして 1 を入れています。

文字列の初期化

コード（クリックで展開）

// **** Set const chars ****
>>>> >>>                          //方向メモリの確保
// ************Set sering "It's '_' turn_\n\0"    (length:16) ※_の部分は0が代入されている
>>>>>>>>>>>>>>>+++++++++++++++++++
[<<<<<<<<<<<<<<<+++>++++++>++>++++++>+>++>>++>+>++++++>++++++>++++++>+++++>++>>-]
<++++++++++<++++++++<+++++++++++++++<<+++<++<+++++++++++++<+<<+<+++++++++++++<+<+<++<++++++++++++++++[>]>[>]
>
// **************Set sering "Plese input place_\n\0"(length:20)
>>>>>>>>>>>>>>>>>>>++++++++++++++++
[<<<<<<<<<<<<<<<<<<<+++++>++++++>++++++>+++++++>++++++>++>++++++>++++++>+++++++>+++++++>+++++++>++>+++++++>++++++>++++++>++++++>++++++>++>>-]
<++++++++++<++++++++++++++<+++++<+++<+<++++++++++++<<<++++<+++++<<++++++++++++++<+++++++++<<+++++<+++<+++++<++++++++++++<[>]
>
// *********************Set sering "Can't put here_\n\0"   (length:17)
>>>>>>>>>>>>>>>>++++++++++++++++
[<<<<<<<<<<<<<<<<++++>++++++>++++++>++>+++++++>++>+++++++>+++++++>+++++++>++>++++++>++++++>+++++++>++++++>++>>-]
<++++++++++<++++++++++++++<+++++<++<+++++<++++++++<<++++<+++++<<<++++<+++++++<++++++++++++++<+<+++[>]
<[<]<[<]<[<]<[<]
<< <<<<< << 
// **** End of Set const chars ****
<<< <<< <<< <<< //Move to Last pointer of field


盤面の表示

盤面のメモリを、表示し易いように調整しているので、盤面表示は特に難しくはないです。
しかし、そのままだと、縦長になるので、各文字の前にスペースを入れることで調整しています。
ついでに、テキストも出力しています。

コード（クリックで展開）

// *** Print stage and text ***
[<<<] >>>[>[-]>[-]++++++++[-<++++>]<.[-]<.>>>]<<<//Print Stage
>>> >>> >>> >>> >>>
>>>>>>> 
[.>]//Print(It's ')
<[<]<<<<<< <<< <<< . >>> >>> >>>>>>>[>]//Print(手番石)
>[.>]//Print(' turn_)
>[.>]//Print(Prease Input place_)
<[<]<[<]<[<]
<<<<<< 
<<< <<< <<< <<< //Move to Last pointer of field
// *** End of Print stage and text ***

この時の出力結果はこのようになります。

 * A B C D E F G H 
 1 _ _ _ _ _ _ _ _ 
 2 _ _ _ _ _ _ _ _ 
 3 _ _ _ _ _ _ _ _ 
 4 _ _ _ o x _ _ _ 
 5 _ _ _ x o _ _ _ 
 6 _ _ _ _ _ _ _ _ 
 7 _ _ _ _ _ _ _ _ 
 8 _ _ _ _ _ _ _ _ 
                   
It's 'x' turn.
Plese input place.

実は、盤面出力よりも、文字出力の方が、圧倒的に面倒です。


つづき

後編が上がったらここにリンクを張っておきます。


コード

今回書いたコードをひと続きにしたものを張っておきます。 気になる方はコピペして走らせてみてください。

コード（クリックで展開）

>>>++++++++[->>>++++++++++++>>>++++++<<< <<<]>>>- //ptr ==2 {0}{0}{95}{32}
// **** Make '_' pattern ***
[
  -
  >>> >>> >>> >>> >>> >>> >>> >>> >>>
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //1
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //2
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //3
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //4
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //5
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //6
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //7
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>> >>>   //8
  
  <<< <<<
  [[<<<]<<< <<< <<<]
  <<< <<< <<< <<< <<< <<<
]
// **** End of Make '_' pattern ***
>>>
// **** Make '1'to'9' pattern ***
>>> >>> >>> >>> >>> >>> >>> >>>+//1
[>>>]>>>++//2
[>>>]>>>+++//3
[>>>]>>>++++//4
[>>>]>>>+++++//5zz
[>>>]>>>++++++//6
[>>>]>>>+++++++//7
[>>>]>>>++++++++//8
<<< <<<
[[<<<]<<<]
<<< <<< <<< <<< <<< <<<
[-
  >>> >>> >>> >>> >>> >>> >>> >>>
  [+[>>>]>>>]
  <<< <<<
  [[<<<]<<<]
  <<< <<< <<< <<< <<< <<<
]
// **** End of Make '1'to'9' pattern ***
<<< <<< <<<
// **** Make 'A'to'H' pattern***
>>>++++++++[-<<<++++++++>>>]
>>>+        //A
>>>++       //B
>>>+++      //C
>>>++++     //D
>>>+++++    //E
>>>++++++   //F
>>>+++++++  //G
>>>++++++++ //H
[<<<]<<<
[-
  >>> >>>[+>>>]
  <<<[<<<]<<<
]
// **** End of Make 'A'to'H' pattern***
// **** Make first ' '  ***
++++++++[->>>++++<<<]
// **** End of Make  first ' ' ***
>>>
// **** Make '\n' pattern (Ignore last2 line '\n'***
  >>>[<<<++++++++++[>>>]>>>]
  
// **** End of Make '\n' pattern ***
// ****Make Last Line ' ' pattern***
++++++++[-<<<++++>>>]<<<
[
  -
  >>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+
  <<< <<< <<< <<< <<< <<< <<< <<< <<<
]
++++++++++
[>>>]++++++++++

// ****End of Make Last Line ' ' pattern***

// **** Set first stones ****
[<<<] // Back to fiest Pointer
// **set 'o' to 4D
>++++++++++[-<++++>]<++++ //Set 4D
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
> <<< [[-]<<<]< //Reset
// **set 'o' to 5E
>++++++++++[-<+++++>]<+++++ //Set 5E
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
> <<< [[-]<<<]< //Reset
// **set 'x' to 5D
>++++++++++[-<+++++>]<++++ //Set 5D
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->++++++<]>[-<+++++>]< // Set 'x'
> <<< [[-]<<<]< //Reset
// **set 'o' to 5E
>++++++++++[-<++++>]<+++++ //Set 4E
[ - > >>> [+>>>]+ [<<<]< ] > >>> [>>>]<
[-]//Zero Zet
++++[->++++++<]>[-<+++++>]< // Set 'x'
> <<< [[-]<<<]< //Reset
>>> [ >>> ] // 末尾に移動
// **** End of Set first stones ****
>>> //位置ポインタに移動
+               //ダミーの設置
>>>             //Move to TrunPlayerStone Pointer 
// **** Set StornColor to TrunStonePointer ****
[-]++++[->++++++<]>[-<+++++>]<  // Set 'x'
>>> 
[-]++++[->+++++<]>++[-<+++++>]<+ // Set 'o'
>>>
// **** End of Set first stones ****
// **** Set const chars ****
>>>> >>>                          //方向メモリの確保
// ************Set sering "It's '_' turn_\n\0"    (length:16) ※_の部分は0が代入されている
>>>>>>>>>>>>>>>+++++++++++++++++++
[<<<<<<<<<<<<<<<+++>++++++>++>++++++>+>++>>++>+>++++++>++++++>++++++>+++++>++>>-]
<++++++++++<++++++++<+++++++++++++++<<+++<++<+++++++++++++<+<<+<+++++++++++++<+<+<++<++++++++++++++++[>]>[>]
>
// **************Set sering "Plese input place_\n\0"(length:20)
>>>>>>>>>>>>>>>>>>>++++++++++++++++
[<<<<<<<<<<<<<<<<<<<+++++>++++++>++++++>+++++++>++++++>++>++++++>++++++>+++++++>+++++++>+++++++>++>+++++++>++++++>++++++>++++++>++++++>++>>-]
<++++++++++<++++++++++++++<+++++<+++<+<++++++++++++<<<++++<+++++<<++++++++++++++<+++++++++<<+++++<+++<+++++<++++++++++++<[>]
>
// *********************Set sering "Can't put here_\n\0"   (length:17)
>>>>>>>>>>>>>>>>++++++++++++++++
[<<<<<<<<<<<<<<<<++++>++++++>++++++>++>+++++++>++>+++++++>+++++++>+++++++>++>++++++>++++++>+++++++>++++++>++>>-]
<++++++++++<++++++++++++++<+++++<++<+++++<++++++++<<++++<+++++<<<++++<+++++++<++++++++++++++<+<+++[>]
<[<]<[<]<[<]<[<]
<< <<<<< << 
// **** End of Set const chars ****
<<< <<< <<< <<< //Move to Last pointer of field
// ************************End of setUp
// *** Print stage and text ***
[<<<] >>>[>[-]>[-]++++++++[-<++++>]<.[-]<.>>>]<<<//Print Stage
>>> >>> >>> >>> >>>
>>>>>>> 
[.>]//Print(It's ')
<[<]<<<<<< <<< <<< . >>> >>> >>>>>>>[>]//Print(手番石)
>[.>]//Print(' turn_)
>[.>]//Print(Prease Input place_)
<[<]<[<]<[<]
<<<<<< 
<<< <<< <<< <<< //Move to Last pointer of field
// *** End of Print stage and text ***
// *********************************************

あとがき

brainfuck でオセロを書く人なんて、自分以外にいるんですかね…

質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
それでは良い、brainfuck ライフを。

brainfuck 閑話 : 配列のランダムアクセス

AtCoder Brainf*ck brainfuck入門

初めに

今回は Brainf*ck Advent Calendar 2019 の 7 日目の記事です。 adventar.org
前日の記事はこちら
明日の記事はこちら

目次

概要

今回は、配列のランダムアクセスの話をしたいと思います。
適当に思いついた 4 つの方法で計算量の観点から解説したいと思います。

配列の表現方法

brainfuck で配列を表現する場合、配列の両端に 0 を入れることで終端を表現します。
c++で char[] を用いて文字列を表現するときに終端に \0 が入るようなものと思えば理解できるのではないでしょうか。
また、その性質上、数値が配列要素の値が 0 であってはいけないです。

本記事での制約

今回は、要素は 1~100 として、要素数も 100 以下として話をします。

コードとメモリ遷移

ランダムアクセスのコードと、その実行例での、メモリの遷移を書いていきます。
実行例として 11,22,33,44,55 の要素を持つ配列の 3 番目の要素にアクセスするという入力を与えています。
また、メモリ遷移は、メインループの前後と、最終的なメモリを示しました。

方法１

コード

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

メモリ遷移
f:id:unidentifiedexe:20191207010717j:plain

方法２

コード

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

メモリ遷移
f:id:unidentifiedexe:20191207010812j:plain

方法３

コード

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

メモリ遷移
f:id:unidentifiedexe:20191207010827j:plain

方法４

コード

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

メモリ遷移
f:id:unidentifiedexe:20191207010848j:plain

ざっくり解説

それぞれの方法は、 1 要素のセル数とインデックスメモリが固定かどうかが異なります。
各方法の内容は以下の表のとおりです。

1要素のセル数 インデックス
方法 1 1 固定
方法 2 1 非固定
方法 3 2 固定
方法 4 2 非固定

計算量

それぞれの方法に関して、空間計算量、時間計算量の観点から利点欠点を見ていきます。

空間計算量

1 要素のセル数が多い方法 2,3 が空間計算量的に悪いです。
わざわざ書くものでもないですね。
インデックスの固定・非固定に関しては、非固定の方が若干良かったりしますが、誤差程度なので無いものとしてよさそうです。

時間計算量

brainfuck における時間計算量をどう定義するかですが、計算ステップ数とします。
実際には、インクリメントより条件分岐の方が早い等ありそうですが、今回は無視します。
方法 1,2 では 1 要素 1 セルであるために、インデックス指定をひとつ動かすたびに値の移動を行っているために、すごく遅くなっています。
一方で、方法 3,4 では移動が発生しないために、遅いです。

方法 3,4 の i 番目へのインデックスアクセスの計算ステップ数は以下のようになります。
確認していないので間違ってたらごめんなさい。

計算ステップ数
方法 3 3*i^2 + 9*i + 4
方法 4 7/2*i^2 - 1/2*i + 2

諸条件によって変わってきますが、要素数が多いほど、方法 3 がいいということになります。
といっても、方法 1,2 に比べるとどっちも変わらないので、好きな方を使ったら良いと思います。

結局どうすればいいの？

正直、よほど気にしない限りはどの方法でもいいかと思います。
空間計算量は普段はあまり気にしませんが、brainfuck ではデバッグのしやすさにも影響するので、一概に方法 1,2 が悪いとも言えません。
私はよく、方法 1 を使っています。

まとめ

配列のランダムアクセスをする場合、1 要素に 2 セルを使うと、時間計算量が大幅に削減できる。

あとがき

今回の記事は brainfuck のコードが登場しまた。
お叱りを回避できそうです。
それでは皆さん、良い brainfuck ライフを。

brianfuckの小手先のテクニックで変数を削減

AtCoder Brainf*ck 競プロ

初めに

今回は Brainf*ck Advent Calendar 2019 の 6 日目の記事です。 adventar.org

前日の記事はこちら
明日の記事はこちら
誘ってくださった主催者さんには感謝しています。

目次

概要

多くの人が brainfuck のコードを書く場合、直接コードを考えるのではなく、一旦別言語で頭の中で考えてから書くと思います。
コード量が多い場合はその傾向が強いと思います。
その過程で、一般的なプログラミング言語での書き方と変えてしまったほうがいい、ということがしばしばあります。
今回はその中の一つである ループ構造の逆転 (と自分が勝手に呼んでいるもの) について、AtCoder の問題を例に挙げて解説していきます。

ループ構造の逆転

問題

今回使用する問題は、ABC066 の ss です。

atcoder.jp

正直、この問題はそもそも brainfuck で解いているのが自分だけなこともあり、説明に向いてない気もするのですが、 ぱっと思いついた問題がこれだったので、この問題を使用します。

解答コード

とりあえず、AC できる回答のコードを記載します。(提出のリンクはこちら)

int main(){
    string s;
    cin >> s;
    int n = (s.size()-1) /2;
    for(int len = n; len > 0; len--){
        bool isSame = true;
        for(int i = 0; i < len; i++){
            if(s.at(i) != s.at(len + i)){
                isSame = false;
                break;
            }
        }
        if(isSame){
            cout << len*2 << endl;
            break;
        }
    }
}

解説

やってることは単純で、 分割後の長さを len として それを |s|-1 の半分を初期値としてループをします。
その中で、s[i] と s[len+i] の等価比較を行って、すべて同じなら、len を出力して終了、異なる場合は、 len のループを継続となります。
必ず存在するように問題が与えられるので、存在しない場合のケアはしていません。

二つのループ

さて、先ほどのコードには len のループと index (i) の ループが登場しました。 多くの人は、len のループの中に index のループを書くと思います。
もっとも、多くの言語では、文字列切り出しと文字列の同値判定ができるので 1 重で済みますが。

brainfuck での実装の検討

先ほどのコードを brainfuck での実装します。 brainfuck で配列に対する処理に関しては割愛します。 この時に、上記コードでいう isSame フラグを管理する必要が出てきます。しかし、このフラグを管理するのは少し面倒です。brainfuck では変数が一つ増えるだけで、結構めんどくさくなります。 実際そこまでめんどくさくはないですが、それを言うと話が進まないので納得してください。 そこで今回は一時変数を削除するためのちょっとしたテクニックとしてループ構造の逆転を紹介します。

ループ構造が逆転したコード

説明するよりも、実際に見てもらったほうが分かり安いと思うので、コードを記します。

int main(){
    string s;
    cin >> s;
    int n = (s.size()-1) /2;
    len = n;
    for(int i = 0; i < len; i++){
        if(s.at(i) != s.at(len + i)){
            len--;
            i = -1;
        }
    }
    cout << len*2 << endl;
}

この実装により isSame 変数を取る必要がなくなります。

何が嬉しいのか

c++ のコード上では、一時変数 isSame がなくなっただけです。
一方でコードの読みやすさは著しく落ちていると思います。
for 文の中で i を操作するのもあまり綺麗と言えません。
しかし brainfuck においては、コードの可読性はもともと低いので、多少低くなったところで気にすることとではなく、変数が一つ減るということはかなりの負担軽減になります。
brainfcuk ではメモリの管理をすべて自分でしない上に、メモリの数値がコードに多大な影響を与えかねない関係上、変数が一つ増えるだけで精神的負担はだいぶ軽くなります。
また、後から変数を増やそうとしたら、コードのいたるところに修正を加えることになるので、変数の存在は見た目以上の負担になります。 今回のテクニックはその負担を減らせると点で優れているわけです。

まとめ

今回はもともと難しい問題なこともありこのテクニックはさほど重要ではないですが、この考え方はいろいろな問題を解くときに使えると思います。
知っていて損はないのではないでしょうか。
今回の話のコーディング方法を一言でまとめると、
* 条件を満たさない場合は、配列の状態を次に走査する配列に切り替えて、最初に戻す。
となります。
これはこれでわかりにくいですが、伝われば嬉しいです。

ss を brainfcuk で解く

ここまで小手先のテクニックを紹介しましたが、これだけで、 ss を解けるのかというと、No としか言えないです。上記のテクニックは、所詮、変数を減らすだけでしかありません。
実際にそれ以上の問題点が ss にはたくさんあります。ざっくりポイントを上げると * 要素数の数の把握をどうするか * s[i] と s[len+i] をどう比較するか * len--; をどう表現するか あたりでしょうか。

特に二つ目の項目は大きな問題となりますし、この項目をクリアできるかが、この問題を解けるかどうかを分けると思っています。
その説明は今回はもちろんしません。
一応、私の回答のリンクを張っておきますので、参考にしたい方はどうぞ。

atcoder.jp

あとがき

今回の記事は brainfuck のコードが登場しませんでしたが、どうでしたでしょうか。
AdCの主催者に怒られたらどうにかします。
皆さん、良い brainfuck ライフを。