Rapport : Des nains sur des épaules de géants

Table des matières

1. Introduction

1.1. Principe de focntionnment

Url du challenge : https://www.codingame.com/ide/puzzle/dwarfs-standing-on-the-shoulders-of-giants

L’objectif de ce challenge est de modéliser les influences entre des personnes.

À la lecture des textes, on ne glane qu’une petite partie de cette dépendance : telle personne a influencé telle autre personne. On apprendra par la suite que cette seconde personne en a, à son tour, influencé une troisième, et ainsi de suite. C’est cette chaîne d’influence qui nous intéresse dans cet exercice, et plus précisément, il s’agit de trouver la longueur de la plus grande de ces chaînes.

1.2. Données fournies

On reçoit en entrée un entier N qui représente le nombre de relations. Suivi de N lignes contenant chacune deux entiers X et Y, qui représentent une relation entre les personnes X et Y.

1.3. Données à fournir

La sortie doit être la longueur de la plus grande chaîne d’influence.

1.4. Contraintes

  • ’N’ est compris entre : 0 < N < 10 000
  • ’X’ et ’Y’ sont compris entre : 0 < X, Y < 10 000

2. Méthode de résolution

On commence par définir structures de données qui vont nous permettre de stocker les relations entre les personnes. La structure ’arbret’ sera le point d’entrée de notre arbre. Elle contient un pointeur vers la racine de l’arbre. La structure ’noeudt’ représente un nœud de l’arbre. Elle contient un identifiant, un pointeur vers le fils et un pointeur vers le frère. 

typedef struct noeud_t {
    int id;
    struct noeud_t *fils;
    struct noeud_t *frere;
} noeud_t;

typedef struct {
    noeud_t *racine;
} arbre_t;

On définit ensuite deux fonctions qui vont nous permettre de créer respectivement un arbre et un nœud. 

arbre_t *creer_arbre() {
    arbre_t *arbre = malloc(sizeof *arbre);

    noeud_t *racine = malloc(sizeof *racine);
    racine->id = 0;
    racine->fils = NULL;
    racine->frere = NULL;

    arbre->racine = racine;
    return arbre;
}

noeud_t *creer_noeud(int id) {
    noeud_t *noeud = malloc(sizeof *noeud);
    noeud->id = id;
    noeud->fils = NULL;
    noeud->frere = NULL;
    return noeud;
}

On définit ensuite deux fonctions qui permettront de détruire l’arbre et les nœuds. La fonction ’destructionnoeud’ est récursive, elle parcourt l’arbre en profondeur. 

void destruction_noeud(noeud_t *noeud) {
    if (noeud->fils != NULL) {
        destruction_noeud(noeud->fils);
    }
    if (noeud->frere != NULL) {
        destruction_noeud(noeud->frere);
    }
    free(noeud);
}

void destruction_arbre(arbre_t *arbre) {
    destruction_noeud(arbre->racine);
    free(arbre);
}

On définit ensuite une fonction qui permet d’ajouter un fils à un nœud. 

void ajouter_fils(noeud_t *noeud, noeud_t *fils) {
    if (noeud->fils == NULL) {
        noeud->fils = fils;
    } else {
        noeud_t *fils_actuel = noeud->fils;
        while (fils_actuel->frere != NULL) {
            fils_actuel = fils_actuel->frere;
        }
        fils_actuel->frere = fils;
    }
}

On définit ensuite une fonction qui permet de savoir si un nœud est fils d’un autre nœud. 

bool est_fils(noeud_t *noeud, int id_noeud) {
    if (noeud->fils != NULL) {
        if (noeud->fils->id == id_noeud) {
            return true;
        } else {
            noeud_t *fils = noeud->fils;
            while (fils->frere != NULL) {
                if (fils->frere->id == id_noeud) {
                    return true;
                }
                fils = fils->frere;
            }
        }
    }
    return false;
}

On définit ensuite une fonction qui permet de rechercher un nœud dans l’arbre. La fonction est récursive, elle parcourt l’arbre en profondeur. La fonction retourne un pointeur sur le nœud recherché, ou NULL si le nœud n’a pas été trouvé. 

noeud_t *recherche_noeud(noeud_t *noeud, int id_noeud) {
    if (noeud->id == id_noeud) {
        return noeud;
    }

    if (noeud->fils != NULL) {
        noeud_t *fils = recherche_noeud(noeud->fils, id_noeud);
        if (fils != NULL) {
            return fils;
        }
    }

    if (noeud->frere != NULL) {
        noeud_t *frere = recherche_noeud(noeud->frere, id_noeud);
        if (frere != NULL) {
            return frere;
        }
    }

    return NULL;
}

On définit ensuite une fonction qui permet de copier un sous-arbre. La fonction est récursive, elle parcourt l’arbre en profondeur, crée un nouvel arbre identique et retourne un pointeur sur la racine de l’arbre copié. 

noeud_t *copie_sous_arbre(noeud_t *noeud) {
    noeud_t *copie = creer_noeud(noeud->id);
    if (noeud->fils != NULL) {
        copie->fils = copie_sous_arbre(noeud->fils);
    }
    if (noeud->frere != NULL) {
        copie->frere = copie_sous_arbre(noeud->frere);
    }
    return copie;
}

On définit ensuite une fonction qui permet d’ajouter un sous-arbre à un autre arbre. 

void ajoute_copie_fils(noeud_t *noeud, int id_pere, noeud_t *fils) {
    // recusivite
    if (noeud->fils != NULL) {
        ajoute_copie_fils(noeud->fils, id_pere, fils);
    }

    if (noeud->frere != NULL) {
        ajoute_copie_fils(noeud->frere, id_pere, fils);
    }

    if (noeud->id == id_pere) {
        noeud_t *copie = copie_sous_arbre(fils);
        copie->frere = NULL;
        ajouter_fils(noeud, copie);
    }
}

On définit ensuite une fonction qui permet d’oublier un fils d’un nœud. On remarquera que la fonction ne libère pas la mémoire du fils, elle ne fait que le déréférencer. 

void oublier_fils(noeud_t *noeud, int id_fils) {
    if (noeud->fils != NULL) {
        if (noeud->fils->id == id_fils) {
            noeud->fils = noeud->fils->frere;
        } else {
            noeud_t *fils = noeud->fils;
            while (fils->frere != NULL) {
                if (fils->frere->id == id_fils) {
                    fils->frere = fils->frere->frere;
                    break;
                }
                fils = fils->frere;
            }
        }
    }
}

La fonction suivante permet d’ajouter une relation entre deux nœud. Si le nœud père n’existe pas, il est créé et est ajouté à la racine. Si le nœud fils n’existe pas, il est créé. Ensuite on ajoute une copie du noeud fils à tous les nœuds père. Enfin on supprime les références au nœud fils dans la racine. 

void ajouter_noeud(arbre_t *arbre, int id_pere, int id_fils) {

    if (recherche_noeud(arbre->racine, id_pere) == NULL) {
        // si le pere n'existe pas on le cree
        ajouter_fils(arbre->racine, creer_noeud(id_pere));
    }

    noeud_t *fils = recherche_noeud(arbre->racine, id_fils);

    if (fils == NULL) {
        fils = creer_noeud(id_fils);
        ajoute_copie_fils(arbre->racine, id_pere, fils);
        destruction_noeud(fils);
    } else {
        // on recopie le fils a tous les version du  noeud pere
        ajoute_copie_fils(arbre->racine, id_pere, fils);
        // on supprime les references au fils dans la racine
        if (est_fils(arbre->racine, id_fils)) {
            oublier_fils(arbre->racine, id_fils);
            fils->frere = NULL;
            destruction_noeud(fils);
        }
    }
}

La fonction suivante permet de calculer la hauteur d’un arbre. On parcourt l’arbre en profondeur, on calcule la hauteur de chaque fils et on retourne la hauteur maximale. 

int hauteur(noeud_t *noeud) {
    if (noeud->fils == NULL) {
        return 0;
    }

    int h;
    int max = hauteur(noeud->fils);
    noeud_t *fils = noeud->fils->frere;
    while (fils != NULL) {
        h = hauteur(fils);
        if (h > max) {
            max = h;
        }
        fils = fils->frere;
    }
    return max + 1;
}

La fonction ’main’ commence par lire le nombre de relations à ajouter à l’arbre. Ensuite on lit les relations et on les ajoute à l’arbre. Enfin on affiche la hauteur de l’arbre et on libère la mémoire. 

int main() {
    int n;
    scanf("%d", &n);

    arbre_t *arbre = creer_arbre();

    int x, y, i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        ajouter_noeud(arbre, x, y);
    }

    printf("%d\n", hauteur(arbre->racine));

    destruction_arbre(arbre);

    return 0;
}

2.1. Implémentation complète

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

typedef struct noeud_t {
    int id;
    struct noeud_t *fils;
    struct noeud_t *frere;
} noeud_t;

typedef struct {
    noeud_t *racine;
} arbre_t;

arbre_t *creer_arbre() {
    arbre_t *arbre = malloc(sizeof *arbre);

    noeud_t *racine = malloc(sizeof *racine);
    racine->id = 0;
    racine->fils = NULL;
    racine->frere = NULL;

    arbre->racine = racine;
    return arbre;
}

noeud_t *creer_noeud(int id) {
    noeud_t *noeud = malloc(sizeof *noeud);
    noeud->id = id;
    noeud->fils = NULL;
    noeud->frere = NULL;
    return noeud;
}

void destruction_noeud(noeud_t *noeud) {
    if (noeud->fils != NULL) {
        destruction_noeud(noeud->fils);
    }
    if (noeud->frere != NULL) {
        destruction_noeud(noeud->frere);
    }
    free(noeud);
}

void destruction_arbre(arbre_t *arbre) {
    destruction_noeud(arbre->racine);
    free(arbre);
}

void ajouter_fils(noeud_t *noeud, noeud_t *fils) {
    if (noeud->fils == NULL) {
        noeud->fils = fils;
    } else {
        noeud_t *fils_actuel = noeud->fils;
        while (fils_actuel->frere != NULL) {
            fils_actuel = fils_actuel->frere;
        }
        fils_actuel->frere = fils;
    }
}

bool est_fils(noeud_t *noeud, int id_noeud) {
    if (noeud->fils != NULL) {
        if (noeud->fils->id == id_noeud) {
            return true;
        } else {
            noeud_t *fils = noeud->fils;
            while (fils->frere != NULL) {
                if (fils->frere->id == id_noeud) {
                    return true;
                }
                fils = fils->frere;
            }
        }
    }
    return false;
}

noeud_t *recherche_noeud(noeud_t *noeud, int id_noeud) {
    if (noeud->id == id_noeud) {
        return noeud;
    }

    if (noeud->fils != NULL) {
        noeud_t *fils = recherche_noeud(noeud->fils, id_noeud);
        if (fils != NULL) {
            return fils;
        }
    }

    if (noeud->frere != NULL) {
        noeud_t *frere = recherche_noeud(noeud->frere, id_noeud);
        if (frere != NULL) {
            return frere;
        }
    }

    return NULL;
}

noeud_t *copie_sous_arbre(noeud_t *noeud) {
    noeud_t *copie = creer_noeud(noeud->id);
    if (noeud->fils != NULL) {
        copie->fils = copie_sous_arbre(noeud->fils);
    }
    if (noeud->frere != NULL) {
        copie->frere = copie_sous_arbre(noeud->frere);
    }
    return copie;
}

void ajoute_copie_fils(noeud_t *noeud, int id_pere, noeud_t *fils) {
    // recusivite
    if (noeud->fils != NULL) {
        ajoute_copie_fils(noeud->fils, id_pere, fils);
    }

    if (noeud->frere != NULL) {
        ajoute_copie_fils(noeud->frere, id_pere, fils);
    }

    if (noeud->id == id_pere) {
        noeud_t *copie = copie_sous_arbre(fils);
        copie->frere = NULL;
        ajouter_fils(noeud, copie);
    }
}

void oublier_fils(noeud_t *noeud, int id_fils) {
    if (noeud->fils != NULL) {
        if (noeud->fils->id == id_fils) {
            noeud->fils = noeud->fils->frere;
        } else {
            noeud_t *fils = noeud->fils;
            while (fils->frere != NULL) {
                if (fils->frere->id == id_fils) {
                    fils->frere = fils->frere->frere;
                    break;
                }
                fils = fils->frere;
            }
        }
    }
}

void ajouter_noeud(arbre_t *arbre, int id_pere, int id_fils) {

    if (recherche_noeud(arbre->racine, id_pere) == NULL) {
        // si le pere n'existe pas on le cree
        ajouter_fils(arbre->racine, creer_noeud(id_pere));
    }

    noeud_t *fils = recherche_noeud(arbre->racine, id_fils);

    if (fils == NULL) {
        fils = creer_noeud(id_fils);
        ajoute_copie_fils(arbre->racine, id_pere, fils);
        destruction_noeud(fils);
    } else {
        // on recopie le fils a tous les version du  noeud pere
        ajoute_copie_fils(arbre->racine, id_pere, fils);
        // on supprime les references au fils dans la racine
        if (est_fils(arbre->racine, id_fils)) {
            oublier_fils(arbre->racine, id_fils);
            fils->frere = NULL;
            destruction_noeud(fils);
        }
    }
}

int hauteur(noeud_t *noeud) {
    if (noeud->fils == NULL) {
        return 0;
    }

    int h;
    int max = hauteur(noeud->fils);
    noeud_t *fils = noeud->fils->frere;
    while (fils != NULL) {
        h = hauteur(fils);
        if (h > max) {
            max = h;
        }
        fils = fils->frere;
    }
    return max + 1;
}

int main() {
    int n;
    scanf("%d", &n);

    arbre_t *arbre = creer_arbre();

    int x, y, i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        ajouter_noeud(arbre, x, y);
    }

    printf("%d\n", hauteur(arbre->racine));

    destruction_arbre(arbre);

    return 0;
}

3. Tests

3.1. Compilation

Compilation avec gcc : 

✅ Compilation sans erreur/warning OK

3.2. Test de Codingame

3.2.1. Test 1 : Simple example

Input: 

3
1 2
1 3
3 4

Expected output: 

3

Actual output: 

3

Run test: 

Test 1: Simple example
✅ Test passed

3.2.2. Test 2 : Complete example

Input: 

8
1 2
1 3
3 4
2 4
2 5
10 11
10 1
10 3

Expected output: 

4

Actual output: 

4

Run test: 

Test 2: Complete example
✅ Test passed

3.2.3. Test 3 : Several mentors

Input: 

4
2 3
8 9
1 2
6 3

Expected output: 

3

Actual output: 

3

Run test: 

Test 3: Several mentors
✅ Test passed

3.2.4. Test 4 : Several mentors 2

Input: 

9
7 2
8 9
1 6
6 9
1 7
1 2
3 9
2 3
6 3

Expected output: 

5

Actual output: 

5

Run test: 

Test 4: Several mentors 2
✅ Test passed

3.2.5. Résumé global

✅ Test 1 : Simple example passed
✅ Test 2 : Complete example passed
✅ Test 3 : Several mentors passed
✅ Test 4 : Several mentors 2 passed
Passed: 4 (100.0%)
Failed: 0 (0.0%)

3.3. Test Valgrind

✅ Valgrind check
==12901== Memcheck, a memory error detector
==12901== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==12901== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info
==12901== Command: ./temp/code
==12901== 
3
==12901== 
==12901== HEAP SUMMARY:
==12901==     in use at exit: 0 bytes in 0 blocks
==12901==   total heap usage: 11 allocs, 11 frees, 8,392 bytes allocated
==12901== 
==12901== All heap blocks were freed -- no leaks are possible
==12901== 
==12901== For lists of detected and suppressed errors, rerun with: -s
==12901== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

3.4. Capture d’écran de DDD

capture.png

Figure 1 : Capture d’écran de DDD (test 4)

4. Solution de la communauté

Solution de TelePario : https://www.codingame.com/training/medium/dwarfs-standing-on-the-shoulders-of-giants/solution?id=1531648 

#include <stdio.h>

int matrix[10000][10000];

int pathLength(int z, int n) {
    for (int s = 0; s < n; s++) if (matrix[z][s]) return pathLength(s, n) + 1;
    return 1;
}

int main(void)
{
    int max = 0;
    int n; // the number of relationships of influence
    if (!scanf("%d", &n)) return -1;

    for (int i = 0; i < n; i++) {
        int x, y;
        if (!scanf("%d%d", &x, &y)) return -2;
        matrix[x][y] = 1;
        if (x > max) max = x;
        if (y > max) max = y;
    }
    max++;

    int maxLength = 0;
    for (int z = 0; z < max; z++) 
        for (int s = 0; s < max; s++)
            if (matrix[z][s]) {
                int length = pathLength(s, max) + 1;
                if (length > maxLength) maxLength = length;
            }

    printf("%d\n", maxLength);
    return 0;
}

J’ai choisi cette solution car elle est très simple et efficace. Elle utilise une matrice pour stocker les relations entre les nœuds. Elle utilise ensuite une fonction récursive pour calculer la longueur du chemin le plus long. On peut remarquer que la fonction récursive est appelée pour chaque nœud, ce qui est très coûteux en temps. On peut donc améliorer la solution en calculant la longueur du chemin le plus long pour chaque noeud et en stockant le résultat dans un tableau. On peut ensuite parcourir le tableau pour trouver le chemin le plus long. Enfin la déclaration de la matrice est très gourmande en mémoire, une allocation dynamique serait peut-être plus adaptée.

5. Conclusion

Lors de cet exercice, j’ai decourvert les graphes orientés acycliques (DAG) et les algorithmes de parcours de graphe. J’ai aussi pu approfondir mon utilisation de valgrind pour détecter les fuites de mémoire.

Retour vers ma page Web personnelle

Crédits :

Date: 2023-03-03

Auteur: Jules Girard

Created: 2023-04-26 mer. 19:26