読者です 読者をやめる 読者になる 読者になる

MANA-DOT

PIXEL ART, PROGRAMING, ETC.

正規表現による置換の繰り返しだけでライフゲームを作る

regexp_lifegame

  • 今更だけど最近正規表現で$1などのマッチした文字列を利用した置換をすることの強力さに気づいたので、なにか面白いことをしたかった
  • 新年一発目だしなにか面白いことをしたかった

ということで、タイトル通りにライフゲーム正規表現による置換の繰り返しだけで実装してみました。

デモ

□□□□□□□□□□
□□□□■■□□□□
□□□■□□■□□□
□□■□□□□■□□
□■□□□□□□■□
□■□□□□□□■□
□□■□□□□■□□
□□□■□□■□□□
□□□□■■□□□□
□□□□□□□□□□

うまく動いているっぽい! (ちなみに、端のセルについては面倒だったので、今回は常に死亡状態にしてしまっています。)

コード

var step = function() {
    var cells = $('#cells').text();
    for (var i = 0; i < 64; i++) {
        cells = cells
            .replace(/([□■BbWw]{3})([□■BbWw\n]{8})([□■BbWw])([□■])([□■BbWw])([□■BbWw\n]{8})([□■BbWw]{3})/, '$1$2$3a$4$1$3$5$7a$5$6$7') // 周り8マスを収集
            .replace(/a([□■])([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?a/, 'a$1$2$4$6$8$10$12$14$16a') // 黒の数を数える
            .replace(/a□[■Bb]{3}a/, 'w') // 誕生
            .replace(/a■[■Bb]{2,3}a/, 'B') // 生存
            .replace(/a■.*a/, 'b') // 死
            .replace(/a□.*a/, 'W') // 変化なし
        ;
    }
    cells = cells.replace(/[Bw]/g, '■').replace(/[bW]/g, '□');
    $('#cells').text(cells);
}
setInterval(step, 500);

描画部分以外はreplaceとループのみによって実装されています。 (セルの数-2)*6回の置換と、最後に全体置換を二回かけることでライフゲームの1ステップを実装しています。

わかりにくい解説

ルールの確認

まず、ライフゲームを再確認します。

  • セルと呼ばれる、黒(生存)白(死亡)の2状態を持つマスが二次元上に並んでいる。
  • ↑は、時間が進むごとに変化していく。
  • 1つのセルの変化のルールは、そのセルの周りの8セルの状態による。
  • 自身が死んでいて、周りのセルに生きてるセルがちょうど3つなら、次のステップで生存状態になる(誕生)
  • 自身が生きていて、周りのセルに生きているセルが2つか3つなら、次のステップで生存状態になる(生存)
  • 自身が生きていて、周りのセルに生きているセルが1つ以下なら、次のステップで死亡状態になる(過疎)
  • 自身が生きていて、周りのセルに生きているセルが4つ以上なら、次のステップで死亡状態になる(過密)
  • それ以外のセルはそのまま
  • 以上の変化を1ステップとし、時間とともに繰り返していく

たったこれだけのルールでセルが面白い変化をしていくというものです。

正規表現による実装

つまりは、

  • セルそれぞれについて、
  • 周り8つのセルのうち、生存状態のものの数を数え、
  • 現在の自身の状態と、数えた数により、次のステップでの状態を決める

ということを行えばよいわけです。セルそれぞれにというのが、コード中のfor文になります。

あるセルについて、周り8つのセルの状態をあつめる

.replace(/([□■BbWw]{3})([□■BbWw\n]{8})([□■BbWw])([□■])([□■BbWw])([□■BbWw\n]{8})([□■BbWw]{3})/, '$1$2$3a$4$1$3$5$7a$5$6$7')

以上の置換は、あるセルについて、その周囲8セルを集めてきて次の処理で扱いやすいように注目しているセルに寄せ集め、印(aで囲む)をつけています。

  • ([□■BbWw]{3}) というパターンは二回登場しますが、それぞれ上側3つのセルと、下側3つのセルにマッチさせます。BbWwについては後ほど解説するので、[□■BbWw]でセル1つ分だと思ってください。
  • ([□■BbWw\n]{8})というパターンは、y軸方向に注目した時の文字の差分にマッチします。8という数字は、x軸方向のマス目の数(今回は10個)からら、注目している周囲マスの数3を引き、改行ぶんの1を足した数です。
  • ([□■])は注目している自身のセルにマッチします。
  • これらを、注目しているセル以外は全くいじらずに、注目しているセルだけ、a□□□□□□□□□□a のような形に置き換えています。
  • aに囲まれた文字のうち、最初の文字は自身($4)です。
  • 以降に続く8つの文字は、周囲8つのセルです。

例えば、

■■□
□□□
□□■

というセルと周囲8セルに対してマッチし置換を行うと、

■■□
□a□■■□□□□□■a□
□□■

に置換されます。

周り8つのセルのうち、生きている物の数を数える

.replace(/a([□■])([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?([■Bb])?([□Ww])?a/, 'a$1$2$4$6$8$10$12$14$16a')

以上の置換で、先ほど置換で作った文字列(a□■■□□□□□■a)のうち、集めた周囲8セル(■■□□□□□■)の生存状態のものを残します。生存状態のマスと死亡状態のマスを交互に?でマッチさせ、生存状態のもののみ残して(ちょうど$偶数に対応します)置換します。

以上の置換で、

■■□
□a□■■□□□□□■a□
□□■

■■□
□a□■■■a□
□□■

に置換されます。

ルールに基づき、次のステップの状態を決定

  • 自身が死んでいて、周りのセルに生きてるセルがちょうど3つなら、次のステップで生存状態になる(誕生)
  • 自身が生きていて、周りのセルに生きているセルが2つか3つなら、次のステップで生存状態になる(生存)
  • 自身が生きていて、周りのセルに生きているセルが1つ以下なら、次のステップで死亡状態になる(過疎)
  • 自身が生きていて、周りのセルに生きているセルが4つ以上なら、次のステップで死亡状態になる(過密)
  • それ以外のセルはそのまま

自身の状態と、周囲8セルの生存セルの数が分かる状態になったので、上記ルールを素直に実装することが出来ます。

.replace(/a□[■Bb]{3}a/, 'w') // 誕生
.replace(/a■[■Bb]{2,3}a/, 'B') // 生存
.replace(/a■.*a/, 'b') // 死
.replace(/a□.*a/, 'W') // 変化なし

aに囲まれた文字列のうち、1文字目が自身の状態、残りが周囲8セルのうち生存状態のものなので、ルールに従ってマッチさせ置換します。

ここで注意したいのが、素直に /a□[■Bb]{3}a/(誕生) を ■に置き換えてしまうと、まだ置換が済んでいない他のセルの置換に影響を与えてしまいます。そこで、■には置換せず、中間状態に置換しています。

今回は、

  • B:現在■→次回■
  • b:現在■→次回□
  • W:現在□→次回□
  • w:現在□→次回■

というルールにしました。

前述までの置換で生存状態を [■Bb] などにマッチさせていたのは、このためです。

すべてのセルに対して置換したのち、中間状態を■□にしてあげる

cells = cells.replace(/[Bw]/g, '■').replace(/[bW]/g, '□');

これは最も簡単な置換ですね。解説不要だと思います。

以上で1ステップの置換が完了となり、これを繰り返すことでライフゲームを表現できます。

最後に

  • やっぱり正規表現すげー
  • セルの数増やすと負荷がどのくらいになるか気になる
  • とはいえ、このくらいのセル数でも辛いと思ってたので、サクサク動いてくれて感動している
  • 一部セル数を正規表現中にハードコードしたのと、for文使ったのが気になる
  • for文は g による全置換で使わずにいけるかと最初思っていたが、マッチした周囲8セルと、それらと同じ行のセルが取り残されるため難しい気がする。
  • 横幅のセル数ハードコードもやむなしかなあ。

改善案があれば教えて欲しいです。