[QUIZ] Packing (#62)

[Ruby Quiz]

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

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

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

 

[Robert Retzbach]

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

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

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

Hello,
this is a interesting quiz, but I am still in the middle to understand
the last!

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

MfG
Retze

 

[James Edward Gray II]

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

 

[Robert Retzbach]

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

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

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

Hello,
this is a interesting quiz, but I am still in the middle to understand
the last!

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.

 

[Adam Shelly]

You're moving. And that means a whole bunch of boxes need to be moved fro=
m 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 o= ne 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?

 

[Ilmari Heikkinen]

T24gMS8xMy8wNiwgQWRhbSBTaGVsbHkgPGFkYW0uc2hlbGx5QGdtYWlsLmNvbT4gd3JvdGU6Cj4g
PiBZb3UncmUgbW92aW5nLiBBbmQgdGhhdCBtZWFucyBhIHdob2xlIGJ1bmNoIG9mIGJveGVzIG5l
ZWQgdG8gYmUgbW92ZWQgZnJvbSB0aGUKPiA+IG9sZCBwbGFjZSB0byB0aGUgbmV3IG9uZS4gWW91
J3ZlIGdvdCBhIHBpY2t1cCB0cnVjayB0byBkbyB0aGUgbW92aW5nLCBidXQgaXQgY2FuCj4gPiBv
bmx5IGhvbGQgb25lIHZlcnRpY2FsIGxldmVsIG9mIGJveGVzLiBUaGUgYm94ZXMgbmVlZCB0byBi
ZSBwYWRkZWQgd2l0aCBvbmUgdW5pdAo+ID4gd29ydGggb2YgZm9hbSBvbiBlYWNoIHNpZGUgdGhh
dCdzIGZhY2luZyBhbm90aGVyIGJveC4KPiA+Cj4KPiByZWdhcmRpbmcgcGFkZGluZywgaXMgdGhp
cyBhIHZhbGlkIHJlc3VsdD8KPiAxMHgxMAo+IDV4NSA1eDUKPgo+ICMjIyMjb29vb28KPiAjIyMj
I29vb29vCj4gIyMjIyNvb29vbwo+ICMjIyMjb29vb28KPiAjIyMjI29vb29vCj4gb29vb28jIyMj
Iwo+IG9vb29vIyMjIyMKPiBvb29vbyMjIyMjCj4gb29vb28jIyMjIwo+IG9vb29vIyMjIyMKPgo+
IGkuZTogZG8gSSBuZWVkIHRvIHB1dCBhIHBhZCBpbiB0aGUgc3BvdCBtYXJrZWQgd2l0aCB0aGUg
Pwo+ICMjIyMjbwo+ICMjIyMjbwo+ICMjIyMjbwo+ICMjIyMjbwo+ICMjIyMjbwo+IG9vb29vPwoK
WWVzLCB0aGF0IG5lZWRzIHRvIGJlIHBhZGRlZC4gRWFjaCBwb2ludCBpbiBhIGJveCBzaG91bGQK
YmUgPj0gMSB1bml0cyBmcm9tIGFub3RoZXIgYm94LgoKR29vZCBjaG9pY2Ugb2YgY2hhcmFjdGVy
cyBidHcsIHdvcmtzIGV2ZW4gb24gZml4ZWQtd2lkdGguCg==

 

[Jacob Fugal]

Yes, that needs to be padded. Each point in a box should
be >=3D 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

 

[Adam Shelly]

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=3Dw,h
end
def [] n
n=3D=3D0 ? @w h
end
def rotate!
@w,@h =3D @h,@w
end
def other n
n=3D=3D@h ? @w h
end
def <=3D> box2 #compares the non-matching dimension
if @w =3D=3D box2[0] then @h <=3D> box2[1]
elsif @w=3D=3D box2[1] then @h <=3D> box2[0]
elsif @h =3D=3D box2[0] then @w <=3D> box2[1]
else @w <=3D> box2[0]
end
end
end

class BoxSorter
def initialize boxset
@h =3D Hash.new
boxset.each{|b|@h[b[0]]||=3D[];@h[b[0]]<<b;@h[b[1]]||=3D[];@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 =3D @h[w]
box =3D set.find{|b| b.other(w)<=3Dh } if set
if box
self.remove box
box.rotate! if box[0] !=3D w
return box
end
w-=3D1;
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=3Dw,h
super []
grow
end
def grow
@openrow=3D0
self<< Array.new(@height){Array.new(@width){" "}}
end

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

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

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

def pack_a_box
column,nextbox =3D nil,nil
loop do
space_available,column =3D @trunks.first_open_space
nextbox =3D @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 p=
ads
end
@trunks.add_box(nextbox,column)
end

def pack
until @loose_boxes.size =3D=3D 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 =3D file.readline.chomp
@blocks =3D 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__ =3D=3D $0
pp =3D PackerParser.new(ARGF)
puts pp.binsize
puts pp.blocks.join(' ')

pk =3D Packer.new(pp.size, pp.boxes)
pk.pack
pk.show
end

 

[horndude77]

Here's my solution. I keep track of the positions of the boxes in each
truckbed and generate the ascii only when it is printed. I was trying
to be fancy with the insertion points, but it became too difficult to
maintain so I just added every point and removed those covered by and
surrounding a box during insertion. I sort the boxes by size to put the
biggest ones in first. I'm fairly happy with my solution. Thanks for
the quiz!

-----Horndude77

class TruckBed
def initialize(width,height)
@width,@height = width,height
@boxes = {}

#This list maintains where it is possible to add boxes
@insertion_points = [(0...width).to_a * height,
(0...height).map{|i| *width}.flatten].transpose
sort_insertion_points
end

def insert(box)
@insertion_points.each do |pos|
[box, box.reverse].each do |curr_box|
if fits_at? curr_box, pos then
@boxes[pos] = curr_box
(-1).upto(curr_box[0]) do |x|
(-1).upto(curr_box[1]) do |y|
@insertion_points.delete [x+pos[0],
y+pos[1]]
end
end
sort_insertion_points
return true
end
end
end
false
end

#Stable sort: keep relative order
#This way we control where insertions happen
def sort_insertion_points
n = 0
@insertion_points.sort_by{|x| n+=1; [x[1], n]}
@insertion_points.sort_by{|x| n+=1; [x[0], n]}
end

#See if box fits at pos
def fits_at?(box, pos)
box_min = pos
box_max = [pos[0]+box[0]-1, pos[1]+box[1]-1]
return false if (box_max[0] >= @width) || (box_max[1] >=
@height)
#check for box intersections
@boxes.each do |curr_pos, curr_box|
curr_box_min = [curr_pos[0]-1, curr_pos[1]-1]
curr_box_max = [curr_pos[0]+curr_box[0],
curr_pos[1]+curr_box[1]]
return false if box_min[0] <= curr_box_max[0] && box_max[0]

= curr_box_min[0] &&

box_min[1] <= curr_box_max[1] && box_max[1] >=
curr_box_min[1]
end
true
end

def to_s
bed = Array.new(@width) { Array.new(@height) {'-'} }
@boxes.each do |pos,box|
box[0].times do |x|
box[1].times do |y|
bed[x+pos[0]][y+pos[1]] = 'X'
end
end
end
bed.transpose.reverse.map {|r| r.join }.join("\n")
end
end

class String
def to_dims
split('x').map {|i| i.to_i}
end
end

truck_bed_dims = ARGF.gets.to_dims
boxes = ARGF.gets.split.map {|box| box.to_dims.sort.reverse}.sort
{|a,b| a[0]*a[1] <=> b[0]*b[1]}

truck_beds = [TruckBed.new(*truck_bed_dims)]

while boxes.size > 0
box = boxes.pop
truck_beds.each do |bed|
if(bed.insert box) then
box = nil
break
end
end
if(box) then
bed = TruckBed.new(*truck_bed_dims)
bed.insert(box)
truck_beds << bed
end
end

puts
puts truck_beds.join("\n\n")