algorithms

find-all-possible-recipes-from-given-supplies.py (2595B)

---

 struct Node{
   size_t inDegree;
   string name;
   bool isRecipe;
   vector<string> requiredBy;
 };
 
 
 class Solution {
 public:
     vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
 
         // n different recipes (recipes.size())
         // ingredients[i] are ingredients to make recipes[i]
         // works if we have all of the ingredients in supplies
         // a recipe can be an ingredient for other recipes too
 
         // approach:
             // this seems like a topological sort problem
             // to add a recipe to the list, all of the priors (ingredients)
             // must be in the sorted list.
 
             // concretely:
                 // use khan's algorithm
                     // add all vertices with an in-degree of zero to sorted list
                     // decrement in-degrees for all nodes they point to
                     // repeat process while the # of in-degree nodes is non-zero
                     // as we work we might also want a parallel list that tracks
                         // the insertion of recipes into our vector to return
         
         vector<string> canMake = {};
         unordered_map<string, Node> graph = {};
 
         // len(ingredients[i]) >= 1 so we just push supplies to stack for evaluation.
         vector<string> stack = {};
         for(auto supply: supplies) {
             graph[supply] = Node(0, supply, false, {});
             stack.push_back(supply);
         }
 
         // since there can be recipe dependence, we can't do the edge tracking here
         // basically we might not be able to reference a pre-req here.
 
         for(auto recipe: recipes) {
             graph[recipe] = Node(0, recipe, true, {});
         }
 
         for(size_t i = 0; i < recipes.size(); ++i) {
             Node& recipe = graph[recipes[i]];
             recipe.inDegree = ingredients[i].size();
             for(auto ingredient: ingredients[i]) {
                 graph[ingredient].requiredBy.push_back(recipes[i]);
             }
         }
 
         while(stack.size() != 0) {
 
             string current = stack.back();
             stack.pop_back();
             Node& cn = graph[current];
             auto& reqs = cn.requiredBy;
 
             for(auto rq : reqs) {
                 graph[rq].inDegree -= 1;
                 if(graph[rq].inDegree == 0) {
                     stack.push_back(rq);
                     if(graph[rq].isRecipe) {
                         canMake.push_back(rq);
                     }
                 }
             }
         }
 
         return canMake;
     }
 };