recursion_challenge.md

Copy this Gist into a new secret gist of your own, and deliver it NO LATER THAN THE TIME specified during the challenge intro.

Rewrite the question in your own words:

Find the combination of items that add up to the price on a receipt

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

Which data structure(s) do you think you'll use? What pros/cons do you see about using it/them?

Array

Write out your initial pseudocode: (mid-level design, this should not be real code!)

=begin first convert prices to ints

1. Plan out your base case(s) of how to exit the recursion exit when money_left = 0
2. Each iteration of the recursion should look through the whole menu; this can help to "buy" things more than once menu.each do |item| skip item if price > money_left remove that item from menu money_left = money_left%item_price if money_left%item_price == 0 end
3. If you find a solution while looping through the menu, you can start returning from your recursion return find_menu(menu, money_left)
4. You'll also need a base case AFTER looping through the menu to indicate that nothing on the menu worked return no solution =end

What do you think the Big O complexity of your algorithm is? (just for practice)

def find_menu(menu, money_left)
items = {}
  # money_left = (money_left*100).to_i
  # menu.reduce({}) do |acc, (item,price)|
  #   acc[item] = (price*100).to_i
  #   acc
  # end

  if money_left == 0
    return items
  end
#   2) Each iteration of the recursion should look through the whole menu; this can help to "buy" things more than once
#     menu.each do |item|
#       skip item if price > money_left
#       money_left = money_left%item_price if money_left%item_price == 0
#     end

  menu.reduce({}) do |acc, (item, price)|
    if price <= money_left
      find_menu(menu, money_left - price)
      return items if money_left == 0
    end
    acc
  end

  items = menu.reduce({}) do |acc, (item,price)|
    if money_left - price > 0
      binding.pry
      acc[item] ||= 0
      acc[item] += 1
      money_left -= price
    end
    acc
  end

#   3) If you find a solution while looping through the menu, you can start returning from your recursion
#     return find_menu(menu, money_left)
#   4) You'll also need a base case AFTER looping through the menu to indicate that nothing on the menu worked
#     return n
# =end
end