solution to an excercise from Computer Science Programming Basics with Ruby by Frieder, Frider and Grossman

potions.rb

# https://stackoverflow.com/questions/26440997/optimizing-a-potion-brewing-program-using-ingredients-and-formulaic-conversions
# 
# "The three witches in Hamlet can brew any potion provided they have the right ingredients. 
# Suppose that five ingredients are necessary in making a health potion => eye of newt (eon), 
# toe of frog (tof), wool of bat (wob), adder's fork (af), and tooth of wolf (tow). Four 
# reactions can occur between these ingredients:
# 
# 4 eon + 2 wob = 3 af + 4 tow
# 3 tow + 1 tof = 2 eon
# 1 wob + 2 af = 1 tof
# 4 tof + 7 tow + 2 af = 1 health potion
# 
# Assuming you can control the order of reactions, write a program that can calculate the 
# maximum number of health potions one can brew with a given amount of ingredients. Here 
# is example output => If I have 34 eon, 59 tof, 20 wob, 5 af, and 20 tow, I can make seven 
# health potions."
# 
# Excerpt From => Ophir Frieder, Gideon Frieder, and David Grossman. 
# "Computer Science Programming Basics with Ruby." iBooks.


def max_potions(ingredients, memo={})
  reactions = []

  # 4 eon + 2 wob = 3 af + 4 tow
  if ingredients[:eon] >= 4 && ingredients[:wob] >= 2
    reactions.push({
      :eon => ingredients[:eon] - 4,
      :tof => ingredients[:tof],
      :wob => ingredients[:wob] - 2,
      :af => ingredients[:af] + 3,
      :tow => ingredients[:tow] + 4,
      :hp => ingredients[:hp]
    })
  end

  # 3 tow + 1 tof = 2 eon
  if ingredients[:tow] >= 3 && ingredients[:tof] >= 1
    reactions.push({
      :eon => ingredients[:eon] + 2,
      :tof => ingredients[:tof] - 1,
      :wob => ingredients[:wob],
      :af => ingredients[:af],
      :tow => ingredients[:tow] - 3,
      :hp => ingredients[:hp]
    })
  end  

  # 1 wob + 2 af = 1 tof
  if ingredients[:wob] >= 1 && ingredients[:af] >= 2
    reactions.push({
      :eon => ingredients[:eon],
      :tof => ingredients[:tof] + 1,
      :wob => ingredients[:wob] - 1,
      :af => ingredients[:af] - 2,
      :tow => ingredients[:tow],
      :hp => ingredients[:hp]
    })
  end

  # 4 tof + 7 tow + 2 af = 1 health potion
  if ingredients[:tof] >= 4 && ingredients[:tow] >= 7 && ingredients[:af] >= 2
    reactions.push({
      :eon => ingredients[:eon],
      :tof => ingredients[:tof] - 4,
      :wob => ingredients[:wob],
      :af => ingredients[:af] - 2,
      :tow => ingredients[:tow] - 7,
      :hp => ingredients[:hp] + 1
    })
  end 

  # if no reactions are possible, return 
  # the number of health potions made
  return ingredients[:hp] if reactions.empty?

  # try every possible reaction for this set 
  # of ingredients and determine the maxiumum
  maximum = 0

  reactions.each do |reaction|
    key = reaction.hash

    # retrieve this node's value if already visited
    if memo.include?(key)
      result = memo[key]
    else # calculate and save the node's value
      result = max_potions(reaction, memo)
      memo[key] = result
    end 

    # update the maximum as necessary
    maximum = result if result > maximum 
  end 

  return maximum
end


ingredients = {
  :eon => 34,
  :tof => 59,
  :wob => 20,
  :af => 5,
  :tow => 20,
  :hp => 0
}
puts max_potions(ingredients) # 7