Hive (42 School Network)

Push Swap

Overview

The goal is to sort a stack of integers using:

• Two stacks: stack A (initial stack) and stack B (temporary stack).
• A limited set of operations to manipulate the stacks.
• The output should be a set of operations that sort a stack in a limited number of moves (less than 5500 for a set of 500 integers for the highest grade).

Solution

The solution uses a circular buffer for the stack implementation, improving performance. Sorting is achieved with a customised quick sort algorithm, designed to generate the required stack operations efficiently and minimise the number of moves. The approach was inspired by results shared by 42 School Seoul peers and this article by Ulysse Gerkens.

Performance

Worst-case scenario for a set of integers:

• 500 integers — 4300 moves.
• 100 integers — 640 moves.

Allowed operations

1. Push: move the top element between stacks.

• pa: Push the top element of stack B to stack A.
• pb: Push the top element of stack A to stack B.

2. Swap: swap the first two elements of a stack.

• sa: Swap the first two elements of stack A.
• sb: Swap the first two elements of stack B.
• ss: Swap the first two elements of both stacks simultaneously.

3. Rotate: rotate the stack upwards (the first element becomes the last).

• ra: Rotate stack A.
• rb: Rotate stack B.
• rr: Rotate both stacks simultaneously.

4. Reverse Rotate: rotate the stack downwards (the last element becomes the first).

• rra: Reverse rotate stack A.
• rrb: Reverse rotate stack B.
• rrr: Reverse rotate both stacks simultaneously.

Where to start

1. Clone the repository:

   git clone https://github.com/ipersids/hive-core-push-swap.git push-swap
   cd push-swap

2. Compile using Makefile:

• make — compile the push-swap program.
• make bonus — compile the checker program.
• make clean — clean up object files.
• make fclean — clean up executables and object files.

3. Run the program:

   ARG="-9 2 -5 1 8 3 -7 4 6 0"; ./push_swap $ARG

   or ./push_swap 4 5 7 1 9 3, or ./push_swap 4 5 "7 1" 9 3 - both formats are supported.
4. Check the operation count:

   ARG="-9 2 -5 1 8 3 -7 4 6 0"; ./push_swap $ARG | wc -l

5. Validate the output using the custome checker program:

   ARG="-9 2 -5 1 8 3 -7 4 6 0"; ./push_swap $ARG | ./checker $ARG

   Output:
   • OK if the numbers are correctly sorted by the given operations
   • KO if the numbers aren't sorted correctly
   • Error\n if there's an error :)

---

Made by Julia Persidskaia.
LinkedIn