module EasyBoxPacker
Public Class Methods
find_smallest_container(items:)
click to toggle source
# File easy-box-packer.rb, line 71 def find_smallest_container(items:) possible_containers = [] invalid_containers = [] min_vol = items.map { |h| h[:dimensions].inject(&:*) }.inject(&:+) # order items from biggest to smallest sorted_items = items.sort_by { |h| h[:dimensions].sort }.reverse # base_container = sorted_items.first based_container = sorted_items.first if sorted_items.size == 1 return based_container[:dimensions] end find_possible_container( possible_containers: possible_containers, invalid_containers: invalid_containers, container: based_container[:dimensions], items: sorted_items.map {|i| i[:dimensions]}, item_index: 1, min_vol: min_vol) select_container = possible_containers.map { |a| a.sort }.sort_by { |a| [a.inject(&:*), a.inject(&:+)] }.each do |c| packing = pack( container: { dimensions: c }, items: items) break c if packing[:packings].size == 1 && packing[:errors].size == 0 end check_container_is_bigger_than_greedy_box({dimensions: select_container}, items) ? item_greedy_box(items) : select_container end
pack(container:, items:)
click to toggle source
# File easy-box-packer.rb, line 3 def pack(container:, items:) packings = [] errors = [] # pack from biggest to smallest items.sort_by { |h| h[:dimensions].sort.reverse }.reverse.each do |item| # If the item is just too big for the container lets give up on this if item[:weight].to_f > container[:weight_limit].to_f errors << "Item: #{item} is too heavy for container" next end # Need a bool so we can break out nested loops once it's been packed item_has_been_packed = false packings.each do |packing| # If this packings going to be too big with this # item as well then skip on to the next packing next if packing[:weight].to_f + item[:weight].to_f > container[:weight_limit].to_f # remove volume size = 0 (not possible to pack) packing[:spaces].reject! { |space| space[:dimensions].inject(:*) == 0 } # try minimum space first packing[:spaces].sort_by { |h| h[:dimensions].sort }.each do |space| # Try placing the item in this space, # if it doesn't fit skip on the next space next unless placement = place(item, space) # Add the item to the packing and # break up the surrounding spaces packing[:placements] += [placement] packing[:weight] += item[:weight].to_f packing[:spaces] -= [space] packing[:spaces] += break_up_space(space, placement) item_has_been_packed = true break end break if item_has_been_packed end next if item_has_been_packed # Can't fit in any of the spaces for the current packings # so lets try a new space the size of the container space = { dimensions: container[:dimensions].sort.reverse, position: [0, 0, 0] } placement = place(item, space) # If it can't be placed in this space, then it's just # too big for the container and we should abandon hope unless placement errors << "Item: #{item} cannot be placed in container" next end # Otherwise lets put the item in a new packing # and break up the remaing free space around it packings += [{ placements: [placement], weight: item[:weight].to_f, spaces: break_up_space(space, placement) }] end if packings.size > 1 && check_container_is_bigger_than_greedy_box(container, items) { packings: generate_packing_for_greedy_box(items), errors: [] } else { packings: packings, errors: errors } end end
Private Class Methods
break_up_space(space, placement)
click to toggle source
# File easy-box-packer.rb, line 193 def break_up_space(space, placement) return_possible_spaces = [ # HEIGHT SPACE => WIDTH => LENGTH [ { dimensions: [ space[:dimensions][0], space[:dimensions][1], space[:dimensions][2] - placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1], space[:position][2] + placement[:dimensions][2] ] }, { dimensions: [ space[:dimensions][0], space[:dimensions][1] - placement[:dimensions][1], placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1] + placement[:dimensions][1], space[:position][2] ] }, { dimensions: [ space[:dimensions][0] - placement[:dimensions][0], placement[:dimensions][1], placement[:dimensions][2] ], position: [ space[:position][0] + placement[:dimensions][0], space[:position][1], space[:position][2] ] } ], # HEIGHT SPACE => LENGTH => WIDTH [ { dimensions: [ space[:dimensions][0], space[:dimensions][1], space[:dimensions][2] - placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1], space[:position][2] + placement[:dimensions][2] ] }, { dimensions: [ space[:dimensions][0] - placement[:dimensions][0], space[:dimensions][1], placement[:dimensions][2] ], position: [ space[:position][0] + placement[:dimensions][0], space[:position][1], space[:position][2] ] }, { dimensions: [ placement[:dimensions][0], space[:dimensions][1] - placement[:dimensions][1], placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1] + placement[:dimensions][1], space[:position][2] ] } ], # LENGTH SPACE => HEIGHT => WIDTH [ { dimensions: [ space[:dimensions][0] - placement[:dimensions][0], space[:dimensions][1], space[:dimensions][2] ], position: [ space[:position][0] + placement[:dimensions][0], space[:position][1], space[:position][2] ] }, { dimensions: [ placement[:dimensions][0], space[:dimensions][1], space[:dimensions][2] - placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1], space[:position][2] + placement[:dimensions][2] ] }, { dimensions: [ placement[:dimensions][0], space[:dimensions][1] - placement[:dimensions][1], placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1] + placement[:dimensions][1], space[:position][2] ] } ], # LENGTH SPACE => WIDTH => HEIGHT [ { dimensions: [ space[:dimensions][0] - placement[:dimensions][0], space[:dimensions][1], space[:dimensions][2] ], position: [ space[:position][0] + placement[:dimensions][0], space[:position][1], space[:position][2] ] }, { dimensions: [ placement[:dimensions][0], space[:dimensions][1] - placement[:dimensions][1], space[:dimensions][2] ], position: [ space[:position][0], space[:position][1] + placement[:dimensions][1], space[:position][2] ] }, { dimensions: [ placement[:dimensions][0], placement[:dimensions][1], space[:dimensions][2] - placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1], space[:position][2] + placement[:dimensions][2] ] } ], # WIDTH SPACE => LENGTH => HEIGHT [ { dimensions: [ space[:dimensions][0], space[:dimensions][1] - placement[:dimensions][1], space[:dimensions][2] ], position: [ space[:position][0], space[:position][1] + placement[:dimensions][1], space[:position][2] ] }, { dimensions: [ space[:dimensions][0] - placement[:dimensions][0], placement[:dimensions][1], space[:dimensions][2] ], position: [ space[:position][0] + placement[:dimensions][0], space[:position][1], space[:position][2] ] }, { dimensions: [ placement[:dimensions][0], placement[:dimensions][1], space[:dimensions][2] - placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1], space[:position][2] + placement[:dimensions][2] ] } ], # WIDTH SPACE => HEIGHT => LENGTH [ { dimensions: [ space[:dimensions][0], space[:dimensions][1] - placement[:dimensions][1], space[:dimensions][2] ], position: [ space[:position][0], space[:position][1] + placement[:dimensions][1], space[:position][2] ] }, { dimensions: [ space[:dimensions][0], placement[:dimensions][1], space[:dimensions][2] - placement[:dimensions][2] ], position: [ space[:position][0], space[:position][1], space[:position][2] + placement[:dimensions][2] ] }, { dimensions: [ space[:dimensions][0] - placement[:dimensions][0], placement[:dimensions][1], placement[:dimensions][2] ], position: [ space[:position][0] + placement[:dimensions][0], space[:position][1], space[:position][2] ] } ] ] # PICK biggest return_possible_spaces.sort_by { |a| a.map {|aa| aa[:dimensions].sort}}.last end
check_container_is_bigger_than_greedy_box(container, items)
click to toggle source
# File easy-box-packer.rb, line 442 def check_container_is_bigger_than_greedy_box(container, items) c = container[:dimensions].sort.reverse greedy_box = item_greedy_box(items) c[0] >= greedy_box[0] && c[1] >= greedy_box[1] && c[2] >= greedy_box[2] && container[:weight_limit].to_f >= items.inject(0) { |sum, i| sum += i[:weight].to_f } end
find_possible_container(possible_containers:,invalid_containers:,container:, items:, item_index:, min_vol:)
click to toggle source
# File easy-box-packer.rb, line 113 def find_possible_container(possible_containers:,invalid_containers:,container:, items:, item_index:, min_vol:) return unless items[item_index] c_length, c_width, c_height = container.sort.reverse b_length, b_width, b_height = items[item_index].sort.reverse c_permutations = [ [c_width, c_height, c_length], [c_length, c_width, c_height], [c_length, c_height, c_width] ] b_permutations = [ [b_width, b_height, b_length], [b_length, b_width, b_height], [b_length, b_height, b_width] ] tmp_possible_containers = [] # (1) loops base_container 3 rotations c_permutations.each do |c_perm| # (2) try to puts items to 3 points, then it will create 3 different possible containers b_permutations.each do |b_perm| tmp_possible_containers << [ c_perm[0] + b_perm[0], [c_perm[1], b_perm[1]].max, [c_perm[2], b_perm[2]].max] tmp_possible_containers << [ [c_perm[0], b_perm[0]].max, c_perm[1] + b_perm[1], [c_perm[2], b_perm[2]].max] tmp_possible_containers << [ [c_perm[0], b_perm[0]].max, [c_perm[1], b_perm[1]].max, c_perm[2]+ b_perm[2]] end end removed_tried_container = tmp_possible_containers.map { |a| a.sort }.uniq - possible_containers - invalid_containers return unless removed_tried_container.any? # (3) loop all container from smallest spaces to biggest space removed_tried_container.sort_by { |a| [a.inject(&:*), a.inject(&:+)] }.each do |cont| # (4) next unless l * w * h >= minimum_space if cont.inject(&:*) >= min_vol possible_containers << cont # else # puts "invalid: #{cont}" # invalid_containers << cont # find_possible_container(possible_containers: possible_containers, invalid_containers: invalid_containers, container: cont, items: items, item_index: item_index + 1, min_vol: min_vol) end end # minimum_space = (removed_tried_container).sort_by { |a| [a.inject(&:*), a.inject(&:+)] }.first minimum_std = removed_tried_container.sort_by { |a| [std(a), a.inject(&:*), a.inject(&:+)] }.first [minimum_std].uniq.compact.each do |cont| find_possible_container(possible_containers: possible_containers, invalid_containers: invalid_containers, container: cont, items: items, item_index: item_index + 1, min_vol: min_vol) end end
generate_packing_for_greedy_box(items)
click to toggle source
# File easy-box-packer.rb, line 448 def generate_packing_for_greedy_box(items) return_h = {placements: [], weight: 0, spaces: []} height = 0 items.each do |i| return_h[:placements] << { dimensions: i[:dimensions], :position=>[0, 0, height], weight: i[:weight].to_f } return_h[:weight] += i[:weight].to_f height += i[:dimensions].sort.first.to_f end [return_h] end
item_greedy_box(items)
click to toggle source
# File easy-box-packer.rb, line 434 def item_greedy_box(items) array_of_lwh = items.map { |i| i[:dimensions].sort.reverse } items_max_length = array_of_lwh.max { |x, y| x[0] <=> y[0] }[0] items_max_width = array_of_lwh.max { |x, y| x[1] <=> y[1] }[1] items_total_height = array_of_lwh.inject(0) { |sum, x| sum+=x[2] }.round(1) [items_max_length, items_max_width, items_total_height] end
place(item, space)
click to toggle source
# File easy-box-packer.rb, line 159 def place(item, space) item_length, item_width, item_height = item[:dimensions].sort.reverse permutations = [ [item_width, item_height, item_length], [item_width, item_length, item_height], [item_height, item_width, item_length], [item_height, item_length, item_width], [item_length, item_width, item_height], [item_length, item_height, item_width] ] possible_rotations_and_margins = [] permutations.each do |perm| # Skip if the item does not fit with this orientation next unless perm[0] <= space[:dimensions][0] && perm[1] <= space[:dimensions][1] && perm[2] <= space[:dimensions][2] possible_margin = [space[:dimensions][0] - perm[0], space[:dimensions][1] - perm[1], space[:dimensions][2] - perm[2]] possible_rotations_and_margins << { margin: possible_margin, rotation: perm } end # select rotation with smallest margin final = possible_rotations_and_margins.sort_by { |a| a[:margin].sort }.first return unless final return { dimensions: final[:rotation], position: space[:position], weight: item[:weight].to_f } end
std(contents)
click to toggle source
# File easy-box-packer.rb, line 105 def std(contents) n = contents.size contents.map!(&:to_f) mean = contents.reduce(&:+)/n sum_sqr = contents.map {|x| x * x}.reduce(&:+) Math.sqrt(((sum_sqr - n * mean * mean)/(n-1)).abs) end