Forum: Ruby Packing (#62)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-01-13 14:43
(Received via mailing list)
The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ilmari Heikkinen

You're moving. And that means a whole bunch of boxes need to be moved
from the
old place to the new one. You've got a pickup truck to do the moving,
but it can
only hold one vertical level of boxes. The boxes need to be padded with
one unit
worth of foam on each side that's facing another box.

The goal is to minimize the amount of trips you have to do to move all
the
boxes.

The solver program should take two lines of input, first one containing
the
trunk dimensions (e.g. 10x20), and the second one containing all the box
dimensions, separated by spaces (e.g. 1x3 4x8 3x7 9x4 10x14.)

The output of the solver should be ascii art of the trunk packings, with
each
trunkful separated by an empty line.

	Example:
	$ ruby solver.rb
	10x20
	1x3 4x8 3x7 9x4 10x14

	**************.***..
	**************......
	**************.****.
	**************.****.
	**************.****.
	**************.****.
	**************.****.
	**************.****.
	**************.****.
	**************.****.

	*********...........
	*********...........
	*********...........
	*********...........
	....................
	*******.............
	*******.............
	*******.............
	....................
	....................
E20e89d58211a3631842daecc1245de2?d=identicon&s=25 Ilmari Heikkinen (Guest)
on 2006-01-13 16:24
(Received via mailing list)
On 1/13/06, Ruby Quiz <james@grayproductions.net> wrote:
>
> worth of foam on each side that's facing another box.
>
>         Example:
>         $ ruby solver.rb
>         10x20
>         1x3 4x8 3x7 9x4 10x14

Good luck, everyone!

Finding an optimal solution is going to be quite computationally
intensive,
so unoptimal solvers are also welcome.

Checking that the solution you get really is optimal might be a wee bit
hard,
so here's a little program that generates problems with known optimal
solutions (these are without the 1 unit padding though):

$ ruby troublemaker.rb 6x6 2 # 2 6x6 trunks
6x6
4x3 4x3 2x6 4x3 4x3 2x6

$ cat troublemaker.rb
def randomly_cut_up(box)
  if box.min > 3
    cut = 3+rand(box.max-3)
    if box.max == box[0]
      randomly_cut_up([cut, box[1]]) +
      randomly_cut_up([box[0]-cut, box[1]])
    else
      randomly_cut_up([box[0], cut]) +
      randomly_cut_up([box[0], box[1]-cut])
    end
  else
    [box]
  end
end

if __FILE__ == $0
  trunk_size = ARGV[0].split("x").map{|i| i.to_i}
  trunk_count = ARGV[1].to_i

  boxes = []

  (1..trunk_count).each{|i|
    boxes += randomly_cut_up trunk_size
  }

  #puts "requested volume: #{trunk_size[0]*trunk_size[1]*trunk_count}"
  #puts "cut up volume: #{boxes.inject(0){|s,b| s+b[0]*b[1]}}"

  box_str = boxes.map{|box| box.join("x")}.join(" ")
  puts trunk_size.join("x")
  puts box_str
end
8aab717743d4f58a4453adb8b6855e1e?d=identicon&s=25 Robert Retzbach (Guest)
on 2006-01-13 16:27
(Received via mailing list)
Ruby Quiz schrieb:

>
>worth of foam on each side that's facing another box.
>
>	**************.****.
>	*******.............
>	*******.............
>	*******.............
>	....................
>	....................
>
>
>
>
Hello,
this is a interesting quiz, but I am still in the middle to understand
the last! :D

However... I can't access ruby62.html. It's always rewritten to
ruby26.html.
Maybe I stand alone with this problem.

MfG
Retze
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-01-13 16:33
(Received via mailing list)
On Jan 13, 2006, at 9:26 AM, Robert Retzbach wrote:

> However... I can't access ruby62.html. It's always rewritten to
> ruby26.html.
> Maybe I stand alone with this problem.

Are you talking about:

http://www.rubyquiz.com/quiz62.html

It loads fine for me.  Is anyone else seeing this?

The page contains exactly the same information as the email you
quoted though, so you're not missing anything.

James Edward Gray II
8aab717743d4f58a4453adb8b6855e1e?d=identicon&s=25 Robert Retzbach (Guest)
on 2006-01-13 16:39
(Received via mailing list)
Robert Retzbach schrieb:

>> http://www.rubyquiz.com/
>> by Ilmari Heikkinen
>> all the
>>
>>     **************.****.
>>     *******.............
>
> However... I can't access ruby62.html. It's always rewritten to
> ruby26.html.
> Maybe I stand alone with this problem.
>
> MfG
> Retze
>
>
Hmmm,
with Ie it works, maybe I have something in my ff cache.
Nvm then, happy quizzing.
912c61d9da47754de7039f4271334a9f?d=identicon&s=25 unknown (Guest)
on 2006-01-13 17:25
(Received via mailing list)
Are we allowed to rotate boxes?

-mental
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-01-13 17:31
(Received via mailing list)
On Jan 13, 2006, at 10:24 AM, mental@rydia.net wrote:

> Are we allowed to rotate boxes?

You bet.

James Edward Gray II
E20e89d58211a3631842daecc1245de2?d=identicon&s=25 Ilmari Heikkinen (Guest)
on 2006-01-13 17:31
(Received via mailing list)
On 1/13/06, mental@rydia.net <mental@rydia.net> wrote:
> Are we allowed to rotate boxes?
>
> -mental
>
>

Yes.
912c61d9da47754de7039f4271334a9f?d=identicon&s=25 unknown (Guest)
on 2006-01-13 21:17
(Received via mailing list)
Quoting Ruby Quiz <james@grayproductions.net>:

> 	**************.****.
> 	*******.............
> 	*******.............
> 	*******.............
> 	....................
> 	....................

Whoops, this example shows an 8x4 box, not a 9x4 one.

-mental
E20e89d58211a3631842daecc1245de2?d=identicon&s=25 Ilmari Heikkinen (Guest)
on 2006-01-13 22:14
(Received via mailing list)
On 1/13/06, mental@rydia.net <mental@rydia.net> wrote:
> >       **************.****.
> >       *********...........
> >       ....................
> >       *******.............
> >       *******.............
> >       *******.............
> >       ....................
> >       ....................
>
> Whoops, this example shows an 8x4 box, not a 9x4 one.

Actually, there's an 8x4 box and a 9x4 box.

The small width of the characters really is quite confusing,
long lines of asterisks merging into each other
while rows are well separated,
making counting difficult -
a Gestalt law in effect.

</bad poetry>

(=
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-01-13 22:48
(Received via mailing list)
> You're moving. And that means a whole bunch of boxes need to be moved from the
> old place to the new one. You've got a pickup truck to do the moving, but it can
> only hold one vertical level of boxes. The boxes need to be padded with one unit
> worth of foam on each side that's facing another box.
>

regarding padding, is this a valid result?
10x10
5x5 5x5

#####ooooo
#####ooooo
#####ooooo
#####ooooo
#####ooooo
ooooo#####
ooooo#####
ooooo#####
ooooo#####
ooooo#####

i.e: do I need to put a pad in the spot marked with the ?
#####o
#####o
#####o
#####o
#####o
ooooo?
E20e89d58211a3631842daecc1245de2?d=identicon&s=25 Ilmari Heikkinen (Guest)
on 2006-01-13 23:10
(Received via mailing list)
On 1/13/06, Adam Shelly <adam.shelly@gmail.com> wrote:
> #####ooooo
> i.e: do I need to put a pad in the spot marked with the ?
> #####o
> #####o
> #####o
> #####o
> #####o
> ooooo?

Yes, that needs to be padded. Each point in a box should
be >= 1 units from another box.

Good choice of characters btw, works even on fixed-width.
Cff9eed5d8099e4c2d34eae663aae87e?d=identicon&s=25 Jacob Fugal (Guest)
on 2006-01-14 01:44
(Received via mailing list)
On 1/13/06, Ilmari Heikkinen <ilmari.heikkinen@gmail.com> wrote:
> > ooooo#####
> > #####o
> > ooooo?
>
> Yes, that needs to be padded. Each point in a box should
> be >= 1 units from another box.

If you calculate using the manhattan distance, the distance between
the two corners (non-inclusive) is 1:

  #        #-O
  |    or    |
  O-#        #

But if you count the diagonal, then you need the pad:

  #
   \
    O
     \
      #

The choice isn't so obvious from the original wording: "The boxes need
to be padded with one unit worth of foam on each side that's facing
another box." The sides in Adam's example aren't *quite* facing each
other, hence the question. But as per your response I assume we're
counting the diagonal.

Jacob Fugal
912c61d9da47754de7039f4271334a9f?d=identicon&s=25 MenTaLguY (Guest)
on 2006-01-15 20:05
(Received via mailing list)
Okay, I'm pretty sure that's 48 hours now.  Here's my shot at a
solution.

Random notes:

* The algorithm isn't very bright -- it's basically a mangled "first
fit" approach which does a barely tolerable job.  I was hoping to come
up with something smarter, but I suck at maths so a good PTAS for this
has eluded me.  The problem is essentially the 2d version of
bin-packing, so there should be one...

* Part of the algorithm's stupidity is due to the aggressive pruning I
have to do to limit the number of solutions under consideration; if I
didn't prune so brutally, there'd be a sort of combinatorial explosion
in the worst cases.  For pruning, I favor the solutions which succeed in
placing boxes early, and those which minimize the fragmentation of the
free space.

* Rather than worry about inter-box padding directly, I just pad the
size of the boxes and the trunk by 1 when I read the initial input, then
trim off the padding when I display the result.

* The state of a trunk is represented as a list of boxes and a list of
overlapping rectangles of free space.  When a new box is placed in the
trunk, it's carved out of each of these free space rectangles via
Box#eliminate, whose result is a list of new overlapping rectangles
covering the remaining space.

* I aimed for a more or less "functional" style, in the sense that I
tried to avoid side-effects or mutation.  The really observant (or those
who have read my incomplete monad tutorial) may notice that I used a
monad built on Array to get non-determinism.

* Performance-wise, profiling shows that most of the time is spent in
Box#intersects? and Box#eliminate.  Maybe it needs a better data
structure for representing free space...

-mental

Solution follows...

--- 8< ------------ 8< ---
#!/usr/bin/ruby

MAX_SOLUTIONS = 100

class Array
  def pass( &block )
    map( &block ).inject( [] ) { |a, b| a.concat b }
  end
  def minimize
    minimum = map { |x| yield x }.min
    reject { |x| yield( x ) > minimum }
  end
end

module Area
  def area
    @area ||= width * height
  end
  def fits?( space )
    space.width >= width && space.height >= height
  end
end

class Box
  include Area

  attr_reader :min_x, :min_y, :max_x, :max_y

  def initialize( min_x, min_y, max_x, max_y )
    @min_x, @min_y, @max_x, @max_y = min_x, min_y, max_x, max_y
  end

  def intersects?( box )
    box.min_x < @max_x && box.min_y < @max_y &&
      box.max_x > @min_x && box.max_y > @min_y
  end
  def eliminate( box )
    return [self] unless self.intersects? box
    remaining = []
    remaining << Box.new( @min_x, @min_y, box.min_x, @max_y ) \
      if @min_x < box.min_x
    remaining << Box.new( @min_x, @min_y, @max_x, box.min_y ) \
      if @min_y < box.min_y
    remaining << Box.new( box.max_x, @min_y, @max_x, @max_y ) \
      if box.max_x < @max_x
    remaining << Box.new( @min_x, box.max_y, @max_x, @max_y ) \
      if box.max_y < @max_y
    remaining
  end

  def width
    @width ||= @max_x - @min_x
  end
  def height
    @height ||= @max_y - @min_y
  end
end

class Dimensions
  include Area

  attr_reader :width, :height

  def self.new_from_string( string )
    string =~ /(\d+)x(\d+)/
    self.new( $2.to_i, $1.to_i )
  end

  def initialize( width, height )
    @width, @height = width, height
  end

  def rotate
    @rotated ||= Dimensions.new( @height, @width )
  end
  def pad( n )
    Dimensions.new( @width + n, @height + n )
  end
end

class Trunk
  def self.new_from_area( area )
    self.new( area, [], [ Box.new( 0, 0, area.width, area.height ) ] )
  end

  def initialize( area, contents, remaining )
    @area, @contents, @remaining = area, contents, remaining
  end

  def empty? ; @contents.empty? ; end
  def fragmentation ; @remaining.length ; end

  def cram( thingy )
    @remaining.map { |space|
      next nil unless thingy.fits? space
      box = Box.new( space.min_x,
                     space.min_y,
                     space.min_x + thingy.width,
                     space.min_y + thingy.height )
      Trunk.new( @area, @contents + [box],
                 @remaining.pass { |space| space.eliminate box } )
    }.compact
  end

  def pretty_print
    all = @contents + @remaining
    width = @area.width - 1
    height = @area.height - 1
    aa = ( [ "." * width ] * height ).map { |x| x.dup }
    @contents.each do |box|
      for y in box.min_y...( box.max_y - 1 )
        run_length = box.width - 1
        aa[y][box.min_x, run_length] = "*" * run_length
      end
    end
    aa.each { |line| puts line }
  end
end

def pack_trunk( trunk_area, box_areas )
  box_areas.inject( [[ Trunk.new_from_area( trunk_area ), [] ]] ) do
    |solutions, box|

    solutions.pass { |trunk, leftovers|
      packings = trunk.cram( box ) + trunk.cram( box.rotate )
      if packings.empty?
        raise "One of them boxes is too big!" if trunk.empty?
        [[ trunk, leftovers + [box] ]]
      else
        packings.map { |packing| [ packing, leftovers ] }
      end
    }.minimize {
      |trunk, leftovers| leftovers.length
    }.minimize {
      |trunk, leftovers| trunk.fragmentation
    }[0, MAX_SOLUTIONS]
  end
end

def pack_trunks( trunks, trunk_area, box_areas )
  return [trunks] if box_areas.empty?

  pack_trunk( trunk_area, box_areas ).minimize {
    |trunk, leftovers| leftovers.length
  }.pass { |trunk, leftovers|
    pack_trunks( trunks + [trunk], trunk_area, leftovers )
  }
end

def solve( trunk_area, box_areas )
  box_areas = box_areas.sort_by { |box| box.area }.reverse
  pack_trunks( [], trunk_area, box_areas ).minimize {
    |trunks| trunks.length
  }.first
end

trunk_area = Dimensions.new_from_string( gets ).pad( 1 )
box_areas = gets.split.map { |s|
  Dimensions.new_from_string( s ).pad( 1 )
}
solve( trunk_area, box_areas ).each do |trunk|
  puts
  trunk.pretty_print
end
E20e89d58211a3631842daecc1245de2?d=identicon&s=25 Ilmari Heikkinen (Guest)
on 2006-01-15 21:32
(Received via mailing list)
Here's mine. It's a greedy heuristic algorithm that tries to fit each
box into the trunk, largest first. If no box fits, a new trunk is
created.

I'm representing trunks as 2D tables of squares (with one unit of
hidden padding around), then fill it starting from top left. The fitter
first finds a row with enough empty space to fit the box and
then checks if the next box-height rows also contain the space.
If they do, the box is drawn to the rows.

Printing is easy because the trunk already is in printable format.

Not a particularly fast way to do it, mind you :)

If you're interested about different algorithms for solving the 2D
bin packing problem, here's a paper:
http://www.dei.unipd.it/~fisch/ricop/tesi/tesi_dot...


#########


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_adding(box) or try_adding(box.rotate)
  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 }
      @rows[i+1, box[1]].each{|s|
        s[idx+1, box[0]] = "#" * box[0]
      }
      @items.push box
      return 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")
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-01-16 00:57
(Received via mailing list)
My solution so far.
I use 'BoxSorter' to keep all the boxes in a hash indexed by both
dimensions so its easy to find one that fits.  The 'TrunkSet'  keeps
track of the loaded boxes using arrays of characters.
The algorithm is kind of the opposite of Ilmari's: it iterates over
empty spaces in the trunk, looking for boxes that fit, instead of
iterating over the boxes.

-Adam
-----------------------------------------------------------------

require 'delegate'
class Box
  def initialize w,h
    @w,@h=w,h
  end
  def [] n
    n==0 ? @w :@h
  end
  def rotate!
    @w,@h = @h,@w
  end
  def other n
    n==@h ? @w :@h
  end
  def <=> box2   #compares the non-matching dimension
    if @w == box2[0] then @h <=> box2[1]
    elsif @w== box2[1] then @h <=> box2[0]
    elsif @h == box2[0] then @w <=> box2[1]
    else @w <=> box2[0]
    end
  end
end

class BoxSorter
  def initialize boxset
    @h = Hash.new
    boxset.each{|b|@h[b[0]]||=[];@h[b[0]]<<b;@h[b[1]]||=[];@h[b[1]]<<b;
@h}
    @h.each {|k,v| (v.sort!||v).reverse!}
    # hash has key for each box side,
    #  containing array of boxes sorted by size of the other side
  end
  def size
    @h.size
  end
  def find_best_fit w,h
    while w>0
      set = @h[w]
      box = set.find{|b| b.other(w)<=h } if set
      if box
        self.remove box
        box.rotate! if box[0] != w
        return box
      end
      w-=1;
    end
  end
  def remove box
    @h.delete_if {|k,v| v.delete(box); v.empty? }
  end
end

class TrunkSet < DelegateClass(Array)
  def initialize w,h
    @width,@height=w,h
    super []
    grow
  end
  def grow
    @openrow=0
    self<< Array.new(@height){Array.new(@width){" "}}
  end

  def first_open_row
    loop do
      break if last[@openrow].find{|s| s==' '}
      grow if @height == (@openrow +=1)
    end
    last[@openrow]
  end
  def first_open_space
    gaps,lastchar = [],nil
    first_open_row.each_with_index do |c,i|
      if c==' '
        if c==lastchar then gaps[-1][0]+=1
        else                gaps << [1,i]; end
      end
      lastchar = c
    end
    gaps.max
  end
  def pad_out
    last[@openrow].map!{|c| if c==' ' then '+' else c end }
    first_open_row
  end

  def add_box box,  col
    size,height = box[0],box[1]
    (0..height).each do |row|
      fillchar = (row == height) ? ['+','-'] : ['|','#']
      if nil != (fillrow = last[@openrow+row])
        fillrow[col-1] = fillchar[0] if (col-1>=0 )
        size.times {|i| fillrow[col+i] = fillchar[1] }
        fillrow[col+size] = fillchar[0] if ( col+size < @width )
      end
    end
  end

  def rows_remaining
    @height-@openrow
  end
  def has_no_boxes?
    last.each{|r| return false if r.find{|c| c == '#'} }
    true
  end
end

class Packer
  def initialize size, boxes
    @loose_boxes = BoxSorter.new(boxes)
    @trunks = TrunkSet.new(*size)
  end

  def pack_a_box
    column,nextbox = nil,nil
    loop do
      space_available,column = @trunks.first_open_space
      nextbox = @loose_boxes.find_best_fit(space_available,
                                    @trunks.rows_remaining)
      break if nextbox
      @trunks.pad_out              #if no box fits, need to fill row
with pads
    end
    @trunks.add_box(nextbox,column)
  end

  def pack
    until @loose_boxes.size == 0
      pack_a_box
    end
    (@trunks.rows_remaining).times { @trunks.pad_out }
  end

  def show
    @trunks.pop if @trunks.has_no_boxes?
    @trunks.each do |bin|
      bin.each { |row|puts row.join }
      puts ""
    end
    puts "#{@trunks.size} loads"
  end
end

class PackerParser
  attr_reader :binsize, :blocks
  def initialize file
    @binsize = file.readline.chomp
    @blocks = file.readline.chomp.split " "
  end
  def size
    @binsize.match(/(\d*)x(\d*)/)
    [$1.to_i,$2.to_i]
  end
  def boxes
    @blocks.map{|s| s.match(/(\d*)x(\d*)/);Box.new($1.to_i,$2.to_i)}
  end
end

if __FILE__ == $0
  pp = PackerParser.new(ARGF)
  puts pp.binsize
  puts pp.blocks.join(' ')

  pk = Packer.new(pp.size, pp.boxes)
  pk.pack
  pk.show
end
This topic is locked and can not be replied to.