Find All Possible Recipes from Given Supplies solution and explanation

from collections import defaultdict, deque

def findAllRecipes(recipes, ingredients, supplies):
    graph = defaultdict(list)
    indegree = defaultdict(int)
    for r, ing in zip(recipes, ingredients):
        for i in ing:
            graph[i].append(r)
            indegree[r] += 1

    queue = deque(supplies)
    possible_recipes = set(supplies)

    while queue:
        item = queue.popleft()

        for neighbor in graph[item]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                possible_recipes.add(neighbor)
                queue.append(neighbor)

    return [r for r in recipes if r in possible_recipes]

# Example Usage
# print(findAllRecipes(["bread"], [["yeast","flour"]], ["yeast","flour","corn"]))

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>

std::vector<std::string> findAllRecipes(std::vector<std::string>& recipes, std::vector<std::vector<std::string>>& ingredients, std::vector<std::string>& supplies) {
    std::unordered_map<std::string, std::vector<std::string>> graph;
    std::unordered_map<std::string, int> indegree;
    std::queue<std::string> q;
    std::unordered_set<std::string> supplies_set(supplies.begin(), supplies.end());

    for (int i = 0; i < recipes.size(); ++i) {
        for (const std::string& ing : ingredients[i]) {
            graph[ing].push_back(recipes[i]);
            indegree[recipes[i]]++;
        }
    }

    for (const std::string& s : supplies) {
        q.push(s);
    }

    std::vector<std::string> result;
    while (!q.empty()) {
        std::string item = q.front(); q.pop();
        if (supplies_set.find(item) == supplies_set.end()) {
            result.push_back(item);
        }
        for (const std::string& neighbor : graph[item]) {
            if (--indegree[neighbor] == 0) {
                q.push(neighbor);
                supplies_set.insert(neighbor);
            }
        }
    }

    return result;
}

int main() {
    std::vector<std::string> recipes = {"bread", "sandwich"};
    std::vector<std::vector<std::string>> ingredients = {{"yeast", "flour"}, {"bread", "meat"}};
    std::vector<std::string> supplies = {"yeast", "flour", "meat"};
    std::vector<std::string> creatable_recipes = findAllRecipes(recipes, ingredients, supplies);
    for (const std::string& recipe : creatable_recipes) {
        std::cout << recipe << " ";
    }
    return 0;
}

import java.util.*;

public class RecipeFinder {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Set<String> suppliesSet = new HashSet<>(Arrays.asList(supplies));
        Map<String, Boolean> memo = new HashMap<>();

        List<String> result = new ArrayList<>();
        for (int i = 0; i < recipes.length; i++) {
            if (canCreate(recipes[i], ingredients, recipes, suppliesSet, memo)) {
                result.add(recipes[i]);
            }
        }

        return result;
    }

    private boolean canCreate(String recipe, List<List<String>> ingredients, String[] recipes, Set<String> supplies, Map<String, Boolean> memo) {
        if (supplies.contains(recipe)) return true;
        if (memo.containsKey(recipe)) return memo.get(recipe);

        int recipeIndex = getRecipeIndex(recipe, recipes);
        if (recipeIndex == -1) return false;

        for (String ing : ingredients.get(recipeIndex)) {
            if (!canCreate(ing, ingredients, recipes, supplies, memo)) {
                memo.put(recipe, false);
                return false;
            }
        }

        memo.put(recipe, true);
        supplies.add(recipe); // Now we can create this recipe
        return true;
    }

    private int getRecipeIndex(String recipe, String[] recipes) {
        for (int i = 0; i < recipes.length; i++) {
            if (recipes[i].equals(recipe)) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        RecipeFinder finder = new RecipeFinder();
        String[] recipes = { "bread", "sandwich" };
        List<List<String>> ingredients = Arrays.asList(
            Arrays.asList("yeast", "flour"),
            Arrays.asList("bread", "meat")
        );
        String[] supplies = { "yeast", "flour", "meat" };
        System.out.println(finder.findAllRecipes(recipes, ingredients, supplies));
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<string> FindAllRecipes(string[] recipes, IList<IList<string>> ingredients, string[] supplies) {
        var supplySet = new HashSet<string>(supplies);
        var memo = new Dictionary<string, bool>();

        List<string> result = new List<string>();
        for (int i = 0; i < recipes.Length; i++) {
            if (CanCreate(recipes[i], ingredients, recipes, supplySet, memo)) {
                result.Add(recipes[i]);
            }
        }
        return result;
    }

    private bool CanCreate(string recipe, IList<IList<string>> ingredients, string[] recipes, HashSet<string> supplies, Dictionary<string, bool> memo) {
        if (supplies.Contains(recipe)) return true;
        if (memo.ContainsKey(recipe)) return memo[recipe];

        int recipeIndex = Array.IndexOf(recipes, recipe);
        if (recipeIndex == -1) return false;

        foreach (string ingredient in ingredients[recipeIndex]) {
            if (!CanCreate(ingredient, ingredients, recipes, supplies, memo)) {
                memo[recipe] = false;
                return false;
            }
        }

        memo[recipe] = true;
        supplies.Add(recipe);
        return true;
    }

    public static void Main(string[] args) {
        var solution = new Solution();
        var recipes = new string[] { "bread", "sandwich" };
        var ingredients = new List<IList<string>> {
            new List<string> { "yeast", "flour" },
            new List<string> { "bread", "meat" }
        };
        var supplies = new string[] { "yeast", "flour", "meat" };
        var creatableRecipes = solution.FindAllRecipes(recipes, ingredients, supplies);
        Console.WriteLine(string.Join(", ", creatableRecipes));
    }
}

func findAllRecipes(recipes []string, ingredients [][]string, supplies []string) []string {
	g := map[string][]string{}
	indeg := map[string]int{}
	for i, a := range recipes {
		for _, b := range ingredients[i] {
			g[b] = append(g[b], a)
		}
		indeg[a] = len(ingredients[i])
	}
	q := []string{}
	for _, s := range supplies {
		q = append(q, s)
	}
	ans := []string{}
	for len(q) > 0 {
		for n := len(q); n > 0; n-- {
			i := q[0]
			q = q[1:]
			for _, j := range g[i] {
				indeg[j]--
				if indeg[j] == 0 {
					ans = append(ans, j)
					q = append(q, j)
				}
			}
		}
	}
	return ans
}