D&C.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from random import seed\n",
    "from random import randint\n",
    "import numpy as np                    #Para trabajar con matrices\n",
    "from binarytree import tree, build    #Para trabajar con árboles\n",
    "\n",
    "#Función para generar arreglos de enteros para tests\n",
    "def generarRandomArr(a, b, size):   #Rango [a,b]\n",
    "    arr = []\n",
    "    for _ in range(size):\n",
    "        valor = randint(a, b)\n",
    "        arr.append(valor)\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Práctica"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 1\n",
    "Escriba un algoritmo con dividir y conquistar que determine si un arreglo de tamaño potencia de 2 es *más\n",
    "a la izquierda*, donde \"más a la izquierda\" significa que:\n",
    "La suma de los elementos de la mitad izquierda superan los de la mitad derecha.\n",
    "- Cada una de las mitades es a su vez \"más a la izquierda\".\n",
    "- Por ejemplo, el arreglo \\[8, 6, 7, 4, 5, 1, 3, 2\\] es \"más a la izquierda\", pero \\[8, 4, 7, 6, 5, 1, 3, 2\\] no lo es.\n",
    "\n",
    "Intente que su solución aproveche la técnica de modo que la complejidad del algoritmo sea estrictamente menor a O(n<sup>2</sup>)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def masALaIzq(A):        #Devuelve una tupla (res: bool, sumaizq: int, sumader: int)\n",
    "    if len(A) == 2:\n",
    "        if A[0] > A[1]:\n",
    "            return (True, A[0], A[1])\n",
    "        else:\n",
    "            return (False, A[0], A[1])\n",
    "    \n",
    "    R1 = masALaIzq(A[0:len(A)//2])          #T(n/2)\n",
    "    R2 = masALaIzq(A[len(A)//2:len(A)])     #T(n/2)\n",
    "    sumaR1 = R1[1] + R1[2]\n",
    "    sumaR2 = R2[1] + R2[2]\n",
    "    \n",
    "    return (R1[0] and R2[0] and sumaR1 > sumaR2, sumaR1, sumaR2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado test 1:  (True, 25, 11)\n",
      "Resultado test 2:  (False, 25, 11)\n",
      "Resultado test 3:  (False, 27, 29)\n",
      "Resultado test 4:  (True, 12, 11)\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A = [8, 6, 7, 4, 5, 1, 3, 2]    #Resultado esperado: True\n",
    "print(\"Resultado test 1: \", masALaIzq(A))\n",
    "\n",
    "B = [8, 4, 7, 6, 5, 1, 3, 2]    #Resultado esperado: False\n",
    "print(\"Resultado test 2: \", masALaIzq(B))\n",
    "\n",
    "C = [2, 10, 9, 6, 9, 9, 5, 6]   #Resultado esperado: False\n",
    "print(\"Resultado test 3: \", masALaIzq(C))\n",
    "\n",
    "D = [10, 2, 6, 5]               #Resultado esperado: True\n",
    "print(\"Resultado test 4: \", masALaIzq(D))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: La recurrencia es de la forma T(n) = 2 T(n/2) + O(1). Por el Teorema Maestro, la complejidad es O(n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 2\n",
    "Tenemos un arreglo a = \\[a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>\\] de n enteros distintos (positivos y negativos) en orden estrictamente creciente. Queremos determinar si existe una posición i tal que a<sub>i</sub> = i. Por ejemplo, dado el arreglo A = \\[-4, -1, 2, 4, 7\\], i = 4 es esa posición.\n",
    "Diseñar un algoritmo dividir y conquistar eficiente (de complejidad de orden estrictamente menor que lineal) que resuelva el problema. Calcule y justifique la complejidad del algoritmo dado.\n",
    "\n",
    "**Aclaración**: en el ejemplo, la primera posición del arreglo es i = 1. Aquí se considerará que la primera posición es i = 0 y, por lo tanto, el resultado esperado del ejemplo de arriba sería *False*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def buscarIndIgualContenido(A, posInicial):   #Devuelve bool\n",
    "    if len(A) == 1:\n",
    "        return A[0] == posInicial\n",
    "    \n",
    "    m = len(A)//2\n",
    "    if A[m] < m + posInicial:\n",
    "        return buscarIndIgualContenido(A[m:len(A)], m + posInicial)\n",
    "    elif A[m] > m + posInicial:\n",
    "        return buscarIndIgualContenido(A[0:m], 0 + posInicial)\n",
    "    else:\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado test 1:  True\n",
      "Resultado test 2:  False\n",
      "Resultado test 3:  True\n",
      "Resultado test 4:  True\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A = [-4, -1, 2, 4, 7]    #Resultado esperado: True\n",
    "print(\"Resultado test 1: \", buscarIndIgualContenido(A, 0))\n",
    "\n",
    "B = [-4, -1, 4, 5, 7, 8]    #Resultado esperado: False\n",
    "print(\"Resultado test 2: \", buscarIndIgualContenido(B, 0))\n",
    "\n",
    "C = [-1, 0, 1, 2, 3, 5]    #Resultado esperado: True\n",
    "print(\"Resultado test 3: \", buscarIndIgualContenido(C, 0))\n",
    "\n",
    "D = [0, 2, 3, 4, 7, 8]    #Resultado esperado: True\n",
    "print(\"Resultado test 4: \", buscarIndIgualContenido(D, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: La recurrencia es de la forma T(n) = T(n/2) + O(1). Por el Teorema Maestro, la complejidad es O(log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 3\n",
    "Encuentre un algoritmo para calcular a<sup>b</sup> en tiempo logarítmico en b. Piense cómo reutilizar los resultados ya calculados. Justifique la complejidad del algoritmo dado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def potencia(b, p):\n",
    "    if p == 0:\n",
    "        return 1\n",
    "    elif p == 1:\n",
    "        return b\n",
    "    \n",
    "    r = potencia(b, p//2)    #T(p/2)\n",
    "    if p % 2 == 0:\n",
    "        return r*r\n",
    "    else:\n",
    "        return b*r*r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3^3 =  27\n",
      "2^5 =  32\n",
      "5^0 =  1\n",
      "5^1 =  5\n",
      "5^3 =  125\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "print(\"3^3 = \", potencia(3, 3))\n",
    "print(\"2^5 = \", potencia(2, 5))\n",
    "print(\"5^0 = \", potencia(5, 0))\n",
    "print(\"5^1 = \", potencia(5, 1))\n",
    "print(\"5^3 = \", potencia(5, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: La recurrencia es de la forma T(p) = T(p/2) + O(1). Por el Teorema Maestro, la complejidad es O(log p)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 5\n",
    "Suponga que se tiene un método *potencia* que, dada un matriz cuadrada A de orden 4 × 4 y un número *n*,\n",
    "computa la matriz A<sup>n</sup>. Dada una matriz cuadrada A de orden 4 × 4 y un número natural *n* que es potencia de 2 (i.e., n = 2<sup>k</sup> para algun k ≥ 1), desarrollar, utilizando la técnica de dividir y conquistar y el método *potencia*, un algoritmo que permita calcular A<sup>1</sup> + A<sup>2</sup> + ... + A<sup>n</sup>.\n",
    "Calcule el número de veces que el algoritmo propuesto aplica el método *potencia*. Si no es estrictamente menor que O(n), resuelva el ejercicio nuevamente.\n",
    "\n",
    "**Idea:**\n",
    "F(1) = A </br>\n",
    "F(2) = A + A² = A(I + A) </br>\n",
    "F(4) = A + A² + A³ + A⁴ = (A + A²)(I + A²) = A(I + A)(I + A²) = F(2)(I + A²) </br>\n",
    "Forma general: F(n) = F(n/2)*(I + A^(n/2)) </br>\n",
    "(Tomada de https://stackoverflow.com/questions/18890570/matrix-power-sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def sumaPotenciasMatriz(A, n):\n",
    "    if n == 1:\n",
    "        return A\n",
    "    if n == 2:      \n",
    "        return np.add(A, np.linalg.matrix_power(A, 2))  #np.linalg.matrix_power(A, n): método potencia\n",
    "    \n",
    "    I = [[1, 0, 0, 0],     # matriz identidad\n",
    "         [0, 1, 0, 0],\n",
    "         [0, 0, 1, 0],\n",
    "         [0, 0, 0, 1]]\n",
    "    I = np.array(I)        #np.add, suma de matrices, np.matmul: producto de matrices\n",
    "    S = np.add(I, np.linalg.matrix_power(A, n//2))      #Suma matriz identidad + potencia n/2\n",
    "    return np.matmul(sumaPotenciasMatriz(A, n//2), S)   #T(n/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado esperado:\n",
      " [[  7  19  29  40]\n",
      " [ 14  49  72 103]\n",
      " [  8  37  57  73]\n",
      " [  9  50  70 103]]\n",
      "Resultado:\n",
      " [[  7  19  29  40]\n",
      " [ 14  49  72 103]\n",
      " [  8  37  57  73]\n",
      " [  9  50  70 103]]\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A = [[1, 0, 0, 1],\n",
    "     [2, 0, 1, 2],\n",
    "     [-1, 1, 0, 2],\n",
    "     [0, 1, 2, 1]]\n",
    "A = np.array(A)\n",
    "A2 = np.linalg.matrix_power(A, 2)\n",
    "A3 = np.linalg.matrix_power(A, 3)\n",
    "A4 = np.linalg.matrix_power(A, 4)\n",
    "sum1 = np.add(A, A2)\n",
    "sum2 = np.add(A3, A4)\n",
    "print(\"Resultado esperado:\\n\", np.add(sum1, sum2))\n",
    "print(\"Resultado:\\n\", sumaPotenciasMatriz(A, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: La recurrencia tiene la forma T(n) = T(n/2) + O(1), donde n es la cantidad de veces que se aplica el método *potencia*. Por el Teorema Maestro, la complejidad es O(log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 6\n",
    "Dado un árbol binario cualquiera, diseñar un algoritmo de dividir y conquistar que devuelva la máxima distancia entre dos nodos (es decir, máxima cantidad de ejes a atravesar). El algoritmo no debe hacer recorridos innecesarios sobre el árbol."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def maxDistanciaSubarb(A):\n",
    "    if A == None:\n",
    "        return 0\n",
    "    if A.left == None and A.right == None:\n",
    "        return 1\n",
    "\n",
    "    return 1 + max(maxDistanciaSubarb(A.left), maxDistanciaSubarb(A.right))\n",
    "\n",
    "def maxDistancia(A):\n",
    "    if A == None:\n",
    "        return 0\n",
    "    elif A.left == None:\n",
    "        return max(maxDistancia(A.right), 1 + maxDistanciaSubarb(A.right))\n",
    "    elif A.right == None:\n",
    "        return max(maxDistancia(A.left), 1 + maxDistanciaSubarb(A.left))\n",
    "    else:\n",
    "        return 1 + maxDistanciaSubarb(A.left) + maxDistanciaSubarb(A.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    __1__\n",
      "   /     \\\n",
      "  2       3\n",
      " / \\     /\n",
      "4   5   6\n",
      "\n",
      "Resultado test 1: 5\n",
      "\n",
      "     _____12____\n",
      "    /           \\\n",
      "  _10__          14\n",
      " /     \\        /  \\\n",
      "13      4      5    8\n",
      "       /      /\n",
      "      3      9\n",
      "\n",
      "Resultado random test 1: 7\n",
      "\n",
      "       __0___\n",
      "      /      \\\n",
      "    _7       _11\n",
      "   /  \\     /   \\\n",
      "  13   5   14    10\n",
      " /                 \\\n",
      "9                   12\n",
      "\n",
      "Resultado random test 2: 7\n",
      "\n",
      "         _______13_____\n",
      "        /              \\\n",
      "     __8___          ___2__\n",
      "    /      \\        /      \\\n",
      "  _3       _7      9        1\n",
      " /  \\     /  \\      \\      / \\\n",
      "11   6   14   0      12   5   10\n",
      "\n",
      "Resultado random test 3: 7\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "valuesA = [1,2,3,4,5,6]\n",
    "A = build(valuesA)\n",
    "print(A)\n",
    "print(\"Resultado test 1:\", maxDistancia(A))\n",
    "                                        \n",
    "B = tree(is_perfect=False)\n",
    "print(B)\n",
    "print(\"Resultado random test 1:\", maxDistancia(B))\n",
    "\n",
    "C = tree(is_perfect=False)\n",
    "print(C)\n",
    "print(\"Resultado random test 2:\", maxDistancia(C))\n",
    "\n",
    "D = tree(is_perfect=False)\n",
    "print(D)\n",
    "print(\"Resultado random test 3:\", maxDistancia(D))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 7\n",
    "La cantidad de parejas en desorden de un arreglo A\\[1...n\\] es la cantidad de parejas de posiciones 1 ≤ i <\n",
    "j ≤ n tales que A\\[i\\] > A\\[j\\]. Dar un algoritmo que calcule la cantidad de parejas en desorden de un arreglo\n",
    "y cuya complejidad temporal sea estrictamente mejor que O(n<sup>2</sup>) en el peor caso.\n",
    "\n",
    "**Hint**: Considerar hacer una modificación de un algoritmo de sorting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parejasEnDesorden(A):   #Devuelve una tupla con el arreglo ordenado y la cantidad de parejas en desorden\n",
    "    if len(A) == 1:\n",
    "        return (A, 0)\n",
    "    elif len(A) == 2:\n",
    "        if A[0] <= A[1]:\n",
    "            return (A, 0)\n",
    "        else:\n",
    "            return ([A[1],A[0]], 1)\n",
    "    \n",
    "    r1 = parejasEnDesorden(A[0:len(A)//2])\n",
    "    r2 = parejasEnDesorden(A[len(A)//2:len(A)])\n",
    "    A1 = r1[0]\n",
    "    A2 = r2[0]\n",
    "    cont = r1[1] + r2[1]\n",
    "    i = 0  #Índice para recorrer A1\n",
    "    j = 0  #Índice para recorrer A2\n",
    "    res = []\n",
    "    while (i < len(A1) and j < len(A2)):\n",
    "        if (A1[i] <= A2[j]):\n",
    "            res.append(A1[i])\n",
    "            i+=1\n",
    "        else:\n",
    "            res.append(A2[j])\n",
    "            j+=1\n",
    "            cont+=len(A1)-i\n",
    "    while (i < len(A1)):\n",
    "        res.append(A1[i])\n",
    "        i+=1\n",
    "    while (j < len(A2)):\n",
    "        res.append(A2[j])\n",
    "        j+=1\n",
    "    return (res, cont)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Caso de test 1: [1, 4, 3, 2, 5, 7, 6]\n",
      "Resultado test 1: 4 \n",
      "\n",
      "Caso de test 2: [1, 2, 3, 4, 5, 6, 7]\n",
      "Resultado test 2: 0 \n",
      "\n",
      "Caso de test 3: [4, -2, -2, 1, 1, -1, -1, -1]\n",
      "Resultado test 3: 13 \n",
      "\n",
      "Caso de test 4: [1, 9, 6, 4, 5]\n",
      "Resultado test 4: 5 \n",
      "\n",
      "Caso de test random 1: [3, 3, -1, 0, 2, 4, 0, 4]\n",
      "Resultado test random 1: 10 \n",
      "\n",
      "Caso de test random 2: [14, 12, 4, 8, 1]\n",
      "Resultado test random 2: 9 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "A = [1,4,3,2,5,7,6]  #Resultado: 4 (las parejas en desorden son: (4,3), (4,2), (3,2), (7,6))\n",
    "print(\"Caso de test 1:\", A)\n",
    "print(\"Resultado test 1:\", parejasEnDesorden(A)[1], \"\\n\")\n",
    "\n",
    "B = [1,2,3,4,5,6,7] #Resultado: 0\n",
    "print(\"Caso de test 2:\", B)\n",
    "print(\"Resultado test 2:\", parejasEnDesorden(B)[1], \"\\n\")\n",
    "\n",
    "C = [4, -2, -2, 1, 1, -1, -1, -1]   #Resultado: 13\n",
    "print(\"Caso de test 3:\", C)\n",
    "print(\"Resultado test 3:\", parejasEnDesorden(C)[1], \"\\n\")\n",
    "\n",
    "D = [1, 9, 6, 4, 5]\n",
    "print(\"Caso de test 4:\", D)   #Resultado: 5\n",
    "print(\"Resultado test 4:\", parejasEnDesorden(D)[1], \"\\n\")\n",
    "\n",
    "E = generarRandomArr(-2,5,8)\n",
    "print(\"Caso de test random 1:\", E)\n",
    "print(\"Resultado test random 1:\", parejasEnDesorden(E)[1], \"\\n\")\n",
    "\n",
    "F = generarRandomArr(1,20,5)\n",
    "print(\"Caso de test random 2:\", F)\n",
    "print(\"Resultado test random 2:\", parejasEnDesorden(F)[1], \"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 8\n",
    "Se tiene una matriz booleana A de n × n y una operación *conjunciónSubmatriz* que toma O(1) y que dados\n",
    "4 enteros i<sub>0</sub>, i<sub>1</sub>, j<sub>0</sub>, j<sub>1</sub> devuelve la conjunción de todos los elementos en la submatriz que toma las filas i<sub>0</sub> hasta i<sub>1</sub> y las columnas j<sub>0</sub> hasta j<sub>1</sub>.\n",
    "1. Dar un algoritmo que tome tiempo estrictamente menor que O(n<sup>2</sup>) que calcule la posición de algún *false*, asumiendo que hay al menos uno. Calcular y justificar la complejidad del algoritmo.\n",
    "2. Modificar el algoritmo anterior para que cuente cuántos *false* hay en la matriz. Asumiendo que hay a lo sumo 5 elementos *false* en toda la matriz, calcular y justificar la complejidad del algoritmo.\n",
    "\n",
    "Si obtuvo una complejidad O(n<sup>2</sup>) en el punto anterior, mejore el algoritmo y/o el cálculo para obtener una complejidad menor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def conjuncionSubmatriz(A, i0, i1, j0, j1):\n",
    "    if i1 - i0 == 0 and j1 - j0 == 0:\n",
    "        return A[i0][j0]\n",
    "    res = True\n",
    "    while i0 <= i1:\n",
    "        k0 = j0\n",
    "        while k0 <= j1:\n",
    "            res = res and A[i0][k0]\n",
    "            k0 += 1\n",
    "        i0 += 1\n",
    "    return res              #Complejidad: O(n²), pero se asume que es O(1) por el enunciado\n",
    "\n",
    "#1\n",
    "def posicionFalse(A, i0, i1, j0, j1):\n",
    "    if i1 - i0 == 0 and j1 - j0 == 0:\n",
    "        return (i0, j0)\n",
    "    \n",
    "    n = i1 - i0 + 1\n",
    "    if conjuncionSubmatriz(A, 0+i0, n//2+i0-1, 0+j0, n//2+j0-1) == False:       #T(n/2)\n",
    "        return posicionFalse(A, 0+i0, n//2+i0-1, 0+j0, n//2+j0-1)\n",
    "    elif conjuncionSubmatriz(A, 0+i0, n//2+i0-1, n//2+j0, n+j0-1) == False:     #T(n/2)\n",
    "        return posicionFalse(A, 0+i0, n//2+i0-1, n//2+j0, n+j0-1)\n",
    "    elif conjuncionSubmatriz(A, n//2+i0, n+i0-1, 0+j0, n//2+j0-1) == False:     #T(n/2)\n",
    "        return posicionFalse(A, n//2+i0, n+i0-1, 0+j0, n//2+j0-1)\n",
    "    else:\n",
    "        return posicionFalse(A, n//2+i0, n+i0-1, n//2+j0, n+j0-1)               #T(n/2)\n",
    "\n",
    "#2\n",
    "def contarFalse(A, i0, i1, j0, j1):\n",
    "    if i1 - i0 == 0 and j1 - j0 == 0:\n",
    "        if A[i0][j0] == True:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "    \n",
    "    n = i1 - i0 + 1\n",
    "    m1, m2, m3, m4 = 0, 0, 0, 0\n",
    "    if conjuncionSubmatriz(A, 0+i0, n//2+i0-1, 0+j0, n//2+j0-1) == False:\n",
    "        m1 = contarFalse(A, 0+i0, n//2+i0-1, 0+j0, n//2+j0-1)\n",
    "    if conjuncionSubmatriz(A, 0+i0, n//2+i0-1, n//2+j0, n+j0-1) == False:\n",
    "        m2 = contarFalse(A, 0+i0, n//2+i0-1, n//2+j0, n+j0-1)\n",
    "    if conjuncionSubmatriz(A, n//2+i0, n+i0-1, 0+j0, n//2+j0-1) == False:\n",
    "        m3 = contarFalse(A, n//2+i0, n+i0-1, 0+j0, n//2+j0-1)\n",
    "    if conjuncionSubmatriz(A, n//2+i0, n+i0-1, n//2+j0, n+j0-1) == False:\n",
    "        m4 = contarFalse(A, n//2+i0, n+i0-1, n//2+j0, n+j0-1)\n",
    "    \n",
    "    return m1 + m2 + m3 + m4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Matriz de 4x4\n",
      "Posición False: (1, 0)\n",
      "Cantidad de False: 4\n",
      "Matriz de 8x8\n",
      "Posición False: (2, 1)\n",
      "Cantidad de False: 5\n",
      "Matriz de 6x6\n",
      "Posición False: (2, 3)\n",
      "Cantidad de False: 3\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A = [[True, True, False, True],\n",
    "     [False, True, True, True],\n",
    "     [True, False, True, True],\n",
    "     [True, True, True, False]]\n",
    "print(\"Matriz de 4x4\")\n",
    "print(\"Posición False:\", posicionFalse(A, 0, 3, 0, 3))\n",
    "print(\"Cantidad de False:\", contarFalse(A, 0, 3, 0, 3))\n",
    "\n",
    "B = [[True, True, True, True, True, True, True, True],\n",
    "     [True, True, True, True, True, False, True, True],\n",
    "     [True, False, True, True, True, True, True, True],\n",
    "     [True, True, True, True, True, True, True, True],\n",
    "     [True, True, True, True, True, True, True, True],\n",
    "     [True, True, False, True, True, True, True, False],\n",
    "     [True, True, True, True, True, True, True, True],\n",
    "     [True, True, False, True, True, True, True, True]]\n",
    "\n",
    "print(\"Matriz de 8x8\")\n",
    "print(\"Posición False:\", posicionFalse(B, 0, 7, 0, 7))\n",
    "print(\"Cantidad de False:\", contarFalse(B, 0, 7, 0, 7))\n",
    "\n",
    "C = [[True, True, True, True, True, True],\n",
    "     [True, True, True, True, True, False],\n",
    "     [True, True, True, False, True, True],\n",
    "     [True, True, True, True, True, True],\n",
    "     [True, True, True, True, True, True],\n",
    "     [True, True, False, True, True, True]]\n",
    "\n",
    "print(\"Matriz de 6x6\")\n",
    "print(\"Posición False:\", posicionFalse(C, 0, 5, 0, 5))\n",
    "print(\"Cantidad de False:\", contarFalse(C, 0, 5, 0, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad de *posicionFalse***: T(n) = T(n/2) + O(1). Por el segundo caso del Teorema Maestro, la complejidad es O(log n).\n",
    "**Complejidad de *contarFalse***: En el peor caso, en la primera vuelta de recursión se llama a contarFalse en los 4 casos, pero en la segunda solo se puede volver llamar hasta 5 veces (porque hay un máximo de 5 falsos). Por lo tanto, en todos los llamados sucesivos va a haber a lo sumo 5 llamados, y en cada uno de esos 5 sigue haciendo la recursión hasta encontrar el False y sumarlo. Como se asume que *conjuncionSubmatriz* cuesta O(1), la complejidad del algoritmo es O(log n) (se puede observar haciendo un árbol de recursión)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 9\n",
    "Dados dos arreglos de naturales, ambos ordenados de manera creciente, se desea buscar, dada una posición i, el i-ésimo elemento de la unión de ambos. Dicho de otra forma, el i-ésimo del resultado de hacer merge ordenado entre ambos arreglos. Notar que no es necesario hacer el merge completo. Se puede asumir que cada natural aparece a lo sumo en uno de los arreglos, y a lo sumo una vez.\n",
    "- Implementar la función *iesimoMerge(in A: arreglo(nat), in B: arreglo(nat), in i: nat) → nat* que resuelve el problema planteado. La función debe ser de tiempo O(log² n), donde n = tam(A) = tam(B).\n",
    "- Calcular y justificar la complejidad del algoritmo propuesto.\n",
    "- Intente resolver el mismo problema en tiempo O(log n) (este ítem es bastante mas difícil, se incluye como desafío adicional)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "#COMPLETAR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejercicio 10\n",
    "Se tienen dos arreglos de n naturales A y B. A está ordenado de manera creciente y B está ordenado de\n",
    "manera decreciente. Ningún valor aparece más de una vez en el mismo arreglo. Para cada posición i consideramos la diferencia absoluta entre los valores de ambos arreglos |A\\[i\\] − B\\[i\\]|. Se desea buscar el mínimo valor posible de dicha cuenta. Por ejemplo, si los arreglos son A = \\[1, 2, 3, 4\\] y B = \\[6, 4, 2, 1\\], los valores de las diferencias son 5, 2, 1, 3 y el resultado es 1.\n",
    "- Implementar la función *minDif(in A: arreglo(nat), in B: arreglo(nat)) → nat* que resuelve el problema planteado. La función debe ser de tiempo O(log n), donde n = tam(A) = tam(B).\n",
    "- Calcular y justificar la complejidad del algoritmo propuesto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def minDif(A, B):\n",
    "    if len(A) == 1:\n",
    "        return abs(A[0] - B[0])\n",
    "    \n",
    "    n = len(A)\n",
    "    if abs(A[n//2] - B[n//2]) > abs(A[n//2-1] - B[n//2-1]):\n",
    "        return minDif(A[0:n//2], B[0:n//2])\n",
    "    else:\n",
    "        return minDif(A[n//2:n], B[n//2:n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 1: A = [1, 2, 3, 4]  B = [6, 4, 2, 1]\n",
      "Resultado test 1: 1 \n",
      "\n",
      "Test 2: A = [1, 2, 3, 4]  B = [7, 5, 6, 4]\n",
      "Resultado test 2: 0 \n",
      "\n",
      "Random test 1: A = [-2, -1, 3, 3, 7]  B = [9, 3, 3, 3, -1]\n",
      "Resultado random test 1: 0 \n",
      "\n",
      "Random test 2: A = [0, 2, 3, 4, 4, 5, 9, 10]  B = [14, 13, 13, 10, 10, 10, 9, 9]\n",
      "Resultado random test 2: 0\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A1 = [1, 2, 3, 4]    # Resultado esperado: 1\n",
    "A2 = [6, 4, 2, 1]\n",
    "print(\"Test 1:\", \"A =\", A1, \" B =\", A2)\n",
    "print(\"Resultado test 1:\", minDif(A1, A2), \"\\n\")\n",
    "\n",
    "B1 = [1, 2, 3, 4]    # Resultado esperado: 0\n",
    "B2 = [7, 5, 6, 4]\n",
    "print(\"Test 2:\", \"A =\", B1, \" B =\", B2)\n",
    "print(\"Resultado test 2:\", minDif(B1, B2), \"\\n\")\n",
    "\n",
    "C1 = generarRandomArr(-2, 10, 5)\n",
    "C2 = generarRandomArr(-2, 10, 5)\n",
    "C1.sort()\n",
    "C2.sort(reverse = True)\n",
    "print(\"Random test 1:\", \"A =\", C1, \" B =\", C2)\n",
    "print(\"Resultado random test 1:\", minDif(C1, C2), \"\\n\")\n",
    "\n",
    "D1 = generarRandomArr(0, 10, 8)\n",
    "D2 = generarRandomArr(5, 15, 8)\n",
    "D1.sort()\n",
    "D2.sort(reverse = True)\n",
    "print(\"Random test 2:\", \"A =\", D1, \" B =\", D2)\n",
    "print(\"Resultado random test 2:\", minDif(D1, D2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: T(m) = T(m/2) + O(1) -> O(log m). Como m = 2n, O(log m) = O(log 2n) = O(log n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejercicios de parcial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1) Divide & Conquer sobre arreglos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1er cuatrimestre 2017 (Parcial)\n",
    "\n",
    "Una empresa informa todos los días el cierre de sus ganancias netas (que pueden ser negativas si tuvo\n",
    "pérdida ese día). Dado un arreglo con tales montos para un período de n días consecutivos, el directorio de la\n",
    "empresa necesita conocer en qué intervalo de días (dentro de este período) se obtuvo la mayor ganancia (la\n",
    "ganancia en un intervalo de días es la suma de los montos informados en los días dentro de ese intervalo).\n",
    "Usando la técnica de D&C, dar un algoritmo que tome un arreglo con los montos de n días consecutivos (i.e., los días de 0 a n−1) e indique un intervalo de días \\[i, j\\], con 0 ≤ i ≤ j < n, en el cual se maximiza la suma de tales montos (puede asumirse que n > 0). El algoritmo propuesto debe tener complejidad estrictamente menor que O(n<sup>2</sup>), lo cual debe justificarse adecuadamente.\n",
    "\n",
    "***Ayuda***: Si pidiésemos que el intervalo devuelto contenga sí o sí un determinado día k, entonces el problema\n",
    "se resuelve en tiempo O(n) (¡pensar cómo!). Aprvechar ese procedimiento en el algoritmo global de D&C\n",
    "implementado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def periodoMaxGananciaCentro(A, posInicial):  # Devuelve una tupla: (inicio: nat, fin: nat, ganancia: nat)\n",
    "    if len(A) == 2:\n",
    "        return (posInicial + 0, posInicial + 1, A[0] + A[1])\n",
    "    \n",
    "    sumaActual = A[len(A)//2]                 # mayor hacia derecha\n",
    "    sumaMaxDer = A[len(A)//2]\n",
    "    indiceFin = len(A)//2\n",
    "    for i in range(len(A)//2+1,len(A)): \n",
    "        sumaActual = sumaActual + A[i]\n",
    "        if sumaActual > sumaMaxDer:\n",
    "            sumaMaxDer = sumaActual\n",
    "            indiceFin = i\n",
    "    \n",
    "    sumaActual = A[len(A)//2]                 # mayor hacia izquierda\n",
    "    sumaMaxIzq = A[len(A)//2]\n",
    "    indiceInicio = len(A)//2\n",
    "    i = len(A)//2-1\n",
    "    while i >= 0:\n",
    "        sumaActual = sumaActual + A[i]\n",
    "        if sumaActual > sumaMaxIzq:\n",
    "            sumaMaxIzq = sumaActual\n",
    "            indiceInicio = i\n",
    "        i-=1\n",
    "    \n",
    "    return (indiceInicio + posInicial, indiceFin + posInicial, sumaMaxIzq + sumaMaxDer - A[len(A)//2])\n",
    "\n",
    "def periodoMaxGanancia(A, posInicial):   # Devuelve una tupla: (inicio: nat, fin: nat, ganancia: nat)\n",
    "    if len(A) == 1:\n",
    "        return (posInicial + 0, posInicial + 0, A[0])\n",
    "    \n",
    "    p1 = periodoMaxGanancia(A[0:len(A)//2], posInicial)                   #T(n/2)\n",
    "    p2 = periodoMaxGanancia(A[len(A)//2:len(A)], len(A)//2 + posInicial)  #T(n/2)\n",
    "    p3 = periodoMaxGananciaCentro(A, posInicial)                          #O(n)\n",
    "    \n",
    "    res = p1\n",
    "    if p2[2] > res[2]:\n",
    "        res = p2\n",
    "    if p3[2] > res[2]:\n",
    "        res = p3\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Caso de test 1:  [-13, 15, -2, -1, 5, 18, 18, -19, 14, -5]\n",
      "Resultado test 1:  (1, 6, 53) \n",
      "\n",
      "Caso de test 2:  [27, 20, -40, 23, 5]\n",
      "Resultado test 2:  (0, 1, 47) \n",
      "\n",
      "Caso de test 3:  [16, 17, 25, -5, 3, -3, 24, 10]\n",
      "Resultado test 3:  (0, 7, 87) \n",
      "\n",
      "Caso de random test 1:  [15, -10, 6, 9, 20, 20, 9, -17, 11, 4]\n",
      "Resultado random test 1:  (0, 6, 69) \n",
      "\n",
      "Caso de random test 2:  [44, -45, -9, 3, 37]\n",
      "Resultado random test 2:  (0, 0, 44) \n",
      "\n",
      "Caso de random test 3:  [25, 17, 4, 15, 20, 1, 8, 23]\n",
      "Resultado random test 3:  (0, 7, 113) \n",
      "\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "test1 = [-13, 15, -2, -1, 5, 18, 18, -19, 14, -5]   #Resultado esperado: (1, 6, 53)\n",
    "test2 = [27, 20, -40, 23, 5]                        #Resultado esperado: (0, 1, 47)\n",
    "test3 = [16, 17, 25, -5, 3, -3, 24, 10]             #Resultado esperado: (0, 7, 87)\n",
    "rndmtest1 = generarRandomArr(-20, 20, 10)\n",
    "rndmtest2 = generarRandomArr(-50, 50, 5)\n",
    "rndmtest3 = generarRandomArr(-5, 25, 8)\n",
    "\n",
    "print(\"Caso de test 1: \", test1)\n",
    "print(\"Resultado test 1: \", periodoMaxGanancia(test1, 0), \"\\n\")\n",
    "\n",
    "print(\"Caso de test 2: \", test2)\n",
    "print(\"Resultado test 2: \", periodoMaxGanancia(test2, 0), \"\\n\")\n",
    "\n",
    "print(\"Caso de test 3: \", test3)\n",
    "print(\"Resultado test 3: \", periodoMaxGanancia(test3, 0), \"\\n\")\n",
    "\n",
    "print(\"Caso de random test 1: \", rndmtest1)\n",
    "print(\"Resultado random test 1: \", periodoMaxGanancia(rndmtest1, 0),\"\\n\")\n",
    "\n",
    "print(\"Caso de random test 2: \", rndmtest2)\n",
    "print(\"Resultado random test 2: \", periodoMaxGanancia(rndmtest2, 0), \"\\n\")\n",
    "\n",
    "print(\"Caso de random test 3: \", rndmtest3)\n",
    "print(\"Resultado random test 3: \", periodoMaxGanancia(rndmtest3, 0), \"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: la recurrencia tiene la forma T(n) = 2 T(n/2) + O(n). <br />\n",
    "a = 2, c = 2, log2 (2) = 1 <br /> \n",
    "Por el teorema maestro (2do caso), la complejidad del algoritmo es O(n log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1er cuatrimestre 2017 (Recuperatorio)\n",
    "\n",
    "Se tiene un arreglo de naturales sin repeticiones que estaba ordenado pero al cual se lo rotó circularmente k\n",
    "posiciones a la derecha. Por ejemplo, \\[10, 13, 1, 4, 6, 7, 8\\] fue rotado k = 2 veces mientras que \\[6, 7, 8, 10, 13, 1, 4\\] fue rotado 5 veces. Escribir un algoritmo que reciba uno de estos arreglos y devuelva el máximo elemento en\n",
    "tiempo estrictamente menor que O(*n*). Justifique la correctitud del algoritmo y su complejidad temporal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def maxArrRotado(arr):\n",
    "    if len(arr) == 1:\n",
    "        return arr[0]                    #O(1)\n",
    "    elif len(arr) == 2:\n",
    "        return max(arr[0], arr[1])       #O(1)\n",
    "    m = len(arr)//2\n",
    "    if arr[0] > arr[m]:\n",
    "        return maxArrRotado(arr[0:m])  #T(n/2)\n",
    "    else:\n",
    "        return maxArrRotado(arr[m:len(arr)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Caso de test 1:  [10, 13, 1, 4, 6, 7, 8]\n",
      "Resultado test 1:  13 \n",
      "\n",
      "Caso de test 2:  [6, 7, 8, 10, 12, 1, 4]\n",
      "Resultado test 2:  12 \n",
      "\n",
      "Caso de test 3:  [1, 4, 6, 7, 8, 10, 12]\n",
      "Resultado test 3:  12 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "test1 = [10, 13, 1, 4, 6, 7, 8]\n",
    "test2 = [6, 7, 8, 10, 12, 1, 4] \n",
    "test3 = [1, 4, 6, 7, 8, 10, 12]\n",
    "\n",
    "print(\"Caso de test 1: \", test1)\n",
    "print(\"Resultado test 1: \", maxArrRotado(test1), \"\\n\")\n",
    "\n",
    "print(\"Caso de test 2: \", test2)\n",
    "print(\"Resultado test 2: \", maxArrRotado(test2), \"\\n\")\n",
    "\n",
    "print(\"Caso de test 3: \", test3)\n",
    "print(\"Resultado test 3: \", maxArrRotado(test3), \"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: la recurrencia tiene la forma T(n) = T(n/2) + O(1). <br />\n",
    "a = 1, c = 2, log2(1) = 0 <br /> \n",
    "Por el teorema maestro (2do caso), la complejidad del algoritmo es O(log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2do cuatrimestre 2018 (Recuperatorio)\n",
    "Un arreglo de enteros es de a lo sumo uno distinto si a lo sumo un elemento del arreglo es distinto del resto.\n",
    "Por ejemplo los arreglos \\[1, 1, 1\\], \\[1, 2, 1, 1, 1\\] y \\[5, 71\\] son de a lo sumo uno distinto pero los arreglos \\[1, 2, 1, 2, 2\\] y \\[1, 2, 3\\] no lo son.\n",
    "Se pide diseñar un algoritmo de Divide & Conquer que, dado un arreglo cualquiera, devuelva la longitud del subarreglo (de elementos contiguos) más largo que sea a lo sumo uno distinto. Por ejemplo, dado el arreglo \\[5, 1, 1, 2, 1, 7\\] la respuesta del algoritmo debería ser 4 (la longitud del subarreglo \\[1, 1, 2, 1\\]). El algoritmo debe tener una complejidad temporal estrictamente menor que O(n²). La complejidad del algoritmo debe estar correctamente justificada."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def maxUnoDistintoCentro(arr):\n",
    "    maxCen = 1\n",
    "    m = len(arr)//2\n",
    "    i = m-1\n",
    "    while i >= 0 and arr[i] == arr[m]:\n",
    "        maxCen +=1\n",
    "        i-=1\n",
    "    j = m+1\n",
    "    while j < len(arr) and arr[j] == arr[m]:\n",
    "        maxCen +=1\n",
    "        j+=1\n",
    "    #i es el índice del primero que es dif a izq, j es el índice del primero que es dif a der\n",
    "    if maxCen > 1:\n",
    "        difIzq = i\n",
    "        maxIzq = 1\n",
    "        if i != -1:\n",
    "            i-=1\n",
    "            while i >= 0 and arr[i] == arr[m]:\n",
    "                maxIzq+=1\n",
    "                i-=1\n",
    "        difDer = j\n",
    "        maxDer = 1\n",
    "        if j != len(arr):\n",
    "            j+=1\n",
    "            while j < len(arr) and arr[j] == arr[m]:\n",
    "                maxDer+=1\n",
    "                j+=1\n",
    "        maxCen = maxCen + max(maxIzq, maxDer)\n",
    "    if maxCen == 1:\n",
    "        izq = i\n",
    "        maxIzq = 1\n",
    "        if i != -1:\n",
    "            i-=1\n",
    "            while i >= 0 and arr[i] == arr[izq]:\n",
    "                maxIzq+=1\n",
    "                i-=1\n",
    "        der = j\n",
    "        maxDer = 1\n",
    "        if j != len(arr):\n",
    "            j+=1\n",
    "            while j < len(arr) and arr[j] == arr[der]:\n",
    "                maxDer+=1\n",
    "                j+=1\n",
    "        if izq >= 0 and der < len(arr) and arr[izq] == arr[der]:\n",
    "            maxCen = maxCen + maxIzq + maxDer\n",
    "        else:\n",
    "            maxCen = maxCen + max(maxIzq, maxDer)\n",
    "\n",
    "    return maxCen\n",
    "\n",
    "def maxUnoDistinto(arr):\n",
    "    if len(arr) == 1:\n",
    "        return 1\n",
    "    if len(arr) == 2:\n",
    "        return 2\n",
    "    r1 = maxUnoDistinto(arr[0:len(arr)//2])            #T(n/2)\n",
    "    r2 = maxUnoDistinto(arr[len(arr)//2:len(arr)])     #T(n/2)\n",
    "    r3 = maxUnoDistintoCentro(arr)                       #O(n)\n",
    "    return max(max(r1, r2), r3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Caso de test 1:  [5, 1, 1, 2, 1, 7]\n",
      "Resultado test 1:  4 \n",
      "\n",
      "Caso de test 2:  [5, 1, 3, 2, 1]\n",
      "Resultado test 2:  2 \n",
      "\n",
      "Caso de test 3:  [5, 1, 1, 1, 2, 7]\n",
      "Resultado test 3:  4 \n",
      "\n",
      "Caso de random test 1:  [7, 7, 2, 2, 8, 8, 6, 0, 3, 3]\n",
      "Resultado random test 1:  3 \n",
      "\n",
      "Caso de random test 2:  [2, 1, 4, 5, 3]\n",
      "Resultado random test 2:  2 \n",
      "\n",
      "Caso de random test 3:  [4, 2, 2, 4, 2, 3, 2, 3]\n",
      "Resultado random test 3:  3 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "test1 = [5, 1, 1, 2, 1, 7]\n",
    "test2 = [5, 1, 3, 2, 1]\n",
    "test3 = [5, 1, 1, 1, 2, 7]\n",
    "rndmtest1 = generarRandomArr(0, 8, 10)\n",
    "rndmtest2 = generarRandomArr(1, 5, 5)\n",
    "rndmtest3 = generarRandomArr(2, 4, 8)\n",
    "\n",
    "print(\"Caso de test 1: \", test1)\n",
    "print(\"Resultado test 1: \", maxUnoDistinto(test1), \"\\n\")\n",
    "\n",
    "print(\"Caso de test 2: \", test2)\n",
    "print(\"Resultado test 2: \", maxUnoDistinto(test2), \"\\n\")\n",
    "\n",
    "print(\"Caso de test 3: \", test3)\n",
    "print(\"Resultado test 3: \", maxUnoDistinto(test3), \"\\n\")\n",
    "\n",
    "print(\"Caso de random test 1: \", rndmtest1)\n",
    "print(\"Resultado random test 1: \", maxUnoDistinto(rndmtest1),\"\\n\")\n",
    "\n",
    "print(\"Caso de random test 2: \", rndmtest2)\n",
    "print(\"Resultado random test 2: \", maxUnoDistinto(rndmtest2), \"\\n\")\n",
    "\n",
    "print(\"Caso de random test 3: \", rndmtest3)\n",
    "print(\"Resultado random test 3: \", maxUnoDistinto(rndmtest3), \"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: la recurrencia tiene la forma T(n) = 2 T(n/2) + O(n). <br />\n",
    "a = 2, c = 2, log2 (2) = 1 <br /> \n",
    "Por el teorema maestro (2do caso), la complejidad del algoritmo es O(n log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Divide & Conquer sobre matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2do cuatrimestre 2015 (Parcial)\n",
    "El famoso y archiconocido juego ***3mb0l3*** se juega, como todos saben, sobre un tablero cuadrado de lado n con n = 2k para algún k natural. El tablero está dividido en n × n casillas. Participan dos jugadores, cada uno tiene su identificador **B** o **N**. En algunas casillas del tablero, un jugador colocó su identicador. Puede haber casillas vacías y no hay más de un identicador por casilla. Una vez finalizado el juego, para decidir el ganador se consideran k + 1 niveles distintos, numerados de 0 a k. El nivel i se forma dividiendo el cuadrado original en 2^(k−i) × 2^(k-i) casillas. Así, el nivel k consta de una sola casilla, el k −1 de un tablero de 2 × 2 y así siguiendo. Se puede ver en la gura cómo quedan los distintos niveles. Para cada casilla de cada nivel (salvo el 0), se toma como dueño de la misma al jugador que más casillas controla del nivel anterior teniendo en cuenta solamente las que están contenidas en la casilla grande. Se coloca el identicador del dueño en cada casilla, y en caso de empate se coloca una **E**. Para cada nivel, se toma como ganador del nivel al que más casillas controla de ese nivel. Acá nuevamente puede haber empate. Por último se dice que el ganador del juego es aquel que haya ganado mayor cantidad de niveles. Realizar un algoritmo que dado un tablero, con los dueños de cada casillero en el nivel 0, devuelva si gana **B** o **N** todo el juego, o **E** si hay empate.\n",
    "Se pide dar un algoritmo que utilice la técnica de Dividir y Conquitar y además se debe calcular y justicar su complejidad temporal.\n",
    "En el ejemplo de la figura, se tiene un tablero con n = 2^2, por lo que hay niveles de 0 a 2. Por ejemplo, en el nivel 1 la casilla inferior izquierda es controlada por **B**, pues entre las casillas correspondientes en el nivel 0 hay tres **B** y una **N**. El nivel 0 es empate pues hay igual cantidad de casillas controladas por cada jugador, el nivel 1 lo gana **B** pues hay dos **B** y sólo una **N** y el nivel 2 lo gana **B**. Como **B** ganó dos niveles y **N** ninguno, el algoritmo debe dar **B** como respuesta.\n",
    "<center>\n",
    "<img src=\"D&C_pics/tablero.jpg\" alt=\"drawing\" width=\"200\" /> <br/>\n",
    "    </center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def construirSigNivel(T):    # Devuelve una matriz que corresponde al nivel siguiente a A\n",
    "    if len(T) == 2:\n",
    "        contE = 0\n",
    "        contB = 0\n",
    "        contN = 0\n",
    "        for i in range(0,len(T)):\n",
    "            for j in range(0,len(T)):\n",
    "                if T[i][j] == 'E':\n",
    "                    contE += 1\n",
    "                elif T[i][j] == 'B':\n",
    "                    contB += 1\n",
    "                else:\n",
    "                    contN +=1\n",
    "        if contB > contN:\n",
    "            return [['B']]\n",
    "        elif contN > contB:\n",
    "            return [['N']]\n",
    "        else:\n",
    "            return [['E']]\n",
    "        \n",
    "    n = len(T)\n",
    "    T = np.array(T)\n",
    "    t1 = construirSigNivel(T[0:n//2,0:n//2])            #T(n/4)\n",
    "    t2 = construirSigNivel(T[0:len(T)//2,n//2:n])       #T(n/4)\n",
    "    t3 = construirSigNivel(T[n//2:n,0:n//2])            #T(n/4)\n",
    "    t4 = construirSigNivel(T[n//2:n,n//2:n])            #T(n/4)\n",
    "    \n",
    "    T1 = np.concatenate((t1, t2), axis=1)\n",
    "    T2 = np.concatenate((t3, t4),  axis=1)\n",
    "    TF = np.concatenate((T1, T2), axis=0)\n",
    "    return TF                                       #Complejidad: T(m) = 4 T(m/4) + O(m)\n",
    "\n",
    "def ganadorNivel(T):\n",
    "    if len(T) == 1:\n",
    "        return T[0][0]\n",
    "    N = np.count_nonzero(T == 'N')\n",
    "    B = np.count_nonzero(T == 'B')\n",
    "    if N > B:\n",
    "        return 'N'\n",
    "    elif B > N:\n",
    "        return 'B'\n",
    "    else:\n",
    "        return 'E'                              #Complejidad total: O(m)\n",
    "    \n",
    "def jugar(T):\n",
    "    puntN = 0\n",
    "    puntB = 0\n",
    "    cantNiveles = int(math.log(len(T), 2))\n",
    "    nivel = 0\n",
    "    while nivel < cantNiveles:                 #log2(n)*\n",
    "        ganNivel = ganadorNivel(T)              #O(m)\n",
    "        if ganNivel == 'N':\n",
    "            puntN += 1\n",
    "        elif ganNivel == 'B':\n",
    "            puntB += 1\n",
    "        T = construirSigNivel(T)                #O(m log m)\n",
    "        nivel += 1\n",
    "    \n",
    "    ganUltNiv = ganadorNivel(T)\n",
    "    if ganUltNiv == 'N':\n",
    "        puntN += 1\n",
    "    elif ganUltNiv == 'B':\n",
    "        puntB += 1\n",
    "        \n",
    "    if puntN > puntB:\n",
    "        return 'N'\n",
    "    elif puntB > puntN:\n",
    "        return 'B'\n",
    "    else:\n",
    "        return 'E'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado test 1: B\n",
      "Resultado test 2: N\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A = [['N', 'N', 'B', 'B'],\n",
    "     ['N', 'N', 'N', 'N'],\n",
    "     ['B', 'B', 'B', 'B'],\n",
    "     ['N', 'B', 'B', 'N']]\n",
    "A = np.array(A)\n",
    "print(\"Resultado test 1:\", jugar(A))\n",
    "\n",
    "B = [['N', 'N', 'B', 'B', 'N', 'B', 'B', 'B'],\n",
    "     ['N', 'N', 'N', 'N', 'B', 'N', 'B', 'N'],\n",
    "     ['B', 'B', 'B', 'B', 'N', 'N', 'N', 'N'],\n",
    "     ['N', 'B', 'B', 'N', 'N', 'B', 'B', 'B'],\n",
    "     ['B', 'N', 'B', 'N', 'B', 'N', 'B', 'N'],\n",
    "     ['N', 'N', 'N', 'B', 'B', 'B', 'N', 'N'],\n",
    "     ['B', 'B', 'N', 'N', 'B', 'N', 'B', 'N'],\n",
    "     ['N', 'B', 'N', 'B', 'B', 'N', 'N', 'B']]\n",
    "B = np.array(B)\n",
    "print(\"Resultado test 2:\", jugar(B))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad:** </br>\n",
    "m = n^2 (m es la cantidad de elementos de la matriz, n es el tamaño de la matriz) </br>\n",
    "*construirSigNivel*: T(m) = 4 T(m/4) + O(m) -> Por el Teorema Maestro, la complejidad es O(m log m) </br>\n",
    "*ganadorNivel*: O(m) </br>\n",
    "*jugar*: O(log2(n)·(m log m + m)) = O(log4(m)·(m log m)) </br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2do cuatrimestre 2019 (Parcial)\n",
    "Decimos que una matriz cuadrada A de tamaño n x n de números naturales tiene *todos consecutivos* si todas sus filas y todas sus columnas son secuencias de números consecutivos. Por ejemplo: </br>\n",
    "\n",
    "\\[2, 3, 4, 5\\] </br>\n",
    "\\[3, 4, 5, 6\\] </br>\n",
    "\\[4, 5, 6, 7\\] </br>\n",
    "\\[5, 6, 7, 8\\] </br>\n",
    "\n",
    "Decimos que se introdujo un *hueco* en una matriz de *todos consecutivos* si se eligió una posición *i, j* y se aumentó en 1 el valor de todos los elementos de la submatriz que comienza en \\[i,j\\] y termina en \\[n-1, n-1\\]. Por ejemplo, si se introduce un hueco en la posición \\[1,2\\], la matriz quedaría así: </br>\n",
    "\n",
    "\\[2, 3, 4, 5\\] </br>\n",
    "\\[3, 4, **6**, 7\\] </br>\n",
    "\\[4, 5, 7, 8\\] </br>\n",
    "\\[5, 6, 8, 9\\] </br>\n",
    "\n",
    "Dada una matriz cuadrada de *todos consecutivos* en la que se introdujo un hueco nos interesa encontrar la posición \\[i, j\\] en la que se encuentra el hueco. Se pide:\n",
    "- Diseñar un algoritmo que utilice la técnica Divide & Conquer para resolver el problema con una complejidad temporal estrictamente menor que O(n) en el peor caso. Notar que la cantidad de elementos de la matriz es n<sup>2</sup>.\n",
    "- Marcar claramente qué partes del algoritmo corresponden a *dividir*, *conquistar* y *unir* subproblemas.\n",
    "- Justificar adecuadamente que el algoritmo cumple con la complejidad pedida.\n",
    "\n",
    "**Tip:** tener en cuenta qué cambios se observan entre la matriz con hueco y la matriz de todos consecutivos si ese hueco no estuviese."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def buscarHueco(A, fi, ci):  #fi = fila de inicio, ci = columna de inicio\n",
    "    if len(A) == 2:                        #casos base\n",
    "        if A[0][0]+1 != A[1][0]:\n",
    "            return (1 + fi, 0 + ci)\n",
    "        elif A[0][0]+1 != A[0][1]:\n",
    "            return (0 + fi, 1 + ci)\n",
    "        elif A[0][0]+2 != A[1][1]:\n",
    "            return (1 + fi, 1 + ci)\n",
    "        else:\n",
    "            return (0, 0)\n",
    "        \n",
    "    n = len(A)\n",
    "    if A[0][n//2] != A[0][n//2-1]+1:    #casos en los que el hueco está al comienzo de una submatriz\n",
    "        return (0 + fi, n//2 + ci)\n",
    "    elif A[n//2][0] != A[n//2-1][0]+1:\n",
    "        return (n//2 + fi, 0 + ci)\n",
    "    elif A[n//2][n//2] != A[n//2-1][n//2]+1:\n",
    "        return (n//2 + fi, n//2 + fi)\n",
    "        \n",
    "    if (A[n//2-1][n//2-1] - A[0][0]) != 2*(n//2-1):    #casos recursivos\n",
    "        return buscarHueco(A[0:n//2,0:n//2], 0 + fi, 0 + ci)         #T(n/4)\n",
    "    elif (A[n//2-1][n-1] - A[0][n//2]) != 2*(n//2-1):\n",
    "        return buscarHueco(A[0:n//2,n//2:n], 0 + fi, n//2 + ci)      #T(n/4)   \n",
    "    elif (A[n-1][n//2-1] - A[n//2][0]) != 2*(n//2-1):\n",
    "        return buscarHueco(A[n//2:n,0:n//2], n//2 + fi, 0 + ci)      #T(n/4)\n",
    "    elif (A[n//2][n//2] - A[n-1][n-1]) != 2*(n//2-1):\n",
    "        return buscarHueco(A[n//2:n,n//2:n], n//2 + fi, n//2 + ci)   #T(n/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado test 1:  (1, 1)\n",
      "Resultado test 2:  (2, 2)\n",
      "Resultado test 3:  (0, 0)\n",
      "Resultado test 4:  (1, 3)\n",
      "Resultado test 5:  (5, 6)\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "A = [[1, 2, 3, 4],    #Respuesta esperada: (1,1) (caso normal)\n",
    "     [2, 4, 5, 6],\n",
    "     [3, 5, 6, 7],\n",
    "     [4, 6, 7, 8]]\n",
    "A = np.array(A)\n",
    "\n",
    "B = [[1, 2, 3, 4],    #Respuesta esperada: (2,2) (hueco al comienzo de submatriz)\n",
    "     [2, 3, 4, 5],\n",
    "     [3, 4, 6, 7],\n",
    "     [4, 5, 7, 8]]\n",
    "B = np.array(B)\n",
    "\n",
    "C = [[1, 2, 3, 4],    #Respuesta esperada: (0,0) (sin hueco)\n",
    "     [2, 3, 4, 5],\n",
    "     [3, 4, 5, 6],\n",
    "     [4, 5, 6, 7]]\n",
    "C = np.array(C)\n",
    "\n",
    "D = [[1, 2, 3, 4],    #Respuesta esperada: (1,3) (hueco en columna)\n",
    "     [2, 3, 4, 6],\n",
    "     [3, 4, 5, 7],\n",
    "     [4, 5, 6, 8]]\n",
    "D = np.array(D)\n",
    "\n",
    "E = [[1, 2, 3, 4, 5, 6, 7, 8],         #Respuesta esperada: (5,6)\n",
    "     [2, 3, 4, 5, 6, 7, 8, 9],\n",
    "     [3, 4, 5, 6, 7, 8, 9, 10],\n",
    "     [4, 5, 6, 7, 8, 9, 10, 11],\n",
    "     [5, 6, 7, 8, 9, 10, 11, 12],\n",
    "     [6, 7, 8, 9, 10, 11, 13, 14],\n",
    "     [7, 8, 9, 10, 11, 12, 14, 15],\n",
    "     [8, 9, 10, 11, 12, 13, 15, 16]]\n",
    "E = np.array(E)\n",
    "\n",
    "print(\"Resultado test 1: \", buscarHueco(A, 0, 0))\n",
    "print(\"Resultado test 2: \", buscarHueco(B, 0, 0))\n",
    "print(\"Resultado test 3: \", buscarHueco(C, 0, 0))\n",
    "print(\"Resultado test 4: \", buscarHueco(D, 0, 0))\n",
    "print(\"Resultado test 5: \", buscarHueco(E, 0, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: La recurrencia es de la forma T(n) = T(n/4) + O(1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Divide & Conquer sobre árboles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1er Cuatrimestre 2018 (Parcial)\n",
    "La copa de un árbol binario de naturales está formada por los primeros niveles (completos) del árbol cuyos elementos coincidan con el de la raíz. Por ejemplo, el siguiente ́arbol tiene una copa de tamaño 2 (formada por el nodo raíz y sus dos hijos), aunque si el nodo marcado en gris tuviese un 5 en lugar de un 4, el ́arbol tendría una copa de tamaño 3. <br/>\n",
    "<center>\n",
    "<img src=\"D&C_pics/copamaxima.jpg\" alt=\"drawing\" width=\"400\" /> <br/>\n",
    "    </center>\n",
    "Se pide diseñar un algoritmo de tipo Divide & Conquer que dado un ́arbol binario de naturales, indique el tamaño máximo de copa entre todos los subárboles del mismo (consideramos que un árbol es también subárbol de sí mismo). En el ejemplo anterior, la respuesta sería 3, dada por el subárbol izquierdo de la raíz del árbol (cuya copa de tamaño 3 está enmarcada en el triángulo). El algoritmo diseñado debe tener una complejidad de peor caso de O(n), siendo n la cantidad de nodos del arbol. Se pide además:\n",
    "<br/> 1. Justificar la complejidad del algoritmo suponiendo que el árbol está balanceado.\n",
    "<br/> 2. Justificar la complejiad del algoritmo en el caso en que el árbol no esté balanceado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def copaMaxima(A):\n",
    "    if A.left == None or A.right == None:\n",
    "        return 1\n",
    "    resIzq = copaMaxima(A.left)\n",
    "    resDer = copaMaxima(A.right)\n",
    "    if A.value == (A.right).value and A.value == (A.left).value:\n",
    "        if resDer == resIzq:\n",
    "            return resDer + 1\n",
    "    return max(resDer, resIzq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "        ______5______\n",
      "       /             \\\n",
      "    __5__           __5__\n",
      "   /     \\         /     \\\n",
      "  5       5       4       5\n",
      " / \\     / \\     / \\     / \\\n",
      "5   5   5   5   3   1   3   2\n",
      "\n",
      "Resultado test 1: 3\n",
      "\n",
      "        ______5______\n",
      "       /             \\\n",
      "    __5__           __4__\n",
      "   /     \\         /     \\\n",
      "  5       5       5       5\n",
      " / \\     / \\     / \\     /\n",
      "5   5   3   1   3   2   1\n",
      "\n",
      "Resultado test 2: 2\n",
      "\n",
      "      __4__\n",
      "     /     \\\n",
      "    1       2\n",
      "   / \\     / \\\n",
      "  6   5   4   3\n",
      " /\n",
      "1\n",
      "\n",
      "Resultado random test 1: 1\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "valuesA = [5,5,5,5,5,4,5,5,5,5,5,3,1,3,2]\n",
    "A = build(valuesA)\n",
    "print(A)\n",
    "print(\"Resultado test 1:\", copaMaxima(A))\n",
    "valuesB = [5,5,4,5,5,5,5,5,5,3,1,3,2,1]\n",
    "B = build(valuesB)\n",
    "print(B)\n",
    "print(\"Resultado test 2:\", copaMaxima(B))\n",
    "valuesC = generarRandomArr(1,6,8)\n",
    "C = build(valuesC)\n",
    "print(C)\n",
    "print(\"Resultado random test 1:\", copaMaxima(C))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: </br>\n",
    "1. Si el árbol está balanceado, se puede usar el Teorema Maestro. La recurrencia es de la forma T(n) = 2 T(n/2) + O(1) -> O(n)\n",
    "2. Si el árbol no está balanceado, se puede usar un árbol de recursión. La complejidad también es O(n) porque se pasa por cada nodo una única vez."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2do cuatrimestre 2018 (Parcial)\n",
    "Decimos que un  ́arbol binario de booleanos esta equilibrado si para todo nodo del arbol ocurre que la cantidad\n",
    "de falsos en su subarbol izquierdo difiere en a lo sumo uno con la cantidad de verdaderos en su subarbol derecho.\n",
    "Sabiendo que contamos con las operaciones de  ́arbol binario *nil*?, *raiz*, *izq* y *der*, cuyas complejidades temporales son O(1), proponer un algoritmo que utilice la técnica de Dividir y Conquistar para determinar si un arbol binario de booleanos esta equilibrado. El algoritmo propuesto debe tener complejidad O(n), donde n es la cantidad de nodos del arbol, sin importar si el mismo esta o no balanceado (notar que estar equilibrado no implica estar balanceado ni viceversa). La complejidad del algoritmo debe estar correctamente justificada."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Solución\n",
    "def arboolEquilibrado(A):\n",
    "    #print(A.value)             #Habilitar para ver complejidad (qué nodos recorre y cuántas veces)\n",
    "    if A.left == None and A.right == None:\n",
    "        if A.value == False:\n",
    "            return (True, 1)    #Equilibrado?, #Falsos\n",
    "        else:\n",
    "            return (True, 0)\n",
    "    fraiz = 0\n",
    "    if A.value == False:\n",
    "        fraiz = 1\n",
    "    subIzq = arboolEquilibrado(A.left)\n",
    "    subDer = arboolEquilibrado(A.right)\n",
    "    return (subIzq[0] and subDer[0] and abs(subIzq[1] - subDer[1]) < 2, subIzq[1] + subDer[1] + fraiz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "          ________True__\n",
      "         /              \\\n",
      "    __False__          False\n",
      "   /         \\\n",
      "False       False\n",
      "\n",
      "(False, 4)\n",
      "\n",
      "         ________True__\n",
      "        /              \\\n",
      "   __False__          False\n",
      "  /         \\\n",
      "True       False\n",
      "\n",
      "(True, 3)\n"
     ]
    }
   ],
   "source": [
    "#Tests\n",
    "valuesA = [True, False, False, False, False]\n",
    "A = build(valuesA)\n",
    "print(A)\n",
    "print(arboolEquilibrado(A))\n",
    "valuesB = [True, False, False, True, False]\n",
    "B = build(valuesB)\n",
    "print(B)\n",
    "print(arboolEquilibrado(B))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Complejidad**: O(n), donde n es la cantidad de nodos del árbol, ya que se recorre cada nodo una única vez. Se puede mostrar con un árbol de recursión (ver comentario en función)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}