Packing (#62)


#1

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

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

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

by Ilmari H.

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

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

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

#2

On 1/13/06, Ruby Q. removed_email_address@domain.invalid 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


#3

Ruby Q. 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! :smiley:

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

MfG
Retze


#4

On Jan 13, 2006, at 9:26 AM, Robert R. 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 G. II


#5

Robert R. schrieb:

http://www.rubyquiz.com/
by Ilmari H.
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.


#6

On Jan 13, 2006, at 10:24 AM, removed_email_address@domain.invalid wrote:

Are we allowed to rotate boxes?

You bet.

James Edward G. II


#7

On 1/13/06, removed_email_address@domain.invalid removed_email_address@domain.invalid wrote:

Are we allowed to rotate boxes?

-mental

Yes.


#8

Are we allowed to rotate boxes?

-mental


#9

On 1/13/06, removed_email_address@domain.invalid removed_email_address@domain.invalid 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>

(=


#10

Quoting Ruby Q. removed_email_address@domain.invalid:

**************.****.
*******…
*******…
*******…

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

-mental


#11

On 1/13/06, Adam S. removed_email_address@domain.invalid 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.


#12

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?


#13

On 1/13/06, Ilmari H. removed_email_address@domain.invalid 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 F.


#14

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


#15

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 :slight_smile:

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_dottorato_Lodi_1999.pdf

#########

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")


#16

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