Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@takaramin株式会社ラクス

PHPでコードゴルフ - Brainf*ck

Last updated at Posted at 2024-03-18

この記事は、以下の記事の続きです。

第3問の自分の提出コードの解説をします。

第3問：Brainf*ck

プログラミング言語Brainf*ckのインタプリタを実装する問題でした。
私の提出コードがこちらです。

$s=fread(STDIN,9999);$p=-1;function l($s,&$p,$r){for($d=1;$d+=["["=>$r,"]"=>-$r][$s[$p+=$r]]??0;);}for($m=[$t=0];$s[++$p]??0;){$a=&$m[$t];match(ord($s[$p])){62=>$t++,60=>$t--,43=>$a++,45=>$a--,46=>print chr($a),91=>$a||l($s,$p,1),93=>$a&&l($s,$p,-1),default=>0};}

整形するとこんな感じ。

$s = fread(STDIN, 9999);
$p=-1;

function l($s, &$p, $r)
{
  for ($d = 1; $d += ["[" => $r, "]" => -$r][$s[$p += $r]] ?? 0;);
}

for ($m = [$t = 0]; $s[++$p] ?? 0;) {
  $a = &$m[$t];
  match (ord($s[$p])) {
    62 => $t++,
    60 => $t--,
    43 => $a++,
    45 => $a--,
    46 => print chr($a),
    91 => $a || l($s, $p, 1),
    93 => $a && l($s, $p, -1),
    default => 0
  };
}

もとの実装例からどのように短くしていったか説明していきます。

$memory[$ptr]の初期化

isset($memory[$ptr])というコードが4箇所出てきています。
これらを消すために、switchの前で初期化してやります。

+ $memory[$ptr] ??= 0;
  switch ($source[$pc]) {
  case '>':
    $ptr++;
    break;
  case '<':
    $ptr--;
    break;
  case '+':
-   if (!isset($memory[$ptr])) {
-     $memory[$ptr] = 0;
-   }
    $memory[$ptr]++;
    break;
  case '-':
-   if (!isset($memory[$ptr])) {
-     $memory[$ptr] = 0;
-   }
    $memory[$ptr]--;
    break;
  case '.':
    echo chr($memory[$ptr]);
    break;
  case '[':
-   if (!isset($memory[$ptr]) || $memory[$ptr] === 0) {
+   if ($memory[$ptr] === 0) {
      $depth = 1;
      while ($depth > 0) {
        $pc++;
        if ($source[$pc] === '[') {
          $depth++;
        } elseif ($source[$pc] === ']') {
          $depth--;
        }
      }
    }
    break;
  case ']':
-   if (isset($memory[$ptr]) && $memory[$ptr] !== 0) {
+   if ($memory[$ptr] !== 0) {
      $depth = 1;
      while ($depth > 0) {
        $pc--;
        if ($source[$pc] === ']') {
          $depth++;
        } elseif ($source[$pc] === '[') {
          $depth--;
        }
      }
    }
    break;
  }

共通部分の関数化

case '['とcase ']'で同じような処理が重複しているので、これをDRYにします。

function loop($source, &$pc, $direction)
{
  $depth = 1;
  while ($depth > 0) {
    $pc += $direction;
    if ($source[$pc] === '[') {
      $depth += $direction;
    } elseif ($source[$pc] === ']') {
      $depth -= $direction;
    }
  }
}

switch ($source[$pc]) {
// 省略
case '[':
  if ($memory[$ptr] === 0) {
    loop($source, $pc, 1);
  }
  break;
case ']':
  if ($memory[$ptr] !== 0) {
    loop($source, $pc, -1);
  }
  break;
}

引数の$directionの加算・減算でインクリメント・デクリメントを切り替えているのと、第2引数をリファレンス渡しにすることで戻り値を受け取る必要をなくしているのがポイントです。

switch→matchへ変更

記述量に関してはまっちちゃんの勝利！ということでmatchに変更します。

match ($source[$pc]) {
  '>' => $ptr++,
  '<' => $ptr--,
  '+' => $memory[$ptr]++,
  '-' => $memory[$ptr]--,
  '.' => print chr($memory[$ptr]),
  '[' => $memory[$ptr] || loop($source, $pc, 1),
  ']' => $memory[$ptr] && loop($source, $pc, -1),
  default => 0
}

matchの場合、=>の右側には式しか書けない、という制限があるため、switch版から少し変更を加えています。

  • echoは式でないのでprintに変更
  • ifは式でないので、&&, ||に変更
    • 0はfalseyなので=== 0 / !== 0を省略

また入力には改行などが含まれるようなので、それらを受け取ったときにエラーにならないようdefaultを追加しています（=> 0には特に意味ありません）。

$memory[$ptr]を減らす

同じ配列アクセスが5箇所あるので、これを減らすためにリファレンスを使います。

$a = &$memory[$ptr];
match ($source[$pc]) {
  '>' => $ptr++,
  '<' => $ptr--,
  '+' => $a++,
  '-' => $a--,
  '.' => print chr($a),
  '[' => $a || loop($source, $pc, 1),
  ']' => $a && loop($source, $pc, -1),
  default => 0
}

ちなみに、リファレンスのアクセスだとWarningが出ません（私も今回初めて知りました）。
なので最初に書いた$memory[$ptr] ??= 0は要らなくなります。

ordの利用

冒頭の提出コードでは、matchのカッコ内でordを使って、文字をASCIIコードに変換しています。こうすることで、関数呼び出しに5文字かかる代わりに=>の左側が1文字ずつ削れて、プラマイ2文字の節約に成功しました。

ループ条件の変更

実装例のwhileループの条件$pc < strlen($source)を$source[$pc] ?? 0に変更します。

while→forへ変更

while文をfor文へ変更すると、キーワードが2文字短くなる代わりに;が2つ増えるので、単に変更するだけだと文字数が減りません。ただし、うまく利用すると全体では文字数がやや削れます。

メインのwhileループ

- $memory = [];
- $ptr = 0;
- while ($source[$pc] ?? 0) {
+ for ($memory = [$ptr = 0]; $source[$pc] ?? 0; $pc++) {
    // ...
-   $pc++;
  }

for文の;を無駄にしないよう、2つ目の条件式以外のところに他からコードを移動させています。
同時に、$memoryの0番目の要素は0でもいいので、配列の初期化と$ptrへの代入をまとめています。

また、$pcのインクリメントと参照をまとめることもできます。

- for ($memory = [$ptr = 0]; $source[$pc] ?? 0; $pc++) {
+ for ($memory = [$ptr = 0]; $source[++$pc] ?? 0;) {

ただ、前置インクリメントでないと上手くいかない関係上、$pcの初期値は0ではなく-1にする必要があります。

関数内のwhileループ

  function loop($source, &$pc, $direction)
  {
-   $depth = 1;
-   while ($depth > 0) {
+   for ($depth = 1; $depth;) {
      $pc += $direction;
      if ($source[$pc] === '[') {
        $depth += $direction;
      } elseif ($source[$pc] === ']') {
        $depth -= $direction;
      }
    }
  }

if文を配列アクセスに変更

ここからはloop関数の中を変えていきます。

  function loop($source, &$pc, $direction)
  {
    for ($depth = 1; $depth;) {
      $pc += $direction;
-     if ($source[$pc] === '[') {
-       $depth += $direction;
-     } elseif ($source[$pc] === ']') {
-       $depth -= $direction;
-     }
+     $depth += (['[' => $direction, ']' => -$direction][$source[$pc]] ?? 0);
    }
  }

代入と参照をまとめる

まず、$pcの代入 (+=) と参照を1つにまとめます。

  function loop($source, &$pc, $direction)
  {
    for ($depth = 1; $depth;) {
-     $pc += $direction;
-     $depth += (['[' => $direction, ']' => -$direction][$source[$pc]] ?? 0);
+     $depth += (['[' => $direction, ']' => -$direction][$source[$pc += $direction]] ?? 0);
    }
  }

さらに、$depthの代入と参照もまとめられます。
するとfor文の{}の中身がなくなりますが、その場合公式マニュアルの例4のように、末尾はセミコロン1文字にできます。

  function loop($source, &$pc, $direction)
  {
-   for ($depth = 1; $depth;) {
-     $depth += (['[' => $direction, ']' => -$direction][$source[$pc += $direction]] ?? 0);
-   }
+   for ($depth = 1; $depth += (['[' => $direction, ']' => -$direction][$source[$pc += $direction]] ?? 0););
  }

stream_get_contents→freadに変更

標準入力から読み込むのにstream_get_contentsを使っていましたが、関数名が長いのでfreadを使います。freadは読み込むバイト数を指定しないといけませんが、今回のテストケースでは9999バイトにしておけば十分だったようです。

これで冒頭のコードと同じになるはずです。

その後

PHPerKaigi終了後、めもりーさんが私のコードを更に短縮してくださいました。

for($s=fread(STDIN,9999),$p=-1,$m=[$t=0];$a=&$m[$t],$s[++$p]??0;)for($d=1,match($o=ord($s[$p])){62=>$t++,60=>$t--,43=>$a++,45=>$a--,46=>print chr($a),default=>0};($o==91&&!$a&&$r=1or$o==93&&$a&&$r=-1)&&$d+=["["=>$r,"]"=>-$r][$s[$p+=$r]]??0;);

これで242バイトで、当初の私のコードより21バイト短縮されています。
で、まだ削れそうなのでさらに削りました。

for($s=fread(STDIN,9999),$p=-1,$m=[$t=0];$a=&$m[$t],@$s[++$p];)for($d=1,match($o=ord($s[$p])){62=>$t++,60=>$t--,43=>$a++,45=>$a--,46=>print chr($a),default=>0};($a?$o==93&&$r=-1:$o==91&&$r=1)&&$d+=@["["=>$r,"]"=>-$r][$s[$p+=$r]];);

これで231バイトです。

やってる間はもうこれ以上削れないだろう……と思っていても、思いの外短縮の余地があるものだなあというところです。

いやまだ減らせるぞ、という方はぜひコメントで教えてください！

03/20 追記
@rana_kualu さんに頂いたコメントと、プラスアルファでもう少し減らして220バイトになりました。

for($s=0 .fread(STDIN,1e8),$m=[$t=0];$a=&$m[$t],$o=ord(@$s[++$p]);)for($d=1,match($o){60,62=>$t+=$o-61,43,45=>$a+=44-$o,46=>print chr($a),default=>0};$a?$o==93&&$r=-1:$o==91&&$r=1and$d+=@["["=>$r,"]"=>-$r][$s[$p+=$r]];);
3
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?