{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyN246JHQFsAbvE+w2Z0BhLl", "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 comenzando con un trio ordenado\n", "Los tres primeros números de A se pasan a B y se ordenan para que queden en B de forma decreciente circularmente.\n", "\n", "Objetivo conseguir que el número de pasos quede por debajo del límite.\n", "* para n=100 el límite es <700\n", "* para n=500 el límite es <5500" ], "metadata": { "id": "ZUAyju3U8GhF" } }, { "cell_type": "markdown", "source": [ "# Comenzando con tres ordenados en B\n", "\n", "\n", "1. Generamos aleatoriamente o nos dan la pila A. \n", "2. La pila B inicialmente está vacía.\n", "3. Pasamos tres elementos de A a B con el mínimo número de pasos posible y de forma que en B queden ordenados decrecientemente\n", "\n", "- Ejemplo 1: Pila B: 78 34 12\n", "- Ejemplo 2: Pila B: 3 2 1\n", "- Ejemplo 3: Pila B: 1 3 2       Esto también estaría ordenado de forma decreciente\n", "- Ejemplo 4: Pila B: 2 1 3       ya que se puede ver de forma circular\n", "\n", "Objetivos correctos en B\n", "* 3 2 1\n", "* 1 3 2\n", "* 2 1 3\n", "\n", "   casos A             Resultado \n", "- 1 2 3 ... pb pb pb         3 2 1 \n", "- 1 3 2 ... pb sa pb pb   3 2 1 \n", "- 2 1 3 ... sa pb pb pb   3 2 1 \n", "- 2 3 1 ... pb pb pb         1 3 2 \n", "- 3 1 2 ... pb pb pb         2 1 3 \n", "- 3 2 1 ... pb pb pb sb   2 1 3" ], "metadata": { "id": "Z_B2p5UqA5_8" } }, { "cell_type": "code", "source": [ "# FUNCIONES\n", "def sa(a, b):\n", " global contador\n", " if len(a) > 1: a[0],a[1] = a[1],a[0]; contador += 1\n", " return a, b\n", "def sb(a, b):\n", " global contador\n", " if len(b) > 1: b[0],b[1] = b[1],b[0]; contador += 1\n", " return a, b\n", "def ss(a, b):\n", " global contador\n", " if len(a) > 1 or len(b) > 1:\n", " contador += 1\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\n", "def pa(a, b):\n", " global contador\n", " if len(b) > 0:\n", " a.insert(0, b[0])\n", " b.pop(0); contador += 1\n", " return a, b\n", "def pb(a, b):\n", " global contador\n", " if len(a) > 0:\n", " b.insert(0, a[0])\n", " a.pop(0); contador += 1\n", " return a, b\n", "def ra(a, b):\n", " global contador\n", " if len(a) > 1: a.append(a.pop(0)); contador += 1\n", " return a, b\n", "def rb(a, b):\n", " global contador\n", " if len(b) > 1: b.append(b.pop(0)); contador += 1\n", " return a, b\n", "def rr(a, b):\n", " global contador\n", " if len(a) > 1 or len(b) > 1:\n", " contador += 1\n", " if len(a) > 1: a.append(a.pop(0))\n", " if len(b) > 1: b.append(b.pop(0))\n", " return a, b\n", "def rra(a, b):\n", " global contador\n", " if len(a) > 1: a.insert(0, a.pop()); contador += 1\n", " return a, b\n", "def rrb(a, b):\n", " global contador\n", " if len(b) > 1: b.insert(0, b.pop()); contador += 1\n", " return a, b\n", "def rrr(a, b):\n", " global contador\n", " if len(a) > 1 or len(b) > 1:\n", " contador += 1\n", " if len(a) > 1: a.insert(0, a.pop())\n", " if len(b) > 1: b.insert(0, b.pop())\n", " return a, b" ], "metadata": { "id": "NnOxqobnuRzl" }, "execution_count": 1, "outputs": [] }, { "cell_type": "code", "source": [ "def bajar_tres(a,b): # se usa en la función tres_decrecientes para el caso habitual en el que hacemos pb pb pb\n", " pb(a,b)\n", " pb(a,b)\n", " pb(a,b)\n", " \n", "def tres_decrecientes(a,b): # bajamos los tres primeros números de A a B, y los hacemos decrecientes de forma circular\n", " if a[0] < a[1] < a[2]: # caso: 1 2 3\n", " bajar_tres(a,b)\n", " elif a[0] < a[1] > a[2] and a[0] < a[2]: # caso: 1 3 2\n", " pb(a,b)\n", " sa(a,b)\n", " pb(a,b)\n", " pb(a,b)\n", " elif a[0] > a[1] < a[2] and a[0] < a[2]: # caso: 2 1 3\n", " sa(a,b)\n", " bajar_tres(a,b)\n", " elif a[0] < a[1] > a[2] and a[0] > a[2]: # caso: 2 3 1\n", " bajar_tres(a,b)\n", " elif a[0] > a[1] < a[2] and a[0] > a[2]: # caso: 3 1 2\n", " bajar_tres(a,b)\n", " elif a[0] > a[1] > a[2]: # caso: 3 2 1\n", " bajar_tres(a,b)\n", " sb(a,b)" ], "metadata": { "id": "H1XwAwswq0QY" }, "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", " #print(\"pasosA: \", pasosA)\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", " #print(\"pasosB: \", pasosB)\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", " #print(\"total: \", total)\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": "ZMoJSTqfu_WV" }, "execution_count": 3, "outputs": [] }, { "cell_type": "code", "source": [ "def giraA(a, b, indice, pasos):\n", " for i in range(abs(pasos)):\n", " if pasos > 0:\n", " ra(a,b)\n", " elif pasos < 0:\n", " rra(a,b)\n", "\n", "def giraB(a, b, indice, pasos):\n", " for i in range(abs(pasos)):\n", " if pasos > 0:\n", " rb(a,b)\n", " elif pasos < 0:\n", " rrb(a,b)\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", " 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)\n", " elif pasosA[indice] < 0: # si el signo de ambos es negativo\n", " rrr(a,b)\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": "ycWnQdAMvD4h" }, "execution_count": 4, "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", " for _ in range(len(b)):\n", " pa(a,b)" ], "metadata": { "id": "RpFPTsfHA6ge" }, "execution_count": 5, "outputs": [] }, { "cell_type": "code", "source": [ "if __name__ == \"__main__\":\n", " from random import seed, shuffle\n", " seed()\n", " for intento in range(10000):\n", " contador = 0\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", " tres_decrecientes(a,b)\n", " while len(a) > 0:\n", " index_minimosPasos = calculaIndexPasosMinimos()\n", " giraPilas(a,b,index_minimosPasos)\n", " pb(a,b) # lo pasa de A a B haciendo pb\n", " situarMax_en_B()\n", " subirTodo_a_A()\n", " if a != sorted(a_original):\n", " print(f\"ERROR: no se ha ordenado\\n {a_original}\\n{a}\")\n", " if contador >= 5500:\n", " print(f\"{intento+1} contador: \\t{contador} {a_original}\")" ], "metadata": { "id": "vn2wuHAXBtih" }, "execution_count": null, "outputs": [] } ] }