From: Ilmari Heikkinen <ilmari.heikkinen@...>
Date: 2006-01-14T00:22:21+09:00
Subject: Re: [QUIZ] Packing (#62)

On 1/13/06, Ruby Quiz <james@grayproductions.net> wrote:> The three rules of 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:>> http://www.rubyquiz.com/>> 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
Good luck, everyone!
Finding an optimal solution is going to be quite computationally intensive,so unoptimal solvers are also welcome.
Checking that the solution you get really is optimal might be a wee bit hard,so here's a little program that generates problems with known optimalsolutions (these are without the 1 unit padding though):
$ ruby troublemaker.rb 6x6 2 # 2 6x6 trunks6x64x3 4x3 2x6 4x3 4x3 2x6
$ cat troublemaker.rbdef randomly_cut_up(box)  if box.min > 3    cut = 3+rand(box.max-3)    if box.max == box[0]      randomly_cut_up([cut, box[1]]) +      randomly_cut_up([box[0]-cut, box[1]])    else      randomly_cut_up([box[0], cut]) +      randomly_cut_up([box[0], box[1]-cut])    end  else    [box]  endend
if __FILE__ == $0  trunk_size = ARGV[0].split("x").map{|i| i.to_i}  trunk_count = ARGV[1].to_i
  boxes = []
  (1..trunk_count).each{|i|    boxes += randomly_cut_up trunk_size  }
  #puts "requested volume: #{trunk_size[0]*trunk_size[1]*trunk_count}"  #puts "cut up volume: #{boxes.inject(0){|s,b| s+b[0]*b[1]}}"
  box_str = boxes.map{|box| box.join("x")}.join(" ")  puts trunk_size.join("x")  puts box_strend