ghost_legs.html

Le problème de Ghost Legs consiste à suivre des chemins.
On possède un diagramme avec des lignes verticales : les chemins. On descend les chemins de haut en bas, mais les chemins peuvent être connectés à gauche ou à droite. Si l’on trouve une connection, on doit la suivre et passer sur une colonne différente.
Le but de l’exercice et de suivre le chemin pour chaques entrées en haut du diagrame et d’en retrouver les sorties correspondantes en bas.

Approche utilisée

Description synoptique

Mon approche a été de d’abord convertir les entrées et sorties qui sont des caractères en indice (de 0 jusqu’à n-1, avec n le nombre de colonnes), pour une manipulation plus facile.
Ensuite positinner des curseurs sur chaque colonnes et les déplacer horizontalement (si il y a une connection) à chaque fois que l’on descend dans le diagramme.
On affiche finalement la solution en reconvertissant des indices, vers les caractères correspondant aux entrées, sorties.

Algorithme

nbSoluce = On calcule le nombre de colonnes à partir de la largeur totale du diagramme
inputs = liste contenant le caractère représentant la colonne (quand on est en haut)
outputs = liste contenant le caractère représentant la colonne (quand on est en bas)
cursors = la liste (de taille nbSoluce) qui va associer chaque indice de colonne de départ avec la colonne actuelle sur laquelle le curseur se trouve.

Pour chaque ligne du diagramme, sauf la 1ère et dernière qui respectivement les listes inputs et outputs :

Résolution

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

int main()
{
    int W;
    int H;
    int nbSoluce;

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

    // Nombre de solutions ( = nombre d'entrées)
    nbSoluce = W/3 +1;

    // Liste contenant les caractères correspondants au inputs (ex : A, B, C)
    char inputs[1025];
    // Liste contenant les caractères correspondants au outputs (ex : 1, 2, 3)
    char outputs[1025];
    // Liste contenant les curseurs qui vont suivre les lignes, un curseur par input
    int cursors[1025];

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

        if (i == 0) {
            // Si 1ere ligne, on update la liste d'inputs, et on initialise les curseurs
            for (int j=0; j < nbSoluce; j++) {
                inputs[j] = line[j*3];
                cursors[j] = j;
            }  
        } 
        else if (i == H-1) {
            // Si dernière ligne, on update la liste d'outputs
            for (int j=0; j < nbSoluce; j++) {
                outputs[j] = line[j*3];
            }
        } 
        else {
            // Ici on est dans les pipes, on update les positions des curseurs
            // On boucle pour chaque curseur
            for (int j=0; j < nbSoluce; j++) {
                int cursorPos = cursors[j] * 3;

                // Si il y a un - à gauche
                if (line[cursorPos-1] == '-') {
                        cursors[j]--;
                        continue;
                }
                // Si il y a un - à droite
                if (line[cursorPos+1] == '-') {
                        cursors[j]++;
                        continue;
                }        
            }
        }
    }

    // On affiche les solutions
    for (int i=0; i<nbSoluce; i++) {
        printf("%c%c\n", inputs[i], outputs[cursors[i]]);
    }

    return 0;
}

Comparaison avec une autre solution

#include <stdio.h>

char g[102][102];
int w, h;
int i, r, c;
char x;

int main(void) {
    /* Read first line */
    scanf("%d%d\n", &w, &h);
    
    /* Read rest of input */
    for (i = 0; i < h; i++)
        fgets(g[i], 102, stdin);
    
    for (i = 0; i < w; i += 3) {
        r = 1;
        c = i;
        x = g[0][i];
        while (r < h-1) {
            /* Move left */
            if (c && g[r][c-1] == '-') c -= 3;
            
            /* Move right */
            else if (g[r][c+1] == '-') c += 3;
            
            r += 1;
        }
        printf("%c%c\n", x, g[r][c]);
    }
}

Cette solution lit d’abord les entrées utilisateurs, et ensuite, parcours les colonnes une par une, le chemin est suivi jusqu’en bas afin de déterminer sa position de fin, ce qui est répété pour les autres colonnes.
J’ai aimé l’approche utilisée car je n’y avais pas pensé alors qu’elle paraît naturelle.

Bilan

J’ai d’abord eu du mal à comprendre le problème, en particulier comment le traiter à partir du code proposé pour les entrées utilisateur. Mais après avoir compris, j’ai réussi sans difficultés à résoudre le problème.