Relative Distance

Instructions

Your task is to determine the degree of separation between two individuals in a family tree. This is similar to the pop culture idea that every Hollywood actor is within six degrees of Kevin Bacon.

• You will be given an input, with all parent names and their children.
• Each name is unique, a child can have one or two parents.
• The degree of separation is defined as the shortest number of connections from one person to another.
• If two individuals are not connected, return a value that represents "no known relationship." Please see the test cases for the actual implementation.

Example

Given the following family tree:

      ┌──────────┐            ┌──────────┐     ┌───────────┐
      │  Helena  │            │  Erdős   ├─────┤  Shusaku  │
      └───┬───┬──┘            └─────┬────┘     └────┬──────┘
      ┌───┘   └───────┐             └───────┬───────┘
┌─────┴────┐     ┌────┴───┐           ┌─────┴────┐
│   Isla   ├─────┤ Tariq  │           │   Kevin  │
└────┬─────┘     └────┬───┘           └──────────┘
     │                │
┌────┴────┐      ┌────┴───┐
│   Uma   │      │ Morphy │
└─────────┘      └────────┘

The degree of separation between Tariq and Uma is 2 (Tariq → Isla → Uma). There's no known relationship between Isla and Kevin, as there is no connection in the given data. The degree of separation between Uma and Isla is 1.

How this exercise is structured for the Python track

The tests for this exercise expect your solution to be implemented as a RelativeDistance class in Python. If you are unfamiliar with classes in Python, classes and classes in the official Python documentation are good places to start.

RelativeDistance should be initialized (see __init__() for more information) using family_tree, a dictionary where the keys are individuals and values are lists of that individual's children. You will also need to implement a degree_of_separation method which will return the degree of separation between person_a and person_b who are individuals in the passed-in family tree.

You are given a stubbed implementation for the __init__ special method used to create an instance of the RelativeDistance class, as well as a stub of the degree_of_separation method. First, you will need to customize the __init__ with an appropriate attribute on self (the instance) to represent the family_tree data. Then you can add your logic to the degree_of_separation method to calculate the degree of separation between person_a and person_b.

Exception messages

Sometimes it is necessary to raise an exception. When you do this, you should always include a meaningful error message to indicate what the source of the error is. This makes your code more readable and helps significantly with debugging. For situations where you know that the error source will be a certain type, you can choose to raise one of the built in error types, but should still include a meaningful message.

This particular exercise requires that you use the raise statement to "throw" multiple ValueErrors. In the first scenario, you will need to raise a ValueError when either one or both of the people passed to the RelativeDistance.degree_of_separation method are not present in the family tree.

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

If both people are present in the family tree, you will need to raise a ValueError when there is no valid connection between them as defined by the rules.

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

The tests will only pass if you both raise the expected exception type and include the expected message with it. Please check the tests and their expected results carefully, as these instructions are not exhaustive.

---

Source

vaeng