[bash] sed だけで 1 次元セルオートマトンを作る

sed コマンドだけで 1 次元セルオートマトンを作るアイデアを
思いついたので、実装してみました。

メインループの中は実質的に sed コマンドしか使っていません。
また、スクリプト全体でも、コマンドは sed, expr, echo の
3 種類だけしか使っていません（for, while などの構文は使っていますが）。

１次元セルオートマトンとは何か、については
セル・オートマトン - Wikipedia の「1次元セル・オートマトン」の項目
をご覧ください。

スクリプト本体と実行方法

スクリプトを示します。

前準備が少し長いですが、
本質は最後のほうの while ループ内です。

#!/bin/bash
# 1D cellular automaton

# rule number
NRULE=90
#NRULE=30
#NRULE=110

# number of generation
NSTEP=300

# half size of width (width = HALFSIZE * 2 + 1)
HALFSIZE=300

# function to repeat string $2 $1 times
rep(){
  n=$1
  s=$2
  ss=""
  i=0
  while [ "$i" != "$n" ]; do
    ss=${ss}${s}
    i=`expr $i + 1`
  done
  echo -n $ss
}

# initial state
zeros=`rep $HALFSIZE 0`
str=$zeros"1"$zeros

next=()
tmp=$NRULE
i=7
while [ "$i" != "-1" ]; do
  next[$i]=`expr 2 + $tmp % 2`
  tmp=`expr $tmp / 2`
  i=`expr $i - 1`
done

# PBM header
echo "P1"
echo `expr $HALFSIZE \* 2 + 1` $NSTEP

# main
istep=0
while [ "$istep" != "$NSTEP" ]; do

  # output PBM
  echo $str | sed -e "s/\([01]\)/\1 /g"

  # calculate next generation
  str=0${str}0   # 0 is boundary
  for i in 1 2 3; do
    str=`echo $str | sed \
      -e "s/111/11${next[0]}11/g" \
      -e "s/110/11${next[1]}10/g" \
      -e "s/101/10${next[2]}01/g" \
      -e "s/100/10${next[3]}00/g" \
      -e "s/011/01${next[4]}11/g" \
      -e "s/010/01${next[5]}10/g" \
      -e "s/001/00${next[6]}01/g" \
      -e "s/000/00${next[7]}00/g"`
  done
  str=`echo $str | sed -e "s/[01]//g"`
  str=`echo $str | sed -e "s/2/0/g" -e "s/3/1/g"`

  istep=`expr $istep + 1`
done

実行方法ですが、

上記をたとえば cellular_automaton.sh という名前で保存して

    $ ./cellular_automaton.sh > rule090.pbm

と実行します。
私の手元 (CPU: Intel Core i7-3770 @ 3.40GHz, OS: Debian wheezy) では
5 秒弱かかりました。

得られた結果を、pbm 形式をサポートしているビューアで開くと
以下のような絵が見えるはずです。
時間は上から下に流れています。

スクリプト内のルール番号 NRULE を変更すると違う絵が描けます。
ルール番号の数字の意味は最初に示した参考文献のとおりです。

縦の長さは NSTEP、横の長さは HALFSIZE で調節できます。

アルゴリズム解説

本質的な部分だけを再掲します。
入力となる str にはセルの状態を表す文字（ここでは 1 または 0）
がセルの数だけ入っています。

  for i in 1 2 3; do
    str=`echo $str | sed \
      -e "s/111/11${next[0]}11/g" \
      (略)
  done
  str=`echo $str | sed -e "s/[01]//g"`
  str=`echo $str | sed -e "s/2/0/g" -e "s/3/1/g"`

3 行目で 111 を 11${next[0]}11 の 5 文字に変換しています。
${next[0]} には 111 の次の世代の文字が入っています。
本来なら

    s/111/${next[0]}/g

と置換したいところですが、
"111" のいずれの文字もあとから隣のセルが
参照するかもしれないので消せません。

これはどういうことかというと、
例えば ...01110... の並びの場合は
左から 011, 111, 110 の次の世代を計算する必要がありますが、
先に 111 を置換してしまうと、その結果は

    ...0(111 の次の世代の文字)0...

となってしまい,
両脇の 011, 110 の計算ができなくなります。

そこで、両脇のセルが参照できるように
上記のように 5 文字に置換しています。
変換後の 5 文字の意味はそれぞれ

    1 文字目、2 文字目、次の世代の文字、2 文字目、3 文字目

となっています。

このように置換した結果だと

    ...011(111 の次の世代の文字)110...

となるので、011, 110 の計算ができます。

別の変数を用意して、次の世代の文字はそこに格納しておけば
こんな複雑なことはしなくていいのですが、
それだとすっきりと書けない気がしたのでやりませんでした。

for ループを 3 周回しているのは、
sed は 1 回のコマンド内で変換した文字列は再変換しない
仕様になっているためです（でないと無限ループが起こりうる）。

これはたとえば

    $ echo 0000 | sed -e "s/00/0/g"
    00

という結果から確認できます。

先ほど示した
...011(111 の次の世代の文字)110... の結果は、
真ん中の 5 文字が変換済なので、
011, 110 の変換はできません。
ということで、3 文字から 1 文字を計算する
1 次元セルオートマトンを 1 ステップ回すためには
3 周回す必要があります。

このとき、変換前の世代と変換後の世代の文字を混ぜないため、
変換後の文字は 2 または 3 になっています。
これはスクリプト中間あたりの

    next[$i]=`expr 2 + $tmp % 2`

がそれに対応しています。

ループ 3 周を抜けたあとは、
もとが ...01110... の場合だと

    ...01311211310...

となります。新旧世代を塗り分けると

    ...01311211310...

となります。
旧世代が 3 文字続く場所がなくなったので、変換は終わりです
（端付近はこの限りではありません。
なので 4 周以上回すと文字数が保存されないことがあります）。

上記のままだと次の変換ができなくなるので

    str=`echo $str | sed -e "s/[01]//g"`

で旧世代の文字を削除し、

    str=`echo $str | sed -e "s/2/0/g" -e "s/3/1/g"`

で 2 を 0 に、3 を 1 に戻します。