CodeIQ の問題「予約語から最長のしりとりを作ろう！」 https://codeiq.jp/ace/stakemura/q408 に回答したときのコード。

solver.rb

#
# CodeIQ の問題「予約語から最長のしりとりを作ろう！」
# https://codeiq.jp/ace/stakemura/q408 に対する回答コードです。
#
# 出題者による解答例は https://github.com/stakemura/codeiq こちらにあります。
#

#
# 予約語の最初の 1 文字と最後の 1 文字で構成される 2 文字の
# 文字列 (headtail) の頻度を保持します
#
class Headtails
  def initialize(keywords)
    @headtails = Hash.new(0)
    @headtails_originals = {}

    keywords.each do |e|
      headtail = e[0] + e[-1]
      @headtails[headtail] += 1

      if @headtails_originals.key?(headtail)
        @headtails_originals[headtail] << e
      else
        @headtails_originals[headtail] = [e]
      end
    end
  end

  #
  # 指定された headtail の頻度を返却します
  #
  def count(headtail)
    return @headtails[headtail]
  end

  #
  # このオブジェクトが保持する headtail を列挙します
  #
  def each
    @headtails.each do |ht, count|
      yield ht
    end
  end

  #
  # headtail で構成されたシーケンスを予約語の列に
  # 復元します
  #
  def decode(sequence)
    result = []
    counts = Hash.new(0)

    sequence.each do |ht|
      result << @headtails_originals[ht][counts[ht]]
      counts[ht] += 1
    end

    return result
  end
end


#
# 前の文字列の最後の文字に合致する、後続できる文字列の集合を
# 保持します
#
class Followers
  def initialize(headtails)
    @followers_table = {}

    headtails.each do |ht_i|
      tail_ch = ht_i[-1]
      followers = []

      headtails.each do |ht_j|
        next if ht_i == ht_j
        followers << ht_j if ht_j[0] == tail_ch
      end

      @followers_table[ht_i] = followers
    end
  end

  #
  # 指定された headtail に後続できる headtail を返却します
  #
  def get_followers(headtail)
    return @followers_table[headtail]
  end
end


#
# 最長のしりとりシーケンスを探す機能です
#
class LongestSequenceFinder
  def initialize(headtails, followers)
    @headtails = headtails
    @followers = followers             
  end

  #
  # 最長のしりとりシーケンスを探します
  #
  def find
    longest_sequence = []

    @headtails.each do |ht|
      used_headtails = Hash.new(0)
      used_headtails[ht] = 1
      sequence = [ht]

      ret = find_recursive(used_headtails, sequence)
      longest_sequence = ret if ret.size > longest_sequence.size
    end

    return longest_sequence
  end

  #
  # 再帰的に最長のしりとりシーケンスを探します
  #
  def find_recursive(used_headtails, sequence)
    last_headtail = sequence[-1]

    candidates = @followers.get_followers(last_headtail)
    found_any = false
    longest_sequence = []

    # 現在得られている最長のシーケンスと同じかそれ未満となるような
    # 結果しか得られない headtail はスキップできるので、それらを
    #  can_skip_headtails で保持しています
    can_skip_headtails = []

    candidates.each do |candidate_headtail|
      # すでにすべて利用しきった headatail をここで取り除く
      next if used_headtails[candidate_headtail] >= @headtails.count(candidate_headtail)

      # スキップ可能な headtail をここで取り除く
      next if can_skip_headtails.include?(candidate_headtail)

      found_any = true

      used_headtails[candidate_headtail] += 1
      sequence << candidate_headtail

      found_sequence = find_recursive(used_headtails, sequence)

      used_headtails[candidate_headtail] -= 1
      sequence.pop

      # いままでより最長のシーケンスが見つかった場合は、それで更新する
      if found_sequence.size > longest_sequence.size
        longest_sequence = found_sequence

        # 最長シーケンスにおいて、現在位置より後方に現れる headtail については、
        # 最適な組み合わせとなっているため、それらを構成する headatail は
        # 再帰的なチェックをする必要がなくなる
        can_skip_headtails = longest_sequence[sequence.size .. -1]
      end
    end

    if found_any
      # 何かしら最長シーケンスが見つかったのであれば、それを返却する
      return longest_sequence

    else
      # 最長シーケンスを見つけることができなかった場合は、
      # 引数に渡された sequence そのものが最長であることを示している
      return sequence.dup
    end
  end
end


# ---

# 予約語を標準入力から受け取ります
keywords = $stdin.readlines.map { |e| e.chomp }

headtails = Headtails.new(keywords)
followers = Followers.new(headtails)

finder = LongestSequenceFinder.new(headtails, followers)
result = finder.find()

puts headtails.decode(result).join(" ")