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

[Ian Kelly]

On Mon, Sep 25, 2017 at 6:49 AM, Paul Moore <p.f.moore at gmail.com> wrote:
> 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?

You have a DAG, so you can sort it topologically. Then you can process
it in that order so that everything that uses X will be processed
before X so that when you get to X you'll know exactly how much of it
you need and you don't have to worry about "feedback". For actual
production, run through it in the opposite order so that you'll
produce all your precursors before the things that require them.