# Packing (#62)

**URL:** <https://www.ruby-forum.com/t/packing-62/95707>\
**Category:** Ruby\
**Created:** [January 19, 2006, 3:11pm UTC](https://www.ruby-forum.com/t/packing-62/95707 "2006-01-19T15:11:24Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 19, 2006, 3:11pm UTC](https://www.ruby-forum.com/t/packing-62/95707/1 "2006-01-19T15:11:24Z")

</div>

As the submitters pointed out, this in the famous “bin packing”  
challenge, in  
two dimensions. There’s a lot of theory available for this problem  
which I’ve  
just been looking into a little myself.

The solutions took pretty different approaches and I encourage you to  
walk  
through them a little and get a handle on how they are working. We will  
go  
through Ilmari’s code here because you can make sense of it without all  
the  
theory, if you work it through carefully. Given that, let’s take it in  
super  
small slices this time:

```
trunk = gets.strip.split("x").map{|i| i.to_i}
boxes = gets.strip.split(" ").map{|s| s.split("x").map{|i| i.to_i} }

```

Those are the first two non-declarative lines of Ilmari’s script.  
Obviously,  
we’re just reading the input here. Looks like we’re breaking the first  
line on  
“x” and the second on " " and then “x”. Note that to\_i() is ignoring  
non-numeric characters like line-endings. Can you envision what the  
Arrays will  
hold at this point (assuming the quiz example)? Here’s a peek:

```
trunk = [10, 20]
boxes = [[1, 3], [4, 8], [3, 7], [9, 4], [10, 14]]

```

The next line is:

```
boxes = boxes.sort_by{|b| b.inject{|f,i| f*i} }.reverse

```

We’re sorting the boxes here, but by what? The product of the two  
numbers that  
make up the box (width and height). That’s their area, right? Just  
remember  
that they get reversed, so here’s what we are looking at now:

```
boxes = [[10, 14], [9, 4], [4, 8], [3, 7], [1, 3]]

```

As you can see, that gives us a largest to smallest ordering. Just as  
it is  
with real moving, it’s easier to load the big items first, then fill  
around them  
with the little items.

The next line of code is:

```
trunks = [Trunk.new(*trunk)]

```

We’re building a Trunk (inside an Array) here. Note the splat operator  
applied  
to trunk, which will separate it out into a width and height.

Looks like we need to see the definition of Trunk at this point, but  
just the  
constructor will do for now:

```
class Trunk
  def initialize(w,h)
    @w = w
    @h = h
    @items = []
    @rows = (1..@h+2).map{ "_"*(@w+2) }
  end
end

```

The first three assignments should be painfully obvious. The only  
mildly  
complicated line is the one that makes @rows:

```
@rows = [ " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________",
          " ____________" ]

```

Notice that an extra column or row is added on every side of the Trunk.  
Let’s  
just assume we will figure out why that is later.

Now we’re going to get adventurous and take in a few more lines, but we  
will  
dissect them slowly:

```
until boxes.empty?
  fitting = boxes.find{|box| trunks.last.add box }
  if fitting
    boxes.delete_first fitting
  elsif trunks.last.empty?
    raise "Can't fit #{boxes.inspect} into the trunk"
  else
    trunks << Trunk.new(*trunk) unless boxes.empty?
  end
end

```

There’s some new methods being used here, but let’s try to get the hang  
of this  
process as a whole. While there are boxes, this loop tries to fit them  
into the  
last Trunk.

Why just the last one though, wouldn’t that miss opportunities? It  
doesn’t but  
it took me a bit to understand why. We’re going through the boxes  
largest to  
smallest and the last Trunk will always be the one with the most open  
space  
(completely open in the example we just saw). If a big box doesn’t have  
room  
there, all the smaller boxes will be tried by find().

Back to that if statement. If we find a fit, we remove it from the  
boxes  
(assume we understand delete\_first()). If it didn’t fit and the last  
Trunk was  
empty?(), the box is bigger than the Trunk and a solution is impossible.  
Finally, if it didn’t fit but the last Trunk had items in it, we better  
make an  
new() Trunk and try again.

Let’s examine some of those extra methods to make sure we have this  
down.  
Here’s delete\_first():

```
class Array
  def delete_first item
    delete_at index(item)
  end
end

```

The function is obvious, find an item and delete it. Why do we need  
that?  
Duplicates:

```
>> arr = [1, 2, 2, 3, 2, 2, 2]
=> [1, 2, 2, 3, 2, 2, 2]
>> arr.delete(2)
=> 2
>> arr
=> [1, 3]
>> arr = [1, 2, 2, 3, 2, 2, 2]
=> [1, 2, 2, 3, 2, 2, 2]
>> arr.delete_first(2)
=> 2
>> arr
=> [1, 2, 3, 2, 2, 2]

```

See the difference? If we used delete(), it would wipe out all boxes of  
the  
same size.

What about Trunk.empty?()?

```
class Trunk
  def empty?
    @items.empty?
  end
end

```

A Trunk that has no @items in it is empty. That’s what we assumed.

Okay, the critical missing piece is the monster. If we get past it, we  
are home  
free. Here we go:

```
class Trunk
  def add box
    try_adding(box) or try_adding(box.rotate)
  end
end

```

We can see here that we just try\_adding() the box both ways. If either  
fits, we  
assume it’s now in the Trunk (the loop deletes it from the box list  
then, if you  
recall), otherwise it seems we will get a false return value. I might  
have  
named this method add?(), because I think it would have made that easier  
to see.

I was guessing about rotate() there of course, let’s make sure I’m  
right:

```
class Array
  def rotate
    d = dup
    d.push d.shift
    d
  end
end

```

Remember a box is something like [10, 14]. That means the above returns  
a copy  
of the form [14, 10]. Yep, that flips it.

That means we just need to see try\_adding():

```
class Trunk
  def try_adding box
    boxrow = "_"*(box[0]+2)
    @rows.each_with_index{|r,i|
      break if i > @rows.size - (box[1]+2)
      next unless r.include?(boxrow)
      idxs = @rows[i+1, box[1]+1].map{|s| s.index boxrow }
      next unless idxs.all?
      idx = idxs.max
      next unless @rows[i, box[1]+2].all?{|s| s[idx,boxrow.size] == 

```

boxrow }  
@rows[i+1, box[1]].each{|s|  
s[idx+1, box[0]] = “#” \* box[0]  
}  
@items.push box  
return box  
}  
nil  
end  
end

Oh boy. I warned you the tough stuff was coming. It’s not as bad as it  
looks  
though, so let’s just keep breaking it down.

First, we see that a boxrow is built. Again, it is expanded on both  
sides. Now  
that makes sense to me. If you expand the Trunk and all the boxes, you  
can  
essentially forget about padding, as long as you remember to strip it  
out later.  
Also note that boxrow is built as a String of “\_” characters, so it will  
be used  
to find empty Trunk space.

Now we walk the Trunk, @row-by-@row. The first line breaks out of the  
iterator  
though, as soon as we run out of enough @rows to hold the box (and the  
two extra  
padding @rows, of course).

The next few lines verify that the box fits on this @row, and the coming  
@rows.  
Let’s look at those again:

```
      # ...
      next unless r.include?(boxrow)
      idxs = @rows[i+1, box[1]+1].map{|s| s.index boxrow }
      next unless idxs.all?
      idx = idxs.max
      next unless @rows[i, box[1]+2].all?{|s| s[idx,boxrow.size] == 

```

boxrow }  
# …

Line-by-line that’s: Verify that this @row holds the box, or move on.  
Fetch  
the index where the box would fit on @rows needed to hold it below this  
one.  
Verify that we got an index for all needed lines, or move on. Find the  
highest  
of those indices. (More on that in a second.) Finally, verify that the  
box  
does fit on all needed @rows at the highest found index, or move on.

When I first read that code, I was sure it didn’t work for all cases.  
Trying to  
prove it wrong taught me how it does work. Remember, the code works  
biggest box  
to smallest, and we now know that it fills Trunks top left to bottom  
right  
(index() favors a left most match). Given that the only danger is a  
setup like:

```
##__
##__
____

```

And us needing to place a 1x3 box. It fits on the right side, but the  
last  
index() wouldn’t match the others. That’s why the code uses the max().  
It  
shifts it to the right as far as needed. (Always using the first  
index() would  
work the same, because of the Trunk fill order.)

The rest of that monster we are breaking down is trivial:

```
      # ...
      @rows[i+1, box[1]].each{|s|
        s[idx+1, box[0]] = "#" * box[0]
      }
      @items.push box
      return box
    }
    nil
  end

```

If we made it this far, we have a match, so draw the actual box in  
place. We  
can ignoring padding now, since we already proved there is room. Add  
the box to  
@items, so we know the Trunk isn’t empty?(), and return any true value  
to  
indicate a match. The final nil is our default false return, if we  
didn’t find  
a match.

We’re home free now. Here’s the final printing code:

```
puts
puts trunks.join("\n\n")

```

It’s important to know here that join() calls to\_s() on all arguments  
before it  
combines them. That’s the only method we haven’t seen:

```
class Trunk
  def to_s
    @rows[1..-2].map{|r|r[1..-2]}.join("\n")
  end
end

```

Nothing surprising here, as long as you remember that the extra space  
has to be  
stripped back out of the Trunk.

That gives us a final answer (for the quiz example) of:

```
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########
__________
#########_
#########_
#########_
#########_
__________

####_###_#
####_###_#
####_###_#
####_###__
####_###__
####_###__
####_###__
#### ______
 __________
 __________
 __________
 __________
 __________
 __________
 __________
 __________
 __________
 __________
 __________
 __________

```

See how they are packed largest to smallest, top left to bottom right?  
That’s  
as tight as we can make it.

A big thank you to the three brave souls willing to slug out a tough  
problem  
this week. Nice solutions all around.

Next week, Matthew M. is back with a tricky little riddle…