diff options
Diffstat (limited to 'possible_recipes_supplies.py')
-rw-r--r-- | possible_recipes_supplies.py | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/possible_recipes_supplies.py b/possible_recipes_supplies.py new file mode 100644 index 0000000..63fe5ff --- /dev/null +++ b/possible_recipes_supplies.py @@ -0,0 +1,66 @@ +# 2115. Find All Possible Recipes from Given Supplies +from collections import defaultdict, Counter + +""" +you have information about 'n' different recipes. you are given a string +array 'recipes' and a 2d string array 'ingredients'. the i'th recipe has the +name 'recipes[i]', and you can create it is you have all the needed +ingredients from 'ingredients[i]'. ingredients to a recipe may need to be +created from other recipes, ie. 'ingredients[i]' may contain a string that is +in 'recipes'. you are also given a string array 'supplies' containing all the +ingredients that you initially have, and you have an infinite supply of all +of them. return a list of all the recipes that you can create. you may return +the answer in any order. +""" + + +class Solution(object): + def findAllRecipes(self, recipes, ingredients, supplies): + """ + :type recipes: List[str] + :type ingredients: List[List[str]] + :type supplies: List[str] + :rtype: List[str] + """ + to_recipe, in_deg = defaultdict(set), Counter() + for i, j in zip(recipes, ingredients): + for k in j: + to_recipe[k].add(i) + in_deg[i] = len(j) + ans = [] + for i in supplies: + for j in to_recipe.pop(i, set()): + in_deg[j] -= 1 + if in_deg[j] == 0: + supplies.append(j) + ans.append(j) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.findAllRecipes( + recipes=["bread"], + ingredients=[["yeast", "flour"]], + supplies=["yeast", "flour", "corn"], + ) + ) + print( + obj.findAllRecipes( + recipes=["bread", "sandwich"], + ingredients=[["yeast", "flour"], ["bread", "meat"]], + supplies=["yeast", "flour", "meat"], + ) + ) + print( + obj.findAllRecipes( + recipes=["bread", "sandwich", "burger"], + ingredients=[ + ["yeast", "flour"], + ["bread", "meat"], + ["sandwich", "meat", "bread"], + ], + supplies=["yeast", "flour", "meat"], + ) + ) |