Exercice CodinGame: GHOST LEGS par java_coffee_cup

Approches de l’exercice

La compréhension de l’exercice n’a pas été particulièrement difficile pour moi puisque j’avais déjà abordé ce type de mini-jeux par le passé. En effet, dans le mini-jeux Pipe Maze de Mario Party, un des joueurs doit en quelques secondes déterminer dans quel tuyau lâcher un coffre rempli de pièces d’or afin qu’il atteigne son personnage.

Pipe Maze - Mario Party

Cependant, même si le concept de ce mini-jeux m’était familier, je ne m’étais jamais vraiment penché sur le fonctionnement du programme qui en découlait. C’est pourquoi il m’a fallu plusieurs essais avant de parvenir à une solution finale totalement fonctionnelle.

Première approche

La première solution que j’ai commencé à construire a découlé d’une mauvaise compréhension de la consigne et plus précisément des données entrées par l’utilisateur. En effet, je pensais que l’on devait générer notre propre diagramme contenant les caractères “|” et “-”.
Ainsi j’ai commencé à créer dynamiquement un tableau de pointeurs sur des tableaux de caractères qui aurait correspondu aux lignes et aux colonnes du diagramme.








/*
 * H et W respectivement la hauteur et la largueur du
 * diagramme donnée en entrée
 * 
*/
char ** tab = (char**) malloc(H*sizeof(char *));
for (int i = 0; i < H; i++):
    tab[i] = (char *) malloc(W*sizeof(char));

Création du tableau que j’aurais utilisé pour la suite de mon programme

J’ai ensuite compris que le diagramme était donné en entrée ligne par ligne par l’utilisateur en relisant l’énoncé et en analysant le début de programme auto-généré par l’exercice. J’aurais pu garder la solution d’un tableau pour stocker l’intégralité du diagramme avant d’analyser les trajets suivis en fonction des différents points d’entrées. Cependant, étant donné qu’il n’était pas utile de garder une trace du diagramme après l’exécution du programme et puisque je commençais à imaginer une seconde solution qui me paraissait plus élégante pour répondre au problème j’ai décidé d’abandonner cette première idée.

Seconde approche

Pour cette seconde approche du problème je me suis représenté la situation comme des billes introduisent dans des tuyaux et dont il fallait que je mémorise et actualise la position à chaque ligne du diagramme. En effet, aucune ligne du diagramme ne serait donnée deux fois. J’ai donc créé un tableau d’entiers comportant autant de cases que d’entrées dans le diagramme et qui ne servirait qu’à stocker la position de ces “billes”.


// W est la largueur du diagramme donnée en entrée
int * pos = (int *) malloc(W/3+1 * sizeof(int));

Création du tableau qui stock les positions

Puisque l’énoncé précisait que l’index des entrées et des sorties du diagramme pouvait ne suivre aucune logique, il fût assez évident qu’il fallait également que je stock dans des tableaux de caractères la première et dernière ligne du diagramme pour pouvoir faire correspondre les positions calculées aux indexages utilisés par le diagramme.




// W est la largueur du diagramme donnée en entrée
char * start = (char *) malloc(W * sizeof(char));
char * end = (char *) malloc(W * sizeof(char));
char * line = (char *) malloc(W * sizeof(char));

Création des tableaux stockant les indexs et la ligne du diagramme actuelle

Ensuite, il fallait coder la partie du programme qui se chargerait d’actualiser les positons correspondant aux différentes entrées du diagramme.
Pour ce faire j’ai simplement créé un boucle ne parcourant chaque ligne du diagramme que de trois en trois caractères ce qui correspond aux emplacements des caractères “|”. Ainsi en analysant si l’un des caractères à droite ou à gauche est “-” je peux incrémenter ou décrémenter la position de la “bille” situé au niveau du caractère “|” actuellement observé.


























/*
 * H et W respectivement la hauteur et la largueur du
 * diagramme donnée en entrée
 * 
*/
for (int i = 0; i < H; i++) {
        // lecture de la ligne courante du diagramme
        scanf("%[^\n]", line); fgetc(stdin);
        
        // copie des index d'entré dans un tableau
        if(i == 0){strcpy(start, line);
        }
        // copie des index de sortie dans un tableau
        else if (i == H-1) {strcpy(end, line);
        }
        
        for(int j = 0; j <= W/3; j++){
            // actualisation de la position de l'entrée n°j
            if(line[pos[j]*3+1] == '-'){
                pos[j]++;
            }
            else if(line[pos[j]*3-1] == '-'){
                pos[j]--;
            }    
        }
    }

Actualisation des positions des entrées en fonction de l’organisation du diagramme au niveau de leur position actuelle

Pour finir, le programme devait afficher pour chaque entrée dans le diagramme la sortie correspondante sans oublier que l’index des entrées et sorties peut ne pas avoir de sens.
Pour ce faire une simple boucle associe chaque index d’entrée à un index de sortie en fonction de la dernière position de l’entrée dans le tableau des positions.




// W est la largueur du diagramme donnée en entrée
for(int i = 0; i < W; i += 3){
    printf("%c%c\n", start[i], end[pos[i/3]*3]);
    }

Affichage de la sortie correspondant à chaque entrée grâce au tableau des positions

Code complet























































#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main()
{
    int W;
    int H;
    scanf("%d%d", &W, &H); fgetc(stdin);

    // dynamic memory allocation
    char * start = (char *) malloc(W * sizeof(char)); // 1st line of diagram
    char * end = (char *) malloc(W * sizeof(char)); // last line of diagram
    char * line = (char *) malloc(W * sizeof(char)); // working line of diagram
    int * pos = (int *) malloc(W/3+1 * sizeof(int)); // current position of player

    // init of the positions
    for(int i = 0; i < W/2; i++){
        pos[i] = i;
    }

    for (int i = 0; i < H; i++) {
        scanf("%[^\n]", line); fgetc(stdin);

        if(i == 0){strcpy(start, line); // copy of 1st line labels
        }
        else if (i == H-1) {strcpy(end, line); //copy of last line labels
        }
        
        for(int j = 0; j <= W/3; j ++){
            if(line[pos[j]*3+1] == '-'){ // move to the right
                pos[j]++;
            }
            else if(line[pos[j]*3-1] == '-'){ // move to the left
                pos[j]--;
            }    
        }
    }

    for(int i = 0; i < W; i += 3){ // print of related starting and ending positions
        printf("%c%c\n", start[i], end[pos[i/3]*3]);
    }

    // freeing of the allocated memory
    free(start);
    free(end);
    free(line);
    free(pos);
    start = NULL;
    end = NULL;
    line = NULL;
    pos = NULL;

    return 0;
}

Autres solutions de la communauté

Beaucoup d’utilisateurs ont utilisé une solution semblable qui est de mettre à jour un tableau de positions ligne après ligne et donc de ne pas garder l’intégralité du diagramme dans un tableau.
Cependant, Wafonga (étudiant d’ISIMA), a utilisé un tableau de pointeur sur des tableaux de caractères comme j’avais commencé à le faire lors de ma première approche du sujet.
D’autres comme BeeGee, ont dans la même optique de conservation du diagramme, a créé un tableau en 2 dimensions. Cependant avec une allocation de mémoire fixe, beaucoup de cette mémoire ne sera jamais utilisé dans le cas d’un petit diagramme ce qui n’est pas optimal.
Cependant dans le cadre d’un programme aussi simple et avec des contraintes clairement défini dans l’énoncé de l’exercice il est vrai qu’il n’y a pas besoin d’allouer de la mémoire dynamiquement pour chaque tableau et qu’allouer la taille maximale imposée par les contraintes est suffisant.