CSC108H Assignment 2
Deadline: Monday, November 1122:00Resubmission with 20 deduction optional but recommended: Wednesday, November 1322:00
Goals of this Assignment
In this assignment you will write functions that use lists and loops including nested lists ad nested loops. After completing this assignment, you will:
Understand how data can be represented as a nested list.
Understand how to create, navigate through, and mutate nested lists of numerical values.
Elevation Map Analysis
In this assignment we will consider a section of the Earths surface. The figures below show an example section of the Earth from a birdseyeview. 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 Earths 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 1000×1000 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.
Assignment Terminology
You may find the following figure useful in understanding the terminology below:
elevation map: We will represent an elevation map in Python as a ListListint.
An elevation maps outer list and inner lists will be nonempty.
An elevation map will be square. That is, the outer list ListListint has the same length as each inner list ListListint, and the number of inner lists is equal to the length of the outer list. For example, in the figure above, the 3×3 elevation map is represented with a nested list of length 3, which contains 3 sublists, each of length 3.
An elevation map will only contain positive integers.
An example of an elevation map is:validmap1, 2, 3, 4, 5, 6, 7, 8, 9You may find it more intuitive to view this elevation map as: validmap1, 2, 3,
4, 5, 6,
7, 8, 9The following examples are not elevation maps note the lengths of all the lists in each list: invalidmap11, 2, 3, 4, 5, 6, 7, 8, 9
invalidmap21, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
invalidmap3
cell: We will represent a cell in Python as a list of 2 nonnegative integers Listint. Given an elevation map m, we say cell i, j as a shorthand for mij.
adjacent cell: We will say that cell i, j is adjacent to cell k, l if and only if k, l equals one of: i1, j1, i1, j, i1, j1, i, j1, i, j1, i1, j1, i1, j, or i1, j1. Or, visually:
sink: Given an elevation map m, the cell i, j is a sink if mijmkl 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, 1cells 0, 2, 2, 1, 2, 3, and 3, 3 are sinks and all other cells are not sinks.
Files to Download
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: a2checker.py We have provided a checker program that you should use to check your code. See below for more information about a2checker.py.
What to do
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.
Functions to write for A2
Function name:
Parameter typesReturn type
Full Description paraphrase to get a proper docstring description
compareelevationswithinrow:
ListListint, int, intListint
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 threeitem 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.
For example, if the elevation map is
1, 2, 1,
4, 6, 5,
7, 8, 9
the row number is 1, and the elevation is 5, then the function should return the list 1, 1, 1, since there is 1 value that is smaller than 5, 1 value that is equal to 5, and 1 value that is larger than 5, in row number 1 in the elevation map the row 4, 6, 5.
updateelevation:
ListListint, Listint, Listint, intNone
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 arguments column value is less than or equal to the third arguments column value. Similarly, if they are in the same column, you may assume that the second arguments row value is less than or equal to the third arguments row value. You may also assume that the requested change in elevation will never cause an elevation to go below 1.
For example, if the elevation map is
1, 2, 1,
4, 6, 5,
7, 8, 9
the second argument is cell 1, 0, the third argument is cell 1, 1, and the change in elevation is 2, then the function should modify the given elevation map to
1, 2, 1,
2, 4, 5,
7, 8, 9
getaverageelevation:
ListListintfloat
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.
For example, if the elevation map is
1, 2, 1,
4, 6, 5,
7, 8, 9
the function should return a value close to 4.778.
findpeak:
ListListintListint
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.
For example, if the elevation map is
1, 2, 3,
9, 8, 7,
4, 5, 6
the function should return 1, 0 since the largest elevation value 9 in the elevation map is in the cell 1, 0.
issink:
ListListint, Listintbool
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 maps 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.
For example, if the elevation map is
1, 2, 1,
4, 6, 5,
7, 8, 9
and the cell is 0, 2, the function should return True, since the value 1 in cell 0, 2 is smaller than the values in all its adjacent cells: 2, 6, and 5. If the cell is 2, 0, then the function should return False, since the value 7 is not smaller than the values in the adjacent cells.
findlocalsink:
ListListint, ListintListint
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.
For example, if the elevation map is
1, 2, 3,
9, 8, 7,
4, 5, 6
and the cell is 1, 1 the function should return 0, 0 since the smallest elevation value 1 among all cells adjacent to cell 1, 1 is in the cell 0, 0.
canhiketo:
ListListint, Listint, Listint, intbool
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 nonnegative 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 NorthWest 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 wont overshoot their destination. They will also not choose to travel in either direction if there is no cell in that direction they wont 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.
getlowerresolution:
ListListintListListint
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 2×2 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 functions behaviour. Note how the the function behaves in example 2, where the number of rowcolumns is odd.
Example 1 argument value:
1, 6, 5, 6,
2, 5, 6, 8,
7, 2, 8, 1,
4, 4, 7, 3
Example 1 return value:
3, 6,
4, 4
Note, when rounding down:
162543
566846
724444
817344
Example 2 argument value:
7, 9, 1,
4, 2, 1,
3, 2, 3
Example 2 return value:
5, 1,
2, 3
Note, when rounding down:
794245
1121
3222
313
No Input or Output
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.
A2 Checker
We are providing a checker module a2checker.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 a2checker.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 descriptions and fix the code style. Please see the PyTA documentation 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.
Marking
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 dont 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: we may check for uses of helper functions and the existence of docstrings in helper functions.
All functions, including helper functions, should have complete docstrings including preconditions when you think they are necessary.
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.
What to Hand In
The very last thing you do before submitting should be to run the checker program one last time.
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.
Reviews
There are no reviews yet.