Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.