Summary:
This project will make you sort data on a stack, with a limited set of instructions, using
the lowest possible number of actions. To succeed you’ll have to manipulate various
types of algorithms and choose the one (of many) most appropriate solution for an
optimized data sorting.
Project description:
The Push_swap project is a very simple and highly effective algorithm project: data will
need to be sorted. You have at your disposal a set of int values, 2 stacks and a set of
instructions to manipulate both stacks.
The goal of the project is to write two programs in C
• The first, named checker which takes integer arguments and reads instructions on
the standard output. Once read, checker executes them and displays OK if integers
are sorted. Otherwise, it will display KO.
• The second one called push_swap which calculates and displays on the standard
output the smallest progam using Push_swap instruction language that sorts integer arguments received.
The game is composed of 2 stacks named a and b.
To start with:
◦ a contains a random number of either positive or negative numbers without any duplicates.
◦ b is empty
The goal is to sort in ascending order numbers into stack a.
To do this you have the following operations at your disposal:
sa : swap a - swap the first 2 elements at the top of stack a. Do nothing if there
is only one or no elements).
sb : swap b - swap the first 2 elements at the top of stack b. Do nothing if there
is only one or no elements).
ss : sa and sb at the same time.
pa : push a - take the first element at the top of b and put it at the top of a. Do
nothing if b is empty.
pb : push b - take the first element at the top of a and put it at the top of b. Do
nothing if a is empty.
ra : rotate a - shift up all elements of stack a by 1. The first element becomes
the last one.
rb : rotate b - shift up all elements of stack b by 1. The first element becomes
the last one.
rr : ra and rb at the same time.
rra : reverse rotate a - shift down all elements of stack a by 1. The last element
becomes the first one.
rrb : reverse rotate b - shift down all elements of stack b by 1. The last element
becomes the first one.
rrr : rra and rrb at the same time.
• checker will get as an argument the stack a formatted as a list of integers.
The first argument should be at the top of the stack. If no argument is given checker stops and
displays nothing.
• checker will then wait and read instructions on the standard input, each instruction
will be followed by ’\n’. Once all the instructions have been read, checker will
execute them on the stack received as an argument.
• If after executing those instructions, stack a is actually sorted and b is empty, then
checker must display OK followed by a \n on the standard output. In every
other case, checker must display KO followed by a \n on the standard output.
• push_swap will receive as an argument the stack a formatted as a list of integers. The first argument should be at the top
of the stack.
• The program must display the smallest list of instructions possible to sort the stack
a, the smallest number being at the top.
• Instructions must be separaed by a \n and nothing else.
• The goal is to sort the stack with the minimum possible number of operations.
make then use as follow
$>ARG="4 67 3 87 23"; ./push_swap $ARG
pb
ra
pb
rr
pa
pa
$>ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker $ARG
OK
$>