わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

puyoren: ぷよぷよ連鎖パターン生成

2009年9月17日:ぷよぷよ2連鎖171種類!Rubyスクリプトを,"puyoren"という名称で公開しました.ソースと生成したパターンは,GitHub - takehiko/puyoren: Puyopuyo Rensa Pattern Generatorより参照・取得できます.
READMEを転載します.

「ぷよぷよ」の連鎖パターンを生成するための Ruby スクリプト群です.
http://d.hatena.ne.jp/takehikom/20090917/1253135033 のために
作成していたのですが,微調整の上,リリースしました.

あらかじめ,gem install multiset を実行してください.
(Ruby 1.8系を使用している人は,rubygems のインストールも.)

ruby generate.rb を実行すると,with_fork と without_fork という
ディレクトリが作られ,何種類かの連鎖パターンがファイルに保存されます.

ruby rensa-generator.rb を実行すると,4個,4個の2連鎖で全消しとなる
全パターン(171通り)が出力されます.(ファイルには保存されません.)

ruby puyo-field.rb を実行すると,ある初期フィールドからの2連鎖の
状況が出力されます.(ファイルには保存されません.)

perm.rb は,Array クラスで順列を生成するメソッド perm および perm2 を
定義しており,オリジナル(ファイル内に URL を記載しています)から
インデントなどを変更しただけです.
perm.rb を除くすべてのファイルは,takehikom
(takehiko@sys.wakayama-u.ac.jp)が作成または生成しました.

ruby-1.9.3-p0 および ruby-1.8.7-p352 で動作確認をしています.

2年前は,「4個,4個」「5個,5個」「4個,4個,4個」の3種類の全消し(になる)パターンのみを求めていましたが,今回は,「4個,5個」「5個,4個」といった2連鎖*1,また連鎖に影響しない「X」の文字を含む2連鎖パターン*2というののも,生成させています.
処理方法についても,順に求めていく(without_fork)ほか,「1列だけで条件を満たすか」「2列を使って条件を満たすか」…「6列を使って条件を満たすか」を別々のプロセスに分けて計算し,最終的に統合するという方法(with_fork)を実装しました.あるクアッドコアLinuxマシンで,「4個,4個,4個」を求めてみると,実行時間は次のようになりました.プロセス分けした効果が出ていると言えます.

Rubyのバージョン 1.8.7 1.9.3
without_fork 15317秒 6110秒
with_fork 5805秒 2342秒

*1:1連鎖目に4個,2連鎖目に5個消えて全消しというパターンは258通り,その逆は320通りとなりました.

*2:Xを取り除いても消去の仕方が変わらないもの,言い換えると,X(複数ある場合はその中の1つ)の上に,何も乗っていない場合には,解から除外します.