全ての選出と交換に渡る全ての敵の組み合わせを計算 その10

ダム問題について考えていたところ、そういや1つの敵のエントリーの決定範囲には同じ種族が複数存在しないことが利用できるんじゃないかと思いつきました。
つまり、ダム問題においては、「グループAの各ダムとつながっている水道局はそれぞれ高々1個」としていいということ。その前提付きならカバーできる水道局の個数についての貪欲法でもうまくいくんじゃないかとやってみたところ、100個のランダムなケースで正しい結果が出ました。

• factory-predictor/dam.rb at master · oupo/factory-predictor · GitHub

これを利用して、1戦分の敵の組み合わせを計算するプログラムを書きました。

ところで、この記事の先頭の行を書いたときに、「あっ、ランクが大きくなると準伝説が出てくるので"1つの敵においてエントリーの決定範囲には同じ種族が複数存在しない"は成立しないじゃん！」と気がつきました…orz

def predict0(prng, skipped, chosen)
  if chosen.length == nParty
    return [chosen].to_set
  end
  # 3つのアイテムと種族を選んでskippedをカバーすることができないなら、
  # skippedの全エントリーがplayersと衝突するような3つのエントリーplayersは
  # 存在しないということなので、このルートはありえないとみなし空集合を返す
  if not coverable?(skipped)
    return [].to_set
  end
  prngp, x = choose_entry(prng)
  if x.collides_within?(chosen)
    # 既に採用済みの場合
    predict0(prngp, skipped, chosen)
  elsif skipped.include?(x)
    # まったく同じエントリをスキップしたことがある場合
    predict0(prngp, skipped, chosen)
  else
    result1 = predict0(prngp, skipped, chosen + [x])
    result2 = predict0(prngp, skipped + [x], chosen)
    result1 + result2
  end
end

# アイテムと種族をそれぞれ3つずつ適当に選べば、それらでentriesをカバーできるかを判定する
def coverable?(entries)
  coverd = Set.new
  selected_items = Set.new
  all_items = entries.map(&:item).to_set
  linked = Hash.new
  entries.each do |entry|
    (linked[entry.item] ||= Set.new).add entry
  end

  # カバーできるエントリーの個数についての貪欲法でアイテムを3つ選ぶ
  nParty.times do |i|
    items = all_items - selected_items
    break if items.empty?
    item = items.max_by {|item|
      (linked[item] - coverd).size
    }
    selected_items.add item
    coverd += linked[item]
  end
  # 残っているエントリーが3つ以下なら、それらの種族3つ選べばすべてカバーできることになる
  (entries.to_set - coverd).size <= 3
end