Python Recursive Data Reading

Question

The following will make more sense if you have ever played minecraft. Since many of you have not, I will try to explain it as best as I can

I am trying to write a recursive function that can find the steps to craft any minecraft item from a flatfile of minecraft recipes. This one has me really stumped.

The flatfile is kinda long so I included it in this gist.

def getRecipeChain(item, quantity=1):
    #magic recursive stuffs go here

So basically I need to look up the first recipe then look up the recipes for all the components of that first recipe and so on till you get to items with no recipes. Each time I need to append the recipe to a list so I get a sort of instruction set of what order to craft items in.

So here is the function I have now(the one the does not work)

def getRecipeChain(name, quantity=1):
    chain = []

    def getRecipe(name1, quantity1=1):
        if name1 in recipes:
            for item in recipes[name1]["ingredients"]["input"]:
                if item in recipes:
                    getRecipe(item, quantity1)
                else:
                    chain.append(item)

    getRecipe(name, quantity)
    return chain

Here is the ideal output I am going for. It is a dictionary with the item name and quantity's stored in it.

>>> getRecipeChain("solar_panel", 1):
{"insulated_copper_cable":13, "electronic_circuit":2, "re_battery":1, "furnace":1, "machine":1, "generator":1, "solar_panel":1}

So the question is, how do I do it?

I know asking for people to do work for you is frowned up here, so if you feel this is a little too close to you just doing the coding for me, just say so.

Answer 1

This can be elegantly solved using collections.Counter, which supports addition:

from collections import Counter

def getRecipe(name, quantity=1):
  if not name in recipes: return Counter({name: quantity})

  subitems = recipes[name]["ingredients"]["input"]
  return sum((getRecipe(item, quantity) for item in subitems), 
             Counter())

print repr(dict(getRecipe("solar_panel")))
# => {'copper': 39, 'refined_iron': 10, 'glass': 3, 
#     'rubber': 78, 'cobblestone': 8, 'tin': 4, 
#     'coal_dust': 3, 'nothing': 10, 'redstone': 6}

Answer 2

I think the problem is 2 fold. First of all, you need to be appending the items to the chain in the recursive call to getRecipe(). Secondly, I think the two functions is needlessly complicating things. I think just the inner one should do. Something like this is what you are looking for. I haven't tested it, but it should be close enough to get you started on the right track.

def getRecipe(name, quantity=1):
    chain=[];
    if name in recipes:
        for item in recipes[name]["ingredients"]["input"]:
            if item in recipes:
                chain.append(getRecipe(item, quantity))
            else:
                chain.append(item)
    return chain

EDIT: The comments are filling my lack of python knowledge, so here's a better solution.

from collections import Counter
def getRecipe(name, quantity=1, count=Counter()):
    if name in recipes:
        for item in recipes[name]["ingredients"]["input"]:
            if item in recipes:
                getRecipe(item, quantity,counter)
            else:
                counter[item]+=quantity
    return counter