Billboards - Facebook Hacker Cup 2012 Qualification Round

billboards.rb

# coding: utf-8

class Billboards
  def initialize(input)
    lines = []
    open(input) do |f|
      lines = f.readlines.map{|l|l.chomp!}
    end
    @num = lines.shift.to_i
    @case = []
    lines.each_with_index do |line,i|
      tokens = line.split
      @case[i] = { :w => tokens.shift.to_i, :h => tokens.shift.to_i, :words => tokens }
    end
  end

  def self.conc(co)
    wls = co[:words].map{|word|word.length}
    p max = [[co[:w]/(wls.max), co[:h]].max, Math.sqrt(co[:w]*co[:h]/wls.inject(:+)).to_i].min
    (0..max).each do |i|
      f = max + 1 - i
      p overflow?(f,co[:w],co[:h],wls)
      return f unless overflow?(f,co[:w],co[:h],wls)
    end
  end

  def set_ans
    @ans = @case.map{|v| p v; Billboards.conc v}
  end

  def put_ans(output)
    self.set_ans
    open(output, "w") do |f|
      @ans.each_with_index do |ans, i|
        p "Case #" + (i+1).to_s + ": " + ans.to_s
        f.puts("Case #" + (i+1).to_s + ": " + ans.to_s)
      end
    end
  end

  attr_reader :num, :case, :ans
end

def overflow?(f,w,h,wls)
  max_w = w / f
  max_h = h / f
  a = []
  i = 0
  wls.each do |wl|
    if wl > max_w
      return true
    end
    if a.last.nil? || (a.last + 1 + wl > max_w)
      a << wl
      i += 1
    else
      a[-1] += wl + 1
    end
    if i > max_h
      return true
    end
  end
  false
end

bill = Billboards.new(ARGV[0])
bill.put_ans(ARGV[1])