Please read this document very carefully.  Follow instructions exactly. If you have any questions please post them to the MS Team’s channel A2.

This assignment is due March. 17th, by 10:00pm

In addition to basic coding skills, this assignment will focus on loops and lists.

Consider a section of the Earth’s surface from a birds-eye-view. The elevation may vary greatly across this section. See the Figures below as an example. If one were interested in analysing this area based on elevation, one could represent the section of Earth as a grid (list of lists) of numerical values, where each cell of the grid would indicate the elevation of the Earth at that particular location. For example, an area the size of 1 square kilometer of Earth could be encoded as a 1000x1000 matrix, where each cell is the elevation of a single square meter; here, the value at cell (500,500) of the grid, would be the elevation at approximately the middle of the original 1 square kilometer section.

For this assignment, you will implement several functions which will allow someone with such a grid of values to perform meaningful analysis on the area of the Earth’s surface the grid represents. You are given a file, assignment2 .py, with 5 incomplete functions.  For this assignment, you’re required to complete these functions. A description regarding the intended behaviour of these functions is given later in this document. Further documentation and examples for these functions are given in the docstrings within the starter code: assignment2 .py.

For the purposes of this assignment we will use the following definitions.

1.  An elevation map  is of the type List[List[int]], and moreover, the length of an elevation map equals the length of all elements within the elevation map.  An elevation map will only contain positive numbers. An example of an elevation map is:

valid map  =  [[1,2,3],[4,5,6],[7,8,9]]

It may be more intuitive to view the map as:

valid map  =  [[1,2,3],

.                        [4,5,6],

.                        [7,8,9]]

The following two examples are not elevation maps (note the length of all the lists in each):

invalid map1  =  [[1,2,3],[4,5],[6,7,8,9]]

invalid map2  =  [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

2.  A cell is of the type List[int] and has a length of 2. All values in a cell will be greater than or equal to 0. Within an elevation map m, we say cell [i, j] as a shorthand for m[i][j]. We also say cell [i, j] is adjacent to cell [n, m] if and only if [n, m] equals one of:

[i + 1, j + 1], [i + 1, j], [i + 1, j − 1], [i, j − 1], [i, j + 1], [i − 1, j + 1], [i − 1, j], or [i − 1, j − 1].

3. Within an elevation map m, cell [i, j] is a sink if for all adjacent cells [n, m], m[i][j] ≤ m[n][m]. With the physical interpretation of an elevation map in mind, water would collect in sinks, since there is no less elevated area in the immediate vicinity for the water to flow to.

Functions

You are required to implement all of the functions below.   Pay attention to parameters of each function, for example, if it is said an input will be an elevation map, you can trust your function will never be tested on input which isn’t an elevation map. For further examples of how these functions are intended to operate, view the docstrings of the starter code for this assignment.

1. get average elevation(List[List[int]])  ->  float

The first parameter is an elevation map, m. Returns the average elevation across all the land in m.

2.  find peak(List[List[int]])  ->  List[int]

The first parameter is an elevation map,  m.   Returns the cell which contains the highest elevation point in m.  For the purposes of us testing this function, you may assume that all values of m are unique (no two locations have equal elevations).

3.  is sink(List[List[int]],  List[int])  ->  bool

The first parameter is an elevation map, m, the second parameter is a cell, c.  Returns True if and only if c is a sink in m.   Note if c does not exist in m  (the values are outside m’s dimensions), this function returns False. See the previous section for the definition of a sink.

4.  find local sink(List[List[int]],  List[int])  ->  List[int]

The first parameter is an elevation map, m, the second parameter is a cell, c, which exists in m. Returns the local sink of c. A local sink of c is the cell which water would flow to if it started at c.  Assume if the current location isn’t a sink, water will always flow to the adjacent cell with the lowest elevation.  You may also assume for the purposes of us testing this function, that all values of m are unique (no two locations have equal elevations). See the docstring for some examples.

5.  can hike to(List[List[int]],  List[int],  List[int],  int)  ->  bool

The first parameter is an elevation map, m, the second is start cell, s which exists in m, the third is a destination cell, d, which exists in m, and the forth is the amount of available supplies. Under the interpretation that the top of the elevation map is north, you may assume that d is to the south-east of s (this means it could also be directly south, or directly east).  The idea is, if a hiker started at s with a given amount of supplies could they reach f if they used the following strategy. The hiker looks at the cell directly to the south and the cell directly to the east, and then travels to the cell with the lower change in elevation. They keep repeating this stratagem until they reach d (return True) or they run out of supplies (return False). Assume to move from one cell to another takes an amount of supplies equal to the change in elevation between the cells. See the docstring for some examples. If the change in elevation is the same between going East and going South, the hiker will always go East. Also, the hiker will never choose to travel South, or East of d (they won’t overshoot their destination).  That is, if d is directly to the East of them, they will only travel East, and if d is directly South, they will only travel South.

Submitting and Grading

This assignment will be submitted electronically via Avenue.  Your submitted file must have the name assignment2 .py, or you may receive 0.