Introdução
Foste contratado para desenvolver a Noble Knots, a nova aplicação de encontros mais badalada para a nobreza!
Com séculos de casamentos entre famílias reais, as coisas ficaram… complicadas.
Para evitar qualquer situação do tipo ups-somos-gémeos, a tua tarefa é construir um sistema que verifica o grau de parentesco entre duas pessoas.
A Noble Knots inspira-se na "Islendinga-App" islandesa, que é sustentada por uma base de dados que traça todas as ligações familiares conhecidas entre islandeses desde o povoamento da Islândia.
O teu algoritmo vai determinar o grau de separação entre duas pessoas na árvore genealógica da família real.
Será que a tua aplicação vai ajudar a coroar um par perfeito?
Instruções
A tua tarefa é determinar o grau de separação entre duas pessoas numa árvore genealógica.
Isto é semelhante à ideia da cultura popular de que qualquer ator de Hollywood está a menos de seis graus de Kevin Bacon.
- Recebes uma entrada com os nomes de todos os pais e os respetivos filhos.
- Cada nome é único e uma criança pode ter um ou dois pais.
- O grau de separação é definido como o menor número de ligações entre uma pessoa e outra.
- Se duas pessoas não estiverem ligadas, devolve um valor que represente "nenhuma relação conhecida".
Consulta os casos de teste para veres a implementação concreta.
Exemplo
Dada a seguinte árvore genealógica:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
O grau de separação entre Tariq e Uma é 2 (Tariq → Isla → Uma).
Não existe nenhuma relação conhecida entre Isla e Kevin, uma vez que não há qualquer ligação nos dados fornecidos.
O grau de separação entre Uma e Isla é 1.
Isla e Tariq são irmãos e têm um grau de separação de 1.
Da mesma forma, esta implementação indicaria um grau de separação de 2 entre ti e o irmão do teu pai.
Como este exercício está estruturado para o percurso de Python
Os testes deste exercício esperam que a tua solução seja implementada em Python como uma class RelativeDistance.
Se ainda não conheces as classes em Python, o classes e a classes na documentação oficial do Python são bons pontos de partida.
O RelativeDistance deve ser inicializado (vê o __init__() para mais informações) com family_tree, um dicionário em que as keys são indivíduos e os values são lists com os filhos desse indivíduo.
Também vais precisar de implementar um método degree_of_separation, que devolve o grau de separação entre person_a e person_b, que são indivíduos na árvore genealógica recebida.
É-te dada uma implementação esboçada do método especial __init__, usado para criar uma instância da classe RelativeDistance, assim como um esboço do método degree_of_separation.
Primeiro, vais precisar de personalizar o __init__ com um atributo adequado em self (a instância) para representar os dados de family_tree.
Depois podes acrescentar a tua lógica ao método degree_of_separation para calcular o grau de separação entre person_a e person_b.
Mensagens de exceção
Por vezes é necessário lançar uma exceção.
Quando o fizeres, deves incluir sempre uma mensagem de erro significativa que indique qual é a origem do erro.
Isto torna o teu código mais legível e ajuda imenso no debugging.
Nas situações em que sabes que a origem do erro é de um determinado tipo, podes optar por lançar um dos tipos de erro incorporados, mas deves continuar a incluir uma mensagem significativa.
Este exercício em particular exige que uses a instrução raise para “lançar” vários ValueErrors.
No primeiro cenário, vais precisar de lançar um ValueError quando uma ou ambas as pessoas passadas ao método RelativeDistance.degree_of_separation não estiverem presentes na árvore genealógica.
# Example when Person A is not in the tree.
raise ValueError("Person A not in family tree.")
Se ambas as pessoas estiverem presentes na árvore genealógica, vais precisar de lançar um ValueError quando não existir uma ligação válida entre elas, tal como definido pelas regras.
# Example when there are no valid connections.
raise ValueError("No connection between person A and person B.")
Os testes só passam se usares raise com o tipo de exception esperado e incluíres também a mensagem esperada.
Verifica com atenção os testes e os resultados esperados, porque estas instruções não são exaustivas.
