[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Looking for an algorithm - calculate ingredients for a set of recipes

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
    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?