[MUSIC] Well, welcome to class, in this lecture we're going to talk about grids. Now, a grid is just a partition of a 2D region into a collection of disjoint cells. That sounds really mathematic, but you have lots of experience with grids. You play games a lot, the games you're going to look at in this class, a lot of them are played on grids. 2048, it's a grid of square tiles. Tic-Tac-Toe, it's played on a three by three grid. Your last project, the 15 puzzle, again a four by four grid of squares. We'll even build a simulation for how zombies behave. And it's going to again, work on a square grid. In this lecture, I'm going to talk a little bit about the terminology we're going to use to work with grids. And then I'll show you a very simple example of some code that works with grids. This should be helpful when you have to implement the second part of 2048. All right, let's talk more about some of the terminology that we use with grids. So, in this class we're going to work exclusively with rectangular grids that are composed entirely of squares. So we'll talk about a grid of a particular size. We'll say something like a three by four grid. And what that means is it's a grid that's three cells high by four cells wide. I built a program that kind of shows an example of a grid of a particular size. In Code Sculpture, you can hit this link here. And I've actually run it and here's an example of a grid that is six cells high by nine cells wide. Now, something that we'll do often in this class is we'll want to work with an individual cell in the grid. The way we'll do that is we'll actually refer to a particular cell by a pair of integer indices. So, what's the numbering scheme we're going to use for our grids? It's going to look very similar to the numbering scheme you might have seen from matrices. If you've ever done linear algebra, it's a rectangular array of numbers. And the way matrices and indices are indexed by rows and by columns. So the first index indicates a row and the second index inditate, indicates a particular column. So for example here, the element 3,2 corresponds to a cell which is on the 0, 1, 2, 3 row, and the 0, 1, 2 column. Now the key difference here is we're indexing things starting at 0, and matrices, you will always start at 1. And that's because we're using python and python loves to start things at 0. So what I want to do next is I want to show you a little bit of code that's going to allow us to work with grids and do a few interesting things, these are things that you'll have to do in the 2048 project. Okay. I've built some code that creates and works with a grid. Now this is going to give you an idea about how we actually, tangibly work with grids inside Python. So spend a few minutes to understand this. This will help you when you're working on your mini projects in this class. To begin with, we've defined, we're defining a grid who's height is 4 and who's width is 6, this is going to be a rectangular grid, it's going to have square cells. This statement right here is probably the most important one in the whole program, it's actually creating the grid in a single line and the way we're doing this is we're representing a little grid as a list of lists. And we're building this list of lists using a nested list comprehension. So that's what's going over, going in here on the right-hand side of this statement. 'Kay. In particular, take a look at this expression right here. This is a list comprehension reiterating over the width of the grid and we're building a list who's length is GRID_WIDTH. Now, the outer comprehension is taking all, each of those lists of length GRID_WIDTH and spilling a new list of size GRID_HEIGHT. So we're really building a list of lists here when we're actually representing our grid. Okay, we've built a grid. Now, let's do something with that grid. So, what I've implemented here is a function called traverse_grid that walks through that grid and picks out a subset of the cells. In fact, it behaves in a way very similar to what you'll need to do for 2048. In 2048, when you hit an arrow key, what you'll need to do is, you need to apply your merge function to a collection of cells that either correspond to a row or a column. Instead of writing a separate piece of code for a row, and another piece of code for a column, what I want to show you is how we can do this with a single function. So traverse_grid is going to take a starting cell, so a place where we're going to start walking from. Okay, and that's going to correspond to kind of a component that's a row and a column. And it's going to give me a direction, and that direction is going to have two numbers, it's going to be a two bull, it's going to correspond to how much we should move in the first component, that corresponds to row. And then, how much we should move in the second and that corresponds to how much we should move in a column. And notice those numbers can both be non-zeros so we could actually move diagonally and then this last premise should be the number of cells that we need to actually pick off. So the code is really straightforward. It's sitting right down here, it's a loop, it just iterates through the number of steps and we need to compute the row and the column of a particular cell we want to, want to actually look at for a given step. And the way we do it is we take the first component of the starting cell and we add to it the step number times the first component of the direction. To get the new column, same thing. We take the second component of the starting cell, this column index and we multiply the step times the second component of the direction. Kind of how we want to stride in the second coordinate. And then I have some print statements down here which actually print out what we've, what we're looking at inside this example grid. And notice here, we're always storing in the example grid just a sum of the indices. So, then, next, let's go out and actually look at some examples of how we can use this to strive through the grid. Okay, to finish up, I've written a function here which actually runs some examples. So the first thing I've done here is I have written some code that actually just prints out what the grid looks like. So over here you can see the values that are stored in the grid. Notice it's just the sum of the row and the column index for each particular entry. You might look at this code if you're trying to print out the values in a particular bridge you're working with on one of your mini projects. The next four chunks of code here actually just called traverse_grid with various parameters. So, to kind of help you visualize what's going on, I've got a little picture here of a four by six grid that I've made with my code from the previous notes. And what I'd like to do is, I'd like to print out the indices of the first row in this grid. So we're, this first row would be row 0. So it'd be like we had 0,0, 0,1, 0,2, 0,3, 0,4 and 0,5. So the starting cell should be 0,0, and the direction should be that we're going to, essentially, leave the, the first entry alone. So it's going to be 0 and then we should like to stride in the second entry. 'Kay? That means the value of 1 and we're going to go with the GRID_WIDTH here. So if you see that, it's actually printing out over here, 0,0, 0,1, 0,2, 0,3, 0,4, 0,5. Okay, let's try to print out the second column. So that would be 0,1, 1,1, 2,1, 3,1. So the starting entry would be 0,1. And the direction would be, well let's see, we want to increment the first component by one and leave the second component alone. So 1,0. What if we wanted to actually do this second row in reversed order? Well, what we want to do is, we would want to print out 3,1, 2,1, 1,1, 0,1. And so to do that, we would start at 3,1. That's this value right here. And then we'd like to decrement the first component each time we stride. So that would give us a direction of minus 1,0. And even more importantly, if we'd like to do something where you move diagonally, we could go through and say, start at 0,0. Hit 1,1, 2,2 and 3,3 so start value would be 0,0 and the direction would be 1,1. So notice, with a really small piece of code, I've managed to build something that can kind of iterate through a linear sequence of cells in the grid without much difficulty. So, think about this when you are writing your code for the full version of 2048, try to avoid lot's of code duplication. And try to use an approach similar to what I'm talking about here. I'll see you next lecture.
