{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOdB8U/IqwIjtFbtD6++niN",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/financieras/campus/blob/main/pilas/pilas21.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Push Swap método \"Modern Times\"\n",
        "En honor a la película de 1936 de Chaplin."
      ],
      "metadata": {
        "id": "chidGUe5WoVU"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "FJNpcZStWYia"
      },
      "outputs": [],
      "source": [
        "# FUNCIONES\n",
        "def sa(a,b):\n",
        "    if len(a) > 1: a[0],a[1] = a[1],a[0]\n",
        "    return a,b\n",
        "def sb(a,b):\n",
        "    if len(b) > 1: b[0],b[1] = b[1],b[0]\n",
        "    return a,b\n",
        "def ss(a,b):\n",
        "    sa(a,b)\n",
        "    sb(a,b)\n",
        "    return a,b\n",
        "def pa(a,b):\n",
        "    if len(b) > 0:\n",
        "        a.insert(0, b[0])\n",
        "        b.pop(0)\n",
        "    return a,b\n",
        "def pb(a,b):\n",
        "    if len(a) > 0:\n",
        "        b.insert(0, a[0])\n",
        "        a.pop(0)\n",
        "    return a,b\n",
        "def ra(a,b):\n",
        "    if len(a) > 1: a.append(a.pop(0))\n",
        "    return a,b\n",
        "def rb(a,b):\n",
        "    if len(b) > 1: b.append(b.pop(0))\n",
        "    return a,b\n",
        "def rr(a,b):\n",
        "    ra(a,b)\n",
        "    rb(a,b)\n",
        "    return a,b\n",
        "def rra(a,b):\n",
        "    if len(a) > 1: a.insert(0, a.pop())\n",
        "    return a,b\n",
        "def rrb(a,b):\n",
        "    if len(b) > 1: b.insert(0, b.pop())\n",
        "    return a,b\n",
        "def rrr(a,b):\n",
        "    rra(a,b)\n",
        "    rrb(a,b)\n",
        "    return a,b"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Generación de la pila A\n",
        "from random import sample, seed\n",
        "seed()\n",
        "\n",
        "def generaPilaA(n):\n",
        "    return sample(range(1, n+1), n)"
      ],
      "metadata": {
        "id": "nZLaWpTGW8Bu"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def algoritmo_LIS(arr):\n",
        "    n = len(arr)\n",
        "    lis = [1]*n\n",
        "    prev = list(range(n))  # una lista con los index\n",
        "    \n",
        "    # Compute optimized LIS values in bottom up manner\n",
        "    for i in range (1, n):\n",
        "        for j in range(i):\n",
        "            if arr[i] > arr[j] and lis[i] < lis[j] + 1:\n",
        "                lis[i] = lis[j]+1\n",
        "                prev[i] = j\n",
        "\n",
        "    # Initialize maximum to 0 to get the maximum of all\n",
        "    # LIS\n",
        "    maximum = 0\n",
        "    idx = 0\n",
        "\n",
        "    # Pick maximum of all LIS values\n",
        "    for i in range(n):\n",
        "        if maximum < lis[i]:\n",
        "            maximum = lis[i]\n",
        "            idx = i\n",
        "\n",
        "    seq = [arr[idx]]\n",
        "    while idx != prev[idx]:\n",
        "        idx = prev[idx]\n",
        "        seq.append(arr[idx])\n",
        "\n",
        "    return list(reversed(seq))"
      ],
      "metadata": {
        "id": "vG4BxbUlIhne"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Llevamos de la pila A hacia la pila B los elementos de la LIS\n",
        "\n",
        "def rotateLIS(lis):\n",
        "    global a\n",
        "    global b\n",
        "    global contador\n",
        "    for vlis in lis:\n",
        "        if a.index(vlis) < len(a)/2:\n",
        "            for i in range(a.index(vlis)):\n",
        "                ra(a,b); contador += 1\n",
        "        else:\n",
        "            for i in range(len(a)- a.index(vlis)):\n",
        "                rra(a,b); contador += 1\n",
        "        pb(a,b); contador += 1"
      ],
      "metadata": {
        "id": "wCS3Dp5i0U5F"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# PASOS NECESARIOS PARA COLOCAR CADA ELEMENTO DE A EN SU SITIO EN B\n",
        "# PASOS NECESARIOS = Pasos necesarios A + Pasos necesarios B\n",
        "\n",
        "# Pasos necesarios para situarse como el primer elemento de la pila A\n",
        "\n",
        "def necesariosA(a, b):   # rellena el array pasosA con todos los pasos necesarios para la pila A\n",
        "    for i in a:\n",
        "        if a.index(i) < len(a)/2:\n",
        "            pasosA.append(a.index(i))\n",
        "        else:\n",
        "            pasosA.append(-(len(a)- a.index(i)))\n",
        "\n",
        "def necesariosB(a,b):   # rellena el array pasosB con todos los pasos necesarios para la pila B\n",
        "    for v in a:\n",
        "        try:\n",
        "            objetivo_primero = max([x for x in b if x<v])\n",
        "        except:\n",
        "            objetivo_primero = max(b)   # objetivo_primero calcula el número que se ha de poner en la primera posición de B\n",
        "\n",
        "        if b.index(objetivo_primero) < len(b)/2:\n",
        "            pasosB.append(b.index(objetivo_primero))\n",
        "        else:\n",
        "            pasosB.append(-(len(b)- b.index(objetivo_primero)))\n",
        "\n",
        "def totaliza(a,b):   # totalizar pasos\n",
        "    global total\n",
        "    for i in range(len(pasosA)):\n",
        "        if pasosA[i] * pasosB[i] < 0:   # si son de distinto signo\n",
        "            total.append(abs(pasosA[i]) + abs(pasosB[i]))\n",
        "        else:\n",
        "            total.append(max(abs(pasosA[i]), abs(pasosB[i])))\n",
        "\n",
        "def calculaIndexPasosMinimos():\n",
        "    global pasosA\n",
        "    global pasosB\n",
        "    global total\n",
        "    pasosA = []   # [0,1,2, ...,41,-41,... , -2,-1]  vector donde cada index está asociado con el valor del mismo index en A\n",
        "    pasosB = []   # [-3,2,-5, ..., -5,0]   estos dos arrays se han de recalcular cada vez que realmente se mueva algún elemento de A a B\n",
        "    total = []\n",
        "    necesariosA(a, b)\n",
        "    necesariosB(a, b)\n",
        "    totaliza(a,b)\n",
        "    return total.index(min(total))   # retorna el índice del elemento de la pila A que menos pasos totales necesita"
      ],
      "metadata": {
        "id": "UdlpzXahlsoh"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def giraA(a, b, indice, pasos):\n",
        "    global contador\n",
        "    for i in range(abs(pasos)):\n",
        "        if pasos > 0:\n",
        "            ra(a,b); contador += 1\n",
        "        elif pasos < 0:\n",
        "            rra(a,b); contador += 1\n",
        "\n",
        "def giraB(a, b, indice, pasos):\n",
        "    global contador\n",
        "    for i in range(abs(pasos)):\n",
        "        if pasos > 0:\n",
        "            rb(a,b); contador += 1\n",
        "        elif pasos < 0:\n",
        "            rrb(a,b); contador += 1\n",
        "\n",
        "# girando pilas A y B\n",
        "def giraPilas(a,b,indice):   # indice es el index del valor en la pila A que deseamos poner el primero\n",
        "    global contador\n",
        "    if pasosA[indice] * pasosB[indice] > 0:   # Existe sinergia, nos podemos ahorrar pasos\n",
        "        pasos_comunes = min(abs(pasosA[indice]), abs(pasosB[indice]))\n",
        "        for i in range(pasos_comunes):\n",
        "            if pasosA[indice] > 0:   # si el signo de ambos es positivo, ya que ambos tienen el mismo signo\n",
        "                rr(a,b); contador += 1\n",
        "            elif pasosA[indice] < 0: # si el signo de ambos es negativo\n",
        "                rrr(a,b); contador += 1\n",
        "        exceso_pasosA = abs(pasosA[indice]) - pasos_comunes\n",
        "        exceso_pasosB = abs(pasosB[indice]) - pasos_comunes\n",
        "        giraA(a, b, indice, ((pasosA[indice] > 0) - (pasosA[indice] < 0)) * exceso_pasosA)    # (a > 0) - (a < 0) da el signo de a\n",
        "        giraB(a, b, indice, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB)   # Python no tiene función sign\n",
        "    else:   # No existe sinergia\n",
        "        giraA(a ,b, indice, pasosA[indice])   # gira A\n",
        "        giraB(a, b, indice, pasosB[indice])   # gira B"
      ],
      "metadata": {
        "id": "SdM6g1pX70kj"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def situarMax_en_B():\n",
        "    indice = b.index(max(b))\n",
        "    if indice < len(a)/2:\n",
        "        pasos = indice\n",
        "    else:\n",
        "        pasos = -(len(b)- indice)\n",
        "    giraB(a, b, indice, pasos)\n",
        "\n",
        "def subirTodo_a_A():\n",
        "    global contador\n",
        "    for _ in range(len(b)):\n",
        "        pa(a,b); contador += 1"
      ],
      "metadata": {
        "id": "rvfYGQeBuU_d"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "if __name__ == \"__main__\":\n",
        "    caso = 0\n",
        "    for prueba in range(100):\n",
        "        n = 500   # número de elementos de la pila\n",
        "        limite =5500\n",
        "        a = generaPilaA(n)\n",
        "        b = []\n",
        "        a_original = a[:]\n",
        "        n = len(a)\n",
        "        lis = [a[0], a[1]]\n",
        "        contador = 0\n",
        "        rotateLIS(lis)\n",
        "        while len(a) > 0:\n",
        "            index_minimosPasos = calculaIndexPasosMinimos()\n",
        "            giraPilas(a,b,index_minimosPasos)\n",
        "            pb(a,b); contador += 1 # lo pasa de A a B haciendo pb\n",
        "        situarMax_en_B()\n",
        "        subirTodo_a_A()\n",
        "        if sorted(a_original) != a: print(\"ERROR: la pila A no ha quedado ordenada.\")\n",
        "        contador_sin = contador\n",
        "        if contador >= limite:\n",
        "            #print(a_original)\n",
        "            #print(f\"contador: {contador} sin LIS\")\n",
        "            ##### Usando la LIS  #####    \n",
        "            a = a_original\n",
        "            b = []\n",
        "            a_original = a[:]\n",
        "            n = len(a)\n",
        "            lis = algoritmo_LIS(a)\n",
        "            contador = 0\n",
        "            rotateLIS(lis)\n",
        "            while len(a) > 0:\n",
        "                index_minimosPasos = calculaIndexPasosMinimos()\n",
        "                giraPilas(a,b,index_minimosPasos)\n",
        "                pb(a,b); contador += 1 # lo pasa de A a B haciendo pb\n",
        "            situarMax_en_B()\n",
        "            subirTodo_a_A()\n",
        "            if sorted(a_original) != a: print(\"ERROR: la pila A no ha quedado ordenada usando la LIS.\")\n",
        "            contador_con = contador\n",
        "            if min(contador_sin, contador_con) >= limite:\n",
        "                caso += 1\n",
        "                print(f\"{caso} / {prueba}\")\n",
        "                if contador_sin <= contador_con:\n",
        "                    print(f\"contador: {contador_sin} sin LIS\")\n",
        "                else:\n",
        "                    print(f\"contador: {contador_con} con LIS\")"
      ],
      "metadata": {
        "id": "cLOrT2wnKgKt",
        "outputId": "f332c33d-6cd4-4c53-e150-cf8b0b1c5535",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 / 0\n",
            "contador: 5546 sin LIS\n",
            "2 / 1\n",
            "contador: 5574 sin LIS\n",
            "3 / 2\n",
            "contador: 5572 sin LIS\n",
            "4 / 5\n",
            "contador: 5560 sin LIS\n",
            "5 / 6\n",
            "contador: 5546 sin LIS\n",
            "6 / 10\n",
            "contador: 5530 con LIS\n",
            "7 / 26\n",
            "contador: 5577 sin LIS\n",
            "8 / 34\n",
            "contador: 5616 con LIS\n",
            "9 / 48\n",
            "contador: 5533 con LIS\n",
            "10 / 54\n",
            "contador: 5558 sin LIS\n",
            "11 / 60\n",
            "contador: 5543 sin LIS\n",
            "12 / 74\n",
            "contador: 5630 sin LIS\n",
            "13 / 76\n",
            "contador: 5507 sin LIS\n",
            "14 / 92\n",
            "contador: 5586 con LIS\n"
          ]
        }
      ]
    }
  ]
}