# Ruby Quiz #62

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

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.

was Ilmari’s and Adam’s excellent (and early) contributions. It was
impossible to improve on them.

Christer

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

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

# try it both ways
# 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

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

On 1/19/06, James Edward G. II [email protected] 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

On 1/19/06, James Edward G. II [email protected] 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.

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…

James Edward G. II

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:

On 1/19/06, James Edward G. II [email protected] 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…

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

On 1/19/06, James Edward G. II [email protected] 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…

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

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

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

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

On 1/20/06, Markus T. [email protected] 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.

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

-----Horndude77

I’m not sure this link will work, but here goes:

E

Hi,

On 1/19/06, Andrew D. [email protected] 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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.