ポケモンしりとりパーティの作成 改良版

前回(http://swimath2.hatenablog.com/entry/2014/06/09/235315)のプログラム(ループの方)は実行時間がおよそ120sでした。
また、しりとりがループになっているのにもかかわらず、重複を取り除いていないなどの欠点もありました。
そこで、色々と改良してみました。

#! ruby -Ku
t0 = Time.now
class String
  def last#しりとりのルールに則った最後の文字を返す。
    large=["ア","イ","ウ","エ","オ","ツ","ヤ","ユ","ヨ"]
    small=["ァ","ィ","ゥ","ェ","ォ","ッ","ャ","ュ","ョ"]
    if self[-1] == "ー"
      return self[0..-2].last
    elsif small.include?(self[-1])
      return large[small.index(self[-1])]
    else
      return self[-1]
    end
  end
  def smaller? #ワニノコなどはワ>コなので不適
    if self[0].ord <= self.last.ord
      return true
    else
      return false
    end
  end
  def sentou?(ar) #あるポケモンがarに追加されるとき、それより前に出ていないかチェック
    if (ar+[self]).sort[0] == self
      return true
    else
      return false
    end
  end
end


def answer
  File.open("shiritori_loop_sort_reuse.txt", "w") { |f|  
    $ans_hash={}
    $ans_hash[1] = {}
    list = []
    File.open("./pokemon_list.txt", "r") { |file|
      file.each do |pokemon|
        pokemon.chomp!
        if pokemon.last!="ン"
          list << pokemon
          $ans_hash[1][pokemon[0]] ||= {} 
          ($ans_hash[1][pokemon[0]][pokemon.last]||= []) << [pokemon]
          #各ポケモンの先頭の文字及び末尾の文字で分類したハッシュを作成。
        end
      end
    }
    list.sort!
    for n in 2..5
      $ans_hash[n] = {}
      list.each do |poke|
        $ans_hash[n][poke[0]] || $ans_hash[n][poke[0]] = {}
        ($ans_hash[n-1][poke.last]||[]).each do |kumi|
          if n==5 
          #5の場合だけは、6匹目が追加されることを考えて、先頭の文字と末尾の文字を満たす
          #ポケモンが存在する時のみ配列を作成する。
            if $ans_hash[1][kumi[0]][poke[0]]
              kumi[1].each do |ar|
                unless ar.include?(poke)
                  ($ans_hash[n][poke[0]][kumi[0]]||=[])<<([poke]+ar)
                end
              end
            end
          else #nが2から4では、$ans_hash[n-1]に分類されたしりとりが作成されているので、
          #各ポケモンの末尾の文字の配列を参照して先頭に追加すれば良い。
            kumi[1].each do |ar|
              unless ar.include?(poke)
              ($ans_hash[n][poke[0]][kumi[0]]||=[])<<([poke]+ar)
            end
          end
        end
      end
      p [n,poke]
      end
    end
    n=6
    $sum = 0
    list.each do |poke|
      p [n,poke]
      unless poke.smaller?
        next
      end
      #n=6では先頭に追加して書き込むだけで良い。
      (($ans_hash[n-1][poke.last]||{})[poke[0]]||[]).each do |ar|
        if poke.sentou?(ar)
          unless ar.include?(poke)
            $sum += 1
            f.puts ([poke]+ar).join(",")
          end
        end
      end
    end
    f.puts $sum.to_s
  }
  return $sum
end
p answer
p (Time.now-t0).to_s+"s" 

String#smaller?で、そもそもそのポケモンの末尾の文字が先頭の文字よりも前かを判定しています。
例えばワニノコだと、必然的にコから始まるポケモンを含むので、それまでの探索で既に見つかっているはずです。

そして、String#smaller(ar)によって、n=6の場合にポケモンをしりとりの配列に追加した時、他にそのポケモンより前に出ているポケモンがいないかをチェックしています。

これらにより、重複削除が可能になり、実行時間は80s程度となりました。
ちなみに、重複を削除した結果は263905通りです。

そして今回の更新の最大のポイントがn==5でも場合分けをすることです。
ans_hash[1]には、各ポケモンを先頭と末尾の文字で場合分けした情報が保存されていると見なすことが出来ます。そこで、この情報を再利用して、「４ポケモンからなるしりとりの末尾の文字」と、「その4ポケモンのしりとりに追加したいポケモンの先頭の文字」をそれぞれ先頭と末尾に持つ時のみ、ans_hash[5]に追加するようにしました。
例えば、アから始まってアで終わるポケモンは存在しないのに、["アリゲイツ", "ツンベアー", "アーマルド", "ドーブル", "ルギア"]のようなものを作っても、この配列が参照されることは絶対にないので、予め考慮の対象から取り除いておこうということです。

この工夫をした結果、263905通りを見つけるのにおよそ13〜14s程度でできるようになりました。

一応、重複を取り除いたtxtファイルのzipを置いておきます。
解凍すると22.8MBになるので注意してください。
ちなみにlist自体もソートしてあるので、今回はこんな感じで名前順に並んでいます。

もっと改良する方法があれば誰か教えてください(・ω<)