saddle_points.py

"""Saddle Points Python Exercism"""

from typing import Set

# SaddlePoint: TypeAlias = dict[str, int]
# SaddlePoints: TypeAlias = Iterable[None] or list[None] or list[dict[str, int]] or list[SaddlePoint]

# SaddlePoint = NewType("SaddePoint", dict[str, int])
# SaddlePoints = NewType("SaddlePoints", list[None] or list[dict[str, int]] or list[SaddlePoint])
# SaddlePoints = NewType("SaddlePoints", list[None] or list[SaddlePoint])


def saddle_points(matrix: list[list[int]]) -> list[dict[str, int]]:
    """Finds the potential trees where you could build your tree house.

    Run doctests with the command: python -m doctest -v saddle_points.py

    >>> matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    >>> list(map(max, matrix))
    [3, 6, 9]

    >>> print(*matrix)
    [1, 2, 3] [4, 5, 6] [7, 8, 9]
    >>> list(zip(*matrix))
    [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    >>> list(map(min, zip(*matrix)))
    [1, 2, 3]

    >>> max_rows = list(map(max, matrix))
    >>> min_columns = list(map(min, zip(*matrix)))
    >>> list(enumerate(max_rows))
    [(0, 3), (1, 6), (2, 9)]
    >>> list(enumerate(min_columns))
    [(0, 1), (1, 2), (2, 3)]
    >>> [{"row": row_id + 1, "column": col_id + 1} for row_id, row_maximums in enumerate(max_rows) for col_id, col_minimums in enumerate(min_columns) if row_maximums == col_minimums]
    [{'row': 1, 'column': 3}]

    param: matrix: list[list[int]] - matrix of tree hights
    returns: list[Dict[str, int]] -
    """
    # result: SaddlePoints = SaddlePoints([])
    result: list[dict[str, int]] = []

    # fast return: empty matrix
    if not matrix:
        return result

    # fast return: if the rows aren't the same length, it's irregular
    lengths: Set[int] = {len(row) for row in matrix}
    if len(lengths) > 1:
        raise ValueError("irregular matrix")

    max_rows: list[int] = list(map(max, matrix))
    min_columns: list[int] = list(map(min, zip(*matrix)))

    result = [{"row": row_id + 1, "column": col_id + 1} for row_id, row_maximums in enumerate(max_rows) for col_id, col_minimums in enumerate(min_columns) if row_maximums == col_minimums]

    return result