bin_packing.rb

require 'active_support'
require 'active_support/core_ext'
require 'ruby-prof'
require "minitest/autorun"

class Array
  def rest
    self[1..-1]
  end
end

def optimize_pack(inventory, order)
  return nil if inventory.sum < order
  loop do
    r = cached_pack(inventory, order)

    return r if r
    order += 1
  end
end

def 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 pack(inventory, order)
  if inventory.empty?
    nil
  elsif order < inventory[0]
    cached_pack(inventory.rest, order)
  elsif order == inventory.first
    [inventory.first]
  else
    x = cached_pack(inventory.rest, order)
    y = cached_pack(inventory.rest, order - inventory.first)

    choices = []
    choices << x if x
    choices << [inventory.first] + y if y

    choices.min_by(&:length)
  end
end

class T < Minitest::Test
  def test_empty
    assert_nil optimize_pack([], 10)
  end

  def test_exact
    assert_equal [10], optimize_pack([10, 5], 10)
  end

  def test_exact_multiple
    assert_equal [10, 1], optimize_pack([10, 1], 11)
  end

  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