Ruby Quiz #62

[Andrew Dudzik]

------=_Part_1051_27618755.1137702130810
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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 woul=
d
terminate in a reasonable amount of time. ("reasonable" =3D "overnight") B=
ut
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.

------=_Part_1051_27618755.1137702130810--

 

[James Edward Gray II]

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 Gray II

 

[horndude77]

I don't think this can be fixed in general without slowing the
algorithm way down. The problem itself is NP-hard like the travelling
salesman problem (http://en.wikipedia.org/wiki/Bin_packing,
http://mathworld.wolfram.com/Bin-PackingProblem.html). To make it
faster people use an algorithm that runs in a reasonable amount of time
and produces a "good enough" solution which is probably not optimal.

Also just a note. I did submit a solution which shows up in google
groups, but somehow it didn't make it to the ruby list. Is there any
reason this would happen? I'm thinking that's why it's not included on
the ruby quiz page and why in the recap it said that only three people
attempted it. Should I try resubmitting it?

 

[Adam Shelly]

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

 

[Adam Shelly]

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 =3D 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=3D1..9
=3D> 1..9
irb(main):011:0> r.last
=3D> 9
irb(main):012:0> r.include? r.last
=3D> true
irb(main):013:0> r=3D1...9
=3D> 1...9
irb(main):014:0> r.last
=3D> 9
irb(main):015:0> r.include? r.last
=3D> false

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

-Adam

 

[James Edward Gray II]

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

James Edward Gray II

 

[Jay Anderson]

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...e4a6ea69434/4d16d42bc9ee0247#4d16d42bc9ee0247

 

[Adam Shelly]

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

-Adam

 

[Markus Tarmak]

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

 

[James Edward Gray II]

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 Gray II

 

[Jacob Fugal]

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

irb(main):001:0> (1...9).include? 8.9
=3D> 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) =3D { b } and |[a, b] - [a,
b)| =3D 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.

 

[Eero Saynatkari]

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:
http://groups.google.com/group/comp...e4a6ea69434/4d16d42bc9ee0247#4d16d42bc9ee0247

E

 

[Ilmari Heikkinen]

SGksCgpPbiAxLzE5LzA2LCBBbmRyZXcgRHVkemlrIDxhZHVkemlrQGdtYWlsLmNvbT4gd3JvdGU6
Cj4gSSB0b29rIGEgZmV3IHNob3RzIGF0ICM2MiBhbmQgd2FzIHVuYWJsZSB0byBjb21lIHVwIHdp
dGggYW55dGhpbmcgdGhhdCB3b3VsZAo+IHRlcm1pbmF0ZSBpbiBhIHJlYXNvbmFibGUgYW1vdW50
IG9mIHRpbWUuICgicmVhc29uYWJsZSIgPSAib3Zlcm5pZ2h0IikKCkkgZ3Vlc3MgdGhlIGNvbXB1
dGF0aW9uYWwgY29tcGxleGl0eSBvZiBhbiBvcHRpbWFsIHNvbHZlciBpcyBuISwgd2hpY2gKd291
bGQgbWFrZSBzb2x2aW5nIGFueXRoaW5nIGJpZ2dlciB0aGFuIDEwIGJveGVzIGEgZmVhdC4gQW5k
IHNpbmNlIGJpbgpwYWNraW5nIHByb2JsZW0gaXMgc3Ryb25nbHkgTlAtaGFyZCwgY2hlY2tpbmcg
dGhhdCBhIHNvbHV0aW9uIGlzCm9wdGltYWwgd291bGQgdGFrZSBub24tcG9seW5vbWlhbCB0aW1l
IGFzIHdlbGwuCgpBIG5pY2UgYXBwcm9hY2ggbWlnaHQgYmUgdXNpbmcgbmV1cmFsIG5ldHMgLyBl
dm9sdXRpb25hcnkgYWxnb3JpdGhtcyAvCnNpbXVsYXRlZCBhbm5lYWxpbmcgLyBzb21lIG90aGVy
IGZ1bmt5IG9wdGltaXphdGlvbiBhbGdvcml0aG0gZm9yCmZpbmRpbmcgc29sdXRpb25zIHRoYXQg
YXJlIGJldHRlciB0aGFuIHdoYXQgdGhlIGdyZWVkeSBhbGdvcml0aG1zCmdpdmUsIHdpdGhvdXQg
dGFraW5nIHllYXJzIHRvIHJ1bi4KCgotSWxtYXJpCg==