This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Generating a Maze Solution" Lesson
[00:00:00]
>> Brian Holt: So what we're gonna do now is we're going to make some helper utility functions. And it's gonna be annoying to try and interpret north, east, south, west, and have those string checks all over our code. It would be really cool if there was a function that I could just pass in north, and it would just say go up one, right, in terms of numbers.
[00:00:19] So what I'm gonna do is, I'm gonna make a const getModifier. It's gonna take in some key. And this key is going to return, again, an x,y pair of where I should go. Now, I'm gonna write this in a really compressed ternary. But you can totally, we can even just do it in terms of, this is fine.
[00:00:51]
>> Brian Holt: So, if key triple equals north, then return
[0, 1].
>> Brian Holt: If key triple equals south, then return
[0, -1]. If key triple equals, you can make these l is, as well. It doesn't particularly matter, because whenever you call return, it just ends the function. So either way, I'm just lazy, so I just do it this way.
[00:01:38] But you can do it however you want. So if it's east, it's gonna go positive 1.
>> Brian Holt: I have to return that. And finally, just return. Cuz these are the only options, so you don't have to really check for west.
>> Brian Holt: But you could do that as well if you wanted to, okay?
[00:02:05] So now I have this function. Whenever I call it, I'm gonna get the proper modifier to go up or down.
>> Brian Holt: Okay, and then the other thing I wanna do is, because I have to worry a lot about the opposite, right? Because if I go north, I'm gonna tear down a wall there right?
[00:02:28] But it's also good to know for the other one, I have to tear down the other wall, right? So that's what I'm gonna do here is the getOpposite. So, const getOpposite, it's gonna again take in a key. This could be a key pair value as well. And again, the function could have been a key value pair as well.
[00:02:47] I just like doing things in terms of functions. So if key, in fact, what we can do here is just copy this same logic cuz it's the same sort of logic. Paste it in here, but instead of that we can just put south, north, west, east, right? So now this is a really easy thing.
[00:03:14] I just call getOpposite, and I instantly know what the other opposite direction is. It just makes it a lot easier to deal with all these strings. I can deal with numbers and assume that they're valid numbers, rather than trying to deal with strings everywhere.
>> Brian Holt: Okay, so this is a recursive function.
[00:03:34] You might have been tipped off in recursive backtracking, I don't know. If not, you might have a problem. Just kidding.
>> Brian Holt: So I'm gonna write a function called nextNode, right? It's just gonna process the nextNode in this. And I'm gonna call it with xStart, I can spell, yStart, and maze.
[00:03:58] I don't know why I chose to flip the argument order. It doesn't make any sense, but that's what I did. So we're going with it, const nextNode = (x, y, maze), okay? The current node that I'm working on is going to be, const,
>> Brian Holt: const node = maze[y][x].
[00:04:28] Right, that's the current node that we're going to be operating on. The first thing that we're going to do is we're gonna say node.visited = true, right? Cuz we're on the node, we're processing it at the moment. Then, we're gonna do randomizeDirection. Which again, is just gonna be an array of those strings of directions to go.
[00:04:52] So I'm gonna do that, and I'm gonna do a forEach that's gonna be a direction.
>> Brian Holt: So I'm gonna do const [xMod, yMod] = getModifier, of the direction that I'm going, right? So that's why I got this x modifier. So this is called destructuring, right? So I know at the 0 element, I have the x, and at the 1 element, I have the y modifier.
[00:05:31] So I'm just pulling those out and into variables called that, right. It's a brand new ES 6, ES 2015 functionality.
>> Brian Holt: So here, I'm gonna have a long if statement. So if, we'll put this on multiple lines, cuz I think it works a little bit better. if maze[y + yMod], so you're trying to make sure that you're not going off of the grid, right?
[00:06:18]
>> Brian Holt: So you're trying to make sure that you're not going off in the y direction. You also need to make sure that you don't go off in the y + yMod.
>> Brian Holt: And oops, x + xMod. So this is making sure that you don't have a null accessory, right?
[00:06:37] Because if I go off in the y direction, there's gonna be no array there to check, right? So you need to check that first the y is valid. But then you need to check that the y and the x are valid. And then you need to check to make sure that they're not visited, right?
[00:06:50] So not visited, maze[y + yMod][x + xMod]. You could've totally done this with something like Lodash. I just wanted to code it out so you can see what's going on. .visited, right, so if it exists and has not been visited, that's what this if statement is saying.
>> Brian Holt: Okay, then you're gonna say node[direction] = false.
[00:07:24] And then you wanna say maze, at the next place you're going, yMod, x + xMod. So that's gonna be a new node, right? This particular thing that we're operating on is a new node. And then we want to set the opposite direction to be false. So if I went north here, I want the south wall of the one above it to be false as well.
[00:07:52] So that's where we're gonna use the getOpposite function here to be false as well. And this will create the burrow, right? It'll tear down both walls.
>> Brian Holt: Okay, and then here is where our recursive call comes. So, nextNode(x + xMod, y + yMod, maze).
>> Brian Holt: Okay, and then just down here I have return false here.
[00:08:38]
>> Brian Holt: Yeah, it doesn't matter. You can return void as well, either/or. And eventually you'll end up with this maze.
>> Brian Holt: That will, that'll work. The reason why this works is because you're just always operating on maze, right? So whatever happens to maze, it still should work. So let's give that a shot, see if it runs.
[00:09:08]
>> Brian Holt: And it works. So if you wanna see if the giant one works,
>> Brian Holt: Give that a shot.
>> Brian Holt: You'll see that the big maze works too, and all the units tests passed.
>> Brian Holt: Pretty cool, right? We generated that, we wrote the code that generates this. To me, I don't know if I get too self impressed sometimes.
[00:09:36] But I think it's really cool that we can write code that generates something like that. I don't know.
>> Brian Holt: Anyway.
>> Speaker 2: I think it's cool that you can write unit tests for something random and have them pass.
>> Brian Holt: Right, yeah, you just have able to provide some sort of deterministic seed value, right, which is what those randomized things said.
[00:10:01] So be it'd kind of a specific unit test. I don't know if they would be the best ones, but this would be something really ideal for something like just snapshot tests, right? That given this input, it gives you this output.
>> Speaker 2: Yeah.
>> Brian Holt: And it would be a lot easier to write than when I wrote it here for you.
[00:10:17] But, yeah, totally, it is really cool. How do we feel about this? Conceptually, do we follow what happened here?
>> Brian Holt: Cool, I will say that this used to be a question that Google asked on their interviews. I don't know if they still ask it. They probably still do.
[00:10:34] Which probably means I'm gonna get a lawsuit by the time I go home. That's fine, I don't care. But a lot of these questions kind of like to tie all these things in together, which I think is also useful for you to know.