Playing with lists and mypy strict

Mypy –strict mode can make your life pretty interesting. Over this weekend I thought to take a look at list operations and enabling mypy strict mode. Mypy is a type-checking module for python. It’s main purpose is to limit runtime issues related to types.

For the 2h timeboxed playground, I have used this very interesting problem to solve (and play with lists and mypy):

You are given two nodes in a symmetrical binary tree. The tree is numbered incrementally from left to right. Each node can only have one parent and two children. Without creating a tree structure in memory try to find the lowest common ancestor. (https://en.wikipedia.org/wiki/Lowest_common_ancestor)

Nodes start from 1.
Examples:
6, 5 -> lowest common ancestor: 1
18, 5 – > lowest common ancestor: 2

Conditions:

1 >= node1 <= 1000000
1 >= node2 <= 1000000

The program takes 2 integers as an input and returns 1 integer.

I thought to myself – ye I can do it using lists and simple division. Code is not necessarily optimized yet. But it was fun!

---

The code is stored here: https://github.com/fitg/lowest-common-ancestor. The three massive learnings were:

1. Finding common elements within 2 lists via list(set.intersection(*map(set, merger)))

def find_lowest_common_ancestor(ancestors1: List[int], ancestors2: List[int]) -> int:
    # merge both lists
    merger: List[List[int]] = [ancestors1, ancestors2]
    # find common elements in both lists
    common = list(set.intersection(*map(set, merger)))  # type: ignore
    # sort the list in descending order to find the ancestor
    common.sort(reverse=True)
    # return the top element as the lowest common ancestor
    return int(common[0]) if len(common) else 1  # type: ignore

2. Somewhat hacky way to get argparse to validate input range

def input(input_value: str) -> str:
    if int(input_value) not in range(MIN_VALUE, MAX_VALUE):
        raise ValueError
    return input_value


def user_input() -> Any:
    parser = argparse.ArgumentParser(description="Find the lowest common ancestor for two binary tree nodes")
    parser.add_argument(
        "integers", metavar="node id", type=input, nargs=2, help=f"two integer node ids; value {MIN_VALUE} >= N <={MAX_VALUE}"
    )

    args = parser.parse_args()
    return args.integers

3. Enabling mypy –strict makes life really fun. Also it actually found 2 places, where type could have been an issue in such a simple program

---

That’s all I have for today, just sharing another 2h timebox learning on python. Have fun checking the repo.

Note: I have taken a proper review and refactored the code since. Including extending the finding common ancestor for any number of nodes, as well as multiple other things. Have fun going through commit history 🙂