R
Ruby Quiz
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:
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 Moss is back with a tricky little riddle...
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:
=> [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 Moss is back with a tricky little riddle...