Εισαγωγή
Σε προσέλαβαν για να αναπτύξεις το Noble Knots, τη νέα, πιο καυτή εφαρμογή γνωριμιών για ευγενείς! Έπειτα από αιώνες βασιλικών επιγαμιών, τα πράγματα έχουν γίνει… περίπλοκα.
Για να αποφύγεις καταστάσεις του τύπου ωχ-είμαστε-δίδυμα, η δουλειά σου είναι να φτιάξεις ένα σύστημα που ελέγχει πόσο στενά συγγενεύουν δύο άτομα.
Το Noble Knots είναι εμπνευσμένο από το ισλανδικό "Islendinga-App", το οποίο στηρίζεται σε μια βάση δεδομένων που καταγράφει όλες τις γνωστές οικογενειακές σχέσεις μεταξύ Ισλανδών, από την εποχή του εποικισμού της Ισλανδίας.
Ο αλγόριθμός σου θα προσδιορίζει τον βαθμό διαχωρισμού ανάμεσα σε δύο άτομα στο βασιλικό οικογενειακό δέντρο.
Θα βοηθήσει η εφαρμογή σου να στέψεις το ιδανικό ταίρι;
Οδηγίες
Η αποστολή σου είναι να προσδιορίσεις τον βαθμό διαχωρισμού ανάμεσα σε δύο άτομα σε ένα οικογενειακό δέντρο.
Αυτό μοιάζει με τη δημοφιλή ιδέα ότι κάθε ηθοποιός του Χόλιγουντ βρίσκεται μέσα σε έξι βαθμούς από τον Kevin Bacon.
- Θα σου δοθεί μια είσοδος, με όλα τα ονόματα των γονέων και τα παιδιά τους.
- Κάθε όνομα είναι μοναδικό, ένα παιδί μπορεί να έχει έναν ή δύο γονείς.
- Ο βαθμός διαχωρισμού ορίζεται ως ο μικρότερος αριθμός συνδέσεων από ένα άτομο σε ένα άλλο.
- Αν δύο άτομα δεν συνδέονται, επίστρεψε μια τιμή που αντιπροσωπεύει "καμία γνωστή σχέση".
Ρίξε μια ματιά στις περιπτώσεις δοκιμών για την πραγματική υλοποίηση.
Παράδειγμα
Δεδομένου του παρακάτω οικογενειακού δέντρου:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Ο βαθμός διαχωρισμού ανάμεσα στον Tariq και την Uma είναι 2 (Tariq → Isla → Uma).
Δεν υπάρχει γνωστή σχέση ανάμεσα στην Isla και τον Kevin, καθώς δεν υπάρχει σύνδεση στα δεδομένα που δίνονται.
Ο βαθμός διαχωρισμού ανάμεσα στην Uma και την Isla είναι 1.
Η Isla και ο Tariq είναι αδέρφια και έχουν βαθμό διαχωρισμού 1.
Παρομοίως, αυτή η υλοποίηση θα ανέφερε βαθμό διαχωρισμού 2 από εσένα προς τον αδερφό του πατέρα σου.
