On 25 September 2017 at 15:20, Paul Moore <p.f.mo...@gmail.com> wrote:
> On 25 September 2017 at 14:23, Ian Kelly <ian.g.ke...@gmail.com> wrote:
>> 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.
>
> Hmm, yes that makes sense. I was thinking of a topological sort in the
> other direction (ingredient before product) and that way round doesn't
> work. For some reason, when thinking about topological sorts, I tend
> to get fixated on one direction and forget they are actually
> reversible...
Thank you. With that hint, the problem turned out to be remarkably
simple. If anyone is interested, here's the basic approach:
import networkx as nx
G = nx.DiGraph()
G.add_edge("Tank", "Bars", qty=4)
G.add_edge("Tank", "Iron", qty=4)
G.add_edge("Tank", "Glass", qty=1)
G.add_edge("Bars", "Iron", qty=6, batch=16)
G.add_edge("Chassis", "Bars", qty=4)
G.add_edge("Chassis", "Iron", qty=4)
G.add_edge("Chassis", "Capacitor", qty=1)
G.add_edge("Alloy Smelter", "Chassis", qty=1)
G.add_edge("Alloy Smelter", "Cauldron", qty=1)
G.add_edge("Alloy Smelter", "Furnace", qty=3)
G.add_edge("Alloy Smelter", "Iron", qty=4)
G.add_edge("Cauldron", "Iron", qty=7)
from collections import defaultdict
need = defaultdict(int)
need["Alloy Smelter"] = 1
need["Tank"] = 2
import math
for item in nx.topological_sort(G):
for ingredient in G[item]:
edge = G[item][ingredient]
if "batch" in edge:
# Round up
batches = math.ceil(need[item] / edge["batch"])
else:
batches = need[item]
need[ingredient] += batches * G[item][ingredient]["qty"]
print(need)
Paul
--
https://mail.python.org/mailman/listinfo/python-list
