In this assignment you will write functions that use lists and loops (including nested lists ad nested loops). You can do this assignment with only the concepts through Week 6 of PCRS. After completing this assignment, you will:
- Understand how data can be represented as a nested list.
- Understand how to create, navigate through, and mutate lists of numerical values.
In this assignment we will consider a section of the Earth’s surface. The figures below show an example section of the Earth from a bird’s-eye-view. The colours represent different elevations, notice how they vary greatly.
In this assignment, we are interested in analysing the elevation of a section of the Earth’s surface. We will represent the section of Earth as a square matrix of numerical values. A square matrix has equal dimensions: the number of rows is the same as the number of columns. Each value in the matrix corresponds to the elevation of the Earth at that particular location. For example, an area the size of 1 square kilometre of Earth could be encoded as a 1000x1000 matrix. Each cell of the matrix contains the elevation of a single square meter. Here, the value at cell [500, 500] of the matrix, would be the elevation at approximately the middle of the original 1 square kilometre section.
For this assignment, you will implement several functions which will allow someone with such a matrix of values to perform meaningful analysis of the Earth elevation data.
You may find the following figure useful in understanding the terminology below:
- elevation map: We will represent an elevation map in Python as a List[List[int]].
- An elevation map’s outer list and inner lists will be non-empty.
- An elevation map will be square. That is, the outer list List[List[int]] has the same length as each inner list List[List[int]], and the number of inner lists is equal to the length of the outer list. For example, in the figure above, the 3x3 elevation map is represented with a nested list of length 3, which contains 3 sub-lists, each of length 3.
- An elevation map will only contain positive integers.
An example of an elevation map is:
valid_map = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
You may find it more intuitive to view this elevation map as:
valid_map = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
The following examples are not elevation maps (note the lengths of all the lists in each list):
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]] invalid_map3 = []
- cell: We will represent a cell in Python as a list of 2 non-negative integers (List[int]). Given an elevation map m, we say “cell [i, j]” as a shorthand for m[i][j].
- adjacent cell: We will say that cell [i, j] is adjacent to cell [k, l] if and only if [k, l] 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].
- sink: Given an elevation map m, the cell [i, j] is a sink if m[i][j] [= m[k][l] for all adjacent cells [k, l]. 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. For example, in the elevation map below:
[[9, 6, 5, 6], [4, 5, 6, 8], [7, 2, 8, 1], [4, 3, 7, 1]]
cells [0, 2], [2, 1], [2, 3], and [3, 3] are sinks (and all other cells are not sinks).
Please download the Assignment 2 Files and extract the zip archive.
- Starter code: elevation.py
This file contains the header and the complete docstring (but not body!) for each of the functions you will write. Your job is to complete this file.
- Checker: a2_checker.py
We have provided a checker program that you should use to check your code. See below for more information about a2_checker.py.
In the starter code file elevation.py, complete the following function definitions. Use the Function Design Recipe that you have been learning in class. We have included the type contracts in the following table; please read through the table to understand how the functions will be used.
|Function name: (Parameter types) -> Return type||Full Description (paraphrase to get a proper docstring description)|
|compare_elevations_within_row: (List[List[int]], int, int) -> List[int]||The first parameter represents an elevation map. The second parameter represents a row number. The third parameter represents an elevation. This function must return a three-item list that contains three counts: the number of elevations that are less than, equal to, and greater than the given elevation, in the given row number of the given elevation map. You may assume that the given elevation map is valid, and that the given row number exists in the given elevation map.|
|update_elevation: (List[List[int]], List[int], List[int], int) -> None||The first parameter represents an elevation map, the second and third parameters represent cells in the elevation map, and the fourth parameter represents a change in elevation. This function must modify the given elevation map, so that the elevation of each cell between the two given cells, inclusive, changes by the given amount. You may assume that the given elevation map is valid and that the given cells appear in the same row or column (or both) in the elevation map. If they are in the same row, you may assume that the second argument’s column value is less than or equal to the third argument’s column value. Similarly, if they are in the same column, you may assume that the second argument’s row value is less than or equal to the third argument’s row value. You may also assume that the requested change in elevation will never cause an elevation to go below 1.|
|get_average_elevation: (List[List[int]]) -> float||The parameter represents an elevation map. The function must return the average elevation across all the cells in it. You may assume that the given elevation map is valid.|
|find_peak: (List[List[int]]) -> List[int]||The parameter represents an elevation map. This function must return the cell which contains the highest elevation point in the given map. You may assume the given elevation map is valid. You may assume that all values in the given map are unique (i.e., no two locations have equal elevations).|
|is_sink: (List[List[int]], List[int]) -> bool||The first parameter represents an elevation map. The second parameter represents a cell, which may or may not exist in the given elevation map. You may assume that the given elevation map is valid. The function must return True if and only if the given location is a sink in the given elevation map. Note: if the given location does not exist in the given elevation map (the cell values are outside the elevation map’s dimensions, so it is not a valid cell in the elevation map), this function must return False. See the Terminology section for the definition of a sink.|
|find_local_sink: (List[List[int]], List[int]) -> List[int]||The first parameter represents an elevation map. The second parameter represents a cell. You may assume that the given elevation map is valid and that the given cell exists in the elevation map. You may also assume that all values of the given elevation map are unique (i.e., no two locations have equal elevations). The function must return the local sink for the given cell. A local sink of a given cell is the cell to which the water from this cell will flow. Here we assume that if the given cell is not a sink, then water will always flow to the adjacent cell with the lowest elevation.|
|can_hike_to: (List[List[int]], List[int], List[int], int) -> bool||The first parameter represents an elevation map, the second represents a start cell, the third represents a destination cell, and the fourth represents the amount of available supplies. You may assume that the elevation map is valid, the start cell and the destination cell exist in the elevation map, and the amount of supplies is a non-negative integer. Under the interpretation that the top of the elevation map (row number 0) is North, you may assume that the destination cell is to the North-West of the start cell (this means it could also be directly North, or directly West). If a hiker started at the start cell with a given amount of supplies, could they reach the destination cell if they used the following strategy: The hiker looks at the cell directly to the North and the cell directly to the West, compares the elevation of the their current cell to each of those cells, and then travels to the cell with the smallest change in elevation. They keep repeating this strategy until they reach the destination cell (return True) or they run out of supplies (return False). Assume that to move from one cell to another takes an amount of supplies equal to the change in elevation between the cells. If the change in elevation is the same between going West and going North, the hiker will always go North. Also, the hiker will never choose to travel North or West of the destination (they won’t overshoot their destination). They will also not choose to travel in either direction if there is no cell in that direction (they won’t jump off the map). That is, if destination is directly to the West of them, they will only travel West, and if destination is directly North, they will only travel North. Look at the docstring for this function in the starter code for several examples.|
|get_lower_resolution: (List[List[int]]) -> List[List[int]]||The parameter represents an elevation map. You may assume the elevation map is valid. The function must return a new elevation map, which is constructed from the values of the given map by decreasing the number of elevation points within the map. To do this, the function views the map as a series of 2x2 entries and collapses the data into a single elevation point by taking the average of the four original points. When taking the average the function rounds down. Here are some example calls that illustrate the function’s behaviour. Note how the the function behaves in example (2), where the number of row/columns is odd.|
Your elevation.py file should contain the starter code, the implementations of the functions specified above, and any helper functions you may choose to define. elevation.py must not include any calls to the print and input functions. Do not add any import statements.
We are providing a checker module (a2_checker.py) that tests two things:
- whether your code follows the Python Style Guidelines, and
- whether your functions are named correctly, have the correct number of parameters, and return the correct types.
To run the checker, open a2_checker.py and run it. Note: the checker file should be in the same directory as your elevation.py, as provided in the starter code zip file. Be sure to scroll up to the top and read all messages.
If the checker passes for both style and types:
- Your code follows the style guidelines.
- Your function names, number of parameters, and return types match the assignment specification. This does not mean that your code works correctly in all situations. We will run a different set of tests on your code once you hand it in, so be sure to thoroughly test your code yourself before submitting.
If the checker fails, carefully read the message provided:
- It may have failed because your code did not follow the style guidelines. Review the error description(s) and fix the code style. Please see the PyTA documentation (Links to an external site.) for more information about errors.
- It may have failed because:
- you are missing one or more function,
- one or more of your functions is misnamed,
- one or more of your functions has the incorrect number or type of parameters, or
- one of more of your function return types does not match the assignment specification.
Read the error message to identify the problematic function, review the function specification in the handout, and fix your code.
Make sure the checker passes before submitting.
In addition to running the checker program on your own computer, run the checker on MarkUs as well. You will be able to run the checker program on MarkUs once every 12 hours (note: we may have to revert to every 24 hours if MarkUs has any issues handling every 12 hours). This can help to identify issues such as uploading the incorrect file.
First, submit your work on MarkUs. Next, click on the “Automated Testing” tab and then click on “Run Tests”. Wait for a minute or so, then refresh the webpage. Once the tests have finished running, you’ll see results for the Style Checker and Type Checker components of the checker program (see both the Automated Testing tab and results files under the Submissions tab). Note that these are not actually marks – just the checker results. If there are errors, edit your code, run the checker program again on your own machine to check that the problems are resolved, resubmit your assignment on MarkUs, and (if time permits) after the 24 hour period has elapsed, rerun the checker on MarkUs.
These are the aspects of your work that may be marked for A2:
- Coding style (20%):
- Make sure that you follow Python Style Guidelines that we have introduced and the Python coding conventions that we have been using throughout the semester. Although we don’t provide an exhaustive list of style rules, the checker tests for style are complete, so if your code passes the checker, then it will earn full marks for coding style with one exception: docstrings may be evaluated separately. For each occurrence of a For each occurrence of a PyTA (Links to an external site.) error, one mark (out of 20) deduction will be applied. For example, if a C0301 (line-too-long) error occurs 3 times, then 3 marks will be deducted.
- If you encounter PyTA error R0915 (too-many-statements), that indicates that your function is too long (more than 20 statements long). In that case, introduce helper functions to do some of the work – even if the helpers will only be called once. Your program should be broken down into functions, both to avoid repetitive code and to make the program easier to read.
- All functions, including helper functions, should have complete docstrings including preconditions when you think they are necessary.
- Also, your variable names and names of your helper functions should be meaningful. Your code should be as simple and clear as possible.
- Correctness (80%): Your functions should perform as specified. Correctness, as measured by our tests, will count for the largest single portion of your marks. Once your assignment is submitted, we will run additional tests not provided in the checker. Passing the checker does not mean that your code will earn full marks for correctness.
No remark requests will be accepted. A syntax error could result in a grade of 0 on the assignment. Before the deadline, you are responsible for running your code and the checker program to identify and resolve any errors that will prevent our tests from running.
The very last thing you do before submitting should be to run the checker program one last time. You should also run the checker program on MarkUs after submitting.
Otherwise, you could make a small error in your final changes before submitting that causes your code to receive zero for correctness.
Submit elevation.py on MarkUs by following the instructions on the course website. Remember that spelling of filenames, including case, counts: your file must be named exactly as above.