Find All Possible Recipes from Given Supplies
Problem statement
You are given recipes, a list of names, and ingredients, where ingredients[i] lists everything needed to make recipes[i]. You also have supplies, items you hold an unlimited amount of.
An ingredient can be a supply, another recipe, or something you have no way to get. A recipe can be made once every one of its ingredients is available, and once made it counts as available for other recipes. Return every recipe that can be made, in any order.
It is the same shape as a build system: targets depend on other targets and on base packages, and a target is buildable only if its whole dependency tree bottoms out in things you already have. Watch out for recipes that depend on each other in a cycle: neither can ever be made.
Examples
Example 1
Input: recipes = ["pasta","sauce","dinner"], ingredients = [["flour","egg"],["tomato","basil"],["pasta","sauce"]], supplies = ["flour","egg","tomato"]
Output: ["pasta"]
Explanation: There is no basil, so sauce can't be made, and dinner needs sauce.
Example 2
Input: recipes = ["toast","sandwich"], ingredients = [["bread"],["toast","cheese"]], supplies = ["bread","cheese"]
Output: ["sandwich", "toast"]
Explanation: Toast only needs bread. Once toast exists, the sandwich has everything. (Shown sorted; any order is accepted.)
Hints
Approach
Topological sort (Kahn's algorithm). For every recipe, set missing[recipe] to its number of ingredients, and for every ingredient remember which recipes use it (used_by).
Put all supplies in a queue. Pop an item and, for each recipe in used_by[item], decrement its missing count. When a count reaches zero, that recipe is makeable: record it and push it onto the queue so it can unlock further recipes.
Each ingredient edge is decremented at most once, so the whole thing is linear. Recipes on a cycle, or depending on an unobtainable item, never reach zero and are left out automatically.
O(R + I + S)Space O(R + I)from collections import defaultdict, deque def find_all_recipes(recipes, ingredients, supplies): missing = {} used_by = defaultdict(list) for name, needs in zip(recipes, ingredients): missing[name] = len(needs) for item in needs: used_by[item].append(name) queue = deque(supplies) made = [] while queue: item = queue.popleft() for name in used_by[item]: missing[name] -= 1 if missing[name] == 0: made.append(name) queue.append(name) return made print(sorted(find_all_recipes(["pasta", "sauce", "dinner"], [["flour", "egg"], ["tomato", "basil"], ["pasta", "sauce"]], ["flour", "egg", "tomato"])))print(sorted(find_all_recipes(["toast", "sandwich"], [["bread"], ["toast", "cheese"]], ["bread", "cheese"])))Follow-up questions
- Return the recipes in an order you could actually cook them (the order they reach zero already is one).
- For each recipe that can't be made, report which base ingredient is missing.
Frequently asked questions
Dependency resolution is everyday infra work: package managers, build systems, Terraform's resource graph and service start-up ordering all decide what can be built or started from what is already present. This problem is that task with the details stripped away, plus the classic traps of cycles and missing inputs.
Course Schedule asks whether all nodes can be ordered. Here some nodes (supplies) start as available, some ingredients may never exist, and the answer is the subset that can be finished. The algorithm is the same Kahn's sort; only the starting queue and the question change.
Neither recipe's missing count can reach zero, because each waits on the other, so neither is ever added. Kahn's algorithm handles cycles for free: whatever is left with a non-zero count at the end is blocked.