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…