a fun problem solving a maze. Yeah. How would you do that? Well, the way we're gonna think about it is first off, let me show you the mates. Okay, zeros are the spaces we can go to and ones are like walls blocking us off. So we're giving a start position. That's indexing this list in this case. That would be 012301. That would be 31. All right. We have that marked as our start point and we want to find the shortest way out. We can see you could go up here and then up you could go over here and then down. You can also go all the way over here. Loop back around. There's an infinite amount of ways you could solve this because you could go back and forth, back and forth, back and forth. So what should we do? Well, there's two classic algorithms for solving these mazes. One is called depth first search. Where you go all the way through one thing and you make sure by the way it's like when you look back and you're like, okay, this is the place. We've already checked. Stop checking it all the way around. Pop up. Okay, we come over here, go up, pop up someone and so forth. Um That's depth first search. The other way is breadth. First search. So we go one. Okay? And then we go check this one. Check this one. Check this one. Let's go check this one. Check this one. Check this one. Check this one. Check this one. Let me go check this one. Okay, we found a solution. Check this one. Okay, we found a solution. What about this? No more. No more. In other words we can go all the way and then come back and then go all the way over here. Okay go all the way down. Hope you can see my mouth. But yeah, we can we can check basically by going deep first and then going deep this way. Going deep and then figuring out which ones worked and seeing which one was the shortest. Or we can go one move and then check all of these and then check all of these and then check all of the next perimeter and that's called breadth. First search in our case we're gonna do a depth first. They're they're the same. I mean there's certain situations where you want to use either either or but in this case it really doesn't matter. So we're gonna use depth first. I've already implemented it. So normally this would be like a let's code, right? But this is a Rust series and you might wonder, hey, isn't this python code? Yeah, it is, it is python code. The reason for that is that this is a prototype. So dealing with data structures like this and rust is can be quite a headache. I want to make our lives a little bit easier. So I went ahead and did it in python, I'm gonna show you how it works in python and then we're gonna translate this prototype to work using rust. So, real quick. I'll just go ahead and explain how this works. We call the function. Yeah. So we have this binary maze and we search for an exit, right? And we give it the starting position. So let's look at exit, smallest distance, you can see what this is going to do. This is gonna say find all the exits. So for exit and distance itself, that exit get the smallest one and return it kind of some repetitive code here. But basically what it's doing is just finding the smallest one. Uh we can go through the syntax on that, but you can implement this however you want. It's really not the fun part. The fun part is finding all the exits. Right. Once you've found all the exits and their distances, finding the smallest one is trivial. So, how do we do this? Okay, So it looks like what we've got is We're going to a depth first search. The default position is 00, but we're giving it a different position. We check ones we've already visited, so we don't rehash them. Okay, very good. And we have this distance tracker. All right, okay. So it looks like this is a recursive one. So what we're gonna do is we're gonna say okay, for all the possible moves. We could make All right, get the roman column represented by that move. Check if it's too high or too wide and if it is, that's an exit, right? I mean that means we left, we left the matrix. If not we're gonna say make sure the next position we're trying to move to is zero. Make sure we haven't already visited it. And then search through that exit and we'll go and we'll find new exits inside of that one. Search it, search it, search it, then we'll come all the way back up here and try the next one. That's why it's depth first. Then we return the valid exits we found and that's it. We we return all of them right? We're gonna return every exit and if you notice, return the position and its distance. As a tuple that way we remember how how far away it was. If we didn't care about that, we could just find the first valid exit that we find. Right, That would be another way is just find an exit and then get the heck out. We don't care if it was the shortest possible one. Just find anyone immediately. That would make it run quicker because we would find one and then leave instead of finding every single one and seeing which one was the quickest. There you go. That's searching through a binary maze. Pretty easy to do. Hope that was helpful. Next video we're gonna be translating this to rust. That's our python prototype. Thank you so much for your time