"Algorithm that sorts data using two stacks."

Index

Index
Folder Structure
About
The rules
Resources Given
Bonus Part
What do I need to know?
How can I organize the "first real hard project"?
Running Tests
Leaks test
Graphical User Interface - GUI (Useful for testing purposes)
How to use?
My Push_Swap
Testing
Tester
Evaluation
Correction sheet
Treasure hunt
Support Me
Skills developed
Sources
Author

Folder Structure

.
├── push_swap
│   ├── include
│   │   └── push_swap.h
│   ├── lib
│   ├── srcs
│   │   ├── ft_error_handling.c
│   │   ├── ft_free.c
│   │   ├── ft_id_stack_a.c
│   │   ├── ft_id_stack_b.c
│   │   ├── ft_init_op.c
│   │   ├── ft_input_preparation.c
│   │   ├── ft_op_p.c
│   │   ├── ft_op_r.c
│   │   ├── ft_op_rr.c
│   │   ├── ft_op_s.c
│   │   ├── ft_stack_calc_a.c
│   │   ├── ft_stack_calc_b.c
│   │   ├── ft_stack_calc.c
│   │   ├── ft_stack_half_opa.c
│   │   ├── ft_stack_half_opb.c
│   │   ├── ft_stack_op.c
│   │   ├── ft_stack_searching_op.c
│   │   ├── ft_stack_sorting.c
│   │   ├── ft_utils.c
│   │   └── main.c
│   ├── srcs_b
│   │   ├── ft_checker.c
│   │   └── main.c
│   └── Makefile
├── resources_given
│   ├── checker_linux
│   └── checker_Mac
└── README.md

About

The purpose of this project is to write a program named push_swap that takes as an argument the stack a formatted as a list of integers. The purpose of this project is to sort the list of integers stored in stack A using a limited set of instructions and another stack called B. To score the maximum you need to use the lowest possible number of actions, is setted a maximum number of moves. There are many ways to manipulate this stack implementing different algorithms.

Some rules to keep in mind:

• Your project must be written in C (in accordance with the Norm).

• Your functions should not quit unexpectedly (segmentation fault, bus error, double free, etc) apart from undefined behaviors.

• All heap allocated memory space must be properly freed when necessary.

• You must submit a Makefile which will compile your source files to the required output with the flags -Wall, -Wextra and -Werror, use cc, and your Makefile must not relink. And the Makefile must at least contain the rules $(NAME), all, clean, fclean and re (bonus if you want maximum score).

• If your project allows you to use your libft, you must copy its sources and its associated Makefile in a libft folder with its associated Makefile. Your project’s Makefile must compile the library by using its Makefile, then compile the project.

•Global variables are forbidden.

Program name:

push_swap Which has as arguments a stack A (a list of integers).

Files to turn in:

Makefile, *.h, *.c

External functs. allowed:

Libft authorized, and:

1. read, write, malloc, free, exit

2. ft_printf and any equivalent YOU coded

Goal:

The goal is to sort the stack with the lowest possible number of operations. During the evaluation process, the number of instructions found by your program will be compared against a limit:

required: sort   3 numbers with <=     3 operations
required: sort   5 numbers with <=    12 operations
scored:   sort 100 numbers with <=   700 operations   max score
                                     900 operations
                                    1100 operations
                                    1300 operations
                                    1500 operations   min score
scored:   sort 500 numbers with <=  5500 operations   max score
                                    7000 operations
                                    8500 operations
                                   10000 operations
                                   11500 operations   min score

Requirements:

• The first argument should be at the top of the stack.

• Instructions must be separated by a \n and nothing else.

• The program must display the smallest list of instructions possible to sort the stack a, the smallest number being at the top.

• If no parameters are specified, the program must not display anything and give the prompt back.

• In case of error, it must display "Error" followed by a ’\n’ on the standard error. Errors include for example: some arguments aren’t integers, some arguments are bigger than an integer (MAXINT) and/or there are duplicates.

Examples:

$>./push_swap 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa
$>./push_swap 0 one 2 3
Error
$>ARG="4 67 3 87 23"; ./push_swap $ARG | wc -l
6
$>ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker_OS $ARG
OK
$>

If the program checker_OS displays "KO", it means that your push_swap came up with a list of instructions that doesn’t sort the numbers.

Where the command ARG="4 67 3 87 23" initializes a variable and assigns the string "4 67 3 87 23" to it. The string contains a sequence of space-separated numbers: 4, 67, 3, 87, and 23. These numbers represent the unsorted list of integers that will be passed to the push_swap program. The ARG variable acts as a placeholder for the unsorted list of integers. It's used later in the command to pass the list to the push_swap program.

The push_swap program takes the unsorted list of integers as input and processes it using its sorting algorithm. It generates a list of instructions that describe the steps required to sort the list.

So, a pipe | is used to connect the output of the push_swap program to the input of the wc -l command. Each instruction generated from push_swap program represents a separate line. The word count command with the flag -l counts the number of lines in its input, so it will count the number of instructions generated by the push_swap program.

The rules

You have 2 stacks named a and b. The stack a contains a random amount of negative and/or positive numbers which cannot be duplicated, instead the stack 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:

operation name	description
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

Example

Resources Given

Are provided two programms named checker: one developed for linux and one for mac. You can download it from here. To use correctly the executables, you need to modify the permissions of these. Run chmod 777 "name of the executable".

Bonus Part

The request of the bonus is regarding the checker, in particular is requested to create your own checker. This checker takes as an argument the stack A formatted as a list of integers. The first argument should be at the top of the stack (be careful about the order). If no argument is given, it stops and displays nothing. It will then wait and read instructions on the standard input, each instruction will be followed by ’\n’. Once all the instructions have been read, the program has to execute them on the stack received as an argument. What does it do?

•If after executing those instructions, the stack a is actually sorted and the stack b is empty, then the program must display "OK" followed by a ’\n’ on the standard output.

•In every other case, it must display "KO" followed by a ’\n’ on the standard output.

•In case of error, you must display "Error" followed by a ’\n’ on the standard error. Errors include for example: some arguments are not integers, some arguments are bigger than an integer, there are duplicates, an instruction doesn’t exist and/or is incorrectly formatted.

$>./checker 3 2 1 0
rra
pb
sa
rra
pa
OK
$>./checker 3 2 1 0
sa
rra
pb
KO
$>./checker 3 2 one 0
Error
$>./checker "" 1
Error
$>

You DO NOT have to reproduce the exact same behavior as the provided binary. It is mandatory to manage errors but it is up to you to decide how you want to parse the arguments.

Program name:

checker Which has as arguments a stack A (a list of integers).

Files to turn in:

*.h, *.c

External functs. allowed:

Libft authorized, and:

1. read, write, malloc, free, exit

2. ft_printf and any equivalent YOU coded

What do I need to know?

What is an algorithm?

An algorithm is just a term for a set of instructions of what a program should do, and how it should do it.

What does analysis of algorithms mean in Computer science?

The analysis of algorithms is the process of finding the computational complexity of algorithms, which means the amount of time, storage, or other resources needed to execute them. It is an important part of computer science, as it allows us to compare different algorithms and choose the most efficient one for a given problem.

There are two main ways to analyze algorithms:

• Asymptotic analysis: considers the behavior of an algorithm as the size of the input grows to infinity. It is the most common type of algorithm analysis, and it uses asymptotic notations such as big O, big Omega, and big Theta to express the algorithm's time and space complexity. In the binary search, it is said to run in a number of steps proportional to the logarithm of the size n of the sorted list being searched, or in O(log n), colloquially "in logarithmic time".

• Empirical analysis: measures the actual performance of an algorithm on a specific set of inputs. It is less common than asymptotic analysis, but it can be useful for comparing different implementations of the same algorithm or for optimizing an algorithm for a specific problem.

Here are some of the key factors that are considered when analyzing algorithms:

• Time complexity: The amount of time required by an algorithm to execute as a function of the size of the input.

• Space complexity/memory usage: The amount of memory required by an algorithm to execute as a function of the size of the input. The space complexity could be classified in-place algorithms or out-of-place algorithms. An in-place algorithm is one that operates directly on the inputted data. The danger with this is that the data is getting completely transformed in the process of transforming it, which means that the original dataset is effectively being destroyed! However, it is more space-efficient, because the algorithm only needs a tiny bit of extra space in memory — usually a constant amount of space, or O(1) — which can be helpful if you don’t have enough memory to spare. out-of-place algorithms don’t operate directly on the original dataset; instead, the make a new copy, and perform the sorting on the copied data. This can be safer, but the drawback is that the algorithm’s memory usage grows with input size.

• Accuracy: How accurately the algorithm solves the problem.

• Robustness: How well the algorithm handles unexpected inputs or errors.

• Parallelizability: Whether the algorithm can be parallelized to improve its performance.

The program's runtime is directly proportional to its input size. Doubling the input size doubles the runtime; quadrupling the input size quadruples the run-time; and so forth. The time complexity of the linear search algorithm is O(n), where n is the number of elements in the array.

What is a stack?

A stack is an abstract data type that serves as a collection of elements, with two main operations:

1. Push, which adds an element to the collection.
2. Pop, which removes the most recently added element that was not yet removed.

Additionally, a peek operation can, without modifying the stack, return the value of the last element added. Calling this structure a stack is by analogy to a set of physical items stacked one atop another, such as a stack of plates.

The order in which an element added to or removed from a stack is described as last in, first out, referred to by the acronym LIFO.

Considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. This data structure makes it possible to implement a stack as a singly linked list and as a pointer to the top element. A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept another element, the stack is in a state of stack overflow. A stack can be easily implemented either through an array or a linked list, as stacks are just special cases of lists. For example, A stack is needed to implement depth-first search (is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph).

What is a binary search?

Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Binary search runs in logarithmic time in the worst case, making O(log(n)) comparisons, where n is the number of elements in the array. Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

Which are the differences between stable and unstable algorithm?

A stable sorting algorithm is one that preserves the relative order of equal elements in the input sequence. An unstable sorting algorithm is one that does not preserve the relative order of equal elements. In other words, if you have a list of elements with duplicate values, and you sort the list using a stable sorting algorithm, the duplicate values will remain in the same order relative to each other after the sort. However, if you sort the list using an unstable sorting algorithm, the duplicate values may be rearranged in any order. Stability is important in some cases, such as when sorting a list of key-value pairs, where the key is the sort key and the value is some other data associated with the key. For example, you might have a list of employee names and their salaries, where the name is the sort key and the salary is the value. If you sort this list using a stable sorting algorithm, the employees with the same name will remain in the same order after the sort. This can be useful for maintaining the original order of the data.

Examples of stable sorting algorithms:

•Merge sort

•Insertion sort

•Bubble sort

•Binary tree sort

Examples of unstable sorting algorithms:

•Quicksort

•Heap sort

•Selection sort

What are sorting algorithms?

Basically, sorting algorithms are ways to organize an array of items from smallest to largest. To analize the algorithm complexity and efficiency is needed to understand the Big O notation (O(n)). The most common algorithms for sorting are:

How can I organize the "first real hard project"?

Firstly, you need to understand what this program should do. You need to study all the theory that you need and understand which algorithm you want to implement in your code. Secondly, you need to do a pattern to understand how to divide this project into many smaller ones. So, don't panic. I will show you my organization pattern:

Running Tests

My project is based on brute force sorting algorithm. I have done mandatory and bonus part, I have implemented for all functions a comment that explains what does it do. I have tested my project with several tests and the result is that my Push_Swap is under the maximum number of moves allowed. To generate a set of random numbers I have used this python script:

import random
numbers = random.sample(range(-2147483648, 2147483647), 500)
random.shuffle(numbers)
print(' '.join(map(str, numbers)))

used on this website.

Leaks test

To check is the memory is freed correctly, so to check if there are some leaks, run this tests:

Ubuntu: valgrind --leak-check=full ./your_program

MacOS: leaks -atExit -- ./your_program

Graphical User Interface - GUI (Usefull for testing purposes)

I visualized my stacks with this push-swap-gui 1.1 wrote in Python. This is a python3 package added to PyPI. To run this, you need to run in the terminal the command: push_swap_gui in your push_swap folder. Before to use you need to install if you don't have it. pip3 install push_swap_gui.

If you noticed an error like this:

    ERROR: Command errored out with exit status 1:
     command: /usr/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-amjzzxzo/pyttk/setup.py'"'"'; __file__='"'"'/tmp/pip-install-amjzzxzo/pyttk/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' egg_info --egg-base /tmp/pip-install-amjzzxzo/pyttk/pip-egg-info
         cwd: /tmp/pip-install-amjzzxzo/pyttk/
    Complete output (7 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-install-amjzzxzo/pyttk/setup.py", line 2, in <module>
        import ttk
      File "/tmp/pip-install-amjzzxzo/pyttk/ttk.py", line 36, in <module>
        import tkinter as Tkinter
    ModuleNotFoundError: No module named 'tkinter'
    ----------------------------------------
ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

You need to install Tkinter, which is the standard GUI library for Python. Python when combined with Tkinter provides a fast and easy way to create GUI applications. Tkinter provides a powerful object-oriented interface to the Tk GUI toolkit. To install this on Linux, run the command: sudo apt-get install python3-tk.

How to use?

You need to select a range of numbers (remember that 0 counts as 1) and generate stack A. You need to uncheck the square flag and select the path of your push_swap. After that, you must calculate the number of moves and click on the play button to view the visualizer's moves (remember that you can control the speed).

My Push_Swap

Testing

1. Run norminette -R CheckForbiddenSourceHeader into the push_swap dir to get a norm check of your work.
2. Tests about the command requested with make.
3. Leaks tests.
4. Errors management.
5. Push_swap tests.
6. Checker tests.

Tester

Push_Swap Tester of Aldisti.

Evaluation

Test the notable cases: 0, 1, 3, 5, 50, 100, 250 and 500 and iterate many times to understand the efficiency.

Correction sheet

Treasure hunt

The subject give the string

Lc6cDCFXDWTiFzZ2H9skYkiJ/DpQtnM/uZ0```

The file.bfe is a Base64 encoded string. Base64 encoding is a way of converting binary data into a string of ASCII characters. This is often used to encode images, videos, and other types of files so that they can be transmitted over the internet or stored in text files.

To decode the Base64, I used the following Python code:

```py
import base64

encoded_string = "VABB7yO9xm7xWXROeASsmsgnY0o0sDMJev7zFHhwQS8mvM8V5xQQpLc6cDCFXDWTiFzZ2H9skYkiJ/DpQtnM/uZ0"

decoded_bytes = base64.b64decode(encoded_string)

with open("decoded_file.txt", "wb") as f:
    f.write(decoded_bytes)

This code decoded the Base 64 string and wrote the decoded bytes to a file named decoded_file.txt.

The decoded file contains a single line of text, which is shown below:

This is a test file.

Support Me

Remember to ⭐ the repository. If you want to support me:

Skills developed

Sources

• Analysis of algorithms

• Stack

• Binary search algorithm

• Push_swap

• Linked Lists

• sorting

• Sorting algorithms 1

• Sorting algorithms 2

• pivot_quick_sort

• Push Swap — A journey to find most efficient sorting algorithm

• Fastest Push_Swap Algorithm

Author

Email Github Linkedin Slack

---