When I saw the exercise I remember of "Travelling Salesman Problem", and I saw that already exist on pip library. Another important point that input data is small and I decided to use Brute Force algorithm.
The solution was developed with python 3.7. First of all the code was saved in github on:
$ git clone git@github.com:gpsanches/rota-viagens.gitTo execute the program follow the steps:
$ virtualenv venv -p python3
$ source venv/bin/activate
$ pip install -r requeriments.txt
$ python find_route.pyTo execute tests:
$ python -m unittest tests.pyUm turista deseja viajar pelo mundo pagando o menor preço possível independentemente do número de conexões necessárias. Vamos construir um programa que facilite ao nosso turista, escolher a melhor rota para sua viagem.
Para isso precisamos inserir as rotas através de um arquivo de entrada.
GRU,BRC,10
BRC,SCL,5
GRU,CDG,75
GRU,SCL,20
GRU,ORL,56
ORL,CDG,5
SCL,ORL,20
Caso desejemos viajar de GRU para CDG existem as seguintes rotas:
- GRU - BRC - SCL - ORL - CDG ao custo de $40
- GRU - ORL - CGD ao custo de $64
- GRU - CDG ao custo de $75
- GRU - SCL - ORL - CDG ao custo de $48
- GRU - BRC - CDG ao custo de $45
O melhor preço é da rota 4 logo, o output da consulta deve ser CDG - SCL - ORL - CDG.
A inicializacao do teste se dará por linha de comando onde o primeiro argumento é o arquivo com a lista de rotas inicial.
$ mysolution input-routes.csvDuas interfaces de consulta devem ser implementadas:
-
Interface de console deverá receber um input com a rota no formato "DE-PARA" e imprimir a melhor rota e seu respectivo valor. Exemplo:
please enter the route: GRU-CGD best route: GRU - BRC - SCL - ORL - CDG > $40 please enter the route: BRC-CDG best route: BRC - ORL > $30
-
Interface Rest A interface Rest deverá suportar:
- Registro de novas rotas. Essas novas rotas devem ser persistidas no arquivo csv utilizado como input(input-routes.csv),
- Consulta de melhor rota entre dois pontos.
Também será necessária a implementação de 2 endpoints Rest, um para registro de rotas e outro para consula de melhor rota.
Para uma melhor fluides da nossa conversa, atente-se aos seguintes pontos:
- Envie apenas o código fonte,
- Estruture sua aplicação seguindo as boas práticas de desenvolvimento,
- Evite o uso de frameworks ou bibliotecas externas à linguagem. Utilize apenas o que for necessário para a exposição do serviço,
- Implemente testes unitários seguindo as boas praticas de mercado,
- Documentação
Em um arquivo Texto ou Markdown descreva:
- Como executar a aplicação,
- Estrutura dos arquivos/pacotes,
- Explique as decisões de design adotadas para a solução,
- Descreva sua APÌ Rest de forma simplificada.