[QUIZ] Packing (#62)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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
**************.***..
**************......
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
*********...........
*********...........
*********...........
*********...........
....................
*******.............
*******.............
*******.............
....................
....................
Robert Retzbach
Hello,
this is a interesting quiz, but I am still in the middle to understand
the last! :D
However... I can't access ruby62.html. It's always rewritten to ruby26.html.
Maybe I stand alone with this problem.
MfG
Retze
James Edward Gray II
> However... I can't access ruby62.html. It's always rewritten to
> ruby26.html.
> Maybe I stand alone with this problem.
Are you talking about:
http://www.rubyquiz.com/quiz62.html
It loads fine for me. Is anyone else seeing this?
The page contains exactly the same information as the email you
quoted though, so you're not missing anything.
James Edward Gray II
Robert Retzbach
Hmmm,
with Ie it works, maybe I have something in my ff cache.
Nvm then, happy quizzing.
men...@rydia.net
-mental
James Edward Gray II
> Are we allowed to rotate boxes?
You bet.
James Edward Gray II
Ilmari Heikkinen
Yes.
Hampton
generating algorithm?
men...@rydia.net
Whoops, this example shows an 8x4 box, not a 9x4 one.
-mental
Ilmari Heikkinen
>
> > Example:
> > $ ruby solver.rb
> > 10x20
> > 1x3 4x8 3x7 9x4 10x14
> >
> > **************.***..
> > **************......
> > **************.****.
> > **************.****.
> > **************.****.
> > **************.****.
> > **************.****.
> > **************.****.
> > **************.****.
> >
> > *********...........
> > *********...........
> > *********...........
> > ....................
> > *******.............
> > *******.............
> > *******.............
> > ....................
> > ....................
>
> Whoops, this example shows an 8x4 box, not a 9x4 one.
Actually, there's an 8x4 box and a 9x4 box.
The small width of the characters really is quite confusing,
long lines of asterisks merging into each other
while rows are well separated,
making counting difficult -
a Gestalt law in effect.
</bad poetry>
(=
Adam Shelly
> 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.
>
regarding padding, is this a valid result?
10x10
5x5 5x5
#####ooooo
#####ooooo
#####ooooo
#####ooooo
#####ooooo
ooooo#####
ooooo#####
ooooo#####
ooooo#####
ooooo#####
i.e: do I need to put a pad in the spot marked with the ?
#####o
#####o
#####o
#####o
#####o
ooooo?
Ilmari Heikkinen
Yes, that needs to be padded. Each point in a box should
be >= 1 units from another box.
Good choice of characters btw, works even on fixed-width.
Jacob Fugal
If you calculate using the manhattan distance, the distance between
the two corners (non-inclusive) is 1:
# #-O
| or |
O-# #
But if you count the diagonal, then you need the pad:
#
\
O
\
#
The choice isn't so obvious from the original wording: "The boxes need
to be padded with one unit worth of foam on each side that's facing
another box." The sides in Adam's example aren't *quite* facing each
other, hence the question. But as per your response I assume we're
counting the diagonal.
Jacob Fugal
MenTaLguY
solution.
Random notes:
* The algorithm isn't very bright -- it's basically a mangled "first
fit" approach which does a barely tolerable job. I was hoping to come
up with something smarter, but I suck at maths so a good PTAS for this
has eluded me. The problem is essentially the 2d version of
bin-packing, so there should be one...
* Part of the algorithm's stupidity is due to the aggressive pruning I
have to do to limit the number of solutions under consideration; if I
didn't prune so brutally, there'd be a sort of combinatorial explosion
in the worst cases. For pruning, I favor the solutions which succeed in
placing boxes early, and those which minimize the fragmentation of the
free space.
* Rather than worry about inter-box padding directly, I just pad the
size of the boxes and the trunk by 1 when I read the initial input, then
trim off the padding when I display the result.
* The state of a trunk is represented as a list of boxes and a list of
overlapping rectangles of free space. When a new box is placed in the
trunk, it's carved out of each of these free space rectangles via
Box#eliminate, whose result is a list of new overlapping rectangles
covering the remaining space.
* I aimed for a more or less "functional" style, in the sense that I
tried to avoid side-effects or mutation. The really observant (or those
who have read my incomplete monad tutorial) may notice that I used a
monad built on Array to get non-determinism.
* Performance-wise, profiling shows that most of the time is spent in
Box#intersects? and Box#eliminate. Maybe it needs a better data
structure for representing free space...
-mental
Solution follows...
--- 8< ------------ 8< ---
#!/usr/bin/ruby
MAX_SOLUTIONS = 100
class Array
def pass( &block )
map( &block ).inject( [] ) { |a, b| a.concat b }
end
def minimize
minimum = map { |x| yield x }.min
reject { |x| yield( x ) > minimum }
end
end
module Area
def area
@area ||= width * height
end
def fits?( space )
space.width >= width && space.height >= height
end
end
class Box
include Area
attr_reader :min_x, :min_y, :max_x, :max_y
def initialize( min_x, min_y, max_x, max_y )
@min_x, @min_y, @max_x, @max_y = min_x, min_y, max_x, max_y
end
def intersects?( box )
box.min_x < @max_x && box.min_y < @max_y &&
box.max_x > @min_x && box.max_y > @min_y
end
def eliminate( box )
return [self] unless self.intersects? box
remaining = []
remaining << Box.new( @min_x, @min_y, box.min_x, @max_y ) \
if @min_x < box.min_x
remaining << Box.new( @min_x, @min_y, @max_x, box.min_y ) \
if @min_y < box.min_y
remaining << Box.new( box.max_x, @min_y, @max_x, @max_y ) \
if box.max_x < @max_x
remaining << Box.new( @min_x, box.max_y, @max_x, @max_y ) \
if box.max_y < @max_y
remaining
end
def width
@width ||= @max_x - @min_x
end
def height
@height ||= @max_y - @min_y
end
end
class Dimensions
include Area
attr_reader :width, :height
def self.new_from_string( string )
string =~ /(\d+)x(\d+)/
self.new( $2.to_i, $1.to_i )
end
def initialize( width, height )
@width, @height = width, height
end
def rotate
@rotated ||= Dimensions.new( @height, @width )
end
def pad( n )
Dimensions.new( @width + n, @height + n )
end
end
class Trunk
def self.new_from_area( area )
self.new( area, [], [ Box.new( 0, 0, area.width, area.height ) ] )
end
def initialize( area, contents, remaining )
@area, @contents, @remaining = area, contents, remaining
end
def empty? ; @contents.empty? ; end
def fragmentation ; @remaining.length ; end
def cram( thingy )
@remaining.map { |space|
next nil unless thingy.fits? space
box = Box.new( space.min_x,
space.min_y,
space.min_x + thingy.width,
space.min_y + thingy.height )
Trunk.new( @area, @contents + [box],
@remaining.pass { |space| space.eliminate box } )
}.compact
end
def pretty_print
all = @contents + @remaining
width = @area.width - 1
height = @area.height - 1
aa = ( [ "." * width ] * height ).map { |x| x.dup }
@contents.each do |box|
for y in box.min_y...( box.max_y - 1 )
run_length = box.width - 1
aa[y][box.min_x, run_length] = "*" * run_length
end
end
aa.each { |line| puts line }
end
end
def pack_trunk( trunk_area, box_areas )
box_areas.inject( [[ Trunk.new_from_area( trunk_area ), [] ]] ) do
|solutions, box|
solutions.pass { |trunk, leftovers|
packings = trunk.cram( box ) + trunk.cram( box.rotate )
if packings.empty?
raise "One of them boxes is too big!" if trunk.empty?
[[ trunk, leftovers + [box] ]]
else
packings.map { |packing| [ packing, leftovers ] }
end
}.minimize {
|trunk, leftovers| leftovers.length
}.minimize {
|trunk, leftovers| trunk.fragmentation
}[0, MAX_SOLUTIONS]
end
end
def pack_trunks( trunks, trunk_area, box_areas )
return [trunks] if box_areas.empty?
pack_trunk( trunk_area, box_areas ).minimize {
|trunk, leftovers| leftovers.length
}.pass { |trunk, leftovers|
pack_trunks( trunks + [trunk], trunk_area, leftovers )
}
end
def solve( trunk_area, box_areas )
box_areas = box_areas.sort_by { |box| box.area }.reverse
pack_trunks( [], trunk_area, box_areas ).minimize {
|trunks| trunks.length
}.first
end
trunk_area = Dimensions.new_from_string( gets ).pad( 1 )
box_areas = gets.split.map { |s|
Dimensions.new_from_string( s ).pad( 1 )
}
solve( trunk_area, box_areas ).each do |trunk|
puts
trunk.pretty_print
end
Adam Shelly
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=w,h
end
def [] n
n==0 ? @w :@h
end
def rotate!
@w,@h = @h,@w
end
def other n
n==@h ? @w :@h
end
def <=> box2 #compares the non-matching dimension
if @w == box2[0] then @h <=> box2[1]
elsif @w== box2[1] then @h <=> box2[0]
elsif @h == box2[0] then @w <=> box2[1]
else @w <=> box2[0]
end
end
end
class BoxSorter
def initialize boxset
@h = Hash.new
boxset.each{|b|@h[b[0]]||=[];@h[b[0]]<<b;@h[b[1]]||=[];@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 = @h[w]
box = set.find{|b| b.other(w)<=h } if set
if box
self.remove box
box.rotate! if box[0] != w
return box
end
w-=1;
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=w,h
super []
grow
end
def grow
@openrow=0
self<< Array.new(@height){Array.new(@width){" "}}
end
def first_open_row
loop do
break if last[@openrow].find{|s| s==' '}
grow if @height == (@openrow +=1)
end
last[@openrow]
end
def first_open_space
gaps,lastchar = [],nil
first_open_row.each_with_index do |c,i|
if c==' '
if c==lastchar then gaps[-1][0]+=1
else gaps << [1,i]; end
end
lastchar = c
end
gaps.max
end
def pad_out
last[@openrow].map!{|c| if c==' ' then '+' else c end }
first_open_row
end
def add_box box, col
size,height = box[0],box[1]
(0..height).each do |row|
fillchar = (row == height) ? ['+','-'] : ['|','#']
if nil != (fillrow = last[@openrow+row])
fillrow[col-1] = fillchar[0] if (col-1>=0 )
size.times {|i| fillrow[col+i] = fillchar[1] }
fillrow[col+size] = 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 == '#'} }
true
end
end
class Packer
def initialize size, boxes
@loose_boxes = BoxSorter.new(boxes)
@trunks = TrunkSet.new(*size)
end
def pack_a_box
column,nextbox = nil,nil
loop do
space_available,column = @trunks.first_open_space
nextbox = @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 pads
end
@trunks.add_box(nextbox,column)
end
def pack
until @loose_boxes.size == 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 = file.readline.chomp
@blocks = 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__ == $0
pp = PackerParser.new(ARGF)
puts pp.binsize
puts pp.blocks.join(' ')
pk = Packer.new(pp.size, pp.boxes)
pk.pack
pk.show
end
hornd...@gmail.com
truckbed and generate the ascii only when it is printed. I was trying
to be fancy with the insertion points, but it became too difficult to
maintain so I just added every point and removed those covered by and
surrounding a box during insertion. I sort the boxes by size to put the
biggest ones in first. I'm fairly happy with my solution. Thanks for
the quiz!
-----Horndude77
class TruckBed
def initialize(width,height)
@width,@height = width,height
@boxes = {}
#This list maintains where it is possible to add boxes
@insertion_points = [(0...width).to_a * height,
(0...height).map{|i| [i]*width}.flatten].transpose
sort_insertion_points
end
def insert(box)
@insertion_points.each do |pos|
[box, box.reverse].each do |curr_box|
if fits_at? curr_box, pos then
@boxes[pos] = curr_box
(-1).upto(curr_box[0]) do |x|
(-1).upto(curr_box[1]) do |y|
@insertion_points.delete [x+pos[0],
y+pos[1]]
end
end
sort_insertion_points
return true
end
end
end
false
end
#Stable sort: keep relative order
#This way we control where insertions happen
def sort_insertion_points
n = 0
@insertion_points.sort_by{|x| n+=1; [x[1], n]}
@insertion_points.sort_by{|x| n+=1; [x[0], n]}
end
#See if box fits at pos
def fits_at?(box, pos)
box_min = pos
box_max = [pos[0]+box[0]-1, pos[1]+box[1]-1]
return false if (box_max[0] >= @width) || (box_max[1] >=
@height)
#check for box intersections
@boxes.each do |curr_pos, curr_box|
curr_box_min = [curr_pos[0]-1, curr_pos[1]-1]
curr_box_max = [curr_pos[0]+curr_box[0],
curr_pos[1]+curr_box[1]]
return false if box_min[0] <= curr_box_max[0] && box_max[0]
>= curr_box_min[0] &&
box_min[1] <= curr_box_max[1] && box_max[1] >=
curr_box_min[1]
end
true
end
def to_s
bed = Array.new(@width) { Array.new(@height) {'-'} }
@boxes.each do |pos,box|
box[0].times do |x|
box[1].times do |y|
bed[x+pos[0]][y+pos[1]] = 'X'
end
end
end
bed.transpose.reverse.map {|r| r.join }.join("\n")
end
end
class String
def to_dims
split('x').map {|i| i.to_i}
end
end
truck_bed_dims = ARGF.gets.to_dims
boxes = ARGF.gets.split.map {|box| box.to_dims.sort.reverse}.sort
{|a,b| a[0]*a[1] <=> b[0]*b[1]}
truck_beds = [TruckBed.new(*truck_bed_dims)]
while boxes.size > 0
box = boxes.pop
truck_beds.each do |bed|
if(bed.insert box) then
box = nil
break
end
end
if(box) then
bed = TruckBed.new(*truck_bed_dims)
bed.insert(box)
truck_beds << bed
end
end
puts
puts truck_beds.join("\n\n")
Ruby Quiz
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 Moss is back with a tricky little riddle...