Rapport sur “Des nains sur des épaules de géant”
Table of Contents
1. Présentation du problème
“Des nains sur des épaules de géant” est un problème du site codingame, le principe est le suivant:
On nous donne en entrées deux valeurs “x y” cela se traduit par “x influence y”, et cela répeter n fois. y peut influencer quelqu’un d’autre…, cela forme des chemins de ce type:
Le but de l’exercice est d’analyser tout les chemins possible et de renvoyer la longueur de chemins la plus grande
2. méthode de résolution
2.1. détail algorithmique
2.2. morceau de code
on crée d’abord les deux structures stmaillon et stchemin avec un entier valeur ainsi qu’un pointeur sur précédent et un sur suivant pour la structure de maillon, et un pointeur sur debut et un sur fin ,ainsi qu’un entier taille pour la structure stchemin
typedef struct st_maillon{ int valeur; struct st_maillon * precedent; struct st_maillon * suivant; }st_maillon; typedef struct st_chemin{ st_maillon * debut; st_maillon * fin; int taille; }st_chemin;
on cree ensuite la fonction ajoute maillon fin qui, comme son nom l’indique, ajoute un maillon a la fin de la liste chainée, elle prend en argument un chemin ainsi que l’entier qu’on veut ajouter a la fin.
void ajoutemaillonfin(st_chemin * chemin,int entier){ st_maillon * maillon=malloc(sizeof(st_maillon)); maillon->valeur=entier; if(chemin->debut==NULL){ chemin->fin=maillon; chemin->debut=maillon; maillon->suivant=NULL; } else{ chemin->fin->suivant=maillon; maillon->precedent=chemin->fin; chemin->fin=maillon; } chemin->taille+=1; }
on crée ensuite la fonction destruction qui permet principalement de ne pas crée d’erreur mémoire lorsqu’on débuge avec valgrind, elle n’est pas utile pour réussir les tests codingame. Elle prend en argument un chemin, et fait un free sur chaque maillon de chaque chemin créé dans le tableau.
void destruction(st_chemin * chemin) { st_maillon * e=chemin->debut; st_maillon * e2; while (e!=NULL) { e2=e; e=e->suivant; free(e2); } free(chemin); }
on implémente ensuite la fonction creer chemin vide, elle permet d’allouer la mémoire à un chemin et intialise les valeurs de taille a et de début à NULL
st_chemin * creecheminvide(){ st_chemin * chemin=malloc(sizeof(st_chemin)); chemin->debut=NULL; chemin->taille=0; return chemin; }
enfin, l’implémentation du main, la fonction crée un chemin pour chaque entrée et met ces entrées dans le chemin. Elle modifie ensuite chaque chemins pour qu’il soit complet. Puis elle analyse chaque longueur de chemins pour enfin renvoyer la plus grande, elle appelle aussi la fonctions destruction afin de ne pas avoir d’erreur mémoire
int main() { int n,i,k=0; scanf("%d", &n); for (i = 0; i < n; i++) { int x; int y; scanf("%d%d", &x, &y); tab[i]= creecheminvide(); ajoutemaillonfin(tab[i],x); ajoutemaillonfin(tab[i],y); } for(k=0;k<n;k++){ int t=0,p; while(t<n){ if(tab[k]->fin->valeur==tab[t]->debut->valeur){ st_maillon * psmaillon=tab[t]->debut->suivant; for(p=0;p<tab[t]->taille-1;p++){ ajoutemaillonfin(tab[k],psmaillon->valeur); psmaillon=psmaillon->suivant;} } t++; } if(tab[k]->taille>taillemax){ taillemax=tab[k]->taille; } } i=0; while(tab[i]!=NULL){ destruction(tab[i]); i++; } printf("%d\n",taillemax); return 0; }
2.3. le code entier
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> typedef struct st_maillon{ int valeur; struct st_maillon * precedent; struct st_maillon * suivant; }st_maillon; typedef struct st_chemin{ st_maillon * debut; st_maillon * fin; int taille; }st_chemin; void ajoutemaillonfin(st_chemin * chemin,int entier){ st_maillon * maillon=malloc(sizeof(st_maillon)); maillon->valeur=entier; if(chemin->debut==NULL){ chemin->fin=maillon; chemin->debut=maillon; maillon->suivant=NULL; } else{ chemin->fin->suivant=maillon; maillon->precedent=chemin->fin; chemin->fin=maillon; } chemin->taille+=1; } void destruction(st_chemin * chemin) { st_maillon * e=chemin->debut; st_maillon * e2; while (e!=NULL) { e2=e; e=e->suivant; free(e2); } free(chemin); } st_chemin * creecheminvide(){ st_chemin * chemin=malloc(sizeof(st_chemin)); chemin->debut=NULL; chemin->taille=0; return chemin; } st_chemin * tab[10000]={0}; int taillemax=0; int main() { int n,i,k=0; scanf("%d", &n); for (i = 0; i < n; i++) { int x; int y; scanf("%d%d", &x, &y); tab[i]= creecheminvide(); ajoutemaillonfin(tab[i],x); ajoutemaillonfin(tab[i],y); } for(k=0;k<n;k++){ int t=0,p; while(t<n){ if(tab[k]->fin->valeur==tab[t]->debut->valeur){ st_maillon * psmaillon=tab[t]->debut->suivant; for(p=0;p<tab[t]->taille-1;p++){ ajoutemaillonfin(tab[k],psmaillon->valeur); psmaillon=psmaillon->suivant;} } t++; } if(tab[k]->taille>taillemax){ taillemax=tab[k]->taille; } } i=0; while(tab[i]!=NULL){ destruction(tab[i]); i++; } printf("%d\n",taillemax); return 0; }
3. tests
3.1. premier test
avec la chaine de caractère suivante,
3 1 2 1 3 3 4
3
si on compare le résultat au résultat attendu:
Test Passé
si on compare le résultat au résultat attendu:
on voit que le code renvoie bien le bon résultat
Il y a cependant un problème que je n’ai pas su résoudre, lorsque je débuge le programme avec valgrind, et comme on le verra par la suite, le programme renvoie une erreur par nombre d’entrées.
==14269== Memcheck, a memory error detector ==14269== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==14269== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info ==14269== Command: ./geant ==14269== ==14269== Conditional jump or move depends on uninitialised value(s) ==14269== at 0x1092A6: destruction (geant.c:41) ==14269== by 0x109542: main (geant.c:100) ==14269== ==14269== ==14269== HEAP SUMMARY: ==14269== in use at exit: 0 bytes in 0 blocks ==14269== total heap usage: 12 allocs, 12 frees, 8,432 bytes allocated ==14269== ==14269== All heap blocks were freed -- no leaks are possible ==14269== ==14269== Use --track-origins=yes to see where uninitialised values come from ==14269== ERROR SUMMARY: 3 errors from 1 contexts (suppressed: 0 from 0) ==14269== ==14269== 3 errors in context 1 of 1: ==14269== Conditional jump or move depends on uninitialised value(s) ==14269== at 0x1092A6: destruction (geant.c:41) ==14269== by 0x109542: main (geant.c:100) ==14269== ==14269== ERROR SUMMARY: 3 errors from 1 contexts (suppressed: 0 from 0)
3.2. deuxième test
on peut voir qu’avec ces entrées:
8 1 2 1 3 3 4 2 4 2 5 10 11 10 1 10 3
le test passe bien,
4
Test Passé
8 erreurs valgrind
==16269== Memcheck, a memory error detector ==16269== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==16269== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info ==16269== Command: ./geant ==16269== ==16269== Conditional jump or move depends on uninitialised value(s) ==16269== at 0x1092A6: destruction (geant.c:41) ==16269== by 0x109542: main (geant.c:100) ==16269== ==16269== ==16269== HEAP SUMMARY: ==16269== in use at exit: 0 bytes in 0 blocks ==16269== total heap usage: 31 allocs, 31 frees, 8,888 bytes allocated ==16269== ==16269== All heap blocks were freed -- no leaks are possible ==16269== ==16269== Use --track-origins=yes to see where uninitialised values come from ==16269== ERROR SUMMARY: 8 errors from 1 contexts (suppressed: 0 from 0) ==16269== ==16269== 8 errors in context 1 of 1: ==16269== Conditional jump or move depends on uninitialised value(s) ==16269== at 0x1092A6: destruction (geant.c:41) ==16269== by 0x109542: main (geant.c:100) ==16269== ==16269== ERROR SUMMARY: 8 errors from 1 contexts (suppressed: 0 from 0)
3.3. trosième test
on peut voir qu’avec ces entrées:
4 2 3 8 9 1 2 6 3
le test passe bien,
3
Test Passé
4 erreurs valgrind
==16279== Memcheck, a memory error detector ==16279== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==16279== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info ==16279== Command: ./geant ==16279== ==16279== Conditional jump or move depends on uninitialised value(s) ==16279== at 0x1092A6: destruction (geant.c:41) ==16279== by 0x109542: main (geant.c:100) ==16279== ==16279== ==16279== HEAP SUMMARY: ==16279== in use at exit: 0 bytes in 0 blocks ==16279== total heap usage: 15 allocs, 15 frees, 8,504 bytes allocated ==16279== ==16279== All heap blocks were freed -- no leaks are possible ==16279== ==16279== Use --track-origins=yes to see where uninitialised values come from ==16279== ERROR SUMMARY: 4 errors from 1 contexts (suppressed: 0 from 0) ==16279== ==16279== 4 errors in context 1 of 1: ==16279== Conditional jump or move depends on uninitialised value(s) ==16279== at 0x1092A6: destruction (geant.c:41) ==16279== by 0x109542: main (geant.c:100) ==16279== ==16279== ERROR SUMMARY: 4 errors from 1 contexts (suppressed: 0 from 0)
3.4. deuxième test
on peut voir qu’avec ces entrées:
9 7 2 8 9 1 6 6 9 1 7 1 2 3 9 2 3 6 3
le test passe bien,
5
Test Passé
malheureusement toujours ces erreurs valgrind.
==16289== Memcheck, a memory error detector ==16289== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==16289== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info ==16289== Command: ./geant ==16289== ==16289== Conditional jump or move depends on uninitialised value(s) ==16289== at 0x1092A6: destruction (geant.c:41) ==16289== by 0x109542: main (geant.c:100) ==16289== ==16289== ==16289== HEAP SUMMARY: ==16289== in use at exit: 0 bytes in 0 blocks ==16289== total heap usage: 37 allocs, 37 frees, 9,032 bytes allocated ==16289== ==16289== All heap blocks were freed -- no leaks are possible ==16289== ==16289== Use --track-origins=yes to see where uninitialised values come from ==16289== ERROR SUMMARY: 9 errors from 1 contexts (suppressed: 0 from 0) ==16289== ==16289== 9 errors in context 1 of 1: ==16289== Conditional jump or move depends on uninitialised value(s) ==16289== at 0x1092A6: destruction (geant.c:41) ==16289== by 0x109542: main (geant.c:100) ==16289== ==16289== ERROR SUMMARY: 9 errors from 1 contexts (suppressed: 0 from 0)
4. solution de la communauté
J’ai choisi de présenter la solution d’Alain-Delpuch qui utilise une solution assez simple et facile à comprendre
#include <stdlib.h> #include <stdio.h> #include <string.h> // ------------------------------------------------------------------------- typedef struct { int person; int next; } list; int persons[10000]; int depth[10000]; int freeIndex = 1; list L[10000]; // ------------------------------------------------------------------------- int max(int a, int b) { return a>b?a:b; } // ------------------------------------------------------------------------- int deep(int x) { if (depth[x] == 0) { int maxDepth = 0; for (int i = persons[x] ; i ; i = L[i].next) maxDepth = max( maxDepth, deep(L[i].person)); depth[x] = maxDepth+1; } return depth[x]; } // ------------------------------------------------------------------------- int main() { int N=0; // biggest person number int n; // the number of relationships of influence scanf("%d", &n); for (int i = 0; i < n; i++) { int x,y; // a relationship of influence between two people (x influences y) scanf("%d%d", &x, &y); N = max(N,x); // add a relation 'y' to person 'x' int next = persons[x]; persons[x] = freeIndex; L[freeIndex].person = y; L[freeIndex++].next = next; } int answer = 0; for (int x = 0 ; x <= N ; x++) answer = max(answer,deep(x)); printf("%d\n",answer); // The number of people involved in the longest succession of influences }
Il initialise tout d’abord sa structure qui contient 2 entiers, “person” et “next”, il initialise ensuite la fonction max qui renvoie la plus grande valeur parmi 2 valeurs données. Il définie ensuite sa fonction deep, c’est une fonction récursive qui revnoie la longueur de chaque tableau grace a la fonction max. Puis dans son main, il récupère d’abord les entrées et les ranges correctement dans son tableau, puis il compare chaque longueur de chemins et renvoie la plus grande.
5. conclusion
vous pouvez retrouver ce rapport sur ma page personelle