push_swap
Tri d’une pile avec un jeu d’instructions restreint, optimisé pour réduire au maximum le nombre d’opérations.
Trier une pile d’entiers avec un jeu d’instructions restreint, en un minimum de coups.
Les règles
Deux piles — A contient les nombres, B démarre vide — et onze opérations : sa sb ss échangent les deux premiers éléments, pa pb poussent d’une pile à l’autre, ra rb rr font tourner, rra rrb rrr font tourner dans l’autre sens. Le programme affiche la plus courte liste d’opérations qu’il trouve laissant A triée.
L’approche
Les petites piles reçoivent une séquence écrite en dur. Au-delà, les nombres sont poussés dans B par paquets puis ramenés un par un, chaque insertion choisissant la combinaison de rotations la moins coûteuse sur les deux piles — c’est là que le nombre de coups se gagne ou se perd.
Le bonus
checker lit une liste d’opérations sur l’entrée standard et dit si elle trie effectivement les nombres passés en arguments.
Ce que j’en ai tiré
Que le coût d’un algorithme se mesure, et que gratter des coups sur une solution qui marche est un travail différent de celui qui consiste à la faire marcher.