From: James Edward Gray II <james@...>
Date: 2006-01-20T08:11:29+09:00
Subject: Re: Ruby Quiz #62

On Jan 19, 2006, at 4:57 PM, James Edward Gray II wrote:

> I'm actually wondering if the algorithm couldn't be adapted to  
> handle this.  I believe it's possible.  The placement of the first  
> block ruins 6 other squares (because of padding).  When placed  
> correctly, it only ruins three.  I bet the code could be made to  
> spot this...

This version of the code seems to fix at least this case:

Neo:~/Desktop$ cat bug_example.txt
3x6
2x3 1x3 1x3
Neo:~/Desktop$ ruby pack.rb bug_example.txt

###
###
___
###
___
###
Neo:~/Desktop$ cat pack.rb
class Array
   def delete_first item
     delete_at index(item)
   end

   def rotate
     d = dup
     d.push d.shift
     d
   end
end

class Trunk
   def initialize(w,h)
     @w = w
     @h = h
     @items = []
     @rows = (1..@h+2).map{ "_"*(@w+2) }
   end

   def add box
     # try it both ways
     possibles = [try_adding(box), try_adding(box.rotate)].compact
     # make sure we found a way
     return if possibles.empty?
     # use the best option we found
     score, rows, box = possibles.max { |a, b| a.first <=> b.first }
     @rows            = rows
     @items           = box
     true
   end

   def try_adding box
     boxrow = "_"*(box[0]+2)
     @rows.each_with_index{|r,i|
       break if i > @rows.size - (box[1]+2)
       next unless r.include?(boxrow)
       idxs = @rows[i+1, box[1]+1].map{|s| s.index boxrow }
       next unless idxs.all?
       idx = idxs.max
       next unless @rows[i, box[1]+2].all?{|s| s[idx,boxrow.size] ==  
boxrow }
       # modify the rows
       rows = @rows.map { |row| row.dup }
       rows[i+1, box[1]].each{|s|
         s[idx+1, box[0]] = "#" * box[0]
       }
       # score the remaining open space
       score = rows[1..-2].map { |row| row[/_(_+)/, 1] }.compact.
                           map { |open| open.size }.inject { |sum, n|  
sum + n }
       # return the score and the things we would need to change
       return score, rows, box
     }
     nil
   end

   def empty?
     @items.empty?
   end

   def to_s
     @rows[1..-2].map{|r|r[1..-2]}.join("\n")
   end
end

trunk = gets.strip.split("x").map{|i| i.to_i}
boxes = gets.strip.split(" ").map{|s| s.split("x").map{|i| i.to_i} }

boxes = boxes.sort_by{|b| b.inject{|f,i| f*i} }.reverse
trunks = [Trunk.new(*trunk)]
until boxes.empty?
   fitting = boxes.find{|box| trunks.last.add box }
   if fitting
     boxes.delete_first fitting
   elsif trunks.last.empty?
     raise "Can't fit #{boxes.inspect} into the trunk"
   else
     trunks << Trunk.new(*trunk) unless boxes.empty?
   end
end
puts
puts trunks.join("\n\n")

James Edward Gray II