From: Adam Shelly <adam.shelly@...>
Date: 2006-01-20T10:44:36+09:00
Subject: Re: Ruby Quiz #62

On 1/19/06, James Edward Gray II <james@grayproductions.net> wrote:
> On Jan 19, 2006, at 4:57 PM, James Edward Gray II wrote:
>
> > I'm actually wondering if the algorithm couldn't be adapted to
> > handle this.  I believe it's possible.  The placement of the first
> > block ruins 6 other squares (because of padding).  When placed
> > correctly, it only ruins three.  I bet the code could be made to
> > spot this...

I spent a bunch of time tuesday playing with different heuristics. I
couldn't find one single rule that did the best placement every time. 
I had 3 pretty good variations on the packing algorithm, but I could
always find a testcase where one of them needed an extra trunk.
I'm pretty sure your modification will still have extra trunks occasionally.

> >Great example.  I was looking for one of these yesterday, but kept
> >coming up short.

In case you want more perfect sets like this,  I rewrote
"troublemaker" to generate them:

------------------Troublemaker2.rb------------------------------

def rrand rng  #rand ought to take a range argument...
  rng.first+rand(rng.to_a.last-rng.first)
end

SplitRange = (3..8)  #boxes bigger than a random number in this range
will be split.
def splitt! set
  set2, changed = [],false
  set.each {|b|
    n=rand(2)
    if (n==0) and (b[0] > rrand(SplitRange) )
      changed = true
      splitline = rrand(2...b[0])
      set2+=[[splitline-1,b[1]],[b[0]-splitline,b[1]]]
    elsif (n==1) and (b[1] > rrand(SplitRange) )
      changed = true
      splitline = rrand(2...b[1])
      set2+=[[b[0],splitline-1],[b[0],b[1]-splitline]]
    else
      set2+=[b]
    end
  }
  set.replace set2
  !changed
end

def make m,n
  done=nil
  p = [[m,n]]
  while !done
     done = splitt! p
  end
  p
end

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 += make *trunk_size
 }
 puts trunk_size.join("x")
puts boxes.map{|box| box.join("x")}.join(" ")
end

------------------------------------------------

-Adam