読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「組合せ最適化:C++予約語から最長のしりとりを作ろう!」問題解説記事~わずか15%の35連鎖突破者はどうこの難問を解いたのか? #cpp #ruby

問題解説

CodeIQ中の人、millionsmileです。

C++の予約語使って、最長のしりとりを作ろう、という問題です。解答するためのプログラミング言語は、ほとんど不問(ideone.comで実行できる言語であればOKという条件なので)。

出題者は、計算幾何学などの難領域を面白い角度から切り出し、問題を出しくれているstakemuraさんです。今回も「予約語でしりとり」という楽しいテーマなんですが、普通に考えては最適解を得られないという、かゆいところに手が届かない問題となっています。

この問題の最長(最適解)は、35個の予約語を繋げたものになります。見事、この答えを導き出したのは、挑戦者の15%。全体的には非常にレベルの高い解答が多かったようです。

2名の解答コードが紹介されているのですが、いずれも秀逸です。

ではでは、stakemuraさんの解説記事をお楽しみください!

https://codeiq.jp/ace/stakemura/q408
f:id:codeiq:20130826184055p:plain

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

高速化の秘訣は乱数にあり

2013年7月22日~2013年8月19日の期間にわたって、「C++予約語から最長のしりとりを作ろう!」というタイトルで組合せ最適化の問題を出題しました。

問題文(要約)


計84種のC++予約語(CSVファイルとして提供)から、前の単語の最後の文字と次の単語の最初の文字が一致するように、しりとりの単語羅列(例: or return new …)を生成するプログラムを実装してください。ただし、しりとりは1度用いた予約語は再び用いてはならないという制約の元に、”使用単語数が最大”になるようにうまく組み合わせてください。先頭の単語は何を選んでもOKです。

予約語の数は84個。その中で挑戦者は最長となる単語の組合せを考えなくてはなりません。今回、ほとんどの挑戦者の方がソースコードと出力結果だけではなく、どこで躓きどう対処したかをびっしり書いて下さったのが特徴的でした。それだけ、悩ませる要素が多かったということでしょう。しかし、頂いた回答の中には理想解を見事導いただけではなく、当方が予想もしていないようなアプローチで解いた回答もあったりして、改めてCodeIQ挑戦者の方々の見識に驚かされました。

集計

さて、挑戦者が求めたしりとりの長さの内訳ですが、以下の通りです(複数回答の場合は最も結果が良かったものをカウントしております)

しりとりの長さ 回答者数
35 3人
34 3人
32 4人
30 1人
29 5人
28 2人
25 1人
21 1人

見事、理想解である”35”連鎖を勝ち取った方、おめでとうございます。上記の結果からも、いかに理想解を奪取するのが難しいかが伺えますね。それもそのはず、今回全ての順列を作成してから最長のしりとりを探すと、順列の数が84!=3.3E+0126となり、1無量大数を軽く凌駕する天文学的な組合せパターンと対峙することになります。さらに、今回の問題はグラフ理論でいう閉路が存在する(グラフ構造がDAGではない)ため、専門書に載っているような(重みを負数にした上での)最短経路問題の解法では解けません。

深さ優先探索で解く場合のポイント

さて、この問題を正攻法とも言える深さ優先探索で解く場合、以下の2点を徹底しない限り、現実的な計算時間には収まりません。



  1. どの単語とどの単語が繋がるかを事前計算により求めることで、再帰呼び出しの中で多用される探索処理を高速化する

  2. 特定条件ですでに求められている最長しりとりを参考に、探索する必要のない単語を枝刈りする


まず、ポイント1の最適化を徹底した実装が、word_chain.cpp (GitHubへのリンク)です。本プログラムでは、単語間の繋がりを前処理で求めることで、33連鎖までのパターンであれば数秒から数十秒で求めることが可能です。しかし、34連鎖にもなると、数時間から数十時間もの計算時間になり、理想解の35連鎖に至っては、数日プログラムを走らせても見つけることはまず無理でしょう。したがって、1の最適化だけでは組合せ爆発を克服するには至りません。

ポイント2は、ある単語が現在位置より後方(前方探索の場合)に現れることがすでに分かっている場合、その単語以降の再帰的探索をスキップすることで、組合せパターン数を劇的に削減しようというものです。このロジックを反映した実装が、word_chain_optimized.cpp (GitHubへのリンク) で、こちらは理想解の35連鎖を数秒で求めることが可能です。実は、挑戦者の方の多くがヒントが一切無かったにも関わらずこのアプローチを組み込んでいたのですが、その結果の多くは28や29連鎖という局所解に陥っていました。何故か?実はC++の予約語にはスキップしてはならない単語の組合せがあり、その条件は先頭の1文字と末尾の1文字が同じ単語が他にもある、というものです。一例として、"true"と"template"が挙げられます。なぜこの排他条件が必要かについて、私の拙い文章力では簡潔に説明出来ないのですが、一度紙の上で「グラフ上の頂点をN回だけ通れる特殊な一筆書き問題」としてシミュレートすると、イメージできるではないかと思います。

実装例

では理想解を勝ち取った2つの回答を紹介したいと思います。奇遇にもどちらもRubyによる実装でした。

まず深さ優先探索による実装の紹介です。ポイント1の最適化について、先頭の1文字と末尾の1文字のペアをハッシュキーにしているのが秀逸ですね。ポイント2についても反映されていますが、実は上記の局所解に陥らないためのスキップ条件が明示的に実装されていません。にも関わらず、理想解を導くことが出来て、しかも処理速度がすごく速い!一体、このコードにはどんな魔法が隠されているのか長らく悩んでいたのですが、今は「Rubyの辞書型の実装に助けられたのでは?」と解釈しています。辞書型をiterationしたときのkeyの順序がvalueの型(配列かそうでないか)によって決まり、う
まい具合にスキップ単語リストが並んだのではないかと…

#
# https://codeiq.jp/ace/stakemura/q408 の回答です
#
# - Ruby で書かれています。
# - 問題データは標準入力から与えてください。
# - 実行は ```ruby solver.rb < cpp11_keywords.csv``` とします。
# - プログラムを実行した結果、得られる出力は以下のとおりです。
#
# alignas sizeof float template else enum mutable explicit true export typename extern new wchar_t this static class signed default thread_local long goto operator register reinterpret_cast typedef friend dynamic_cast typeid do or return noexcept throw while
#

#
# アルゴリズム上の工夫
#   - ```true``` や ```template``` など、先頭の 1 文字と末尾の 1 文字が同じケースを
#     一つのパターン (headtail) に集約して取り扱い、無駄な計算を省いています。
#   - 処理途中において、すでに求められているその時の最長シーケンスを参考に、
#     探索する必要のない headtail を枝刈りしています。
#

#
# 予約語の最初の 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("\n")

次は、まさかの線形計画法とグラフ理論の組合せによる回答です。下記コードの参照文献にある、情報処理学会論文誌で紹介された、まさに学術的に最先端のアプローチで解いた回答になります。これだけ高度なアプローチを、それもフルスクラッチ実装で回答される方がいらっしゃるとは、夢にも思いませんでした。もし、この解法でないと解けないような問題であれば、間違いなく難易度は☆4の設問となっていたでしょう。それにしても、その道のプロとしか思えない実装、見事です…

# 予約語から最長のしりとりを作ろう!(2回目)
# 言語    :Ruby 1.9.3 or later
# OS      :Windows Vista (ideone.comで動作確認済み time:1.8s)
# コメント:1回目の回答では、組み合わせ探索に膨大な時間がかかるため、省力化に乱択を使っていましたが、
#           今回は、しりとりを有向グラフおよびネットワークと見なし、線形計画法(シンプレックス法)を使って最適解を
#           求めました。最適解から使用する単語と始点を求め、使用する単語から閉路を抽出。残った単語で経路を作り、
#           最後に閉路を組み込むことで、最長となるしりとりを作りました。
#
# 参考文献:Vol.46 No.SIG 2(TOM 11) 情報処理学会論文誌:数理モデル化と応用「最長しりとり問題の解法」Jan.2005
#
# 回答:(35個)
#       alignas
#       signed
#       dynamic_cast
#       throw
#       while
#       extern
#       new
#       wchar_t
#       this
#       static
#       class
#       sizeof
#       friend
#       do
#       operator
#       reinterpret_cast
#       thread_local
#       long
#       goto
#       or
#       register
#       return
#       noexcept
#       typeid
#       default
#       true
#       export
#       template
#       explicit
#       typedef
#       float
#       typename
#       enum
#       mutable
#       else

# 単語定義
Word = [
"and",
"alignof",
"asm",
"auto",
"and_eq",
"alignas",
"bitand",
"break",
"bool",
"bitor",
"case","continue",
"catch",
"compl",
"char","constexpr",
"class",
"char16_t","char32_t","const","const_cast",
"decltype","delete","double",
"do",
"default","dynamic_cast",
"else",
"enum",
"extern",
"explicit","export",
"friend",
"false",
"for",
"float",
"goto",
"inline",
"if",
"int",
"long",
"mutable",
"namespace",
"not_eq",
"nullptr",
"noexcept","not",
"new",
"or_eq",
"operator","or",
"public",
"protected",
"private",
"return",
"register",
"reinterpret_cast",
"static",
"signed",
"sizeof",
"switch",
"short","static_assert","static_cast","struct",
"typeid",
"template","true","typename",
"typedef",
"thread_local",
"this",
"throw",
"try",
"unsigned",
"using",
"union",
"void",
"volatile",
"virtual",
"while",
"wchar_t",
"xor_eq",
"xor",
]

# シンプレックス法パラメータ
$MAX_LOOP = 100 # 最大反復回数

# シンプレックス法
def simplex_method(st)
    max_row    = st.size-1
    max_column = st[0].size-1
    work       = nil
    new_st     = Marshal.load(Marshal.dump(st))
    for count in 1..$MAX_LOOP
        # Step1:ピボット列を求める。
        pivot_column = st[1].index(st[1][1..-2].min)
        if st[1][pivot_column] == 0 then # 解あり
            return st,0
        end
        
        # Step2:ピボット行を求める。
        min_constant = nil
        pivot_row    = nil
        max_row.times{|r|
            if st[r+1][pivot_column] > 0 then
                work = st[r+1][-1]/(st[r+1][pivot_column].to_f)
                if min_constant == nil or min_constant >= work then
                    min_constant = work
                    pivot_row    = r+1
                end
            end
        }
        if pivot_row == nil then # 解なし
            return st,-1
        end
        
        # Step3:ピボット行以外の全要素について、st[r][c] = st[r][c]-st[ピボット行][c]×st[r][ピボット列]/st[ピボット行][ピボット列]
        #       ピボット行の全要素について、st[ピボット行][c] = st[ピボット行][c]/st[ピボット行][ピボット列]
        pivot  = st[pivot_row][pivot_column].to_f
        max_row.times{|r|
            if r+1 != pivot_row then
                work = st[r+1][pivot_column]/pivot
                max_column.times{|c|new_st[r+1][c+1] -= st[pivot_row][c+1]*work}
            else
                max_column.times{|c|new_st[r+1][c+1] /= pivot}
            end
        }
        new_st[pivot_row][0],new_st[0][pivot_column] = new_st[0][pivot_column],new_st[pivot_row][0]
        st = new_st
    end
    
    if st[1][pivot_column] == 0 then # 解あり
        return st,0
    else                             # 反復回数オーバー
        return st,-2
    end
    
end

# シンプレックス表作成
def create_simplex_tableau(v_list,az_list)
    st = []
    az_keys = az_list.keys.sort
    
    # 0行目
    st1 = ["_Basis"]   # 基底
    az_keys.each{|az|st1 << "x" +az   } # xij:変数
    v_list.each {|v |st1 << "xS"+v    }
    v_list.each {|v |st1 << "x" +v+"T"}
    az_keys.each{|az|st1 << "S" +az   } # Sij:スラック変数
    v_list.each {|v |st1 << "SS"+v    }
    v_list.each {|v |st1 << "S" +v+"T"}
    st1 << "_Constant" # 定数項
    st << st1
    
    # 1行目(目的関数): 最大化 Σxij
    st2 = ["_Object"]  # 目的関数
    st1.each{|s|st2 << (s[0] == "x" ? -1 : 0)}
    st << st2
    
    # 3行目以降(制約条件)
    # 制約条件1: xij ≦ 先頭文字がi,末尾文字がjのワード数
    st1[1..-2].each{|s1|
        if s1[0] == "S" then
            st3 = [s1]
            st1[1..-2].each{|s2|st3 << (s1[1..2] == s2[1..2] ? 1 : 0)}
            st3 << (az_list[s1[1..2]] == nil ? 1 : az_list[s1[1..2]]["WORD"].size) # 定数項
            st << st3
        end
    }
    # 制約条件2: 各頂点の入力量と出力量が同じ
    v_list.each{|v|
        st4 = [v]
        st1[1..-2].each{|s1|
            if s1[0] == "x" then
                if s1[1] == v then
                    st4 << (s1[2] == v ? 0 : -1)
                else
                    st4 << (s1[2] == v ? 1 : 0)
                end
            else
                st4 << 0
            end
        }
        st4 << 0 # 定数項
        st << st4
    }
    # 制約条件3: 始点(S)の出力量は1,終点(T)の入力量は1
    ["S","T"].each{|v|
        st5 = [v]
        st1[1..-2].each{|s1|st5 << ((s1[0] == "x" and (s1[1] == v or s1[2] == v)) ? 1 : 0)}
        st5 << 1 # 定数項
        st << st5
    }
    
    return st
end

# 「頂点リスト」と「ワードの先頭文字と末尾文字の集合」を作成する。
def create_v_az_list(word)
    v_list  = [] # 頂点リスト
    az_list = {} # ワードの先頭文字と末尾文字の集合
    word.each{|w|
        az = w[0]+w[-1]
        if az_list[az] == nil then
            az_list[az] = {"WORD"  => []}
        end
        az_list[az]["WORD"] << w
        v_list += [w[0],w[-1]]
    }
    v_list.uniq!
    v_list.sort!
    
    return v_list,az_list
end

# 最適解より、しりとりで使用する「ワードの先頭文字と末尾文字の部分集合」を作成する
def create_az_subset(ans)
    ans2 = []
    ans.each{|r|
        if r[0][0] == "x" and r[0].size == 3 and r[-1] > 0 then
            ans2 << [r[0][1..2],r[-1].to_i]
        end
    }
    
    return ans2
end

# 閉路の抽出
def detect_loop(ans2,az_list)
    loop_data = [] # 閉路データが格納される
    stock     = [] # 閉路に含まれなかった残ワードが格納される
    ans2.each{|a|
        if az_list[a[0]] != nil then
            stock += az_list[a[0]]["WORD"][0..a[1]-1]
        end
    }
    stock.each{|s|
        if s[0] == s[-1] then
            loop_data << s
        end
    }
    stock -= loop_data
    stock2 = stock
    while stock2.size > 0
        flag = true
        while flag
            flag = false
            stock3 = []
            stock2.each{|s1|
                stock.each{|s2|
                    if s1[-1] == s2[0] then
                        if s1[0] == s2[-1] then
                            loop_data << s1+","+s2
                            delete_list = []
                            stock2.each{|s4|
                                s1.split(",").each{|s3|
                                    if s4.split(",").index(s3) != nil then
                                        delete_list << s4
                                        break
                                    end
                                }
                                if s4.split(",").index(s2) != nil then
                                    delete_list << s4
                                end
                            }
                            stock2 -= delete_list
                            s1.split(",").each{|s3|stock.delete(s3)}
                            stock.delete(s2)
                            flag = true
                            break
                        else
                            stock3 << s1+","+s2
                        end
                    end
                }
                break if flag
            }
        end
        stock2 = stock3
    end
    
    return loop_data,stock
end

# 始点ワードの選択
def select_start_word(ans2,stock)
    start_word = nil
    ans2.each{|a|
        if a[0][0] == "S" then
            stock.each{|s|
                if s[0] == a[0][-1] then
                    start_word = s
                    stock.delete(s)
                    break
                end
            }
            break if start_word != nil
        end
    }
    
    return start_word,stock
end

# 残ワードを連結する
def join_stock_word(word_list,stock)
    while stock.size > 0
        stock.each{|s|
            if word_list[-1] == s[0] then
                word_list += ","+s
                stock.delete(s)
                break
            end
        }
    end
    
    return word_list,stock
end

# 残ワードに閉路を組み込む
def join_loop(word_list,loop_data)
    word_list = word_list.split(",")
    while loop_data.size > 0
        flag = false
        for j in 0..loop_data.size-1
            ld = loop_data[j]
            for i in 0..word_list.size-1
                if word_list[i][-1] == ld[0] then
                    word_list.insert(i+1,ld.split(","))
                    word_list.flatten!
                    loop_data.delete(ld)
                    flag = true
                    break
                end
            end
            break if flag
            loop_data[j] = ld.split(",").rotate.join(",")
        end
    end
    
    return word_list,loop_data
end

#-------------------------------------------------------------------------------------------
# メイン
#-------------------------------------------------------------------------------------------

# 「頂点リスト」と「ワードの先頭文字と末尾文字の集合」を作成する。
v_list,az_list = create_v_az_list(Word)

# 線形計画法により最適解を求める。
simplex_tableau = create_simplex_tableau(v_list,az_list) # シンプレックス表を作成する
ans,status = simplex_method(simplex_tableau)             # シンプレックス法で最適解を求める
                                                         #   ans = 解, status = エラー情報(本プログラムでは、エラー処理は省略)

# 最適解より、しりとりで使用する「ワードの先頭文字と末尾文字の部分集合」を作成する
ans2 = create_az_subset(ans)

# 閉路の抽出
loop_data,stock = detect_loop(ans2,az_list)

# 始点ワードの選択
start_word,stock = select_start_word(ans2,stock)

# 残ワードを連結する
word_list,stock = join_stock_word(start_word,stock)

# 残ワードに閉路を組み込む
result,loop_data = join_loop(word_list,loop_data)

# 解出力
print result.join("\n"),"\n"


以上、今回の出題は本当に寄稿者である私自身が大変勉強になる展開となりました。頂いた回答を紹介することで、この驚きを読者の皆さんと共有できると思うと、本当に嬉しい気持ちでいっぱいです。それでは、また機会があればお会いしましょう。

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

CodeIQ中の人後記:
「爽やか」って秋の季語らしいですよ。今朝、知りました。
秋は爽やか、もこみちは爽やか、よって、もこみちは秋男になるんですかね、三段論法的に(違

エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る