{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyM4bgXKB8mrzd/ahp8GoyP9", "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": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Algoritmo Deep Moder Times\n", "Si realizamos el proceso tres veces, es posible que interese tomar las siguientes parejas del array m2, comenzando por index cero.\n", "* pareja 9: [1,3]\n", "* pareja 17: [2,-3]\n", "* pareja 18: [-2,3]" ], "metadata": { "id": "YG97doX9tqWp" } }, { "cell_type": "code", "execution_count": 1, "metadata": { "id": "7vqmBYUatK3m" }, "outputs": [], "source": [ "# FUNCIONES\n", "def sa(a, b, result): # result es un array que va acumulando los pasos dados. Ejemplo: result = ['pb','ra','sa','rra']\n", " if len(a) > 1: a[0],a[1] = a[1],a[0]; result.append('sa')\n", " return a, b, result\n", "def sb(a, b, result):\n", " if len(b) > 1: b[0],b[1] = b[1],b[0]; result.append('sb')\n", " return a, b, result\n", "def ss(a, b, result): # ss no llama a sa y sb ya que en result quedarían anotadas las tres funciones: ss, sa y sb\n", " if len(a) > 1 or len(b) > 1:\n", " result.append('ss')\n", " if len(a) > 1: a[0],a[1] = a[1],a[0]\n", " if len(b) > 1: b[0],b[1] = b[1],b[0]\n", " return a, b, result\n", "def pa(a, b, result):\n", " if len(b) > 0:\n", " a.insert(0, b[0])\n", " b.pop(0); result.append('pa')\n", " return a, b, result\n", "def pb(a, b, result):\n", " if len(a) > 0:\n", " b.insert(0, a[0])\n", " a.pop(0); result.append('pb')\n", " return a, b, result\n", "def ra(a, b, result):\n", " if len(a) > 1: a.append(a.pop(0)); result.append('ra')\n", " return a, b, result\n", "def rb(a, b, result):\n", " if len(b) > 1: b.append(b.pop(0)); result.append('rb')\n", " return a, b, result\n", "def rr(a, b, result):\n", " if len(a) > 1 or len(b) > 1:\n", " result.append('rr')\n", " if len(a) > 1: a.append(a.pop(0))\n", " if len(b) > 1: b.append(b.pop(0))\n", " return a, b, result\n", "def rra(a, b, result):\n", " if len(a) > 1: a.insert(0, a.pop()); result.append('rra')\n", " return a, b, result\n", "def rrb(a, b, result):\n", " if len(b) > 1: b.insert(0, b.pop()); result.append('rrb')\n", " return a, b, result\n", "def rrr(a, b, result):\n", " if len(a) > 1 or len(b) > 1:\n", " result.append('rrr')\n", " if len(a) > 1: a.insert(0, a.pop())\n", " if len(b) > 1: b.insert(0, b.pop())\n", " return a, b, result" ] }, { "cell_type": "code", "source": [ "def establece_lis(arr): # esta función solo se debería invocar una vez. Proporciona una matriz con listas de posibles lis\n", " m2 = [[0,1],[0,-1],[0,2],[0,-2],[0,3],[0,-3],[1,-1],[1,2],[1,-2],[1,3],[1,-3],[-1,2],[-1,-2],[-1,3],[-1,-3],[2,-2],[2,3],[2,-3],[-2,3],[-2,-3],[3,-3]]\n", " posibles_lis = []\n", " for pareja in m2: # m2 tiene 21 parejas\n", " x,y = pareja[0], pareja[1]\n", " lis = [arr[x], arr[y]]\n", " posibles_lis.append(lis)\n", " return posibles_lis\n", "\n", "# Llevamos de la pila A hacia la pila B los elementos de la LIS\n", "def rotateLIS(a, b, result, lis):\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, result)\n", " else:\n", " for i in range(len(a)- a.index(vlis)):\n", " rra(a, b, result)\n", " pb(a, b, result)" ], "metadata": { "id": "a9oEsS-oHdBA" }, "execution_count": 2, "outputs": [] }, { "cell_type": "code", "source": [ "# PASOS NECESARIOS PARA COLOCAR CADA ELEMENTO DE A EN SU SITIO EN B total = pasosA + pasosB (esta suma es solo una idea, se ha de sumar de una forma peculiar)\n", "\n", "def necesariosA(a, b): # array pasosA calcula los pasos necesarios para colocar cada elemento de A como el primero de su pila\n", " for v in a:\n", " if a.index(v) < len(a)/2:\n", " pasosA.append(a.index(v))\n", " else:\n", " pasosA.append(-(len(a)- a.index(v)))\n", "\n", "def necesariosB(a, b): # array pasosB calcula los pasos de B necesarios para colocar cada elemento de A dentro de su sitio en B\n", " for i in range(len(a)): # objetivo_primero es el número que se ha de poner en la primera posición de la pila B\n", " if a[i] < min(b): # si el elemento de A considerado es menor que el mayor de B entonces\n", " objetivo_primero = max(b) # el objetivo_primero será el mayor de B\n", " else: # objetivo_primero en este caso será el maximo de los inferiores en B al valor iésimo de A\n", " objetivo_primero = min(b) #se inicializa en el valor mínimo de la pila B\n", " for j in range(len(b)):\n", " if b[j] < a[i] and b[j] > objetivo_primero:\n", " objetivo_primero = b[j]\n", " # el objetivo_primero se ha de situar el primero de la pila B \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, uno positivo y otro negativo\n", " total.append(abs(pasosA[i]) + abs(pasosB[i])) # no hay sinergia\n", " else: # si son de igual signo o alguno cero\n", " total.append(max(abs(pasosA[i]), abs(pasosB[i]))) # si son de igual signo hay sinergia\n", "\n", "def calculaIndexPasosMinimos():\n", " global pasosA, pasosB, 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": "Vy8JRVgnNutZ" }, "execution_count": 3, "outputs": [] }, { "cell_type": "code", "source": [ "def giraA(a, b, indice, steps, result):\n", " for i in range(abs(steps)):\n", " if steps > 0:\n", " ra(a, b, result)\n", " elif steps < 0:\n", " rra(a, b, result)\n", "\n", "def giraB(a, b, indice, steps, result):\n", " for i in range(abs(steps)):\n", " if steps > 0:\n", " rb(a, b, result)\n", " elif steps < 0:\n", " rrb(a, b, result)\n", "\n", "# girando pilas A y B\n", "def giraPilas(a, b, indice, result): # indice es el index del valor en la pila A que deseamos poner el primero\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, result)\n", " elif pasosA[indice] < 0: # si el signo de ambos es negativo\n", " rrr(a, b, result)\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, result) # (a > 0) - (a < 0) da el signo de a\n", " giraB(a, b, indice, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB, result) # Python no tiene función sign\n", " else: # No existe sinergia\n", " giraA(a ,b, indice, pasosA[indice], result) # gira A\n", " giraB(a, b, indice, pasosB[indice], result) # gira B" ], "metadata": { "id": "jp2JPuQKQ6IL" }, "execution_count": 4, "outputs": [] }, { "cell_type": "code", "source": [ "def situarMax_en_B(a, b, result): # situa el valor máximo de B en la primera posición de B\n", " indice = b.index(max(b))\n", " if indice < len(a)/2:\n", " steps = indice\n", " else:\n", " steps = -(len(b)- indice)\n", " giraB(a, b, indice, steps, result)\n", "\n", "def crecientesA(a, b, result): # situa los tres valores de A en forma creciente estricta: Ejemplo: 17, 45, 82\n", " if a[0] < a[1] > a[2] and a[0] < a[2]: # caso: 1 3 2\n", " ra(a, b, result)\n", " sa(a, b, result)\n", " rra(a, b, result)\n", " elif a[0] > a[1] < a[2] and a[0] < a[2]: # caso: 2 1 3\n", " sa(a, b, result)\n", " elif a[0] < a[1] > a[2] and a[0] > a[2]: # caso: 2 3 1\n", " rra(a, b, result)\n", " elif a[0] > a[1] < a[2] and a[0] > a[2]: # caso: 3 1 2\n", " ra(a, b, result)\n", " elif a[0] > a[1] > a[2]: # caso: 3 2 1\n", " sa(a, b, result)\n", " rra(a, b, result)\n", " return # caso: 1 2 3 en este caso no se hace nada pq ya están ordenados" ], "metadata": { "id": "3xu35ZrfTm_4" }, "execution_count": 5, "outputs": [] }, { "cell_type": "code", "source": [ "# Después de ordenar los tres elementos de A en orden creciente estricto con la función crecientesA\n", "\n", "def cremallera(a, b, result): # función que va pasando los números de B a A en forma de cremallera, intercalándolos con los que ya hay en A\n", " aux = [a[-3], a[-2], a[-1]] # creamos un array aux con los tres últimos valores de A\n", " while len(aux) > 0: # Mientras aux tenga elementos\n", " maximo = max(b + aux) # calcula el maximo entre b y aux\n", " if maximo in b: # si el maximo está en B hacer pa\n", " pa(a, b, result)\n", " if maximo in aux: # si el máximo está en aux hacer rra y aux.pop\n", " rra(a, b, result)\n", " aux.pop()\n", " while len(b) > 0: # ahora aux está vacío y solo queda hacer pa todo el rato\n", " pa(a, b, result)" ], "metadata": { "id": "dLMI_rruYP0f" }, "execution_count": 6, "outputs": [] }, { "cell_type": "code", "source": [ "if __name__ == \"__main__\":\n", " from random import seed, shuffle\n", " seed()\n", " n = 500 # número de elementos de la pila\n", " a = list(range(1, n+1)); shuffle(a) # generación aleatoria de la pila A\n", " b = []\n", " a_original = a[:]\n", " posibles_lis = establece_lis(a) # llama a la función que proporciona una matriz con las posibles lis de dos números de la pila A\n", " mejor_contador = 32767 # calcularemos los mínimos pasos necesarios de los intentos. Se inicializa en infinito o casi\n", " mejor_result = [] # contendrá el array con el result de la mejor solución que correspone a la de minimos pasos requeridos\n", " for intento in [9,17,18]: # vamos a probar cada una de las 3 parejas elegidas. pareja 9: [1,3], pareja 17: [2,-3], pareja 18: [-2,3] Cada prueba será un intento\n", " a = a_original[:]\n", " b = []\n", " result = [] # recoje los pasos dados en este intento. Ejemplo: result = ['pb','ra','sa','rra']\n", " lis = posibles_lis[intento] # establece lis por ejemplo: lis = [a[0], a[1]]\n", " rotateLIS(a, b, result, lis) # pasa de A a B la pareja de elementos de A elegidos en la lis\n", " while len(a) > 3:\n", " #print(f\"\\n{a}\\n{b}\")\n", " index_minimosPasos = calculaIndexPasosMinimos()\n", " giraPilas(a, b, index_minimosPasos, result)\n", " pb(a, b, result) # lo pasa de A a B haciendo pb\n", " situarMax_en_B(a, b, result) # situa el valor máximo de B en la primera posición de B\n", " crecientesA(a, b, result) # situa los tres valores de A en forma creciente estricta: Ejemplo: 17, 45, 82\n", " cremallera(a, b, result) # función que va pasando los números de B a A en forma de cremallera, intercalándolos con los que ya hay en A\n", " nresult = len(result)\n", " #print(nresult, \" \", end=\"\")\n", " if nresult < mejor_contador:\n", " mejor_contador = nresult\n", " mejor_result = result[:]\n", " print(\"\\nmejor_contador:\", mejor_contador)\n", " #print(\"mejor_result:\\n\", mejor_result)" ], "metadata": { "id": "riSVzyEEuJgF", "colab": { "base_uri": "https://localhost:8080/" }, "outputId": "4c05bf18-8c4c-4dad-a502-a1e44f68d29a" }, "execution_count": 7, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "\n", "mejor_contador: 5217\n" ] } ] } ] }