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.
Come è strutturato questo esercizio per il track Python
I test di questo esercizio si aspettano che la soluzione sia implementata come una class RelativeDistance in Python.
Se non hai familiarità con le class in Python, classes e la sezione classes della documentazione ufficiale di Python sono buoni punti di partenza.
RelativeDistance va inizializzato (per maggiori informazioni, vedi __init__()) usando family_tree, un dizionario in cui le keys sono gli individui ed i values sono list dei figli di quell'individuo.
Dovrai anche implementare un metodo degree_of_separation che restituisce il grado di separazione tra person_a e person_b, che sono individui dell'albero genealogico passato.
Ti viene fornita un'implementazione stub del metodo speciale __init__ usato per creare un'istanza della classe RelativeDistance, insieme a uno stub del metodo degree_of_separation.
Per prima cosa, dovrai personalizzare __init__ con un attributo appropriato su self (l'istanza) per rappresentare i dati di family_tree.
Poi potrai aggiungere la logica al metodo degree_of_separation per calcolare il grado di separazione tra person_a e person_b.
Messaggi di eccezione
A volte è necessario sollevare un'eccezione.
Quando lo fai, dovresti sempre includere un messaggio di errore significativo che indichi qual è la causa dell'errore.
Questo rende il codice più leggibile ed aiuta parecchio nel debug.
Nei casi in cui sai che la causa dell'errore sarà di un certo tipo, puoi scegliere di sollevare uno dei tipi di errore predefiniti, ma dovresti comunque includere un messaggio significativo.
Questo esercizio in particolare richiede che tu usi l'istruzione raise per «lanciare» più ValueError.
Nel primo scenario, dovrai sollevare un ValueError quando una o entrambe le persone passate al metodo RelativeDistance.degree_of_separation non sono presenti nell'albero genealogico.
# Example when Person A is not in the tree.
raise ValueError("Person A not in family tree.")
Se entrambe le persone sono presenti nell'albero genealogico, dovrai sollevare un ValueError quando non esiste una connessione valida tra loro secondo le regole stabilite.
# Example when there are no valid connections.
raise ValueError("No connection between person A and person B.")
I test passeranno solo se usi raise con il tipo di exception atteso ed includi anche il messaggio atteso.
Controlla con attenzione i test e i risultati attesi, perché queste istruzioni non sono esaustive.
