三流プログラマの戯言

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

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

初めに

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

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

目次

概要

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

ループ構造の逆転

問題

今回使用する問題は、ABC066ss です。

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 ではメモリの管理をすべて自分でしない上に、メモリの数値がコードに多大な影響を与えかねない関係上、変数が一つ増えるだけで精神的負担はだいぶ軽くなります。
また、後から変数を増やそうとしたら、コードのいたるところに修正を加えることになるので、変数の存在は見た目以上の負担になります。 今回のテクニックはその負担を減らせると点で優れているわけです。

まとめ

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

ssbrainfcuk で解く

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

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

atcoder.jp

あとがき

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