03 Diseño de Algoritmos Eficientes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3 Diseño de Algoritmos Eficientes\n",
    "\n",
    "En este capítulo veremos un conjunto de ideas que permiten diseñar algoritmos que, en muchos casos, son de los más eficientes que se conocen para sus respectivos problemas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dividir para Reinar\n",
    "\n",
    "Este es un método de diseño de algoritmos que se basa en subdividir el problema en sub-problemas, resolverlos recursivamente, y luego combinar las soluciones de los sub-problemas para construir la solución del problema original. Es necesario que los subproblemas tengan la misma estructura que el problema original, de modo que se pueda aplicar la recursividad."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo: Multiplicación de Polinomios\n",
    "\n",
    "Supongamos que tenemos dos polinomios $A(x)$ y $B(x)$, cada uno de grado $n-1$:\n",
    "\n",
    "$$\n",
    "A(x) = a_0+a_1 x+a_2 x^2 + \\ldots + a_{n-1}x^{n-1}\n",
    "$$\n",
    "$$\n",
    "B(x) = b_0+b_1 x+b_2 x^2 + \\ldots + b_{n-1}x^{n-1}\n",
    "$$\n",
    "\n",
    "representados por sus respectivos arreglos de coeficientes $a[0],\\ldots,a[n-1]$ y $b[0],\\ldots,b[n-1]$.\n",
    "\n",
    "El problema consiste en calcular los coeficientes $c[0],\\ldots,c[2n-2]$ del polinomio producto $C(x)=A(x)B(x)$.\n",
    "\n",
    "Por ejemplo,\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "A(x) &= 2+3x-6x^2+x^3\\\\\n",
    "B(x) &= 1-x+3x^2+x^3\\\\\n",
    "C(x) &= A(x)B(x) = 2+x-3x^2+18x^3-16x^4-3x^5+x^6\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "La manera obvia de resolver este problema es multiplicando cada término de $A(x)$ por cada término de $B(x)$ y acumulando los resultados que corresponden a la misma potencia de $x$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def multpol(a, b):\n",
    "    n=len(a)\n",
    "    assert len(b)==n\n",
    "    c=np.zeros(2*n-1)\n",
    "    for i in range(0,n):\n",
    "        for j in range(0,n):\n",
    "            c[i+j]+=a[i]*b[j]\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  2.,   1.,  -3.,  18., -16.,  -3.,   1.])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multpol(np.array([2,3,-6,1]), np.array([1,-1,3,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Evidentemente, este algoritmo demora tiempo $O(n^2)$.\n",
    "¿Es posible hacerlo más rápido?\n",
    "Para esto, aplicaremos la técnica de _dividir para reinar_.\n",
    "\n",
    "Supongamos que $n$ es par, y dividamos los polinomios en dos partes, separando las potencias bajas de las altas.\n",
    "Por ejemplo, si\n",
    "\n",
    "$$\n",
    "A(x)=2+3x-6x^2+x^3\n",
    "$$\n",
    "\n",
    "lo podemos reescribir como\n",
    "\n",
    "$$\n",
    "A(x)=(2+3x) + (-6+3x)x^2\n",
    "$$\n",
    "\n",
    "En general, podemos reescribir $A(x)$ y $B(x)$ como\n",
    "\n",
    "$$\n",
    "A(x) = A'(x)+A''(x)x^{n/2}\n",
    "$$\n",
    "$$\n",
    "B(x) = B'(x)+B''(x)x^{n/2}\n",
    "$$\n",
    "\n",
    "y entonces (omitiendo los \"$(x)$\" para simplificar la notación),\n",
    "\n",
    "$$\n",
    "C = A'B'+(A'B''+A''B')x^{n/2}+A''B''x^n\n",
    "$$\n",
    "\n",
    "Esto se puede implementar con 4 multiplicaciones recursivas, cada una involucrando polinomios de la mitad del tamaño.\n",
    "Nótese que las multiplicaciones por potencias de $x$ son solo realineaciones de los arreglos de coeficientes, de modo que son \"gratis\".\n",
    "\n",
    "Si llamamos $T(n)$ al número total de operaciones, éste obedece la ecuación de recurrencia\n",
    "\n",
    "$$\n",
    "T(n) = 4T \\left(\\frac{n}{2}\\right)+Kn\n",
    "$$\n",
    "\n",
    "para alguna constante K.\n",
    "\n",
    "Por el Teorema Maestro, con $p=4$, $q=2$, $r=1$, tenemos\n",
    "\n",
    "$$\n",
    "T(n)=\\Theta(n^2)\n",
    "$$\n",
    "\n",
    "lo cual no es mejor que el algoritmo anterior.\n",
    "\n",
    "Afortunadamente, hay una manera de obtener un algoritmo realmente más eficiente.\n",
    "Si calculamos\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "D &= (A'+A'')(B'+B'')\\\\\n",
    "E &= A'B'\\\\\n",
    "F &= A''B''\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "podemos construir el polinomio $C$ de la manera siguiente:\n",
    "\n",
    "$$\n",
    "C = E+(D-E-F)x^{n/2}+Fx^n\n",
    "$$\n",
    "\n",
    "¡lo cual utiliza solo 3 multiplicaciones recursivas!\n",
    "\n",
    "$$\n",
    "T(n) = 3T \\left(\\frac{n}{2}\\right)+Kn\n",
    "$$\n",
    "\n",
    "Usando nuevamente el Teorema Maestro, esta vez con $p=3$, tenemos que\n",
    "\n",
    "$$\n",
    "T(n)=\\Theta(n^{\\log_2{3}}) \\approx \\Theta(n^{1.59})\n",
    "$$\n",
    "\n",
    "Éste se llama el *Algoritmo de Karatsuba*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 3.1\n",
    "\n",
    "Si tenemos dos números complejos\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "u&=a+bi\\\\\n",
    "v&=c+di\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "podemos calcular su producto\n",
    "\n",
    "$$\n",
    "uv=(ac-bd)+(ad+bc)i\n",
    "$$\n",
    "\n",
    "haciendo 4 multiplicación de números reales.\n",
    "\n",
    "Encuentre una forma de realizar este cálculo haciendo solo 3 multiplicaciones de números reales."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Programación Dinámica\n",
    "\n",
    "Hay ocasiones en que la simple aplicación de la recursividad conduce a algoritmos muy ineficientes, pero es posible evitar esa ineficiencia con un uso adecuado de memoria."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo: Cálculo de un número de Fibonacci\n",
    "\n",
    "Recordemos la ecuación de Fibonacci\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "f_n &= f_{n-1}+f_{n-2} \\text{ para } n\\ge 2\\\\\n",
    "f_0 &= 0\\\\\n",
    "f_1 &= 1\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "algunos de cuyos valores son:\n",
    "\n",
    "| $𝑛$  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| $f_n$ | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 | 6765 |\n",
    "\n",
    "Queremos resolver el siguiente problema: dado un $n$, calcular $f_n$.\n",
    "\n",
    "A partir de la ecuación de recurrencia podemos escribir de inmediato una solución recursiva:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n<=1:\n",
    "        return n\n",
    "    else:\n",
    "        return fibonacci(n-1)+fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "print(fibonacci(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema es que, para $n$ grande, este algoritmo es horriblemente ineficiente.\n",
    "El motivo de esto es que, a medida que se van ejecutando las llamadas recursivas, un mismo número de Fibonacci puede calcularse múltiples veces, independientemente de si ya se ha calculado antes.\n",
    "\n",
    "Una forma de dimensionar esta ineficiencia es calcular, por ejemplo, el número de operaciones de suma que se hacen al calcular `fibonacci(n)`.\n",
    "Llamemos $s_n$ a ese número de sumas. Es fácil ver que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "s_n &= s_{n-1}+s_{n-2}+1 \\text{ para } n\\ge 2\\\\\n",
    "s_0 &= 0\\\\\n",
    "s_1 &= 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Si definimos una nueva función incógnita $t_n=s_n+1$, tenemos que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "t_n &= t_{n-1}+t_{n-2} \\text{ para } n\\ge 2\\\\\n",
    "t_0 &= 1\\\\\n",
    "t_1 &= 1\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Esta es la misma ecuación de Fibonacci, comenzando un paso más adelante, y por lo tanto su solución es $t_n=f_{n+1}$, y el número de sumas es $s_n=f_{n+1}-1=\\Theta(\\phi^n)$.\n",
    "Conclusión: ¡el tiempo que demora la ejecución de `fibonacci(n)` crece exponencialmente!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evitando la ineficiencia: Memoización\n",
    "\n",
    "La ineficiencia de la solución recursiva se debe, como dijimos antes, a que un mismo valor de la función $f$ se calcula y recalcula múltiples veces.\n",
    "Una forma de evitar esto es incorporar una memoria auxiliar, en forma de un arreglo $F$ inicializado con ceros.\n",
    "La primera vez que se pide calcular un $f_n$ dado, lo hacemos recursivamente, pero dejamos el valor anotado en $F[n]$.\n",
    "Las siguientes veces lo tomamos del arreglo, sin incurrir de nuevo en el costo del cálculo recursivo.\n",
    "Esta forma de utilizar una memoria para almacenar resultados calculados previamente, para evitar recalcularlos, se llama una _memoria caché_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def fibonacci(n):\n",
    "    F=np.zeros(n+1,dtype=int)\n",
    "    def fib_rec(k):\n",
    "        if k>0 and F[k]==0: # primera vez que se calcula\n",
    "            if k<=1:\n",
    "                F[k]=k\n",
    "            else:\n",
    "                F[k]=fib_rec(k-1)+fib_rec(k-2)\n",
    "        return F[k]\n",
    "    return fib_rec(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "print(fibonacci(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La introducción de esta memoria auxiliar tiene como efecto transformar el algoritmo original, de tiempo exponencial, en un algoritmo de tiempo lineal $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evitando la ineficiencia: Tabulación\n",
    "\n",
    "La técnica de _memoización_ va llenando el arreglo auxiliar $F$ a medida que sus valores son solicitados. Este método es bastante general, pero se puede mejorar si logramos encontrar un orden para ir llenando el arreglo $F$ que garantice que cuando se requiere el valor de un cierto casillero, éste ya está llenado.\n",
    "\n",
    "En el caso de Fibonacci, esto se logra simplemente al ir llenando los casilleros $F[k]$ en orden creciente de $k$.\n",
    "Esta técnica se llama _tabulación_:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def fibonacci(n):\n",
    "    F=np.zeros(n+1,dtype=int)\n",
    "    F[0]=0\n",
    "    F[1]=1\n",
    "    for k in range(2,n+1):\n",
    "        F[k]=F[k-1]+F[k-2]\n",
    "    return F[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "print(fibonacci(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es evidente que el tiempo que demora este algoritmo es $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Derrotando al algoritmo lineal\n",
    "\n",
    "Si bien parecería que para calcular $f_n$ es necesario calcular previamente todos los $f_k$, para $0\\le k<n$, en realidad esto no es cierto.\n",
    "\n",
    "Introduzcamos una función incógnita adicional $g_n$ en la ecuación de Fibonacci, definiéndola como $g_n=f_{n-1}$.\n",
    "La ecuación puede reescribirse así:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "f_n &= f_{n-1}+g_{n-1}\\\\\n",
    "g_n &= f_{n-1}\\\\\n",
    "f_1 &=1\\\\\n",
    "g_1 &=0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Esto se puede reescribir en forma matricial:\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "f_n \\\\\n",
    "g_n\n",
    "\\end{pmatrix}\n",
    "=\n",
    "\\begin{pmatrix}\n",
    "1 & 1\\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}\n",
    "\\begin{pmatrix}\n",
    "f_{n-1} \\\\\n",
    "g_{n-1}\n",
    "\\end{pmatrix}\n",
    "\\text{ para }n\\ge 2\n",
    "$$\n",
    "\n",
    "con la condición inicial\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "f_1 \\\\\n",
    "g_1\n",
    "\\end{pmatrix}\n",
    "=\n",
    "\\begin{pmatrix}\n",
    "1 \\\\\n",
    "0\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "Este ecuación es muy simple de resolver \"desenrrollándola\", y su solución es\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "f_n \\\\\n",
    "g_n\n",
    "\\end{pmatrix}\n",
    "=\n",
    "\\begin{pmatrix}\n",
    "1 & 1\\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-1}\n",
    "\\begin{pmatrix}\n",
    "1 \\\\\n",
    "0\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "\n",
    "Por lo tanto, para resolver el problema del calcular $f_n$, basta evaluar esta fórmula matricial y luego tomar la primera componente del vector resultante.\n",
    "\n",
    "Recordando que para la elevación a potencia podemos usar el algoritmo binario, la evaluación de la fórmula se puede hacer en tiempo logarítmico, y por lo tanto el problema de calcular $f_n$ se puede resolver en tiempo $\\Theta(\\log{n})$.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La siguiente es una versión del algoritmo `potencia` adaptada para calcular $B=A^n$ cuando $A$ es una matriz cuadrada:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def potencia(A, n):\n",
    "    B=np.eye(len(A),dtype=int) # matriz identidad\n",
    "    k=n\n",
    "    C=A\n",
    "    while k>0:\n",
    "        while k%2==0:\n",
    "            C=np.dot(C,C) # C=C**2\n",
    "            k//=2\n",
    "        B=np.dot(B,C) # B=C*C\n",
    "        k-=1\n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    F=np.dot(potencia(np.array([[1,1],[1,0]]),n-1), np.array([[1],[0]]))\n",
    "    return F[0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "print(fibonacci(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 3.2\n",
    "\n",
    "Si $f_n$ son los números de Fibonacci, demuestre que, para todo $n\\ge 1$,\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "1 & 1\\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n\n",
    "=\n",
    "\\begin{pmatrix}\n",
    "f_{n+1} & f_n \\\\\n",
    "f_n & f_{n-1}\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo: Encontrar la parentización óptima para multiplicación de $n$ matrices\n",
    "\n",
    "Hemos visto que las técnicas de _memoización_ y de _tabulación_ nos permiten construir algoritmos eficientes en algunos problemas en que la recursividad aplicada directamente daría soluciones muy ineficientes.\n",
    "\n",
    "Cuando estas técnicas se aplican a problemas de optimización, hablamos de _programación dinámica_.\n",
    "\n",
    "Consideremos el siguiente problema: Dadas tres matrices $A$, $B$ y $C$ para las cuales se desea calcular su producto $A B C$, ¿qué es más eficiente, calcular $(A B)C$ o calcular $A (B C)$?\n",
    "\n",
    "La respuesta depende de las dimensiones de las matrices involucradas.\n",
    "Si una matriz $A$ es de $p\\times q$ y otra matriz $B$ es de $q\\times r$, calcular su producto $A B$ utilizando el algoritmo usual requiere hacer $pqr$ multiplicaciones escalares, y un número similar de sumas.\n",
    "\n",
    "Para nuestro problema de calcular $ABC$, supongamos por ejemplo que $A$ es de $100\\times 10$, $B$ de $10\\times 100$ y $C$ de $100\\times 10$, tenemos que\n",
    "\n",
    "* Calcular $(AB)C$ requiere $100\\times 10\\times 100+100\\times 100\\times 10=200.000$ multiplicaciones\n",
    "* Calcular $A(BC)$ requiere $10\\times 100\\times 10+100\\times 10\\times 10=20.000$ multiplicaciones\n",
    "\n",
    "La respuesta, por lo tanto, es que para las dimensiones dadas, la parentización óptima es $A(BC)$.\n",
    "\n",
    "Consideremos ahora el problema general. Dadas $n$ matrices $A_1, A_2, \\ldots, A_n$ y números $p[0], p[1], \\ldots, p[n]$ tales que la matriz $A_i$ es de $p[i-1]\\times p[i]$, encontrar el costo (en número de multiplicaciones) de la parentización óptima para calcular el producto\n",
    "\n",
    "$$\n",
    "A_1 A_2 \\cdots A_n\n",
    "$$\n",
    "\n",
    "Generalicemos el problema para poder abordarlo recursivamente (o inductivamente). Supongamos que el problema es encontrar el costo de la parentización óptima para calcular el producto\n",
    "\n",
    "$$\n",
    "A_i \\cdots A_j\n",
    "$$\n",
    "\n",
    "para $1\\le i\\le j\\le n$. Llamemos $m[i,j]$ a este costo óptimo.\n",
    "\n",
    "En el caso $i=j$ el producto involucra a una sola matriz, así que, trivialmente, $m[i,i]=0$. En el caso $i<j$, supongamos que parentizamos de modo que el producto se factorice como\n",
    "\n",
    "$$\n",
    "(A_i \\cdots A_k)(A_{k+1}\\cdots A_j)\n",
    "$$\n",
    "\n",
    "para algún $k\\in [i..j-1]$. Suponiendo que cada producto parentizado se ha calculado en forma óptima, el costo total sería\n",
    "\n",
    "$$\n",
    "m[i,k]+m[k+1,j]+p[i-1]\\times p[k]\\times p[j]\n",
    "$$\n",
    "\n",
    "Esto no es necesariamente óptimo para el producto $A_i \\cdots A_j$, porque podríamos haber elegido el valor equivocado de $k$. Para asegurarnos de alcanzar el óptimo, tenemos que minimizar sobre todo $k$:\n",
    "\n",
    "$$\n",
    "m[i,j] = \\min_{i\\le k\\le j-1} \\left\\{ m[i,k]+m[k+1,j]+p[i-1]\\times p[k]\\times p[j] \\right\\}\n",
    "$$\n",
    "\n",
    "Esto lo podríamos implementar mediante una función recursiva, pero, tal como sucedía en el ejemplo de Fibonacci, ésta demoraría un tiempo exponencial en ejecutarse, porque generaría y evaluaría todas las parentizaciones posibles.\n",
    "Esta búsqueda exhaustiva es un método que encuentra la respuesta correcta (se le suele llamar \"método fuerza bruta\"), pero usualmente es demasiado ineficiente.\n",
    "\n",
    "Afortunadamente, en este caso podemos usar tabulación, porque hay solo alrededor de $n^2/2$ casilleros que llenar en la matriz $m$, y los podemos ir llenando en un orden tal que al calcular el mínimo sobre todo $k$, los casilleros necesarios ya han sido llenados previamente.\n",
    "\n",
    "En efecto, introduzcamos una nueva variable $d=j-i+1$. Esto es el número de matrices involucradas en el producto $A_i \\cdots A_j$. Lo que haremos será ir llenando la matriz en orden ascendente de la variable $d$, comenzando con el caso trivial $d=1$, hasta terminar con el caso $d=n$, que corresponde a la solución del problema original."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "def opti_multi_mat(p):\n",
    "    n=len(p)-1\n",
    "    m=np.zeros((n+1,n+1)) # Esto ya deja la diagonal en cero\n",
    "    for d in range(2,n+1):\n",
    "        for i in range(1,n-d+2):\n",
    "            j=i+d-1\n",
    "            m[i,j]=math.inf # +infinito\n",
    "            for k in range(i,j):\n",
    "                q=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]\n",
    "                if q<m[i,j]:\n",
    "                    m[i,j]=q\n",
    "    return m[1,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20000.0\n"
     ]
    }
   ],
   "source": [
    "p=np.array([100,10,100,10])\n",
    "print(opti_multi_mat(p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es fácil ver que este algoritmo corre en tiempo $O(n^3)$, porque debe rellenar $\\Theta(n^2)$ casilleros, y cada uno puede requerir examinar $n$ valores posibles de $k$ en el peor caso.\n",
    "Esto es significativamente mejor que el algoritmo de fuerza bruta.\n",
    "\n",
    "Esta cota cúbica podría, sin embargo, ser un poco exagerada, porque en muchos casos la variable $k$ toma mucho menos que $n$ valores. Un cálculo más preciso nos señala que el número total de veces que se ejecuta el cuerpo del ciclo `for k` es igual a\n",
    "\n",
    "$$\n",
    "\\sum_{1\\le i\\le k<j\\le n} 1 =\\frac{n(n-1)(n+1)}{6} = \\Theta(n^3)\n",
    "$$\n",
    "\n",
    "Por lo tanto el algoritmo en realidad demora un tiempo cúbico.\n",
    "\n",
    "Como vemos, el resultado del proceso es el costo óptimo, pero eso no nos da ninguna información sobre cuál es la parentización óptima. Pero en realidad la información está ahí, porque el valor de $k$ para el cual se alcanza el mínimo nos dice dónde separar la parentización en cada caso. Basta entonces con que dejemos anotado, para cada $i,j$ cuál es el valor de $k$ para el que se alcanza el mínimo.\n",
    "Llamemos $s[i,j]$ a ese valor de $k$.\n",
    "\n",
    "Modifiquemos nuestra función para que construya y retorne la matriz $s$ además del costo óptimo, y escribamos otra función que, dada esa matriz $s$, imprima la fórmula parentizada de la manera óptima."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "def opti_multi_mat(p):\n",
    "    n=len(p)-1\n",
    "    m=np.zeros((n+1,n+1)) # Esto ya deja la diagonal en cero\n",
    "    s=np.zeros((n+1,n+1),dtype=int)\n",
    "    for d in range(2,n+1):\n",
    "        for i in range(1,n-d+2):\n",
    "            j=i+d-1\n",
    "            m[i,j]=math.inf # +infinito\n",
    "            for k in range(i,j):\n",
    "                q=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]\n",
    "                if q<m[i,j]:\n",
    "                    m[i,j]=q\n",
    "                    s[i,j]=k # anotamos dónde se alcanza el min\n",
    "    return (m[1,n],s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def paren_desde_hasta(s,i,j):\n",
    "    if i==j:\n",
    "        return \"A\"+str(i)\n",
    "    else:\n",
    "        return \"(\"+paren_desde_hasta(s,i,s[i,j])+\" \"\\\n",
    "                +paren_desde_hasta(s,s[i,j]+1,j)+\")\"\n",
    "\n",
    "def parentizacion(s):\n",
    "    n=len(s)-1\n",
    "    return paren_desde_hasta(s,1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(A1 (A2 A3))\n",
      "Costo= 20000.0\n"
     ]
    }
   ],
   "source": [
    "p=np.array([100,10,100,10])\n",
    "(opt,s)=opti_multi_mat(p)\n",
    "print(parentizacion(s))\n",
    "print(\"Costo=\", opt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((A1 (A2 A3)) ((A4 A5) A6))\n",
      "Costo= 15125.0\n"
     ]
    }
   ],
   "source": [
    "p=np.array([30,35,15,5,10,20,25])\n",
    "(opt,s)=opti_multi_mat(p)\n",
    "print(parentizacion(s))\n",
    "print(\"Costo=\", opt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para recapitular, la técnica de diseño de programación dinámica divide un problema en varios subproblemas con la misma estructura que el problema original, luego se resuelven dichos subproblemas y finalmente, a partir de éstos, se obtiene la solución al problema original. La diferencia radica en que la programación dinámica se ocupa cuando los subproblemas se repiten, como en el cálculo de los números de Fibonacci. En este caso, en vez de usar recursión para obtener las soluciones a los subproblemas éstas se van tabulando en forma bottom-up, y luego estos resultados son utilizados para resolver subproblemas más grandes. De esta forma, se evita el tener que realizar el mismo llamado recursivo varias veces.\n",
    "\n",
    "La programación dinámica se ocupa en general para resolver problemas de optimización (maximización o minimización de alguna función objetivo). Estos problemas pueden tener una o varias soluciones óptimas, y el objetivo es encontrar alguna de ellas. Los pasos generales para utilizar programación dinámica en la resolución de un problema son los siguientes:\n",
    "\n",
    "* Encontrar la subestructura óptima del problema, es decir, encontrar aquellos subproblemas en los que se compone el problema original, tal que si uno encuentra sus soluciones óptimas entonces es posible obtener la solución óptima al problema original.\n",
    "\n",
    "* Definir el valor de la solución óptima en forma recursiva.\n",
    "\n",
    "* Calcular el valor de la solución partiendo primero por los subproblemas más pequeños y tabulándo las soluciones, lo que luego permite obtener la solución de subproblemas más grandes. Terminar cuando se tiene la solución al problema original.\n",
    "\n",
    "Estos pasos permiten obtener el valor óptimo de la solución al problema. También es posible ir guardando información extra en cada paso del algoritmo, que luego permita reconstruir el camino realizado para hallar la solución óptima (por ejemplo, para obtener la instancia específica de la solución óptima, y no sólo el valor óptimo de la función objetivo)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo: Encontrar la subsecuencia común más larga\n",
    "\n",
    "Dadas dos secuencias de datos $a$ y $b$, de largo $m$ y $n$ respectivamente (pueden ser listas o strings), una subsecuencia común es una subsecuencia de elementos (posiblemente saltados) de $a$ que coincide con una subsecuencia de $b$. Nos interesa encontrar el largo de la subsecuencia común más larga (en inglés *LCS*, por *longest common subsequence*).\n",
    "\n",
    "Este problema se puede resolver recursivamente.\n",
    "La condición de borde es que la subsecuencia común más larga entre dos secuencias en que al menos una de ellas es vacía (de largo cero) es la secuencia vacía.\n",
    "Si ambas secuencias son no vacías, observamos que una subsecuencia común más larga entre $a[0:i]$ y $b[0:j]$ se puede obtener de la siguiente manera:\n",
    "\n",
    "* Si ambas secuencias terminan en el mismo elemento, agregamos ese elemento al final de la subsecuencia común más larga entre $a[0:i-1]$ y $b[0:j-1]$\n",
    "* Si no terminan en el mismo elemento, tomamos lo más largo que resulte entre ignorar el último elemento de $a[0:i]$ y buscar una subsecuencia común más larga entre $a[0:i-1]$ y $b[0:j]$, o ignorar el último elemento de $b[0:j]$ y buscar una subsecuencia común más larga entre $a[0:i]$ y $b[0:j-1]$\n",
    "\n",
    "Si llamamos $L_{i,j}$ al largo de la subsecuencia común más larga entre $a[0:i]$ y $b[0:j]$, tenemos que $L_{0,j}=L_{i,0}=0$, y que para $i,j>0$\n",
    "\n",
    "$$\n",
    "L_{i,j}=\n",
    "\\begin{cases}\n",
    "1+L_{i-1,j-1} & \\text{si } a[i-1]=b[j-1]\\\\\n",
    "\\max\\{L_{i,j-1},L_{i-1,j}\\} & \\text{si } a[i-1] \\ne b[j-1]\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "El resultado buscado es $L_{m,n}$.\n",
    "\n",
    "Una implementación eficiente de este algoritmo se puede lograr usando tabulación:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def LCS(a,b):\n",
    "    \"\"\"\n",
    "    Encuentra el largo de la subsecuencia común más larga entre a y b\n",
    "    \"\"\"\n",
    "    m=len(a)\n",
    "    n=len(b)\n",
    "    L=np.zeros((m+1,n+1),dtype=int)\n",
    "    for i in range(1,m+1):\n",
    "        for j in range(1,n+1):\n",
    "            if a[i-1]==b[j-1]:\n",
    "                L[i,j]=1+L[i-1,j-1]\n",
    "            else:\n",
    "                L[i,j]=max(L[i-1,j],L[i,j-1])\n",
    "    return L[m,n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "print(LCS(\"abracadabra\",\"pasapalabra\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 3.3\n",
    "\n",
    "Modifique la función ``LCS`` para que retorne una subsecuencia común más larga, en lugar de retornar su longitud."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmos Avaros (*Greedy Algorithms*)\n",
    "\n",
    "Se dice que un algoritmo de optimización es _avaro_ si siempre toma la decisión óptima de corto plazo.\n",
    "Por ejemplo, un algoritmo avaro que intenta llegar a la cima del cerro más alto, daría siempre un paso en la dirección que le permite subir más con ese paso.\n",
    "\n",
    "En general, la estrategia avara no garantiza llegar a un óptimo global, porque es fácil quedarse atrapado en un óptimo local (en nuestro ejemplo, llegar a la cima de un cerro pequeño y no poder salir de ahí).\n",
    "\n",
    "Sin embargo, hay problemas para los cuales la estrategia avara sí encuentra un óptimo global:\n",
    "\n",
    "### Ejemplo: Asignación de actividades\n",
    "\n",
    "Supongamos que hay un conjunto $n$ de actividades $a_1, \\ldots, a_n$ que para poder realizarse necesitan acceso a un recurso que no puede ser compartido.\n",
    "Por ejemplo, $n$ reuniones que solo se pueden realizar en una única sala.\n",
    "\n",
    "Cada actividad tiene un tiempo de inicio $t_i$ y un tiempo de término $t_f$, lo que se interpreta como que necesita ocupar el recurso en el intervalo $[t_i,t_f)$, cerrado a la izquierda, abierto a la derecha. Se dice que dos actividades son compatibles si sus respectivos intervalos no se traslapan. El problema de asignación de actividades consiste en encontrar un conjunto maximal de actividades compatibles.\n",
    "\n",
    "Por ejemplo, para el siguiente conjunto de actividades,\n",
    "\n",
    "![actividades](actividades.png)\n",
    "\n",
    "un conjunto compatible maximal es $\\{a_1,a_3,a_4,a_6,a_7\\}$.\n",
    "\n",
    "Un problema de optimización de este tipo siempre se puede resolver por fuerza bruta, porque el número de soluciones posibles es finito, pero tratamos de evitarlo a menos que no haya alternativa, porque puede demorar un tiempo exponencial.\n",
    "\n",
    "En este caso, podemos resolver el problema de manera mucho más eficiente (tiempo $\\Theta(n)$) usando una estrategia avara.\n",
    "\n",
    "Supongamos que las actividades están ordenadas en forma ascendente por su hora de término $t_f$.\n",
    "El algoritmo escoge la primera actividad disponible en este orden, luego elimina todas las actividades que se superponen con ella, y a continuación repite el proceso con las actividades restantes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Input es una matriz con filas de la forma [ti,tf]\n",
    "# ordenada ascendente por tf\n",
    "import numpy as np\n",
    "A=np.array([ [0,0], # la fila 0 se ignora\n",
    "    [1,3],\n",
    "    [0,6],\n",
    "    [5,7],\n",
    "    [7,8],\n",
    "    [4,9],\n",
    "    [10,11],\n",
    "    [11,12],\n",
    "    [9,12]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def asigna_avaro(A):\n",
    "    n=len(A)-1\n",
    "    sol=[1] # la primera tarea es siempre parte de la solución\n",
    "    j=1     # j identifica a la más reciente tarea seleccionada\n",
    "    for i in range(2,n+1):\n",
    "        if A[i,0]>=A[j,1]: # ti[i]>=tf[j] ==> i es la primera tarea\n",
    "            sol.append(i)  # que es compatible con j, se agrega\n",
    "            j=i            # a la solución y pasa a ser la más reciente\n",
    "    return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 4, 6, 7]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "asigna_avaro(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo resultante se llama \"*Earliest-Finish-First*\" (*EFF*).\n",
    "\n",
    "¿Cómo podemos estar seguros que la solución encontrada es realmente óptima?\n",
    "\n",
    "Demostraremos por inducción sobre $n$ que el algoritmo avaro encuentra una solución óptima.\n",
    "\n",
    "Trivialmente el algoritmo encuentra la solución correcta en el caso $n=1$.\n",
    "\n",
    "Consideremos entonces el caso $n>1$ y supongamos, por contradicción, que no existe ninguna solución óptima que incluya a la actividad $a_1$. Consideremos una solución óptima y supongamos que su actividad con menor $t_f$  es la actividad $a_k$. Dado que la lista está ordenada por $t_f$, se tiene que $t_f[1]\\le t_f[k]$. Como la solución no puede contener ninguna otra actividad que comience antes de $t_f[k]$, entonces podemos reemplazar la actividad $a_k$ por la actividad $a_1$ y obtenemos otra solución válida y que tiene el mismo número de actividades, por lo tanto también es óptima: contradicción con la hipótesis que $a_1$ no podía ser parte de ninguna solución óptima.\n",
    "\n",
    "Por lo tanto, $a_1$ puede ser parte de una solución óptima, y en consecuencia ninguna actividad que se superponga con ella puede estar incluída. Si las eliminamos, lo que queda es un problema de optimización del mismo tipo, pero con un número estrictamente menor de actividades, el cual lo resuelve correctamente el algoritmo avaro por hipótesis de inducción."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking\n",
    "\n",
    "Hay ocasiones en que no tenemos más alternativa que resolver un problema por prueba y error, explorando un espacio de soluciones en forma exhaustiva. Una forma de hacerlo es en forma recursiva, probando distintas vías de solución hasta que alguna funcione, o hasta agotar las posibilidades.\n",
    "\n",
    "### El laberinto\n",
    "\n",
    "Supongamos que nos encontramos al interior de un laberinto y queremos encontrar la salida.\n",
    "Si no tenemos ninguna información adicional, lo que podemos hacer es intentar salir en una dirección, si eso no funciona intentar en otras, etc.\n",
    "\n",
    "Para fijar las ideas, supongamos que el laberinto se dibuja usando caracteres del teclado, donde los espacios en blanco son lugares por donde se puede pasar, y el sigo \"igual\" representa la salida.\n",
    "Todos los demás símbolos representan murallas. Por ejemplo,\n",
    "\n",
    "```\n",
    "+--+-----+--+\n",
    "|  |     |  |\n",
    "|  +--+     =\n",
    "|     |  |  |\n",
    "+--+  |  |  |\n",
    "|  |        |\n",
    "|  |     |  |\n",
    "+--+-----+--+\n",
    "```\n",
    "\n",
    "Almacenaremos el laberinto en una lista de strings (de a uno por línea): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [\n",
    "\"+--+-----+--+\",\n",
    "\"|  |     |  |\",\n",
    "\"|  +--+     =\",\n",
    "\"|     |  |  |\",\n",
    "\"+--+  |  |  |\",\n",
    "\"|  |        |\",\n",
    "\"|  |     |  |\",\n",
    "\"+--+-----+--+\"\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema es determinar si existe una manera de salir si uno comienza en el casillero $[i][j]$. Solo está permitido moverse en dirección  horizontal o vertical, no en diagonal.\n",
    "\n",
    "Resolveremos este problema escribiendo una función booleana $salida(i,j)$ que retorna verdadero si existe un camino hacia la salida a partir de la coordenada $i,j$.\n",
    "Esto lo hace intentando en las cuatro direcciones:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def salida(i,j):\n",
    "    if L[i][j]==\"=\": # encontramos la salida\n",
    "        return True\n",
    "    if L[i][j]!=\" \": # espacio ocupado\n",
    "        return False\n",
    "    if salida(i,j-1) \\\n",
    "    or salida(i,j+1) \\\n",
    "    or salida(i-1,j) \\\n",
    "    or salida(i+1,j):\n",
    "        return True\n",
    "    return False  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probemos si es posible salir desde la posición $5,2$ (¡pero por si acaso estemos atentos al botón para interrumpir el proceso!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded in comparison",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-19-0ea1bd4da578>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      9\u001b[0m \u001b[0;34m\"+--+-----+--+\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m ]\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-18-ba8a4ad77a65>\u001b[0m in \u001b[0;36msalida\u001b[0;34m(i, j)\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m!=\u001b[0m\u001b[0;34m\" \"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# espacio ocupado\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-18-ba8a4ad77a65>\u001b[0m in \u001b[0;36msalida\u001b[0;34m(i, j)\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "... last 2 frames repeated, from the frame below ...\n",
      "\u001b[0;32m<ipython-input-18-ba8a4ad77a65>\u001b[0m in \u001b[0;36msalida\u001b[0;34m(i, j)\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m!=\u001b[0m\u001b[0;34m\" \"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# espacio ocupado\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[0;32mor\u001b[0m \u001b[0msalida\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded in comparison"
     ]
    }
   ],
   "source": [
    "L = [\n",
    "\"+--+-----+--+\",\n",
    "\"|  |     |  |\",\n",
    "\"|  +--+     =\",\n",
    "\"|     |  |  |\",\n",
    "\"+--+  |  |  |\",\n",
    "\"|  |        |\",\n",
    "\"|  |     |  |\",\n",
    "\"+--+-----+--+\"\n",
    "]\n",
    "print(salida(5,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lo más probable es que el programa se haya caído por exceso de recursividad antes de que tuviéramos que interrumpirlo a mano.\n",
    "\n",
    "Lo que sucede es que olvidamos incluir algo que impidiera que el programa explorara de nuevo un camino que ya antes había recorrido sin éxito, y eso lo condujo a entrar en un \"loop\" infinito.\n",
    "\n",
    "Para evitar esto, iremos marcando con un símbolo \"x\" los casilleros a medida que van siendo visitados.\n",
    "De esta forma, ninguno se puede visitar más de una vez:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def salida(i,j):\n",
    "    if L[i][j]==\"=\": # encontramos la salida\n",
    "        return True\n",
    "    if L[i][j]!=\" \": # espacio ocupado\n",
    "        return False\n",
    "    L[i]=L[i][:j]+\"x\"+L[i][j+1:]\n",
    "    if salida(i,j-1) \\\n",
    "    or salida(i,j+1) \\\n",
    "    or salida(i-1,j) \\\n",
    "    or salida(i+1,j):\n",
    "        return True\n",
    "    return False  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "+--+-----+--+\n",
      "|  |     |  |\n",
      "|  +--+     =\n",
      "|     |  |  |\n",
      "+--+  |  |  |\n",
      "|xx|        |\n",
      "|xx|     |  |\n",
      "+--+-----+--+\n"
     ]
    }
   ],
   "source": [
    "L = [\n",
    "\"+--+-----+--+\",\n",
    "\"|  |     |  |\",\n",
    "\"|  +--+     =\",\n",
    "\"|     |  |  |\",\n",
    "\"+--+  |  |  |\",\n",
    "\"|  |        |\",\n",
    "\"|  |     |  |\",\n",
    "\"+--+-----+--+\"\n",
    "]\n",
    "print(salida(5,2))\n",
    "for linea in L:\n",
    "    print(linea)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "+--+-----+--+\n",
      "|xx|xxxxx|  |\n",
      "|xx+--+xxxxx=\n",
      "|xxxxx|xx|xx|\n",
      "+--+xx|xx|xx|\n",
      "|  |xxxxxxxx|\n",
      "|  |xxxxx|xx|\n",
      "+--+-----+--+\n"
     ]
    }
   ],
   "source": [
    "L = [\n",
    "\"+--+-----+--+\",\n",
    "\"|  |     |  |\",\n",
    "\"|  +--+     =\",\n",
    "\"|     |  |  |\",\n",
    "\"+--+  |  |  |\",\n",
    "\"|  |        |\",\n",
    "\"|  |     |  |\",\n",
    "\"+--+-----+--+\"\n",
    "]\n",
    "print(salida(4,10))\n",
    "for linea in L:\n",
    "    print(linea)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 3.4\n",
    "\n",
    "Modifique la función para que marque con `\".\"` los casilleros por donde hubo intentos no exitosos de salir, y con `\"x\"` los casilleros que finalmente condujeron a la salida."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}