Introduzione
Ti hanno assunto per sviluppare Noble Knots, la nuovissima app di incontri per la nobiltà più in voga del momento!
Con secoli di matrimoni tra consanguinei nelle famiglie reali, le cose si sono fatte… complicate.
Per evitare qualsiasi situazione ops-siamo-gemelli, il tuo compito è costruire un sistema che verifichi quanto strettamente due persone sono imparentate.
Noble Knots si ispira a «Islendinga-App», l'app islandese supportata da un database che traccia tutte le connessioni familiari note tra gli islandesi a partire dall'epoca del popolamento dell'Islanda.
L'algoritmo determinerà il grado di separazione tra due persone nell'albero genealogico della famiglia reale.
Riuscirà l'app a incoronare l'abbinamento perfetto?
Istruzioni
Il tuo compito è determinare il grado di separazione tra due individui in un albero genealogico.
È simile all'idea della cultura pop secondo cui ogni attore di Hollywood è entro sei gradi di separazione da Kevin Bacon.
- Riceverai un input con tutti i nomi dei genitori e i loro figli.
- Ogni nome è unico; un figlio può avere uno o due genitori.
- Il grado di separazione è definito come il numero più breve di connessioni da una persona all'altra.
- Se due individui non sono connessi, restituisci un valore che rappresenta «no known relationship».
Per l'implementazione effettiva, dai un'occhiata ai casi di test.
Esempio
Dato il seguente albero genealogico:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Il grado di separazione tra Tariq e Uma è 2 (Tariq → Isla → Uma).
Non esiste alcuna relazione nota tra Isla e Kevin, poiché non c'è alcuna connessione nei dati forniti.
Il grado di separazione tra Uma e Isla è 1.
Isla e Tariq sono fratelli e hanno una separazione di 1.
Allo stesso modo, questa implementazione riporterebbe una separazione di 2 da te al fratello di tuo padre.
