Untitled

from random import randint
from statistics import mean, stdev

def print2(text):
    if False:
        print(text)

class Node:
    def __init__(self, nbr, parent):
        self.parent = parent
        self.left = None
        self.right = None
        self.marked = False
        self.nbr = nbr

    def testRules(self):
        if not self.marked:
            if self.left and self.left.marked and self.right.marked:
                print2("Marking from rule node " + str(self.nbr))
                self.marked = True
                return True
            if self.parent and self.parent.marked and (self.parent.left.marked or self.parent.right.marked):
                print2("Marking from rule node " + str(self.nbr))
                self.marked = True
                return True
            else:
                return False

class Tree:
    def __init__(self, n):
        self.n = n
        nodeList = []
        self.root = Node(1, None)
        nodeList.append(self.root)
        for i in range(2,n+1,2):
            left = Node(i, nodeList[i//2-1])
            right = Node(i+1, nodeList[i//2-1])
            nodeList.append(left)
            nodeList[i//2-1].left = left
            nodeList.append(right)
            nodeList[i//2-1].right = right
        self.nodeList = nodeList

    def getRoot(self):
        return self.root

    def find(self, nbr):
        if self.root is not None:
            return self._find(nbr, self.root)
        else:
            return None

    def _find(self, nbr, node):
        if nbr == node.nbr:
            return node
        elif (nbr < node.nbr and node.left is not None):
            return self._find(nbr, node.left)
        elif (nbr > node.nbr and node.right is not None):
            return self._find(nbr, node.right)

    def printTree(self):
        if self.root is not None:
            self._printTree(self.root)

    def _printTree(self, node):
        if node is not None:
            self._printTree(node.left)
            print(str(node.nbr) + ' ')
            self._printTree(node.right)

    def mark(self, nbr):
        node = self.nodeList[nbr-1]
        node.marked = True
        print2("Marking node " + str(nbr))
        self.evalGame(node.left)
        self.evalGame(node.right)
        self.evalGame(node.parent)
        if node.parent and node.parent.left is node:
            self.evalGame(node.parent.right)
        elif node.parent:
            self.evalGame(node.parent.left)

    def evalGame(self, node):
        if node is None or node.marked:
            return
        elif node.testRules():
            self.evalGame(node.left)
            self.evalGame(node.right)
            self.evalGame(node.parent)
            if node.parent and node.parent.left is node:
                self.evalGame(node.parent.right)
            elif node.parent:
                self.evalGame(node.parent.left)
    
    def isDone(self):
        for node in self.nodeList:
            if not node.marked:
                return False
        return True

def roundOne(tree):
    counter = 0
    while not tree.isDone():
        counter += 1
        tree.mark(randint(1, tree.n))
    return counter

def roundTwo(tree):
    markOrder = [*range(1,tree.n+1)]
    for i in reversed(range(tree.n)):
        r = randint(0,i)
        markOrder[i], markOrder[r] = markOrder[r], markOrder[i]
    counter = 0
    while not tree.isDone():
        counter += 1
        tree.mark(markOrder[counter])
    return counter

def roundThree(tree):
    counter = 0
    while not tree.isDone():
        nodeNbrs = []
        for node in tree.nodeList:
            if not node.marked:
                nodeNbrs.append(node.nbr)
        r = randint(0,len(nodeNbrs)-1)
        counter += 1
        tree.mark(nodeNbrs[r])
    return counter

def main():
    data = {}
    for h in range(2,15):
        N = 2**h-1
        serie = []
        for i in range(3):
            tree = Tree(N)
            serie.append(roundThree(tree))
            #print("N = " + str(N) + ", i = " + str(i))
        data[N] = (mean(serie), stdev(serie))
    print(data)
if __name__ == "__main__": main()