Path: g2news1.google.com!news2.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!t-online.de!news.karotte.org!news2.arglkargh.de!noris.net!not-for-mail
From: MenTaLguY <men...@rydia.net>
Newsgroups: comp.lang.ruby
Subject: [QUIZ] [SOLUTION] Packing (#62)
Date: Mon, 16 Jan 2006 04:04:47 +0900
Lines: 227
Message-ID: <1137351894.7197.264.camel@localhost.localdomain>
NNTP-Posting-Host: sinus.lauschmusik.de
Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="=-SdjiVxcjPnSZsftdlA/c"
X-Trace: ork-un.noris.net 1137351915 26077 213.95.32.201 (15 Jan 2006 19:05:15 GMT)
X-Complaints-To: news@noris.net
NNTP-Posting-Date: Sun, 15 Jan 2006 19:05:15 +0000 (UTC)
X-received-from: This message has been automatically forwarded from
   the ruby-talk mailing list by a gateway at lauschmusik.de. If it is
   SPAM, it did not originate at lauschmusik.de. Please report the 
   original sender, and not us. Thanks!
   Please see http://hypermetrics.com/rubyhacker/clrFAQ.html#tag24 to.
In-Reply-To: <20060113133829.DEPF8318.centrmmtao04.cox.net@localhost.localdomain>
X-ML-Name: ruby-talk
X-Mail-Count: 175867
X-ruby-talk: <1137351894.7197.264.ca...@localhost.localdomain>
X-rubymirror: yes

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