ジグソーパズルで素数を生成する
第54回冬のプログラミングシンポジウムにて中野先生が発表された「ジグソーパズルによる関数型プログラミング」がとても面白かったです。講演中ではジグソーパズルを置いていくことで3進法表記の数を2進法表記に変換したり、n進表現をグレイコードに変換したり、と「計算」がジグソーパズルできることを示していました。(TODO:論文が掲載されたらリンクを張る)
講演中の「3進法から2進法への変換」を早速実装してみたのがこちら。 https://github.com/nishio/jigsaw_model/blob/master/ex1.py
横方向の情報の流れを「左から右」に変更したので、結果の2進法表記は論文とは逆順です。
start: ['2', '0', '1'] ['0', '0', '0', '0', '0'] finished: ['0', '0', '0'] ['1', '1', '0', '0', '1']
で、僕は講演を聞いていて「これって45度傾ければ1次元セルオートマトンになるんじゃない？」と思ったので帰りの登山電車で考えていたのですが、結論から言うとN状態の1次元セルオートマトンの遷移規則は N**3 + N**2 + 4*N のピースがあれば十分シミュレートできます。あと、初期状態の長さをMとして、M * (M + 1) / 2 のピースがあれば任意の初期状態をセットアップするのに十分です。というわけで2状態で初期状態の長さが1のルール90の挙動は21種類のピースでシミュレートできます。
実行して1ピース1文字で、いくつかのピースを*、他をスペースで表現したものがこちら。キャスケットの模様が浮かび上がっています。上端・左端はまっすぐで、つながるようにピースを並べていくと模様が浮かび上がってくる、と。ジグソーパズルっぽさが上がって来ましたねｗ
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* * * *
* *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* * * *
* *
* * * * * * * *
* * * *
* * * *
* *
* * * *
* *
* *
* さて、セルオートマトンが実現できるなら、素数が計算できるわけなので(see 素数を計算するオートマトンを実装してみた)、せっかくだからそこまで実装してみましょう。
https://github.com/nishio/jigsaw_model/blob/master/ex4.py
出力はこうなります:
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . . . . . . . . .
. | . . . . . . . . . . . . . . . . . . . . .
| . . | . . . . . . . . . . . . . . . . . .
. | | . . . . . . . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . . . . . .
. | | | . . . . . . . . . . . . . . . .
| . . . | . . . . . . . . . . . . . . . . .
. | | | | . . . . . . . . . . . . . . . . . .
| . . . | . | . . . . . . . . . . . . . . . .
. | | | | | . . . . . . . . . . . . . .
| . . . | . . . . . . . . . . . . . . . . .
. | | | | | | . . . . . . . . . . . . .
| . . . | . . | . . | . . . . . . . . . . . . .
. | | | | | | | . . . . . . . . . . . . .
| . . . | . . | . | . . . . . . . .
. | | | | | | | | . . . . . . . . . . . . .
| . . . | . . | . . . . . . . . . . .
. | | | | | | | | | . . . . . . . . .
| . . . | . . | . . | | . . . . . . . .
. | | | | | | | | | | . . . . .
| . . . | . . | . . | . | . . . . .
. | | | | | | | | | | | . . . . . . . . . .
| . . . | . . | . . | . | | . . . . . . . .
. | | | | | | | | | | | | . . . . . . .
| . . . | . . | . . | . | | . | . . . . .
. | | | | | | | | | | | | | . . . .
| . . . | . . | . . | . | | . | . . . . . .
. | | | | | | | | | | | | | | . | . . . . . .
| . . . | . . | . . | . | | . . | . . | . . . .
. | | | | | | | | | | | | | | | . . .
| . . . | . . | . . | . | | . . | . . . | . . . .
. | | | | | | | | | | | | | | | | . . . . .
| . . . | . . | . . | . | | . . | | | | . .
. | | | | | | | | | | | | | | | | | . . . . . .
| . . . | . . | . . | . | | . . | | . . .
. | | | | | | | | | | | | | | | | | | . . | .
| . . . | . . | . . | . | | . . | | . | . . | . .
. | | | | | | | | | | | | | | | | | | | | . | .
| . . . | . . | . . | . | | . . | | . | . | . .
. | | | | | | | | | | | | | | | | | | | | | .
| . . . | . . | . . | . | | . . | | . | . . . . .
. | | | | | | | | | | | | | | | | | | | | | .
| . . . | . . | . . | . | | . . | | . | . . | | . | .
. | | | | | | | | | | | | | | | | | | | | | | |
| . . . | . . | . . | . | | . . | | . | . . | . |
. | | | | | | | | | | | | | | | | | | | | | | | | .
| . . . | . . | . . | . | | . . | | . | . . | . | .
. | | | | | | | | | | | | | | | | | | | | | | | |
| . . . | . . | . . | . | | . . | | . | . . | . | | | .
. | | | | | | | | | | | | | | | | | | | | | | | | |
| . . . | . . | . . | . | | . . | | . | . . | . | | . |
. | | | | | | | | | | | | | | | | | | | | | | | | | |
| . . . | . . | . . | . | | . . | | . | . . | . | | . | 模様の読み方がわかりにくいかもしれないので解説しておくと、下の2行
. | | | | | | | | | | | | | | | | | | | | | | | | | | | . . . | . . | . . | . | | . . | | . | . . | . | | . |
の「.」があるのは左から何文字目か、を数えると素数列になっています。
2 | | | | | | | | | | | | | | | | | | | | | | | | | | | 3 5 7 |1113 |1719 |23 | |2931 | |37 |4143 |47 | |53 |
広いテーブルにジグソーパズルのピースをきちんと繋がるように並べていくと、素数の縞模様が現れてくるわけです。
ピースの情報はこちら: https://github.com/nishio/jigsaw_model/blob/master/prime_pieces.csv
この素数を計算するオートマトンが16状態で、初期状態の長さが4なので先ほどの計算式から4426種類のピースがあれば十分であることが分かります。
