ポケモンしりとりパーティの作成 - クフでダローバルな日記

昨晩、@KRiver1君のツイートを見てて、ポケモンのパーティをしりとり縛りで作るのが楽しそうだったので、全パターン列挙をしてみようと思いまして、一晩色々やってみました。
Rubyで作ってソースをGitHubに公開してみました。
mazamachi/poke_shiritori

最初に作ったのはpokemon_shiritori.rbですね。
$hashはポケモンを頭文字、末尾の文字で分類したハッシュです。
しりとりのため末尾が「ー」や小文字の時を特別扱いする必要があったのでString#lastで場合分けしています。
本当は小文字をもっと楽に使うメソッドがあればよかったんですが、特に良いのもないらしいので何ら工夫することなくやってみました。

そして、Hash#shiritoriメソッドを再帰的に定義しています。もっとも、これは$hashのように、しりとり用に整形されたハッシュにしか使えませんが…。
これは、しりとりの最初の文字と単語数nを与えると、しりとり用hashの中で頭文字が与えられたものと一致する各単語を、「各単語の末尾とn-1を与えたHash#shiritoriが返した配列」に追加するものです。

もちろん再帰的定義なため時間が凄くかかります。見てた感じ数時間はかかるんではないでしょうか。
また、今回ポケモンが718匹も居るために意外とパターン数が多く、メモリの使用量が膨大になったことも影響し、目に見えてどんどん遅くなっていました。

そこで、再帰的定義をしない改良版がpokemon_nosaiki.rbです。(安直なファイル名)
これは、n単語で出来たしりとり組を、その最初の単語の先頭の文字で場合分けしたものを＄ans_hash[n]に保存しておくものです。
こうしておくと、n+1単語のしりとり組を作成する際には$ans_hash[n][(各ポケモンの末尾)]にある配列の先頭に追加して、これをまた$ans_hash[n+1][(このポケモンの先頭)]に保存しておけばいいので、そこそこ高速化出来たようです。たしか全部を出力するのに30分くらいです。
ただ、n=6も作ってそれをtxtファイルに書き込むとなると、かなりメモリを食ってしまうので、n=6だけはいきなりtxtファイルに書き込むようにしています。
多分時間がかかっているのは計算量というよりは仮想メモリの部分だと思うので、ハイスペPCが欲しくなりますね。

ここまで完成して朝もう一度@KRiver1君のツイート見たら、しりとりがループになるようにとか言っているわけですよ。
つらい。

そこで作ったのが、pokemon_nosaiki_loop.rbです。
考え方としてはpokemon_nosaiki.rbとほぼ一緒なのですが、単語数、先頭の文字と一緒に最後の文字でも場合分けをしています。
この影響で $1 \leq n \leq 5$ではpokemon_nosaiki.rbよりみた感じ遅いんですが,$n==6$の時すぐ終わるので、結果的に全体で120sくらいで終わります。

で、肝心の結果ですが、
ループをしないしりとりパーティでは104,586,806通り、
ループのパーティでは1,553,658通りです。

多いな…
せっかくだしzip形式でdropboxに上げたので、ご自由にお使い(?)ください。
","区切りなのでExcelとかで表形式にもしやすくなっているはずです。

ループ:https://www.dropbox.com/s/9l9edrbcyhccdk4/shiritori_loop.txt.zip
解凍したら134.3MBになります。
こんな感じ
f:id:SWIMATH2:20140610002918p:plain