Overview
push_swap is an algorithmic challenge: sort a stack of integers using only two stacks and a restricted set of operations (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr) in as few moves as possible.
What I Built
- An efficient sorting algorithm optimized for different input sizes
- Cost analysis system to determine the cheapest move at each step
- Index-based sorting to normalize input values
- A parser that validates input and handles edge cases (duplicates, overflow, non-numeric)
Key Concepts
- Algorithm complexity analysis and optimization under constraints
- Stack data structures and their operations
- Decision-making under limited operations (like a constrained Turing machine)
- Benchmarking: measuring number of operations across thousands of random inputs
- Edge cases: already sorted, reverse sorted, single element, maximum int values