CODEWITHSUNDEEP
pythonrecursion
jay
jay

Reputation: 1463

Find the count of raw ingredients using Recursion in Python

We are given a dictionary of recipes, as well as list of raw ingredients;

recipes = {
'axe': {'stick': 1, 'rock': 1, 'tape': 1},
'double_axe': {'axe': 2, 'tape': 1},
'quadruple_axe': {'double_axe': 2, 'tape': 1, 'rock': 2}
}

raw_ingredients = {'rock', 'stick', 'tape'}

The question is; programmatically find number of raw ingredients(of each type) used for each recipe. Please note that raw ingredients only include rock,tape, and stick.

Here is my attempt to solve this question in Python;

def get_ingredients(name, s, l):
s[name]=dict1
#get dictionary for each recipe

k=dict1.keys()
#retrieve the keys
dict2={}
#define empty dictionary to store count of raw ingredients
for i in k:
 #loop over the keys   
    if i in l:
 #if key is a raw ingredient, we will increase the count for that corresponding raw ingredient
        dict2[i]=dict1[i]
    else:
#otherwise call the function recursively
        for j in range(0,dict1[i]):
        get_ingredients(i, s, l)

Here name can be either {axe, double_axe,quadruple_axe}, s is same as recipes, and l is same as raw_ingredients.

I fully understand that, my code is not complete. It is only my first attempt at the question, and I am trying to get skeleton here. Here are the two key questions I need help with;

  1. First, how to keep track of count of the ingredients needed, for instance quadruple_axe needs 4 sticks in total.
  2. Second, when do we stop recursing, i.e. what is the base case here?

Thanks in advance for help

Upvotes: 0

Views: 787

Answers (2)

cdlane
cdlane

Reputation: 41872

First, how to keep track of count of the ingredients needed, for instance quadruple_axe needs 4 sticks in total.

Your instinct to use a dictionary to gather the ingredient counts is good:

dict2={}
#define empty dictionary to store count of raw ingredients

But please, put the comment before the line about which it comments, not after.

Second, when do we stop recursing, i.e. what is the base case here?

You handle raw ingredients directly, you recurse on sub recipes. So the recusion naturally stops when you've exhausted all the sub recipes -- you don't have to test for it explicitly.

I recommend that you stop thinking in terms of dict1 and dict2 as well as i, j and k and program in the language of the problem. I also suggest that you use a defaultdict to collect your final list of raw ingredients, converting it to a generic dict at the end if you feel the need. But this is optional and just simplifies the code:

from collections import defaultdict

recipes = {
    'axe': {'stick': 1, 'rock': 1, 'tape': 1},
    'double_axe': {'axe': 2, 'tape': 1},
    'quadruple_axe': {'double_axe': 2, 'tape': 1, 'rock': 2}
}

raw_ingredients = {'rock', 'stick', 'tape'}

def count_raw_ingredients(recipe):
    ingredients = defaultdict(int)

    for ingredient, amount in recipes[recipe].items():
        if ingredient in raw_ingredients:
            ingredients[ingredient] += amount
        else:
            for subingredient, subamount in count_raw_ingredients(ingredient).items():
                ingredients[subingredient] += amount * subamount

    return dict(ingredients)

print(count_raw_ingredients('quadruple_axe'))

OUTPUT

> python3 test.py
{'stick': 4, 'rock': 6, 'tape': 7}
>

Upvotes: 1

Prune
Prune

Reputation: 77857

Your base case is when the ingredient name does not appear as a recipe label. You recur on the three axe types; you stop on stick, rock, or tape.

You can keep track by passing back a dict of base ingredient counts. For instance, a check for "double-axe" will return the computational roll-up for 2 * {'stick': 1, 'rock': 1, 'tape': 1} + {'tape': 1}. You should be able to derive that code for yourself, or look it up here with something like "Python add values two dicts".

Upvotes: 0

Related Questions