• Python
  • 07. Armazenamento de múltiplos dados em listas

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:
    [[1, 5], [7, 2], [15, 35]]
    
  • Saída:
    [[1, 5], [7, 2], [15, 35]]
    

Exemplo 2:

  • Entrada:
    [[7, 2], [10, 3], [20, 12], [12, 28], [8, 14], [10, 3], [25, 3], [32, 8]]
    
  • Saída:
    [[7, 2], [10, 3], [25, 3], [32, 8]]
    

Exemplo 3:

  • Entrada:
    [[7, 2], [10, 3], [20, 12], [10, 3], [10, 3], [25, 3], [32, 8], [25, 3], [32, 8]]
    
  • Saída:
    [[7, 2], [10, 3], [25, 3], [32, 8]]
    

Dica 1

Dica: Pegue um papel, rascunhe os caminhos e os resultados esperados