Looking for an algorithm - calculate ingredients for a set of recipes
Paul Moore
p.f.moore at gmail.com
Mon Sep 25 08:49:17 EDT 2017
I'm trying to work out a good algorithm to code a calculation I need
to do. I can see brute force ways of handling the problem, but I keep
getting bogged down in details, and the question seems like it's
something that should have been solved plenty of times in the past, I
just don't know where to look.
The basic problem is that I'm trying to model a set of recipes, and
calculate the amounts of base ingredients needed to produce what I
require. This is actually for calculating production requirements in
Minecraft, so I have recipes of the form:
1 tank = 4 bars, 4 iron, 1 glass
16 bars = 6 iron
1 chassis = 4 bars, 4 iron, 1 capacitor
1 alloy smelter = 1 chassis, 1 cauldron, 3 furnace, 4 iron
1 cauldron = 7 iron
If I want to make 1 alloy smelter and 2 tanks, I need:
(alloy smelter)
1 chassis
4 bars
4 iron
1 capacitor
1 cauldron
7 iron
3 furnace
4 iron
(tanks)
8 bars
8 iron
2 glass
Total iron (for example) = 23, plus 6 (enough for 12 bars - note that
we have to make bars in batches of 16) = 29.
I can model the recipes as basically a graph (a DAG). Calculating the
amounts isn't too hard if we ignore the batch crafting aspect, but I
also need to cater for the possibility of "I need 3 of X and 4 of Y,
but I need 2 extra X to craft each Y, so I need a total of 11 X). So
there's an element of feedback involved as well.
I can probably come up with a viable approach given some time, but
this feels like the sort of calculation that comes up a lot (basically
any "recipe" based exercise - cooking, manufacturing, etc) and I feel
as if I'm at risk of reinventing the wheel, which I could avoid if I
only knew what the techniques I need are called.
Can anyone suggest any pointers?
Thanks,
Paul
More information about the Python-list
mailing list