{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyNrIuW64bFicfaaBGaUq0B4", "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": [ "# Deep Moder Times iniciando el algoritmo con los dos primeros números de A \n", "* En esta versión no se utilizan vairas parejas haciendo varios intentos. \n", "* Únicamente se inicia el algoritmo pasando los dos primeros elementos de la pila A a la pila B.\n", "* La pareja con la que se inicia el algoritmo es ```a[0],a[1]```" ], "metadata": { "id": "v3orFRqdIE-h" } }, { "cell_type": "code", "execution_count": null, "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": [ "# 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", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " return pasosA\n", "\n", "def necesariosB(a, b): # código nuevo: buscando el hueco\n", " arr_target = [None] * len(a)\n", " for i in range(len(a)):\n", " if a[i] < min(b) or a[i] > max(b):\n", " target = max(b); arr_target[i] = target\n", " else:\n", " for j in range(len(b)-1):\n", " if a[i] < b[j] and a[i] > b[j+1]:\n", " target = b[j+1]; arr_target[i] = target\n", " elif a[i] < b[-1] and a[i] > b[0]:\n", " target = b[0]; arr_target[i] = target\n", " # en este momento ya tenermos el target completamente calculado\n", " # ahora toca calcular pasosB\n", " if b.index(target) < len(b)/2:\n", " pasosB.append(b.index(target))\n", " else:\n", " pasosB.append(-(len(b)- b.index(target)))\n", " return pasosB, arr_target\n", "\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", " return total\n", "\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", " pasosA = necesariosA(a, b)\n", " pasosoB, arr_target = necesariosB(a, b)\n", " total = totaliza(a, b)\n", " print(\"target:\", arr_target)\n", " print(\"pasosA:\", pasosA)\n", " print(\"pasosB:\", pasosB)\n", " print(\"total: \", total)\n", " print()\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": null, "outputs": [] }, { "cell_type": "code", "source": [ "def giraA(a, b, 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, 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. Estoy en el caso de que pasosA y pasosB tienen el mimso signo\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, ((pasosA[indice] > 0) - (pasosA[indice] < 0)) * exceso_pasosA, result) # (a > 0) - (a < 0) da el signo de a\n", " giraB(a, b, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB, result) # Python no tiene función sign\n", " else: # No existe sinergia\n", " giraA(a ,b, pasosA[indice], result) # gira A\n", " giraB(a, b, pasosB[indice], result) # gira B" ], "metadata": { "id": "jp2JPuQKQ6IL" }, "execution_count": null, "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, 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": null, "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", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " if maximo in aux: # si el máximo está en aux hacer rra y aux.pop\n", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " rra(a, b, result)\n", " aux.pop()\n", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " while len(b) > 0: # ahora aux está vacío y solo queda hacer pa todo el rato\n", " pa(a, b, result)\n", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()" ], "metadata": { "id": "dLMI_rruYP0f" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "if __name__ == \"__main__\":\n", " from random import seed, shuffle\n", " seed()\n", " n = 20 # número de elementos de la pila\n", " for muestra in range(1):\n", " a = list(range(1, n+1)); shuffle(a) # generación aleatoria de la pila A\n", " a = [2, 3, 6, 1, 4, 5]\n", " a = [2, 4, 6, 1, 3, 5]\n", " a = [3, 4, 5, 1, 2, 6]\n", " a = [2, 3, 4, 1, 5, 6]\n", " a = [3, 2, 6, 1, 4, 5]\n", " a = [4, 3, 2, 1, 6, 5]\n", " a = [4, 3, 2, 5, 6, 1]\n", " b = []\n", " a_original = a[:]\n", " print(\"a_original:\", a_original, \"\\n\")\n", " a_srt = ' '.join(map(str, a_original))\n", " result = [] # recoje los pasos dados. Ejemplo: result = ['pb','ra','sa','rra']\n", " pb(a, b, result); pb(a, b, result) # pasa de A a B la pareja de elementos de A elegidos a[0], a[1]\n", " while len(a) > 3:\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", " print(\"Ha finalizado el bucle while\\n\")\n", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " situarMax_en_B(a, b, result) # situa el valor máximo de B en la primera posición de B\n", " print(\"Situamos el máximo de B el primero\\n\")\n", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " print(\"Odenamos A de forma creciente\\n\")\n", " crecientesA(a, b, result) # situa los tres últimos valores de A en forma creciente estricta: Ejemplo: 17, 45, 82\n", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " print(\"Ejecutamos el cremallera\\n\")\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", " print(\"pila A:\", a)\n", " print(\"pila B:\", b)\n", " print()\n", " for i in range(len(result)-2):\n", " if result[i]=='pb' and result[i+1]=='pa':\n", " result.pop(i+1)\n", " result.pop(i)\n", " for i in range(len(result)-2):\n", " if (result[i]=='rb' and result[i+1]=='ra') or (result[i]=='ra' and result[i+1]=='rb'):\n", " result.pop(i+1)\n", " result[i] = 'rr'\n", " #print(len(result))\n", " print(result)\n", " largo = len(result)\n", " #if largo <= 4900 or largo >= 5600:\n", " print(\"a_original:\", a_srt)\n", " print(largo, a == sorted(a_original))" ], "metadata": { "id": "riSVzyEEuJgF", "colab": { "base_uri": "https://localhost:8080/" }, "outputId": "90c801cf-4818-4bd5-c640-d50d99c8d104" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "a_original: [4, 3, 2, 5, 6, 1] \n", "\n", "pila A: [2, 5, 6, 1]\n", "pila B: [3, 4]\n", "target: [4, 4, 4, 4]\n", "pasosA: [0, 1, -2, -1]\n", "pasosB: [-1, -1, -1, -1]\n", "total: [1, 2, 2, 1]\n", "\n", "Ha finalizado el bucle while\n", "\n", "pila A: [5, 6, 1]\n", "pila B: [2, 4, 3]\n", "\n", "Situamos el máximo de B el primero\n", "\n", "pila A: [5, 6, 1]\n", "pila B: [4, 3, 2]\n", "\n", "Odenamos A de forma creciente\n", "\n", "pila A: [1, 5, 6]\n", "pila B: [4, 3, 2]\n", "\n", "Ejecutamos el cremallera\n", "\n", "pila A: [1, 5, 6]\n", "pila B: [4, 3, 2]\n", "\n", "pila A: [6, 1, 5]\n", "pila B: [4, 3, 2]\n", "\n", "pila A: [6, 1, 5]\n", "pila B: [4, 3, 2]\n", "\n", "pila A: [5, 6, 1]\n", "pila B: [4, 3, 2]\n", "\n", "pila A: [4, 5, 6, 1]\n", "pila B: [3, 2]\n", "\n", "pila A: [3, 4, 5, 6, 1]\n", "pila B: [2]\n", "\n", "pila A: [2, 3, 4, 5, 6, 1]\n", "pila B: []\n", "\n", "pila A: [2, 3, 4, 5, 6, 1]\n", "pila B: []\n", "\n", "pila A: [1, 2, 3, 4, 5, 6]\n", "pila B: []\n", "\n", "pila A: [1, 2, 3, 4, 5, 6]\n", "pila B: []\n", "\n", "['pb', 'pb', 'rrb', 'pb', 'rb', 'rra', 'rra', 'rra', 'pa', 'pa', 'pa', 'rra']\n", "a_original: 4 3 2 5 6 1\n", "12 True\n" ] } ] } ] }