Limpa Caminho para Robô Entregador#
2022.2: Avaliação Intermediário Design de Software
Certa startup deseja implementar um sistema de entregas por robôs autônomos. Parte do sistema autônomo envolve o planejamento de rotas. Uma rota é composta por uma lista de coordenadas 2D (\(x\) e \(y\) para cada ponto, nesta ordem) que determinam os pontos no espaço que devem ser percorridos pelo robô, de modo que vá do ponto inicial (restaurante, por exemplo) até o ponto final (destino da entrega, casa do cliente, por exemplo).
Sua função deve chamar limpa_caminho
Veja um exemplo:
Entretanto, o planejamento de rotas está com um problema: por vezes, ele cria passos desnecessários, com pontos a serem percorridos que poderiam ser evitados.
Veja um exemplo: nele, a partir do ponto [10, 3]
o robô irá desnecessariamente para os pontos [20, 12]
, [12, 28]
, [8, 14]
até finalmente voltar para o ponto [10, 3]
.
O caminho apresentado anteriormente poderia ser simplificado, removendo passos desnecessários:
Então, você deve criar uma função que recebe uma lista de passos e devolve o caminho limpo, sem passos desnecessários.
A entrada será uma lista onde cada item da lista é uma sub-lista de duas posições que representam um ponto (coordenadas \(x\) e \(y\), nesta ordem).
OBS:
- Considere como passos desnecessários os sub-caminhos que partem de um ponto e voltam para o mesmo ponto de partida
- As coordenadas poderão ser tanto negativas quanto positivas e sempre serão numéricas (confie, não precisa validar)
- A ordem dos pontos não deve ser alterada entre a entrada e saída
Exemplo 1:
- Entrada:
- Saída:
Exemplo 2:
- Entrada:
- Saída:
Exemplo 3:
- Entrada:
- Saída:
Dica 1
Dica: Pegue um papel, rascunhe os caminhos e os resultados esperados