<jupyter_start><jupyter_text>Homework 8 Due Date:  Tuesday, October 31st at 11:59 PM<jupyter_code>class BinaryTree():
    """
    This class creates a binary tree. We 
    
    """
    def __init__(self):
        #self.parent = None #initialize parent node
        self.key = None #initializing the Center of Activity (CoA)
        self.left = None #pointer to left child
        self.right = None #pointer to the right child
        self.min = None #initialize minimum
        self.parent = None
        self.current_depth = 0 #initialize current depth
    
    def find_max(self):
        #find min of the subtree
        if self.key is None:
            return None
        node = self
        while node.right is not None:
            node = node.right
        return node
        
    def insert(self,val):
        "Insert the value into the tree according to the BST property"
        if self.key == None: #base case
            self.key = val
        
        node = self
        
        while node.key != val:
            if node.key > val:
                if node.left is None: #if there is no child on the left, I need to create that subtree
                    node.left = self.__class__()
                    node.left.key = val
                    node.left.parent = node
                node = node.left
                    
            else:
                if node.right is None: #if there is no child on the right, I need to create that subtree
                    node.right = self.__class__()
                    node.right.key = val
                    node.right.parent = node
                #node.parent = node
                node = node.right
                
    def delete(self):
        "Deletes self's key from subtree and returns parent of removed node"
        node = self
        if (self.left is not None) and (self.right is not None):
            node = self.left.find_max()
            self.key = node.key
            
        if node.right is not None:
            node.replace(node.right)
        elif node.left is not None:
            node.replace(node.left)
            
        else:
            if node.parent is None:
                node.key = None
            elif node.parent.right is node:
                node.parent.right = None
            elif node.parent.left is node:
                node.parent.left = None
                
        return node
    
    def replace(self, node):
        "Replaces self's key, left, and right with node's key, left, and right"
        self.key = node.key
        self.left = node.left
        self.right = node.right
        if self.left is not None:
            self.left.parent = self
        if self.right is not None:
            self.right.parent = self
            
    def remove(self,val):
        #print(self.key)
        if self.key == val:
            self.delete()

        else: #if we are not on the correct node, recurse either left or right
            if self.key > val:
                if self.left:
                    self.left.remove(val)
                    
            else:
                if self.right:
                    self.right.remove(val)
        
    def getValues(self,counter=0,depth=0,a=[]):
        
        #print("Current key:", self.key)
        if counter == depth: #base case
            a.append(self.key)
            return
        
        else:
            counter = counter + 1
            if self.left:
                #print("going left")
                self.left.getValues(counter,depth,a)
            else:
                b =pow(2,(depth-counter))
                #print(c*b)
                c=["None"]
                for i in c*b:
                    a.append(i)
            if self.right:
                self.right.getValues(counter,depth,a)
            else:
                b =pow(2,(depth-counter))
                c=["None"]
                #print(c*b)
                for i in c*b:
                    a.append(i)
        
        return a
    
    def print_postorder(self,a=[]):
        
        if self != None:
            if self.left:
                self.left.print_postorder()
            if self.right:
                self.right.print_postorder()
            #print(self.key)
            a.append(self.key)
            
        return a
    
    def print_preorder(self,a=[]):
        
        if self != None:
            #print(self.key)
            a.append(self.key)
            if self.left:
                self.left.print_preorder()
            if self.right:
                self.right.print_preorder()
        
        return a
    
    def print_inorder(self,a=[]):
        
        if self != None:
            if self.left:
                self.left.print_inorder()
            #print(self.key)
            a.append(self.key)
            if self.right:
                self.right.print_inorder()
        
        return a
    
    def __str__(self):
        "Returns ASCII drawing of the tree"
        s = str(self.key)
        if (self.left is not None) or (self.right is not None):
            ws = len(s)
            sl, wl, cl = [''], 0, 0
            if self.left is not None:
                sl = str(self.left).splitlines()
                wl = len(sl[0])
                cl = len(sl[0].lstrip(' _'))
            sr, wr, cr = [''], 0, 0
            if self.right is not None:
                sr = str(self.right).splitlines()
                wr = len(sr[0])
                cr = len(sr[0].rstrip(' _'))
            while len(sl) < len(sr):
                sl.append(' ' * wl) 
            while len(sr) < len(sl):
                sr.append(' ' * wr)
            s = s.rjust(ws + cl, '_').ljust(ws + cl + cr, '_')
            s = [s.rjust(ws + wl + cr).ljust(ws + wl + wr)]
            s = '\n'.join(s + [l + (' ' * ws) + r for (l,r) in zip(sl, sr)])
        return s<jupyter_output><empty_output><jupyter_text>Problem 1:  BST TraversalThis problem builds on Problem 1 of Homework 7 in which you wrote a binary search tree. Part 1As discussed in lecture, three different types to do a depth-first traversal are: preorder, inorder, and postorder. Here is a reference: [Tree Traversal](https://en.wikipedia.org/wiki/Tree_traversalDepth-first_search).Write an iterator class called `DFSTraversal` with the following specifications:* `__init__(self, tree, traversalType)`: Constructor takes a `BinaryTree` object and one of the enums from `DFSTraversalTypes````pythonfrom enum import Enumclass DFSTraversalTypes(Enum):    PREORDER = 1    INORDER = 2    POSTORDER = 3```* `changeTraversalType(self, traversalType)`: Change the traversal type* `__iter__(self)`: This is the initialization of an iterator* `__next__(self)`: This is called in the iterator for getting the next valueHere's how you might use your `DFSTraversal` class:```pythoninput_array = [3, 9, 2, 11]bt = BinaryTree()for val in input_array:    bt.insert(val)traversal = DFSTraversal(bt, DFSTraversalTypes.INORDER)for val in traversal:    print(val)23911``` Part 2Put your `BinaryTree` class (from homework 7) and your `DFSTraversal` class (from Part 1 of this homework) in a file titled `TreeTraversal.py`. Part 1<jupyter_code>from enum import Enum
class DFSTraversalTypes(Enum):
    PREORDER = 1
    INORDER = 2
    POSTORDER = 3
class DFSTraversal:
    
    def __init__(self, tree, traversalType):
        self.tree = tree
        #self.leftS = tree.left
        #self.rightS = tree.right
        
        self.traversal = traversalType
        self.printlist= None
        self.index = 0
    
    def changeTraversalType(self,traversalType):
        self.traversal = traversalType
        #print(self.traversal.value)
    
    def __iter__(self):
        #create the tree traversal here
        if self.traversal.value == 1:
            self.printlist = self.tree.print_preorder()
        
        #in-order case
        elif self.traversal.value == 2:
            self.printlist = self.tree.print_inorder()
        
        else:
            self.printlist = self.tree.print_postorder()
        
        return self
    
    def __next__(self):
        try:
            tree = self.printlist[self.index]
            #tree = self.tree[self.index] 
        except IndexError:
            raise StopIteration() 
        self.index += 1
        return tree
BST1 = BinaryTree()
testlist=[7, 0, 1,5, 11, 2, 9, 6, 0, 3, 8, 12,13,14]
for i in testlist:
    BST1.insert(i)
print(BST1)
traversal = DFSTraversal(BST1, DFSTraversalTypes.POSTORDER)
for i in traversal:
    print(i)
traversal2 = DFSTraversal(BST1, DFSTraversalTypes.PREORDER)
for i in traversal2:
    print(i)
traversal3 = DFSTraversal(BST1, DFSTraversalTypes.INORDER)
for i in traversal3:
    print(i)
%%file TreeTraversal.py

class BinaryTree():
    """
    This class creates a binary tree. We 
    
    """
    def __init__(self):
        #self.parent = None #initialize parent node
        self.key = None #initializing the Center of Activity (CoA)
        self.left = None #pointer to left child
        self.right = None #pointer to the right child
        self.min = None #initialize minimum
        self.parent = None
        self.current_depth = 0 #initialize current depth
    
    def find_max(self):
        #find min of the subtree
        if self.key is None:
            return None
        node = self
        while node.right is not None:
            node = node.right
        return node
        
    def insert(self,val):
        "Insert the value into the tree according to the BST property"
        if self.key == None: #base case
            self.key = val
        
        node = self
        
        while node.key != val:
            if node.key > val:
                if node.left is None: #if there is no child on the left, I need to create that subtree
                    node.left = self.__class__()
                    node.left.key = val
                    node.left.parent = node
                node = node.left
                    
            else:
                if node.right is None: #if there is no child on the right, I need to create that subtree
                    node.right = self.__class__()
                    node.right.key = val
                    node.right.parent = node
                #node.parent = node
                node = node.right
                
    def delete(self):
        "Deletes self's key from subtree and returns parent of removed node"
        node = self
        if (self.left is not None) and (self.right is not None):
            node = self.left.find_max()
            self.key = node.key
            
        if node.right is not None:
            node.replace(node.right)
        elif node.left is not None:
            node.replace(node.left)
            
        else:
            if node.parent is None:
                node.key = None
            elif node.parent.right is node:
                node.parent.right = None
            elif node.parent.left is node:
                node.parent.left = None
                
        return node
    
    def replace(self, node):
        "Replaces self's key, left, and right with node's key, left, and right"
        self.key = node.key
        self.left = node.left
        self.right = node.right
        if self.left is not None:
            self.left.parent = self
        if self.right is not None:
            self.right.parent = self
            
    def remove(self,val):
        #print(self.key)
        if self.key == val:
            self.delete()

        else: #if we are not on the correct node, recurse either left or right
            if self.key > val:
                if self.left:
                    self.left.remove(val)
                    
            else:
                if self.right:
                    self.right.remove(val)
        
    def getValues(self,counter=0,depth=0,a=[]):
        
        #print("Current key:", self.key)
        if counter == depth: #base case
            a.append(self.key)
            return
        
        else:
            counter = counter + 1
            if self.left:
                #print("going left")
                self.left.getValues(counter,depth,a)
            else:
                b =pow(2,(depth-counter))
                #print(c*b)
                c=["None"]
                for i in c*b:
                    a.append(i)
            if self.right:
                self.right.getValues(counter,depth,a)
            else:
                b =pow(2,(depth-counter))
                c=["None"]
                #print(c*b)
                for i in c*b:
                    a.append(i)
        
        return a
    
    def print_postorder(self,a=[]):
        
        if self != None:
            if self.left:
                self.left.print_postorder()
            if self.right:
                self.right.print_postorder()
            #print(self.key)
            a.append(self.key)
            
        return a
    
    def print_preorder(self,a=[]):
        
        if self != None:
            #print(self.key)
            a.append(self.key)
            if self.left:
                self.left.print_preorder()
            if self.right:
                self.right.print_preorder()
        
        return a
    
    def print_inorder(self,a=[]):
        
        if self != None:
            if self.left:
                self.left.print_inorder()
            #print(self.key)
            a.append(self.key)
            if self.right:
                self.right.print_inorder()
        
        return a
    
    def __str__(self):
        "Returns ASCII drawing of the tree"
        s = str(self.key)
        if (self.left is not None) or (self.right is not None):
            ws = len(s)
            sl, wl, cl = [''], 0, 0
            if self.left is not None:
                sl = str(self.left).splitlines()
                wl = len(sl[0])
                cl = len(sl[0].lstrip(' _'))
            sr, wr, cr = [''], 0, 0
            if self.right is not None:
                sr = str(self.right).splitlines()
                wr = len(sr[0])
                cr = len(sr[0].rstrip(' _'))
            while len(sl) < len(sr):
                sl.append(' ' * wl) 
            while len(sr) < len(sl):
                sr.append(' ' * wr)
            s = s.rjust(ws + cl, '_').ljust(ws + cl + cr, '_')
            s = [s.rjust(ws + wl + cr).ljust(ws + wl + wr)]
            s = '\n'.join(s + [l + (' ' * ws) + r for (l,r) in zip(sl, sr)])
        return s
    
from enum import Enum
class DFSTraversalTypes(Enum):
    PREORDER = 1
    INORDER = 2
    POSTORDER = 3

class DFSTraversal:
    
    def __init__(self, tree, traversalType):
        self.tree = tree
        #self.leftS = tree.left
        #self.rightS = tree.right
        
        self.traversal = traversalType
        self.printlist= None
        self.index = 0
    
    def changeTraversalType(self,traversalType):
        self.traversal = traversalType
        #print(self.traversal.value)
    
    def __iter__(self):
        #create the tree traversal here
        if self.traversal.value == 1:
            self.printlist = self.tree.print_preorder()
        
        #in-order case
        elif self.traversal.value == 2:
            self.printlist = self.tree.print_inorder()
        
        else:
            self.printlist = self.tree.print_postorder()
        
        return self
    
    def __next__(self):
        try:
            tree = self.printlist[self.index]
            #tree = self.tree[self.index] 
        except IndexError:
            raise StopIteration() 
        self.index += 1
        return tree<jupyter_output>Overwriting TreeTraversal.py<jupyter_text>---  Problem 2: Markov Chains[Markov Chains](https://en.wikipedia.org/wiki/Markov_chain) are widely used to model and predict discrete events. Underlying Markov chains are Markov processes which make the assumption that the outcome of a future event only depends on the event immediately preceeding it. In this exercise, we will be assuming that weather has Markov properties (e.g. today's weather is dependent only on yesterday's weather). We will use the Markov assumption to create a basic model for predicting weather. To begin, let's categorize weather into 7 types: ['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing'].In the `weather.csv` file accompanying this homework, each row corresponds to one type of weather (in the order given above) and each column is the probability of one type of weather occurring the following day (also in the order given above).The $ij$th element is the probability that the $j$th weather type occurs after the $i$th weather type. So for example, (1,2) is the probability a cloudy day occurs after a sunny day.Take a look at the data. Make sure you see how if the previous day was sunny, the following day will have a 0.4 probability of being sunny as well. If the previous day was raining (index $i = 3$), then the following day (index $j$) has a 0.05 probability of being windy ($j = 5$).  Part 1:  Parse the `.csv` file into a `Numpy` array<jupyter_code>#Load CSV file -- hint: you can use np.genfromtxt()
import numpy as np
data_weather = np.genfromtxt('weather.csv',delimiter=',',names=['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing'])
data_weather<jupyter_output><empty_output><jupyter_text>Part 2:  Create a class called `Markov` that has the following methods:* `load_data(array)`: loads the Numpy 2D array and stores it as a class variable.* `get_prob(previous_day, following_day)`: returns the probability of `following_day` weather given `previous_day` weather. **Note:** `previous_day` and `following_day` should be passed in string form (e.g. "sunny"), as opposed to an index (e.g. 0).<jupyter_code>class Markov:
    def __init__(self):
        self.A = None #store array indices
        self.days = ['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing']

    def load_data(self,array):
        self.A = array
        
    def get_prob(self,previous_day, following_day):
        row = self.days.index(previous_day)
        col = self.days.index(following_day)
        return self.A[row][col]

w_class = Markov()
w_class.load_data(data_weather)
w_class.get_prob('sunny','hailing')<jupyter_output><empty_output><jupyter_text>---  Problem 3: Iterators Iterators are a convenient way to walk along your Markov chain. Part 1: Using your `Markov` class from Problem 3, write `Markov` as an iterator by implementing the `__iter__()` and `__next__()` methods.Remember:  * `__iter__()` should return the iterator object and should be implicitly called when the loop begins* The `__next()__` method should return the next value and is implicitly called at each step in the loop.Each 'next' step should be stochastic (i.e. randomly selected based on the relative probabilities of the following day weather types) and should return the next day's weather as a string (e.g. "sunny") rather than an index (e.g. 0).<jupyter_code>class Markov:
    def __init__(self,curr_weather,num_sims):
        import random
        self.A = None #store array indices
        self.days = ['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing']
        self.nsimulations = num_sims #will be predicting weather in num_sims days
        self.index = 0
        self.curr_weather = curr_weather
        self.simresults = []
        
    def random_pick(self,some_list, probabilities):
        #picks a random element from some_list based on probability dist in probabilities
        x = random.uniform(0, 1)
        cumulative_probability = 0.0
        for item, item_probability in zip(some_list, probabilities):
            cumulative_probability += item_probability
            if x < cumulative_probability: break
        return item

    def load_data(self,array):
        self.A = array
    
    def get_prob(self,previous_day, following_day):
        row = self.days.index(previous_day)
        col = self.days.index(following_day)
        return self.A[row][col]

    def __iter__(self):
        #create the iterable here and then "next" will just get the list of already created sims
        for i in range(self.nsimulations):
            simul = random_pick(self.days,self.A[self.days.index(self.curr_weather)])
            self.curr_weather = simul
            self.simresults.append(simul)
        return self
    
    def __next__(self):
        try:
            curr_simul = self.simresults[self.index]
        except IndexError:
            raise StopIteration() 
        self.index += 1
        return curr_simul
My_mark = Markov('sunny',7)
My_mark.load_data(data_weather)
#My_mark.random_pick(My_mark.days,My_mark.A[My_mark.days.index(My_mark.curr_weather)])
#My_mark.A
for i in My_mark:
    print(i)<jupyter_output>windy
cloudy
sunny
sunny
sunny
rainy
sunny<jupyter_text>Part 2: We want to predict what weather will be like in a week for 5 different cities.Now that we have our `Markov` iterator, we can try to predict what the weather will be like in seven days from now.Given each city's current weather in the dictionary `city_weather` (see below), simulate what the weather will be like in 7 days from now.  Rather than just producing one prediction per city, simulate 100 such predictions per city and store the most commonly occuring prediction.In your submission, print a dictionary `city_weather_predictions` that has each city as a key and the most commonly predicted weather as the corresponding value.**Note**: Don't worry if your values don't seem to make intuitive sense.  We made up the weather probabilities.<jupyter_code>city_weather = {
    'New York': 'rainy',
    'Chicago': 'snowy',
    'Seattle': 'rainy',
    'Boston': 'hailing',
    'Miami': 'windy',
    'Los Angeles': 'cloudy',
    'San Fransisco': 'windy'
}

"""
Loop through one city : use for debbuging
nsims=7 #simulations for a week
from collections import Counter
NYC = Markov(city_weather['San Fransisco'],nsims)
NYC.load_data(data_weather)
common_weather = []
city_weather_predictions = {k: v for (k, v) in zip(list(city_weather.keys()), np.zeros(len(unique_preds)))}


for i in range(10):
    current_predictions = []
    for j in NYC:
        current_predictions.append(j)
    common_weather.append(current_predictions[-1])
    #print("end of loop\n")

print(Counter(common_weather).most_common(1)[0][0])
"""
#######################
nsims=7 #simulations for a week
niter = 100 #number of iterations per city

#import Counter to get the most common values
from collections import Counter

#use dict comprehension to create a dict with cities as keys and placeholder values of 0.0
city_weather_predictions = {k: v for (k, v) in zip(list(city_weather.keys()), np.zeros(len(unique_preds)))}

#loop through each city in city dict
for key in city_weather:
    #create a Markov class instance for a city
    current_mark = Markov(city_weather[key],nsims)
    #load data to the instance of the class
    current_mark.load_data(data_weather)
    #create a list of most common weathers aafter
    common_weather = []
    #niter number of iterations
    for i in range(niter):
        #current predictions is a markov chain where each prediction depends on the previous one
        current_predictions = []
        #iterate through the class instance, implicitly calling __iter__() to create the iterable and __next__() to iterate
        for j in current_mark:
            current_predictions.append(j)
        #the last prediction is the predictions for the nsims'th day
        common_weather.append(current_predictions[-1])
    #print("Adding most common prediction of {} to city {}".format(Counter(common_weather).most_common(1)[0][0],key))
    city_weather_predictions[key]=Counter(common_weather).most_common(1)[0][0]

#####################
city_weather_predictions<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.096432623219463, 'fraction_numerical': 0.006302785831337451, 'mean_word_length': 1.927069241175747, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 27, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '98269', 'license': 'MIT', 'n_tokens_mistral': 7172, 'n_tokens_neox': 6757, 'n_words': 2181, 'path': 'HW8/HW8-Final.ipynb', 'repo_name': 'filip-michalsky/CS207_Systems_Development', 'size': '23799'}