ruby - 使用 ruby​​ 中的成分和公式转换优化药水酿造程序？

Question

这是我要解决的问题:

"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.

这是我的解决方案:

ingredients = Hash.new
potion = 0

puts "Welcome to potion brewer! To make a health potion you must combine 4 TOF + 7 TOW + 2 AF. Let's get started.\n\n" 

puts "How many EON do you have?"

ingredients["EON"] = gets.to_i

puts "How many TOF do you have?" 

ingredients["TOF"] = gets.to_i

puts "How many WOB do you have?" 

ingredients["WOB"] = gets.to_i

puts "How many AF do you have?"

ingredients["AF"] = gets.to_i

puts "How many TOW do you have?" 

ingredients["TOW"] = gets.to_i


while (ingredients["EON"] >= 4 and ingredients["WOB"] >= 2)
    ingredients["AF"] += 3
    ingredients["TOW"] += 4
    ingredients["EON"] -= 4
    ingredients["WOB"] -= 2
    # ==/== DEBUG ==/== 
#    puts "4 EON and 2 WOB convereted into +3 AF and +4 TOW."
#    puts ingredients["EON"]
#    puts ingredients["WOB"]
end
while ((ingredients["TOF"]/4) < (ingredients["AF"]/2))
   ## puts "debug"
    if (ingredients["WOB"] >= 1 and ingredients["AF"] >= 2)
        ingredients["TOF"] += 1
        ingredients["WOB"] -= 1
        ingredients["AF"] -= 2
   #     puts "1 WOB and 2 AF converted to +1 TOF."
    else
    break
    end
end
while (ingredients["TOF"] >= 4 and ingredients["TOW"] >= 7 and ingredients["AF"] >= 2)
    potion += 1
    ingredients["TOF"] -= 4
    ingredients["TOW"] -= 7
    ingredients["AF"] -= 2
    # ==/== DEBUG ==/==
    #puts "Potion created.."
end


puts "\n\nMade #{potion} potion(s).\n\n" 

for name in ingredients.keys
puts "You have " + ingredients[name].to_s + " " + name + " left.\n"
end    

无论如何，这是我能想到的“最整洁”的解决方法。我认为我正确地对转换进行了排序，这样在制作药水时就不会出现任何低效情况……并且我通过书中示例的输入得到了想要的结果。

任何人都可以确认它实际上看起来没问题/我没有错过一些可以进一步最大化我的药水的重大优化吗？我找不到与第三次转换 (1wob+2af=1tof) 有多大关系。

谢谢!

Answer 1

有趣的问题!

因此让我们重新表述一下:目标是计算“健康”药水，如果此药水的任何成分缺失，则找到可用于制造缺失成分的其他药水。

这听起来像是一种递归算法。因此，首先，让我们对“制作药水”问题进行建模。

假设 e 有一个药水公式，一个包含所有需要的成分(负值)的散列和生成的成分，正值。

例如:

4 eon + 2 wob = 3 af + 4 tow

可以写成:

formulae={:eon=>-4,:wob=>-2,:af=>3,:tow=>4}

因此，计算公式将非常简单:

def compute_formulae ingredients,formulae
   result=ingredients.clone
   formulae.each do |needed,amount|
     if ingredients[needed]<-amount
        puts "Missing #{needed}" # The is an ingredient missing, we should probably exit now
        return nil
     else
        result[needed]+=amount
     end
   end
   result
end

现在的问题是缺少配料怎么办？我们必须根据我们现有的成分，在公式列表中找到一个我们可以用来“创建它”的公式

formulas=[
 {:tof=>-4,:tow=>-7,:af=>-2,:health=>1},
 {:eon=>-4,:wob=>-2,:af=>3,:tow=>4},
 {:tow=>-3,:tof=>-1,:eon=>2},
 {:wob=>-1,:af =>-2,:tof=>1}
  ]
formulas.each{|f| f.default=0} # Just ensure that there is de fault value for all ingredients


def find_missing_ingredient ingredients,formulas,missing
   formulas.each do | formulae |
      if formulae[missing]>0
        compute_formulae_ingredient ingredients,formulae
      end
   end
end

# so basically, the problem is
ingredients={:eon=>34,:tof=>59,:wob=>20,:af=>5,:tow=>20}
ingredients.default=0

while find_missing_ingredient ingredients,formulas,:health
end

现在，有一些小细节，比如主循环(我们需要继续，只要我们能得到新的“健康”，错误(在这个递归循环中什么时候停止)，输入部分，但我留下了这个给读者!