Hatena::ブログ(Diary)

西尾泰和のはてなダイアリー

2013-01-15

ジグソーパズルで素数を生成する

第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文字で、いくつかのピースを*、他をスペースで表現したものがこちら。キャスケットの模様が浮かび上がっています。上端・左端はまっすぐで、つながるようにピースを並べていくと模様が浮かび上がってくる、と。ジグソーパズルっぽさが上がって来ましたねw


* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
                                                               
*   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *  
                                                               
* *     * *     * *     * *     * *     * *     * *     * *    
                                                               
*       *       *       *       *       *       *       *      
                                                               
* * * *         * * * *         * * * *         * * * *        
                                                               
*   *           *   *           *   *           *   *          
                                                               
* *             * *             * *             * *            
                                                               
*               *               *               *              
                                                               
* * * * * * * *                 * * * * * * * *                
                                                               
*   *   *   *                   *   *   *   *                  
                                                               
* *     * *                     * *     * *                    
                                                               
*       *                       *       *                      
                                                               
* * * *                         * * * *                        
                                                               
*   *                           *   *                          
                                                               
* *                             * *                            
                                                               
*                               *                              
                                                               
* * * * * * * * * * * * * * * *                                
                                                               
*   *   *   *   *   *   *   *                                  
                                                               
* *     * *     * *     * *                                    
                                                               
*       *       *       *                                      
                                                               
* * * *         * * * *                                        
                                                               
*   *           *   *                                          
                                                               
* *             * *                                            
                                                               
*               *                                              
                                                               
* * * * * * * *                                                
                                                               
*   *   *   *                                                  
                                                               
* *     * *                                                    
                                                               
*       *                                                      
                                                               
* * * *                                                        
                                                               
*   *                                                          
                                                               
* *                                                            
                                                               
*                                                              

さて、セルオートマトンが実現できるなら、素数が計算できるわけなので(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種類のピースがあれば十分であることが分かります。

投稿したコメントは管理者が承認するまで公開されません。

トラックバック - http://d.hatena.ne.jp/nishiohirokazu/20130115/1358238311