Path: g2news1.google.com!news1.google.com!proxad.net!212.101.4.254.MISMATCH!solnet.ch!solnet.ch!newsfeed.freenet.de!news.n-ix.net!news2.arglkargh.de!noris.net!not-for-mail
From: Adam Shelly <adam.she...@gmail.com>
Newsgroups: comp.lang.ruby
Subject: Re: [QUIZ][SOLUTION] Packing (#62)
Date: Mon, 16 Jan 2006 08:56:26 +0900
Lines: 180
Message-ID: <491107790601151556l24e4b3d4p404fb5ce4eb0c45c@mail.gmail.com>
References: <20060113133829.DEPF8318.centrmmtao04.cox.net@localhost.localdomain>
	 <854c25eb0601151232h268292cdn29ec19806f508c22@mail.gmail.com>
NNTP-Posting-Host: sinus.lauschmusik.de
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: ork-un.noris.net 1137369413 10565 213.95.32.201 (15 Jan 2006 23:56:53 GMT)
X-Complaints-To: news@noris.net
NNTP-Posting-Date: Sun, 15 Jan 2006 23:56:53 +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: <854c25eb0601151232h268292cdn29ec19806f508c22@mail.gmail.com>
X-ML-Name: ruby-talk
X-Mail-Count: 175877
X-ruby-talk: <491107790601151556l24e4b3d4p404fb5ce4eb0c...@mail.gmail.com>
X-rubymirror: yes

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