{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOsfFmq0cm4o4Tb1ZMtUsIB",
      "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/pilas20.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": "WAFm1lcJXV0B"
      },
      "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",
        "    n = 100   # número de elementos de la pila\n",
        "    a = generaPilaA(n)\n",
        "    print('a:', a)\n",
        "    b = []\n",
        "    a_original = a[:]\n",
        "    n = len(a)\n",
        "    lis = algoritmo_LIS(a)\n",
        "    print(\"LIS:\", lis)\n",
        "    contador = 0\n",
        "    rotateLIS(lis)\n",
        "    print(\"a:\", a)\n",
        "    print(\"b:\", b)\n",
        "    print(\"contador:\", contador)\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",
        "    print(\"a:\", a)\n",
        "    print(\"b:\", b)\n",
        "    print(f\"La pila A {'SI' if sorted(a_original)==a else 'No' } está ordenada.\")\n",
        "    print(f\"contador: {contador} con LIS\")\n",
        "\n",
        "    ### sin LIS, con los dos primeros números de la pila A ###\n",
        "    a = a_original\n",
        "    b = []\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",
        "    print(f\"contador: {contador} sin LIS\")"
      ],
      "metadata": {
        "id": "cLOrT2wnKgKt",
        "outputId": "b3153858-ae6f-4e05-843c-e7a5b91667b0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "a: [6, 41, 36, 59, 2, 24, 33, 83, 57, 77, 78, 81, 65, 56, 88, 70, 53, 89, 17, 93, 96, 30, 61, 94, 55, 23, 26, 29, 18, 54, 32, 66, 62, 80, 39, 73, 98, 48, 21, 12, 11, 25, 14, 95, 3, 28, 16, 22, 37, 27, 91, 1, 42, 85, 4, 69, 47, 9, 75, 100, 63, 20, 10, 38, 60, 51, 31, 90, 50, 99, 52, 34, 84, 8, 58, 87, 64, 46, 67, 19, 82, 40, 13, 92, 45, 43, 86, 74, 49, 44, 68, 71, 97, 35, 72, 15, 5, 79, 76, 7]\n",
            "LIS: [6, 17, 23, 26, 29, 32, 39, 42, 47, 51, 52, 58, 64, 67, 68, 71, 72, 79]\n",
            "a: [76, 7, 41, 36, 59, 2, 24, 33, 83, 57, 77, 78, 81, 65, 56, 88, 70, 53, 89, 93, 96, 30, 61, 94, 55, 18, 54, 66, 62, 80, 73, 98, 48, 21, 12, 11, 25, 14, 95, 3, 28, 16, 22, 37, 27, 91, 1, 85, 4, 69, 9, 75, 100, 63, 20, 10, 38, 60, 31, 90, 50, 99, 34, 84, 8, 87, 46, 19, 82, 40, 13, 92, 45, 43, 86, 74, 49, 44, 97, 35, 15, 5]\n",
            "b: [79, 72, 71, 68, 67, 64, 58, 52, 51, 47, 42, 39, 32, 29, 26, 23, 17, 6]\n",
            "contador: 98\n",
            "a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]\n",
            "b: []\n",
            "La pila A SI está ordenada.\n",
            "contador: 587 con LIS\n",
            "contador: 560 sin LIS\n"
          ]
        }
      ]
    }
  ]
}