XORでシェルピンスキーのギャスケットを描く

ProcessingのPythonモードで、短いコードから複雑な模様を生成してみます。

python

size(320,160)
background(255)
p=[0]*320;p[160]=1

for y in range(160):
 for x in range(320):
  if p[x]:point(x,y)
 p=[p[x-1]^p[(x+1)%320] for x in range(320)]

実行すると、シェルピンスキーのギャスケットが現れます。

何をしているのか

pは、横一列に並んだセルの状態を表すリストです。

p = [0] * 320
p[160] = 1

最初はすべてのセルを0にし、中央のセルだけを1にします。

0000000010000000

1になっているセルだけを点として描画します。

for x in range(320):
    if p[x]:
        point(x, y)

一行を描いたら、次の行を計算します。

p = [p[x - 1] ^ p[(x + 1) % 320] for x in range(320)]

^は排他的論理和、XORです。

左	右	XOR
0	0	0
0	1	1
1	0	1
1	1	0

左右のセルの状態が異なる場合だけ、次の世代のセルが1になります。

Pythonではリストの-1番目が最後の要素を意味するため、一番左のセルから見た左隣は、一番右のセルになります。

「ルール90」

このコードは、セル・オートマトンのルール90として知られています。

一般的なセル・オートマトンでは、左・中央・右の3セルから次の状態を決めます。
しかしルール90では中央の状態は使わず、左右のXORだけで表現できます。

ほかのXORでいけるルール

ルール	式
0	0
255	1
240	左
15	1 ^ 左
204	中央
51	1 ^ 中央
170	右
85	1 ^ 右
60	左 ^ 中央
195	1 ^ 左 ^ 中央
90	左 ^ 右
165	1 ^ 左 ^ 右
102	中央 ^ 右
153	1 ^ 中央 ^ 右
150	左 ^ 中央 ^ 右
105	1 ^ 左 ^ 中央 ^ 右

おまけ

更に短く

p = [a^b for a,b in zip([0]+p,p[1:]+[0])]

ルール30

p=[p[x-1]^(p[x]|p[(x+1)%320]) for x in range(320)]

ルール150

p=[p[x-1]^p[x]^p[(x+1)%320] for x in range(320)]

processing版

processing

size(320, 160);
background(255);

int[] p = new int[width];
p[width / 2] = 1;

for (int y = 0; y < height; y++) {
  for (int x = 0; x < width; x++)
    if (p[x] > 0) point(x, y);

  int[] q = new int[width];

  for (int x = 0; x < width; x++)
    q[x] = (x > 0 ? p[x - 1] : 0) ^ (x < width - 1 ? p[x + 1] : 0);
  p = q;
}