#! /usr/bin/ruby

# LasBabasDelDiablo
# solution to the POTM contest 09/2005 "Glossy"
#
# (c) MMV Sven Reichard
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the 
# Free Software Foundation, Inc.
# 51 Franklin Street, Fifth Floor
# Boston, MA  02110-1301, USA.
#

require("timeout")

AspectRatioTolerance = 0.02

Debug = false

module Geometry
  def Geometry.aspectRatio x, y
    if x < y
      1.0*y/x
    else
      1.0*x/y
    end
  end
end

class Box

  def initialize left=0, bottom=0, right=0, top=0
    if left > right
      left,right = right,left
    end
    if top < bottom 
      top, bottom = bottom, top
    end
    @left = left
    @bottom = bottom  
    @right = right
    @top = top
  end
  
  
  attr_accessor :left
  attr_accessor :bottom
  attr_accessor :top
  attr_accessor :right

  def width
    right-left
  end
  def width= aNumber
    right = left + aNumber
  end
  def height
    top-bottom
  end
  def height= aNumber
    top = bottom + aNumber
  end
  def area
    width * height
  end
  
  def aspectRatio
    return Geometry.aspectRatio(width, height)
  end
  
  def intersects anotherBox 
    return false if bottom >= anotherBox.top
    return false if top <= anotherBox.bottom
    return false if left >= anotherBox.right
    return false if right <= anotherBox.left 
    true
  end
  
  def contains anotherBox
    return false if anotherBox.top > top
    return false if anotherBox.right > right
    return false if anotherBox.left < left
    return false if anotherBox.bottom < bottom
    true
  end
  
  def flip
    bottom, left = left, bottom
    top, right = right, top
  end

end  


class Photo
  
   def Photo::fromString( aString )
     md = /(\w+)\s+(\d+)\s+(\d+)/.match( aString)
     result = self.new(md[2].to_i,md[3].to_i, md[1])
     result
   end # Photo::fromString

  def initialize( width, height, name="" )
    @width = width
    @height = height
    @name = name
  end # initialize

  attr_reader :width, :height, :name
  
  def aspectRatio
    return Geometry.aspectRatio( width, height)
  end
  
  attr_accessor :placement
   
  def placementString
    string = name + " " +
             placement.width.to_s + 
                       " " + placement.height.to_s +
                                       " " + placement.left.to_s +
                                                       " " + placement.bottom.to_s
  end # placementString
   
end # class Photo

class Problem
  def initialize
    @photos = Array.new
  end # initialize

  attr_reader :photos

  def numberOfPhotos
    @photos.size
  end # numberOfPhotos

  attr_accessor :page  

  def addPhoto (photo)
    @photos.push(photo)
  end # addPhoto

  def photo(which)
    @photos[which]
  end # photo

  def photoByName name
    @photos.detect{|photo| photo.name == name}
  end # photoByName

  def read( filename )
    IO.foreach(filename) { |line |
      @photos.push(Photo.fromString(line))
    }
    @page = @photos.shift
    @page.placement = Box.new(0, 0, @page.width, @page.height)
  end # read

  def solutionString
    result = String.new
    @photos.each{ |photo|
       result += photo.placementString + "\n"
    }
    result
  end # solutionString

  def minimalArea
    page.placement.area*0.01
  end  # minimalArea

  def validSolution?
    @photos.each do |photo|
      if photo.placement == nil
        #print "no placement"
        return false
      end
      if photo.placement.area < minimalArea
        #print photo.name, ": minimal! ", photo.aspectRatio, "\n"
        return false;
      end
      if not @page.placement.contains(photo.placement)
        #print "not contained!\n"
        return false;
      end
      if (photo.aspectRatio - photo.placement.aspectRatio).abs >
          AspectRatioTolerance
        #print photo.name, ": aspect ratio!\n"
        #print "should be ", photo.aspectRatio, "\n"
        #print "is ", photo.placement.aspectRatio, "\n"
        box = photo.placement
        #print box.left, ",", box.bottom, " -- ", box.right, ", ", box.top, "\n"
        return false;
      end
    end
    0.upto(@photos.size-1) do |i|
      (i+1).upto(@photos.size-1) do |j|
        if photo(i).placement.intersects(photo(j).placement)
          #print i," intersects ", j
          return false;
        end
      end
    end
    true
  end # validSolution?

  def areaNotCovered 
    result = @page.placement.area
    @photos.each do |i|
      result -= i.placement.area
    end
    result
  end # areaNotCovered

  def tieBreaker
    sizes = @photos.collect{|photo| photo.placement.area}
    difference = sizes.max-sizes.min
  end # tieBreaker
  
  def saveSolution
    @bestSolution = @photos.collect{|photo| photo.placement}
    @bestArea = areaNotCovered
    @bestTiebreaker = tieBreaker
    #print areaNotCovered, "/", tieBreaker, "\n"
  end

  def proposeSolution
    if !validSolution?
      #print "    not valid!\n"
      return
    end
    if @bestSolution == nil
      saveSolution
      return
    end
    if areaNotCovered > @bestArea
      return
    end
    if (areaNotCovered == @bestArea) && (tieBreaker >= @bestTiebreaker)
      return
    end
    saveSolution
  end # proposeSolution

  def applyBest
    0.upto(@photos.size-1) do |i|
      @photos[i].placement = @bestSolution[i]
    end
  end # applyBest

end # class Problem

class Subproblem < Problem
  def initialize problem, page
    @problem = problem
    @photos = problem.photos.select{|x| x.placement == nil}
    @page = page
  end
  def proposeSolution
    @problem.proposeSolution
  end
  def applyBest
    @problem.applyBest
  end
  def validSolution?
    @problem.validSolution
  end
  def solutionString
    @problem.solutionString
  end
end

class Column

  def initialize
    @ratios = Array.new
    @flipped = Array.new
    @names = Array.new
  end
  
  def clone
    result = Column.new
    result.ratios = @ratios.clone
    result.flipped = @flipped.clone
    result.names = @names.clone
    result
  end

  def numberOfPhotos
    @ratios.size
  end

  attr_accessor :ratios, :flipped, :names

  def aspectRatio
    result = 0.0
    0.upto(@ratios.size-1) do |i|
      result += getActualRatio(i)
    end
    result
  end

  def add(aRatio, aName)
    @ratios.push aRatio
    @names.push aName
    @flipped.push false
  end

  def remove
    @ratios.pop
    @names.pop
    @flipped.pop
  end
  def isFlipped anInteger
    @flipped[ anInteger ]
  end

  def flip anInteger
    @flipped[ anInteger ] = ! @flipped[ anInteger ]
  end

  def getActualRatio anInteger
    if isFlipped anInteger
      1.0/@ratios[anInteger]
    else
      @ratios[anInteger]
    end
  end

  def maximalRatio
    result = 0.0
    ratios.each do |x|
      result += x
    end
    result
  end

  def minimalRatio
    result = 0.0
    ratios.each do |x|
      result += 1.0/x
    end
    result
  end
end

class ColumnSet

  def initialize  numberOfColumns=0
    @columns = Array.new(numberOfColumns)
    0.upto(numberOfColumns-1) do |i|
      @columns[i] = Column.new
    end
  end

  
    

  def clone
    result = ColumnSet.new(@columns.size)
    result.columns = @columns.collect{|x| x.clone}
    result
  end

  attr_accessor :columns

  def flip
    @flipped = !@flipped
  end

  def aspectRatio
    result = 0.0
    columns.each do |column|
      result += 1.0/column.aspectRatio
    end
    result = 1.0/result
  end

  def maximalAspectRatio
    aspectRatio
  end

  def minimalAspectRatio
    @columns.each do |column|
       0.upto(column.numberOfPhotos-1) do |i|
         column.flip i
       end
    end

    result = aspectRatio
    @columns.each do |column|
       0.upto(column.numberOfPhotos-1) do |i|
         column.flip i
       end
    end
    result
  end
  def addPhotos photos
    photos = photos.sort{|x,y| y.aspectRatio<=>x.aspectRatio}
    photos.each do | aPhoto |
      minColumn = columns.min{|x,y| x.aspectRatio <=> 
        y.aspectRatio}
      minColumn.add(aPhoto.aspectRatio, aPhoto.name)
    end
  end
  
  def increaseHeight width, heights, column
    0.upto(heights.size-1) do |i|
      heights[i] += 1
      ratio = Geometry::aspectRatio heights[i], width
      wantedRatio = column.ratios[i]
      if (ratio-wantedRatio).abs < AspectRatioTolerance then
        return true
      end
      heights[i] -= 1
    end
    false
  end

  def decreaseHeight width, heights, column
    0.upto(heights.size-1) do |i|
      heights[i] -= 1
      ratio = Geometry::aspectRatio heights[i], width
      wantedRatio = column.ratios[i]
      if (ratio-wantedRatio).abs < AspectRatioTolerance then
        return true
      end
      heights[i] += 1
    end
    false
  end

  def reduceMax width, heights, column
    maxpos = 0
    0.upto( heights.size-1 ) do |i|
      if heights[i] > heights[maxpos] then
        maxpos = i
      end
    end
    wantedRatio = column.ratios[maxpos]
    reducedRatio = Geometry::aspectRatio(heights[maxpos]-1, width)
    if (wantedRatio-reducedRatio).abs > AspectRatioTolerance then
      return false
    end
    0.upto(heights.size-1) do |i|
      if i == maxpos then
        next
      end
      if heights[i] > heights[maxpos]-2 then
        next
      end
      wantedRatio = column.ratios[i]
      increasedRatio = Geometry::aspectRatio(heights[i]+1, width)
      if (wantedRatio-increasedRatio).abs > AspectRatioTolerance then
        next
      end
      #print "->reducing!\n"
      heights[maxpos] -= 1
      heights[i] += 1
      return true
    end
    return false
  end

  def increaseMin width, heights, column
    maxpos = 0
    0.upto( heights.size-1 ) do |i|
      if heights[i] < heights[maxpos] then
        maxpos = i
      end
    end
    wantedRatio = column.ratios[maxpos]
    reducedRatio = Geometry::aspectRatio(heights[maxpos]+1, width)
    if (wantedRatio-reducedRatio).abs > AspectRatioTolerance then
      return false
    end
    0.upto(heights.size-1) do |i|
      if heights[i] < heights[ maxpos]+2 then
        next
      end
      wantedRatio = column.ratios[i]
      increasedRatio = Geometry::aspectRatio(heights[i]-1, width)
      if (wantedRatio-increasedRatio).abs > AspectRatioTolerance then
        next
      end
      #print "->reducing!\n"
      heights[maxpos] += 1
      heights[i] -= 1
      return true
    end
    return false
  end

  def selectDimensions  problem
    width = problem.page.width
    height = problem.page.height
    sum = 0.0
    inverses = columns.collect{|x| 1/x.aspectRatio}
    inverses.each do |x|
      sum += x
    end
    widths = inverses.collect{|x| (width*x/sum).round}
    total = 0
    widths.each do |x| 
      total += x
    end
    widths[0] -= total-width
    heights = Array.new
    0.upto(columns.size-1) do |i|
      sum = 0
      heights[i] = Array.new
      0.upto(columns[i].numberOfPhotos-1) do |x|
        h = (widths[i]*columns[i].getActualRatio(x)).round
        heights[i].push(h)
        sum += h
      end

      while sum < height do
        if not increaseHeight widths[i], heights[i], columns[i] then
          break
        end
        sum += 1
      end

      while sum > height do
        if not decreaseHeight widths[i], heights[i], columns[i] then
          break
        end
        sum -= 1
      end

      if sum > height then
        #puts "too high"
        return
      end
      while reduceMax(widths[i], heights[i], columns[i]) ||
             increaseMin(widths[i], heights[i], columns[i]) do
        #nothing
      end
    end
  
    left = 0

    0.upto(columns.size-1) do |i|
      right = left + widths[i]
      bottom = 0

      0.upto(heights[i].size-1) do |j|
        top = bottom + heights[i][j]
        box = Box.new left, bottom, right, top
        photo = problem.photoByName(columns[i].names[j])
        photo.placement = box
        bottom = top
      end
      
      left = right
    end
    #print "proposing\n"
    problem.proposeSolution
  end
end

class Backtrack
  def initialize wantedRatio, columnSet, problem
    @bestResult = 100.0
    @bestDifference = 100.0
    @nodesSearched = 0
    @wantedRatio = wantedRatio
    @columnSet = columnSet
    @done = false
    @problem = problem
  end
  def columns
    @columnSet.columns
  end
  
  attr_reader :nodesSearched, :bestResult, :bestSolution
  def backtrack( currentColumn, currentPicture)
    @nodesSearched += 1
    difference = ((@columnSet.aspectRatio)-@wantedRatio).abs
    #print difference, "\n"
    if (@columnSet.aspectRatio) < @wantedRatio-@bestDifference
      #@columnSet.selectDimensions @problem
      return
    end
    if difference < @bestDifference 
      @columnSet.selectDimensions @problem
      @bestResult = @columnSet.aspectRatio
      #print "wanted: ", @wantedRatio, "\n"
      #print "best: ", @bestResult, "\n"
      #print "difference: ", difference, "\n"
      @bestDifference = difference
      @bestSolution = @columnSet.clone
      #@bestSolution.selectDimensions @problem
      
      if difference < 0.002
        @done = true
      end
    end
    if @columnSet.aspectRatio < @wantedRatio - @bestDifference

      return
    end
    0.upto(columns.size-1) do |i|
      next if i < currentColumn
      0.upto(columns[i].numberOfPhotos-1) do |j|
        next if i == currentColumn && j <= currentPicture
        columns[i].flip(j)
        backtrack( i, j)
        columns[i].flip(j)
        return if @done
      end
    end
  end
end

class PartitionGenerator
  
  def initialize ratios, names, problem
    @ratios = ratios
    @names = names
    @columns = ColumnSet.new
    @nrSolutions = 0
    @problem = problem
  end
  
  def recursion i
    
    if i >= @ratios.size
      @nrSolutions += 1
      wantedRatio = 1.0*@problem.page.height/@problem.page.width
      max = @columns.maximalAspectRatio
      min = @columns.minimalAspectRatio

      if min > wantedRatio || max < wantedRatio
        return
      end

      bck = Backtrack.new( wantedRatio, @columns, @problem )
      bck.backtrack( -1, -1 )
      columnSet = bck.bestSolution

      if columnSet == nil
        return
      end
      
      columnSet.selectDimensions  @problem
      return
    end
    
    @columns.columns.each do |col|
      if col.numberOfPhotos < 6 then
        col.add @ratios[i], @names[i]
        recursion i+1
        col.remove
      end
    end
    
    newColumn = Column.new
    @columns.columns.push newColumn
    newColumn.add @ratios[i], @names[i]
    recursion i+1
    @columns.columns.pop
        
  end

  def run
    recursion 0
    #print "found ", @nrSolutions, "solutions\n"
  end
  
end

def solve numberOfColumns, problem
  #print "solve ", numberOfColumns, "\n"
  wantedRatio = problem.page.height/problem.page.width
  columnSet = ColumnSet.new numberOfColumns
  columnSet.addPhotos problem.photos
  max = columnSet.maximalAspectRatio
  min = columnSet.minimalAspectRatio
  
  if min > wantedRatio || max < wantedRatio
    return
  end
  #print min, " -- ", max, "\n"
  bck = Backtrack.new( wantedRatio, columnSet, problem )
  bck.backtrack( -1, -1 )
  #puts "backtrack done"
  
end

def solveHeuristically problem
  photos = problem.photos.sort{|x,y| y.aspectRatio <=> x.aspectRatio}
  wantedArea =problem.page.placement.area / photos.size
  heights = photos.collect{ |x| Math::sqrt(wantedArea*x.aspectRatio)}
  columns = ColumnSet.new
  column = Column.new
  totalHeight = 0
  wantedHeight = problem.page.height
  0.upto(photos.size-1) do |i|
    if column.numberOfPhotos > 0 && totalHeight + heights[i] > wantedHeight
      columns.columns.push column
      column = Column.new
      totalHeight = 0
      #puts
    end
    column.add photos[i].aspectRatio, photos[i].name
    totalHeight += heights[i]
    #print photos[i].aspectRatio, "\n"
  end
  if column.numberOfPhotos > 0
    columns.columns.push column
  end
  #print "resulting: ", columns.aspectRatio, "\n"
  columns.selectDimensions problem
end

# main program
if $0 == __FILE__
  problem = Problem.new

  begin
    timeout(59) do # raise signal after 59 seconds

      problem.read(ARGV[0])

      solveHeuristically problem
      
      ##############
      #problem.photos[0].placement = Box.new(0, 1000, 1000, 1100)
      #page = Photo.new 1000, 1000
      #page.placement = Box.new(0, 0, 1000, 1000)
      #problem = Subproblem.new(problem, page)
      #puts problem.photos.size
      #problem = constructSubproblem problem
      ################

      maxNumber = 5

      if maxNumber > problem.photos.size
        maxNumber = problem.photos.size
      end

      # heuristic partition into columns
      1.upto(maxNumber) do |numberOfColumns|
        solve numberOfColumns, problem
      end

      # complete search for partitions, if time allows
      ratios = problem.photos.collect{|x| x.aspectRatio}
      names = problem.photos.collect{|x| x.name}
      partitions = PartitionGenerator.new ratios, names, problem
      partitions.run
      
    end # timeout

  rescue TimeoutError
  # nothing
  end
  
  problem.applyBest
  print problem.solutionString

end