Introducción
¡Te han contratado para desarrollar Noble Knots, la nueva aplicación de citas para la nobleza que está causando furor!
Tras siglos de matrimonios entre familias reales, las cosas se han vuelto… complicadas.
Para evitar cualquier situación del tipo vaya, resulta que somos gemelos, tu trabajo consiste en construir un sistema que compruebe el grado de parentesco entre dos personas.
Noble Knots se inspira en la «Islendinga-App» islandesa, que se apoya en una base de datos que rastrea todos los vínculos familiares conocidos entre islandeses desde la época de la colonización de Islandia.
Tu algoritmo determinará el grado de separación entre dos personas del árbol genealógico de la realeza.
¿Ayudará tu aplicación a coronar a la pareja perfecta?
Instrucciones
Tu tarea consiste en determinar el grado de separación entre dos personas de un árbol genealógico.
Es parecido a la idea popular de que cualquier actor de Hollywood está a menos de seis grados de Kevin Bacon.
- Recibirás una entrada con los nombres de todos los padres y sus hijos.
- Cada nombre es único; un hijo puede tener uno o dos padres.
- El grado de separación se define como el menor número de conexiones de una persona a otra.
- Si dos personas no están conectadas, devuelve un valor que represente «ninguna relación conocida».
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 existe 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.
Del mismo modo, esta implementación indicaría una separación de 2 entre tú y el hermano de tu padre.
