Path Finding: Base Case

[00:00:00]
>> Let's go back into here and let's create a new file. Zoom in twice, cuz zooming in twice is the best type of zoom, and go up to the top. And so what we're gonna call this thing is the Maze Solver. Man, that was just the worst E ever, Solver.

[00:00:17]
Aren't you happy I don't have terrible handwriting? Imagine this class if I had terrible handwriting. I always thought like, man, because we had one professor that just, you couldn't tell if he's drawn an S or a 5. And you're like, is that a 5 or an S? And he would just never tell you and he drew them from the same way, and someone finally asked in class, and it was very, very funny, and everyone knew what they're saying.

[00:00:35]
Anyways, all right, so let's talk about a maze solver. So what we're gonna have is we're gonna have a list of strings. So you could imagine this, you could actually read this out from a file. We're not gonna read it out from a file, instead we'll just have an array passed in.

[00:00:49]
And this list of strings is gonna contain some characters. The first thing it's going to contain are pound signs. It could be asterisk, it doesn't really matter. These are walls. You cannot go through a wall, right? This makes sense. At some point it's gonna also have an ending, right?

[00:01:07]
The ending, of course, is where we want to get to. There we go, look at that, we already have the first row done. The second row we'll make really easy. I intentionally made this maze very, very simple. And the third row, we could have a start. There we go.

[00:01:27]
Let me just finish this off. There we go. So we're humans, we're awesome, we look at it and go, dude, you just go like that, man. It's just that simple. Well, you can't do that to a computer. You can't just go, well, look at that. I mean maybe with Dolly, I don't know.

[00:01:43]
Dolly, you say thanks to it, and out comes images that are crazy. So maybe you can do it these days, but for our sake you can't do it. So how are we going to solve this? Well, I'll tell you this much, recursion is our friend. And I've never been asked this in an interview, I don't think this would be a great interview question.

[00:02:00]
It would be great to know that they know recursion, but that's about it. It's a very simple problem once you understand it. So first, how would we just theoretically solve this? Well, once we know where our start condition is, we know what walls look like, we know what pathways look like, and we know that we're looking for an ending thing.

[00:02:19]
And maybe we're given the exact coordinate of the endpoint or just the, say, symbol it represents. It doesn't really matter what we're given, we just know that there's end, and we recognize that they're end. Well, what we could do, our human brain has probably taken over right now and say, okay, we'll go up.

[00:02:33]
Well, again, computers, you can't just say go up, right? So what would you do? Well, at any one square, let's just draw that in more of the abstract sense. What can we do at any one square? Well, we can go up, we can go right, we can go down, we can go left.

[00:02:53]
I start with up because I did too much CSS when I was a youngster, okay? Don't do CSS, it's bad for your health. And so now I always start with top, right, bottom, left, and there you go. So we can do any of those four directions, correct? Right, but you can't always do them, right?

[00:03:12]
You could run into walls, correct? Walls are bad. You could go off the graph, right? If we went down from start, we'd be literally off the graph, that would be really, really bad, correct? Correct, we could also go to a spot we've seen before. That'd be pretty bad, right?

[00:03:29]
You wouldn't wanna just sit there and go back and forth between, maybe it's here, maybe it's here, and then you're stuck forever in this loop, because you didn't program it correctly. All right, so we should consider these all our base case. And there's a good reason why you consider the base case, and you don't check for it in the recursive case.

[00:03:47]
It's very, very important not to do that. I keep stressing the base case cuz it just makes recursion a million times simpler. So let's think about our base cases. Base Case. Well, 1, it's a wall, right? If the point we're at in recursion, we are on a wall, we cannot be here, correct?

[00:04:13]
Right, you're on a wall, you cannot be here. So that's an invalid state, perfect. 2, what's the next one? I feel like there's four. Now, all of a sudden, I'm confused. Yeah, off the map, right? If somehow you're in a spot that's not on the map, you have to return, correct?

[00:04:36]
That makes sense. 3, it's the end, right? Cuz if we make it to the end, we are done recursing, right? That is our actual goal is to make it to that point, correct? Awesome. And then 4, if we have seen it. This part is very, very important. Have you seen this tile before?

[00:05:05]
If you have, you also don't want to be here, right? We don't want to visit anything twice. So that's really the base cases. And then the recursive cases is simply checking every direction. It's the dot, so the recursive step is actually pretty simple. Just go all four directions.

[00:05:23]
The base case is really, really simple. Can't be any of these places, and that's it. And so when you put these two things together, when we program them, it actually becomes very, very easy. All right, so I believe at this point I said, hey, yeah, let's implement it.

[00:05:40]
Yeah, let's implement it. All right, so is everyone ready to implement it? So in the Kata machine, we can actually implement this. This is one of the things that I put in there. So if we go to our day1 and go to MazeSolver, it is right here. So this is what we're past in.

[00:05:55]
We're past in a maze, which is a list of strings, all right? So that's exactly like that, correct? Awesome, we're past in what a wall looks like. Hey, this is a wall, so we now know what a wall is. We're past in our starting point. Awesome, we now know where to start.

[00:06:12]
And last, we're past in an ending point, we know where to end. And lastly, we need to return, I said lastly twice. Most lastly, we need to return a list of points from the start to the end. This is where things get a little tricksy, right? This is where the hard things happen.

[00:06:30]
Well, don't worry, it's not actually all that hard. So like any good recursive function, I often find that the entrance to the recursive function, like this function solve, isn't the one you want to recurse in. I don't know why it always ends up being that way, it just does.

[00:06:44]
So let's just write a function up here and let's call it walk, right? So we're just gonna simply walk the maze. So remember, we want to be able to do our base cases, then our recursive cases. The base cases require us to know where we're currently at, the recursive case requires us to be able to walk in directions.

[00:07:03]
So let's remember that. So I guess that means we need the maze to be able to walk, correct? We're probably gonna want the wall because we need to know if we're on a wall or not. We're gonna want the current point, where are we at this exact moment, right?

[00:07:20]
We just need to know where we're at. We need to know the ending, cuz again, that's a part of our ability to know if we've been done, it's one of our base cases. All right, for now we can just keep it like that, we're gonna add some more things.

[00:07:35]
Don't you just love when arguments get really long? I do, too. And lastly, I am gonna do this, I'm gonna kinda give away a part of the game. We're gonna wanna return a true or a false. And there's good reasons for it, so just let it happen. All right, so first, let's just start with the base cases.

[00:07:51]
We don't even need to know how to do recursion to be able to program these base cases, right? Base cases are pretty simple. So let's move these two around, right? Because if we're in a language in which you accessed outside of the bounds, it would throw an error.

[00:08:08]
Right now we're in TypeScript which doesn't do that, but we're gonna pretend like it is because it's just good practice. So 1, base case, let's say, off the map, right? So are we off the map? So easy check, we can go curr.x is greater than or, let's say, is less than 0, or curr.x >= maze first row, it's a square, right?

[00:08:34]
It's a square, the maze is a square, so we can just say, hey, your first row's length, right? That's what we're grabbing out of here. Cuz remember, whenever you're doing 2D arrays, you actually traverse the columns, then the rows, it's backwards, unless if you tilt it 90 degrees.

[00:08:51]
So just a fun little fact, just makes it easier cuz then you can print it in order as well, right? So that is a base case, correct? Well, we also need to do this for the y case, correct? We need to be able to also check our y condition.

[00:09:04]
So I'm gonna go to the end, and let's do another or, and let's do the exact same thing again. Let's go if curr.y < 0, or curr.y > = maze.length, right? That's how many rows we have, there we go, awesome. There we go, so we have our first condition.

[00:09:24]
If we run into this condition, we return false. This is not a place we should be looking. Great, oopsies, what's our second one? Our second one, let's find out. It's, are we on a wall? Okay, that's pretty straightforward. On a wall, I normally don't comment to code as simple as this, but for the case of us walking through from pseudocode to actual code, I'm trying to make it more concrete.

[00:09:49]
All right, so if current, let's go like this, let's go if (maze[curr.y][curr.x]. I know, don't you love, it's just beautiful that way, is equal to the wall. Well, we've just got done. We're on a wall, we cannot be here, right? We've recursed into a spot we're not supposed to be, return false.

[00:10:09]
Our third condition, which is, are we at the end? Okay, well, this should be pretty easy. If(curr.x === end.x, curr.y === end.y, well, guess what? We're there. end.y actually sounds like a word, I don't know why that is, it almost sounds like endonym, just kinda got in my head there for a second.

[00:10:29]
Anyway, so if we do get to this point, we have successfully found the end, great success, and now we're done recursing, right? Yay, our base case, we're done. This is awesome. All right, but we do have one more condition, which is seen. How the heck do we do a seen, right?

[00:10:47]
Well, we could mutate our points to have a true and false on them. But then, now we have this weird type that's both a point and a Boolean, right? It's kinda weird, maybe too much information on that single type. So what we can do, and one of the beautiful parts about recursion, is that we can have a beautiful Boolean 2D array.

[00:11:07]
Here's every position that is possible. False if we haven't seen it, true if we have seen it. All right, awesome. Look at that, just made life easier. So if (seen[curr y][curr x]), then guess what? Return false, we don't wanna be here. We don't wanna keep recursing on places we've already been.

[00:11:27]
That means you'd get into an infinite loop effectively, you'd blow your stack eventually. So you don't wanna do that, cuz, If you could imagine a situation where you get down a corridor or something like this, and we went in CSS order, right? You would get here, you go, can't go here, can't go here, can't go here, go back.

[00:11:50]
I can traverse here, can't go here, go this way. Traverse here, here, here, go back. Here, and you just, [SOUND] and eventually you'd run out of memory and everything would explode. Cuz remember, we store return address, return value and arguments, therefore you would run out of memory just calling it over and over again.

[00:12:08]
That's what a stack overflow is effectively, in the easiest way. It's not the website in which you ask a question, someone berates you, it's actually what happens on a computer. It's named after something, on a computer it's different. All right, so there we go, we've done our base case.

[00:12:21]
So now that we've done our base case, we can actually do the recursive step. But this was pretty easy, right? We can all agree the base case makes sense.