Four Semesters of Computer Science in 5 Hours, Part 2 Pathfinding Solution

[00:00:00]
>> Brian Holt: So welcome back. Hopefully you're able to feel your brain a little bit before we start melting it again. [LAUGH] We talked about pathfinding last time. We gave you the exercise and so what we're gonna do now is we're gonna go through and write it together so we can see what it looks like.

[00:00:27]
>> Brian Holt: Let's go ahead and get started. So the first thing that I'm gonna do is I'm just gonna make three different flags of has this particular note been opened by no one, has it been opened by someone and like which person has been opened by or which origin point rather.

[00:00:54] So no one,
>> Brian Holt: Equals zero Const by A equals 1, and const by B equals 2. Now, I could just put those numbers directly in there, but the reason why I like doing this is so it makes my code a little bit more readable. So if these two aren't equal to each other it means something's up and we should investigate.

[00:01:24] Wonder why my, well, it's different, it is what it is. Okay. So, we're gonna start by doing that. Next, we're gonna go start writing our algorithm. Actually, lets go ahead and write Get neighbors as well. Because this is going to be a useful function. Like helper function for us that we talked about.

[00:01:48] The basic idea being if I have one part of the graph, I'm going to investigate above it, to the right of it, below it, and to the left of it. [COUGH] This will be useful because we can contain all the logic in therefore, checking if it's a wall, checking if it's like all those various checks we have to do.

[00:02:13] That will be useful to kind of contain in one place. It will make it testable and those, you know kind of idea. So I'm gonna call it getNeighbors and and it's gonna take in visited, which is what I'm calling my graph. And it's gonna take in a point, okay?

[00:02:38]
>> Brian Holt: So this neighbors array is gonna be valid neighbors. This is eventually what I'm going to return at the bottom. And then I'm just gonna go check all the sides.
>> Brian Holt: So the first thing I'm gonna say is, if y minus 1,
>> Brian Holt: Is greater than or equal to 0, again, this is a ligature that combines those two things together, right?

[00:03:09] If I put a space between those it's less than equal to, but if I put them together, that's just my font, right? Sometimes that confuses people.
>> Brian Holt: And If it's not closed, so visited y minus 1 x.closed. This is going to the left, right? I think so yeah, it's going to the left.

[00:03:44] Then we're going to say, neighbors.push visited y minus 1 of x, this confuses people. You're used to see X Y, right? But if you think about it as this is an array of arrays, right? This is an array of arrays, right? So actually the Y column is represented by the first array and the X column is represented by the second array.

[00:04:15] Which is why you're gonna do Y is the first accessor and X is the second accessor does that make sense to you? You can do a bunch of backwards thinking to get it to go the other way but just don't [LAUGH] I promise this is easier. Okay, so does this make sense what we're doing right here?

[00:04:37] We're just saying If this is not out of bounds, right, so if it's not below zero and it's not closed. We're going to make this data structure that's going to make this true later. But closed just means that it's not a one. You could have just as easily said, triple equals one, here, right?

[00:04:57] Then put that into a valid neighbor. And we're gonna do that for each one of these. In fact I'm just gonna copy and paste 'cuz we all know that I'm good at that. So this one we're gonna go right. So this is gonna be y plus 1 is less than visited 0.length, right?

[00:05:28] Again, to the graph that I'm giving you is a square, right, so you can just check the row of the first, the first row's length. And say is this outside of the bounds of that particular row, right? Does that make sense?
>> Brian Holt: And then here, and it's not closed.

[00:05:55]
>> Brian Holt: Then push that in, right? And this is gonna check to the right, so far so good?
>> Brian Holt: Okay, let's go ahead and do up.
>> Brian Holt: So now, we're gonna do x plus 1 is greater than visited 0.length.
>> Brian Holt: Did I, I did mess this up, didn't I?

[00:06:29] It actually doesn't matter because so this should be, right? Yep, that is. This wasn't a bug because everything I gave you was a square, too. Which may not always be true. But nonetheless, x plus 1 is less than visited 0.length. And visited y of x plus 1. y plus 1.

[00:06:59]
>> Brian Holt: Then we're gonna push in neighbors.
>> Brian Holt: Of yx plus1.
>> Brian Holt: Okay? That was up.
>> Brian Holt: And lastly, we're gonna go down.
>> Brian Holt: Down, down. Now, we're doing the get neighbors function. We're gonna use that inside of our function that we're about to write up. If we were gonna do diagonals as well, if that was gonna be a valid move, we would just put some more function or more checks in here.

[00:07:35] To say can I go northeast, can I go northwest, southeast, southwest, right? And that's all you would have to do to add diagonals functionality to this code, which is pretty cool I think.
>> Brian Holt: So this is actually down, I believe.
>> Brian Holt: Yeah, it's down.
>> Brian Holt: Cardinality is a weird thing.

[00:08:02] [LAUGH] It all depends on what perspective you're taking on it. x + 1, so we're gonna do x- 1 > 0.
>> Brian Holt: Greater than or equal to cuz you can go to 0. And this is going to be x- 1.
>> Brian Holt: And the new approach, x- 1. There we go, okay.

[00:08:43] So far, you're just gonna get all of the valid neighbors. So that's all this function's gonna do for you. And that makes it really easy for us in the above function to be able to go through each one of those. And check if we've intersected and all that kind of stuff.

[00:09:00] So now that we've done that, let's go back up to our findShortestPath function and start on that.
>> Brian Holt: So the first thing what we're going to do is massage this maze data structure into something a little bit more useful. So I'm gonna call this visited. And we're gonna do maze.map.

[00:09:34] If your not familiar with map, again, I suggest you check out the first course. There's a whole section on what is map. There's also plenty of stuff on Frontend Masters from Brian Lonsdorf and Kyle Simpson about functional programming in general. But the too long didn't read version of what map is, is it's a function that takes in another function.

[00:09:58] And it's going to apply that function to every item in your array. Whatever that function returns on that individual item is going to be the new value in the array. So just to give you a really quick demo of that, if I do 1,2,3. So an array of 1,2,3 and I say .map.

[00:10:17] And now I'm gonna give it a function that all I want it to do is double the numbers in the array. So it's gonna be function, oops, num. And that's just going to return x x 2, or num x 2 rather.
>> Brian Holt: So what I would expect back is to get 2, 4, 6, right?

[00:10:43] 2, 4, 6, so that's what map does. Whatever this function does, it's going to be run on every item in the array. And then whatever is returned there is going to be the new array. So it's a very, very valuable function. If you're not familiar with it, I definitely suggest deep diving.

[00:11:00] I use this dozens of time a day. Probably not exaggerating, probably a dozen times a day. So that's what we're doing here. What I showed you here is a simple example. But, please go away. Okay, there we go. [COUGH] The times that you're gonna use map are the times that you say, I have this one array of things and I want another array of things, right?

[00:11:26] I wanna transform this set of things into this set of things, right? So in this case, I have this array of arrays, right? And what I wanna get back is an array of array of objects, right? Because I wanna be able to mark this has been visited, this is the value.

[00:11:41] This is how far away, I wanna be able to associate some metadata associated with that. So that's what I'm gonna do up here in this map.
>> Brian Holt: So I'm gonna say row map, and I'm gonna say,
>> Brian Holt: row, y, right? The second item that you get in there is the index.

[00:12:01] So this is gonna represent wherever I am in the array on the y axis.
>> Brian Holt: Okay?
>> Brian Holt: Then you have to keep in mind that row is what? Row is an array of numbers, right? Because working with an array of an array of numbers. It's a 2D array.

[00:12:21] So row is gonna be an array, so what I wanna do is I want to return row.map. So we're going to do another map inside of here. So row.map and this is going to be some point. Well, we can call it a point or a cell or whatever you wanna call it.

[00:12:40] I think I called it origin. But let's go with point. That might make more sense. It's one point on the graph. And the index that here is gonna be represented as the x axis. Cool, do we follow so far?
>> Brian Holt: Now you could definitely do this without map.

[00:13:04] I just find this to be, it simplifies the mental model for me, okay? Now what we're going to do here is we're going to return an object. The first thing that I want it keeping track of, is it closed, right? We know if a thing is closed if the point ===, again, people find that weird.

[00:13:31] That's my ===, right? So if I say ===, so if you see the three lines that's what that is.
>> Brian Holt: 1, then we know that that point is closed. It's a wall, you can't go through it, okay? The length at time of creation is 0, right? Because we haven't touched it yet.

[00:13:53] openedBy, openedBy, it's been opened by NO_ONE, right? Remember this up here? So that's what that represents.
>> Brian Holt: And then lastly, we wanna put in the x y value for every one of these, right? So you can put x: x. Because we're using modern JavaScript, you can just put x and y.

[00:14:17] It's the same thing, right? x: x, or just x.
>> Brian Holt: Cool.
>> Brian Holt: So now I have this really useful data structure that I can start working the grid with.
>> Brian Holt: So the first thing I'm gonna do is I'm going to go mark.
>> Brian Holt: visited [yA] and [xA] as being visited by itself, right?

[00:14:54] That follows.
>> Brian Holt: So openedBy = BY_A. Same thing down here for B.
>> [COUGH]
>> Brian Holt: Bless you.
>> Brian Holt: Then after that, we're going to go mark B as being marked by B.
>> Brian Holt: We still follow? Right, makes sense that something, the origin has been opened by itself.
>> Brian Holt: Now we're gonna go and do two depth first traversals with these.

[00:15:34] Or sorry, not depth first, breadth first. I don't know what I'm talking about. Keep up, okay, so just kidding, that's terrible. let, we're gonna have an aQueue and a bQueue. let aQueue, I know it's weird terminology. So what we're gonna put, we're gonna put one item in this.

[00:15:54] We're gonna put the origin, right? Cuz that's where we're gonna start. So we're gonna put Visited yA xA, right? It's gonna be an array, right, because when you keep continuing putting things in there and take out there, and same thing with pQ. This is what I was saying, that you could be clever and do this with one queue, well, you can't do it with one queue.

[00:16:21] But you could do it with one function, but don't. This is just a lot clearer to write this way, even if it is a little repeating yourself.
>> Brian Holt: Okay, and then we also have to keep track of the iteration that we are on. So let iteration equal zero because we have to mark.

[00:16:47] This is one away, two away, and three away for the iteration to keep track of. So now, down here we are going to have a Y loop, while aqueue.length && bqueue.length. Right, because if we have a maze that's unsolvable, eventually one of these is gonna run out. And if one of them runs out, you'll instantly know.

[00:17:19] It doesn't matter what the other one is gonna do, there's no way to get to the other one. So if that's true, then you're going to return negative 1 down here at the bottom. Because, if it's not case, then we'll know somewhere in the loop here, we'll just return that number.

[00:17:41]
>> Brian Holt: Cool, so first thing we're gonna do is we're gonna start out by going iteration, plus plus, cuz it's the next iteration. And we're going to set.
>> Brian Holt: First thing we're gonna do is we're gonna go get As neighbors. So we're gonna say ,const aNeighbors. So what you need to do is you need to go through everything that's currently in the a queue.

[00:18:15] I mean, you need to go get all its neighbors, right? So if I have four things in the aQueue, I need to go get all of the neighbors for all of those, right? So that could end up being, four times four, it could be quite a few neighbors.

[00:18:29] And as you get further and further out, you have the potential to have lots and lots and lots of neighbors.
>> Brian Holt: So you can, however you want to do this is totally up to you, right? You can have a for loop that keeps them all together. Me being someone that likes a little bit more functional approach to things, you can implement this fairly easy as a reduce.

[00:18:52] So just to give you the five second version, maybe 15 second version of what it reduces. One, two, three, right, and I say reduce. This is going to take in a function, but it's reducing an array of things down to another something. So in this particular case, I'm gonna have usually it's called acc for accumulator.

[00:19:16] I did not invent that so and it's gonna be some number. And let's just I want to add all those numbers together, right? So what I'm going to do is it's going to return acc plus number.
>> Brian Holt: And this should just add them all together, right? So I get six, right?

[00:19:38] Which is all of them added together, right? So what acc is the result of the previous iteration. So it starts out with one because it just pulls the first item off the list, right? And then it goes through [COUGH] it returns that. So this is going to be one, and then it's going to add two to it and then it's gonna add three to it and then we end up with six, right?

[00:19:59] Do we understand more or less what reduce is? So the times we wanna use reduce is when you have an array of something and you want to basically in some way combine it with the other elements in the array.
>> Brian Holt: Not quite as useful as map, but I still use it quite frequently.

[00:20:16] Like if I use math 50% of the time, I use reduce 10% of the time, or something like that. Okay.
>> Brian Holt: So what I'm going to do is, aQueue, it's going to be a reduce function.
>> Brian Holt: So it's gonna be that accumulator, right? Now in this particular case, I have an array of these various items, right?

[00:20:50] What I want to do is I wanna have an array of all its neighbors. So that's what I'm gonna write in terms of a reduce. So neighbor, and what I am going to return. I want to return acc which is going to be an array. I'm going to call concat which is, I'm gonna add another array to it.

[00:21:19] That's gonna be a result of getNeighbors with visited, neighbor.x and neighbor.y, okay? You follow so far? I will also say that this also could be implemented as a map and flatten, but we don't have flatten yet. In fact, if you've been following the Twitter drama this week, they're debating if they wanna call it smush or flatten.

[00:21:53]
>> Brian Holt: JavaScript is weird. That's all I'm gonna say. It's a ridiculous argument. I'm not upset, okay, let's keep going. So that's there, if you don't provide reduced seed value it just pulls the first time off the array. We don't actually want it to be the first time in the array we want it to be an empty array.

[00:22:16] So that's going to be the first acc, right? So the first acc, we want it to be an array, so that's what we provided here.
>> Brian Holt: So even if this is a little bit difficult to read for those of you that are not more functionally oriented yet. One, I have faith in you, and, two, what this does is I have an array of next notes to process and this just gets me all of the neighbors of that.

[00:22:50] That's what this blob of code does, cool? Okay.
>> Brian Holt: So next thing I'm gonna do here is I'm gonna go through every item in this particular list, and I'm going to process it. So I'm gonna say, for let i equal to 0, i less than any neighbors, rather, .length i plus plus.

[00:23:26] The typical full loop. So the current neighbor I'm on. Let's just put some space there so you can see.
>> Brian Holt: neighbor equals aNeighbors of i, right? That's the current thing that we're on at this moment in time.
>> Brian Holt: Then, The first thing that we're going to check because we're processing a.

[00:23:59] If the current neighbor that we're on has been processed by b, we've solved it, right? We've intersected with the other one so we've found the answer. So that's the first thing that we're gonna check.
>> Brian Holt: So if (neighbor.openedBy === BY_B), then we have solved the problem, right?
>> Brian Holt: So what you're gonna do is you're gonna return neighbor.length + iteration, right?

[00:24:33] So that basically means whereever we are in their currents file plus the length of the neighbor. Those added together is gonna be the correct answer of how far away I was. Does that make sense?
>> off screen male: What's neighbor going [INAUDIBLE]
>> Brian Holt: neighbor.length, if we go up here into this data structure that we created.

[00:24:57] It's how far away it is from its origin, right? So if it's opened by b, it's 10 away from b, right? So it's going to be the length of the current node plus the length of the neighbor node, yeah?
>> Brian Holt: It is, I assure you, but let's understand why that is, right?

[00:25:20] So can I just, let's see if I can bring this up, four.
>> Brian Holt: If we're going out to Pathfinding, right? So if I meet here, so here. Iteration is let's say I'm on this node at the time, right? The one that I've highlighted there. If I'm on that node at the time, iteration is going to be where I am right now at this moment in time.

[00:25:50] So that's going to be 3, right? And then I find this one, it's going to be plus the length that that one is away, right? So those are the two numbers that we're adding together to get the correct answer, yeah?
>> off screen female: Are we updating the length somewhere?
>> Brian Holt: Yeah, we'll get there.

[00:26:07]
>> off screen female: Okay, we're not-
>> Brian Holt: Yeah, we haven't gotten there yet.
>> off screen female: That's probably why it doesn't make sense.
>> Brian Holt: It's magical. [LAUGH]
>> off screen female: [LAUGH] I was gonna say, cuz I'm pretty sure all the lengths are 0 right now.
>> Brian Holt: Yeah no, I'm gonna call the sprinkle fairy dust function next.

[00:26:20]
>> off screen female: [LAUGH]
>> Brian Holt: Yeah, that's a good point. Fair point, okay. So if it hasn't been opened by anyone, then you update the length, so else.
>> Brian Holt: else if,
>> Brian Holt: (neighbor.openedBy === NO_ONE). Then we're gonna do all this updating that we were talking about, right? Now there's one more case that we haven't provided for.

[00:26:54] What if it's opened by A? Just ignore it, it's already been processed, right? So a good example of that going back here. If I'm, let's say, here. I'm processing this node right here. It's going to see this node and it's gonna see this node, right? Because those are valid neighbors, right?

[00:27:14] That's gonna see those have been open by A. I'm not gonna check those, right? They have been checked. So that's why you're just ignoring the opened by A case. Does that make some sense? Cool.
>> Brian Holt: So first thing we're gonna say is neighbor.length = iteration. neighbor.openedBy = BY_A, right?

[00:27:40] Cuz it's been opened by A. And then what we're going to do is we're going to push it on the aQueue, right? So that on the next iteration, up here, it's gonna go okay, all of its neighbors and then process all the neighbors, right? So that's why you push itself on there.

[00:28:04]
>> Brian Holt: And that's it. That's how you process the A part. Now what we're gonna do is we're just going to copy and paste this little block of code. The one thing I did miss.
>> Brian Holt: You could do this by queueing and dequeuing, right? So I could have been shifting these things off instead of saying neighbor.length, whatever.

[00:28:29] What I'm just gonna do here is once I've processed all the neighbors and I have them up here. I'm just gonna say aQueue = new array, right? Because you don't wanna process those things again. Somehow you have to get them out of the array. If you wanna do that by shifting or whatever, be destructive on the other array, that's fine.

[00:28:45] Up to you. Some of the stories each iteration you need a new queue. Well, rather it needs to be cleared out by this point. In fact, that's actually why you have to do it this way. Scratch that, listen to me, only do it this way. [LAUGH] Once I've grabbed all the neighbors, I'm gonna start pushing things into the new queue to be processed next time, right?

[00:29:08] So that's why I got get all the neighbors and I reset the queue. So that I can have a new queue to work with. Does that make sense? Okay.
>> Brian Holt: Sometimes I have to work through my own problems. That's what my therapist tells me, just kidding.
>> Brian Holt: Cool, so we're gonna do the same thing.

[00:29:30] We're just gonna grab everything like this and we're just gonna change everything from a to b.
>> Brian Holt: So bNeighbors = bQueue. This is all fine. bQueue= blank. aNeighbors, bNeighbors, BY_A.
>> Brian Holt: This has been opened BY_B, and aQueue. Did I miss any?
>> Brian Holt: Again, you could be more clever and drive out this.

[00:30:16] What's annoying about this is if you modify anything in here, you're gonna have to modify it in two places. It is annoying. Just like my personal kind of mantra of Web development is only abstract things when you have to. Because abstractions just make things tougher in general, right?

[00:30:33] Something like this, I would typically leave in my code, just personally. But I know this would greatly offend some people and they're wrong. So don't listen to them, [LAUGH] listen to me. No, I'm just kidding. Yeah, listen to me at your own risk. That's a good idea. Okay, so I think this should work now.

[00:30:53]
>> Brian Holt: Let's give it a shot, see what happens, fingers crossed.
>> Brian Holt: First time. [LAUGH] So let's see what happens if we go for the other two as well. So the extra credit ones.
>> Brian Holt: And it does solve. What happens if there's no possible path and it does solve it if they're next to each other as well?

[00:31:25]
>> Brian Holt: Any questions, or rather, what questions? There's gotta be questions about this.
>> Brian Holt: Either I taught it perfectly and everyone gets it or everyone's like no just shut up and move on, Brian. [LAUGH] Okay, it's the latter. I was not expecting that. [LAUGH]
>> Brian Holt: Conceptually, does this make sense?

[00:31:58] That's the important thing. Whether or not you actually got the correct syntax on the page, I'm confident that if I gave you enough time and you spent enough hours debugging and crying, like I did when I was writing this, that you would come to the correct answer, right?

[00:32:12] Given time we can solve these problems, but what's important is that you grasp these conceptually, right? Cuz later, at some point, it might not be solving a maze, but maybe it's like finding the closest edge network in your CDN or something like that, right? That's what's important. Because eventually you're gonna have this problem that's like, that looks like a graph that I'm gonna have to do a breadth-first traversal on.

[00:32:32] Those are the kind of patterns that I want you to recognize. This is like pathfinding, right? Cuz this is useful for more than just finding from point a to point b, not everyone's gonna look at Google Maps. But there are a lot of us have to work with CDNs and that's just traversing things, right?

[00:32:48] So that's what's important about this, that's what I would really would like you to get out of this. All right, that said is there any questions?
>> off screen female: I have a question?
>> Brian Holt: Yeah.
>> off screen female: So if you go back to where you're looping through the neighbors, in the else if statement for either the b cue or the a cue, when you're pushing the neighbor back onto the b cue, that's because you're gonna come back and reduce again and get the neighbors of that node.

[00:33:17]
>> Brian Holt: Yep.
>> off screen female: Okay, okay, that's the part that just connected.
>> Brian Holt: Yeah, it's a little weird. So I don't blame you for having to reason through that out loud.
>> off screen female: Okay [LAUGH].
>> Brian Holt: I talk to myself, but mostly I just talk to my dog. She just looks at me.

[00:33:32] It's like, I don't care about this. Just give me treats. Yes, so you are kind of re-populating so the next the iteration through then you can process them again, right, yep that's accurate. Okay, cool. We all get it, this is all perfect, everyone's really happy about this.
>> off screen male: The question is she didn't understand why you would need to clear the aQueue.

[00:33:59]
>> Brian Holt: Sure let's take a look at that really quick.
>> Brian Holt: So,
>> Brian Holt: I'm gonna get aNeighbors, right? aNeighbors is going to be. All of the neighbors, all the valid neighbors for everything that's currently in my queue, right? Why are we clearing out a queue every single time? aNeighbors, after we do this line 39 right here, is going to be full of all of the valid neighbors that we're going to process on this particular iteration.

[00:34:40] What we need to do is aq for the next iteration, after we finish with this entire iteration, it needs to be full of the next set of neighbors to process. So, after we do this aNeighbors thing, aq is still going to be full of the previous neighbors, right?

[00:34:57] But we've gotten all the information that we'd need out of them, so we don't need to worry about them anymore. And if we don't clear it out, we're just going to be adding more and more things to the queue that we're going to keep processing over and over and over and over again, which we don't need to do.

[00:35:10] It would be totally pointless. So that's why we cleared out. And then down here we can end queue a bunch of new things that need to be processed on the next iteration.
>> Brian Holt: Does that make sense?
>> Brian Holt: I see blank stares so no, that does not make any sense.

[00:35:28] So,
>> Brian Holt: Let's see.
>> Brian Holt: Let's see if I can show you this way. All right so, come on. There we go.
>> Brian Holt: Let's go all the way to the top. Make this just a tiny bit smaller so I can get everything on the page. Okay. So, and then make this a little bit bigger so you can see the code.

[00:36:00]
>> Brian Holt: So if I'm processing, let's go with just a queue right now. So everything that's here that's marked as two, right? Would be processing the next iteration on top of that. What I need when I process it this time, is this needs to be enqueued, this one, this one, this one and that one, right?

[00:36:23] Those all need to be added so I can process those on the next one. However, the problem that we have, particularly with AQ is it's still full of everything that has two on it. We have to remove everything that all those two's because if you don't want to process them again.

[00:36:36] We want to process the three's, and then the four's, and then the five's. So that's what we do here is we cleared out so that there's no more two's and it's just gonna be full of three's after this current iteration. That's why we clear it out. Does that make more sense?

[00:36:51]
>> off screen female: So it is kind of like how we unshifted the element in our breadth-first search? But this time, instead of unshifting one thing, we're unshifting many things.
>> Brian Holt: The whole thing. That's a very good way of putting it. That you're basically dequeuing everything all at once. Whereas before we had been doing it one at a time, we're just doing it a batch at a time.

[00:37:13] Yeah. Do you want to teach? [LAUGH]
>> off screen female: No, that was my contribution. I'm done now.
>> Brian Holt: Okay, well thank you, that was very valuable. Cool.