Find All Possible Recipes from Given Supplies - Leetcode 2115 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem find all possible recipes from given supplies. The problem description is more simple than it actually seems. So I'm going to be mostly focusing on like the input and output for this example here. I'm going to go through what this problem is asking for and then I want to cover why the sort of naive solution won't work and why we will have to do a different solution. And that solution is going to be turning this problem into a graph problem. In that graph problem, there's multiple ways to solve this problem. I'll just focus on one of those solutions, but I'll try to discuss some of the alternatives as well. The idea here is that we are given a bunch of recipes. So these are the recipes here. What we want to do is determine which one of these we can actually cook. Can we cook bread? Yes or no? Can we cook a sandwich? Can we cook a burger? And so for each of these, we just want to know which ones we can cook. And that's what we want to return. So you can see that in this example, the output is all three of them. We can cook all of them. Now, how do you know if you can cook a certain recipe or not? Well, I'll try to color code it to make this a little bit easier to read. For bread, we have this array, I guess. First of all, we have the recipes array. In this case, it's of size three. We call that n. While the ingredients array which is going to be separate is going to be of the same length. So for each item in the recipes we have bread. Inside of the ingredients array we have an item which is a sublist a subarray of these ingredients that are required to cook bread. For sandwich we have these ingredients that are required. And lastly for a burger we have these three ingredients required. Separately we are actually also given a third array which is supplies. The length of this array could be anything. It's not related to the first two arrays. So the way to think about this is sort of like these supplies are like our smallest units. Like these are the ones that are indivisible. Like these are kind of our base cases. So we have yeast, we have flour and we have meat. But for these recipes here, these are not units. These are compound. It takes other things to create each of these. These can be divided. So for bread, you can see that bread is just yeast and flour. It takes yeast and flour to make bread. Next, we have a sandwich. It takes bread and meat to make a sandwich. We have meat over here, but we do not have bread over here. Notice that. So, a sandwich, not only does it require some supplies, our smallest units, but it also requires a compound item, a recipe in this case. So, for us to know if we can cook sandwich, it's not enough for us just to look at the supplies. It was for bread. For bread, we can just go through each of these ingredients and then just do a lookup with supplies. When I say the word a lookup, you probably can guess what data structure I would want to use for that. I'd probably want to use just a hashbased data structure. Maybe a hash set or a hashmap. I think in this problem, we are actually given an infinite quantity of each of these. So, we have an unlimited amount and therefore a hash set, I think, would be fine. But it's actually not going to work. that naive solution would not work for this example because I mean maybe in this example with going through these items in a certain order it might work if I'm going through these recipes and I want to know okay can I make bread can I make a sandwich can I make a burger I'll start with bread I'll see I need yeast and flour I have both of those down here so I can make bread that's great so in some ways I can take bread and add it to my list of supplies and say okay now I have these available ailable to me, but I also have bread and I have an infinite amount of it because I had an infinite amount of these other ingredients as well. So now I have bread available to me. And then next I will look at sandwich and say what do I need for a sandwich? I need bread and meat. I have both of those. I just made some bread. But what if the order of these was swapped? What if we saw sandwich first and then we saw bread? Well, then after making bread, then we have to kind of backtrack and go to all the other new recipes that we can create. And it might not just be one like link, it might be something like this. Maybe if I want to make, let's say, like a burger, to make a burger, I need a sandwich. And to make a sandwich, I need bread. And maybe to make bread, I need like some other recipe. Well, let's say I went through these items like this. I want to make a burger. Well, I can't make a burger. I want to make a sandwich. I can't do that. I want to make bread. Well, maybe I can't do that either. But then I get to another recipe, I can make that. Once I find out I can make this recipe, now I'm able to make this one as well. I have to kind of go back up that link. And now that I can do this one, I have to do the previous one as well. And then I can do the previous one as well. So this seems like recursion and it exactly is because this is actually a graph problem. The items like the recipes and the supplies, these are sort of like our nodes and these ingredients are sort of like the edges. And once you can kind of think of it as a graph problem, it becomes pretty trivial. You can solve it either with DFS or BFS. I will be covering the DFS solution. So if this was a graph, what would it look like? Let me try to draw it out. I'll start with the supplies. So we have our supplies down here and then we have bread which will be its own node and to make bread we need yeast as well as flour. So I'm going to make a directed edge from here to there. I guess I could have done it in the other way as well but I think this is a bit more descriptive because if we want the ingredients of a specific recipe, we can just follow each edge that goes out of it. We also have a sandwich which takes um bread as well as meat. And for whatever reason, a burger is separate from a sandwich. I guess they're making like a Big Mac or something where now we will need a existing sandwich and some extra meat I believe and I think actually extra bread as well. So yeah, we can see here that a burger requires sandwich, meat, and bread. So this is kind of what we would expect the graph to look like. It's not really a coincidence that it looks like a tree because it probably should be an asyical graph and it probably should be connected. I guess it doesn't necessarily have to be connected. Maybe these two don't exist. We could have had bread dependent on this and maybe like some other item dependent on that one. That would be unconnected. But mainly we we definitely don't want there to be a cycle because think about now the question that we're trying to answer now that I gave you a little picture to think about. You have a much higher chance of solving this problem because think about this. Now I want to go through each of these items. Bread. Can we make bread or not? Well, now I just look at my graph and I ask myself, am I able to make bread? Like for all of the ingredients of bread, do I have them? Well, for bread, it's really easy because all of the ingredients of bread are supplies, and we know that supplies exist for sure. So, this one's like trivial. We don't have any sort of actual edges that we have to like go down. So, bread is good. Now, let's look at sandwich. Same thing here. We will look at each edge. So, we'd go down this one, we'd see, okay, it's meat. We know we have meat. But going down the other edge is interesting. We see, okay, we have bread. So, now what should we do? Because for us to know that we can make a sandwich, we want eventually all of the paths that go out of sandwich to be able to land at like leaf nodes like this. So really now what we want to know is can we make bread? So we could redo some of that work. We could kind of follow the two edges now, but it would probably be better for us to eliminate this repeated work, this need to retraverse this portion of a graph by instead having some kind of data structure. I guess for me I'll call it can cook. So for each of these recipes that are compound that aren't just supplies I'm going to track if I can cook them or not. So once we traversed bread we could track it in our hash set and say that it's true bread can be cooked. So then if we ever land on that node again like from sandwich for example then we know we already have bread. We don't have to keep going down the a graph again. So, basically, I'm just going through each of the nodes in my list of recipes and just running a pretty simple DFS on it. If you're not familiar with DFS, I highly recommend checking out some resources on graphs. I have plenty of resources on Neat Code.io if you're interested. Um, but lastly, just to finish the example, we'd look at burger. We'd start here, follow every edge. Okay, we land on bread. We already know we can make bread. We go here. We already have meat. That's like the leaf node. And then here sandwich. We already found that we can make a sandwich. So it turns out we can make all three of these. And thus we return that as the output. Now what if that was not possible? Well, I highly encourage you to try to think of an example where it's not possible for us to cook every single recipe. What would that look like? Well, it would have to be a cycle. Because think about it for bread, if it has any dependencies that are all like base cases, well then it's pretty much good. For supply here, I mean, there's no edge I can draw that would be invalid except for a circular dependency where I depend on you and you depend on me. So there's no way to make either of these unless we started out with them. If they were supplies, that'd be great. But if they're recipes and we don't start out with any of them, well then we can't make any of them ever. That doesn't mean that our result will necessarily be an empty array because like I said at kind of the beginning, we might have like disjoint sets. We might have one side here that has a cycle and something like that and we might have one side over here that doesn't have a cycle in which case this would be included in the output but these guys would not. So we're more or less done now. But I want to mention in terms of implementation details, we actually don't need to build the graph because the graph is already given to us. We already have for each like item we have a list of the ingredients. So I mean this literally is an adjacency list here. Like for each item we have a list of other nodes. So we're not going to be rebuilding this. And also for us to not use these strings. Strings take up more space generally than like integers. So instead of referring to this as like the bread node or the sandwich node, it might be easier just to use an index for us to refer to like what we're talking about. And again we will be using a hash set called ken cook so that we do not revisit the same node. Thus our time complexity should be efficient. It should just be like the size of the graph which should be the number of vertices plus edges which roughly is going to be like the sum of the supplies and recipes as well as the ingredients. When I say the sum, I mean the length, but I guess the length of the characters matters as well. Oh yeah, lastly, in case you're wondering why another algorithm that's sometimes used for cycle detection wouldn't actually work for this problem, unionf find. It would not work for this problem because union find is good at detecting cycles in undirected graphs, but it's not so great at directed graphs, which is what we are given here in this example. It can't easily detect cycles in directed graphs. We could have used like breath for search. I think that would have worked as well. I think the complexity would have been the same as um TFS. Also, this problem like very much falls into the category of the course schedule problems. It's practically identical to them if you haven't noticed by now. If you've solved these problems before, the course schedule ones, they're pretty much variations of topological sort, which is also another way to solve this problem that's a little bit more advanced and I think it's not really necessary for a problem like this one, but if you want to learn more about that, definitely check out necode.io. Okay. So, what I want to do is start out with just writing out the DFS. And this is what we want to do with it. I want to say for every recipe in my list of recipes, I want to run DFS on it. And that's the only parameter I'm going to throw in there. So, it's going to take r the recipe and I'm going to have my result, which is going to be an array. If the result of this DFS is true, then we will say, okay, we can cook this recipe. If it's false, then we assume we can't. If we can, then we do this and we can return. This isn't super important, but an easier way to write this in Python, you you can save like four lines of code. I can turn this into a oneliner like this, where I will return an array that I'm going to build with something called list comprehension. You can learn more about that in my Python for coding interviews course and it walks you through a bunch of like code that you have to write and like little challenges that you solve. But basically we write a loop inside of here. So for every recipe in the list of recipes and then we call a function. We say if dfs pretty much like we have up above. So if this returns true then take that recipe and add it to this array. I know the syntax is kind of weird if this is the first time you're seeing it, but it's a lot more concise than what we have over here. And I think that this is plenty readable. Like people who use Python write code like this all the time. So I think this is fine. Now for the DFS, the first base case is going to be this one. It's the most important. If R is in can cook my hashet, then we're going to return true. Otherwise, we will potentially do some work. But so this data structure is important. It's going to be my hash set. And initially, I guess I could say it's empty. And actually, I'm going to end up using a hashmap instead of a hash set. So, sorry for misspeaking. I think it's a little bit easier with a hashmap because what I'm going to do in here is I'm going to say for each recipe, I'm going to map it to true or false. And so, that tells me I should probably do this. Instead of returning true down here, it's possible that for that recipe, we determined that actually we can't cook it. And so in that case we'd want to return false. So here we can do can cook of this recipe. This is good. But think about what's going to happen now with our DFS when we reach the case where we hit the leaf nodes, the base case, the supply nodes. Well, we know that right now we're just going through the recipes. We're not actually going through the supplies. And so thus the supplies won't exist in Ken Cookook but they should they should be set to true. So what we can do up here is something called dictionary comprehension similar to list comprehension where we will uh for every supply in the list of supplies. I'm going to map that supply to true because we know that we can already cook all of the supplies. We already have them. Now, I'm going to try to finish up the main part of the code and then talk about some of the other details. Right now, generally what we want to do for this recipe, we want to know if we can cook it. If the base case didn't execute, then we're going to go through every neighbor in the ingredients of the current recipe. But how do I get the recipe? Well, there's many ways to handle this, I think. Like we could have passed that in to the function. We could have created like a map. We could have created our own adjacy list, but one easy way to do this is to do some pre-processing and just map every single recipe to the index of that recipe. Because if I had that, if I had something like this recipe index, and then I just pass R to that, that gives me the index of the recipe and then I can use that in ingredients to get the neighbors of the node. So, if I had that, then I could just do this. And it's pretty easy to make that. So, let's go ahead and do it. So up here once again I'm going to use dictionary comprehension. So for each recipe we want to map it to the index. So I can do this recipe to index for I enumerate uh the list of recipes. Enumerate just lets you unpack the index and the item at the same time. Cover that as well in the Python for coding interviews course. So now inside of the loop what we want to know is for like the current item R, can we cook all of the dependencies? Well, think about the opposite case. If I can't cook any of the dependencies, so if not DFS on the neighbor, if any time this ever executes, then we should just return false immediately. Otherwise, we can assume that we can cook the recipe because none of these ended up executing. And so at that point we could say can cook is going to be set to true. What we want to do is just return ken cook. Now there's a couple edge cases that we're missing. One is the fact that before we start doing the recursive case before we start running this loop and anything after that we want to say okay this recipe has not been determined whether we can cook it or not. But for now I'm going to assume I can't cook it. I'm going to put it in this hashmap and mark it as false. I'm going to assume I cannot cook it because if there is a circular dependency in this DFS, we want it to eventually stop and we want it to eventually return false. By doing this, we basically uh guarantee that that will happen by having this line of code and having this false down here. If there's a circular dependency, we will return false and we will stop the recursion. So now we're almost done, but there is one very subtle bug. And I think the easiest way for me to explain it is just to show you the code not working on this example. And you might be wondering why is it not working? Well, it's kind of an edge case. Here you can see we have a recipe bread. It has two ingredients, yeast and flour. Yeast is a supply, but flour is not a supply. And also flour is not a recipe either. So what our code is going to do for an example like that one I want to make bread. So then I go through my neighbors yeast and flour. For yeast we do the recursive call and we see that yeast is actually just a supply. So we will return true from here. But flour is not a supply. So we're going to go here. We're going to do the recursive case and then we're going to go through the neighbors of flour. But flour has not been inserted into the recipe index because flour is not a recipe. So the easiest way to get around this is just to add another if statement. So here if r is not in recipe index and if this did not execute so it's definitely not a supply. Well then we have to stop. So here we will return false because it's not a supply and it's not a recipe. So then it's definitely impossible to make it. So after that, we run the code and it works and it's pretty efficient. If you found this helpful, check out neatcode.io for a lot more.