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}