by Ilmari Heikkinen
You're moving. And that means a whole bunch of boxes need to be moved from the old place to the new one. You've got a pickup truck to do the moving, but it can only hold one vertical level of boxes. The boxes need to be padded with one unit worth of foam on each side that's facing another box.
The goal is to minimize the amount of trips you have to do to move all the boxes.
The solver program should take two lines of input, first one containing the trunk dimensions (e.g. 10x20), and the second one containing all the box dimensions, separated by spaces (e.g. 1x3 4x8 3x7 9x4 10x14.)
The output of the solver should be ascii art of the trunk packings, with each trunkful separated by an empty line.
Example:
$ ruby solver.rb
10x20
1x3 4x8 3x7 9x4 10x14
**************.***..
**************......
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
*********...........
*********...........
*********...........
*********...........
....................
*******.............
*******.............
*******.............
....................
....................
Quiz Summary
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:
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:
boxes = [[1, 3], [4, 8], [3, 7], [9, 4], [10, 14]]
The next line is:
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:
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:
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:
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:
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________",
"____________" ]
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:
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():
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?()?
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:
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:
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():
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 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:
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 Moss is back with a tricky little riddle...
