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.
Les tests de cet exercice attendent que ta solution soit implémentée en Python sous la forme d'une class RelativeDistance.
Si tu ne connais pas les classes en Python, classes et les classes dans la documentation officielle de Python sont de bons points de départ.
RelativeDistance doit être initialisée (voir __init__() pour plus d'informations) avec family_tree, un dictionnaire dans lequel les keys sont des individus et les values des listes contenant les enfants de cet individu.
Tu devras aussi implémenter une méthode degree_of_separation qui renvoie le degré de séparation entre person_a et person_b, deux individus de l'arbre familial fourni.
On te fournit une implémentation ébauchée de la méthode spéciale __init__ qui sert à créer une instance de la classe RelativeDistance, ainsi qu'une ébauche de la méthode degree_of_separation.
Tout d'abord, tu devras personnaliser __init__ en ajoutant un attribut approprié sur self (l'instance) pour représenter les données de family_tree.
Ensuite, tu pourras ajouter ta logique à la méthode degree_of_separation pour calculer le degré de séparation entre person_a et person_b.
Messages d'exception
Il est parfois nécessaire de lever une exception.
Dans ce cas, tu dois toujours inclure un message d'erreur explicite pour indiquer l'origine de l'erreur.
Cela rend le code plus lisible et facilite grandement le débogage.
Lorsque tu sais que l'origine de l'erreur sera d'un certain type, tu peux choisir de lever l'un des types d'erreur prédéfinis, mais tu dois tout de même inclure un message explicite.
Cet exercice demande d'utiliser l'instruction raise pour « lever » plusieurs ValueError.
Dans le premier cas, tu devras lever une ValueError quand l'une des deux personnes passées à la méthode RelativeDistance.degree_of_separation, voire les deux, ne figure pas dans l'arbre familial.
# Example when Person A is not in the tree.
raise ValueError("Person A not in family tree.")
Si les deux personnes sont présentes dans l'arbre familial, tu devras lever une ValueError quand il n'existe aucune connexion valide entre elles, au sens des règles.
# Example when there are no valid connections.
raise ValueError("No connection between person A and person B.")
Les tests ne passeront que si tu raise le bon type d'exception et que tu y joins le message attendu.
Vérifie attentivement les tests et leurs résultats attendus, car ces instructions ne sont pas exhaustives.
