push_swap

Sorting a stack of integers with a restricted instruction set, in as few moves as possible.

The rules

Two stacks — A holds the numbers, B starts empty — and eleven operations: sa sb ss swap the top two elements, pa pb push from one stack to the other, ra rb rr rotate, rra rrb rrr rotate the other way. The program prints the shortest list of operations it can find that leaves A sorted.

The approach

Small stacks get a hard-coded sequence. Beyond that, the numbers are pushed to B in chunks and brought back one at a time, each insertion picking the cheapest combination of rotations on both stacks — which is where the move count is won or lost.

The bonus

checker reads a list of operations on standard input and says whether it really sorts the numbers given as arguments.

What it taught me

That the cost of an algorithm is measurable, and that shaving moves off a working solution is a different job from making it work.