DSA_Midterm_Lab.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "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.7.6"
    },
    "colab": {
      "name": "DSA Midterm Lab.ipynb",
      "provenance": [],
      "collapsed_sections": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Op_ms0XfgxKD",
        "colab_type": "text"
      },
      "source": [
        "# DSA Practice Programming Lab\n",
        "The goal of this lab is to review the concepts seen in class so far, and to use some of the tools not already implemented for homework. This will be a good starting point to prepare for the midterm exam so make notes of any questions/areas that you find more difficult. \n",
        "\n",
        "The first few questions were taken from Cracking the Coding Interview, 6th edition. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k4MFGssSgxKG",
        "colab_type": "text"
      },
      "source": [
        "## Question 1: \n",
        "Given a short string $s1$ and a long string $s2$, write a function that counts how many permutations of $s1$ are found in $s2$. Also, give the runtime analysis (should be O($n1*n2$) where $n1$ is the length of $s1$ and $n2$ is the length of $s2$). This is roughly linear in $n2$ if $n1$ is small. \n",
        "\n",
        "Example: Your function should return three permutations for $s1$ = 'ab', $s2$ = 'baba' (starting at indices 0, 1, 2)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SdETm41-SQtB",
        "colab_type": "code",
        "outputId": "3aa5e15d-10c1-48a6-f584-ecbe75c79b55",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "s1 = 'ab'\n",
        "s2 = 'baba'\n",
        "\n",
        "def perm_finder(s1, s2):\n",
        "\n",
        "  perm_counter = 0 # O(1)\n",
        "  s1_sum = 0 # O(1)\n",
        "  enc = {} # O(1)\n",
        "  ord_a = ord('a') # O(1)\n",
        "  for index in range(0,26): # O(25) - Constant runtime\n",
        "    enc[ord_a + index] = 2**index + 1000000\n",
        "  \n",
        "  for char in s1: # O(n1)\n",
        "    s1_sum += enc[ord(char)]\n",
        "  \n",
        "  for ind in range(len(s2)): #O(n2)\n",
        "    temp_sum = 0 \n",
        "    current_combination = s2[ind : ind + len(s1)]\n",
        "    \n",
        "    for comb_char in current_combination:\n",
        "      temp_sum += enc[ord(comb_char)]\n",
        "\n",
        "    if temp_sum == s1_sum:\n",
        "      perm_counter += 1\n",
        "\n",
        "  return perm_counter\n",
        "\n",
        "perm_finder(s1, s2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 39
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A105GiqTj2nt",
        "colab_type": "text"
      },
      "source": [
        "We have mentioned the runtime anaylsis for each of the steps as comments in the program. Starting off of that, we can say that this program runs in linear-ish runtime, considering the relative magnitudes of n1 and n2 - theoretically it will be O(n1*n2) for this program. We map each letter to a unique hash then when we sum them up, there is in theory only one sum of characters that matches any other sum of characters. This way, we don't care about order in permutations, but we still campture all permutations in a reasonably efficient runtime."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iX658_-XgxKL",
        "colab_type": "text"
      },
      "source": [
        "## Question 2: \n",
        "Given a list $l$ of integers and an integer value $x$, write a function that finds a pair of indices $i,j$ ($i \\neq j$) such that $l[i]+l[j] = x$. Your runtime should be O($n$), where $n$ is the length of $l$.\n",
        "\n",
        "Example: Your function should return 0,2 for $l = [3, -4, 1, 5, 2, 4]$ and $x = 4$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DJdupAZqgxKM",
        "colab_type": "code",
        "outputId": "0707bef1-5d25-42dd-8a12-f03df1d9a548",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def find_pair(l, x):\n",
        "  list_dict = {}\n",
        "  sum_sub = {}\n",
        "  count = 0\n",
        "  indicies = []\n",
        "\n",
        "  # fill a dict with the list and a second with the sum-list and no repeats\n",
        "  for i in range(len(l)):\n",
        "    if (list_dict.get(i) == None):\n",
        "      list_dict[i] = l[i]\n",
        "      sum_sub[x - l[i]] = i\n",
        "      count += 1\n",
        "      indicies.append(i)\n",
        "\n",
        "  for i in range(count):\n",
        "    # check if the number that adds to the sum is in the other dict and they aren't the same index\n",
        "    if (sum_sub.get(list_dict.get(indicies[i])) != None and indicies[i] != sum_sub.get(list_dict.get(indicies[i]))):\n",
        "      return [indicies[i], sum_sub.get(list_dict.get(indicies[i]))]\n",
        "\n",
        "l = [3, -4, 1, 5, 2, 4]\n",
        "x = 4\n",
        "print (find_pair(l, x))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0, 2]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gg-17h0sEerc",
        "colab_type": "text"
      },
      "source": [
        "This function works by creating a dictionary filled with the list and a second dictionary with the sum minus the list. If you know one number, there is only one other number that adds to the sum and by creating these two dictionaries, you can check if the complement that adds to the sum exists or not. Then, by keeping track of the indicies and ensuring there are no duplicates, you can check in O(1) time if there is a complement while looping through the dict in O(n) time --> O(2n) --> O(n) time overall"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eAp8aO27gxKQ",
        "colab_type": "text"
      },
      "source": [
        "## Question 3: \n",
        "Write a function that takes in two lists $l1$ and $l2$ and returns whether $l2$ is a rotation of $l1$ in $O(n1+n2)$ time, where $n1$ is the length of $l1$ and $n2$ is the length of $l2$. \n",
        "\n",
        "Example: Your function should return True for $11 = [h,e,l,l,o]$, $l2 = [e,l,l,o,h]$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Fr0QbHUGgxKR",
        "colab_type": "code",
        "outputId": "54880d4f-c764-436f-8c6c-a6c5cf457657",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def rotation(l1, l2):\n",
        "\n",
        "  # Intializes two empty strings\n",
        "  sl1 = \"\"\n",
        "  sl2 = \"\"\n",
        "  \n",
        "  # Creates a string from all the elements in list 1\n",
        "  for char in l1:\n",
        "    sl1 += char\n",
        "\n",
        "  # Creates a string from all the elements in list 2\n",
        "  for char in l2:\n",
        "    sl2 += char\n",
        "\n",
        "  # Concatenation occurs here\n",
        "  sl2 += sl2\n",
        "  if sl1 in sl2:\n",
        "    return True\n",
        "  \n",
        "l1 = ['h','e','l','l','o']\n",
        "l2 = ['e','l','l','o','h']\n",
        "(rotation(l1, l2))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "07ew2e6uP0jd",
        "colab_type": "text"
      },
      "source": [
        "For the function 'rotation,' we used the .includes function in the Python library, which checks for if the given string is included in another string in O(n) runtime. We have created two strings, one containg the elements of l1, the other containg elements of l2. The concatenation trick here is to concatenate l2 to itself, to create a string as follows:\n",
        "if l1 = \"sparsh\" and l2 = \"rshspa\"\n",
        "concatenated l2 = \"rshsparshspa\"\n",
        "We can observe that if l2 is a rotation of l1, we will have at least one occurence of l1 in concatenated l2. On this new list, we run the includes function and print the result."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4nXrcbaUgxKU",
        "colab_type": "text"
      },
      "source": [
        "## Question 4: \n",
        "Given a list $l$ that is a rotation of a sorted list, write a function that returns the index with the minimum element in O($log n$), where $n$ is the length of $l$.\n",
        "\n",
        "Example: Your function should return 3 for $l = [4.5, 6, 8.2, 0, 1.3, 1.4]$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LFL7TShtgxKV",
        "colab_type": "code",
        "outputId": "c356a37a-03ea-4649-de9a-6d66e58d1d78",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        }
      },
      "source": [
        "def min_index_sorted(l):\n",
        "  # finds the min index of a rotated sorted list\n",
        "  offset = 0\n",
        "\n",
        "  while(len(l) > 1):\n",
        "    # cut in half every time\n",
        "    cur_index = (int)(len(l)/2)\n",
        "    if(l[cur_index - 1] > l[cur_index]):\n",
        "      # found the correct min index\n",
        "      return cur_index + offset\n",
        "    elif(l[-1] < l[cur_index]):\n",
        "      # move to the right side\n",
        "      offset += cur_index\n",
        "      l = l[cur_index:]\n",
        "    else:\n",
        "      l = l[:cur_index]\n",
        "  \n",
        "  # case where the list is sorted and not rotated\n",
        "  return 0\n",
        "\n",
        "l = [1, 3, 6, 7, 8, 9, 11]\n",
        "print(min_index_sorted(l))\n",
        "\n",
        "l = [3, 5, 7, 9, 11, 2]\n",
        "print(min_index_sorted(l))\n",
        "\n",
        "l = [5, 6, 1, 2, 3, 4]\n",
        "print(min_index_sorted(l))\n",
        "\n",
        "l = [4, 5, 6, 1, 2, 3]\n",
        "print(min_index_sorted(l))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n",
            "5\n",
            "2\n",
            "3\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BHBYjUVt5pJe",
        "colab_type": "text"
      },
      "source": [
        "Theoretically, we are going to iterate through and cut the list in half every time while searching for a minimum. The way we know if we have found the minimum is based on if the element to the left of that index is greater than the element we are focused on. We know this because the list is a rotation of a sorted list. Furthermore, we can decide if we need to focus on the left or right side based on the last element of the list. Following this until we find an element creates an O(logn) time function that finds the minimum index. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b4wMg6ZWgxKY",
        "colab_type": "text"
      },
      "source": [
        "## Question 5: \n",
        "Implement an in-place version of Merge Sort using the doubly linked list class you implemented for homework 2."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "p0vmJ4JtgxKZ",
        "colab_type": "code",
        "outputId": "25ffb9c1-4041-4c75-d2bc-096fbe38a8db",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Defines a single node\n",
        "class Node:\n",
        "    def __init__(self,val=None,next=None,prev=None):\n",
        "        # Value stored in the list element\n",
        "        self.val = val\n",
        "        # Pointer to the next node\n",
        "        self.next = next\n",
        "        # Pointer to the previous node\n",
        "        self.prev = prev\n",
        "\n",
        "class DLL:\n",
        "    def __init__(self,head=None,tail=None,length=None):\n",
        "        ''' Constructor for an empty list '''\n",
        "        self.head = None\n",
        "        self.tail = None\n",
        "        self.len = 0\n",
        "        # Recommendation - good thing to use sentinal nodes\n",
        "\n",
        "    def length(self):\n",
        "        ''' Returns the number of nodes in the list '''\n",
        "        # Method 1 - Iteration through the list - bigger O time\n",
        "        # than mantaining self.len during pushes and deletes\n",
        "        # \n",
        "        # i = self.head\n",
        "        # count = 0\n",
        "        # while i.next:\n",
        "        #     i = i.next\n",
        "        #     count +=1\n",
        "        # return count\n",
        "\n",
        "        # Method 2 - This class keeps track of the count as functions are called\n",
        "        return self.len\n",
        "\n",
        "    def push(self, val):\n",
        "        ''' Adds a node with value equal to val to the front of the list '''\n",
        "\n",
        "        new = Node(val)\n",
        "        # Case I - when the list does not contain nodes with values\n",
        "        if self.len == 0:\n",
        "            self.head = new\n",
        "            self.len += 1\n",
        "            self.tail = new\n",
        "\n",
        "        # Case II - when the list contains only one node with a value\n",
        "        elif self.len == 1:\n",
        "            new.next = self.head\n",
        "            self.head.prev = new\n",
        "            self.head = new\n",
        "            self.tail = new.next\n",
        "            self.tail.prev = self.head\n",
        "            self.len += 1\n",
        "\n",
        "        # All other cases\n",
        "        else:\n",
        "            new.next = self.head\n",
        "            self.head.prev = new\n",
        "            self.head = new\n",
        "            self.len += 1\n",
        "\n",
        "    def insert_after(self, prev_node, val):\n",
        "        ''' Adds a node with value equal to val in the list after prev_node '''\n",
        "        # Case for lengh = 0\n",
        "        new = Node(val)\n",
        "        # Case I - If the node after prev_node is the tail\n",
        "        if prev_node == self.tail:\n",
        "            prev_node.next = new\n",
        "            new.next = None\n",
        "            new.prev = prev_node\n",
        "            self.tail = new\n",
        "            self.len += 1\n",
        "\n",
        "        # All other cases\n",
        "        else:\n",
        "            new.next = prev_node.next\n",
        "            prev_node.next = new\n",
        "            new.prev = prev_node\n",
        "            new.next.prev = new\n",
        "            self.len += 1\n",
        "\n",
        "    def delete(self, node):\n",
        "        ''' Removes node from the list '''\n",
        "\n",
        "        #Case 0 : Case with one node\n",
        "        # Case I - If the given node is the head of the list\n",
        "        if node == self.head:\n",
        "            self.head = self.head.next\n",
        "            self.head.prev = None\n",
        "            self.len -= 1\n",
        "        \n",
        "        # Case II - if the given node is the tail of the list\n",
        "        elif node == self.tail:\n",
        "            self.tail = self.tail.prev\n",
        "            self.tail.next = None\n",
        "            self.len -= 1\n",
        "        \n",
        "        # All other cases\n",
        "        else: \n",
        "            prev_node = node.prev\n",
        "            next_node = node.next\n",
        "            prev_node.next = next_node\n",
        "            next_node.prev = prev_node\n",
        "            self.len -= 1\n",
        "        \n",
        "    def index(self, i):\n",
        "        ''' Returns the node at position i (i<n) '''\n",
        "        # Include the cases for negative numbers and greater than the length\n",
        "        n = self.head\n",
        "        while i != 0:\n",
        "            n = n.next\n",
        "            i -= 1\n",
        "               \n",
        "        return n\n",
        "\n",
        "    def multiply_all_pairs(self):\n",
        "        ''' Multiplies all unique pairs of nodes values for nodes i, j (i != j) \n",
        "        and returns the sum '''\n",
        "\n",
        "        # A nested for loop that mulitplies each node with every other node,\n",
        "        # and then subtracts the product of each node with itself to come\n",
        "        # up with the required multiplication. The last process is to divide\n",
        "        # the result by the number of (nodes - 1)\n",
        "        # The mathematical function used: (a + b + ....)^2\n",
        "\n",
        "        # Method 1\n",
        "        # sum = 0\n",
        "        # for i in range(self.len):\n",
        "        #     node = self.index(i)\n",
        "        #     sum -= ((node.val)**2)\n",
        "        #     for j in range(self.len):\n",
        "        #         sum += ((node.val)*((self.index(j)).val))\n",
        "        # return sum/2\n",
        "\n",
        "        # Method 2\n",
        "        sum = 0\n",
        "        subsum = 0\n",
        "        for i in range(self.len):\n",
        "            node = self.index(i)\n",
        "            subsum += node.val\n",
        "            sum -= ((node.val)**2)\n",
        "        sum += subsum**2\n",
        "        return sum/2    \n",
        "\n",
        "    def listmaker(self):\n",
        "        '''\n",
        "        Acknowledgement for the idea of generating this function - Casey May\n",
        "        '''\n",
        "\n",
        "        lst = []\n",
        "        n = self.head\n",
        "        while n != None:\n",
        "            lst.append(n.val)\n",
        "            n = n.next\n",
        "        return lst\n",
        "\n",
        "      # Credits: https://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/\n",
        "      # Function to merge two linked list\n",
        "    def merge(self, a, b): \n",
        "        \n",
        "\n",
        "        # If first linked sublist is empty \n",
        "        if a is None: \n",
        "            return b  \n",
        "          \n",
        "        # If secon linked sublist is empty  \n",
        "        if b is None: \n",
        "            return a \n",
        "  \n",
        "        # Pick the smaller value \n",
        "        if a.val < b.val: \n",
        "            a.next = self.merge(a.next, b) \n",
        "            a.next.prev = a \n",
        "            a.prev = None   \n",
        "            return a \n",
        "        else: \n",
        "            b.next = self.merge(a, b.next) \n",
        "            b.next.prev = b \n",
        "            b.prev = None\n",
        "            return b\n",
        "\n",
        "    # Function to do merge sort\n",
        "    \n",
        "    def mergeSort(self, temp_head):\n",
        "        \"\"\"\n",
        "\n",
        "        \"\"\"\n",
        "        \n",
        "        # Checks if the length of the list or sublist is of length 0 - the two\n",
        "        # if loops check for both even and odd lengths.\n",
        "        if temp_head is None:  \n",
        "            return temp_head \n",
        "        \n",
        "        if temp_head.next is None: \n",
        "            return temp_head \n",
        "        \n",
        "\n",
        "        second = self.split(temp_head) \n",
        "          \n",
        "        # Recur for left and righ halves \n",
        "        temp_head = self.mergeSort(temp_head) \n",
        "        second = self.mergeSort(second) \n",
        "  \n",
        "        # Merge the two sorted halves \n",
        "        return self.merge(temp_head, second) \n",
        "  \n",
        "    # Split the doubly linked list (DLL) into two DLLs \n",
        "    # of half sizes \n",
        "    def split(self, tempHead): \n",
        "        \"\"\"\n",
        "\n",
        "\n",
        "        \"\"\"\n",
        "        \n",
        "        fast = slow =  tempHead \n",
        "        while(True): \n",
        "            # The while loops carries on until the value fast is assigned to the\n",
        "            # last or the second to last element of the list or a sublist based\n",
        "            # on if its length is even or odd\n",
        "            if fast.next is None: \n",
        "                break\n",
        "            if fast.next.next is None: \n",
        "                break\n",
        "            fast = fast.next.next \n",
        "            slow = slow.next\n",
        "        \n",
        "        # Stores the temporary node to split the list at this node\n",
        "        # by reassinging the \n",
        "        temp = slow.next\n",
        "        slow.next = None\n",
        "        return temp \n",
        "\n",
        "# Driver program to test the above functions \n",
        "dll = DLL() \n",
        "dll.push(60) \n",
        "dll.push(17); \n",
        "dll.push(9); \n",
        "dll.push(30); \n",
        "dll.push(700) \n",
        "dll.push(109); \n",
        "dll.head = dll.mergeSort(dll.head)\n",
        "dll.listmaker()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[9, 17, 30, 60, 109, 700]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 49
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c4ksvehXgxKh",
        "colab_type": "text"
      },
      "source": [
        "# Challenges \n",
        "Pick at least one of the following challenges. I recommend the first one if you'd like to practice divide-and-conquer algorithms."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ju_g9coggxKi",
        "colab_type": "text"
      },
      "source": [
        "## Challenge 1 - Skyline Problem\n",
        "Given a list of buildings including their positions and heights, find the skyline visible using a divide-and-conquer approach. See image below for a skyline example. First, you should think about how you will represent a building and how you will represent the outputted skyline. You may assume all buildings are rectangular (what a boring city). "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i7QnyNhNgxKj",
        "colab_type": "code",
        "outputId": "22cdb7b0-019e-415e-caca-47d63482839b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 282
        }
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "plt.step([i for i in range(12)], [0,0,2,2,3,3,2,0,5,4,4,0])"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[<matplotlib.lines.Line2D at 0x7ffae6dd7d68>]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 20
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0\ndHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAMEElEQVR4nO3dXYxcBRnG8eexW8NnRdNKli3rckEw\nKwlbM6EgxmBRUwVZL4yFBkIMZrkQBSUh4A3hwsQLQ/DCmG4AIeE7fKRIEGn4CCGp1S2s2k4xEoTS\nZbBLCC54IYKvFzOFpU7Z0+05c96d/n9Js/NxOvOedvqfs2fP9DgiBADI62N1DwAA+GiEGgCSI9QA\nkByhBoDkCDUAJDdQxYOuXLkyRkZGqnhoAOhL27dvfz0iVnW7r5JQj4yMaGpqqoqHBoC+ZPvlA93H\nrg8ASI5QA0ByhBoAkiPUAJAcoQaA5Aod9WH7JUlvSXpP0rsR0ahyKADABw7m8LwvR8TrlU0CAOiq\nkuOoASzOndt2a/P0TE+fc3xsSBvXDvf0OXFwiu6jDkmP2d5ue6LbArYnbE/ZnpqdnS1vQuAwsnl6\nRs3WXM+er9ma6/kbAw5e0S3qL0bEjO1PS9pi+/mIeHr+AhExKWlSkhqNBmcjABZpdHCF7rnszJ48\n14ZNW3vyPDg0hbaoI2Km83WvpAclnV7lUACADywYattH2z5232VJX5O0o+rBAABtRXZ9HC/pQdv7\nlr8zIh6tdCoAwPsWDHVEvCjptB7MAgDogk8mAkByhBoAkiPUAJAcoQaA5Ag1ACRHqAEgOUINAMkR\nagBIjlADQHKEGgCSI9QAkByhBoDkCDUAJEeoASA5Qg0AyRFqAEiOUANAcoQaAJIj1ACQHKEGgOQI\nNQAkR6gBIDlCDQDJEWoASI5QA0ByhBoAkiPUAJAcoQaA5Ag1ACRHqAEgOUINAMkVDrXtZbafs/1w\nlQMBAD7sYLaor5C0q6pBAADdDRRZyPZqSedK+qmkH1c6EYCearbmtGHT1rrHqMT42JA2rh2ue4xD\nVijUkm6UdLWkYw+0gO0JSROSNDy89P9ggMPB+NhQ3SNUptmak6TDI9S2z5O0NyK22z77QMtFxKSk\nSUlqNBpR2oQAKrNx7XBfhKybfvouocg+6rMknW/7JUl3S1pn+/ZKpwIAvG/BUEfEtRGxOiJGJF0g\n6YmIuKjyyQAAkjiOGgDSK/rDRElSRDwl6alKJgEAdMUWNQAkR6gBIDlCDQDJEWoASI5QA0ByhBoA\nkiPUAJAcoQaA5Ag1ACRHqAEgOUINAMkRagBIjlADQHKEGgCSI9QAkByhBoDkCDUAJEeoASA5Qg0A\nyRFqAEiOUANAcoQaAJIj1ACQHKEGgOQINQAkR6gBIDlCDQDJEWoASI5QA0ByhBoAklsw1LaPsP0H\n23+yvdP29b0YDADQNlBgmX9LWhcRb9teLukZ27+NiN9XPBsAQAVCHREh6e3O1eWdX1HlUDh0d27b\nrc3TM3WPUZnxsSFtXDtc9xhATxTaR217me1pSXslbYmIbV2WmbA9ZXtqdna27DlxkDZPz6jZmqt7\njEo0W3N9/SYE7K/Irg9FxHuSxmwfJ+lB26dGxI79lpmUNClJjUaDLe4ERgdX6J7Lzqx7jNJt2LS1\n7hGAnjqooz4i4k1JT0paX804AID9FTnqY1VnS1q2j5T0VUnPVz0YAKCtyK6PQUm32V6mdtjvjYiH\nqx0LALBPkaM+/ixpTQ9mAQB0wScTASA5Qg0AyRFqAEiOUANAcoQaAJIj1ACQHKEGgOQINQAkR6gB\nIDlCDQDJEWoASI5QA0ByhBoAkiPUAJAcoQaA5Ag1ACRHqAEgOUINAMkRagBIjlADQHKEGgCSI9QA\nkByhBoDkCDUAJEeoASA5Qg0AyRFqAEiOUANAcoQaAJIj1ACQHKEGgOQWDLXtE20/abtpe6ftK3ox\nGACgbaDAMu9KuioinrV9rKTttrdERLPi2QAAKhDqiGhJanUuv2V7l6QhSUs61Hdu263N0zN1j1GZ\nZmtOo4Mr6h6jMs3WnDZs2tqz5xsfG9LGtcM9ez5gvoPaR217RNIaSdu63Ddhe8r21OzsbDnTVWjz\n9Iyarbm6x6jM6OAKjY8N1T1GJcbHhnr6JtRszfX1mzryK7LrQ5Jk+xhJ90u6MiL+r3ARMSlpUpIa\njUaUNmGFRgdX6J7Lzqx7DBykjWuHe7p128std6CbQlvUtperHek7IuKBakcCAMxX5KgPS7pZ0q6I\nuKH6kQAA8xXZoj5L0sWS1tme7vz6RsVzAQA6ihz18Ywk92AWAEAXfDIRAJIj1ACQHKEGgOQINQAk\nR6gBIDlCDQDJEWoASI5QA0ByhBoAkiPUAJAcoQaA5Ag1ACRHqAEgOUINAMkRagBIjlADQHKEGgCS\nI9QAkByhBoDkCDUAJEeoASA5Qg0AyRFqAEiOUANAcoQaAJIj1ACQHKEGgOQINQAkR6gBIDlCDQDJ\nLRhq27fY3mt7Ry8GAgB8WJEt6lslra94DgDAASwY6oh4WtIbPZgFANBFafuobU/YnrI9NTs7W9bD\nAsBhr7RQR8RkRDQiorFq1aqyHhYADnsc9QEAyRFqAEiuyOF5d0naKukU23tsX1r9WACAfQYWWiAi\nLuzFIACA7tj1AQDJEWoASI5QA0ByhBoAkiPUAJAcoQaA5Ag1ACRHqAEgOUINAMkRagBIjlADQHKE\nGgCSI9QAkByhBoDkCDUAJEeoASA5Qg0AyRFqAEiOUANAcoQaAJIj1ACQHKEGgOQINQAkR6gBIDlC\nDQDJEWoASI5QA0ByhBoAkiPUAJAcoQaA5Ag1ACRXKNS219v+q+0XbF9T9VAAgA8sGGrbyyT9UtLX\nJY1KutD2aNWDAQDaBgosc7qkFyLiRUmyfbekcUnNsoe5/jc71Xx1ruyH7arZmtPo4IqePBeWvmZr\nThs2be3J8/C6LE+v/t72GT1hha775udKf9wioR6S9Mq863skrd1/IdsTkiYkaXh4uJThqjQ6uELj\nY0N1j4EloJevE16X5emnP0dHxEcvYH9b0vqI+F7n+sWS1kbE5Qf6PY1GI6ampkodFAD6me3tEdHo\ndl+RHybOSDpx3vXVndsAAD1QJNR/lHSy7ZNsf1zSBZIeqnYsAMA+C+6jjoh3bV8u6XeSlkm6JSJ2\nVj4ZAEBSsR8mKiIekfRIxbMAALrgk4kAkByhBoDkCDUAJEeoASC5BT/wsqgHtWclvbzI375S0usl\njpMJ67Z09fP6sW45fCYiVnW7o5JQHwrbUwf6dM5Sx7otXf28fqxbfuz6AIDkCDUAJJcx1JN1D1Ah\n1m3p6uf1Y92SS7ePGgDwYRm3qAEA8xBqAEguTaj7+QS6tk+0/aTtpu2dtq+oe6ay2V5m+znbD9c9\nS5lsH2f7PtvP295l+8y6ZyqT7R91XpM7bN9l+4i6Z1os27fY3mt7x7zbPmV7i+2/db5+ss4ZFytF\nqA+DE+i+K+mqiBiVdIak7/fZ+knSFZJ21T1EBX4h6dGI+Kyk09RH62h7SNIPJTUi4lS1/xvjC+qd\n6pDcKmn9frddI+nxiDhZ0uOd60tOilBr3gl0I+IdSftOoNsXIqIVEc92Lr+l9j/2vjmhm+3Vks6V\ndFPds5TJ9ickfUnSzZIUEe9ExJv1TlW6AUlH2h6QdJSkV2ueZ9Ei4mlJb+x387ik2zqXb5P0rZ4O\nVZIsoe52At2+Cdl8tkckrZG0rd5JSnWjpKsl/bfuQUp2kqRZSb/u7Na5yfbRdQ9VloiYkfRzSbsl\ntST9MyIeq3eq0h0fEa3O5dckHV/nMIuVJdSHBdvHSLpf0pURMVf3PGWwfZ6kvRGxve5ZKjAg6fOS\nfhURayT9S0v0W+duOvtrx9V+QzpB0tG2L6p3qupE+1jkJXk8cpZQ9/0JdG0vVzvSd0TEA3XPU6Kz\nJJ1v+yW1d1mts317vSOVZo+kPRGx77uf+9QOd7/4iqS/R8RsRPxH0gOSvlDzTGX7h+1BSep83Vvz\nPIuSJdR9fQJd21Z7P+euiLih7nnKFBHXRsTqiBhR++/tiYjoi62yiHhN0iu2T+ncdI6kZo0jlW23\npDNsH9V5jZ6jPvphacdDki7pXL5E0uYaZ1m0QudMrNphcALdsyRdLOkvtqc7t/2kcy5K5PYDSXd0\nNiBelPTdmucpTURss32fpGfVPjLpOS3hj1zbvkvS2ZJW2t4j6TpJP5N0r+1L1f6vl79T34SLx0fI\nASC5LLs+AAAHQKgBIDlCDQDJEWoASI5QA0ByhBoAkiPUAJDc/wAeear0K+tB0AAAAABJRU5ErkJg\ngg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "c-gGUIKQgxKn",
        "colab_type": "code",
        "outputId": "627bd8d7-d3a6-4b64-dcdc-4c8c057eafeb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# building = (left, right, height)\n",
        "## WE used help from dieter to build this\n",
        "buildings = [(1,6,7), (3,8,9), (7,10,2), (10,13,12)]\n",
        "\n",
        "def skyline(buildings):\n",
        "  # list of skylines by new coordinates\n",
        "\n",
        "  # base case where there is only one building\n",
        "  if len(buildings) == 1:\n",
        "    l, r, h = buildings[0]\n",
        "    return [(l, h), (r, 0)]\n",
        "\n",
        "  mid = len(buildings) // 2\n",
        "  left = skyline(buildings[:mid])\n",
        "  right = skyline(buildings[mid:])\n",
        "\n",
        "  return merge_skylines(left, right)\n",
        "  \n",
        "def merge_skylines(left, right):\n",
        "  # takes two skylines and merges them\n",
        "  # height trackers for skyline 1 and 2\n",
        "  hl = hr = 0\n",
        "  i = j = 0\n",
        "  current_height = 0\n",
        "  new_skyline = []\n",
        "\n",
        "  # loop through significant elements\n",
        "  while i < len(left) and j < len(right):\n",
        "    # get left positions\n",
        "    left_x = left[i][0]\n",
        "    right_x = right[j][0]\n",
        "\n",
        "    # find the relative heights for left and right skyline\n",
        "    if (left_x <= right_x):\n",
        "      hl = left[i][1]\n",
        "      i += 1\n",
        "    if (right_x <= left_x):\n",
        "      hr = right[j][1]\n",
        "      j += 1\n",
        "\n",
        "    # check if there is a new max height and update current height\n",
        "    if (max(hr,hl) != current_height):\n",
        "      current_height = max(hr, hl)\n",
        "      new_skyline.append((min(right_x, left_x), current_height))\n",
        "\n",
        "  # add the excess if one of the skylines has no more elements\n",
        "  new_skyline.extend(right[j:])\n",
        "  new_skyline.extend(left[i:])\n",
        "  return new_skyline\n",
        "\n",
        "            \n",
        "skyline(buildings)\n"
      ],
      "execution_count": 34,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 7), (3, 9), (8, 2), (10, 12), (13, 0)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YPYy4aW5PcD8",
        "colab_type": "text"
      },
      "source": [
        "In this case, we are using a mergesort-esque function that splits buildings down until they are a bunch of individual buildings by cutting in half and then building back up. While cutting in half, we are running through the list in O(logn) time, but in every iteration, we have to iterate through a list of all the building elements which can be up to n points, making the runtime O(nlogn). "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A4A7KJ_1gxKr",
        "colab_type": "text"
      },
      "source": [
        "## Challenge 2 - Minesweeper\n",
        "Design an object class to represent the game of minesweeper. Think about how the way you represent the game will impact the runtime of updating the grid. You may also want to allow the user to start a game with different difficulty levels. \n",
        "\n",
        "If you want to add some funk, think about how you can change the structure or elements of the game (maybe the landscape isn't a grid? are there fun surprises to uncover?)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i9Ycil05gxKs",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}