A year ago, when I was in the 42 piscine, I had to use the terminal for the first time to push code to GitHub. I can vividly remember how nervous and confused I was, playing around with the commands and finding even the most basic tasks difficult. Fast forward to today, and I am proud of the progress I’ve made, culminating in building a shell that operates similarly to the one I once found daunting. This project, a collaborative effort of a two-person team, marks a significant milestone in my journey.

In the world of Unix-like systems, the shell acts as the primary interface between the user and the system’s deeper functionalities.

This blog post examines the development of our “MiniShell,” a project intended to mimic the key aspects of sophisticated shells like Bash, but on a more rudimentary level. Our MiniShell is also an educational aid, providing for a hands-on experience with command parsing, process management, and the nuance of environment manipulation required to accommodate more sophisticated systems.

Working on this project solidified my C programming and widened my understanding of system internals such as file descriptors, process lifecycle, and signal handling. As one of the most challenging assignments at 42 school — and casually known as “miniHell” by our team — this challenge was as rewarding as it was difficult. In this post, I will describe the obstacles we encountered, the methods we employed to navigate through them, and the learnings we accumulated in the process.

Project Overview

what is Shell?

Shell is called a command interface or command interpreter. It provides a system-level interface program for users to send requests to the Linux kernel for running programs.

The objective of MiniShell project was to create a simplified yet functional version of a Unix-like shell using C programming language. This involved implementing several core features that are typical of more sophisticated shells like Bash.

Key Functionalities

1. Command Parsing and Execution:

• Prompt Display: The shell continuously displays a prompt, waiting for user input.
• Input Tokenization: User inputs are broken down into tokens to interpret commands and their arguments.
• Command Execution: Based on the parsed input, the shell executes the corresponding commands either by invoking built-in functions or external programs.

2. Handling Redirections and Piping:

• Redirection: Handles input (<), output (>), and append (>>) redirections, allowing the user to direct the flow of data into and out of commands and files.
• Pipes: By using pipes (|), the output of one command can serve as the input to another, facilitating a chain of command executions that share data seamlessly.

3. Built-in Commands:

• We included several built-in commands like echo, cd, pwd, env, export, and exit, which are handled internally without spawning new processes. This not only improves the performance but also simplifies the management of environment variables and the current working directory.

4. Environment and Signal Handling:

• Environment Management: The shell supports setting and retrieving environment variables.
• Signal Handling: We implemented handlers for CTRL-C, CTRL-D, and CTRL-\\ to manage shell termination and interruption, mimicking the behaviour seen in Bash.

5. Error Handling and Process Management:

• Robust Error Handling: The shell gracefully handles errors like incorrect commands or permissions issues without crashing.
• Process Management: Each command runs in a separate process, where the parent manages the lifecycle and ensures that all resources are cleaned up properly.

Development Approach

The project was split into two main parts: parsing and execution, handled by my teammate and me, respectively. We used a modular design to keep components like parsing, executing, and signal handling distinct and manageable. Regular code reviews and paired programming sessions helped us maintain code quality and consistency across the project.

Basic lifetime of a shell

Let’s look at a shell from the top down. A shell does three main things in its lifetime.

• Initialize: In this step, a typical shell would read and execute its configuration files. These change aspects of the shell’s behavior.
• Interpret: Next, the shell reads commands from stdin (which could be interactive, or a file) and executes them.
• Terminate: After its commands are executed, the shell executes any shutdown commands, frees up any memory, and terminates.

int main(int argc, char **argv)
{
 // Load config files, if any.
// Run command loop.
 lsh_loop();
// Perform any shutdown/cleanup.
return EXIT_SUCCESS;
}

Program Flow of MiniShell

Initialization

The journey of our MiniShell starts with the main function, where the shell environment is prepared. This includes:

• Argument Verification: Using check_args(), the shell ensures it is started with the correct parameters.
• Environment Setup: The init_shell() function sets up the necessary shell environment, initializing variables and configuring the shell's state.

void init_shell(t_shell *mini, char **envv)
{
 mini->running_status = 1;
 mini->input = NULL;
 mini->commands = NULL;
 mini->last_exit_status = 0;
 mini->expand_heredoc = 0;
 set_envv(mini, envv);
}

Input Processing and Signal Handling

Once initialized, MiniShell enters its main operational loop, continuously processing user input:

• Signal Configuration: setup_sig_handling() configures how the shell responds to external signals like SIGINT (Ctrl+C) and SIGQUIT, ensuring that the shell remains responsive and user-friendly.

void setup_sig_handling(t_shell *mini)
{
 struct sigaction sa_int;
 struct sigaction sa_quit;

 if (pipe(mini->signal_pipe) == -1)
 {
  perror("pipe");
  exit (1);
 }
 sa_int.sa_handler = handle_sigint;
 sigemptyset(&sa_int.sa_mask);
 sa_int.sa_flags = SA_RESTART;
 sa_quit.sa_handler = SIG_IGN;
 sigemptyset(&sa_quit.sa_mask);
 sa_quit.sa_flags = SA_RESTART;
 if (sigaction(SIGINT, &sa_int, NULL) == -1 || 
  sigaction(SIGQUIT, &sa_quit, NULL) == -1)
 {
  perror("sigaction");
  exit(1);
 }
}

• Environment Variables: set_env() is responsible for populating the shell’s environment, crucial for the proper execution of commands.

Command Loop

The core of MiniShell’s functionality lies in its ability to process and execute commands:

• Reading Input: take_input() leverages the readline library to capture user input, benefiting from built-in line editing and history features.
• Tokenization: The input string is broken down into manageable pieces or tokens by tokenize(), distinguishing between commands, options, and arguments.

Execution

After parsing the input:

• Token Expansion: expand_tokens() handles the expansion of environment variables and other necessary token transformations.
• Command Grouping: group_tokens_to_cmd() organizes tokens into commands and manages setups for piping and redirection.
• Command Execution: Finally, execute_minishell() takes the structured commands and either executes built-in functions or external programs.

Clean-up

Post-execution, the shell cleans up to maintain efficiency and prevent memory leaks:

• Freeing Resources: Functions like free_tokens() and free_commands() are called to release any allocated memory.
• Continuation Check: The loop continues based on the status flags set during execution, ensuring the shell only exits when prompted by the user.

Technical Challenges and Solutions

Challenge: Signal Handling

Problem: Ensuring that the shell correctly handles Unix signals like SIGINT without terminating unexpectedly or freezing.

Solution: We implemented custom signal handlers that intercept these signals and appropriately dictate the shell’s response, allowing for a seamless user experience similar to more advanced shells.

Challenge: Command Tokenization and Parsing

Problem: Correctly parsing user input into tokens while managing different command types, options, arguments, and handling special characters and quotations.

Solution: We developed a tokenizer that respects quoted strings and correctly identifies and separates commands and their parameters. Implementing specific checks for the context, such as skipping expansion inside single quotes.

Challenge: Memory Management

Problem: Managing memory efficiently in a shell that continuously allocates memory for new commands and their arguments.

Solution: Through meticulous tracking and management, including regular use of gdb, Valgrind and a lot of print statements, we ensured that each allocation was paired with a corresponding deallocation, preventing memory leaks even during complex command executions.

Challenge: Handling Redirections and Pipes

Problem: Implementing a flexible system for input/output redirection and inter-command piping that respects the precedence of redirections over pipes.

Solution: We crafted a system that sets up file descriptors before command execution to manage the flow of data correctly between commands and external files, ensuring that the shell behaves predictably and efficiently.

Let’s consider an example command to check the flow:

cat file.txt | grep 'pattern' > output.txt

1. Input Reception

As with any command, the MiniShell starts by waiting for user input in its main loop. When the user enters cat file.txt | grep 'pattern' > output.txt, the command string is captured using the readline library via the take_input() function.

2. Tokenization

The received input string is passed to the tokenize() function, which processes the string to break it into manageable pieces (tokens):

• The tokenizer identifies cat, file.txt, |, grep, 'pattern', >, and output.txt as individual tokens.

3. Token Expansion

The expand_tokens() function processes each token to handle environment variables or other expansions. In this case, since there are no environment variables or expandable elements in this command, the tokens remain unchanged.

4. Command Grouping

Using group_tokens_to_cmd(), tokens are organized into command structures:

• The tokens are grouped by recognizing the pipe (|) as a command separator. This results in two command groups: one for cat file.txt and another for grep 'pattern'.
• The redirection (> output.txt) is noted in the command structure of the grep command to redirect its output.

5. Execution Preparation

The execute_minishell() function sets up the command execution:

• It validates the tokens using validate_tokens() to ensure there are no misplaced pipes or redirection symbols.

6. Command Execution

The execute() function processes the command groups:

• Piping Setup: The shell sets up a pipe between cat file.txt and grep 'pattern' using the pipe() system call. This links the standard output of cat directly to the standard input of grep.
• Redirection Setup: For grep 'pattern', the output redirection is set up to write to output.txt instead of the terminal.
• Command Execution: Each command group is executed in turn:
• cat file.txt reads the contents of file.txt and writes it to the pipe.
• grep 'pattern' reads from the pipe, filters lines containing 'pattern', and writes the result to output.txt.

7. Clean-up

After executing the commands, resources are cleaned up:

• Freeing Resources: free_tokens() and free_commands() are called to release memory used for tokens and command structures.
• Handling Pipes and Redirection: Any open file descriptors from pipes or redirections are closed to prevent resource leaks.

8. Continuation

The shell checks if it should continue running and returns to the input prompt, waiting for the next command.

Error Handling

Types of errors to look out for

Examples of the types of errors that a simple shell may encounter and how they can be handled

Incorrect command:

If the user enters an incorrect command, the shell should display an error message indicating that the command was not recognized.

Incorrect number of arguments:

If the user enters a valid command but with an incorrect number of arguments, the shell should display an error message indicating the correct usage of the command.

Permission denied:

If the user attempts to execute a command for which they do not have the necessary permissions, the shell should display an error message indicating that permission was denied.

System call error:

If a system call made by the shell fails, the shell should display an error message indicating that the system call failed.

In summary, error handling is an important aspect of building a shell, and it requires careful attention to system calls, library functions, and signals. A shell should check return values, handle signals correctly, and provide meaningful error messages to the user when necessary. It’s important to provide informative error messages to the user in order to aid in debugging and troubleshooting.

Some C functions that can be used for error handling in a shell include:

perror(): This function is used to print an error message to the console. It takes a string argument that is printed before the error message and uses the value of the global errno variable to determine the error message to display.

strerror(): This function takes an error code as an argument and returns a string describing the error. It can be used to provide more detailed error messages to the user.

signal(): This function is used to register a signal handler function for a specific signal. The signal handler function is called when the specified signal is received by the process.

waitpid(): This function is used to wait for a child process to exit. It takes the PID of the child process and a pointer to an integer that will hold the exit status of the child process when it exits. It returns the PID of the exited child process.

Running the program

Check and run the code

git clone
make
./minishell
cat input.txt | grep -i "error" | sort | uniq -c > final.txt

Reflections

When we first started this project, I felt completely lost, unsure of where to begin. The idea of building a shell from scratch seemed overwhelming, but step by step, things started to make sense. Looking at examples and watching videos helped me grasp the fundamentals, and from there, we began with a simple hardcoded implementation before gradually expanding its functionality.

Throughout this journey, I gained a deeper appreciation for system programming, debugging, memory management and team work. Working on MiniShell was both a challenge and a learning experience that strengthened my understanding of Unix-like systems and C programming. I must also express my gratitude to my incredible teammate, Alex!. Her collaboration made this demanding project feel much more manageable and less stressful.

There’s always room for improvement. We still have issues with unclosed file descriptors that need to be fixed, and refining the handling of edge cases could make the shell even more robust.

Despite the hurdles, this project reinforced an essential lesson: the best way to learn is by building.

References and tools

Tester by LucasKuhn

Introduction

The Dining Philosophers Problem, originating from Edsger Dijkstra as a thought experiment in 1965 is one of computer science’s enduring challenges. It is often used to illustrate the challenges of allocating limited resources among multiple processes in a concurrent system. It provides a vivid scenario to explore the fundamentals of process synchronization and concurrency within computer science.

Understanding the Problem

Description: X amount of philosophers sit at a round table with bowl of food. Forks are placed in front of each philosopher. There are as many forks as philosophers. All day the philosophers take turns eating, sleeping, and thinking. A philosopher must have two forks in order to eat, and each fork may only be used by one philosopher at a time. At any time a philosopher can pick up or set down a fork, but cannot start eating until picking up both forks. The philosophers alternatively eat, sleep, or think. While they are eating, they are not thinking nor sleeping, while thinking, they are not eating nor sleeping, and, of course, while sleeping, they are not eating nor thinking.

Challenges Faced: The challenge is to design a system where each philosopher can think, eat and sleep without starvation. The main challenges include deadlock, where philosophers wait on each other indefinitely for forks, and starvation, where a philosopher never gets enough resources to eat. Race conditions can also occur, complicating the synchronization of thread operations.

Technical Setup

Tools and Technologies Used: This solution was implemented in C as part of 42 Projects, using POSIX threads (pthreads) for handling multiple philosophers simultaneously and mutexes for managing access to the forks.

Environment Setup: The solution is developed on a Linux system, utilizing GCC for compilation with flags for thread safety and performance optimization.

Before getting into the implementation details let us look at the basis of programming to understand what a process, thread is.

Process vs Thread

Building a house is a process, but the people doing the work to install the pipes, paint the walls and do the electrical work are all the working threads within the process of building the house.

I like to use threads synonymously with “unit of work” or “thing that executes a specific piece of work / action for the process to complete successfully.

So if I run chrome, and have 10 tabs open, I will have 10 processes running. Within each process are 1 or many units of work (called threads) responsible for memory management, access, logic, etc.

Processes are isolated executable files in memory, while threads are units of execution within those processes sharing memory space.

Summary

🖥️ Program Definition: A program is an executable file containing processor instructions. Recognizing that a program is merely a file until executed helps clarify the transition to processes, emphasizing the importance of execution context.

🚀 Process Creation: When a program is executed, it becomes a process and requires resources managed by the OS.

🔒 Process Isolation: Each process has its own memory address space, preventing corruption by other processes.

🧵 Thread Function: A thread is a unit of execution within a process, with its own stack but sharing memory space with other threads.

⚙️ Context Switching: The OS uses context switching to manage process and thread execution on the CPU, which is resource-intensive.

⏩ Efficiency of Threads: Context switching is faster between threads than processes due to shared memory, reducing overhead.

🔄 Alternative Scheduling: Mechanisms like fibers and coroutines minimize context switching costs by allowing applications to manage scheduling.

🔗 Memory Protection: Process isolation is vital for system stability, particularly in multi-process applications like web browsers, which utilize this to enhance user experience.

🧩 Threads vs. Processes: Understanding that threads share memory space while processes don’t is key for developers in designing efficient applications and managing data.

Common Issues in Thread Programming

When working with threads in C, there are several common issues that programmers may encounter. These include:

• Race Conditions: A race condition occurs when two or more threads can access shared data and they try to change it at the same time. Because the thread scheduling algorithm can swap between threads at any time, you don’t know the order in which the threads will attempt to access the shared data. Therefore, the result of the change in data is dependent on the thread scheduling algorithm, i.e. both threads are “racing” to access/change the data.
• Deadlocks: Improper handling of resource acquisition and release can lead to deadlocks, where threads are stuck indefinitely waiting for each other. Deadlocks happen when we lock the same mutex twice or more or more often due to the order in which the mutexes are locked and unlocked.
• Resource Management: Managing shared resources such as memory or file handles among multiple threads requires careful coordination to avoid conflicts and corruption.
• Synchronization: Coordinating the execution of multiple threads to ensure correct program behaviour often involves the use of synchronization primitives like mutexes, semaphores, and condition variables.
• Performance Overhead: Creating and managing threads can introduce overhead in terms of memory and CPU usage, impacting the overall performance of the application if not managed efficiently.
• Debugging Challenges: Debugging multi-threaded programs can be challenging due to the non-deterministic nature of thread execution and timing-dependent bugs.
• Platform Dependency: Thread behaviour may vary across different operating systems and platforms, requiring platform-specific considerations for thread programming.

Key Implementation Details

1. Thread Management: Each philosopher is represented as a thread. This parallelism simulates the simultaneous actions of thinking, eating, and sleeping.
2. Mutex Usage: Mutex locks are crucial. Each fork has an associated mutex to ensure that no two philosophers can hold the same fork at the same time, thus preventing deadlock.
3. State Management: I maintained the state of each philosopher (eating, thinking, sleeping) using shared variables protected by mutexes, ensuring that changes in state were mutually exclusive among threads.
4. Monitoring and Control: A separate monitoring thread checks continuously to ensure no philosopher is starved and the program can terminate correctly once all philosophers have eaten sufficiently or when one of the philosopher dies.

🔑 Simulating Deadlocks: Introducing delays can help demonstrate deadlocks in a controlled manner, useful for educational purposes and debugging.

🔑 Preventive Measures: Standardizing lock acquisition order across threads can significantly reduce the risk of deadlocks in complex applications.

Core Functions Explained

1. Checking Philosophers’ Status

char	control_simu(t_rcs *data)
{
	int	i;
	i = 0;
	pthread_create(&data->monitor, NULL, monitor_routine, (void *)data);
	while (i < data->num_philo)
	{
		if (pthread_create(&data->philos[i].thread, NULL, philo_routine, 
				(void *)&data->philos[i]) != 0)
		{
			printf("\\033[0;31mFailed to create philosopher thread\\033[0m \\n");
			return (0);
		}
		i++;
	}
	join_threads(data);
	return (1);
}

It begins by creating a monitoring thread that oversees the entire simulation, ensuring conditions like starvation or task completion are appropriately handled. Then, individual threads for each philosopher are spawned, each executing a routine that simulates the philosopher’s activities such as eating, thinking, and sleeping. If any thread fails to initiate, an error is reported, and the function exits with failure. After initializing all philosopher threads and the monitor thread, join_threads(data) is called to ensure that the main thread (typically the one running main()) waits for all other threads to complete before proceeding. This is essential to prevent the program from exiting prematurely and to ensure all resources are properly released.

2. Action: Eating

void	eating(t_philo *philo)
{
	if (philo->id % 2)
	{
		pthread_mutex_lock(philo->right_fork);
		log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
		pthread_mutex_lock(philo->left_fork);
		log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
	}
	else
	{
		pthread_mutex_lock(philo->left_fork);
		log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
		pthread_mutex_lock(philo->right_fork);
		log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
	}
	ft_start_eating(philo);
	log_action("is eating", philo->id, philo->s_data, "\\033[0;34m");
	precise_sleep(philo->eat_time);
	pthread_mutex_unlock(philo->left_fork);
	pthread_mutex_unlock(philo->right_fork);
	pthread_mutex_lock(&philo->s_data->meal_lock);
	philo->eating = 0;
	philo->meals_eaten++;
	pthread_mutex_unlock(&philo->s_data->meal_lock);
}

Philosophers with odd IDs first pick up the right fork and then the left, while those with even IDs do the opposite, preventing a circular wait condition that could lead to deadlock. Once both forks are secured, the philosopher is logged as eating, and the action is timed to simulate the duration of the meal. After eating, the forks are released in the opposite order they were picked up to further minimize potential deadlocks. Finally, the meal’s completion is recorded under the protection of a meal_lock mutex to safely update the shared state variables eating and meals_eaten, ensuring that these critical sections are not accessed concurrently by other threads, thus maintaining data integrity throughout the simulation.

3. Logging Actions

void	log_action(char *action, int i, t_rcs *data, char *color)
{
	unsigned long	timestamp;	
        pthread_mutex_lock(&data->logging);
	timestamp = get_time_ms() - data->philos[i -1].start_time;
	pthread_mutex_lock(&data->death_lock);
	if (data->dead != 1)
	{
		printf("%lu %s%d %s\\033[0m\\n", timestamp, color, i, action);
	}
	pthread_mutex_unlock(&data->death_lock);
	pthread_mutex_unlock(&data->logging);
}

The function first locks the logging mutex to prevent other threads from writing simultaneously, ensuring that log entries are not interleaved and remain readable. It then calculates the time elapsed since the start of the simulation for that particular philosopher. Another lock, death_lock, is used to check if the simulation is still active before logging the action. This dual-lock mechanism ensures that actions are only logged when the philosopher is active and the simulation has not been terminated.

4. Precise Timing

This function marks the start time and continuously checks against the current time until the desired duration has passed, pausing execution in very short intervals (0.5 milliseconds) to prevent the thread from monopolizing CPU resources.

void	precise_sleep(unsigned long duration)
{
		unsigned long	start;
		start = get_time_ms();
		while (get_time_ms() - start < duration)
		{
		usleep(500);
		}
}

Challenges and Solutions

Challenge 1: Circular Wait Condition

• Problem Faced: The circular wait condition arose when each philosopher attempted to pick up the left and right forks in no particular order. This issue could lead to a deadlock, where all philosophers hold one fork and wait indefinitely for the other, preventing any philosopher from eating.
• Solution Implemented: To prevent this deadlock scenario, a strict order was enforced in which philosophers pick up their forks. Philosophers with odd IDs first pick up the right fork and then the left, while those with even IDs do the opposite. This strategy breaks the cycle of circular wait and effectively prevents deadlock.

Challenge 2: Favouritism in Fork Acquisition

• Problem Faced: Some philosophers were favoured in terms of accessing forks due to their position at the table or the sequence of actions, leading to unfair resource allocation where some philosophers would always pick up the fork first, they would finish eating and then pick up the fork to eat again immediately.
• Solution Implemented: The solution involved implementing an algorithm that considers fairness; each philosopher must put down their forks and wait a random minimal duration before attempting to pick them up again if they were not successful in their first attempt. This randomized delay reduces the chance of favoritism and ensures that all philosophers get an equal opportunity to eat.

Challenge 3: Delayed Death Logging

• Problem Faced: The simulation had an issue where a philosopher’s death would only be logged after they had completed their full sleep cycle or finished eating, which could misleadingly suggest that the philosopher was alive for longer than actually was the case.
• Solution Implemented: To address this, the monitoring system was refined to check the status of philosophers more frequently and independently of their eating or sleeping cycles. The implementation of a dedicated monitoring thread allowed for immediate recognition and logging of a philosopher’s death, thus ensuring that death events are recorded and handled promptly and accurately.

Running the program

Check and run the code

git clone
make
./philo 5 610 200 200 3
or 
valgrind --tool=helgrind ./philo 5 610 200 200

*All time in milliseconds

./philo [number_of_philosophers] [time_to_die] [time_to_eat] [time_to_sleep] [number_of_times_each_philosopher_must_eat(optional)]

**Helgrind is a Valgrind tool for detecting synchronisation errors in C, C++ and Fortran programs that use the POSIX pthreads threading primitives.

Mood Check

• What is a thread even?😲
• Deadlocks! 😣
• Finally they follow a routine 😴🍽️🤔

Reflections

The real-world applications of such a solution are vast, particularly in operating systems and database transaction systems, where resource allocation must be managed meticulously to prevent deadlocks and ensure fairness.

Feel free to share your thoughts, experiences, or any questions in the comments below! Whether you are a student grappling with similar problems or an experienced developer with insights to share, I look forward to your feedback and discussion.

References and tools

Play and try: Interactive Explanation

Visualizer : visualizer

A tale of stacks and chunks. A sorting algorithm for the push_swap project of 42 Programming School.

Welcome to a detailed exploration of the Push_Swap challenge, a complex puzzle that tests the limits of algorithm design and efficiency. In this journey, we delve deep into the mechanics of sorting algorithms, particularly focusing on the use of two stacks to sort data with a minimal number of operations. This challenge not only sharpens problem-solving skills but also enhances understanding of data structures and algorithm optimization. Join me as we unpack the strategies that lead to an effective solution, learn from trials, and ultimately master the art of stack sorting.

Introduction : Entering the Chaos

The Push_Swap problem involves two stacks, a and b. Stack a starts filled with a random assortment of integers, and stack b starts empty. The objective is to sort the integers in stack a in ascending order using a limited set of operations. Oh, and you better keep it snappy because every operation counts. 😅

Operations in Toolbox

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

Getting Hands-On with the Problem

Before I could even type a line of code, I decided to get physical with the problem. Picture this: cutting squares of paper, each with a number, and laying them out on my living room floor. I was manually swapping these paper squares, pushing them from one side to the other, essentially performing the stack operations in real life.

Through this tactile approach, I could see the algorithms come to life. It was a practical way to see the problem literally unfold before my eyes, helping me grasp the mechanics behind each algorithmic twist and turn. I experimented with different algorithms like the bubble sort, quick sort and even the mechanical turk algorithm.

I referred to this video to understand different sorting algorithms and their Time complexity.

But I finally took inspiration from Ulysse Gerkerns’ approach of considering the two stacks as 4 stacks.

Sorting Strategy

Now, let’s talk strategy. The program doesn’t just sort — it strategizes. Here’s the flow:

1. Small Stack Handling:

• For stacks with 2–5 elements, we use specific functions (sort_two_a, sort_three_a, etc.) to sort them directly.(Small stacks = less drama. Quick and clean.)

2. Divide and Conquer:

• For larger stacks, we split them into chunks of three and use functions like sort_from_left to tackle them in segments.

3. Control Checks:

• Functions like n_ascending and n_descending ensure we’re staying on track.

To reduce the number of operations:

• Check If an element in Stack A has to be pushed to stack B and then rotated in B(rb) and if the next element in Stack A also has to be rotated(ra) then rr is used instead.
• Check if an element in Stack A has to be swapped and also an element in Stack B has to be swapped then ss is used.

Diving Into Thirds-Based Sorting

1. Initial Distribution: The sorting process begins by distributing the contents of Stack A into three categories based on their rank — max, mid, and min thirds. This distribution helps in managing the complexity by focusing on smaller subsets of the stack.

• Max Thirds remain in Stack A, positioned at the bottom as they represent the largest elements.
• Mid Thirds are transferred to Stack B, specifically to the top of Stack B.
• Min Thirds are rotated within Stack B to move to the bottom, preparing them for the subsequent sorting phase.

2. Recursive Sorting: Each of these chunks is recursively sorted again by dividing them into 3 chunks. When sorting elements in stack B,

• Max Thirds are transferred to top of Stack A.
• Mid Thirds are Transferred and rotated to bottom of Stack A.
• Min Thirds remain in Stack B.

The algorithm employs recursive functions that sort these smaller chunks and prepare them for eventual reintegration into Stack A.

3. Integrating Back to Stack A: Stack is sorted to have elements in ascending order. Once sorted in Stack B, elements are strategically moved back to Stack A. This step also involves recursive sorting to ensure elements are placed in the correct order as they return to Stack A.

4. Final Adjustments: The algorithm concludes with any necessary final adjustments in Stack A to ensure the entire stack is sorted in ascending order. This might involve additional sorting operations or simple rotations to align all elements properly.

General Approach and Flow

The Main Event

The main function is the quarterback, orchestrating the entire play. Here’s what happens:

1. Initialization: Sets up our stacks.
2. Input Validation: Checks for invalid input.
3. Stack Filling: Populates Stack A with integers from the command line and ranks them.
4. Sorting: Calls the right function to work its magic.
5. Clean-up: Frees up memory (because who likes a memory leak?).

Building the Stack

Before we get into the thick of code, let’s set the stage with the main characters:

• s_rlist: Each node in this doubly linked list holds a piece of our puzzle—the integers we need to sort. It’s like each number is waiting in line for the roller coaster, linked arm in arm with the next.
• s_head: Think of this as the gatekeeper of our list. It knows how many are in line and who’s first.
• s_stacks: The mastermind struct, holding together both Stack A and Stack B, keeping track of every move.

The push_swap program focuses solely on sorting the order of numbers, rather than their actual values. To simplify comparisons during the sorting process, it’s helpful to map each number to its rank within the list.

For example, given the list:

( 78, -12, 15, 300, 0 )

We can map these values into their ranks:

( 4, 1, 3, 5, 2 )

This transformation allows the algorithm to work more efficiently, as comparisons are made based on the ranks rather than the original values.

We first Initialize the Stacks and fill Stack A with the elements passed via command-line arguments.

if (!stacks_init(&stacks)) 
    return (ft_putstr_fd("Error\\n", 2), 1);
if (!fill_stacks(&stacks, argc, argv)) { 
    free_stacks(&stacks); 
    return (ft_putstr_fd("Error\\n", 2), 1); }

1. sort_from_left: Sorting From Small to Large

This function kicks off the sorting process for Stack A:

• Small Segments: If there are 5 or fewer elements, it calls specialized functions like sort_three_a or sort_five_a. (Because why reinvent the wheel?)

• Large Segments: For bigger groups, it delegates to thirds_right to divide and sort the stack further.

2. thirds_right

This function is where the real action happens. For a given segment:

• Divide into Thirds: Split the range of positions into three smaller chunks.
• Push & Rotate:
• Smallest elements? Push them to Stack B.
• Middle elements? Rotate Stack A to keep things neat.
• Largest elements? They stay in Stack A for now.

3. sort_back_left:

After splitting and sorting:

• This function merges the sorted thirds back into Stack A.
• It uses rotations and reverse rotations (rr_times) to maintain order while reintegrating the elements.

Example: Tackling a 20-Element Stack

Imagine we’ve got 20 elements in Stack A, and we need to sort them back into Stack A:

1. Split into Thirds: Ranks 1–7, 8–14, and 15–20 are identified.
2. Process the Thirds:

• check if elements are in 15–20 rank then rotate to stack A bottom.
• If elements are in 8–14 rank then push to Stack B and finally push 1–7 rank elements to stack B and rotate to bottom.

3. Merge Back: Use sort_back_right to integrate the sorted thirds into a fully ordered Stack A.

Benchmark? Crushed It. 💥

To validate the project, the benchmark we were aiming for:

• 100 random numbers: Sort them in under 700 operations.
• 500 random numbers: Keep it below 5500 operations.

Here’s how the above algorithm stacked up:

• 100 numbers: Sorted in ~630 operations.
• 500 numbers: Sorted in ~4600 operations.

Challenges Faced:

1. Managing Complexity: “How many moves are too many?” 🤔

• The Challenge: My initial attempts were more “brute force” than “elegant solution.” I hit operation counts that were way over the benchmark.
• How I Fixed It: I had to rethink my approach, break down the problem into smaller chunks (hello, thirds-based sorting!), and optimize every move.

2. Debugging Rotations and Reverse Rotations: “Why is everything upside down?” 🙃

• The Challenge: Rotations (ra, rb) and reverse rotations (rra, rrb) sounded simple... until my stacks started looking like scrambled eggs. Keeping track of how elements moved around in the stack was hard.
• How I Fixed It: I added print statements to track every operation and visualize the stack at every step.

3. Handling Edge Cases: “What even is sorted?” 🤯

• The Challenge: Edge cases like stacks with only two numbers, already-sorted stacks, or reverse-sorted stacks threw unexpected curveballs. My code initially failed on these cases, either doing extra operations or not sorting at all.
• How I Fixed It: I wrote specific conditions to handle these cases efficiently, avoiding unnecessary operations and reducing the overall count.

4. Optimization Paralysis: “Is this the best I can do?” 🤷‍♂️

• The Challenge: Even after meeting the benchmarks, I kept wondering if I could squeeze out a few more operations. The pursuit of perfection was never-ending, and I had to draw the line between “good enough” and over-engineering.
• How I Fixed It: I set milestones — once my algorithm consistently performed well below the benchmarks, I pushed the project for evaluation.

Mood Check:

Throughout the project, I fluctuated between:

• “I don’t know where or how to start!”
• “Oh this is interesting”
• “I’m the sorting master!” 💪
• “Why isn’t this working?” 😭
• “Okay, it works… but it’s slooow.” 🐢

And finally, “YES! IT PASSES ALL TESTS!” 🎉

Here’s a link to check the code.

While developing the sorting logic, I found invaluable insights in a blog post by Ulysse Gerkens on Medium, which outlines an efficient approach to the push_swap challenge in less than 4200 operations. This resource inspired some of the strategies I implemented in my own solution.

Tools Used

• Visualizer for visualization.
• For generating a large list of random numbers: random number generator.