bin_packing.rb

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

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