Ruby Quiz #62

ruby-talk
1

Hi all--just found my way into this list by way of Ruby Quiz, which looks
amazing, and I look forward to participating in successive weeks. I'm a
newcomer to Ruby in general.

I took a few shots at #62 and was unable to come up with anything that would
terminate in a reasonable amount of time. ("reasonable" = "overnight") But
I did look over the posted answer and it seems that the algorithm fails in
the case of a 3x6 truck bed with boxes of sizes 2x3, 1x3, and 1x3--it
concludes that two loads are needed, while the other two solutions give the
correct result of a single load:

···

###
###
___
###
___
###

I think that the nature of this bug is that placing the largest box in the
corner may exclude an optimal solution--I do not know if this is simply a
problem of orientation, or something larger. As the problem specified
finding the minimum number of trips, I thought that this warranted
discussion.

As I have just joined this list, I shall have to apologize if this has
already been talked about.

2

Andrew,

these solutions are not guaranteeing the minimum. They are heuristical.
Using one extra trunk is their normal behaviour. Look at the thesis
mentioned earlier.

I tried to find the mathematically perfect solution, but it takes hours
or years, to execute.

There has not been much conversation about this quiz. I think the reason
was Ilmari's and Adam's excellent (and early) contributions. It was
impossible to improve on them.

Christer

···

--
Posted via http://www.ruby-forum.com/.

3

Hi all--just found my way into this list by way of Ruby Quiz, which looks
amazing

Thanks!

and I look forward to participating in successive weeks. I'm a
newcomer to Ruby in general.

Then let me welcome you.

I took a few shots at #62 and was unable to come up with anything that would
terminate in a reasonable amount of time. ("reasonable" = "overnight") But
I did look over the posted answer and it seems that the algorithm fails in
the case of a 3x6 truck bed with boxes of sizes 2x3, 1x3, and 1x3--it
concludes that two loads are needed, while the other two solutions give the
correct result of a single load:

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

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...

James Edward Gray II

···

On Jan 19, 2006, at 2:22 PM, Andrew Dudzik wrote:

4

Hi,

I took a few shots at #62 and was unable to come up with anything that would
terminate in a reasonable amount of time. ("reasonable" = "overnight")

I guess the computational complexity of an optimal solver is n!, which
would make solving anything bigger than 10 boxes a feat. And since bin
packing problem is strongly NP-hard, checking that a solution is
optimal would take non-polynomial time as well.

A nice approach might be using neural nets / evolutionary algorithms /
simulated annealing / some other funky optimization algorithm for
finding solutions that are better than what the greedy algorithms
give, without taking years to run.

-Ilmari

···

On 1/19/06, Andrew Dudzik <adudzik@gmail.com> wrote:

5

This version of the code seems to fix at least this case:

Neo:~/Desktop$ cat bug_example.txt
3x6
2x3 1x3 1x3
Neo:~/Desktop$ ruby pack.rb bug_example.txt

···

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...

###
___
###
___
###
Neo:~/Desktop$ cat pack.rb
class Array
   def delete_first item
     delete_at index(item)
   end

   def rotate
     d = dup
     d.push d.shift
     d
   end
end

class Trunk
   def initialize(w,h)
     @w = w
     @h = h
     @items =
     @rows = (1..@h+2).map{ "_"*(@w+2) }
   end

   def add box
     # try it both ways
     possibles = [try_adding(box), try_adding(box.rotate)].compact
     # make sure we found a way
     return if possibles.empty?
     # use the best option we found
     score, rows, box = possibles.max { |a, b| a.first <=> b.first }
     @rows = rows
     @items = box
     true
   end

   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 }
       # modify the rows
       rows = @rows.map { |row| row.dup }
       rows[i+1, box[1]].each{|s|
         s[idx+1, box[0]] = "#" * box[0]
       }
       # score the remaining open space
       score = rows[1..-2].map { |row| row[/_(_+)/, 1] }.compact.
                           map { |open| open.size }.inject { |sum, n| sum + n }
       # return the score and the things we would need to change
       return score, rows, box
     }
     nil
   end

   def empty?
     @items.empty?
   end

   def to_s
     @rows[1..-2].map{|r|r[1..-2]}.join("\n")
   end
end

trunk = gets.strip.split("x").map{|i| i.to_i}
boxes = gets.strip.split(" ").map{|s| s.split("x").map{|i| i.to_i} }

boxes = boxes.sort_by{|b| b.inject{|f,i| f*i} }.reverse
trunks = [Trunk.new(*trunk)]
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
puts
puts trunks.join("\n\n")

James Edward Gray II

6

> 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

···

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:

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

-Adam

7

This version of the code seems to fix at least this case:

There's a small bug in your code, James:
If you pass a box that fits the trunk exactly, you get an exception.
The culprit is this line from #try_adding box

       # score the remaining open space
       score = rows[1..-2].map { |row| row[/_(_+)/, 1] }.compact.
                           map { |open| open.size }.inject { |sum, n|
sum + n }

score is nil if there is no open space. you need to make it ...
inject(0) {|sum,n| ...

You've got a good heuristic, but it still makes mistakes. Here's a
case that needs an extra trunk with your solution:

C:\ruby\RUBYRE~1\Main\Quiz>more 662.txt
6x6
2x3 2x2 3x6 1x6 4x1 4x4

C:\ruby\RUBYRE~1\Main\Quiz>pack.rb 662.txt

···

On 1/19/06, James Edward Gray II <james@grayproductions.net> wrote:

######
######
######
______
######
______

####__
####__
####__
####__
______
####__

###_##
###_##
______
______
______
______

Those 2 in the last trunk ought to be where in the 1st trunk, and the
1x6 should be in the 2nd trunk. I think it's impossible to have a
perfect solution without an incredibly deep search.

On a totally unrelated note - I discovered something odd when working
on this solution:
irb(main):010:0> r=1..9
=> 1..9
irb(main):011:0> r.last
=> 9
irb(main):012:0> r.include? r.last
=> true
irb(main):013:0> r=1...9
=> 1...9
irb(main):014:0> r.last
=> 9
irb(main):015:0> r.include? r.last
=> false

I really expected (1...9).last to return 8. I guess this is just
another way ranges are screwy.

-Adam

8

This version of the code seems to fix at least this case:

There's a small bug in your code, James:
If you pass a box that fits the trunk exactly, you get an exception.
The culprit is this line from #try_adding box

       # score the remaining open space
       score = rows[1..-2].map { |row| row[/_(_+)/, 1] }.compact.
                           map { |open| open.size }.inject { |sum, n|
sum + n }

score is nil if there is no open space. you need to make it ...
inject(0) {|sum,n| ...

Great catch again. I'm glad someone is watching over me. I need all the help I can get, as we can see!

You've got a good heuristic, but it still makes mistakes.

Oh, no doubt. Good example.

On a totally unrelated note - I discovered something odd when working
on this solution:
irb(main):010:0> r=1..9
=> 1..9
irb(main):011:0> r.last
=> 9
irb(main):012:0> r.include? r.last
=> true
irb(main):013:0> r=1...9
=> 1...9
irb(main):014:0> r.last
=> 9
irb(main):015:0> r.include? r.last
=> false

I really expected (1...9).last to return 8. I guess this is just
another way ranges are screwy.

Na, that's not odd at all. Just tell yourself .. is inclusive and ... is exclusive (with regards to the last member). See how that extra dot pushes it off the end there... :wink:

James Edward Gray II

···

On Jan 19, 2006, at 8:06 PM, Adam Shelly wrote:

On 1/19/06, James Edward Gray II <james@grayproductions.net> wrote:

9

It seems my posts from google groups aren't making it over to the main
ruby list. Anyone know why this would be happening? I can see them fine
from google, but when I search through the ruby list they don't show up.
So, I'm trying from the ruby forum. I submitted a solution to this quiz.
Should I try and re-post?

-----Horndude77

I'm not sure this link will work, but here goes:
http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/9e889e4a6ea69434/4d16d42bc9ee0247#4d16d42bc9ee0247

···

--
Posted via http://www.ruby-forum.com/.

10

That part I know. But I expected (1...x) to be exactly equivalent to (1..x-1)
The difference bit me when I was trying to write a version of rand
that took a range (It would be nice if that was a built-in...). My
first attempt is below, but it returns the wrong results when rng is
an exclusive range.
def rrand rng
  rng.first + rand(rng.last-rng.first)
end

-Adam

···

On 1/19/06, James Edward Gray II <james@grayproductions.net> wrote:

On Jan 19, 2006, at 8:06 PM, Adam Shelly wrote:
> irb(main):013:0> r=1...9
> => 1...9
> irb(main):014:0> r.last
> => 9
> irb(main):015:0> r.include? r.last
> => false
>
> I really expected (1...9).last to return 8. I guess this is just
> another way ranges are screwy.

Na, that's not odd at all. Just tell yourself .. is inclusive
and ... is exclusive (with regards to the last member). See how that
extra dot pushes it off the end there... :wink:

11

Adam Shelly wrote:

···

On 1/19/06, James Edward Gray II <james@grayproductions.net> wrote:

Na, that's not odd at all. Just tell yourself .. is inclusive
and ... is exclusive (with regards to the last member). See how that
extra dot pushes it off the end there... :wink:

That part I know. But I expected (1...x) to be exactly equivalent to
(1..x-1)
The difference bit me when I was trying to write a version of rand
that took a range (It would be nice if that was a built-in...). My
first attempt is below, but it returns the wrong results when rng is
an exclusive range.
def rrand rng
  rng.first + rand(rng.last-rng.first)
end

-Adam

It's not equivalent because you forgot about floating point numbers.

irb(main):001:0> (1...9).include? 8.9
=> true

--
Posted via http://www.ruby-forum.com/\.

12

I'm sorry I missed this. I didn't know that gateway is misbehaving. Thanks for pointing it out to me.

James Edward Gray II

···

On Jan 19, 2006, at 11:41 PM, Jay Anderson wrote:

I submitted a solution to this quiz.

13

Jay Anderson wrote:

It seems my posts from google groups aren't making it over to the main
ruby list. Anyone know why this would be happening? I can see them fine
from google, but when I search through the ruby list they don't show up.
So, I'm trying from the ruby forum. I submitted a solution to this quiz.
Should I try and re-post?

There are occasional problems with the ML <-> NG gateway. I have
actually found that http://www.ruby-forum.com is often the most
up-to-date one :slight_smile:

-----Horndude77

I'm not sure this link will work, but here goes:
http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/9e889e4a6ea69434/4d16d42bc9ee0247#4d16d42bc9ee0247

E

···

--
Posted via http://www.ruby-forum.com/\.

14

Exactly. Think of a..b in ruby as equivalent[1] to [a, b] in
mathematics, and a...b as equivalent to [a, b). The latter will
include (b - delta) for all delta > 0 and < (b - a), no matter how
small. The only difference between [a, b] and [a, b) is the *one*
value b. In set terminology: [a, b] - [a, b) = { b } and |[a, b] - [a,
b)| = 1.

Jacob Fugal

[1] This equivalence/analogy only holds for well ordered Range objects
such as those on Numeric. Don't expect this to make any sense for
non-Numeric ranges. I never use ... with non-numeric ranges anyways.

···

On 1/20/06, Markus Tarmak <m4rkusha@gmail.com> wrote:

Adam Shelly wrote:
> That part I know. But I expected (1...x) to be exactly equivalent to
> (1..x-1)

It's not equivalent because you forgot about floating point numbers.

irb(main):001:0> (1...9).include? 8.9
=> true