Introducción
¡Te contrataron para desarrollar Noble Knots, la nueva app de citas para la nobleza más popular del momento!
Tras siglos de matrimonios entre la realeza, las cosas se han vuelto… complicadas.
Para evitar cualquier situación del tipo ups, somos gemelos, tu trabajo es construir un sistema que compruebe qué tan emparentadas están dos personas.
Noble Knots está inspirada en la «Islendinga-App» de Islandia, que se apoya en una base de datos que rastrea todos los vínculos familiares conocidos entre islandeses desde la época del asentamiento de Islandia.
Tu algoritmo determinará el grado de separación entre dos personas en el árbol genealógico de la familia real.
¿Ayudará tu app a coronar una pareja perfecta?
Instrucciones
Tu tarea es determinar el grado de separación entre dos personas en un árbol genealógico.
Esto es parecido a la idea de la cultura popular de que todo actor de Hollywood está a seis grados o menos de Kevin Bacon.
- Recibirás un argumento con todos los nombres de los padres y sus hijos.
- Cada nombre es único y un hijo puede tener uno o dos padres.
- El grado de separación se define como el menor número de conexiones entre una persona y otra.
- Si dos personas no están conectadas, devuelve un valor que represente «no known relationship».
Consulta los casos de prueba para ver la implementación concreta.
Ejemplo
Dado el siguiente árbol genealógico:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
El grado de separación entre Tariq y Uma es 2 (Tariq → Isla → Uma).
No hay ninguna relación conocida entre Isla y Kevin, ya que no hay conexión en los datos proporcionados.
El grado de separación entre Uma e Isla es 1.
Isla y Tariq son hermanos y tienen una separación de 1.
De forma similar, esta implementación reportaría una separación de 2 de ti al hermano de tu padre.
