Skip to content

Instantly share code, notes, and snippets.

@phiggins
Forked from joevandyk/bin_packing.rb
Last active September 27, 2017 02:10
Show Gist options
  • Save phiggins/6b35128619c1eca42982149eea0d0c44 to your computer and use it in GitHub Desktop.
Save phiggins/6b35128619c1eca42982149eea0d0c44 to your computer and use it in GitHub Desktop.
require "minitest/autorun"
require "benchmark/ips"
class CachingPack
def self.call(inventory, order)
return if inventory.nil? || inventory.empty?
return if inventory.inject(:+) < order
loop do
r = cached_pack(inventory, order)
return r if r
order += 1
end
end
def self.cached_pack(inventory, order)
@cache ||= {}
inventory_hash = inventory.hash
if @cache[inventory_hash] && @cache[inventory_hash].key?(order)
return @cache[inventory_hash][order]
end
result = pack(inventory, order)
@cache[inventory_hash] ||= {}
@cache[inventory_hash][order] = result
result
end
def self.pack(inventory, order)
if inventory.empty?
nil
elsif order < inventory[0]
cached_pack(inventory.drop(1), order)
elsif order == inventory.first
[inventory.first]
else
x = cached_pack(inventory.drop(1), order)
y = cached_pack(inventory.drop(1), order - inventory.first)
choices = []
choices << x if x
choices << [inventory.first] + y if y
choices.min_by(&:length)
end
end
end
class SlidingWindowPack
def self.call(inventory, order)
return if inventory.nil? || inventory.empty?
start = inventory.index {|i| i <= order }
return unless start
inventory = inventory.drop(start)
1.upto(inventory.size) do |i|
slice = inventory.take(i)
return slice if slice.inject(:+) >= order
end
nil
end
end
module SharedTests
def test_empty
assert_nil klass.call([], 10)
end
def test_exact
assert_equal [10], klass.call([10, 5], 10)
end
def test_exact_multiple
assert_equal [10, 1], klass.call([10, 1], 11)
end
def test_exact_multiple_with_excess_inventory
assert_equal [10, 5], klass.call([10, 5, 1], 15)
end
def test_assert_overselling
assert_equal [10, 5], klass.call([10, 5, 1], 14)
end
def test_order_smaller_than_largest
assert_equal [5, 1, 1], klass.call([10, 8, 5, 1, 1], 7)
end
end
class CachingPackTest < Minitest::Test
def klass ; CachingPack ; end
include SharedTests
end
class SlidingWindowPackTest < Minitest::Test
def klass ; SlidingWindowPack ; end
include SharedTests
end
pathological_input = Array.new(1_000, 1)
order = 10
Benchmark.ips do |x|
x.report("caching") { CachingPack.call(pathological_input, order) }
x.report("sliding") { SlidingWindowPack.call(pathological_input, order) }
x.compare!
end
@phiggins
Copy link
Author

pete@rhombus:~/projects/bin_packing$ ruby bin_packing.rb 
Warming up --------------------------------------
             caching   256.000  i/100ms
             sliding    20.833k i/100ms
Calculating -------------------------------------
             caching      6.320k (± 2.1%) i/s -     31.744k in   5.025259s
             sliding    223.238k (± 2.5%) i/s -      1.125M in   5.042578s

Comparison:
             sliding:   223238.3 i/s
             caching:     6319.7 i/s - 35.32x  slower

Run options: --seed 39017

# Running:

............

Finished in 0.001098s, 10931.7494 runs/s, 10931.7494 assertions/s.

12 runs, 12 assertions, 0 failures, 0 errors, 0 skips

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment