elevation map

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]
    '''

    lst = [0, 0, 0]
    for i in elevation_map[map_row]:
            if i < level:
                lst[0] += 1
            if i == level:
                lst[1] += 1
            if i > level:
                    lst[2] += 1
    return lst


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]]

    '''
    if valid_cell(elevation_map, start) and valid_cell(elevation_map, stop):
        for y_index in range(start[0], stop[0] + 1):
            for x_index in range(start[1], stop[1] + 1):
                elevation_map[y_index][x_index] += delta


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
    '''
    sum = 0
    counter = 0
    for index in elevation_map:
        for i in index:
            sum += i
            counter += 1
    return sum/counter

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]
    '''
    curr_highest_elevation = 0
    curr_best_cell = [0, 0]
    for index in elevation_map:
        for i in range(len(index)):
            if index[i] > curr_highest_elevation:
                curr_highest_elevation = index[i]
                curr_best_cell[0] = elevation_map.index(index)
                curr_best_cell[1] = i
    return curr_best_cell

def valid_cell(elevation_map: List[List[int]], cell: List[int], )-> bool:
    ''' Return true if the cell is within elevation map boundaries'''
    row = len(elevation_map[0]) - 1
    column = len(elevation_map) - 1
    return 0 <= cell[0] <= row and 0 <= cell[1] <= column

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
    '''
    potential_cell = cell
    if valid_cell(elevation_map, potential_cell):
        sink = elevation_map[cell[0]][cell[1]]
        row = len(elevation_map[0]) - 1
        column = len(elevation_map) - 1
        e_map = elevation_map
        if cell[1] + 1 < row and sink > e_map[cell[0]][cell[1] + 1]:
            return False
        if 0 <= cell[1] - 1 and sink > e_map[cell[0]][cell[1] - 1]:
            return False
        if 0 <= cell[0] - 1 and sink > e_map[cell[0] - 1][cell[1]]:
            return False
        if 0 <= cell[0] - 1 and 0 <= cell[1] - 1 \
           and sink > e_map[cell[0] - 1][cell[1] - 1]:
            return False
        if 0 <= cell[0] - 1 and cell[1] + 1 < row \
           and sink > e_map[cell[0] - 1][cell[1] + 1]:
            return False
        if cell[0] + 1 < column and sink > e_map[cell[0] + 1][cell[1]]:
            return False
        if cell[0] + 1 < column and 0 <= cell[1] - 1 \
           and sink > e_map[cell[0] + 1][cell[1] - 1]:
            return False
        if cell[0] + 1 < column and cell[1] + 1 < row \
           and sink > e_map[cell[0] + 1][cell[1] + 1]:
            return False
        return True
    return False


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]
    '''
    curr_local_sink = [0, 0]
    curr_sink = 999999

    for adj_cell in [[cell[0], cell[1]], [cell[0], cell[1] + 1],\
                     [cell[0], cell[1] - 1], [cell[0] - 1, cell[1]],
                     [cell[0] - 1, cell[1] - 1], [cell[0] - 1, cell[1] + 1],\
                     [cell[0] + 1, cell[1]],
                     [cell[0] + 1, cell[1] - 1], [cell[0] + 1, cell[1] + 1]]:
        if valid_cell(elevation_map, adj_cell):
            curr_adj_cell = elevation_map[adj_cell[0]][adj_cell[1]]
            if curr_adj_cell < curr_sink:
                curr_sink = curr_adj_cell
                curr_local_sink = adj_cell
    return curr_local_sink

def north_difference(elevation_map: List[List[int]], start: List[int]) -> int:
    ''' Return the north difference between elevations'''
    e_map = elevation_map
    cur_p = start
    diff = abs(e_map[cur_p[0] - 1][cur_p[1]] - e_map[cur_p[0]][cur_p[1]])
    return diff

def west_difference(elevation_map: List[List[int]], start: List[int]) -> int:
    ''' Return the west difference between elevations'''
    e_map = elevation_map
    cur_p = start
    diff = abs(e_map[cur_p[0]][cur_p[1] - 1] - e_map[cur_p[0]][cur_p[1]])
    return diff

def can_hike_to(elevation_map: List[List[int]], start: List[int],
                dest: 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
    '''
    cur_p = start
    cur_s = supplies
    if start == dest:
        return True
    while True:
        if cur_p[0] == dest[0]:
            cur_s -= abs(
                elevation_map[cur_p[0]][cur_p[1] - 1] - elevation_map[cur_p[0]][
                    cur_p[1]])
            cur_p[1] -= 1
        elif cur_p[1] == dest[1]:
            cur_s -= abs(
                elevation_map[cur_p[0] - 1][cur_p[1]] - elevation_map[cur_p[0]][
                    cur_p[1]])
            cur_p[0] -= 1
        else:
            if north_difference(elevation_map, start) \
               < west_difference(elevation_map, start):
                cur_s -= north_difference(elevation_map, start)
                cur_p[0] -= 1
            else:
                cur_s -= west_difference(elevation_map, start)
                cur_p[1] -= 1
        if cur_s < 0:
            return False
        if cur_p == dest:
            return True

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]]
    '''
    return_map = []
    y_comp = len(elevation_map)
    x_comp = len(elevation_map[0])
    for y in range(0, y_comp, 2):
        row = []
        for x in range(0, x_comp, 2):
            if x + 1 == x_comp and y + 1 == y_comp:
                total = elevation_map[y][x]
            elif x + 1 == x_comp:
                total = (elevation_map[y][x] + elevation_map[y + 1][x]) // 2
            elif y + 1 == y_comp:
                total = (elevation_map[y][x] + elevation_map[y][x + 1]) // 2
            else:
                total = (elevation_map[y][x] + elevation_map[y + 1][x] +
                         elevation_map[y + 1][x + 1] + elevation_map[y]
                         [x + 1]) // 4
            row.append(total)
        return_map.append(row)
    return return_map

        
if __name__ == '__main__':
    import doctest
    doctest.testmod()