Code a depth-first search in Python - Python Tutorial

- [Instructor] We are now going to code out a version of depth-first search in Python. Our implementation makes use of some helper functions and values that we've provided in a separate file and which we will import into our DFS file. Let's briefly look at helper functions dot py. So, this is chapter 04_04. So we'll go into that folder and have a look at helpers.py. So what have we got here? We got offsets. These are just quick ways of referencing relative positions within our maze. So, if you think in terms of the row and column coordinates, going right means going zero up and down, but one to the right. And going left means going zero up or down, but going negative one to the right, which is the same as going one to the left. And then going up means decreasing the row number, but leaving the column number constant. And going down means increasing the row number, but leaving the column number constant. And then we have exactly the same read_maze function, which we looked at earlier on in the context of reading a 2d maze into our list. And then just two more functions. So one is, is_legal_pos. This is checking whether a given position is actually on the maze that we have, and also whether it's not a obstacle symbol. And finally, we have a function called get_path, starting on line 40. And what this does is it takes you through the predecessors. So you give it a start position, and a goal position, and a list of predecessors, and it will work backwards, working out what the predecessor of each node is until you get the path and then it reverses that and returns it. And you'll see that in action later. So that's our helper functions. Now, let's open up dfs.py. And I like to move the main file that I'm working on at any given point to the right hand side of my various tabs. It just means that I can go to it quickly without having to search through what's up there. That's by no means essential. That's just part of my workflow. So then, what we've given you here is some template code. So, we've given you a header describing what the file does. We've got our imports and they're hidden at the moment, but let's quickly look at them. So from helpers, we're importing all those functions that we need by name. And then we also have from stack import Stack. So stack is the stack that we actually wrote together earlier on. And by doing it like this, by doing from stack import Stack, that means we can actually just use the name stack rather than stack.Stack. And that will make sense later on. And the minute, is grayed out because we're not using it. And then we also have some tests. Now, I've used some assert statements here, which you may or may not be familiar with. Assert statements are just a very, very useful way of testing your code. If an assert statement is correct, then nothing at all will happen. However, if it's not correct, you'll get an assertion error. So on line 22, for example, when I assert that the result is this, I'm saying, this is the path here, 0, 0, 1, 0, 2, 0, 2, 1, 2, 2. If it turns out that that's not the path that gets returned by my function, I'll get an assertion error. But if my function does return this result, then absolutely nothing will happen. So, this is a very, very basic way of getting into testing and test-driven development. Don't worry about it too much. If it confuses you at all, you can replace this with print statements. You can literally say print result and then check that the output is the same as what you think it should be. So, yeah, we've got some tests there, and we'll see how those work in a moment. So, let's start writing our code. So, line 13 is pass, which isn't going to do much, but it prevents the code from producing an error when I run it. So we're now going to actually start coding depth-first search. We have a stack and it's equal to a Stack, with a capital S. And then onto our stack, we push our start position. Now, I should emphasize here that, as I said in line five in the comment, that these positions are all in the form of tuples, containing a row number and a column number. So they're row column tuples. Now, tuples, if you don't know them, it's just a list that can't be changed. It is immutable list, in this case, with two items. And it's just the way that we're storing all of our coordinates referencing maze cells throughout this whole project. So, we push start onto our stack. And then also predecessors is a dictionary containing just one item, which is start whose predecessor is None. So, that's the initial configuration. And then we have this algorithm. So, while not stack.is_empty. So while the stack isn't empty, that's what that means, then we're going to go through this routine. We're going to do current_cell is equal to stack.pop. And so that means getting the top item off of our stack. And then if the current_cell is equal to our goal, then we're done. Okay, so at that point, we can, notice it's red there, because I've done a single equals. It's a very common mistake to make, watch out for it, 'cause I'm doing comparisons on double equals. So, if that is the goal, then I return at that point. And what I return is get_path. So that's the path generated by this function when it's past predecessors, and the same start and goal_pos that I passed in on line 12 to my function. So that's the case where we find the goal and that's fine. However, if we don't find the goal, then for each direction, so for direction in, right, So, we've got these directions, up, right, down, and left. Now, you could change this, or whatever, but let's keep it like this for now. And just to remind you that these are coming from our helpers file. Okay, so that's our offsets. So, for direction in that list, we will do row_offsets. So row_offset and col_offset will be equal to offsets, and we're going to take the direction. So the offset for the given direction from that list of offsets that we just imported from our helper file. Okay, so this is going to unpack both of those values into row_offset and col_offset. Then, neighbour, that's my English spelling of that word. It's a hard habit to break. Neighbour is equal to current_cell zero. So that's the first of those, because remember, the cell is in the form of an i, j tuple, and we just want the i for this first one. So that's current_cell zero plus row_offset and then current_cell one, so that's the j, plus col_offset. And we'll talk about why this works in a moment. And then we say if is_legal_pos, within our maze. So that function takes the maze and the neighbour or the cell. So if that is a legal position and also it's not already in the predecessors. Okay, so remember in the algorithm, we say, we push undiscovered neighbours. So if it's in predecessors, that means it has been discovered. So we have to say, if it's not in predecessors, then at that point, and neighbour, and neighbour not in predecessors, then at that point, we will push. So we do stack.push. Then, we push on neighbour onto the stack and we'll also update our predecessors. So for that neighbour, we will set it equal to the current_cell. Okay, so, try and link what I'm doing here to what we did previously when we stepped through the algorithm in the grid tracer, it's a direct mapping between the two processes. If at that point, we haven't found our goal, then we go to this level and we return None. And looks like there's a spelling here, n-e-i, just add h. Okay, so, I'm just going to tidy up my code before I do anything else. So, Code, Reformat Code, so this will say any little errors with commas and things. And then let's run it and see what happens. Okay, so no errors. This is a good thing. And we get some output. And the reason we get that output is because in my second test, I have this for row in maze print row. That was just to give a visual idea of what the maze was looking like. Then the maze that's being worked with here is inside the mazes folder, mini_maze_dfs.txt. And it looks just like this then in the terminal. The first one is just an empty maze that we create by using a list comprehension. So that's the one that we did in the grid tracer app, just a three by three empty grid. And the last one is a position which is not on the maze, just checking that it does in fact return None, as it should. Okay, now you can add lots and lots more tests like this, and you should do actually, and you should try out some of the different mazes that we have in our mazes folder. Let's just go over what the algorithm is doing again. So we have a stack, starts off empty. We push onto it the start position. We have predecessors, which is a dictionary containing just the predecessor of that start position, which is None, because the initial position cannot have a predecessor. Then, we go into our main algorithm, which says, while the stack isn't empty, we get the current cell by popping. We check if it's the goal. If it is, then we will go and get the path then we return that path. And we're done. Otherwise, for every single direction in this list, we check the offsets, which we've imported from our helper file, and we assign the i, j values from that so that we can then check the neighbour. Okay, the whole point of this section is to be finding out the coordinates of the neighboring cells in all of those four directions. And then we say for each of those four directions, if it's a legal position and it isn't in the predecessors list, that means we haven't discovered it yet. So, we're going to push it onto our stack. And then finally, we pushed the neighbour onto the stack and update the predecessors. And we're done. Now, you have seen how to code depth-first search for a 2d maze in Python. I encourage you to try this algorithm out on several different mazes and do your best to understand exactly why the path returned is what it is. It may be helpful to add print statements at strategic places in the code, so you can see exactly what is happening at any given stage. Also, bear in mind that it can take some time to fully understand how this and the other algorithms from this course work. If you find yourself confused, I encourage you to be patient with yourself, rewatch the video on tracing DFS, try tracing the algorithm manually a few times for different mazes, and also try taking a break and coming back with fresh eyes. When I was learning this material myself, there were definitely times when I had to use some of these strategies. Of course, if you find that you understand easily, then that is great too.