Implementation of these function are done in a1_partd.py

def get_overflow_list(grid):

 

This function is passed a grid (2D array) of numbers and returns a list of 2 valued tuples (see below). You may assume the grid is rectangular (no need to test if each row has same length as the other rows). Each cell within the grid has a number of "neighbours". The neighbours are cells that are beside a cell either vertically or horizontally. Thus:

cells in the corners of the grid have exactly two neighbours
other cells at edge of grid have exactly 3 neighbours
cells that are not on the outside have exactly 4 neighbours
Each cell is defined by a row and column, indexed from 0. Thus, the top left corner is row 0, column 0, and the bottom right corner is indexed (number of rows-1, number of columns-1)

The ascii picture below shows the number of neighbours each cell contains on a 4 X 5 grid:

|-----|-----|-----|-----|-----|
|  2  |  3  |  3  |  3  |  2  |
|-----|-----|-----|-----|-----|
|  3  |  4  |  4  |  4  |  3  |
|-----|-----|-----|-----|-----|
|  3  |  4  |  4  |  4  |  3  |
|-----|-----|-----|-----|-----|
|  2  |  3  |  3  |  3  |  2  |
|-----|-----|-----|-----|-----|

 

The number of neighbours contained within a cell define when a cell will overflow.

The grid of numbers passed to this function can be positive, negative or zero. The absolute value of these numbers represent the number of items within each cell.

This function returns a list of tuples (row,col) indicating all the cells that will overflow. A cell will overflow if a cell has as at least as many items as neighbours. If there are no cells that will overflow, function returns None

Example 1

For example, given the following grid:

|-----|-----|-----|-----|-----|
|  2  |  0  |  0  |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  | -3  |  0  |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  0  |  -2 |  0  |  0  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  0  |  0  |  3  |
|-----|-----|-----|-----|-----|

 

Given the above grid, the function would return the following list

[(0,0), (3,4)]. This is because both the top left and bottom right cells contain cells that are greater than or equal to the number of neighbours

Example 2

For example, given the following grid:

|-----|-----|-----|-----|-----|
|  -2 |  0  |  2  |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  | -4  |  0  |  -5 |  0  |
|-----|-----|-----|-----|-----|
|  0  |  0  |  -2 |  0  |  1  |
|-----|-----|-----|-----|-----|
|  -2 |  0  |  0  |  0  |  1  |
|-----|-----|-----|-----|-----|

 

Given the above grid, the function would return the following list

[(0,0), (1,1), (1,3), (3,0)]. the two corner cells with -2, as well as the cells with -4 and -5 have all reached or exceeded the capacity for their cells, so their locations are part of the result list.

def overflow(grid, a_queue):

 

This function must be written recursively. An iterative solution will not be accepted and subject to resubmission with penalty

This function is passed a grid of numbers and an instance of the Queue data structure from part C. The absolute value of the numbers within each cell represent the number of items within a cell. If the grid contains one or more cells that are overflowing, a new grid is created based on the following rules and added to the queue:

you may assume that all overflowing cells will have the same sign (either all positive or all negative)
any cell that is overflowing becomes empty (assigned 0)
every neighbour of an overflowing cell gets one extra item
every neighbour of an overflowing cell takes on the same sign as the overflowing cell (ie overflowing cell "takes over" its neighbours if they were not the same sign)
all overflowing cells overflow at the same time to form the next grid
this process continues until the grid does not contain any overflowing cells.

This function returns number of grids added to the queue. Note, this is not necessarily the same as the number length of the queue as the queue does not have to be initially empty.

Example 1:

Suppose you are given the following:

|-----|-----|-----|-----|-----|
|  -2 |  2  |  -3 |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  | -4  |  0  |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  0  |  3  |  0  |  1  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  0  |  0  |  1  |
|-----|-----|-----|-----|-----|

cells with -2, -3, and -4 are all overflowing
 

All overflows happen at the same time resulting in the following:

|-----|-----|-----|-----|-----|
|  0  |  -5 |  0  |  -1 |  0  |
|-----|-----|-----|-----|-----|
|  -2 |  0  |  -2 |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  -1 |  3  |  0  |  1  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  0  |  0  |  1  |
|-----|-----|-----|-----|-----|

All 3 of the overflowing cells become empty and spread.

Cell [0,1] with the -5 became -5 because it had 3 overflowing neighbours that added 1 item to that cell, it became negative because the overflowing neighbours were negative

Cell [1,0] and [1,2] -2 because it had 2 overflowing neighbours

Cell [2,1] and [0,3] became -1 because it had 1 overflowing neighbour

This grid is added to the queue

but.. not done as cell [0,1] is will overflow
 

after it overflows we get:

|-----|-----|-----|-----|-----|
|  -1 |  0  |  -1 |  -1 |  0  |
|-----|-----|-----|-----|-----|
|  -2 |  -1 |  -2 |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  -1 |  3  |  0  |  1  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  0  |  0  |  1  |
|-----|-----|-----|-----|-----|

overflowing cell become empty and spread.


Cell [0,0] [0,2] and [1,1] became -1 because it had 1 overflowing neighbour


This grid is added to the queue


 

Above grid is done, no cells are at overflow. function returns 2

Example 2:

When 2 side by side cells are set to overflow, they both overflow at the same time. This means that they both become empty (0) and both gain one from their overflowing neighbour:


|-----|-----|-----|-----|-----|
|  -1 |  0  |  -1 |  -1 |  0  |
|-----|-----|-----|-----|-----|
|  -1 |  4  |  4  |  0  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  -1 |  3  |  0  |  1  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  0  |  0  |  1  |
|-----|-----|-----|-----|-----|

both cells with 4 are set to overflow

 

result:

|-----|-----|-----|-----|-----|
|  -1 |  1  |  2  |  -1 |  0  |
|-----|-----|-----|-----|-----|
|  2  |  1  |  1  |  1  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  2  |  4  |  0  |  1  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  0  |  0  |  1  |
|-----|-----|-----|-----|-----|


The two cells with 4 became 0 at the same time, then each of them gained 1 from their neighbour that use to have 4
 

But we are not done as there is another cell with 4, so we will have to overflow that cell

|-----|-----|-----|-----|-----|
|  -1 |  1  |  2  |  -1 |  0  |
|-----|-----|-----|-----|-----|
|  2  |  1  |  2  |  1  |  0  |
|-----|-----|-----|-----|-----|
|  0  |  3  |  0  |  1  |  1  |
|-----|-----|-----|-----|-----|
|  -1 |  0  |  1  |  0  |  1  |
|-----|-----|-----|-----|-----|


The cell with 4 becomes 0 and each of it's neighbour gains 1 item