[QUIZ] [SOLUTION] Packing (#62)

[MenTaLguY]

--=-SdjiVxcjPnSZsftdlA/c
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

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 =3D 100

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

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

class Box
include Area
=20
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 =3D 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 =3D []
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
=20
def width
@width ||=3D @max_x - @min_x
end
def height
@height ||=3D @max_y - @min_y
end
end

class Dimensions
include Area
=20
attr_reader :width, :height

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

def initialize( width, height )
@width, @height =3D width, height
end
=20
def rotate
@rotated ||=3D 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 =3D area, contents, remaining
end

def empty? ; @contents.empty? ; end
def fragmentation ; @remaining.length ; end
=20
def cram( thingy )
@remaining.map { |space|
next nil unless thingy.fits? space
box =3D 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
=20
def pretty_print
all =3D @contents + @remaining
width =3D @area.width - 1
height =3D @area.height - 1
aa =3D ( [ "." * width ] * height ).map { |x| x.dup }
@contents.each do |box|
for y in box.min_y...( box.max_y - 1 )
run_length =3D box.width - 1
aa[y][box.min_x, run_length] =3D "*" * 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 =3D 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 =3D box_areas.sort_by { |box| box.area }.reverse
pack_trunks( [], trunk_area, box_areas ).minimize {
|trunks| trunks.length
}.first
end

trunk_area =3D Dimensions.new_from_string( gets ).pad( 1 )
box_areas =3D gets.split.map { |s|
Dimensions.new_from_string( s ).pad( 1 )
}
solve( trunk_area, box_areas ).each do |trunk|
puts
trunk.pretty_print
end


--=-SdjiVxcjPnSZsftdlA/c
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQBDypzVcUNIGiXCc4MRAj+IAJ97Y2WqVO1lapeJg72zn4fd7rGyjACePB66
ExBGfObBmspnrDg41eyJhqE=
=++AN
-----END PGP SIGNATURE-----

--=-SdjiVxcjPnSZsftdlA/c--