Mètodes
42 (VI): push_swap, ordenar amb una mà lligada
Ordenar una pila amb un joc limitat de moviments i el mínim d'instruccions: algorismes, heurístiques i frustració sana.
El següent projecte després de pipex prometia ser curt: l’enunciat de push_swap cabia en un paràgraf. Tens una pila de números desordenats, una segona pila buida i un joc molt limitat de moviments: intercanviar els dos elements de dalt, rotar la pila, passar l’element superior d’una pila a l’altra. La feina és ordenar-ho tot imprimint la llista d’instruccions. El detall que ho canviava tot: les instruccions es compten, i si te’n surts del límit, el projecte no es valida.
El problema de debò
Les xifres del subject són una escala de patiment: tres números en tres moviments com a màxim, cinc en dotze, cent en set-cents i cinc-cents en cinc mil cinc-cents. Vaig començar dibuixant piles en paper i movent fitxes a mà, i ràpid vaig veure que cap algorisme clàssic encaixa directament: has d’ordenar amb les eines que et donen, no amb les que voldries tenir. Ordenar és la part fàcil; ordenar amb pressupost, no.
Com ho vaig atacar
Vaig partir el problema en dos mons. Amb cinc elements o menys, casos tancats: amb tres números hi ha un grapat de configuracions possibles i cadascuna té una seqüència curta que l’ordena; em vaig fer la taula a mà i la vaig codificar tal qual. Amb quatre i cinc, baixava els elements més petits a la pila auxiliar, ordenava els tres restants i desfeia el camí.
Amb cent i cinc-cents números vaig anar amb l’algorisme de chunks. Primer assigno a cada valor un índex relatiu, la seva posició dins de la llista ordenada, perquè les comparacions no depenguin dels valors reals. Després empenyo els números cap a la pila auxiliar per grups, deixant-los col·locats per recuperar-los del més gran al més petit. La constant que més vaig retocar va ser la mida del grup: quinze per a cent elements i trenta-dos per a cinc-cents, valors afinats amb scripts que generaven llistes aleatòries i comptaven instruccions a cada execució. També vaig estalviar moviments barats: quan cal portar un element amunt rotant, triar sempre la direcció curta.
Al repositori, 42_push_swap, hi ha dos fitxers d’àudio gravats amb l’algorisme explicat en veu alta. Era la meva manera de preparar la defensa: si sóc capaç d’explicar per què quinze i no vint, és que l’he entès de debò.
Què m’enduc
Push_swap em va ensenyar que una heurística ben afinada guanya un algorisme teòricament millor però mal ajustat, i que mesurar val tant com programar. També que el parsing no és un tràmit: validar duplicats i desbordaments d’enter abans de començar em va estalviar més d’un error en avaluació. I que la frustració sana paga: cada tanda de proves que baixava la mitjana de moviments es notava a l’instant.