 |
Welcome to the fifth episode of the Software Carpentry lecture on program design using invasion percolation as an example. In this episode, we’ll take a look at how we find the neighbors of a cell. |
 |
If you recall, we need to find the neighbors of cells that have already been marked as being filled with pollution. |
 |
Those cells have been given the value -1. |
 |
The blue cell shown here is a neighbor of the filled region if any of the green cells have already been given the value -1. |
 |
Those cells have coordinates that are +1 or -1 on either the X or the Y axis from the coordinates of the blue cell. |
 |
We’re not looking at the cells that are on the diagonals, at (x-1, y+1) and so forth. |
 |
We should check the science on this, but again, it’s a simplifying assumption that’s safe to make in the first version of our program. |
 |
Here’s a piece of code that tests to see whether a cell is a candidate for being filled in. This version is buggy. For x in range(N), and for y in range(N), if the cell to our left is filled, or the cell to our right is filled, or the cell below us is filled, or the cell above us is filled, then this cell is a candidate for filling. |
 |
This code is buggy because it doesn’t take into account what happens at the edges. |
 |
If we take x equals 0 and subtract 1, we get an X coordinate of -1. In Python, that means the last cell in the row. That will wrap around to the far edge, which is definitely not what we want. |
 |
The situation on the other border is even worse. If we’re at the right-hand edge, and we add one to the X coordinate, we actually fall off the end of the list and get an out-of-bounds exception. |
 |
Here’s another version of the code that tests for this. For x in range(N), for y in range(N), if x is greater than 0, i.e., if we’re not on the left edge, then we check to see if the cell to our left is filled. If it is, then this cell is a candidate for filling. We then repeat this double test for each of the other directions. |
 |
The problem with this is that it means a lot of repeated code, and code that is repeated in two or more places will eventually be wrong in at least one. |
 |
Here’s a third version that’s good enough for production. We’re going to combine the two tests in each direction using an and. So, if x is greater than 0 and the cell to our left is filled, or if x is less than N-1 and the cell to our right is filled, and so forth, then this cell is a candidate for filling. |
 |
Why does this work? Well, the first half of each test checks to make sure that the second half can safely be run. If we are not on the left edge… |
 |
…then we can take a look to the left to see if that cell is filled. |
 |
and in Python (and in most other modern programming languages) does short-circuit evaluation—it only tests the second part if the first part is true. |
 |
This is the general pattern. When you need to do a sanity check before you can safely execute some other test, the idiom is “If sanity check and some other test”. The and ensures that if the sanity check fails, i.e., if it is False, then the other test is never even executed, because as soon as and knows that one side is False, it doesn’t need to test the other, because False and anything is False. |
 |
|
