commit 5c2cacb54c304aa785e2455e4aecbc6342c2c9dd
parent dc6d20748dbd175bcbf2155fd870ca53fb13098d
Author: Andrew Laack <andrew@laack.co>
Date: Tue, 25 Aug 2026 22:18:18 -0500
Continued working on kahn's algorithm / top sort problems
Diffstat:
3 files changed, 98 insertions(+), 0 deletions(-)
diff --git a/find-all-possible-recipes-from-given-supplies/find-all-possible-recipes-from-given-supplies.py b/find-all-possible-recipes-from-given-supplies/find-all-possible-recipes-from-given-supplies.py
@@ -0,0 +1,76 @@
+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;
+ }
+};
diff --git a/smallest-missing-multiple-of-k/smallest-missing-multiple-of-k-v2.py b/smallest-missing-multiple-of-k/smallest-missing-multiple-of-k-v2.py
@@ -0,0 +1,10 @@
+def recurse(itr, k, lookup):
+ if not (itr * k) in lookup:
+ return itr * k
+ return recurse(itr + 1, k, lookup)
+
+class Solution:
+
+ def missingMultiple(self, nums: List[int], k: int) -> int:
+ lookup = {num for num in nums}
+ return recurse(1, k, lookup)
diff --git a/smallest-missing-multiple-of-k/smallest-missing-multiple-of-k.py b/smallest-missing-multiple-of-k/smallest-missing-multiple-of-k.py
@@ -0,0 +1,12 @@
+class Solution:
+ def missingMultiple(self, nums: List[int], k: int) -> int:
+ lookup = set()
+
+ for num in nums:
+ lookup.add(num)
+
+ itr = 1
+ while True:
+ if not (itr * k) in lookup:
+ return itr * k
+ itr += 1
