Voici la deuxième partie de mon expérience de challenge technique avec un test python que j’ai échoué. J’ai donc décidé de résoudre à nouveau ce défi.
Contexte
Le challenge était le suivant : nous étions responsables du maintien des équipements informatiques d’un centre d’hébergement de serveurs. Nous avons un bâtiment d’une taille donné (x, y). Chaque case du bâtiment contenait un (1) serveur. Un hacker s’est infiltré dans un des serveurs et nous devons l’arrêter le plus rapidement possible.
Le but de l’exercice est de trouver la coordonnée de ce hacker (ligne et colonne d’un tableau à deux dimensions) le plus rapidement possible en faisant le moins possible de déplacement sur la grille. À chaque, tour d’une boucle, on nous indique si le serveur est à droite (R), à gauche (L), en haut (U) ou en bas (D)
Règles
Avant chaque saut, le détecteur vous fournira la direction du hacker par rapport à votre position actuelle :
- U (Up : hacker situé au-dessus)
- UR (Up-Right : hacker situé au-dessus et à droite)
- R (Right : hacker situé à droite)
- DR (Down-Right : hacker situé en dessous et à droite)
- D (Down : hacker situé en dessous)
- DL (Down-Left : hacker situé en dessous et à gauche)
- L (Left : hacker situé à gauche)
- UL (Up-Left : hacker situé au-dessus et à gauche)
Note
Pour certains tests, la position du hacker varie d’une exécution à l’autre. L’objectif est de trouver le meilleur algorithme possible. Les tests fournis et les validateurs utilisés pour le calcul du score sont similaires, mais différents.
Première solution
Au début, j’ai été vers une solution très simple pour résoudre cette problématique. Car je n’avais pas bien compris le principe qu’on nous donnait l’indication de la position du hacker à chaque tour… Note à moi-même ici, faire attention dans certaines compréhensions! C’est d’autant plus difficile de poser des questions à un texte. N’empêche que j’ai fait un simple schéma pour trouver la solution
Ici 1 indique le joueur et 2 indique le hacker :
[1][O][O][O] [O][O][O][O] [O][O][2][O] [O][O][O][O]
Donc, j’ai réalisé un code vraiment simple du genre :
def try_guest_hacker_v1(direction_hacker, matrix_width, matrix_height, player_x, player_y):
position_move_y = 0
if "U" in direction_hacker:
position_move_y = min(0, player_y - 1)
if "D" in direction_hacker:
position_move_y = max(matrix_height - 1, player_y + 1)
position_move_x = 0
if "L" in direction_hacker:
position_move_x = min(0, player_x - 1)
if "R" in direction_hacker:
position_move_x = max(matrix_width - 1, player_x + 1)
return [position_move_x, position_move_y]
Avec cette solution, les premières étapes ont bien passé, car les tableaux étaient petits. Donc, je respectais le nombre d’étapes maximum autorisé avec le jeu. Par contre, cela n’a pas du tout fonctionné avec les grands tableaux. Je ne saisis pas non plus quel algorithme utilisé selon ce contexte ? Car parfois vers, le centre, parfois à la fin. Bref, j’étais un peu perdu avec ce défi technique. Qui est en passant était sous pression avec le temps. Donc, cela m’a complexifié un peu les choses.
Solution mathématique (algorithme?)
C’est alors qu’en faisant mes recherches sur internet je suis tombé sur la recherche dichotomique (binary search)
Lorsque l’on cherche une donnée que l’on ne connaît pas, il y a toujours plusieurs stratégies pour l’aborder. Le système d’exploration par contradiction consiste à couper notre intervalle d’exploration en 2 et à chercher dans quel sous-intervalle se trouve ce que l’on cherche. De même, on recommence avec le sous-intervalle, on le coupe en deux pour ne garder que l’intervalle où l’on trouve ce que l’on cherche, etc. Eurêka, j’avais potentiellement trouvé une solution à mon équation.
Voici un petit jeu que j’ai trouvé sur internet avec ce concept.
Le jeu en python
Bien entendu que mon test était déjà terminé, mais j’ai quand même décidé de relever à nouveau ce défi pour mes propres connaissances dans les algorithmes mathématiques. Je me suis donc amusé à recréer le jeu que j’avais observé pour le refaire en python. Ainsi, j’avais une matrice de données avec une largeur et hauteur générée aléatoirement. Ensuite, je positionnais sur cette matrice 2 joueurs (joueur 1 et le hackeur).
J’ai réussi à bâtir la solution tout de même assez rapidement, puisque j’avais déjà presque résous la première équation. Il me manquait simplement de diviser la recherche par 2. Enfin, je crois puisque je n’ai pas le code officiel pour tester cette nouvelle solution pour savoir si elle répond à la caractéristique demandée du jeu. N’empêche que je me suis amusé à créer en plus quelques tests unitaires pour essayer les différentes techniques et les différents niveaux qui m’avaient été présentés lors de mon premier test. Et ce fut un succès, plus simple que je pensais encore une fois.
Conclusion
Voilà, une solution simple et complexe à la fois. Comme on dit, nous devons toujours apprendre chaque jour. C’est pour cela que j’ai créé un petit dossier sur le git avec ces exemples. En plus de mettre quelques petits tests unitaires pour tester cette solution. github.com/alfreddagenais/kilukru-dev-articles/tree/main/python/binary_search
Bon codage ❤️ !
