0062_unique_paths_stupid_solution.py

0062_unique_paths_stupid_solution.py

"""
The naive/stupid version where I actually created a tree... for unique paths...
<https://leetcode.com/problems/unique-paths>

before I realised we could just do simple DP of: #paths(i, j) = #paths(i, j + 1) + #paths(i + 1, j)

ouch.
"""


class Node:
    def __init__(self, i: int, j: int):
        self.i, self.j = i, j

    def __repr__(self):
        return f'({self.i}, {self.j})'

    def is_star(self, m: int, n: int) -> bool:
        return True if self.i + 1 == n and self.j + 1 == m else False


class PathTree:
    def __init__(self, root: Node):
        self.root = root
        self.left = None
        self.right = None
        self.star_count = 0

    def update_star_count(self, m: int, n: int):
        if self.root.is_star(m, n):
            self.star_count = 1
        if self.left:
            self.left.update_star_count(m, n)
            self.star_count = self.star_count + self.left.star_count
        if self.right:
            self.right.update_star_count(m, n)
            self.star_count = self.star_count + self.right.star_count


def make_left_node(node: Node, m: int, n: int) -> Node:
    i, j = node.i, node.j
    return None if j + 1 == m else Node(i, j + 1)


def make_right_node(node: Node, m: int, n: int) -> Node:
    i, j = node.i, node.j
    return None if i + 1 == n else Node(i + 1, j)


def create_path_tree(root: Node, m: int, n: int) -> PathTree:
    tree = PathTree(root)
    if root.is_star(m, n):
        return tree
    else:
        left_node = make_left_node(root, m, n)
        if left_node:
            tree.left = create_path_tree(left_node, m, n)

        right_node = make_right_node(root, m, n)
        if right_node:
            tree.right = create_path_tree(right_node, m, n)

    return tree


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        tree = create_path_tree(Node(0, 0), m, n)
        tree.update_star_count(m, n)
        return tree.star_count


s = Solution()
print(s.uniquePaths(18, 9))