Questão 47: hasLoops
Voltar
Considere o seguinte tipo para representar movimentos de um robot.
data Movimento = Norte | Sul | Este | Oeste deriving Show
Defina a função hasLoops :: (Int,Int) -> [Movimento] -> Bool
que, dada uma posição inicial e uma lista de movimentos (correspondentes a um percurso), verifica se o robot alguma vez volta a passar pela posição inicial ao longo do percurso correspondente. Pode usar a função posicao
definida acima.
Exemplo
> hasLoops (0,0) [Norte, Norte, Este, Sul, Oeste, Sul, Este, Norte, Este]
True
> hasLoops (2,1) [Sul, Este, Sul, Oeste, Norte, Este, Sul]
False
Resolução
data Movimento = Norte | Sul | Este | Oeste deriving Show
posicao :: (Int,Int) -> [Movimento] -> (Int,Int)
posicao p [] = p
posicao (x, y) (Norte:t) = posicao (x, y + 1) t
posicao (x, y) (Sul:t) = posicao (x, y - 1) t
posicao (x, y) (Este:t) = posicao (x + 1, y) t
posicao (x, y) (Oeste:t) = posicao (x - 1, y) t
hasLoops :: (Int,Int) -> [Movimento] -> Bool
hasLoops _ [] = False
hasLoops posi movs = posi == posicao posi movs || hasLoops posi (init movs)
Explicação
A função posicao
calcula a posição final do robot depois de efetuar um conjunto de movimentos.