思いついたので、実装してみました。
メインループの中は実質的に sed コマンドしか使っていません。
また、スクリプト全体でも、コマンドは sed, expr, echo の
3 種類だけしか使っていません（for, while などの構文は使っていますが）。
前準備が少し長いですが、
本質は最後のほうの while ループ内です。
本質は最後のほうの 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）
がセルの数だけ入っています。
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 に戻します。
$ ./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"`
