Brainfuckインタープリタのコードを短くする

Brainfuckといえば色々なコードが短くかけるのが長所ですが、前回書いたコードからかなり短くしました。ちょっと荒技多めですが。

前回のコード

Brainfuckインタープリタをできるだけ短く書く

2014.10.12

using System;
class C
{
  static void Main()
  {
    string _ = Console.ReadLine();
    int[] m = new int[256], s = new int[9];
    int i = 0, p = 0, l = 0, d = -1, c;
    for (; i < _.Length; i++)
    {
      c = _[i];
      if (d != -1) { d += c == 91 ? 1 : c == 93 ? -1 : 0; break; }
      switch (c)
      {
        case 43: m[p]++; break;
        case 45: m[p]--; break;
        case 62: case 60: p += c - 61; break;
        case 46: Console.Write((char)m[p]); ; break;
        case 44: m[p] = Console.Read(); break;
        case 93: if (m[p] < 1) l--; else i = s[l]; break;
        case 91: if (m[p] < 1) d = 0; else s[++l] = i; break;
      }
    }
    Console.ReadKey();
  }
}

前回のコードはswitch文で条件分岐していましたが、if文で書いた方が文字数は減ることが判明。そりゃいちいちcaseとかbreakとか書いてたら文字数増えますわ。

今回のコード

using static System.Console;
class z
{
    static void Main()
    {
        string _ = ReadLine();
        int[] m = new int[999];
        for (int i = 0, p = 9, l = 0, d = 0, c; ++i < _.Length;)
        {
            c = _[i];
            if (d > 0) d -= c > 90 ? c - 92 : 0;
            else if (c == 44) m[p] = Read();
            else if (c < 46) m[p] -= c - 44;
            else if (c < 47) Write((char)m[p]);
            else if (c < 63) p += c - 61;
            else if (c < 92) if (m[p] < 1) d = 1; else m[++l] = i;
            else i = m[l--] - 1;
        }
    }
}

正直言って短くする要所はかなり多かったのでそれぞれ説明。

using staticでクラス省略

using static System.Console;

これで、これ以降はConsoleを省略することができます。

条件分岐の数を減らす

Brainfuckの命令が8個だということはこの記事を読んでいる方はわかると思いますが、その文字コードに着目すると、そもそも条件分岐の数を減らすことができることがわかります。

このことから考えていただくと、例えばメモリのインクリメント・デクリメントは結局は+1しているか-1しているかの問題です。そして+(43)と-(45)の文字コードは2番違い。ということは44で引いた結果をメモリから引けば結論として同じことができます。

// +の場合
m[p] -= 43 - 44;
// -の場合
m[p] -= 45 - 44;

これはポインターにも使うことができます。>(62)と<(60)も文字コードでは2番違いなので61引いた結果を足せば同じことができます。

// >の場合
p += 62 - 61;
// <の場合
p += 60 - 61;

こうなりますね。
次に文字の入出力ですがこれはやってる内容は文字の入力と出力というように、やっていることが真逆なので==式で条件分岐します。また、コンマ命令は44で、ピリオド命令は46です。これは+命令と-命令と文字コードが近いです。というか+と-の間にコンマが入ってしまっています。なのれこの命令は先に条件分岐しておく必要があります。

// ,の場合
m[p] = Read();
// .の場合
Write((char)m[p]);

これは正直短くしようがないと思います。
次にループです。ここが一番鬼門です。ループ開始の時にメモリの値あ0ならばループの中身は全てスキップする必要があります。また、ここでループ内にループが存在することも考慮する必要があります。
実は前回のコードはここにバグがありまして、ループ内にループがあった時にバグります。今回はスキップ用カウントを用意して対処しています。
さて、前回はメモリ用の配列とは別にループ用の配列を作っていました。これでは文字数が伸びてしまうので、配列をまとめちゃいましょう。
今回のコードではm配列の0〜8がループ用配列として、9＿998がメモリとなっています。

// [の場合
if (m[p] < 1)
  d = 1;
else
  m[++l] = i;

メモリの値が<1の場合(0の場合)はスキップカウント(d変数)を1にします。 d変数はスキップ用カウントです。0の時は通常実行、>=1の時はスキップ用のコードへ行きます。
メモリの値が<1ではない場合はループ配列に今の自分の場所を記録します。lを先にインクリメントしてから配列に記録しています。そのため、ループ用配列は実質0からではなく1から利用することになります。
ループ終了の]命令がきた時の条件分岐については、その他の命令ということで一番最後のelseにあります。命令は8個しかありえないわけですし、ここで条件分岐を組む必要はありません。

i = m[l--] - 1;

ここでの特徴は、ループ終了時にメモリの値が0だったらループを終了させ、そうでなければ再びループを実行します。しかし、ループをスキップする命令はループ開始の命令のところに既に書いたため、ここではメモリの値の中身関係なしにループ開始のところに戻っています。ループ開始命令の前に戻る必要があるため、m[l–] – 1という風に-1しています。

その他の対策

あとは細かい対策です。forループの書き方について、根本的に書き方を直せば1文字減らせます。

// 一般的な書き方
for (int i = 0; i < 10; i++) ;
// 削った書き方
for (int i = 0; ++i < 10; ) ;

また、ループに関係ない変数であっても、forの初期化文で変数を宣言・初期化すればセミコロンが1つ削れます。

まとめ

今回のインタープリタは前回と比べて一気に削れましたが、欠点としてコメントが一切使えなくなっています。また脆弱性対策…といいますか、Brainfuckに脆弱性があるのかわかりませんが、ループ用の配列とメモリ用の配列を一緒にしてしまったため、メモリのポインタがループ用のところに行ってしまう恐れがありますし、逆にループが多いとメモリ用の配列にめり込みます。
今現状だとこれが一番短い方という感じですが、最近のC#はもっと短いコードがかけるようになっているので将来的にもっと短くできるかもしれないですね