Вступ
Нас найняли, щоб розробити Noble Knots, найгарячіший новий застосунок для знайомств для знаті! Через століття королівських шлюбів усе стало… заплутаним. Щоб уникнути ситуацій у стилі ой, ми близнюки, наше завдання - побудувати систему, яка перевіряє, наскільки близько споріднені двоє людей.
Noble Knots натхненний ісландським «Islendinga-App», який спирається на базу даних, що простежує всі відомі родинні звʼязки між ісландцями від часів заселення Ісландії. Наш алгоритм визначатиме ступінь спорідненості між двома людьми в королівському родинному дереві.
Чи допоможе наш застосунок коронувати ідеальну пару?
Вказівки
Наше завдання - визначити ступінь віддаленості між двома особами в сімейному дереві.
Це нагадує відому з попкультури ідею, що між будь-яким голлівудським актором і Kevin Bacon не більше ніж шість ступенів віддаленості.
- На вхід буде подано всі імена батьків та їхніх дітей.
- Кожне імʼя унікальне. Дитина може мати одного або двох батьків.
- Ступінь віддаленості визначається як найкоротша кількість звʼязків від однієї особи до іншої.
- Якщо дві особи не повʼязані між собою, поверніть значення, яке означає «no known relationship».
Конкретну реалізацію дивіться в тестових випадках.
Приклад
Розглянемо таке сімейне дерево:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Ступінь віддаленості між Tariq та Uma дорівнює 2 (Tariq → Isla → Uma).
Між Isla та Kevin немає відомого звʼязку, оскільки в наведених даних немає зʼєднання.
Ступінь віддаленості між Uma та Isla дорівнює 1.
Isla та Tariq - рідні брат і сестра, і ступінь віддаленості між ними дорівнює 1.
Так само ця реалізація повідомила б про ступінь віддаленості 2 від нас до брата нашого батька.
Підказки
Показати підказки
FamilyTree.(family_tree) у заготовці розгортає номінальний тип і дає нам базовий Dict(Str, List(Str)).
Dict.to_list подає свої записи як кортежі (parent, children).
Set(Str) допоможе не повертатися до вже пройдених людей, коли ми досліджуємо звʼязки.
