Найти количество сырых ингредиентов с помощью рекурсии в Python - PullRequest
Новая
       7

Найти количество сырых ингредиентов с помощью рекурсии в Python

0 голосов
/ 14 февраля 2020

Нам дан словарь рецептов, а также список сырьевых ингредиентов; 

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'}

Вопрос в том; Программно найти количество сырья (каждого типа), используемого для каждого рецепта. Обратите внимание, что сырые ингредиенты включают только rock, tape и stick.

Вот моя попытка решить этот вопрос в 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)

Здесь name может быть либо {axe, double_axe,quadruple_axe}, s совпадает с recipes, а l совпадает с raw_ingredients.

Я полностью понимаю, что мой код не завершен. Это только моя первая попытка ответить на этот вопрос, и я пытаюсь получить здесь скелет. Вот два ключевых вопроса, с которыми мне нужна помощь:

  1. Во-первых, как отслеживать количество необходимых ингредиентов, например, quadruple_axe нужно всего 4 палочки.
  2. Во-вторых, когда мы перестанем возвращаться, то есть каков здесь базовый случай?

Заранее спасибо за помощь

Ответы [ 2 ]

1 голос
/ 14 февраля 2020

Во-первых, как отслеживать количество необходимых ингредиентов, например, quadruple_axe нужно всего 4 палочки.

Ваш инстинкт использования словаря для сбора количества ингредиентов хорош : 

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

Но, пожалуйста, поместите комментарий перед строкой, о которой он комментирует, а не после.

Во-вторых, когда мы прекращаем повторение, то есть каков базовый случай здесь?

Вы работаете с сырьем напрямую, вы используете рецепты по субрецептам. Таким образом, отречение естественным образом прекращается, когда вы исчерпали все вспомогательные рецепты - вам не нужно явно проверять его.

Я рекомендую вам перестать думать в терминах dict1 и dict2 как а также i, j и k и программа на языке проблемы. Я также предлагаю вам использовать defaultdict для сбора окончательного списка ингредиентов, преобразовав его в общий c dict в конце, если вы чувствуете необходимость. Но это необязательно и просто упрощает код: 

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'))

ВЫХОД 

> python3 test.py
{'stick': 4, 'rock': 6, 'tape': 7}
>
0 голосов
/ 14 февраля 2020

Ваш базовый случай, когда название ингредиента не отображается в виде ярлыка рецепта. Вы повторяетесь по трем axe типам; Вы останавливаетесь на stick, rock или tape.

. Вы можете отслеживать, передавая счет количества базовых ингредиентов. Например, проверка для «двойного топора» вернет вычислительное свертывание для 2 * {'stick': 1, 'rock': 1, 'tape': 1} + {'tape': 1}. Вы должны быть в состоянии получить этот код для себя или посмотреть здесь что-то вроде «Python add values ​​two dicts».

...