From: MenTaLguY <mental@...>
Date: 2006-01-16T04:04:47+09:00
Subject: [QUIZ] [SOLUTION] Packing (#62)

--=-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--