diff options
| -rw-r--r-- | hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc | bin | 0 -> 14463 bytes | |||
| -rw-r--r-- | hw4/__pycache__/bintest.cpython-310.pyc | bin | 0 -> 4383 bytes | |||
| -rw-r--r-- | hw4/assignment_lists_sortingandsearching_f22.py | 571 | ||||
| -rw-r--r-- | hw4/bintest.py | 189 | ||||
| -rw-r--r-- | hw5/.DS_Store | bin | 0 -> 6148 bytes | |||
| -rw-r--r-- | hw5/Tree_Introduction.ipynb | 543 | ||||
| -rw-r--r-- | hw6/.DS_Store | bin | 0 -> 6148 bytes |
7 files changed, 1303 insertions, 0 deletions
diff --git a/hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc b/hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc Binary files differnew file mode 100644 index 0000000..3bfec39 --- /dev/null +++ b/hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc diff --git a/hw4/__pycache__/bintest.cpython-310.pyc b/hw4/__pycache__/bintest.cpython-310.pyc Binary files differnew file mode 100644 index 0000000..52c8672 --- /dev/null +++ b/hw4/__pycache__/bintest.cpython-310.pyc diff --git a/hw4/assignment_lists_sortingandsearching_f22.py b/hw4/assignment_lists_sortingandsearching_f22.py new file mode 100644 index 0000000..ea131e3 --- /dev/null +++ b/hw4/assignment_lists_sortingandsearching_f22.py @@ -0,0 +1,571 @@ +# -*- coding: utf-8 -*- +"""assignment-lists-sortingAndSearching_f22.ipynb + +Automatically generated by Colaboratory. + +Original file is located at + https://colab.research.google.com/drive/1Ra4cQV_Fn1TwDr-EzF2VlzM3Pnk752PA +""" + + + +"""### Doubly Linked List + +We have previously developed a doubly linked list in an object oriented way. A proper implementation is found below, but feel free to use the code you wrote instead of mine. + +The code needs to be extended to have Class functions that will search for values and also will sort the values. + +## Constructing a Doubly Linked List + +The **Node** and **Doubly Linked List** class implementations are given: +""" + +class Node(object): + """Doubly linked node which stores an object""" + + def __init__(self, element, next_node=None, previous_node=None): + # The underscores are to prevent overwriting the variables if inherited and prevents access from outside of scope + self.__element = element + self.__next_node = next_node + self.__previous_node = previous_node + + def get_element(self): + """Returns the element stored in this node""" + return self.__element + + def get_previous(self): + """Returns the previous linked node""" + return self.__previous_node + + def get_next(self): + """Returns the next linked node""" + return self.__next_node + + def set_element(self, element): + """Sets the element stored in this node""" + self.__element = element + + def set_previous(self, previous_node): + """Sets the previous linked node""" + self.__previous_node = previous_node + + def set_next(self, next_node): + """Sets the next linked node""" + self.__next_node = next_node + + def __gt__(self, node): + if self.get_element() > node.get_element(): + return True + return False + + def __ge__(self, node): + if node.get_element() <= self.get_element(): + return True + return False + + def __str__(self): + return str(self.__element) + +class DoublyLinkedList(object): + """Doubly linked node data structure""" + + def __init__(self): + self.__size = 0 + self.__header = Node('Header') + self.__trailer = Node('Trailer') + self.__header.set_next(self.__trailer) + self.__trailer.set_previous(self.__header) + self.__current = None + + def __repr__(self): + if not self.is_empty(): + out = f'(' + for node in self: + out += f"({node.get_element()}), " + out = out[:-2] + out += ')' + else: + out = 'Empty List' + return out + def __iter__(self): + self.__current = None + return self + + def __next__(self): + """Standard python iterator method""" + if self.is_empty() or self.__current == self.__trailer: + raise StopIteration() + elif self.__current is None: + self.__current = self.__header + self.__current = self.__current.get_next() + if self.__current != self.__trailer: + return self.__current + else: + raise StopIteration() + + def map(self, function): + """Run function on every element in the list""" + for node in self: + if node != self.__trailer and node != self.__header: + node.set_element(function(node.get_element())) + + def size(self): + """Returns the number of elements in the list""" + return self.__size + + def is_empty(self): + """Returns the number of elements in the list""" + return self.__size == 0 + + def get_first(self): + """Get the first element of the list""" + if self.is_empty(): + raise Exception("List is empty") + else: + return self.__header.get_next() + + def get_last(self): + """Get the last element of the list""" + if self.is_empty(): + raise Exception("List is empty") + else: + return self.__trailer.get_previous() + + def get_previous(self, node): + """Returns the node before the given node""" + if node == self.__header: + raise Exception("Cannot get the element before the header of this list") + else: + return node.get_previous() + + def get_next(self, node): + """Returns the node after the given node""" + if node == self.__trailer: + raise Exception("Cannot get the element after the trailer of this list") + else: + return node.get_next() + + def add_before(self, new, existing): + """Insert the new before existing""" + previous_existing = self.get_previous(existing) + new.set_previous(previous_existing) + new.set_next(existing) + existing.set_previous(new) + previous_existing.set_next(new) + self.__size += 1 + + def add_after(self, new, existing): + """Insert the new after existing""" + next_existing = self.get_next(existing) + new.set_previous(existing) + new.set_next(next_existing) + existing.set_next(new) + next_existing.set_previous(new) + self.__size += 1 + + def add_first(self, new): + """Insert the node at the head of the list""" + self.add_after(new, self.__header) + + def add_last(self, new): + """Insert the node at the tail of the list""" + self.add_before(new, self.__trailer) + + def remove(self, node): + """Removes the given node from the list""" + before = self.get_previous(node) + after = self.get_next(node) + before.set_next(after) + after.set_previous(before) + node.set_next(None) + node.set_previous(None) + self.__size -= 1 + return node + + def __getitem__(self, index): + """ + Move to a given index in the list + I copied this over from the last assignment to make things easier + """ + assert index < self.__size + if index < (self.__size // 2): + pos = self.get_next(self.__header) + for _ in range(index): + pos = self.get_next(pos) + else: + pos = self.__trailer + for _ in range(self.__size - index): + pos = self.get_previous(pos) + + return pos + + def swap(self, target, moving): + """ + prev -> moving - > target + + >>> dll = DoublyLinkedList() + >>> dll.add_last(Node('a')) + >>> b = Node('b') + >>> dll.add_last(b) + >>> c = Node('c') + >>> dll.add_last(c) + >>> dll + ((a), (b), (c)) + >>> dll.swap(b, c) + >>> dll + ((a), (c), (b)) + """ + if moving == self.__trailer or moving == self.__header: + raise Exception("You cannot move the header or trailer") + pm = moving.get_previous() + am = moving.get_next() + pm.set_next(am) + am.set_previous(pm) + prev = target.get_previous() + prev.set_next(moving) + moving.set_previous(prev) + moving.set_next(target) + target.set_previous(moving) + + + def swap_forward(self, node): + """ + before: prev -> node -> next + after: prev -> next -> node + + >>> dll = DoublyLinkedList() + >>> dll.add_first(Node('a')) + >>> dll.add_first(Node('b')) + >>> c = Node('c') + >>> dll.add_first(c) + >>> dll.swap_forward(c) + >>> dll + ((b), (c), (a)) + """ + self.swap(node, node.get_next()) + + def swap_backward(self, node): + """ + before: prev -> node -> next + after: next -> prev -> next + + >>> dll = DoublyLinkedList() + >>> dll.add_last(Node('a')) + >>> dll.add_last(Node('b')) + >>> c = Node('c') + >>> dll.add_last(c) + >>> dll.swap_backward(c) + >>> dll + ((a), (c), (b)) + """ + self.swap(node.get_previous(), node) + + def replace(self, new, existing): + """ + before: prev -> existing -> next + after: prev -> new -> next + """ + self.add_before(new, existing) + self.remove(existing) + + def sequential_search(self,value): + """Finds the value in the list and returns the node""" + for node in self: + if node.get_element() == value: + return node + return None + + def binary_search(self,value): + """Implementation of a binary search for a value, + also returns the node""" + #HINT: REQUIRES THE LIST TO BE SORTED! + max = self.size() + index = max // 2 + val = self[index] + while val.get_element() != value: + if index <= 0 or index >= self.size() - 1: + return None + elif val.get_element() > value: + max = index + index = index // 2 + val = self[index] + else: + index += (max - index) // 2 + val = self[index] + return val + + def bubble_sort(self): + """ + >>> dll = DoublyLinkedList() + >>> [ dll.add_first(Node(i)) for i in range(20) ] + >>> dll.bubble_sort() + >>> dll + """ + for i in range(self.size()): + n = self.get_first() + for j in range(self.size()-i): + if n.get_next() != self.__trailer: + if n > n.get_next(): + self.swap_forward(n) + else: + n = n.get_next() + + def selection_sort(self): + """ + Sort a list using insertion sort + >>> dll = DoublyLinkedList() + >>> [ dll.add_first(Node(i)) for i in range(20) ] + >>> dll.insertion_sort() + >>> dll + """ + # Start at the beginning and move through every element + head = self.__header + while head != self.get_last(): + min = head.get_next() + cmp = min + # Find the minimum value in the rest of the unsorted list + while cmp != self.__trailer: + if cmp <= min: + min = cmp + cmp = cmp.get_next() + # This prevents elements from linking to themselves + if head.get_next() != min: + self.swap(head.get_next(), min) + head = min + + def insertion_sort(self): + """ + Sort a list using insertion sort + >>> dll = DoublyLinkedList() + >>> [ dll.add_first(Node(i)) for i in range(20) ] + >>> dll.insertion_sort() + >>> dll + """ + # Get the first element to compare to others + cmphead = self.get_first() + cmp = cmphead.get_next() + # Move through all elements + while cmp != self.__trailer: + # Switch the cmphead if the compared node is bigger + if cmphead < cmp: + cmphead = cmp + cmp = cmphead.get_next() + continue + # Move the cmp node to its right place + prev = cmp.get_previous() + while prev != self.__header: + if prev > cmp: + prev = prev.get_previous() + self.swap_backward(cmp) + else: + break + cmp = cmphead.get_next() + + def shell_sort(self): + gap = self.size() // 2 # This should give a good gap size + while 1 < gap: + j = 0 + while j - gap < 0: # This prevents running out of elements + if self[j] > self[j+gap]: + k = self[j].get_element() + self[j].set_element(self[j+gap].get_element()) + self[j+gap].set_element(k) + j += 1 + gap -= 1 + + # At this point with a gap size of 1 it is insertion sort + self.insertion_sort() + + + + def merge_sort(self): + """ + Sort a list using merge sort + >>> dll = DoublyLinkedList() + >>> [ dll.add_first(Node(i)) for i in range(20) ] + >>> dll.merge_sort() + >>> dll + """ + if self.size() < 2: + return + left = DoublyLinkedList() + right = DoublyLinkedList() + m = self.size() // 2 + while self.size() > 0: + if m > 0: + left.add_last(self.remove(self.get_first())) + else: + right.add_last(self.remove(self.get_first())) + m -= 1 + + left.merge_sort() + right.merge_sort() + self.merge(left, right) + + def merge(self, left, right): + while left.size() > 0 or right.size() > 0: + # Dump the right list if left is empty + if left.size() <= 0: + while right.size() > 0: + self.add_last(right.remove(right.get_first())) + # Dump the left list if right is empty + elif right.size() <= 0: + while left.size() > 0: + self.add_last(left.remove(left.get_first())) + else: + # Merge Nodes from each list depending on size + if left.get_first() < right.get_first(): + self.add_last(left.remove(left.get_first())) + else: + self.add_last(right.remove(right.get_first())) + + def quick_sort(self, b=None, e=None): + # I decided to do this one with indexing because it made it easier for + # me to figure out the base case for the recursion. + if b == None and e == None: + b = 0 + e = self.size() - 1 + + if e <= b: + return + + pivot = self[e] + i = b + j = i - 1 + + while i <= e: + if self[i] < pivot: + j += 1 + # This prevents swapping with itself + if j != i: + self.swap(self[j], self[i]) + i += 1 + + # Put the pivot in the right place + j += 1 + if self[j] != pivot: + # This prevents swapping with itself + self.swap(self[j], pivot) + + self.quick_sort(b, j - 1) + self.quick_sort(j + 1, e) + + +"""**Task 1 (25 points)**: Implement a sequential search and show the implementation works.""" + +from numpy import random + +print("Testing Sequential Search") +dL = DoublyLinkedList() +for i in range(1,21,2): + dL.add_first(Node(i)) +print(dL) + +#The code below is broken - make it work +node13 = dL.sequential_search(13) +print(node13) + +# This is to show it works +print("One moment please") +import matplotlib.pyplot as plt +from time import time +min, max, offset = 0, 500, 20 +times = [] +dl = DoublyLinkedList() +[ dl.add_first(Node(i+offset)) for i in range(max) ] +for i in range(min + offset, max + offset): + t0 = time() + dl.sequential_search(i) + times.append(time() - t0) +times.sort() +plt.plot(times) +print("As can be seen from the plot, the sequential search runs in linear time or O(n)") +plt.show() +print("Searching for value not in list") +print(dl.sequential_search(0)) + + + +"""**Task 2 (25 points)**: A Faster Search + +A **binary search** should return the node which has a value faster than the above sequential search. + +Implement a **binary search** and run it on the ***Doubly Linked List*** created. + +""" + +#Test your implementation here +#The code below is broken - make it work +print("Testing Binary Search") +dL.quick_sort() +node15 = dL.binary_search(15) +print(node15) + +# this is to show it works +print("One moment please") +min, max, offset = 0, 500, 20 +times = [] +dl.quick_sort() +for i in range(min + offset, max + offset): + t0 = time() + dl.binary_search(i) + times.append(time() - t0) +times.sort() +plt.yscale('log') +plt.plot(times) +print("As can be seen from the plot, the binary search runs in roughly logorithmic time or O(log n)") +plt.show() +print("Searching for value not in list") +print(dl.binary_search(0)) + +"""**Task 4 (50 points)**: Implement the two of the following sorting methods <br> +`Bubble Sort`, `The Selection Sort`, `The Insertion Sort`, `The Shell Sort`,<br> +`The Merge Sort`, or `The Quick Sort` + +If you did not like your grade on the previous ** Doubly Linked List** assignment, <br> +I will neglect that grade and count this assignment twice if you successfully implement the `Merge Sort` or `Quick Sort` algorithm(s). +""" + +#Test your implementation here +#do a sort here +from random import randint + +max = 20 +dl = DoublyLinkedList() +[ dl.add_first(Node(i)) for i in range(max)] +print(f"Before Quick Sort: {dl}") +dl.quick_sort() +print(f"After Quick Sort: {dl}\n") + +dl = DoublyLinkedList() +[ dl.add_first(Node(randint(0, max))) for i in range(max) ] +l = dl.size() +print(f"Before Quick Sort: {dl}") +dl.quick_sort() +print(f"After Quick Sort: {dl}\n") + +dl = DoublyLinkedList() +[ dl.add_last(Node(i)) for i in range(max)] +print(f"Before Quick Sort: {dl}") +dl.quick_sort() +print(f"After Quick Sort: {dl}\n") + + +dl = DoublyLinkedList() +[ dl.add_first(Node(i)) for i in range(max)] +print(f"Before Merge Sort: {dl}") +dl.merge_sort() +print(f"After Merge Sort: {dl}\n") + +dl = DoublyLinkedList() +[ dl.add_first(Node(randint(0, max))) for i in range(max) ] +l = dl.size() +print(f"Before Merge Sort: {dl}") +dl.merge_sort() +print(f"After Merge Sort: {dl}\n") + +dl = DoublyLinkedList() +[ dl.add_last(Node(i)) for i in range(max)] +print(f"Before Merge Sort: {dl}") +dl.merge_sort() +print(f"After Merge Sort: {dl}\n") diff --git a/hw4/bintest.py b/hw4/bintest.py new file mode 100644 index 0000000..4ee9f6c --- /dev/null +++ b/hw4/bintest.py @@ -0,0 +1,189 @@ +from assignment_lists_sortingandsearching_f22 import DoublyLinkedList, Node +import matplotlib.pyplot as plt +from time import time +from random import randint + +def binstest(): + min, max, offset = 0, 500, 20 + times = [] + dl = DoublyLinkedList() + [ dl.add_last(Node(i+offset)) for i in range(max) ] + print(dl) + for i in range(min + offset, max + offset): + t0 = time() + s = dl.binary_search(i) + times.append(time() - t0) + j = i - offset + print(f"{i}\t{j}\t{s}") + times.sort() + plt.yscale('log') + plt.plot(times) + plt.show() + print("Searching for value not in list") + print(dl.binary_search(0)) + +def bstest(): + max = 20 + dl = DoublyLinkedList() + [ dl.add_first(Node(i)) for i in range(max)] + print(dl) + dl.bubble_sort() + print(dl, "\n") + + dl = DoublyLinkedList() + [ dl.add_first(Node(randint(0, max))) for i in range(max) ] + l = dl.size() + print(dl) + dl.bubble_sort() + print(dl, "\n") + assert dl.size() == l + + dl = DoublyLinkedList() + [ dl.add_last(Node(i)) for i in range(max)] + print(dl) + dl.bubble_sort() + print(dl) + +def itest(): + max = 20 + dl = DoublyLinkedList() + [ dl.add_first(Node(i)) for i in range(max)] + print(dl) + dl.insertion_sort() + print(dl, "\n") + + dl = DoublyLinkedList() + [ dl.add_first(Node(randint(0, max))) for i in range(max) ] + l = dl.size() + print(dl) + dl.insertion_sort() + print(dl, "\n") + assert dl.size() == l + + dl = DoublyLinkedList() + [ dl.add_last(Node(i)) for i in range(max)] + print(dl) + dl.insertion_sort() + print(dl) + +def stest(): + max = 20 + dl = DoublyLinkedList() + [ dl.add_first(Node(i)) for i in range(max)] + print(dl) + dl.selection_sort() + print(dl, "\n") + + dl = DoublyLinkedList() + [ dl.add_first(Node(randint(0, max))) for i in range(max) ] + l = dl.size() + print(dl) + dl.selection_sort() + print(dl, "\n") + assert dl.size() == l + + dl = DoublyLinkedList() + [ dl.add_last(Node(i)) for i in range(max)] + print(dl) + dl.selection_sort() + print(dl) + +def mtest(): + max = 20 + dl = DoublyLinkedList() + [ dl.add_first(Node(i)) for i in range(max)] + print(dl) + dl.merge_sort() + print(dl, "\n") + + dl = DoublyLinkedList() + [ dl.add_first(Node(randint(0, max))) for i in range(max) ] + l = dl.size() + print(dl) + dl.merge_sort() + print(dl, "\n") + assert dl.size() == l + + dl = DoublyLinkedList() + [ dl.add_last(Node(i)) for i in range(max)] + print(dl) + dl.merge_sort() + print(dl) + +def qtest(): + max = 20 + dl = DoublyLinkedList() + [ dl.add_first(Node(i)) for i in range(max)] + print(dl) + dl.quick_sort() + print(dl, "\n") + + dl = DoublyLinkedList() + [ dl.add_first(Node(randint(0, max))) for i in range(max) ] + l = dl.size() + print(dl) + dl.quick_sort() + print(dl, "\n") + assert dl.size() == l + + dl = DoublyLinkedList() + [ dl.add_last(Node(i)) for i in range(max)] + print(dl) + dl.quick_sort() + print(dl) + +def shtest(): + max = 20 + dl = DoublyLinkedList() + [ dl.add_first(Node(i)) for i in range(max)] + print(dl) + dl.shell_sort() + print(dl, "\n") + + dl = DoublyLinkedList() + [ dl.add_first(Node(randint(0, max))) for i in range(max) ] + l = dl.size() + print(dl) + dl.shell_sort() + print(dl, "\n") + assert dl.size() == l + + dl = DoublyLinkedList() + [ dl.add_last(Node(i)) for i in range(max)] + print(dl) + dl.shell_sort() + print(dl) + +def atest(): + max = 20 + bub = DoublyLinkedList() + ins = DoublyLinkedList() + sel = DoublyLinkedList() + mer = DoublyLinkedList() + qui = DoublyLinkedList() + she = DoublyLinkedList() + + for _ in range(max): + i = randint(0, 100) + bub.add_last(Node(i)) + ins.add_last(Node(i)) + sel.add_last(Node(i)) + mer.add_last(Node(i)) + qui.add_last(Node(i)) + she.add_last(Node(i)) + + print(f"bub {bub}\nins {ins}\nsel {sel}\nmer {mer}\nqui {qui}\nshe {she}\n") + + bub.bubble_sort() + print(f"bub {bub}") + ins.insertion_sort() + print(f"ins {ins}") + sel.selection_sort() + print(f"sel {sel}") + mer.merge_sort() + print(f"mer {mer}") + qui.quick_sort() + print(f"qui {qui}") + she.shell_sort() + print(f"she {she}") + diff --git a/hw5/.DS_Store b/hw5/.DS_Store Binary files differnew file mode 100644 index 0000000..5008ddf --- /dev/null +++ b/hw5/.DS_Store diff --git a/hw5/Tree_Introduction.ipynb b/hw5/Tree_Introduction.ipynb new file mode 100644 index 0000000..ed32f70 --- /dev/null +++ b/hw5/Tree_Introduction.ipynb @@ -0,0 +1,543 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": { + "id": "15JSQmv0xSLG" + }, + "source": [ + "# Trees - A fast introduction\n", + "\n", + "A tree is an abstract model of a hierarchical structure. It consists of nodes with a parent-child relationship. Its name comes from the fact that when drawn, it resembles an upside-down tree: the root of the tree is at the top and the leaves are at the bottom.\n", + "\n", + "A tree is a recursive data structure; each node of the tree contains a label value and a list of branches, each of which are also trees. The label can be any data type, while the branches are represented as a list of trees. The lecture slides provide a good overview of tree terminology and a visual to help demonstrate.\n", + "\n", + "## Definitions\n", + "\n", + "* `Node`\n", + "A node is a fundamental part of a tree. It can have a name, which we call the “key.” A node may also have additional information. We call this additional information the “payload.” While the payload information is not central to many tree algorithms, it is often critical in applications that make use of trees.\n", + "\n", + "* `Edge`\n", + "An edge is another fundamental part of a tree. An edge connects two nodes to show that there is a relationship between them. Every node (except the root) is connected by exactly one incoming edge from another node. Each node may have several outgoing edges.\n", + "\n", + "* `Root`\n", + "The root of the tree is the only node in the tree that has no incoming edges. \n", + "\n", + "* `Path`\n", + "A path is an ordered list of nodes that are connected by edges. For example, Mammal → Carnivora → Felidae → Felis → Domestica is a path.\n", + "\n", + "* `Children`\n", + "The set of nodes c that have incoming edges from the same node to are said to be the children of that node. In Figure Figure 2, nodes log/, spool/, and yp/ are the children of node var/.\n", + "\n", + "* `Parent`\n", + "A node is the parent of all the nodes it connects to with outgoing edges. In Figure 2 the node var/ is the parent of nodes log/, spool/, and yp/.\n", + "\n", + "* `Sibling`\n", + "Nodes in the tree that are children of the same parent are said to be siblings. The nodes etc/ and usr/ are siblings in the filesystem tree.\n", + "\n", + "* `Subtree`\n", + "A subtree is a set of nodes and edges comprised of a parent and all the descendants of that parent.\n", + "\n", + "* `Leaf Node`\n", + "A leaf node is a node that has no children. For example, Human and Chimpanzee are leaf nodes in Figure 1.\n", + "\n", + "* `Level`\n", + "The level of a node n is the number of edges on the path from the root node to n. For example, the level of the Felis node in Figure 1 is five. By definition, the level of the root node is zero.\n", + "\n", + "* `Height`\n", + "The height of a tree is equal to the maximum level of any node in the tree. The height of the tree in Figure 2 is two." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "id": "qiJgZPzWy3VM" + }, + "outputs": [], + "source": [ + "\n", + "def tree(root_label, branches=[]):\n", + " ''' This is a simple tree implementation that allows for an arbitrary number of\n", + " children for any node'''\n", + " for branch in branches:\n", + " assert is_tree(branch), 'branches must be trees'\n", + " return [root_label] + list(branches)\n", + "def label(tree):\n", + " return tree[0]\n", + "def branches(tree):\n", + " return tree[1:]\n", + "def is_tree(tree):\n", + " if type(tree) != list or len(tree) < 1:\n", + " return False\n", + " for branch in branches(tree):\n", + " if not is_tree(branch):\n", + " return False\n", + " return True\n", + "\n" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "id": "OVAJA6SbzeBG" + }, + "outputs": [], + "source": [ + "t = tree(1, [tree(2), tree(3, [tree(4), tree(5)])])" + ] + }, + { + "cell_type": "markdown", + "metadata": { + "id": "Wn5aTBAzziPb" + }, + "source": [ + "Below is some lifted code to visualize the above tree. Credit to Allen Downey." + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "id": "vyOHFZR5x0vs" + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "zsh:1: command not found: pip\n", + "zsh:1: command not found: pip\n" + ] + } + ], + "source": [ + "try:\n", + " import EoN\n", + "except ImportError:\n", + " !pip install EoN\n", + "\n", + "\n", + "try:\n", + "\timport networkx as nx\n", + "except ImportError:\n", + " !pip install networkx\n", + "\n", + "def add_edges(parent, G):\n", + " \"\"\"Make a NetworkX graph that represents the tree.\"\"\"\n", + " if parent is None:\n", + " return\n", + " \n", + " for child in branches(parent):\n", + " if child:\n", + " G.add_edge(parent[0], child[0])\n", + " add_edges(child, G)\n", + "def get_labels(parent, labels):\n", + " if parent is None:\n", + " return\n", + " \n", + " if parent[0] == '\\0':\n", + " labels[parent] = parent.count\n", + " else:\n", + " labels[parent] = parent.letter\n", + " \n", + " get_labels(parent.left, labels)\n", + " get_labels(parent.right, labels)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "id": "7pAGS6bcx1WE" + }, + "outputs": [], + "source": [ + "G = nx.DiGraph()\n", + "add_edges(t, G)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/", + "height": 319 + }, + "id": "6YO21tUGyYyC", + "outputId": "669ddc4e-9ccd-470c-8fc6-6d0c93cc8847" + }, + "outputs": [ + { + "data": { + "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAAsTAAALEwEAmpwYAAAmhUlEQVR4nO3dy1OUWYI28CdvXJOL3ORW3ASFklsJQgFCJqCIE10d1RGzn5hFx7eazaz6H5jVrCZi9lPLnon+OvqLjmkQC0lAEhVKMEUpUQQ1C0EgTcgE8vq+36JaSwtRUDLPe3l+OyGTfMI4vA958rznGGRZlkFERKQTRtEBiIiI4onFR0REusLiIyIiXWHxERGRrrD4iIhIV1h8RESkKyw+IiLSFRYfERHpCouPiIh0hcVHRES6wuIjIiJdYfEREZGusPiIiEhXWHxERKQrLD4iItIVFh8REekKi4+IiHSFxUdERLrC4iMiIl1h8RERka6w+IiISFdYfEREpCtm0QGIjlMgHMWTdT82/CEEo1EkmkzIsSagIteKJItJdDwiUgAWH2nCpj+I2ede3HV7EZFkWExGmI0GRCQZkagEs9GAhi8y0VCciWxroui4RCSQQZZlWXQIos+xsOrDX10rMBoMyLYmwGzaP4MfiUrY9IcgyTK+qS/E6fw0AUmJSAlYfKRqC6s+/HnGjbz0pENNZQbCUaz7gvhdYxHLj0inWHykWpv+IL5zLuNEasKb0nM/WcCLp4vwb3txsrgMXza17XteIByFdyeEf2ov47QnkQ5xVSep1uxzL4wGwzvv9BKSklB2phaFpZUHPi/JYoLBYIDrJ28cUhKR0rD4SJUC4Sjuur3Itia88/W8whLkFn4Bc0LCAc/8WbY1AbPPvAiEo7GMSUQKxOIjVXqy7kdEkt+7kOUwzCYjIpKMJ+v+Y05GRErH4iNV2vCHYPnE0nvNbDLCsxM6pkREpBYsPlKlYDQKs9HwWT/DZDQgEOFUJ5HesPhIlRJNJkSkz1uQHJVkJJm5mwuR3nDnFlKlHGsCwlFp39clSQJkGZBlyLIMKRoFDAYYje+/qT0r9cOLYIhIe1h8pEoVudaftySLSu8scHn68D6Wfrz35t9rz5dRXl2H8pq6d57/ehuzilxr3DITkTLwBnZSreH5NbjcWziZkXTk565tBdBYkoHuMydjkIyIlIyf8ZF6eZ7i8eLike/Fc96agufVK9QXZcYmFxEpGouPVCcajeL69evwra/g/1xpxroveOjyC4SjyCkuR6bvCX568jDGSYlIiTjVSaoSCAQwNDSE5ORkdHd3w2w2H/p0hg1/EJCB39QXotBqwODgIE6ePImOjo73Ln4hIm1i8ZFqbG9vY2BgAGVlZWhpaYHB8Mt9fJv+IFw/eTH7zPtmRxeT0YDoW+fxNZZkor7ol/P4QqEQhoeHIcsyLl68iISPbHNGRNrA4iNVWF1dxbVr19Dc3IyampoDH/f6BHbPTgiBSBRJZhOyUg8+gV2SJDidTqyurqK/vx9WK1d5Emkdi48U7/Hjx3A6nejp6UFxcXFMXsPlcuHevXu4fPkycnJyYvIaRKQMLD5StJmZGczPz6O/vx9ZWVkxfa2lpSWMj4/DZrOhtLQ0pq9FROLwBnZSJEmSMD4+js3NTXz77bdISUmJ+WuWl5cjNTUVQ0ND8Pl8qK2tjflrElH88R0fKU4oFMLQ0BAsFgt6e3thNsf37zOfz4eBgQEUFxejra3tnUU0RKR+LD5SFKWUztvl29PTA4vFIiQHER0/Fh8pxsuXLzE0NITGxkZFTDO+Pd3a398fl+lWIoo9Fh8pgpIXlsRzgQ0RxR6Lj4RTw60E8bilgojig8VHwkiShImJCaytrani5vHD3kRPRMrG4iMhXm8XBgC9vb2q2S7sQ9umEZE6sPgo7vx+v6o3iH7fRtlEpB4sPoqrjY0NXL16FXV1daivrxcd55NFo1GMjo5ie3sbly9fRnJysuhIRHRILD6Km2fPnsHhcKCzsxPl5eWi4xyL6elpPHr0CFeuXEFmZqboOER0CCw+iou5uTnMzs6ir68PeXl5ouMcq4WFBdy6dQu9vb0oLCwUHYeIPoLFRzElyzImJyfhdrtx5coVpKWliY4UEysrKxgeHkZraytOnz4tOg4RfQCLj2ImEolgeHgY4XAYly5dQmJiouhIMeX1ejEwMICqqio0NzeLjkNEB2DxUUzs7u5icHAQWVlZ6OrqUt3KzU+1t7eHq1evIj09HTabDSbT/sNviUgsFh8dO4/Hg8HBQdTU1OCrr74SHSfuIpEIHA4Hdnd30dfXh6SkJNGRiOgtLD46Vm63G9evX0d7ezsqKytFxxFGlmVMTU1haWkJ/f39yMjIEB2JiP6OxUfHZn5+HtPT07h06RLy8/NFx1GEH3/8EVNTU/w/IVIQFh99NlmWcfv2bSwvL/PdzXvwXTCRsrD46LPw86zD0fvnnkRKwuKjT8YVjEej15WuRErD4qNPwnvWPs3b9zb29fWp5lQKIi1h8dGRcZeSz6OX3WyIlIrFR0fCfSmPj5b3LyVSMhYfHRpPIjh+WjyxgkjpWHz0UTx7Lra0ckYhkVqw+OiDeNp4fKj9VHoiNWHx0YG2t7cxMDCAsrIytLS0wGAwiI6kaaFQCMPDw5BlGRcvXuSKT6IYYfHRe62uruLatWtobm5GTU2N6Di6IUkSnE4nVldX0d/fD6vVKjoSkeaw+Gifx48fw+l0oqenB8XFxaLj6JLL5cK9e/dw+fJl5OTkiI5DpCksPnrHzMwM5ufn0d/fj6ysLNFxdG1paQnj4+Ow2WwoLS0VHYdIM7hSgQD8PMU2Pj6Ozc1NfPvtt0hJSREdSffKy8uRmpqKoaEh+Hw+1NbWio5EpAl8x0cIhUIYGhqCxWJBb28vV24qjM/nw8DAAIqLi9HW1sZFRkSficWnc7yoqsPbf5z09PTAYrGIjkSkWiw+HXv58iWGhobQ2NjIaTQVeHs6ur+/n9PRRJ+IxadTXDihXlyARPR5WHw6xKXy6sdbTog+HYtPRyRJwsTEBNbW1nhztAZwkwGiT8Pi04nX22EBQG9vL7fD0ghuK0d0dCw+HeAGyNrGjcSJjobFp3E88kYfeHQU0eGx+DSMh5zqDw8LJvo4Fp9Gzc3NYXZ2Fn19fcjLyxMdh+JoYWEBt27dQm9vLwoLC0XHIVIcFp/GyLKMyclJuN1uXLlyBWlpaaIjkQArKysYHh5Ga2srTp8+LToOkaKw+DQkEolgeHgY4XAYly5dQmJiouhIJJDX68XAwACqqqrQ3NwsOg6RYrD4NGJ3dxeDg4PIyspCV1cXV24SAGBvbw9Xr15Feno6bDYbTCaT6EhEwrH4NMDj8WBwcBA1NTX46quvRMchhYlEInA4HNjd3UVfXx+SkpJERyISisWncm63G9evX0d7ezsqKytFxyGFkmUZt2/fxvLyMvr7+5GRkSE6EpEwLD4Vm5+fx/T0NC5duoT8/HzRcUgFOGaIWHyqxL/e6XNwloD0jsWnMvy8ho4DPxcmPWPxqQhX6NFx4kpg0isWn0rwniyKhbfv/ezr6+OpHaQLLD4V4C4cFEvc7Yf0hsWncNx3keKF+7uSXrD4FIw77VO88UQP0gMWnwLxbDUS6fUZjrW1tWhoaBAdh+jYsfgU5vVp2ikpKbDb7TxNm4Tw+/0YHBzEyZMn0dHRwRWfpCksPgXZ3t7GwMAAysrK0NLSAoPBIDoS6Vg4HMb3338PWZZx8eJFrvgkzWDxKcTq6iquXbuG5uZm1NTUiI5DBACQJAlOpxOrq6vo7++H1WoVHYnos7H4FODx48dwOp3o6elBcXGx6DhE+7hcLty7dw+XL19GTk6O6DhEn4XFJ9jMzAzm5+fR39+PrKws0XGIDrS0tITx8XHYbDaUlpaKjkP0ybhyQhBJkjA+Po7NzU18++23SElJER2J6IPKy8uRmpqKoaEh+Hw+1NbWio5E9En4jk+AUCiEoaEhWCwW9Pb2cuUmqYrP58PAwACKi4vR1tbGRVikOiy+OONFg7Tg7T/eenp6YLFYREciOjQWXxy9fPkSQ0NDaGxs5DQRqd7b0/X9/f2crifVYPHFCRcGkFZxgRapDYsvDrgUnLRucXERExMTvCWHVIHFF0OSJGFiYgJra2u8+Zc0j5swkFqw+GIkFApheHgYANDb28vtnkgXuO0eqQGLLwa4wS/p2euN1pOTk9Hd3c3bdUhxWHzH7PWRLnV1daivrxcdh0gIHq1FSsbiO0ZPnz7F6OgoD/Ek+rvXhyn39/fjxIkTouMQAWDxHZu5uTnMzs6ir68PeXl5ouMQKcbCwgJu3bqF3t5eFBYWio5DxOL7XLIsY3JyEm63G1euXEFaWproSESKs7KyguHhYbS2tuL06dOi45DOsfg+QyQSwfDwMMLhMPr6+rhyk+gDvF4vBgcHUVlZiebmZtFxSMdYfJ9od3cXg4ODyMrKQldXF1duEh3C3t4erl69ivT0dNhsNphMJtGRSIdYfJ/A4/FgcHAQNTU1+Oqrr0THIVKVSCQCh8OB3d1d9PX1ISkpSXQk0hkW3xG53W5cv34d7e3tqKysFB2HSJVkWcbU1BSWlpbQ39+PjIwM0ZFIR1h8RzA/P4/p6WlcunQJ+fn5ouMQqd6PP/6Iqakp/k5RXLH4DkGWZdy+fRvLy8v865TomHEWheKNxfcRkUgEIyMj2Nvb4+cRRDHy+nPz6upqnDt3TnQc0jgW3wdwBRpR/HClNMULi+8AXq8XAwMDqKqq4j1HRHESiURw/fp1hEIhXLp0CYmJiaIjkQax+N6Du0wQiSPLMm7evInnz59zNySKCRbfr3BfQSJluH//PmZmZrj/LR07Ft9bXu8kf+XKFWRmZoqOQ6R7z549g8PhwIULF1BRUSE6DmkEiw88O4xIyV6fcVlbW4uGhgbRcUgDdF98r0+LTklJgd1u52nRRAq0s7ODgYEBnDx5Eh0dHVzxSZ9F18W3tbWFwcFBlJWVoaWlBQaDQXQkIjpAOBzG999/D1mWcfHiRZ6GQp9Mt8W3urqKa9euobm5GTU1NaLjENEhSJIEp9OJ1dVV9Pf3w2q1io5EKqTL4nv8+DGcTid6enpQXFwsOg4RHZHL5cK9e/dw+fJl5OTkiI5DKqO74puZmcH8/Dz6+/uRlZUlOg4RfaKlpSWMj4/DZrOhtLRUdBxSEd2s5JAkCWNjY/B4PPj222+RkpIiOhIRfYby8nKkpqZiaGgIPp8PtbW1oiORSujiHV8oFMLQ0BAsFgt6e3u5cpNIQ3w+HwYHB1FUVIS2tjYuUqOP0mTxBYNBWCwWGI1G+Hw+DAwMoLi4mL8URBoVCoVw7do1mM1m9PT0wGKxIBwOw2Aw8A9d2keTxfdf//VfyM3Nxfnz53Ht2jU0NjZyGoRI4yRJwvj4ODY3N9HT04P/+Z//walTp9Db2ys6GimM5opvbW0N//Ef/4HNzU3k5eXh97//PUpKSkTHIqI4uXPnDr777jvIsozc3Fz84Q9/4D1/9A7VzAEEwlE8Wfdjwx9CMBpFosmEHGsCKnKtSLL8ck7e9PQ0Njc3EQgEsLW1hZ2dHYGpiSjePB4PgsEggsEgZFnGwsLCvhmfw15PSJsUX3yb/iBmn3tx1+1FRJJhMRlhNhoQkWREohLMRgMavshEQ3EmkgwR/PGPf4Tf70dVVRUSEhLw8OFD3qBOpBPhcBiLi4vIycnBzs4OFhYW8N///d9viu8o15NsK88C1CpFT3UurPrwV9cKjAYDsq0JMJv2788XiUrY9IcgyTIqE7xw/L8/4sqVK6iqqkJBQQGSkpIEJCcikXw+H1ZWVuByuTA2NoZ/+7d/w+qu4UjXk2/qC3E6n2cBapFii29h1Yc/z7iRl550qKmHQDiKdV8Qv2ss4mAlonfwekJvU2TxbfqD+M65jBOpCW8GqRSN4uHdKXjWVxEJhZCcasWps43IPvnLYbGBcBTenRD+qb2M0xREBOD91xMAuD89gVfra4hGIkhISkZpVQ0KyyrffJ/XE+1S5Gd8s8+9MBoM7wxSWZaRlJyKcxcuIiklFZtrK5i7fQMtPf+A5NSfN6pNsphgMBjg+smL7jMnRcUnIgV53/UEAMpO16Lmq69hNJmw49vCnfFhpGVmIS3z560MeT3RLsUdahUIR3HX7UW29d3lxyazGeU1dUhOtcJgMCAnvwhJKanwbXneeVy2NQGzz7wIhKPxjE1ECnTQ9QQAUtMzYDT9UoYGA7C343/nMbyeaJPi3vE9WfcjIsnv/eD5baFAAHs7PqSmZbzzdbPJiIgk48m6H18WZhzwbCLSg49dTx7OTuHFsyeQolGkZZ5A1smCd77P64k2Ka74NvwhWD5SepIk4f70BPK/qNhXfMDPg9WzE4pVRCJSiY9dT840nsfphmZsedbxan0NRuP+hS+8nmiP4qY6g9EozMaD99OUZRkPfnDCYDTidEPzex9jMhoQiHBqgkjvPnY9AQCDwYDM7DwE9/bw09Kjfd/n9UR7FFd8iSYTItLBC03n79xEKBhEXUsnjMb3x49KMpLM3H2BSO8+dj15mwwZezu+fV/n9UR7FFd8OdYEhKPSe7/348xt7Pq3Uf91F0wf2HE9EpWQlcq9+Yj07qDrSSgQwJr7KSKRMGRZxubaC6w9X8aJ3Px9j+X1RHsU9xlfRa715y2EotI7H0gHdnewsvwYRpMRN/725zdfr/6qFflflL359+tthypyrfGMTUQKdND1BAbgp6VH+HH2NiDLSEpJxen6JuQWFL/zfF5PtEmRN7APz6/B5d7CyYyjbze2thVAY0kG77shIgC8ntB+ipvqBIDGLzIhyfKR750JhKOQZRn1RZmxCUZEqsPrCf2aIosv25qIb+oLse4LHnqwvt5b7zf1hdxeiIjeeH09WfH4sfpy46OP9/l88Gz5eD3RMEUWHwCczk/D7xqL8GonhLWtACIHLHiJRCWsbu3BuxPihrJE9F6n89OQH3iGF698H72evPDu4oe5H/FNbR6vJxqlyM/43rbpD8L1kxezz7xvdmAwGQ2IvnV+VmNJJuqLeH4WEb3fgwcP8PDhQ1y42I+5le2PXk98Tx8gK8WCCxcuiI5OMaD44nvt9YnJnp0QApEokswmZKXyxGQi+rDt7W385S9/wW9/+1tkZmYC+Pj1JBQK4U9/+hO6urpQXFz84Rcg1VFN8RERHZUsy/jrX/+KsrIy1NfXH+m5brcbY2Nj+Md//EckJPA+Pi1R7Gd8RESfa25uDgBQV1d35OcWFxejpKQETqfzuGORYCw+ItIkr9eLmZkZ2O12GAwf3q/zIK2trVhdXcXTp0+POR2JxOIjIs2RJAkOhwNNTU1IT0//5J9jsVhgs9kwPj6OQCBwjAlJJBYfEWmOy+WCxWLBl19++dk/q6CgAKdOncLExMQxJCMlYPERkaZ4PB64XC7YbLZPnuL8tfPnz2NzcxNPnjw5lp9HYrH4iEgzJEnCyMgIWltbYbUe38bSZrMZdrsdExMT2NvbO7afS2Kw+IhIM+7cuYPU1FScOXPm2H92Xl4ezpw5g7GxsWP/2RRfLD4i0oT19XU8ePAAXV1dMXuNpqYm+Hw+LCwsxOw1KPZYfESketFoFA6HA+3t7UhJSYnZ65hMJtjtdty8eRM7Ozsxex2KLRYfEane9PQ0MjMzUVlZGfPXysnJQW1tLUZHR2P+WhQbLD4iUrW1tTU8evQorhtKNzY2IhAIYH5+Pm6vSceHxUdEqhWJROBwONDR0YHk5OS4va7RaER3dzempqbg8/ni9rp0PFh8RKRat2/fRm5uLsrLy+P+2idOnEBDQwMcDge417+6sPiISJVWVlawtLSEjo4OYRnq6+shSRLu378vLAMdHYuPiFQnHA5jdHQUnZ2dSEwUdwC1wWCA3W7HnTt3sLW1JSwHHQ2Lj4hUZ3JyEkVFRSgpKREdBRkZGTh37hynPFWExUdEqvL8+XO43W58/fXXoqO8cfbsWZhMJrhcLtFR6BBYfESkGsFgEGNjY7DZbIo6Fd1gMMBms+Hu3bvweDyi49BHsPiISDWcTifKyspQVFQkOso+aWlpaGlpgcPhgCRJouPQB7D4iEgVlpeXsba2htbWVtFRDlRdXY3k5GTMzs6KjkIfwOIjIsULBAK4ceMG7HY7zGaz6Dgf1NXVhbm5OWxsbIiOQgdg8RGR4t24cQOVlZXIz88XHeWjUlNT0dbWBofDgWg0KjoOvQeLj4gUbXFxER6PB+fPnxcd5dCqqqqQnp6OH374QXQUeg8WHxEp1u7uLpxOJ7q7u2EymUTHOZLOzk48fPgQL1++FB2FfoXFR0SKNTY2hurqauTm5oqOcmTJycno6OjAyMgIIpGI6Dj0FhYfESnSwsIC/H4/mpqaREf5ZBUVFcjJycHU1JToKPQWFh8RKY7f78fNmzfR3d0No1Hdl6mOjg4sLi7ixYsXoqPQ36l7RBGRJo2NjaGurg7Z2dmio3y2pKQkdHZ2wuFwIBwOi45DYPERkcI8ePAAwWAQDQ0NoqMcm9LSUhQUFODWrVuioxBYfESkINvb25ientbEFOevtbe349mzZ3C73aKj6J62RhYRqZYsyxgdHUVjYyMyMzNFxzl2CQkJ6OrqwtjYGEKhkOg4usbiIyJFmJubgyzLqKurEx0lZoqLi1FSUgKn0yk6iq6x+IhIOK/Xi5mZGdjtdhgMBtFxYqq1tRWrq6t4+vSp6Ci6xeIjIqEkSYLD4UBTUxPS09NFx4k5i8UCm82G8fFxBAIB0XF0icVHREK5XC5YLBZ8+eWXoqPETUFBAU6dOoWJiQnRUXSJxUdEwng8HrhcLthsNs1Pcf7a+fPnsbm5iSdPnoiOojssPiIS4vUUZ0tLC6xWq+g4cWc2m2G32zExMYG9vT3RcXSFxUdEQty5cwcpKSmorq4WHUWYvLw8nDlzBuPj46Kj6AqLj4jibmNjAw8ePEBXV5foKMI1NTVhe3sbjx49Eh1FN1h8RBRX0WgUIyMjaG9vR0pKiug4wplMJtjtdkxOTmJnZ0d0HF1g8RFRXE1PTyMzMxOVlZWioyhGTk4OamtrMTo6KjqKLrD4iChu1tbWsLCwgAsXLoiOojiNjY0IBAKYn58XHUXzWHxEFBeRSAQOhwMXLlxAcnKy6DiKYzQa0d3djampKfh8PtFxNI3FR0Rxcfv2beTm5qK8vFx0FMU6ceIEGhoaMDo6ClmWRcfRLBYfEcXcysoKlpaW0NHRITqK4tXX1yMajeL+/fuio2gWi4+IYiocDmN0dBSdnZ1ITEwUHUfxDAYD7HY77ty5g62tLdFxNInFR0QxNTk5icLCQpSUlIiOohoZGRk4d+4cHA4HpzxjgMVHRDHz/PlzuN1utLW1iY6iOmfPnoXJZILL5RIdRXNYfEQUE8FgEGNjY7DZbEhISBAdR3UMBgNsNhvu3r2LV69eiY6jKSw+IooJp9OJsrIyFBUViY6iWmlpaWhpacHIyAgkSRIdRzNYfER07JaXl7G2tobW1lbRUVSvuroaycnJmJ2dFR1FM1h8RHSsAoEAbty4AbvdDrPZLDqOJnR1dWFubg4bGxuio2gCi4+IjtWNGzdQWVmJ/Px80VE0IzU1FW1tbXA4HIhGo6LjqB6Lj4iOzeLiIjweD5qbm0VH0Zyqqiqkp6fjhx9+EB1F9Vh8RHQsdnd34XQ6OcUZQ52dnXj48CFevnwpOoqqsfiI6FiMjY2huroaeXl5oqNoVnJyMjo6OjAyMoJIJCI6jmqx+Ijosy0sLMDv96OpqUl0FM2rqKhATk4OpqamREdRLRYfEX0Wv9+Pmzdvoru7G0YjLynx0NHRgcXFRbx48UJ0FFXiKCWizzI2Noa6ujpkZ2eLjqIbSUlJ6OzshMPhQDgcFh1HdVh8RPTJHjx4gGAwiIaGBtFRdKe0tBQFBQW4deuW6Ciqw+Ijok+yvb2N6elpTnEK1N7ejmfPnsHtdouOoiocrUR0ZLIsY3R0FI2NjcjMzBQdR7cSEhLQ1dWFsbExhEIh0XFUg8VHREc2NzcHWZZRV1cnOoruFRcXo6SkBE6nU3QU1WDxEdGReL1ezMzMwG63w2AwiI5DAFpbW7G6uoqnT5+KjqIKLD4iOjRJkuBwONDU1IT09HTRcejvLBYLbDYbxsfHEQgERMdRPBYfER2ay+WC2WzGl19+KToK/UpBQQFOnTqFiYkJ0VEUj8VHRIfi8Xjgcrk4xalg58+fx+bmJp48eSI6iqKx+Ijoo15Pcba0tMBqtYqOQwcwm82w2+2YmJjA3t6e6DiKxeIjoo+6c+cOUlJSUF1dLToKfUReXh7OnDmD8fFx0VEUi8VHRB+0sbGBBw8eoKurS3QUOqSmpiZsb2/j0aNHoqMoEouPiA4UjUYxMjKC9vZ2pKSkiI5Dh2QymWC32zE5OYmdnR3RcRSHxUdEB5qenkZmZiYqKytFR6EjysnJQW1tLUZHR0VHURwWHxG919raGhYWFnDhwgXRUegTNTY2IhAIYH5+XnQURWHxEdE+kUgEDocDFy5cQHJysug49ImMRiO6u7sxNTUFn88nOo5isPiIaJ/bt28jNzcX5eXloqPQZzpx4gQaGhowOjoKWZZFx1EEFh8RvWNlZQVLS0vo6OgQHYWOSX19PaLRKO7fvy86iiKw+IjojXA4jNHRUXR2diIxMVF0HDomBoMBdrsdd+7cwdbWlug4wrH4iOiNyclJFBUVoaSkRHQUOmYZGRk4d+4cHA6H7qc8WXxEBAB4/vw53G43vv76a9FRKEbOnj0Lk8kEl8slOopQLD4iQjAYxNjYGGw2GxISEkTHoRgxGAyw2Wy4e/cuPB6P6DjCsPiICE6nE2VlZSgqKhIdhWIsLS0NLS0tcDgckCRJdBwhWHxEOre8vIy1tTW0traKjkJxUl1djeTkZMzOzoqOIgSLj0jHAoEAbty4AbvdDrPZLDoOxVFXVxfm5uawsbEhOkrcsfiIdOzGjRuorKxEfn6+6CgUZ6mpqWhra4PD4UA0GhUdJ65YfEQ6tbi4CI/Hg/Pnz4uOQoJUVVUhPT0dP/zwg+goccXiI9Kh3d1dOJ1OdHd3w2QyiY5DAnV2duLhw4d4+fKl6Chxw+Ij0qGxsTFUV1cjNzdXdBQSLDk5GR0dHRgZGUEkEhEdJy5YfEQ6s7CwAL/fj6amJtFRSCEqKiqQk5ODqakp0VHigsVHpCN+vx83b95Ed3c3jEb++tMvOjo6sLi4iBcvXoiOEnMc+UQ6MjY2hrq6OmRnZ4uOQgqTlJSEzs5OOBwOhMNh0XFiisVHpBMPHjxAMBhEQ0OD6CikUKWlpSgoKMCtW7dER4kpFh+RDmxvb2N6eppTnPRR7e3tePbsGdxut+goMcPfACKNk2UZo6OjaGxsRGZmpug4pHAJCQno6urC2NgYQqGQ6DgxweIj0ri5uTnIsoy6ujrRUUgliouLUVJSAqfTKTpKTLD4iDRod3cXAOD1ejEzMwO73Q6DwSA4FalJa2srVldX8fTpUwC/jCktMMh6P4qXSGNkWca///u/o6qqCqFQCLW1tTh79qzoWKRCL168wNDQEIqKijA5OYl/+Zd/0cR0ObdjJ9KYnZ0dbG1t4W9/+xsikQiam5tFRyKVMplMmJubw9WrV1FaWoqtrS1NFB+nOok0Znt7G8FgEJFIBNnZ2fjuu+90tQ8jHY9QKITvvvsOwWAQqamp2Nrawvb2tuhYx4LFR6QxXq8XCwsLMJvNqKiowO9//3vk5eWJjkUqk5CQgH/+539Ga2srkpOTsbi4iJWVFdGxjgU/4yNSmUA4iifrfmz4QwhGo0g0mZBjTUBFrhVJFhP+9Kc/4X//93/xr//6rzh79izv26PPtry8jP/8z/9ETk4O/vCHPwD4+DhUMhYfkUps+oOYfe7FXbcXEUmGxWSE2WhARJIRiUowGw1o+CITp7MTkZOWhKSkJNGRSUOi0Sh8Ph+i5uRDjcOG4kxkWxNFx34vFh+RCiys+vBX1wqMBgOyrQkwm/a/i4tEJWz6Q5BkGd/UF+J0fpqApKRlWhmHLD4ihVtY9eHPM27kpScdagopEI5i3RfE7xqLFHnRIXXS0jhk8REp2KY/iO+cyziRmvDei82ufxu3r/8NuYVf4Gxzx5uvB8JReHdC+Kf2MsVON5F6HDQO74x/j+1XGwB+3hwhMTkFbZe+efN9pY5D3sdHpGCzz70wGgwH/oW9cHcaaZn7jxhKsphgMBjg+smL7jMnYx2TNO5D4/B0fTMKyyrf+zyljkMu9yJSqEA4irtuL7KtCe/9/pr7KcyWBGTl5r/3+9nWBMw+8yIQjsYyJmncx8bhxyhxHLL4iBTqybofEUl+/wKCcAhP5l2orDt34PPNJiMikown6/5YxiSN+9A4BIDFB3cx/rf/i+nRIbxaX9v3fSWOQ051EinUhj8EywEXmyfzLhSUViApOeWDP8NsMsKzo82jZSg+PjQOT51tRGp6BowGI9Z+egrXzVGc776CFOu7i1mUNg75jo9IoYLRKMzG/Scq+LZe4dX6Gkoqaz76M0xGAwIR5UwxkfocNA4BICMrB2azBUaTCQUlFcjIysHm2v7dXZQ2DvmOj0ihEk0mRKT9i65fra9hb8ePicG/AACikTAAGVMjAzjffeWdx0YlGUlmZe+iQcp20Dh8rwOOvlLaOGTxESlUjjUB4ai07+tFZZU4WVz65t/PHs0jsLuDM43n9z02EpWQlfppixKIgIPHYSQcwpZnEydy8gCDAS9/egbvxkucrm/a/1iFjUMWH5FCVeRaf94KKiq9s7DAZDbDZP7lV/fnqSYjEhLf3aLs9fZRFbnWuGUm7TloHEqShCfzd7Hr2wYMBqSmpaOutQsp1vR3nq/Eccgb2IkUbHh+DS73Fk5mHH3fzbWtABpLMhR1/xSpk9bGIRe3EClY4xeZkGT5yPdABcJRyLKM+qLM2AQjXdHaOGTxESlYtjUR39QXYt0XPPRF5/Ueib+pL1TUNlGkXlobh5zqJFKBw+6Kv+EPAjLwG4Xuik/qppVxyOIjUolNfxCun7yYfeZ9s5OGyWhA9K1z0BpLMlFfpNxz0Ej9tDAOWXxEKvP65GvPTgiBSBRJZhOyUtVx8jVph5rHIYuPiIh0hYtbiIhIV1h8RESkKyw+IiLSFRYfERHpCouPiIh0hcVHRES6wuIjIiJdYfEREZGusPiIiEhXWHxERKQrLD4iItIVFh8REekKi4+IiHSFxUdERLrC4iMiIl1h8RERka6w+IiISFdYfEREpCssPiIi0hUWHxER6QqLj4iIdOX/A9clE1X5IKntAAAAAElFTkSuQmCC", + "text/plain": [ + "<Figure size 432x288 with 1 Axes>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "from EoN import hierarchy_pos\n", + "\n", + "def draw_tree(tree):\n", + " G = nx.DiGraph()\n", + " add_edges(tree, G)\n", + " pos = hierarchy_pos(G)\n", + " labels = {1:1,2:2,3:3,4:4,5:5}\n", + " # get_labels(tree, labels)\n", + " nx.draw(G, pos, labels=labels, alpha=0.4)\n", + "\n", + "draw_tree(t)" + ] + }, + { + "cell_type": "markdown", + "metadata": { + "id": "WMUbIIbN4XAu" + }, + "source": [ + "## Tree traversal \n", + "This is the question of how to visit each of the nodes in a tree **exactly once.**\n", + "1. Visit current node and **process node** check if node is a leaf or some other stopping condition. \n", + "2. Iterate across branches and recurse down. \n", + " Often you can use `for ` loop or `list` comprehensions for branch iterations and recursion to go down.\n", + "3. Combination of recursive call returns are used to determine the final result of your probelm. ***ex: find sum of all labels in a tree -- it is not sufficient to just use recursive call, but must also process the label values***. \n", + "\n", + "The above functions are okay, but we can place all of the abstraction into a class. This allows for easy passage of data and storage. It will be a proper *ADT* in the eyes of *the Greater Will*.\n" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "id": "wJjuOEHY11yU" + }, + "outputs": [], + "source": [ + "class Tree: \n", + " def __init__(s, label, branches= []):\n", + " s.label = label\n", + " s.branches = branches\n", + " def is_leaf(s):\n", + " return not s.branches\n", + " def __repr__(self):\n", + " return f\"[ {self.label}, {', '.join([ b.__repr__() for b in self.branches ])} END ]\"\n" + ] + }, + { + "cell_type": "markdown", + "metadata": { + "id": "bNrbEpGE6kiF" + }, + "source": [ + "Following are several examples which you need to solve in class. " + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "id": "hRFRKYn26jz_" + }, + "outputs": [], + "source": [ + "def count_leaves(t):\n", + " '''Write a function that counts the number of leaves in a given Tree t'''\n", + " if t.is_leaf():\n", + " return 1\n", + " else:\n", + " c = 0\n", + " for n in t.branches:\n", + " c += count_leaves(n)\n", + " return c\n" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/" + }, + "id": "rGC1q4LV13NT", + "outputId": "b1311681-fa7a-440f-f12c-184233686ed1" + }, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "t = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)])])\n", + "count_leaves(t) == 3" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/" + }, + "id": "YMbFu3zw2F3r", + "outputId": "24ac5e26-87f4-4294-ab16-ab469091caa1" + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[1, 2, [3]]" + ] + }, + "execution_count": 9, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def list_of_leaves(t):\n", + " '''Returns a list of leaves of a tree '''\n", + " if t.is_leaf():\n", + " return [t.label]\n", + " else:\n", + " return sum([ list_of_leaves(b) for b in t.branches ], [])\n", + "#HINT:\n", + "sum([ [1], [2, [3]]],[])" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/" + }, + "id": "FjKnywx-9VBF", + "outputId": "02391553-29a9-4f1d-e9d1-5e7557a96765" + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "[2, 4, 5]\n" + ] + }, + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "print(list_of_leaves(t))\n", + "list_of_leaves(t) == [2,4,5]" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "id": "BvZbzWH49_pl" + }, + "outputs": [], + "source": [ + "def fib_tree(n):\n", + " if n == 0 or n == 1:\n", + " return Tree(n)\n", + " s = Tree(n, [fib_tree(n-1), fib_tree(n-2)])\n", + " s.label = sum([b.label for b in s.branches])\n", + " return s" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/" + }, + "id": "vjYVr2v1_1e0", + "outputId": "09fb48fa-632c-4c44-898b-55643b173e1b" + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[ 5, [ 3, [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ], [ 1, [ 1, END ], [ 0, END ] END ] END ], [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ] END ]" + ] + }, + "execution_count": 22, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "fibt = fib_tree(5)\n", + "fibt\n", + "# Fix the labeling system that is hardcoded above to dynamically given level\n", + "# labels to this tree so it can be plotted - get_labels(t)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "id": "HlA744R9_4P0" + }, + "outputs": [], + "source": [ + "def counting_paths(t, total): # reduce total by current tree.label each time\n", + " '''Count the # of paths from root to any node in the tree for which the labels\n", + " sum up to the total'''\n", + " if t.label == total: \n", + " return 1\n", + " else:\n", + " return sum([ counting_paths(b, total - t.label) for b in t.branches])" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/" + }, + "id": "MiYhj6CZxWcW", + "outputId": "276a9307-33dc-45c3-cb35-46d6d37d13be" + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1\n", + "2\n", + "2\n", + "3\n", + "1\n", + "0\n", + "0\n" + ] + } + ], + "source": [ + "fibt = fib_tree(5)\n", + "c = counting_paths(fibt, 12)\n", + "assert c == 1\n", + "print(c)\n", + "fibt = fib_tree(5)\n", + "c = counting_paths(fibt, 11)\n", + "assert c == 2\n", + "print(c)\n", + "c = counting_paths(fibt, 9)\n", + "assert c == 2\n", + "print(c)\n", + "fibt = fib_tree(5)\n", + "c = counting_paths(fibt, 8)\n", + "assert c == 3\n", + "print(c)\n", + "c = counting_paths(fibt, 5)\n", + "assert c == 1\n", + "print(c)\n", + "c = counting_paths(fibt, 4)\n", + "assert c == 0\n", + "print(c)\n", + "c = counting_paths(fibt, 400)\n", + "assert c == 0\n", + "print(c)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "id": "TtRqJUivASO1" + }, + "outputs": [], + "source": [ + "def tripler(t):\n", + " ''' Triple the value of the labels of each node in the tree'''\n", + " t.label *= 3\n", + " if t.is_leaf():\n", + " return\n", + " else:\n", + " [ tripler(b) for b in t.branches ]" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "colab": { + "base_uri": "https://localhost:8080/" + }, + "id": "LuUh4r4zBWQ9", + "outputId": "819b7853-8021-4f8e-a7d4-37f91196e45d" + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "[ 5, [ 3, [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ], [ 1, [ 1, END ], [ 0, END ] END ] END ], [ 2, [ 1, [ 1, END ], [ 0, END ] END ], [ 1, END ] END ] END ]\n", + "[ 15, [ 9, [ 6, [ 3, [ 3, END ], [ 0, END ] END ], [ 3, END ] END ], [ 3, [ 3, END ], [ 0, END ] END ] END ], [ 6, [ 3, [ 3, END ], [ 0, END ] END ], [ 3, END ] END ] END ]\n" + ] + } + ], + "source": [ + "fibt = fib_tree(5)\n", + "print(fibt)\n", + "tripler(fibt)\n", + "print(fibt)" + ] + } + ], + "metadata": { + "colab": { + "provenance": [] + }, + "kernelspec": { + "display_name": "Python 3.9.6 64-bit", + "language": "python", + "name": "python3" + }, + "language_info": { + "codemirror_mode": { + "name": "ipython", + "version": 3 + }, + "file_extension": ".py", + "mimetype": "text/x-python", + "name": "python", + "nbconvert_exporter": "python", + "pygments_lexer": "ipython3", + "version": "3.9.6" + }, + "vscode": { + "interpreter": { + "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6" + } + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/hw6/.DS_Store b/hw6/.DS_Store Binary files differnew file mode 100644 index 0000000..5008ddf --- /dev/null +++ b/hw6/.DS_Store |