Des nains sur des épaules de géants

1. Présentation du puzzle
2. Presentation de ma méthode de résolution
3. Description d’une autre méthode.
- 3.1. Code de MJZ
4. Apprentissage

1. Présentation du puzzle

Pour ce puzzle, on nous donne un arbre avec des liens. On doit déterminer le nombre de personnes impliquées dans la plus longue succession d’influences. On reçoit en entrée un entier N qui est le nombre d’influence en entrée. Une entrée possible est :

Cette entrée represente l’arbre :

2. Presentation de ma méthode de résolution

2.1. Description

Pour réaliser ce puzzle j’ai utilisée des listes chainées. J’ai donc crée une strcuture noeud qui comporte son nombre. Un pointeur vers son fils, et un pointeur vers un frère. Tout d’abord j’initialise un noeud racine. Je stocke dans un tableau toutes les influence mis en entrée. Pour chaque influence j’ajoute cette influence dans ma liste chainée. Cette ajout ce fait grâce à la fonction ajouteinfluence(). J’ai distingué 6 cas pour ajouter l’influence:

2.1.1. Premier cas :

Ajout d’un lien interne, les deux nombres apparaissent deja dans la liste chainée. Si le lien est A -> B, je cherche A dans ma liste chainée grace a la fonction trouve() qui renvoie l’adresse du noeud qui contient le nombre A, je recupere aussi l’adresse du noeud qui contient B. Je tente de lier le fils de A comme B si A n’a pas de fils. Si A a un fils alors je l’ajoute au dernier frere du fils de A.

2.1.2. Second cas :

J’observe que il y eu une influence A -> B , et que ma nouvelle influence est A -> C. Alors j’ajoute C comme dernier frere du frere de B.

2.1.3. Troisieme cas :

Ajout d’un frere au fils de la racine. J’observe qu’il y a eu A -> B et que mon influence est C -> B. J’ajoute donc un frere au dernier frere du fils de la racine.

2.1.4. Quatrieme cas :

J’observe qu’il y eu A -> B et que ma nouvelle influence est C -> A. Dans ce cas je place C comme père de A.

2.1.5. Cinquieme cas :

Il y a eu A -> B et ma nouvelle influence est B -> C. Dans ce cas j’ajoute C comme fils de B ou C comme dernier frere du fils de B.

2.1.6. Sixieme cas :

Si ma nouvelle influence est A -> B et que ni A ni B n’apparait dans mes precedentes influences alors j’ajoute A comme fils de la racine ou comme dernier frere du fils de la racine et je lie B comme fils de A.

2.2. Affichage du max

A la fin de l’ajout de chaque influence. J’utilise une fonction recursive qui me permet de determiner la hauteur maximale de fils. C’est la fonction affichehauteurmax(). Cependant j’obtiens des erreurs de segmentation pour certains tests, probablement du à une boucle infinie lors du parcours de l’arbre. Je n’ai pas réussi à corriger le code.

2.3. Le code :

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

struct influence{
  int x;
  int y;
};typedef struct influence influence;

struct noeud{
    int nb;
    struct noeud *frere;
    struct noeud *fils;
};typedef struct noeud noeud;

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


int affichehauteurmax(noeud *actuel, int hmax, int hi) {
    if(actuel == NULL) {
        return hmax;
    }
    if(hi > hmax) {
        hmax = hi;
    }
    if(actuel->fils != NULL) {
        hmax = affichehauteurmax(actuel->fils, hmax, hi+1);
    }
    if(actuel->frere != NULL) {
        hmax = affichehauteurmax(actuel->frere, hmax, hi);
    }
    return hmax;
}
noeud * trouve(int nb, noeud *actuel, noeud *pere){
    if (actuel->nb==nb){
        return actuel;
    }
    if (actuel->frere!=NULL && actuel->frere != pere){
        noeud *resultat = trouve(nb,actuel->frere, pere);
        if (resultat != NULL){
            return resultat;
        }
    }
    if (actuel->fils!=NULL){
        return trouve(nb,actuel->fils, actuel);
    }
    return NULL;
}

void ajouteinfluence(influence tabinfluence[],int pos,noeud *racine){
    int i,j;
    noeud *nouveau;
    noeud *actuel;
    noeud *actuel2;
    noeud *filsnouv;
    nouveau=malloc(sizeof(noeud));
    nouveau->frere=NULL;
    nouveau->fils=NULL;
    for(i=0;i<pos;i++){
        if (tabinfluence[pos].x==tabinfluence[i].x || tabinfluence[pos].x==tabinfluence[i].y ){
            for(j=0;j<pos;j++){
                if (tabinfluence[pos].y==tabinfluence[j].x || tabinfluence[pos].y==tabinfluence[j].y ){
                    actuel=trouve(tabinfluence[pos].x,racine->fils,racine);
                    actuel2=trouve(tabinfluence[pos].y,racine->fils,racine);
                    if (actuel->fils==NULL){
                        actuel->fils=actuel2;
                    }else{
                        actuel=actuel->fils;
                        while(actuel->frere!=NULL){
                            actuel=actuel->frere;
                        }
                        actuel->frere=actuel2;
                    }/*Ajout d'un lien interne*/
                    return;
                }
            }
        }
    }

    for (i=0;i<pos;i++){
        if (tabinfluence[i].x==tabinfluence[pos].x){
            actuel=trouve(tabinfluence[i].x,racine->fils,racine);
            actuel=actuel->fils;
            while(actuel->frere!=NULL){
                actuel=actuel->frere;
            }
            actuel->frere=nouveau;
            nouveau->nb=tabinfluence[pos].y;
            return;
        } /*Ajout d'un frere*/

        else if (tabinfluence[pos].y==tabinfluence[i].y){
            actuel=racine->fils;
            while(actuel->frere!=NULL){
                actuel=actuel->frere;
            }
            nouveau->fils=trouve(tabinfluence[i].y,racine->fils,racine);
            actuel->frere=nouveau;
            nouveau->nb=tabinfluence[pos].x;
            return;
        } /*Ajouter un frere au plus haut pere*/

        else if (tabinfluence[pos].y==tabinfluence[i].x){
            actuel=racine->fils;
            nouveau->frere=actuel->frere;
            actuel->frere=NULL;
            racine->fils=nouveau;
            nouveau->fils=actuel;
            nouveau->nb=tabinfluence[pos].x;
            return;
        }

        else if (tabinfluence[i].y==tabinfluence[pos].x){
            actuel=trouve(tabinfluence[pos].x,racine->fils,racine);
            if (actuel->fils!=NULL){
                actuel=actuel->fils;
                while(actuel->frere!=NULL){
                    actuel=actuel->frere;
                }
                actuel->frere=nouveau;
                nouveau->nb=tabinfluence[pos].y;
            }else{
                actuel->fils=nouveau;
                nouveau->nb=tabinfluence[pos].y;
            }
            return;
        } /*Ajout fils ou frere du fils si deja un fils qui existe*/
    }
    filsnouv=malloc(sizeof(noeud));
    filsnouv->frere=NULL;
    filsnouv->fils=NULL;
    if (racine->fils==NULL){
        racine->fils=nouveau;
        nouveau->fils=filsnouv;
        nouveau->nb=tabinfluence[pos].x;
        filsnouv->nb=tabinfluence[pos].y;
    }else{
        actuel=racine->fils;
        while(actuel->frere!=NULL){
            actuel=actuel->frere;
        }
        actuel->frere=nouveau;
        nouveau->fils=filsnouv;
        nouveau->nb=tabinfluence[pos].x;
        filsnouv->nb=tabinfluence[pos].y;
    }
    return;
}/*Ajout fils à la racine et fils a ce fils*/


int main()
{
    int n,i,z;
    int x;
    int y;
    influence *tabinfluence;
    noeud *racine;
    scanf("%d", &n);
    tabinfluence=malloc(n*sizeof(influence));
    racine=malloc(sizeof(noeud));
    racine->nb=0;
    racine->frere=NULL;
    racine->fils=NULL;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        tabinfluence[i].x=x;
        tabinfluence[i].y=y;
        ajouteinfluence(tabinfluence,i,racine);
    }
    z=affichehauteurmax(racine,0,0);
    printf("%d\n",z);
    libere_noeud(racine);
    free(tabinfluence);
    return 0;
}

2.4. Tests :

2.4.1. test 1 :

Résultat valide 3 on obtient :

2.4.2. test 2:

Résultat valide 4 on obtient :

Une erreur de segmentation se produit.

2.4.3. test 3:

Voici un test personnel Résultat valide 4 on obtient :

3. Description d’une autre méthode.

3.1. Code de MJZ

Afin de pouvoir voir d’autre code j’ai utilisé le code d’un camarade pour passer les tests codingame. La solution de MJZ est intérressante et déconcertante de par ses 16 lignes de code. Il recupere d’abord chaque influence dans un tableau 2d grace a une premiere boucle. Puis la boucle suivante appelle la fonction influence pour chaque noeud enfant dans le tableau r avec une longueur initiale de 2. La fonction influence est une fonction récursive qui prend en entrée un noeud p et une longueur c. Cette fonction explore tous les noeuds qui ont un parent égal à p et met à jour la valeur max si la longueur c est supérieure à la valeur actuelle de max.

#include <stdio.h>

int n, r[9999][2], max = 0;

void influence(int p, int c) {
    if(c > max) max = c;
    for(int i = 0; i < n; i++)
        if(r[i][0] == p) influence(r[i][1], c+1);
}

main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d%d", &r[i][0], &r[i][1]);
    for(int i = 0; i < n; i++) influence(r[i][1], 2);
    printf("%d", max);
}

4. Apprentissage

Je n’ai pas réussi à effectuer ce codingame. Cependant j’ai énormément appris sur les listes chainées et les pointeurs. On peut créer n’importe quel type de listes chainée. J’ai compris l’importance de cet objet et qu’il permet de résoudre une multitude de problème. J’ai appris à utilisé ddd pour voir mes listes chainées. J’ai apprécié tenter de résoudre ce codingame.