cpsc320_tutorial.py

from random import randint


class Node(object):
    def __init__(self, id=None):
        self.children = []
        self.id = id

    def add_child(self, child):
        self.children.append(child)


class Tree(object):
    def __init__(self):
        self.root = Node(id=0)
        self.node_count = 1
        self.MAX_TREE_SIZE = 10
        self.branching = 4

    def generate(self):
        def generate_children(node):
            n_children = randint(0, self.branching)
            for _ in range(n_children):
                if self.node_count < self.MAX_TREE_SIZE:
                    child = Node(id=self.node_count)
                    self.node_count += 1
                    node.add_child(child)
                    # print("Created node_id {}, parent_id {}".format(child.id, node.id))
                else:
                    break
            for child in node.children:
                if self.node_count < self.MAX_TREE_SIZE:
                    generate_children(child)

        generate_children(self.root)

    def traverse(self):
        def inorder_traversal(node):
            print(node.id)
            for child in node.children:
                inorder_traversal(child)

        inorder_traversal(self.root)

    def __str__(self):
        def str_node(node, level):
            ret = " "*level + str(node.id) + "\n"
            for child in node.children:
                ret += str_node(child, level + 1)
            return ret

        return str_node(self.root, 0)

    def R(self):
        memory1 = {}
        memory2 = {}

        def R1(node):  # Zafer's proposal
            if memory1.get(node.id, False):
                return memory1[node.id]

            c = len(node.children)
            if c == 0:
                return 0

            res = max(max([R1(child) for child in node.children]) + 1, len(node.children))
            memory1[node.id] = res
            return res

        def R2(node):
            if memory2.get(node.id, False):
                return memory2[node.id]

            c = len(node.children)
            if c == 0:
                return 0

            subs = [R2(child) for child in node.children]
            sorted_subs = sorted(subs, reverse=True)
            res = -1
            for i, sub in enumerate(sorted_subs):
                res = max(res, sub + i + 1)
            return res

        # print("Zafer's proposal: {}".format(R1(self.root)))
        # print("Lin's proposal: {}".format(R2(self.root)))
        return (R1(self.root), R2(self.root))


if __name__ == '__main__':
    for _ in range(1000000):
        tree = Tree()
        tree.generate()
        res = tree.R()
        if res[0] != res[1]:
            print("Failed. Results are {}".format(res))
            print(tree)
            break