Alejandro_Fernandez_AG1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Alejandro Fernandez - AG1.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "mount_file_id": "1PMdtV_Nu8G6ehzMEML3qi1g-JLHuTfpa",
      "authorship_tag": "ABX9TyOFqV96emfYUwvzI8TSlJeq",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/alejandrofdzllorente/public/blob/main/Alejandro_Fernandez_AG1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8gGSEWh5yxsE"
      },
      "source": [
        "# Actividad Guiada 1 de Algoritmos de Optimización 1\r\n",
        "\r\n",
        "Alejandro Fernández Llorente\r\n",
        "\r\n",
        "URL: https://colab.research.google.com/drive/1PMdtV_Nu8G6ehzMEML3qi1g-JLHuTfpa?usp=sharing\r\n",
        "\r\n",
        "GitHub: https://github.com/alejandrofdzllorente/03MAIR-Algoritmos-de-Optimizacion/blob/main/Alejandro_Fernandez_AG1.ipynb\r\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tvYaC94p83ln"
      },
      "source": [
        "##Torres de Hanoi utilizando \"divide y vencerás\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8EynsOiZ5p04",
        "outputId": "0edea0fd-1a2a-43e5-b129-6a5ff8559461"
      },
      "source": [
        "\r\n",
        "\r\n",
        "def TorresHanoi(fichas,origen, destino):\r\n",
        "  posiblidades = {1,2,3}\r\n",
        "  #caso base\r\n",
        "  if (fichas == 1):\r\n",
        "    print(\"Lleva la ficha desde\" , origen , \"hasta \" , destino)\r\n",
        "  else:\r\n",
        "    destinoAux = next(iter(posiblidades - {origen, destino}))\r\n",
        "    TorresHanoi(fichas - 1 , origen, destinoAux)\r\n",
        "    print(\"Lleva la ficha desde\" , origen , \"hasta \" , destino)\r\n",
        "    TorresHanoi(fichas - 1 , destinoAux, destino)\r\n",
        "\r\n",
        "\r\n",
        "#solución deseada\r\n",
        "TorresHanoi(3,1,3)\r\n",
        "\r\n",
        "#TorresHanoi(1,1,3)\r\n",
        "\r\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Lleva la ficha desde 1 hasta  3\n",
            "Lleva la ficha desde 1 hasta  2\n",
            "Lleva la ficha desde 3 hasta  2\n",
            "Lleva la ficha desde 1 hasta  3\n",
            "Lleva la ficha desde 2 hasta  1\n",
            "Lleva la ficha desde 2 hasta  3\n",
            "Lleva la ficha desde 1 hasta  3\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BE2L0jExuF41"
      },
      "source": [
        "## Devolución de cambio utilizando técnica voraz"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bpYTIvzfuOOg",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a4dd516e-56d5-4db0-9479-8dbbe778d39c"
      },
      "source": [
        "def cambioMonedas(cantidad, sistema):\r\n",
        "  #lista con la solución, inicializada a cero\r\n",
        "  solucion = [0] * len(sistema)\r\n",
        "\r\n",
        "  for i,valor in enumerate(sistema):\r\n",
        "    #hallamos el divisor entero y lo guardamos\r\n",
        "    solucion[i] = cantidad // valor\r\n",
        "    #si es cero, continuamos\r\n",
        "    if (solucion[i] == 0):\r\n",
        "      continue\r\n",
        "    #en caso contrario, calculamos la cantidad que falta\r\n",
        "    cantidad = cantidad % (valor*solucion[i])\r\n",
        "  \r\n",
        "  #solución obtenida\r\n",
        "  return solucion\r\n",
        "\r\n",
        "cambioMonedas(141,[25,10,5,2])"
      ],
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[5, 1, 1, 0]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 31
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0uBpp_iZFOEH"
      },
      "source": [
        "### ¿Qué tiene que pasar para que funcione bien?\r\n",
        "\r\n",
        "Si entendemos funcionar bien como que nos dé el mínimo número de monedas, lo ideal seria que la cantidad a cambiar sea múltiplo del número más grande del sistema monetario."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MuIZNG2-F7lF"
      },
      "source": [
        "##Problema de las N-Reinas utilizando backtracking"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Xn4zPtrUGCgC",
        "outputId": "400c508d-e444-40b8-a204-0e7681738bf8"
      },
      "source": [
        "def escribe(S):\r\n",
        "  n = len(S)\r\n",
        "  for x in range(n):\r\n",
        "    print(\"\")\r\n",
        "    for i in range(n):\r\n",
        "      if S[i] == x+1:\r\n",
        "        print(\" X \" , end=\"\")\r\n",
        "      else:\r\n",
        "        print(\" - \", end=\"\")\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "def es_prometedora(SOLUCION,etapa):\r\n",
        "  #print(SOLUCION)\r\n",
        "  #Si la solución tiene dos valores iguales no es valida => Dos reinas en la misma fila\r\n",
        "  for i in range(etapa+1):\r\n",
        "    #print(\"El valor \" + str(SOLUCION[i]) + \" está \" +  str(SOLUCION.count(SOLUCION[i])) + \" veces\")\r\n",
        "    if SOLUCION.count(SOLUCION[i]) > 1:       \r\n",
        "      return False\r\n",
        "\r\n",
        "    #Verifica las diagonales\r\n",
        "    for j in range(i+1, etapa +1 ):\r\n",
        "      #print(\"Comprobando diagonal de \" + str(i) + \" y \" + str(j))\r\n",
        "      if abs(i-j) == abs(SOLUCION[i]-SOLUCION[j]) : return False\r\n",
        "  return True\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "def reinas (nReinas, solucion=[], etapa=0):\r\n",
        "  #inicializamos el vector solución\r\n",
        "  if (len(solucion) == 0):\r\n",
        "    solucion = [0 for i in range(0,nReinas)]\r\n",
        "\r\n",
        "  for i in range(1,nReinas + 1):\r\n",
        "    solucion[etapa] = i\r\n",
        "\r\n",
        "    if (es_prometedora(solucion,etapa)):\r\n",
        "      if (etapa == nReinas - 1):\r\n",
        "        print (solucion)\r\n",
        "        escribe(solucion)\r\n",
        "        print()\r\n",
        "        print()\r\n",
        "      else:\r\n",
        "        reinas(nReinas,solucion,etapa+1)\r\n",
        "    #reset\r\n",
        "    solucion[etapa] = 0\r\n",
        "\r\n",
        "reinas(4)"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2, 4, 1, 3]\n",
            "\n",
            " -  -  X  - \n",
            " X  -  -  - \n",
            " -  -  -  X \n",
            " -  X  -  - \n",
            "\n",
            "[3, 1, 4, 2]\n",
            "\n",
            " -  X  -  - \n",
            " -  -  -  X \n",
            " X  -  -  - \n",
            " -  -  X  - \n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "110kI03InvLg"
      },
      "source": [
        "## Algoritmo de encontrar los dos puntos más cercanos\r\n",
        "\r\n",
        "(Subido al foro evaluable)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MIYk9jEEn4Z0"
      },
      "source": [
        "import math\r\n",
        "import random\r\n",
        "from time import time\r\n",
        "import matplotlib.pyplot as plt\r\n",
        "\r\n",
        "#distanciaEuclídea\r\n",
        "def distancia(p1,p2):\r\n",
        "  sum = 0\r\n",
        "  for i in range(0,len(p1)):\r\n",
        "    sum = sum +  math.sqrt(pow(p1[i] - p2[i],2))\r\n",
        "  return sum\r\n",
        "\r\n",
        "def creaLista(dimension, elementos):\r\n",
        "    #creación de x listas\r\n",
        "    for i in range(0,elementos):\r\n",
        "        locals()['elementos' + str(i)] =  [random.randint(0,1000) for _ in range(dimension)]\r\n",
        "    lista = []\r\n",
        "    #unión de las listas en una lista\r\n",
        "    for i in range(0,elementos):\r\n",
        "        lista.append(locals()['elementos' + str(i)])\r\n",
        "    return lista\r\n",
        "\r\n",
        "\r\n",
        "def puntosMasCercanos(dimension, elementos):\r\n",
        "    #se crea la lista con la función anterior\r\n",
        "    lista = creaLista(dimension, elementos)\r\n",
        "    #valor de comienzo, lo más grande posible\r\n",
        "    minimo = float('inf')\r\n",
        "    cercanos = ()\r\n",
        "    puntos=()\r\n",
        "    #inicio del tiempo del experimentos\r\n",
        "    start_time = time()\r\n",
        "    #EXPERIMENTO\r\n",
        "    for i in range(0,elementos):\r\n",
        "        for j in range( i + 1, elementos):\r\n",
        "            if distancia(lista[i],lista[j]) < minimo:\r\n",
        "                minimo = distancia(lista[i],lista[j])\r\n",
        "                cercanos = (lista[i],lista[j])\r\n",
        "                puntos = (i,j)\r\n",
        "    #tiempo de ejecución del experimento\r\n",
        "    tiempo = time() - start_time    \r\n",
        "    return [cercanos,puntos,tiempo]\r\n",
        "\r\n",
        "\r\n",
        "# =============================================================================\r\n",
        "#EXPERIMENTO\r\n",
        "# =============================================================================\r\n",
        "\r\n",
        "#número de valores por cada punto\r\n",
        "dimension = 5\r\n",
        "#número de puntos de la lista\r\n",
        "elementos = 200\r\n",
        "\r\n",
        "prueba = puntosMasCercanos(dimension, elementos)\r\n",
        "\r\n",
        "print(\"\")\r\n",
        "print(\"Los puntos más cercanos son los que tienen como valor: \" + str(prueba[0]))\r\n",
        "print(\"\")\r\n",
        "print(\"Los puntos más cercanos son los de las posiciones: \" + str(prueba[1]))\r\n",
        "print(\"\")\r\n",
        "print(\"El tiempo de ejecución para una dimensión \"+ str(dimension) +\" y \" + str(elementos) + \" elementos ha sido : \" + str(prueba[2]))\r\n",
        "print(\"\")\r\n",
        "\r\n",
        "\r\n",
        "# =============================================================================\r\n",
        "#PRUEBAS\r\n",
        "# =============================================================================\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "#prueba de subir elementos\r\n",
        "prueba1 = [5,1]\r\n",
        "prueba2 = [5,100]\r\n",
        "prueba3 = [5,200]\r\n",
        "prueba4 = [5,300]\r\n",
        "prueba5 = [5,400]\r\n",
        "prueba6 = [5,500]\r\n",
        "prueba7 = [5,600]\r\n",
        "prueba8 = [5,700]\r\n",
        "prueba9 = [5,800]\r\n",
        "prueba10 = [5,900]\r\n",
        "\r\n",
        "y = []\r\n",
        "\r\n",
        "for i in range (1,11):\r\n",
        "    locals()['resultados' + str(i)] = puntosMasCercanos(locals()['prueba' + str(i)][0], locals()['prueba' + str(i)][1])\r\n",
        "    y.append(locals()['resultados' + str(i)][2])\r\n",
        "    \r\n",
        "plt.figure(figsize=(16,3))\r\n",
        "plt.title('Crecimiento del tiempo subiendo el número de elementos en la lista')\r\n",
        "plt.ylabel(\"Tiempo de ejecución\")\r\n",
        "plt.plot(y)\r\n",
        "plt.show()    \r\n",
        "    \r\n",
        "    \r\n",
        "    \r\n",
        "\r\n",
        "#prueba de subir dimension\r\n",
        "prueba1 = [1,5]\r\n",
        "prueba2 = [100,5]\r\n",
        "prueba3 = [200,5]\r\n",
        "prueba4 = [300,5]\r\n",
        "prueba5 = [400,5]\r\n",
        "prueba6 = [500,5]\r\n",
        "prueba7 = [600,5]\r\n",
        "prueba8 = [700,5]\r\n",
        "prueba9 = [800,5]\r\n",
        "prueba10 = [900,5]\r\n",
        "\r\n",
        "y = []\r\n",
        "\r\n",
        "for i in range (1,11):\r\n",
        "    locals()['resultados' + str(i)] = puntosMasCercanos(locals()['prueba' + str(i)][0], locals()['prueba' + str(i)][1])\r\n",
        "    y.append(locals()['resultados' + str(i)][2])\r\n",
        "    \r\n",
        "plt.figure(figsize=(16,3))\r\n",
        "plt.title('Crecimiento del tiempo subiendo la dimensión la lista')\r\n",
        "plt.ylabel(\"Tiempo de ejecución\")\r\n",
        "plt.plot(y)\r\n",
        "plt.show()    \r\n",
        "    \r\n",
        "\r\n",
        "\r\n",
        "#prueba de subir las dos\r\n",
        "prueba1 = [1,1]\r\n",
        "prueba2 = [50,50]\r\n",
        "prueba3 = [100,100]\r\n",
        "prueba4 = [150,150]\r\n",
        "prueba5 = [200,200]\r\n",
        "prueba6 = [250,250]\r\n",
        "prueba7 = [300,300]\r\n",
        "prueba8 = [350,350]\r\n",
        "prueba9 = [450,450]\r\n",
        "prueba10 = [500,500]\r\n",
        "\r\n",
        "y = []\r\n",
        "\r\n",
        "for i in range (1,11):\r\n",
        "    locals()['resultados' + str(i)] = puntosMasCercanos(locals()['prueba' + str(i)][0], locals()['prueba' + str(i)][1])\r\n",
        "    y.append(locals()['resultados' + str(i)][2])\r\n",
        "    \r\n",
        "plt.figure(figsize=(16,3))\r\n",
        "plt.title('Crecimiento del tiempo subiendo todo')\r\n",
        "plt.ylabel(\"Tiempo de ejecución\")\r\n",
        "plt.plot(y)\r\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ICvFO9yxr-iz"
      },
      "source": [
        "Dado que ésta parte la subí al foro, he realizado un código que obtiene, con las misma bases configurables, los tres puntos más cercanos entre sí."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vo7i_2zzrAlh",
        "outputId": "88476cab-d203-4fe9-c946-a80359045e11"
      },
      "source": [
        "#distanciaEuclídea\r\n",
        "def distancia(p1,p2,p3):\r\n",
        "  sum = 0\r\n",
        "  for i in range(0,len(p1)):\r\n",
        "    sum = sum +  math.sqrt(pow(p1[i] - p2[i] - p3[i],2))\r\n",
        "  return sum\r\n",
        "\r\n",
        "\r\n",
        "def tresPuntosMasCercanos(dimension, elementos):\r\n",
        "    if(elementos <= 3):\r\n",
        "      print(\"Se necesitan más de tres puntos\")\r\n",
        "      return\r\n",
        "    #se crea la lista con la función anterior\r\n",
        "    lista = creaLista(dimension, elementos)\r\n",
        "    #valor de comienzo, lo más grande posible\r\n",
        "    minimo = float('inf')\r\n",
        "    cercanos = ()\r\n",
        "    puntos=()\r\n",
        "    #inicio del tiempo del experimentos\r\n",
        "    start_time = time()\r\n",
        "    #EXPERIMENTO\r\n",
        "    for i in range(0,elementos):\r\n",
        "        for j in range( i + 1, elementos):\r\n",
        "          for k in range( j + 1, elementos):\r\n",
        "            if distancia(lista[i],lista[j],lista[k]) < minimo:\r\n",
        "                minimo = distancia(lista[i],lista[j],lista[k])\r\n",
        "                cercanos = (lista[i],lista[j],lista[k])\r\n",
        "                puntos = (i,j,k)\r\n",
        "    #tiempo de ejecución del experimento\r\n",
        "    tiempo = time() - start_time    \r\n",
        "    return [cercanos,puntos,tiempo]\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "#número de valores por cada punto\r\n",
        "dimension = 5\r\n",
        "#número de puntos de la lista\r\n",
        "elementos = 200\r\n",
        "\r\n",
        "prueba = tresPuntosMasCercanos(dimension, elementos)\r\n",
        "\r\n",
        "print(\"\")\r\n",
        "print(\"Los puntos más cercanos son los que tienen como valor: \" + str(prueba[0]))\r\n",
        "print(\"\")\r\n",
        "print(\"Los puntos más cercanos son los de las posiciones: \" + str(prueba[1]))\r\n",
        "print(\"\")\r\n",
        "print(\"El tiempo de ejecución para una dimensión \"+ str(dimension) +\" y \" + str(elementos) + \" elementos ha sido : \" + str(prueba[2]))\r\n",
        "print(\"\")"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "\n",
            "Los puntos más cercanos son los que tienen como valor: ([353, 514, 728, 723, 274], [194, 191, 689, 911, 75], [412, 193, 959, 644, 390])\n",
            "\n",
            "Los puntos más cercanos son los de las posiciones: (0, 2, 3)\n",
            "\n",
            "El tiempo de ejecución para una dimensión 5 y 4 elementos ha sido : 2.7179718017578125e-05\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}