42 (VI): push_swap, ordenar con una mano atada

El siguiente proyecto después de pipex prometía ser corto: el enunciado de push_swap cabía en un párrafo. Tienes una pila de números desordenados, una segunda pila vacía y un juego muy limitado de movimientos: intercambiar los dos elementos de arriba, rotar la pila, pasar el elemento superior de una pila a la otra. El trabajo es ordenarlo todo imprimiendo la lista de instrucciones. El detalle que lo cambiaba todo: las instrucciones se cuentan, y si te pasas del límite, el proyecto no se valida.

El problema de verdad

Las cifras del subject son una escala de sufrimiento: tres números en tres movimientos como máximo, cinco en doce, cien en setecientos y quinientos en cinco mil quinientos. Empecé dibujando pilas en papel y moviendo fichas a mano, y vi rápido que ningún algoritmo clásico encaja directamente: hay que ordenar con las herramientas que te dan, no con las que querrías tener. Ordenar es la parte fácil; ordenar con presupuesto, no.

Cómo lo atacué

Partí el problema en dos mundos. Con cinco elementos o menos, casos cerrados: con tres números hay un puñado de configuraciones posibles y cada una tiene una secuencia corta que la ordena; me hice la tabla a mano y la codifiqué tal cual. Con cuatro y cinco, bajaba los elementos más pequeños a la pila auxiliar, ordenaba los tres restantes y deshacía el camino.

Con cien y quinientos números fui con el algoritmo de chunks. Primero asigno a cada valor un índice relativo, su posición dentro de la lista ordenada, para que las comparaciones no dependan de los valores reales. Después empujo los números hacia la pila auxiliar por grupos, dejándolos colocados para recuperarlos del más grande al más pequeño. La constante que más retoqué fue el tamaño del grupo: quince para cien elementos y treinta y dos para quinientos, valores afinados con scripts que generaban listas aleatorias y contaban instrucciones en cada ejecución. También ahorré movimientos baratos: cuando hay que rotar para subir un elemento, elegir siempre la dirección corta.

En el repositorio, 42_push_swap, hay dos archivos de audio grabados con el algoritmo explicado en voz alta. Era mi forma de preparar la defensa: si soy capaz de explicar por qué quince y no veinte, es que lo he entendido de verdad.

Qué me llevo

Push_swap me enseñó que una heurística bien afinada gana a un algoritmo teóricamente mejor pero mal ajustado, y que medir vale tanto como programar. También que el parsing no es un trámite: validar duplicados y desbordamientos de entero antes de empezar me ahorró más de un error en evaluación. Y que la frustración sana paga: cada tanda de pruebas que bajaba la media de movimientos se notaba al instante.