push_swap

1. Make sure you understand the difference between algorithm and code.

   As Wikipedia says, an algorithm is a specification of a sequence of instructions used to solve a problem or perform a computation.
   It guarantees correct results and it has to be clear what it does on every possible input.

   The code you'll be writing is 'just' the implementation of such an algorithm. This implementation can have errors, even if the algorithm is correct. However, if the algorithm has errors, then there's no way your implementation following your algorithm could ever possibly be correct.

2. Make sure you know what unit testing is, and why it's highly superior to integration/integrated testing – that's what you probably will do naturally ;)
   For that, you could watch the first 22 minutes of this talk, or read its accompanying article.
3. Get to know what a stack is.
4. Get to know some sorting algorithms.
   (As well as the difference between comparison and non-comparison algorithms - if you like :))

So, you did your research? Great! Let's finally start. For that, let's make a plan.

After reading the subject, you probably were a little bit confused about what exactly you would have to do to solve this task. For me, it was quite confusing at the time. That's what we'd like to provide a map for.

In order to do this project, we think it's best to do the following:

1. Create yourself some bigger struct you can put all else in, and which most of your functions take as a parameter. This might look like that:

   typedef struct s_state
   {
           t_stack	*a;
           t_stack	*b;
           ...
   }	t_s;
   
   typedef struct s_push_swap
   {
           t_state	*s;
           ...
   }	t_ps;

   Concerning the data structure inside of t_stack? Choose for yourself :)
   A linked list probably works a bit better than an array – but choose whatever you'd like to practice more ^^

2. Implement the basic data type. More concretely:
   

   1. Implement a stack based on either a linked list or an array.

   2. Implement the push, pop, swap and rotate functions on this 'stack'. (A real stack has only push and pop.)
      For that, think for a moment what you'd like them to do.
      

      • What should swap and rotate on a 1-element stack do?
      • What should push with NULL be?
      • What should be the result of popping an empty stack?

      And only if you've come up with rules for these cases, then start to finally write the code.

   3. And then, when you – after some superficial or more profound testing – have decided that your functions work, write some unit tests, meaning:

      Write a test that inputs some 'normal' and all the special cases and compares the behaviour of your functions with the expected one.
      For that, it is helpful to write this additional testing functionality inside of another file (a test.c, maybe?), and to add a make test-rule to your Makefile that compiles and runs the tests. That way, you can ensure that you do run the tests regularly.

   4. Run make test:
      

      $ make test
      ...
      Testing simple stack functions...
      
      Test 4 (push): {4, 2, 3} ≠ {4, 2, 3, NULL}
      Test 11 (rotate): {2, 2, 3, NULL} ≠ {2, 3, NULL}
      Passed 10 / Failed 2 (of 12)

      Or however you want to make it look ;)

3. Implement your 'special' functionality on top of your general, well-tested one.
   

   1. Implement pa, pb, sa, sb, ss, ra, rb, rr, rra, rrb and rrr.
   2. The nice thing now is: You know for sure that the underlying functions work. Everything that goes wrong now only can be in your small additional layer that only composes all of the underlying functions together. Plus, whenever you need to change something, you can be sure that it isn't the bottom layer (provided you tested it and didn't introduce mistakes).

4. And now, finally: You've arrived at the algorithmic part. There's a few branches opening up from here, but there are two big approaches most of the people at our school took. The general idea is that you take some established algorithm (or some essential concepts out of it) and adjust it to our scenario.
   I won't guide you through an existing solution in here. But here's some general advice:
   

   Think about what your algorithm should do with a set of inputs. On paper/a whiteboard/whatever and not in code. Make sure you've got it in your mind, or at least written down what the sequence of steps your program should take is. And then try to implement them.

And there's also a push_swap visualizer for testing your algorithmic attempts. (If you can't get the C++ version to run, try the python one. That should work.)

Well, not much to be done here. Make sure you tested your push_swap properly, ran it against the checker, and got enough points on that to pass.

That should be it. Good luck!

To be honest, I fear that you're already quite fed up with doing anything like push_swap again. So, no algorithms or anything in here. Instead, again some of the basics:

Re-implement your stack from scratch, following the same process as last time. Only this time, you choose the underlying data structure you didn't choose for push_swap. Think before you write, and also write unit tests.

• What is easier, what harder?
• Would you still go with the one you've tried in the first place?

And if you're like: 'Bah, I don't need that.'?

Trust us, it'll come in handy to know when to use an array over a linked list and vice versa. The latest in *shudder* minishell.

• 'Sorting a stack' tutorial
• Another 'sorting a stack' tutorial
• An example project
• Another example project