Find All Possible Recipes from Given Supplies
Problem
You have recipes and their ingredients list, plus a starting set of supplies. A recipe can be made if all its ingredients are either available supplies or other makeable recipes. Return every recipe you can eventually make.
recipes = ["bread","sandwich"], ingredients = [["flour","yeast"],["bread","meat"]], supplies = ["flour","yeast","meat"]["bread","sandwich"]from collections import deque, defaultdict
def find_all_recipes(recipes, ingredients, supplies):
indeg = {r: len(ing) for r, ing in zip(recipes, ingredients)}
graph = defaultdict(list)
for r, ing in zip(recipes, ingredients):
for x in ing:
graph[x].append(r)
q = deque(supplies)
made = []
rset = set(recipes)
while q:
cur = q.popleft()
for r in graph[cur]:
indeg[r] -= 1
if indeg[r] == 0:
made.append(r)
q.append(r)
return madefunction findAllRecipes(recipes, ingredients, supplies) {
const indeg = new Map();
const graph = new Map();
for (let i = 0; i < recipes.length; i++) {
indeg.set(recipes[i], ingredients[i].length);
for (const x of ingredients[i]) {
if (!graph.has(x)) graph.set(x, []);
graph.get(x).push(recipes[i]);
}
}
const q = [...supplies];
const made = [];
while (q.length) {
const cur = q.shift();
for (const r of (graph.get(cur) || [])) {
indeg.set(r, indeg.get(r) - 1);
if (indeg.get(r) === 0) {
made.push(r);
q.push(r);
}
}
}
return made;
}class Solution {
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Map<String, Integer> indeg = new HashMap<>();
Map<String, List<String>> graph = new HashMap<>();
for (int i = 0; i < recipes.length; i++) {
indeg.put(recipes[i], ingredients.get(i).size());
for (String x : ingredients.get(i))
graph.computeIfAbsent(x, k -> new ArrayList<>()).add(recipes[i]);
}
Deque<String> q = new ArrayDeque<>(Arrays.asList(supplies));
List<String> made = new ArrayList<>();
while (!q.isEmpty()) {
String cur = q.poll();
for (String r : graph.getOrDefault(cur, List.of())) {
indeg.put(r, indeg.get(r) - 1);
if (indeg.get(r) == 0) { made.add(r); q.offer(r); }
}
}
return made;
}
}vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
unordered_map<string, int> indeg;
unordered_map<string, vector<string>> graph;
for (int i = 0; i < (int)recipes.size(); i++) {
indeg[recipes[i]] = ingredients[i].size();
for (auto& x : ingredients[i]) graph[x].push_back(recipes[i]);
}
queue<string> q;
for (auto& s : supplies) q.push(s);
vector<string> made;
while (!q.empty()) {
string cur = q.front(); q.pop();
for (auto& r : graph[cur]) {
if (--indeg[r] == 0) { made.push_back(r); q.push(r); }
}
}
return made;
}Explanation
A recipe becomes makeable once all of its ingredients are available, and ingredients can themselves be other recipes. This is a topological BFS: start from what you already have and unlock recipes as their needs get satisfied.
For each recipe we store indeg = how many ingredients it still needs, and we build a graph mapping each ingredient to the recipes that depend on it. We seed a queue with the supplies you start with.
We then pop an available item cur and look at every recipe that uses it. Each such recipe gets its remaining-need count decremented. When a recipe's count hits zero, all its ingredients are present — so we add it to made and push it onto the queue, since it can now serve as an ingredient for others.
Example: recipes bread (needs flour, yeast) and sandwich (needs bread, meat), supplies [flour, yeast, meat]. Flour and yeast drive bread's count to 0, so bread is made and queued. Bread plus meat then drive sandwich to 0, so both are makeable.
Because each recipe is only emitted when its needs truly reach zero, this naturally handles chains and avoids any recipe that depends on something unavailable.