Відносна відстань

Вказівки

Наше завдання - визначити ступінь віддаленості між двома особами в сімейному дереві. Це нагадує відому з попкультури ідею, що між будь-яким голлівудським актором і 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.

Як цю вправу структуровано для треку Python

Тести цієї вправи вимагають, щоб наше рішення було реалізовано як class із назвою RelativeDistance у Python. Якщо ми ще не знайомі з class у Python, то почати варто з classes і classes в офіційній документації Python.

RelativeDistance слід ініціалізувати (див. __init__() для докладнішої інформації) за допомогою family_tree, словника, у якому keys - це окремі особи, а values - це list-и з дітьми цієї особи. Також нам потрібно буде реалізувати метод degree_of_separation, який повертає ступінь віддаленості між person_a і person_b, особами з переданого родинного дерева.

Нам дано заготовку реалізації спеціального методу __init__, який використовується для створення екземпляра класу raise, а також заготовку методу degree_of_separation. Спершу нам потрібно буде налаштувати __init__ з відповідним атрибутом у self (екземплярі), щоб представити дані family_tree. Потім ми можемо додати свою логіку до методу degree_of_separation, щоб обчислити ступінь віддаленості між person_a і person_b.

Повідомлення про винятки

Іноді виникає потреба порушити виняток. Коли ми це робимо, слід завжди додавати змістовне повідомлення про помилку, яке вказує, у чому джерело помилки. Це робить наш код зрозумілішим і значно допомагає з налагодженням. Якщо ми знаємо, що джерело помилки буде певного типу, ми можемо вибрати один із вбудованих типів помилок, але все одно маємо додати змістовне повідомлення.

Ця конкретна вправа вимагає, щоб ми використали інструкцію raise, щоб «кинути» кілька ValueError. У першому сценарії нам потрібно порушити ValueError, коли одна або обидві особи, передані методу RelativeDistance.degree_of_separation, відсутні в родинному дереві.

# Example when Person A is not in the tree.
raise ValueError("Person A not in family tree.")

Якщо обидві особи присутні в родинному дереві, нам потрібно порушити ValueError, коли між ними немає дійсного звʼязку, як визначено правилами.

# Example when there are no valid connections.
raise ValueError("No connection between person A and person B.")

Тести пройдуть лише тоді, коли ми і порушимо очікуваний тип exception, і додамо до нього очікуване повідомлення. Уважно перегляньте тести та їхні очікувані результати, бо ці вказівки не вичерпні.

---

Джерело

vaeng