42 (VI): push_swap, sorting with one hand tied

The next project after pipex promised to be short: the push_swap brief fit in a paragraph. You have a stack of unsorted numbers — imagine a stack of plates, where you can only touch the one on top —, a second empty stack, and a very limited set of moves: swap the top two elements, rotate the stack, move the top element from one stack to the other. The job is to sort everything by printing the list of instructions. The detail that changed everything: instructions are counted, and if you exceed the limit, the project doesn't validate.

The real problem

The subject's numbers are a suffering scale: three numbers in three moves maximum, five in twelve, a hundred in seven hundred, and five hundred in five thousand five hundred. I started by drawing stacks on paper and sliding tokens by hand, and I quickly realized that no classical algorithm (the textbook sorting recipe) fits directly: you have to sort with the tools they give you, not the ones you'd like to have. Sorting is the easy part; sorting on a budget is not.

How I tackled it

I split the problem into two worlds. With five elements or fewer, closed cases: with three numbers there are a handful of possible configurations and each one has a short sequence that sorts it; I built the table by hand and coded it as is. With four and five, I pushed the smallest elements to the auxiliary stack, sorted the remaining three, and unwound the path.

With a hundred and five hundred numbers I went with the chunks algorithm (sorting by groups). First I assign each value a relative index, its position within the sorted list, so the comparisons don't depend on the actual values. Then I push the numbers toward the auxiliary stack in groups, leaving them positioned so they can be recovered from largest to smallest. The constant I tweaked the most was the group size: fifteen for a hundred elements and thirty-two for five hundred, values fine-tuned with scripts that generated random lists and counted instructions on each run. I also saved moves by cheap means: when you have to bring an element up by rotating, always choose the short direction.

In the repository, 42_push_swap, there are two audio files recorded with the algorithm explained out loud. It was my way of preparing the defense: if I'm able to explain why fifteen and not twenty, it's because I truly understand it.

What I take away

Push_swap taught me that a heuristic (a well-tuned thumb rule) beats an algorithm that's theoretically better but poorly calibrated, and that measuring is as valuable as programming. Also, that parsing (reading the input and validating it) isn't a formality: validating duplicates and integer overflows before starting saved me more than one evaluation error. And that healthy frustration pays off: every test batch that lowered the average number of moves was felt instantly.

The next one in the series was no longer about stacks but about the first game: 42 (VII): so_long, the first game.