# CS Exam
## 2019

1.

class Node:
    def __init__(self, name, type_):
        
        self.name = name
        self.type_ = type_
        self.childs = []
        
    def add_child(self, nodes):
        
        if type(nodes) is Node:
            self.childs.append(nodes)
        elif type(nodes) is list:
            for n in nodes:
                if type(n) is Node:
                    self.child.append(n)
                else:
                    raise Exception('Non node type in the given list')
        else:
            raise Exception('Pass Node or List of Node ')            

2.

root = Node('Peoria', 'D')
root.add_child([Node('Springfield', 'D'), Node('Bloomington', 'R'), Node('Naperville', 'D')])
root.child[0].add_child([Node('Decatur', 'R'), Node('Jacksonville', 'R')])
root.child[2].add_child([Node('Chicago', 'R'), Node('Evanston', 'R'), Node('Rockford', 'R')])

3.

class Node2(Node):
    super().__init__()
    

    def count_nodes(self, root):

        self._node_num = 0

        if root is None:
            return self._node_num

        elif len(root.childs) == 0:
            node_num += 1
            return self._node_num

        else:
            self.traverse(root)
            return self._node_num

    def traverse(self, node):
    
        self._node_num += len(node.child)
        for n in node.child:
            try:
                self.traverse(n)
            except:
                pass

4.

class Node3(Node2):
    super().__init__()
    
    def search(self, node, goal):
        if self.find_path(node, goal):
            return True
        else:
            print('no path')
            return False
        
    def find_path(self, node, goal):
        
        self._hist = []
        
        if node is None:
            return None
        
        self._hist.append(node.name)
        if node.name == goal:
            print(self_hist)
            return True
        temp = [self.find_path(n, goal) for n in node.child]
        
        if True in temp:
            return True
        else:
            self._hist.remove(self._hist[-1])
            return False

## 2020

1.

class Team:
    def __init__(self, name):
        self.name = name
class Match:
    def __init__(self, home, away, home_score, away_score):
        
        self.home, self.away, self.home_score, self.away_score=home, away, home_score, away_score
        
        if home_score < away_score:
            self.win_team = away
        else:
            self.win_team = home
    def advance(self):
        return self.win_team

class Tourney:
    def __init__(self):
        self.teams = set()
        self.rounds = [[]]
        self.current_round = 0
    def add_match(self, match):
        
        self.rounds[self.current_round].append(match)
        self.teams.add(match.home)
        self.teams.add(match.away)

    def round_adv(self):
        self.current_round += 1
        self.rounds.append([])        

2.

teams = [Team('Aardvarks'), Team('Bats'), Team('Chinchillas'), Team('Dingoes'), Team('Foxes'), Team('Geckos'), Team('Elephants')]

round1 = [
    Match(teams[0], teams[1], 10, 5),
    Match(teams[2], teams[3], 7, 7),
    Match(teams[3], teams[4], 2, 3)
]

round2 = [
    Match(round1[0].advance(), round1[1].advance(), 9, 6),
    Match(teams[-1], round1[2].advance(), 18, 0)
]

round3 = [
    Match(round2[0].advance(), round2[1].advance(), 4, 1)
]

3+4

class Tourney2(Tourney):
    super().__init__()
    
    def count_rounds(self):
        return len(self.teams)//2
    def winner(self):
        return self.round[-1][-1].advance().name
        
T = Tourney2()
for m in round1:
    T.add_match(m)
T.round_adv()

for m in round2:
    T.add_match(m)
T.round_adv()

for m in round3:
    T.add_match(m)
T.round_adv()

## 2021
1.

class Node:
    def __init__(self, name, events=None, probs=None):
        
        self.name = name
        if events is None and probs is None:
            assert len(events) == len(probs)
            for p in probs:
                assert p >= 0.0
            assert sum(probs) == 1 # unless it's a continous distribution
        
        self.events = events
        self.probs = probs
class Tree:
    def __init__(self, root):
        self.root = root

2.

c1 = Node('c1',['h', 't'], [1/3, 2/3])
c2 = Node('c2',['h', 't'], [1/4, 3/4])
c3 = Node('c3',['h', 't'], [1/5, 4/5])
pick_coin =Node('pick coin', [c1, c2, c3], [1/3, 1/3, 1/3])
experiment = Tree(pick_coin)

3.

class Tree2(Tree):
    super().__init__()
    
    def count_terminal(self):
        self._terminals = 0
        
        if self.root is not None:
            for e in self._terminals.events:
                self._traverse(e)
            return self._terminals
        else:
            return 0       
                
    def _traverse(self, node):
        if type(node) is str:
            self._traverse += 1
        else:
            for e in node.events:
                self._traverse(e)
                
    def compute_prob(self, path):
        
        self._p = 1
        reach=False
        path_idx = 0
        cur_node = root
        
        while(path_idx < len(path)):
            n = self.find_path(cur_node, path[path_idx])
            if n is None:
                print('no such path')
                self._p = 0
                break
            else:
                cur_node = n
                path_idx += 1
                if path_idx == len(path):
                    break
            
        return self._p
        
    def find_path(self, cur_node, next_goal):
        
        found = False
        for i, n in enumerate(cur_node.events):
            if type(n) is str:
                if n == next_goal:
                    self._p *= cur_node.probs[i]
                    found=True
                    break
            elif type(n) is Node:
                if n.name == next_goal:
                    self._p *= cur_node.probs[i]
                    found=True
                    break
        if found:
            return n
        else:
            return None