Hello, and welcome to the sixth Software Carpentry lecture on program design using invasion percolation as an example. In this episode, we'll look at how we resolve ties between cells that are on the boundary.
This diagram shows the problem we face. Three cells next to the filled region are tied equal for having the lowest value.
Our specification says we're supposed to choose one at random…
…but how do we keep track of the cells we're supposed to be choosing from?
We're going to use a set of tuples. Each tuple will be the (x,y) coordinates of one cell that's on the boundary that has the current lowest value.
So of course we'll have to record the current lowest value that we've seen as well.
There will be three cases to consider every time we look at a new cell.
Case 1: its value is greater than the minimum we've seen so far, in which case we can ignore it, because we know there are better cells elsewhere.
Case 2: the value of the new cell is equal to the current minimum. In this case, we add the new cell's (x,y) coordinates to the set.
Case 3: the new value is less than the current minimum. In this case, we replace all the coordinates that are currently in the set with the coordinates of the new cell, and re-set our minimum to be this new value.
An example will make this clearer. Before we start looking at cells, we set min_val equal to 11, which is one greater than the maximum possible value that could be in the grid, and we set min_set to be the empty set, because we haven't look at any cells yet.
We then take a look at our first cell. Its value is less than min_val, so we re-set min_val to 4 (the value of the cell), and we put the coordinates of this cell (in this case, X equals 12, Y equals 23) into the set.
We look at the next cell. Its value is greater than the currently known minimum value, so we ignore it.
The next cell is tied equal for the minimum value, so we add its coordinates—in this case, (11,22)—to our set.
The next cell is greater than the minimum value, so we ignore it.
Then we see a cell whose value is less than the minimum value we've seen previously, so we throw out all of the coordinates we've saved in the set, and put the coordinates of this cell into the set in their place.
Finally, the last cell we look at ties equal for minimum value, so we add its coordinates to the set.
Here's the code that implements that—we'll step through it line by line.
We start by setting min_val to one greater than the range of random values that could legally appear in the grid. This way we know that the very first cell we look at will have a value less than the minimum we've seen so far.
We then initialize our set of coordinates to be empty because we haven't actually looked at any cells yet.
Now, inside the loop, if the cell is a neighbor of the filled region, there are three cases to consider.
In the first case, where the value is greater than the minimum seen so far, we do nothing…
…because there's nothing to do.
In Case 2, the value of the cell we're looking at ties with the minimum value seen so far, so we add the coordinates of this cell to the set.
Finally, in case 3, we've got a new minimum value, so we record that minimum value, and put the coordinates of this cell into the set.
This third case automatically runs the first time we look at any actual cell because we've initialized min_val to be one greater than the maximum possible value in the grid.
Finally, once we've got the set of candidate cells, we're going to use the random library to pick one. We import the choice function from the random library…
…and check that the set actually has something in it (because if there are no cells in the set when we finish our loop, then something's gone wrong with our program).
We convert the set to a list, because the random choice function requires an argument that can be indexed…
…and then we call that function to choose one element from the list of neighboring cells.
Thank you.