Na ficção científica, a viagem entre diferentes universos, é feita através de portais ou buracos de minhocas que conectam mundos diferentes ou até mesmo dimensões diferentes.
Imagine que você é um físico renomado que descobriu “buracos de minhocas” (rotas) que permitem o deslocamento entre universos. De acordo com sua descoberta, Todas as rotas são unidirecionais, ou seja, uma rota do universo A para o universo B não implica existência de uma rota do universo B para o universo A.
Mesmo quando existam rotas nos dois sentidos, elas são distintas e não possuem necessariamente a mesma distância (medidas em unidades de espaço-tempo).
O objetivo deste desafio é ajudar futuros viajantes a navegar entre os universos gastando a menor quantidade de espaço-tempo possível. Seu software deverá ser capaz de calcular o custo de deslocamento entre rotas, os números diferentes de rotas entre universos e as rotas mais econômicas.
Os universos e as rotas correspondem respectivamente aos vértices e arestas ponderadas do grafo abaixo:
Seu código deverá resolver os seguintes problemas:
- A distância de A a C passando por B?
- A distância entre A e D?
- A distância de A a C passando por D?
- O número de rotas saindo de C e voltando a C com no máximo 3 paradas?
- O número de rotas entre A e C com no máximo 4 paradas?
- A menor rota (em espaço-tempo) entre A e C?
- A menor rota (em espaço-tempo) saindo de B e voltando a B?
- O número de diferentes rotas saindo de C e voltando a C com distância máxima de 300 unidades de espaço-tempo?
A forma de entrada e saída dos dados fica a sua escolha.
Pedimos que você leia atentamente as instruções abaixo e crie uma solução de código usando Java, JavaScript, Ruby, ou Pyhton.
- Faça a cópia do repositório (fork), desenvolva e submeta uma solicitação de mudança (pull request) no branch master.
- Em caso de dúvidas basta abrir uma issue com sua pergunta (aqui mesmo no github) que nossa equipe irá respondê-lo assim que possível.
- Você não poderá usar bibliotecas externas ou ferramentas resolver o problema das rotas.
- Não será permitido o uso de bancos de dados orientedos a grafos.
- Avaliaremos uma variedade de aspectos, como design da solução, orientação a objeto, complexidade do código e a existência de testes unitários.
- Esperamos que você encaminhe um código que acredite ter qualidade, que possa ser executado e evoluído.
- Caso deseje evoluir a ideia seguindo essa base, fique à vontade: por exemplo, adaptar as entradas e saídas para ser um serviço web, criar uma interface gráfica, etc.
- Envie as instruções para execução do código
- De preferência, utilize um ferramenta como gradle, maven, npm ou yarn para realizar as tarefas necessárias de build.