Einführung
Du hast den Auftrag, Noble Knots zu entwickeln, die angesagteste neue Dating-App für den Adel! Nach Jahrhunderten königlicher Heiratspolitik ist die Sache … kompliziert geworden. Um Hoppla-wir-sind-Zwillinge-Situationen zu vermeiden, sollst du ein System bauen, das prüft, wie eng zwei Personen miteinander verwandt sind.
Noble Knots ist von Islands „Islendinga-App" inspiriert, hinter der eine Datenbank steht, die alle bekannten Familienverbindungen zwischen Isländern seit der Besiedlung Islands nachzeichnet. Dein Algorithmus bestimmt den Grad der Trennung zwischen zwei Personen im königlichen Stammbaum.
Wird deine App dazu beitragen, die perfekte Partie zu krönen?
Anleitung
Deine Aufgabe ist es, den Grad der Trennung zwischen zwei Personen in einem Familienstammbaum zu bestimmen.
Das ist der Popkultur-Idee ähnlich, dass jeder Hollywood-Schauspieler innerhalb von sechs Graden von Kevin Bacon entfernt ist.
- Du erhältst eine Eingabe mit allen Namen der Eltern und ihren Kindern.
- Jeder Name ist eindeutig, ein Kind kann ein oder zwei Elternteile haben.
- Der Grad der Trennung ist definiert als die kürzeste Anzahl von Verbindungen von einer Person zu einer anderen.
- Wenn zwei Personen nicht verbunden sind, gib einen Wert zurück, der für „keine bekannte Beziehung“ steht.
Schau dir für die tatsächliche Umsetzung die Testfälle an.
Beispiel
Gegeben ist der folgende Familienstammbaum:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Der Grad der Trennung zwischen Tariq und Uma ist 2 (Tariq → Isla → Uma).
Zwischen Isla und Kevin gibt es keine bekannte Beziehung, da es in den gegebenen Daten keine Verbindung gibt.
Der Grad der Trennung zwischen Uma und Isla ist 1.
Isla und Tariq sind Geschwister und haben einen Grad der Trennung von 1.
Ebenso würde diese Umsetzung einen Grad der Trennung von 2 von dir zum Bruder deines Vaters melden.
