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
