Ruby Quiz #62


#1

Hi all–just found my way into this list by way of Ruby Q., 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


#3

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

Hi all–just found my way into this list by way of Ruby Q., 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 G. II


#4

On Jan 19, 2006, at 4:57 PM, James Edward G. 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…

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



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


#5

On 1/19/06, James Edward G. II removed_email_address@domain.invalid wrote:

On Jan 19, 2006, at 4:57 PM, James Edward G. 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


#6

On 1/19/06, James Edward G. II removed_email_address@domain.invalid wrote:

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



####__
####__
####__
####__


####__

#####
###
##





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


#7

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

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.

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


#8

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


#9

On 1/19/06, James Edward G. II removed_email_address@domain.invalid 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


#10

Adam S. wrote:

On 1/19/06, James Edward G. II removed_email_address@domain.invalid 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


#11

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

I submitted a solution to this quiz.

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

James Edward G. II


#12

On 1/20/06, Markus T. removed_email_address@domain.invalid wrote:

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

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

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


#13

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


#14

Hi,

On 1/19/06, Andrew D. removed_email_address@domain.invalid wrote:

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