joevandyk · September 27, 2017 02:10 · Sep 26, 2017 · Sep 26, 2017 · Sep 26, 2017 · Sep 26, 2017
diff --git a/bin_packing.rb b/bin_packing.rb
@@ -1,6 +1,7 @@
 require 'active_support'
 require 'active_support/core_ext'
 require 'ruby-prof'
+require "minitest/autorun"
 
 class Array
   def rest
@@ -49,21 +50,33 @@ def pack(inventory, order)
   end
 end
 
-puts nil == pack([], 10)
-puts [10] == pack([10, 5], 10)
-puts [10, 1] == pack([10, 1], 11)
-puts [10, 5] == pack([10, 5, 1], 15)
-puts [10, 5] == optimize_pack([10, 5, 1], 14)
+class T < Minitest::Test
+  def test_empty
+    assert_nil optimize_pack([], 10)
+  end
 
-lots_of_one_pounds = Array.new(500, 1)
+  def test_exact
+    assert_equal [10], optimize_pack([10, 5], 10)
+  end
 
-result = nil
-bm = Benchmark.measure do
-  RubyProf.start
-  puts Array.new(10, 1) == optimize_pack(lots_of_one_pounds, 10)
-  result = RubyProf.stop
-end
-puts bm
+  def test_exact_multiple
+    assert_equal [10, 1], optimize_pack([10, 1], 11)
+  end
 
-printer = RubyProf::GraphHtmlPrinter.new(result)
-printer.print(File.open('prof.html', 'w+'))
+  def test_exact_multiple_with_excess_inventory
+    assert_equal [10, 5], optimize_pack([10, 5, 1], 15)
+  end
+
+  def test_assert_overselling
+    assert_equal [10, 5], optimize_pack([10, 5, 1], 14)
+  end
+
+  def test_benchmark
+    RubyProf.start
+    lots_of_one_pounds = Array.new(500, 1)
+    assert_equal Array.new(10, 1), optimize_pack(lots_of_one_pounds, 10)
+    result = RubyProf.stop
+    printer = RubyProf::FlatPrinterWithLineNumbers.new(result)
+    printer.print(STDOUT, min_percent: 2)
+  end
+end
diff --git a/bin_packing.rb b/bin_packing.rb
@@ -1,3 +1,7 @@
+require 'active_support'
+require 'active_support/core_ext'
+require 'ruby-prof'
+
 class Array
   def rest
     self[1..-1]
@@ -15,13 +19,14 @@ def optimize_pack(inventory, order)
 end
 
 def cached_pack(inventory, order)
-  @hash = {}
-  if @hash[inventory] && @hash[inventory].key?(order)
-    return @hash[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)
-  @hash[inventory] ||= {}
-  @hash[inventory][order] = result
+  @cache[inventory_hash] ||= {}
+  @cache[inventory_hash][order] = result
   result
 end
 
@@ -40,17 +45,25 @@ def pack(inventory, order)
     choices << x if x
     choices << [inventory.first] + y if y
 
-    choices.min_by { |a| a.length }
+    choices.min_by(&:length)
   end
 end
 
-
 puts nil == pack([], 10)
 puts [10] == pack([10, 5], 10)
 puts [10, 1] == pack([10, 1], 11)
 puts [10, 5] == pack([10, 5, 1], 15)
-puts pack([10, 5, 1], 14)
 puts [10, 5] == optimize_pack([10, 5, 1], 14)
 
-lots_of_one_pounds = Array.new(100, 1)
-p optimize_pack(lots_of_one_pounds, 10) # takes a while
+lots_of_one_pounds = Array.new(500, 1)
+
+result = nil
+bm = Benchmark.measure do
+  RubyProf.start
+  puts Array.new(10, 1) == optimize_pack(lots_of_one_pounds, 10)
+  result = RubyProf.stop
+end
+puts bm
+
+printer = RubyProf::GraphHtmlPrinter.new(result)
+printer.print(File.open('prof.html', 'w+'))
diff --git a/bin_packing.rb b/bin_packing.rb
@@ -1,31 +1,40 @@
-# A greedy algorithm for bin packing
-
 class Array
   def rest
     self[1..-1]
   end
 end
 
-def optimize_pack inventory, order
+def optimize_pack(inventory, order)
+  return nil if inventory.sum < order
   loop do
-    r = pack(inventory, order)
+    r = cached_pack(inventory, order)
 
     return r if r
     order += 1
   end
 end
 
-def pack inventory, order
-  case
-  when inventory.empty?
+def cached_pack(inventory, order)
+  @hash = {}
+  if @hash[inventory] && @hash[inventory].key?(order)
+    return @hash[inventory][order]
+  end
+  result = pack(inventory, order)
+  @hash[inventory] ||= {}
+  @hash[inventory][order] = result
+  result
+end
+
+def pack(inventory, order)
+  if inventory.empty?
     nil
-  when order < inventory[0]
-    pack(inventory.rest, order)
-  when order == inventory.first
+  elsif order < inventory[0]
+    cached_pack(inventory.rest, order)
+  elsif order == inventory.first
     [inventory.first]
   else
-    x = pack(inventory.rest, order)
-    y = pack(inventory.rest, order - inventory.first)
+    x = cached_pack(inventory.rest, order)
+    y = cached_pack(inventory.rest, order - inventory.first)
 
     choices = []
     choices << x if x
@@ -41,4 +50,7 @@ def pack inventory, order
 puts [10, 1] == pack([10, 1], 11)
 puts [10, 5] == pack([10, 5, 1], 15)
 puts pack([10, 5, 1], 14)
-puts [10, 5] == optimize_pack([10, 5, 1], 14)
+puts [10, 5] == optimize_pack([10, 5, 1], 14)
+
+lots_of_one_pounds = Array.new(100, 1)
+p optimize_pack(lots_of_one_pounds, 10) # takes a while
diff --git a/bin_packing.rb b/bin_packing.rb
@@ -0,0 +1,44 @@
+# A greedy algorithm for bin packing
+
+class Array
+  def rest
+    self[1..-1]
+  end
+end
+
+def optimize_pack inventory, order
+  loop do
+    r = pack(inventory, order)
+
+    return r if r
+    order += 1
+  end
+end
+
+def pack inventory, order
+  case
+  when inventory.empty?
+    nil
+  when order < inventory[0]
+    pack(inventory.rest, order)
+  when order == inventory.first
+    [inventory.first]
+  else
+    x = pack(inventory.rest, order)
+    y = pack(inventory.rest, order - inventory.first)
+
+    choices = []
+    choices << x if x
+    choices << [inventory.first] + y if y
+
+    choices.min_by { |a| a.length }
+  end
+end
+
+
+puts nil == pack([], 10)
+puts [10] == pack([10, 5], 10)
+puts [10, 1] == pack([10, 1], 11)
+puts [10, 5] == pack([10, 5, 1], 15)
+puts pack([10, 5, 1], 14)
+puts [10, 5] == optimize_pack([10, 5, 1], 14)
No results found