Skip to content

Instantly share code, notes, and snippets.

@btakita btakita/input.txt
Last active Mar 25, 2019

Embed
What would you like to do?
MaxMyInterest knapsack interview problem
$15.05
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
require 'set'
ValidMenuLineItems = Struct.new(:currency__target, :price__target, :arr__arr__MenuLineItem__valid, :arr__arr__count__MenuLineItem__valid)
MenuItem = Struct.new(:name, :currency, :price)
MenuLineItem = Struct.new(:name, :currency, :price, :count, :subtotal)
=begin
= puts_valid_menu_line_items
= Example usage
See the bottom of this file for example usage.
The contents of input.txt are passed to a new instance of FactoryValidMenuItems & the #call return value is formatted
=end
def puts_valid_menu_line_items(txt_input)
currency__target, price__target, arr__arr__MenuLineItem__valid = *FactoryValidMenuItems.new(txt_input).call
if arr__arr__MenuLineItem__valid && !arr__arr__MenuLineItem__valid.empty?
printf "The following menu combinations match the target price of #{currency__target}%.2f\n", price__target
arr__arr__MenuLineItem__valid.each_with_index do |arr__MenuLineItem__valid, i|
puts "\tCombination #{i + 1}"
arr__MenuLineItem__valid.each do |__MenuLineItem__valid|
name, currency, price, count, subtotal = *__MenuLineItem__valid
next if count == 0
printf "\t\t%-20s %8s\n", "#{count} #{name}", sprintf("#{currency}%.2f", subtotal)
end
end
else
printf "No combination of dishes will be equal in cost to the target price of #{currency__target}%.2f\n", price__target
end
end
class FactoryValidMenuItems
attr_accessor :txt__input
attr_reader :currency__target, :price__target, :arr__MenuItem
def initialize(txt__input)
@txt__input = txt__input
@set__arr__count__MenuItem__valid = Set.new
end
def call
set__arr__count__MenuItem__valid.clear
@currency__target, @price__target, @arr__MenuItem = _arr__input
arr__arr__MenuLineItem__valid = _arr__arr__MenuLineItem__valid
arr__arr__count__MenuLineItem__valid = arr__arr__MenuLineItem__valid.map do |arr__MenuLineItem__valid|
arr__MenuLineItem__valid.map(&:count)
end
ValidMenuLineItems.new(currency__target, price__target, arr__arr__MenuLineItem__valid, arr__arr__count__MenuLineItem__valid)
end
protected
attr_reader :set__arr__count__MenuItem__valid
def _cents(price)
(price * 100).to_i
end
def cents__total
_cents(price__target)
end
def _arr__input
arr__txt__input = txt__input.split("\n")
currency__target, price__target = _arr__currency__price(arr__txt__input[0])
arr__MenuItem = arr__txt__input[1..-1].map do |input|
arr__input = input.split(',')
MenuItem.new(arr__input[0], *_arr__currency__price(arr__input[1]))
end
[currency__target, price__target, arr__MenuItem]
end
def _arr__arr__MenuLineItem__valid()
arr__count__MenuItem__zero = Array.new(arr__MenuItem.length)
arr__MenuItem.each_with_index do |root_MenuItem, i|
name, currency, price = *root_MenuItem
cents = _cents(price)
max_count__MenuItem__root = (cents__total / cents).to_i
max_count__MenuItem__root.downto(0) do |count__MenuItem__root|
arr__count__MenuItem__root = _arr__count__MenuItem__copy(arr__count__MenuItem__zero, i, count__MenuItem__root)
add__set__arr__count__MenuItem__valid(arr__count__MenuItem__root)
end
end
set__arr__count__MenuItem__valid.to_a.map do |arr__count__MenuItem__valid|
arr__count__MenuItem__valid.each_with_index.map do |count, i|
name, currency, price = *arr__MenuItem[i]
subtotal = (_cents(price) * count) / 100.0
MenuLineItem.new(name, currency, price, count, subtotal)
end
end
end
def add__set__arr__count__MenuItem__valid(arr__count__MenuItem)
cents__arr__count__MenuItem = _cents__arr__count__MenuItem(arr__count__MenuItem)
if cents__total == cents__arr__count__MenuItem
arr__count__MenuItem = _arr__count__MenuItem__copy__replace__null__with__0(arr__count__MenuItem)
set__arr__count__MenuItem__valid.add(arr__count__MenuItem)
end
return if cents__arr__count__MenuItem >= cents__total
cents__remaining = cents__total - cents__arr__count__MenuItem
arr__MenuItem.each_with_index do |__MenuItem, i|
next unless arr__count__MenuItem[i].nil? # traversed
cents__MenuItem = _cents(arr__MenuItem[i].price)
max_count__MenuItem__remaining = (cents__remaining / cents__MenuItem).to_i
max_count__MenuItem__remaining.downto(0) do |count__MenuItem|
arr__count__MenuItem = _arr__count__MenuItem__copy(arr__count__MenuItem, i, count__MenuItem)
add__set__arr__count__MenuItem__valid(arr__count__MenuItem) if count__MenuItem > 0
end
end
end
def _arr__count__MenuItem__copy(arr__count__MenuItem, i, count)
arr__count__MenuItem__copy = arr__count__MenuItem.dup
arr__count__MenuItem__copy[i] = count
arr__count__MenuItem__copy
end
def _arr__count__MenuItem__copy__replace__null__with__0(arr__count__MenuItem)
arr__count__MenuItem.map do |count, i|
count || 0
end
end
def _arr__currency__price(txt__price)
match = /(\W*)([0-9\.]*)/.match(txt__price)
[match[1], match[2].to_f]
end
def _cents__arr__count__MenuItem(arr__count__MenuItem)
cents__arr__count__MenuItem = 0
arr__MenuItem.each_with_index do |__MenuItem, i|
cents = _cents(__MenuItem.price)
count = arr__count__MenuItem[i] || 0
cents__arr__count__MenuItem += (cents * count)
end
cents__arr__count__MenuItem
end
end
if __FILE__ == $0
puts_valid_menu_line_items(File.read('./input.txt'))
puts_valid_menu_line_items('$20.00')
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.