”’CSC108: Assignment 2
Author:Yu Tong Yang
”’
from typing import List
THREE_BY_THREE = [[1, 2, 1],
[4, 6, 5],
[7, 8, 9]]
FOUR_BY_FOUR = [[1, 2, 6, 5],
[4, 5, 3, 2],
[7, 9, 8, 1],
[1, 2, 1, 4]]
UNIQUE_3X3 = [[1, 2, 3],
[9, 8, 7],
[4, 5, 6]]
UNIQUE_4X4 = [[10, 2, 3, 30],
[9, 8, 7, 11],
[4, 5, 6, 12],
[13, 14, 15, 16]]
def compare_elevations_within_row(elevation_map: List[List[int]], map_row: int,
level: int) -> List[int]:
”’Return a new list containing three counts: the number of elevations
from row number map_row of elevation_map that are less than, equal to,
and greater than elevation level.
Precondition: elevation_map is a valid elevation map.
0 <= map_row < len(elevation_map).
>>> compare_elevations_within_row(THREE_BY_THREE, 1, 5)
[1, 1, 1]
>>> compare_elevations_within_row(FOUR_BY_FOUR, 1, 2)
[0, 1, 3]
”’
count = [0] * 3
for value in elevation_map[map_row]:
if value < level:
count[0] += 1
elif value == level:
count[1] += 1
else:
count[2] += 1
return count
def update_elevation(elevation_map: List[List[int]], start: List[int],
stop: List[int], delta: int) -> None:
”’Modify elevation_map so that the elevation of each cell
between cells start and stop, inclusive, changes by amount delta.
Precondition: elevation_map is a valid elevation map.
start and stop are valid cells in elevation_map.
start and stop are in the same row or column or both.
If start and stop are in the same row,
start’s column <= stop's column.
If start and stop are in the same column,
start's row <= stop's row.
elevation_map[i, j] + delta >= 1
for each cell [i, j] that will change.
>>> THREE_BY_THREE_COPY = [[1, 2, 1],
… [4, 6, 5],
… [7, 8, 9]]
>>> update_elevation(THREE_BY_THREE_COPY, [1, 0], [1, 1], -2)
>>> THREE_BY_THREE_COPY
[[1, 2, 1], [2, 4, 5], [7, 8, 9]]
>>> FOUR_BY_FOUR_COPY = [[1, 2, 6, 5],
… [4, 5, 3, 2],
… [7, 9, 8, 1],
… [1, 2, 1, 4]]
>>> update_elevation(FOUR_BY_FOUR_COPY, [1, 2], [3, 2], 1)
>>> FOUR_BY_FOUR_COPY
[[1, 2, 6, 5], [4, 5, 4, 2], [7, 9, 9, 1], [1, 2, 2, 4]]
”’
def get_average_elevation(elevation_map: List[List[int]]) -> float:
”’Return the average elevation across all cells in elevation_map.
Precondition: elevation_map is a valid elevation map.
>>> get_average_elevation(UNIQUE_3X3)
5.0
>>> get_average_elevation(FOUR_BY_FOUR)
3.8125
”’
total = 0
count = 0
for values in elevation_map:
for value in values:
if value >0:
total += value
count += 1
return total/count
def find_peak(elevation_map: List[List[int]]) -> List[int]:
”’Return the cell that is the highest point in the elevation_map.
Precondition: elevation_map is a valid elevation map.
Every elevation value in elevation_map is unique.
>>> find_peak(UNIQUE_3X3)
[1, 0]
>>> find_peak(UNIQUE_4X4)
[0, 3]
”’
max = 0
for i in range(len(elevation_map)):
if i < i+1:
max = i+1
return max
def is_sink(elevation_map: List[List[int]], cell: List[int]) -> bool:
”’Return True if and only if cell exists in the elevation_map
and cell is a sink.
Precondition: elevation_map is a valid elevation map.
cell is a 2-element list.
>>> is_sink(THREE_BY_THREE, [0, 5])
False
>>> is_sink(THREE_BY_THREE, [0, 2])
True
>>> is_sink(THREE_BY_THREE, [1, 1])
False
>>> is_sink(FOUR_BY_FOUR, [2, 3])
True
>>> is_sink(FOUR_BY_FOUR, [3, 2])
True
>>> is_sink(FOUR_BY_FOUR, [1, 3])
False
”’
x = cell[0]
y = cell[1]
x_initial = 0
x_final = 0
y_initial = 0
y_final = 0
if x > len(elevation_map):
return False
elif y > len(elevation_map[0]):
return False
x_initial = x if x – 1 < 0 else x - 1
if x + 1 >= x:
x_final = x
else:
x_final = x + 1
if y – 1 < 0:
y_initial = y
else:
y_initial = y - 1
if y + 1 >= y:
y_final = y
else:
y_final = y + 1
validsink = True
for i in range(x_initial, x_final + 1):
for j in range(y_initial, y_final + 1):
if elevation_map[i][j] < elevation_map[x][y]:
validsink = False
return validsink
def find_local_sink(elevation_map: List[List[int]],
cell: List[int]) -> List[int]:
”’Return the local sink of cell cell in elevation_map.
Precondition: elevation_map is a valid elevation map.
elevation_map contains no duplicate elevation values.
cell is a valid cell in elevation_map.
>>> find_local_sink(UNIQUE_3X3, [1, 1])
[0, 0]
>>> find_local_sink(UNIQUE_3X3, [2, 0])
[2, 0]
>>> find_local_sink(UNIQUE_4X4, [1, 3])
[0, 2]
>>> find_local_sink(UNIQUE_4X4, [2, 2])
[2, 1]
”’
pass # remove this line when you implement this function
def can_hike_to(m: List[List[int]], s: List[int],
d: List[int], supplies: int) -> bool:
”’Return True if and only if a hiker can move from start to dest in
elevation_map without running out of supplies.
Precondition: elevation_map is a valid elevation map.
start and dest are valid cells in elevation_map.
dest is North-West of start.
supplies >= 0
>>> map = [[1, 6, 5, 6],
… [2, 5, 6, 8],
… [7, 2, 8, 1],
… [4, 4, 7, 3]]
>>> can_hike_to(map, [3, 3], [2, 2], 10)
True
>>> can_hike_to(map, [3, 3], [2, 2], 8)
False
>>> can_hike_to(map, [3, 3], [3, 0], 7)
True
>>> can_hike_to(map, [3, 3], [3, 0], 6)
False
>>> can_hike_to(map, [3, 3], [0, 0], 18)
True
>>> can_hike_to(map, [3, 3], [0, 0], 17)
False
”’
i = s[0]
j = s[1]
if s == d:
return True
else:
while supplies >= 0 and d != [i, j]:
if d[0] == i:
supplies -= 1
i = i + 1
elif d[1] == j:
supplies -= 1
j = j + 1
else:
while i < len(m) - 1 and j < len(m[0]) - 1:
if m[i + 1][j] - m[i][j] > m[i][j + 1] – m[i][j]:
j = j + 1
supplies -= 1
elif m[i + 1][j] – m[i][j] < m[i][j + 1] - m[i][j]:
i = i + 1
supplies -= 1
elif m[i + 1][j] - m[i][j] == m[i][j + 1] - m[i][j]:
j = j + 1
supplies -= 1
return [i, j] == d
def get_lower_resolution(elevation_map: List[List[int]]) -> List[List[int]]:
”’Return a new elevation map, which is constructed from the values
of elevation_map by decreasing the number of points within it.
Precondition: elevation_map is a valid elevation map.
>>> get_lower_resolution(
… [[1, 6, 5, 6],
… [2, 5, 6, 8],
… [7, 2, 8, 1],
… [4, 4, 7, 3]])
[[3, 6], [4, 4]]
>>> get_lower_resolution(
… [[7, 9, 1],
… [4, 2, 1],
… [3, 2, 3]])
[[5, 1], [2, 3]]
”’
pass # remove this line when you implement this function