Introduction
On t'a embauché pour développer Noble Knots, la nouvelle application de rencontre pour la noblesse dont tout le monde parle ! Avec des siècles de mariages royaux entre familles, les choses sont devenues… compliquées. Pour éviter les situations oups, on est jumeaux, ton travail consiste à construire un système qui vérifie à quel point deux personnes sont apparentées.
Noble Knots s'inspire de l'« Islendinga-App » islandaise, qui s'appuie sur une base de données retraçant tous les liens familiaux connus entre les Islandais depuis le peuplement de l'Islande.
Ton algorithme déterminera le degré de séparation entre deux individus de l'arbre généalogique royal.
Ton application aidera-t-elle à couronner un match parfait ?
Instructions
Ta tâche consiste à déterminer le degré de séparation entre deux personnes dans un arbre généalogique.
C'est l'équivalent de l'idée, très répandue dans la culture populaire, selon laquelle tout acteur hollywoodien est à moins de six degrés de Kevin Bacon.
- On te donne une entrée qui contient tous les noms des parents et leurs enfants.
- Chaque nom est unique, et un enfant peut avoir un ou deux parents.
- Le degré de séparation est le plus petit nombre de liens entre une personne et une autre.
- Si deux personnes ne sont pas reliées, renvoie une valeur qui représente « aucune relation connue ».
Regarde les cas de test pour connaître la valeur réellement attendue.
Exemple
Voici l'arbre généalogique suivant :
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Le degré de séparation entre Tariq et Uma est 2 (Tariq → Isla → Uma).
Il n'existe aucune relation connue entre Isla et Kevin, car les données fournies ne contiennent aucun lien entre eux.
Le degré de séparation entre Uma et Isla est 1.
Isla et Tariq sont frère et sœur, et leur séparation est de 1.
De même, cette implémentation indiquerait une séparation de 2 entre toi et le frère de ton père.
