Solve an algorithmic problem

> Drafts

Draft in progress by ''Hazurl''

This article will give you the basics to achieve all types of algorithmic problem. It is aimed primarily at beginners who do not know how to start, but not only. The first part will explain the different methods of resolution, that is to say the theory. Then I would take for example the algorithm of the accessible squares in order to concretize these methods. I chose this algorithm because it is one of the most useful algorithms, and because the page dealing with it is not suitable for beginners; it is more from an optimization perspective. Since I am talking about it, optimization will not be part of this article, there are already some on this subject.

Theoretically

Generally speaking, an algorithmic problem is a question that can be solved by a computer. We distinguish two of them:

Decision problem: the answer is binary, yes or no, we can cite for example canUseWeapon or isObstacle, we can notice that these functions often have "is" or "can" at the beginning of their name, this allows reading, to immediately know that the response of the function will be a boolean, I strongly encourage you to do the same for your functions.
Evaluation problem: consists of the creation of an object stated by the problem, for example getCellsToUseWeapon which returns a structure: an array

It's not really for remembering but more for your general knowledge.

Understand the statement

Nothing more obviously but yet a step that many people forget. And not just beginners. It is necessary to understand the subject well and not to hesitate to read it again so that it is not vague. Imagine explaining the subject to someone who has never read it. You have to know how to reformulate it in your head, without making generalizations or specifications, otherwise you will start off on the wrong footing. Don't start thinking about solving the program. It is necessary to explain the input and output data, how it is built, etc... If the problem does not have any constraint on the output, imagine how it will be manipulated in order to simplify its use. You have to know how to answer (perfectly!) these two questions:

What do I have for starters?
What should I get?

Solve examples

The best way to find an implementation of the algorithm is to solve it yourself. The examples to be solved are not to be found purely randomly. We must take different cases and limits. You have to find out when the resolution is complicated, and then create the examples to the extreme. It is then necessary to prepare a support to test the algorithm. A simple equality test on the good output can do the job, otherwise you can make it a simple display to check it by hand.

Algorithm search

Here is the most concrete step. You need to turn your problem into a solution. The best is to proceed in more and more precise steps starting with your initial problem, moreover we can see that this process is an algorithm in itself 😉. You have to divide the problem into sub-problems while revealing the control structures: loops, conditional structures... Seek to redefine all your problems at each stage. Nothing better than an example to illustrate this concept: Sorting an array. We have an array in input and in return a sorted array (say in ascending order). How to sort an array? you have to modify it obviously, but it is not enough, you have to modify it until it is sorted. Oh ! But... wouldn't that be a loop? So our first division brought up a loop as well as his body and his condition. But modifying the array is not very precise... You also have to take into account that loop potentially equals infinite loop. Be very careful that the condition is evaluated differently at some point to break out of the loop. So modifying the array should make it more sorted before than after the loop so that the array is sorted at some point and the loop exits. There are a lot of ways to sort an array, one of the simplest is to invert the smallest element with the first element, then do the same with the second element, i.e. more generally, for each array element at position i invert it with the smallest element to its left. Here is a representation of where we are:

function sort_array (tab) // tab being the variable of the array to be sorted While is_not_sort(tab) For i ranging from 0 to n - 1 // n is the size of the array pos_elem_min = pos_elem_min_droite(tab, i) // position of the smallest array element to the right of i invert(tab, i, pos_elem_min) // We invert the two elements End For End Tan