ticketgobble

solver.rb

#!/usr/bin/env ruby
# coding: utf-8

class SimpleDate
  include Comparable

  # フォーマットは"mm/dd"
  def initialize(format)
    month, day = format.split('/').map(&:to_i)
    @month = month
    @day = day
  end

  attr_reader :month, :day

  def <=>(other)
    result = self.month <=> other.month
    if result == 0
      result = self.day <=> other.day
    end
    return result
  end
end

class Ticket

  # フォーマットは"Name mm/dd-mm/dd"
  def self.from_format(format)
    name, term = format.split(' ')
    from, to = term.split('-').map{|day| SimpleDate.new(day)}
    return Ticket.new(name, from, to)
  end
  
  def initialize(name, from, to)
    @name = name
    @from = from
    @to = to
  end

  attr_reader :name, :from, :to

  def previous_to?(other)
    return self.to < other.from
  end
end

class TicketGraph

  class TicketNode
    def initialize(ticket, parent=nil, count=0)
      @ticket = ticket
      @children = Array.new
      @parent = parent
      @count = count
    end

    def update_parent(parent)
      @parent = parent
      @count = parent.count + 1

      # 子に変更を伝播させる
      @children.each do |child|
        if child.count <= @count
          child.update_parent(self)
        end
      end
    end

    attr_reader :ticket, :children, :parent, :count
  end

  @@start = TicketNode.new(Ticket.new("START", SimpleDate.new("0/0"), SimpleDate.new("0/0")))
  @@node_list = Array.new
  @@node_list.push @@start

  # チケットを追加し、グラフ構造を更新する
  def self.add(ticket)
    new_node = TicketNode.new(ticket, @@start, 1)

    # まず、後続するチケットを子として追加しておく
    # （自分自身の親の変更を伝播させるため）
    @@node_list.each do |node|
      if new_node.ticket.previous_to?(node.ticket)
        new_node.children.push node
      end
    end

    # 先行するチケットに自分を子として追加させつつ、
    # 適切な親を探す
    @@node_list.each do |node|
      if node.ticket.previous_to?(new_node.ticket)
        node.children.push new_node
        if new_node.count <= node.count
          new_node.update_parent(node)
        end
      end
    end

    @@node_list.push new_node
  end

  def self.print
    @@node_list.each do |node|
      puts "[#{node.ticket.name}]"
      puts "  parent  : #{node.parent ? node.parent.ticket.name : '(empty)'}"
      puts "  count   : #{node.count}"
      puts "  children: #{node.children.map{|child| child.ticket.name}.join(', ')}"
    end
  end

  # 最大枚数になるチケットのリストを返す
  def self.get_max_tickets
    max_node = @@start
    @@node_list.each do |node|
      if node.count > max_node.count
        max_node = node
      end
    end

    max_tickets = Array.new
    node = max_node
    loop do
      if node == @@start
        break
      else
        max_tickets.unshift node.ticket
        node = node.parent
      end
    end

    return max_tickets
  end
end

File.open(ARGV[0]) do |file|
  file.each do |line|
    format = line.chomp
    ticket = Ticket.from_format(format)
    p ticket
    TicketGraph.add(ticket)
    TicketGraph.print # for debug
  end
end

max_tickets = TicketGraph.get_max_tickets
puts "max size: #{max_tickets.size}"
max_tickets.each do |ticket|
  p ticket
end

# 解答用出力
puts "#{max_tickets.size} #{max_tickets.sort_by{|ticket| ticket.name}.map(&:name).join(' ')}"