aboutsummaryrefslogtreecommitdiff
path: root/possible_recipes_supplies.py
diff options
context:
space:
mode:
Diffstat (limited to 'possible_recipes_supplies.py')
-rw-r--r--possible_recipes_supplies.py66
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"],
+ )
+ )