Learning Objectives

• Practice data parsing and multi-dimensional lists in Python
• Introduce multi-dimensional data visualization using matplotlib
• Explore two time-sensitive computational models (Cellular Automata and Flood Fill)

Getting set up

This assignment is entirely doable inside Prairielearn, although the matplotlib version on Prairielearn is a bit outdated and will not produce an identical gif / a perfectly animated gif. You are strongly encouraged to run your animation code locally when completing part 3.

Assignment Description

Many very complex problems in the world can be approximated by modeling or approximating a phenomena using some manner of computational or mathematical rules. These rules do not exactly mirror reality but can offer fantastic insight into the underlying behavior or effects of changes to the system. For example, a model of a cell may have complex rules defining how different proteins are created and scientists may use this model to guess good targets for a disease or cancer. However they are merely predicting in silico while doing so and their drug may not work as intended or have unforeseen side-effects in the real world.

While many of these models are very advanced or rely on algorithms and data structures we have not yet discussed, a fundamental computational model can be created using only lists and a few simple rules. In this mini-project you will be tasked with coding up several key functions for a time-sensitive state machine that is built around a 2-dimensional matrix. In other words, you will be practicing your skills with lists and multi-dimensional lists while creating a tool you can (and will) apply to visualizing computational models!

Part 1: Fun with 2D Lists

emptyMatrix()

#INPUT:
# rows, an integer storing the number of rows in the matrix
# cols, an integer storing the number of columns in the matrix
#OUTPUT:
# A list of lists forming a 2D matrix containing zeros for every value
# The output must be either a numpy.ndarray or a built-in python nested list
def emptyMatrix(rows, cols):

The first required function, emptyMatrix(), should take as input a row and column number and produce a matrix of the appropriate dimensions with the integer value ‘0’ for every cell. Every row should have the same number of columns (defined by column number). So the shape will always be a rectangle. Your output can either be a numpy n-dimensional array (numpy.ndarray) or a built-in nested list (List[List[int]]).

Successfully implementing this function will produce an ‘empty’ gameboard that can be used to import values at the start of our computational modeling. It will also help you keep the ‘old’ matrix and the ‘new’ matrix distinct in both gol_update() and ff_update().

HINT: You can do this manually using the nested loop and nested list logic we’ve seen in class. However you are also allowed to use numpy, which has a number of useful methods in their list implementation, some of which we have also seen in class.

getSize()

#INPUT:
# matrix, a lists of lists forming a 2D matrix (using a built-in list)
#OUTPUT:
# A list of size 2 storing the number of rows at index 0 
# and the number of columns at index 1
def getSize(matrix):

Given a matrix input as a list of lists (not a numpy array!), return a list containing two elements. The number of rows should be at index 0 and the number of columns should be at index 1.

This function is not required to implement our models (there are built-in operations that can do this), but you should understand how to get these values when given an arbitrary matrix. It also incentivizes you to test the accuracy of your matrix sizes before you start doing complicated automata logic that will be difficult to debug.

HINT: Although the autograder will always give a built-in list as input, you can still use numpy helper methods. How might you convert a list from one type to another? Alternatively, this is also straightforward to write using built-in methods.

getTotalWeight()

#INPUT:
# matrix, a lists of lists forming a 2D matrix (using a built-in list)
#OUTPUT:
# A float storing the total non-negative numeric weight in the matrix.  
# For the Game of Life model this is simply the number of non-zero cells (as living cells have value 1 and there is no '-1' values)
# For the Flood Filling model, add the total volume of water but do not include the '-1' values for boundaries.
# NOTE: The same logic should work for both matrices, you just have to identify and ignore '-1' spaces
def getTotalWeight(matrix):

Given a matrix input as a list of lists (not a numpy array!), return the total non-negative numeric weight in the matrix. In other words, sum up every non-negative cell in your matrix and return that sum. You must ignore negative values and not include them in your sum! This is because negative values are only used in the Flood Fill model and they imply that there is an impassible water barrier, not a ‘-1’ volume of water.

This function is directly relevant for setting the color boundaries of our Flood Filling animation – we don’t want to visualize values on a 0 to 1 scale if (for example) we have 10000 ‘units’ of water! Likewise, if we have an equal amount of barriers as we have water, we don’t want our visualization to be on a scale from 0 to 0 hence we ignore the ‘-1’ value when computing our weight.

It is less relevant for the Game of Life model, as there are only 0s and 1s in that matrix, but still can tell us the number of living cells at any step in our model, which you might find useful for identifying the ‘most successful pattern’ in Part 3.

getMaxDif()

# INPUT:
# start_matrix, a 2D list of lists storing the starting state of a cellular automata (time step t)
# end_matrix,  2D list of lists storing the end state of a cellular automata (time step t+1)
# OUTPUT:
# A float storing the maximum difference in a single cell between the two matrices
# As there can be positive and negative differences, take the absolute value of the numeric difference
# **TIP:** abs() is the Python built-in for absolute value.
def getMaxDif(start_matrix, end_matrix):

Given two matrices as input (both passed in as a list of lists), return the maximum difference in magnitude in any one cell between the start and end matrix. In other words, you should compute the difference between (x,y) at time t and time t+1 for each (x,y) pair in your matrix and then return the maximum total difference. Make sure you take the absolute value of the numeric difference! For example:

start = [[10 5], [2 8]]
end = [[1 6], [9 8]]

• The differences at (0, 0) would be -9 (magnitude 9).
• The differences at (0, 1) would be 1.
• The differences at (1, 0) would be 7.
• The differences at (1, 1) would be 0.

The max difference is 9.

importValues()

#INPUT:
# matrix, a lists of lists forming a 2D matrix (using a built-in list)
# fName, a string fName storing the absolute path to a space-separated text file
#OUTPUT:
# None
# Instead set the input matrix to have all the same values as the input file.
# For each line in the file:
# If the input line has two arguments (x, y), you should assume the value at matrix[x][y]=1
# If the input line has three arguments (x, y, z), you should import the value as matrix[x][y]=z
# NOTE: If an input has an x- or y-coordinate larger than the matrix, it should be ignored
def importValues(matrix, fName):

The input data format for this project is a space-separated text file storing individual data points on each line. Your code should read in the input file by it’s filename, read each line, and add them to the input matrix. It is possible for the same data point to be in the file twice (and potentially with different values!). Your code should import from top to bottom of the file and overwrite the values if necessary. There are two allowable formats, both of which would be possible as input to this singular function.

If you read in a line with just two values, they are <row> <col> and it is implied that the value is 1. This is the case for data inputs to the Game of Life model, where every living cell is reported in the input file like this:

0 3
2 1

This tiny text files states that there are two live cells, one located row 0, column 3 in the matrix and the other located at row 2, column 1 in the matrix. Assuming the input matrix is an empty 3x4 matrix, importing would modify that matrix to have the values:

[[0. 0. 0. 1.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]]

If you read in a line with three values, they are <row> <col> <val>. This is the case for data inputs for the Flood Fill model, where squares have an initial water value that is gradually spread across all available cells. See part 2 for details about this model and the meaning behind its input values. For the purposes of importing, you should just set the given values at the given coordinates.

For example given the following input file:

3 3 10
3 4 -1
2 2 -1
2 3 -1

The output on a 5x5 matrix would be:

[[ 0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]
 [ 0.  0. -1. -1.  0.]
 [ 0.  0.  0. 10. -1.]
 [ 0.  0.  0.  0.  0.]]

WARNING: To receive full credit, your solution must be able to identify when an input pair would go out of bounds for a given input matrix. When this happens, you should ignore that particular point and continue parsing the list. For example if I have a 5x5 matrix:

-3 3
2 5

neither one of these pairs are valid. -3 is not in the bounds of our rows and 5 is not in the bounds of our columns (both of which go from 0 to 4).

TIP: It is easy to mix up or confuse (row, column) with (x, y) from more conventional plots. Point (0,0) as row, column is the top left corner. The provided workspace includes many example input / output for you to play around with. In particular, test your implementation by comparing your output to the given output for vertLine.txt and horizLine.txt to make sure you arent inverting things.

Part 2: Cellular Automata Models

Both of our computational models are Cellular Automata – a computational model defined with a matrix of values that evolves over time according to fixed rules. In both instances, you will be implementing the update function that takes as input a time t matrix and returns a time t+1 matrix. The input and output matrices are different! You should not edit the input matrix values in any way! Instead, you will define a brand new matrix of equal size (hint: do we have a function that can make a fixed size empty matrix?) and update the value in that matrix according to the values in the input matrix.

Game of Life

Cellular Automata refers to a large range of computational models built around a two-dimensional plane organized into ‘cells’ and rules that govern how these cells change over time. One of the more popular rulesets was created by mathematician John Conway in 1970 – ‘Conways Game of Life’. For the first part of your mini-project, you are tasked with implementing a number of key functions needed to load and visualize the Game of Life variant of Cellular automata.

gol_update() (The Game of Life Model)

#INPUT:
# A lists of lists forming a 2D matrix (using a built-in list)
#OUTPUT:
# A list of lists forming a 2D matrix.
# The output must be either a numpy.ndarray or a built-in python nested list
# The matrix should be the same dimensions as the input and be the next timestamp of the matrix
# using the Game of Life rules. Your logic should consider indices past matrix boundaries 'empty'.
# NOTE: You should return a deep copy of the matrix, not a shallow one!
# In other words, do not change or return the original matrix
def gol_update(matrix):

The Game of Life model is a finite matrix of cells with four rules that define how the matrix changes with each time step:

1. Any live cell with fewer than two live neighbours dies. (Underpopulation)
2. Any live cell with two or three live neighbors lives.
3. Any live cell with more than three live neighbours dies. (Overpopulation)
4. Any dead cells with exactly three live neighbours becomes a live cell. (Reproduction)

When writing this function, consider carefully the following suggested sub-problems:

• What is the value of my specific (x, y) cell? [Note that living and dead cells have different rules!]
• How many neighbors does my specific (x, y) cell have? [How can I search a matrix for specific coordinate values?]
• What is the sum of values of all my neighbors? [How can I compute the sum for each cell in a matrix?]
• Using the above information, what is the state of my cell in the next timestep?

While most conventional models fake an infinite grid by connecting the top and bottom as well as the left and right edges, our implementation will instead always consider those edges to be empty. Despite this, we can still see a number of interesting behaviors, including infinite patterns and patterns which will gradually move off our finite grid.

TIP: The autograder will tell you when you have a specific cell value out of place along with the timestamp it is occuring. However you may find it more helpful to visually debug against some some pre-generated examples (which can be found in the output directory).

ff_update() (The FloodFill Model)

One very important real-world use for cellular automata models is generating fast flood models for predicting flood risk for different terrains. Cellular Automata is an excellent tool here for reducing the computational complexity of such studies to something that can be easily modeled at scale. However even the ‘simplified’ cellular automata approaches produced in recent years are a bit too complicated for our use. Instead we will use a very simplified model, which we will call Flood Filling.

In our Flood Fill model, each cell contains a numerical value of water (or is a barrier to water with a ‘weight’ of -1). The rules for updating the matrix are as follows:

1. Any barrier space (value = -1) persists forever. (Any position with value -1 should stay -1 in the next timestep)
2. For all other cells, the next timestep’s water value is the sum of the outgoing water from itself and its neighbors (A max of five: Up, Down, Left, Right, and itself).

To do this calculation, each square must first count the number of its neighbors which are valid – that is to say not barriers and not the edge of the matrix. Once that value is computed (it will always be a value from 1 to 5), that square should pass an equal amount of its water to every valid neighbor (as well as itself). Unlike the Game of Life model, we will only look in the four cardinal directions so water will only spread up, down, left, and right ( as well as stay in its current square).

When writing this function, consider carefully the following suggested sub-problems:

• What is the value of my specific (x, y) cell? [Barrier cells should remain -1 for all iterations; cells with no water don’t spread water but may accept water]
• How many neighbors does my specific (x, y) cell have? [Remember that the floodfill model does not look at diagonal neighbors!]
• How much water is spread to my neighbors? [Remember that water is equally spread between the cell itself and its neighbors!]
• Using the above information, what is the state of my cell in the next timestep? [Note that unlike Game of Life, my final value depends on potentially more than one cell’s calculation!]

To elaborate on the final point above lets look at a specific timestep calculation for a very tiny Floodfill matrix! For convenience each cell has been labeled:

A=6 B=0
C=3 D=9

Given the above matrix and our boundary conditions, each square splits its water across three cells as each has two valid neighbors (and two matrix boundary neighbors):

1. Cell A sends 6/3 = 2 water to A, B, and C each [in the next time step].
2. Cell B sends 0/3 = 0 water to A, B, and D each [in the next time step].
3. Cell C sends 3/3 = 1 water to A, C, and D each [in the next time step].
4. Cell D sends 9/3 = 3 water to B, C, and D each [in the next time step].

So the output of this sum is:

A=3 B=5
C=6 D=4

Be sure that when you update the cell that you are properly summing the value in the next time step, not overwriting the amount of water!

TIP: When calculating the update for the Flood Fill model, you should create a new empty matrix and sum all ‘outgoing’ water for each space, including from the square to itself. At no point should you be subtracting water.

timeWaterHit()

# INPUT:
# matrix, a 2D list of list storing the starting state of a cellular automata
# maxTime, an integer storing the maximum timestep of our Flood Fill model
# location, a list of two values (x, y) defining the point to watch for
# OUTPUT:
# The timestep (starting at t=0) where water first reaches the specific location
# If water never reaches that position, return -1
# **NOTE:** This function requires using ff_update() so you must pass that function first.
# **Warning:** This function should not modify the input matrix!
def timeWaterHit(matrix, maxTime, location):

Using your Flood Fill update rule and an input matrix, write a function which will identify the first time water touches a particular square (or returns -1 if no water will ever touch that square within maxTime iterations). Successful completion of this function will require using ff_update() to create all timesteps from t=0 to t=maxTime - 1. The location will be passed in as a 1D list storing a single 2D point ([x, y]) where the ‘x’ coordinate is the row and the ‘y’ coordinate is the column index for our matrix.

As a final function, this is one of many ways in which we could use our Cellular Automata to answering interesting questions. For those interested in a challenge, consider also exploring how long it would take your solution to reach a ‘steady state’, where the difference between time steps in your update matrix falls below some fixed value (such as 0.01).

Part 3: Creative Automata

For the final part of the mini-project, write your own starting state for both Game of Life and Flood Fill matrices and submit both this state and your visualization of that state on Prairielearn. Credit will be awarded for successful submission of a unique gif (and matching starting point). Your submissions must meet the following criteria:

• Your gifs should both be at least 20 frames in length
• Your gifs should visibly change during the course of the gif. This means that your Game of Life input should evolve through a (non-empty) pattern and have at least one living cell in each frame for the full animation. Your Flood Fill model should likewise demonstrate visible diffusion of water from at least one water source in each frame.
• Your Game of Life matrix must be at least a 25 x 25 grid. Your Flood Fill should be at least a 10 x 10 grid (but is not required to be larger). Be warned that FloodFill text writing will start to overlap if you make too large of a FloodFill gif! If you choose to make a large FloodFill simulation, you will have to change the animation code yourself to reduce the text size.