CodeIQ 863 TicketGobble Problem

answer.txt

62 Afghanistan Angola Anguilla Antarctica Austria Azerbaijan Bangladesh Barbados Belarus Belize Botswana Burundi Canada Chad China Cyprus Denmark Ecuador Egypt Eritrea Ethiopia Fiji Finland Germany Ghana Greece Guadeloupe Guyana Jamaica Jersey Kiribati Kuwait Kyrgyzstan Libya Liechtenstein Macao Malawi Malaysia Maldives Martinique Montenegro Montserrat Namibia Narnia Nepal Nicaragua Niger Oman Poland Portugal Rwanda Samoa Seychelles Singapore Slovakia Slovenia Sudan Sweden Switzerland Tokelau Turkey Uganda
ENV: Ruby
POINT: 重複を消していけばよい

★解き方
以下のような形で日程の重なっているチケットを消していく

- 重複タイプ1: チケットの出発日から帰国日までの期間を完全に含む他のチケットがある
チケットA      D----A       D: 出発日、A: 帰国日
チケットB   D------------A
--  重複の解消方法: 期間の短い方を残して長い方を消す(上の例ではチケットBを消す)
---   短い方を残した方が、さらに他のチケットと重なる可能性が低くなるため

- 重複タイプ2: チケットの出発日、帰国日がそれぞれ別のチケットと重なっている場合
チケットA      D------A       D: 出発日、A: 帰国日
チケットB   D----A
チケットC           D-------A
--  重複の解消方法: チケットAを消す
---   チケットAを採用するとチケットB,Cを両方あきらめなければならないが、AをあきらめればB,Cは両方生かすことができる
---   このとき、チケットBとCが重なっていると、どちらか一方しか行けないため、このタイプの重複としてカウントしないようにする

- 重複タイプ3
--  以上の2タイプの重複によってチケットを消しても、まだ重複が残る場合、どれかひとつを任意に選んでよい
チケットA      D------A       D: 出発日、A: 帰国日
チケットB   D----A

★想定した罠
- 2/29日がある
--  あった。想定済
- カレンダーが地球でない(13月2日や8月35日がある)
--  なかった
- 新年を海外で過ごすチケットがある(12月に出発して1月に帰国するなど)
--  なかった。計算が楽だった
- 国名に空白を含む
--  なかった。parseが楽だった
- 実在しない国がある
--  Antarctica 南極に飛行機で行けるのかなあ
--  Narnia 行きたいですね
- 行きたい国がない
--  英国も米国も韓国もニュージーランドもチェコもイランもないですね
--  外した基準はわかりません(空白を含む国名だとするとチェコやイランが説明できない)

★感想
- リベンジというからには罠があると思ったのですが、2/29の存在に気づかず3/1と扱っても解ける問題でした
- 正解をすべて生成する、もっとも旅行期間が長い解を得る、のはめんどくさそうだったのでやめました

★プログラム
- しめ切り後にgistで公開する予定です。

以上

solve.rb

# CodeIQ Q863 ticketgobble

class Day
  MON_DAYS = [31,29,31,30,31,30,31,31,30,31,30,31]
  MON_ACC = (1..12).map{|m| MON_DAYS[0,m-1].inject(0, &:+)}

  attr_accessor :mon, :day

  def initialize(other = nil, mon: nil, day: nil, day_of_year: nil)
    if other
      @mon = other.mon
      @day = other.day
    elsif mon && day
      @mon = mon.to_i
      @day = day.to_i
      raise if @mon < 1 || @mon > 12
      raise if @day > MON_DAYS[@mon - 1]
    elsif day_of_year
      self.day_of_year = day_of_year
    else
      raise
    end
  end

  def day_of_year
    MON_ACC[mon.to_i - 1] + day.to_i - 1
  end
  alias_method :d, :day_of_year
  def day_of_year=(day)
    m = 1; day += 1
    MON_DAYS.each{|d| if day > d then m += 1; day -= d else break end }
    self.mon = m
    self.day = day
  end
  def to_s
    "#{mon}/#{day}"
  end
end

class Ticket
  attr_accessor :country, :from, :to

  def initialize(country: country, from: from, to: to)
    self.country = country
    self.from = Day.new(from)
    self.to   = Day.new(to)
  end
  def self.parse(line)
    country, fmon, fday, tmon, tday = line.split(%r|[\s\-/]|)
    from = Day.new(mon: fmon, day: fday)
    to   = Day.new(mon: tmon, day: tday)
    if from.to_s != Day.new(day_of_year: from.d).to_s
      raise "#{country} from date illegal #{from.to_s} vs #{Day.new(day_of_year: from.d).to_s}"
    end
    if to.to_s != Day.new(day_of_year: to.d).to_s
      raise "#{country} to date illegal #{to.to_s} vs #{Day.new(day_of_year: to.d).to_s}"
    end
    if from.d == to.d
      raise "#{country} from == to: #{line}"
    elsif from.d > to.d
      raise "#{country} from > to: #{line}"
    end
    new(country: country, from: from, to: to)
  end
  def to_s
    "#{country} #{from}-#{to}"
  end
end

class TicketCollection
  def initialize
    @by_country = {}
    @by_day = (1..366).map{[]}
  end
  def add(ticket)
    @by_country[ticket.country] = ticket
    (ticket.from.d..ticket.to.d).each {|d| @by_day[d] << ticket}
  end
  alias_method :<<, :add
  def delete(ticket)
    if @by_country.delete(ticket.country)
      (ticket.from.d..ticket.to.d).each do |d|
        @by_day[d].delete_if {|t| t.country == ticket.country}
      end
    end
  end
  def [](index)
    case index
    when String
      @by_country[index]
    when Integer
      @by_day[index]
    when Day
      @by_day[index.d]
    end
  end
  def all(&block)
    @by_country.values.sort_by {|t| t.country}
  end
end

def eliminate_simple_overlaps(tickets)
  366.times do |d|
    ts = tickets[d]
    if ts.size >= 2
      to_delete = []
      ts.sort_by {|t| t.to.d - t.from.d}.permutation(2) do |a, b|
        next if to_delete.include?(a) || to_delete.include?(b)
        if b.from.d <= a.from.d && a.to.d <= b.to.d
          to_delete << b
          # puts "Delete #{b.country} by #{a.country}"
        end
      end
      to_delete.each {|t| tickets.delete(t)}
    end
  end
end

def eliminate_hairy_overlaps(tickets)
  366.times do |d|
    ts = tickets[d]
    if ts.size >= 2
      to_delete = []
      ts.each do |t|
        from_contained = tickets[t.from.d] - [t]
        to_contained   = tickets[t.to.d]   - [t]
        from_contained.product(to_contained).each do |a, b|
          next if a === b
          # reject if a and b intersect
          next if [a.from.d, b.from.d].max <= [a.to.d, b.to.d].min
          # puts "Delete #{t.country} because its covered by #{a.country} and #{b.country}"
          to_delete << t
          break
        end
      end
      to_delete.each {|t| tickets.delete(t)}
    end
  end
end

def choose_first(tickets)
  366.times do |d|
    ts = tickets[d].dup
    if ts.size >= 2
      # remove all but first
      ts.shift
      ts.each {|t| tickets.delete(t)}
    end
  end
end

def main
  tickets = TicketCollection.new
  IO.foreach("problem/tickets.txt") do |line|
    tickets << Ticket.parse(line)
  end

  eliminate_simple_overlaps(tickets)
  eliminate_hairy_overlaps(tickets)
  choose_first(tickets)

  366.times do |d|
    tickets[d].size >= 2 and puts "#{Day.new(day_of_year: d)}: #{tickets[d].size} #{tickets[d].map{|t| t.country} * ' '}"
  end

  puts "#{tickets.all.size} #{tickets.all.map(&:country) * ' '}"
end

main if $0 == __FILE__