「憤怒の火山」全列挙プログラム(2)

fname = "songs_.txt"

open(fname) {|file|
  # パスデータ、曲名のハッシュを作成
  path = {}
  songdb = {}
  while line = file.gets
    line.chomp!
    # Ruby1.9前提：stringのlengthの仕様の差で日本語のlengthを正しく取れない
    len = line.length
    upper = line.upcase
    # おそらくここもRuby1.9前提
    first = upper[0]
    last = upper[len - 1]
    # [A-Z]を[A-Z0-9]とすれば数字のマッチ取れるけど忘れてた
    if first =~ /[A-Z]/ && last =~ /[A-Z]/
      # パスを追加
      if path[first] == nil
        path[first] = [last]
      else
        if !path[first].include?(last)
          path[first] << last
        end
      end
      
      # 曲名をハッシュに追加
      key = first + last
      if songdb[key] == nil
        songdb[key] = [line]
      else 
        songdb[key] << line
      end
    end
  end
  
  # 全パス探索
  solutions = []
  for first_char in "A".."Z" do
    path[first_char].each do |second_char|
      path[second_char].each do |third_char|
        path[third_char].each do |fourth_char|
          if path[fourth_char].include?(first_char)
            solutions << [first_char, second_char, third_char, fourth_char]
          end
        end
      end
    end
  end
  
  # パス出力
  solutions.each do |sol|
      key1 = sol[0] + sol[1]
      key2 = sol[1] + sol[2]
      key3 = sol[2] + sol[3]
      key4 = sol[3] + sol[0]
      
      # 曲の表示形式調整
      songs1 = "("
      count = 0
      songdb[key1].each do |song|
        if count != 0
          songs1 += " / "
        end
        songs1 += song
        count += 1
      end
      songs1 += ")"
      
      songs2 = "("
      count = 0
      songdb[key2].each do |song|
        if count != 0
          songs2 += " / "
        end
        songs2 += song
        count += 1
      end
      songs2 += ")"
      
      songs3 = "("
      count = 0
      songdb[key3].each do |song|
        if count != 0
          songs3 += " / "
        end
        songs3 += song
        count += 1
      end
      songs3 += ")"
      
      songs4 = "("
      count = 0
      songdb[key4].each do |song|
        if count != 0
          songs4 += " / "
        end
        songs4 += song
        count += 1
      end
      songs4 += ")"
      
      puts songs1 + " -> " + songs2 + " -> " + songs3 + " -> " + songs4
  end
}

解説

理論は一時期わりと話題になった論文、『ポケモンつなげるもん♪ ―最長しりとり問題を整数計画法で解く―』(佐藤,2011)にあるアイデアと同じで、各アルファベットをグラフのノードとし、選曲を曲名の頭文字から曲名の末尾の文字までの遷移を表す有向グラフの枝とした有向グラフを探索する問題になります。ただし今回はグラフの最長路を探索するのではなく、長さ4の閉路を探索する、というのが目標になります。長さ4の閉路ってことはつまり選曲は4回しかないから4回の選曲でどうやって元の文字に戻ってくるかを探す、ということになります。
また、今回は簡単のため同じ枝の再利用に関しては制限を設けていません。そのためINORI -> INORI -> INORI -> INORIというような同じ曲を繰り返し選ぶパスができてしまっています。それでもAの自己閉路(A->Aに行くパスのこと)は複数個の曲含んでますしそもそも解が余るほど出力できてるのでお許しくださいまし。枝の再利用に関しては完全なパス（今回出力したのは枝に属する曲名グループに対するパスなので、ここでの完全なパスは曲名で表記したパスの意味）を出力するときにパスの中の曲名のuniquenessで判定すれば（コードに相当な無駄は出るかもしれませんが）とりあえず完全列挙が可能になるでしょう、と推定。
さて、まぁやってることなんですが、上から順に、

• 曲名から「頭文字」「末尾の文字」によるパスごとに曲を分類してsongdbに追加、「頭文字」から「末尾の文字」のパスが存在することを示すため頭文字をキーにしたハッシュに対応する末尾の文字の配列を作って行きます。
• そして、アルファベットの各文字に対して可能なパスの組み合わせ（グラフ理論でいうところの接続行列に相当します）をどんどん辿って行く。ここが最悪26の4乗パターン辿るforの4重ループになっているので正直ここは最適化できるんであればするべきです。4曲目から辿れる末尾の文字が1文字目の頭文字に一致すれば解の配列に追加していきます。
• 最後に、1文字目+2文字目、2文字目+3文字目、3文字目+4文字目、4文字目+1文字目のキーを持つ曲をsongdbから取り出します。ここで全パスを分解して列挙するのが面倒だったので、探索できたパスに対する曲グループの列挙をするようにしています。

…あらわかりにくい（汗）。