Caminos reducidos
Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].
Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.
En Haskell, las direcciones y los caminos se pueden definir por
data Direccion = N | S | E | O deriving (Show, Eq) type Camino = [Direccion]
Definir la función
reducido :: Camino -> Camino
tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,
reducido [] == [] reducido [N] == [N] reducido [N,O] == [N,O] reducido [N,O,E] == [N] reducido [N,O,E,S] == [] reducido [N,O,S,E] == [N,O,S,E] reducido [S,S,S,N,N,N] == [] reducido [N,S,S,E,O,N] == [] reducido [N,S,S,E,O,N,O] == [O] reducido (take (10^7) (cycle [N,E,O,S])) == []
Nótese que en el penúltimo ejemplo las reducciones son
[N,S,S,E,O,N,O] --> [S,E,O,N,O] --> [S,N,O] --> [O]
Soluciones
data Direccion = N | S | E | O deriving (Show, Eq) type Camino = [Direccion] -- 1ª solución (por recursión): reducido1 :: Camino -> Camino reducido1 [] = [] reducido1 (d:ds) | null ds' = [d] | d == opuesta (head ds') = tail ds' | otherwise = d:ds' where ds' = reducido1 ds opuesta :: Direccion -> Direccion opuesta N = S opuesta S = N opuesta E = O opuesta O = E -- 2ª solución (por plegado) reducido2 :: Camino -> Camino reducido2 = foldr aux [] where aux N (S:xs) = xs aux S (N:xs) = xs aux E (O:xs) = xs aux O (E:xs) = xs aux x xs = x:xs -- 3ª solución reducido3 :: Camino -> Camino reducido3 [] = [] reducido3 (N:S:ds) = reducido3 ds reducido3 (S:N:ds) = reducido3 ds reducido3 (E:O:ds) = reducido3 ds reducido3 (O:E:ds) = reducido3 ds reducido3 (d:ds) | null ds' = [d] | d == opuesta (head ds') = tail ds' | otherwise = d:ds' where ds' = reducido3 ds -- 4ª solución reducido4 :: Camino -> Camino reducido4 ds = reverse (aux ([],ds)) where aux (N:xs, S:ys) = aux (xs,ys) aux (S:xs, N:ys) = aux (xs,ys) aux (E:xs, O:ys) = aux (xs,ys) aux (O:xs, E:ys) = aux (xs,ys) aux ( xs, y:ys) = aux (y:xs,ys) aux ( xs, []) = xs -- Comparación de eficiencia -- ghci> reducido1 (take (10^6) (cycle [N,E,O,S])) -- [] -- (3.87 secs, 460160736 bytes) -- ghci> reducido2 (take (10^6) (cycle [N,E,O,S])) -- [] -- (1.16 secs, 216582880 bytes) -- ghci> reducido3 (take (10^6) (cycle [N,E,O,S])) -- [] -- (0.58 secs, 98561872 bytes) -- ghci> reducido4 (take (10^6) (cycle [N,E,O,S])) -- [] -- (0.64 secs, 176154640 bytes) -- -- ghci> reducido3 (take (10^7) (cycle [N,E,O,S])) -- [] -- (5.43 secs, 962694784 bytes) -- ghci> reducido4 (take (10^7) (cycle [N,E,O,S])) -- [] -- (9.29 secs, 1722601528 bytes) -- -- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S]) -- 400002 -- (4.52 secs, 547004960 bytes) -- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S]) -- 400002 -- -- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S) -- [] -- (7.35 secs, 537797096 bytes) -- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S) -- [] -- (2.30 secs, 244553404 bytes) -- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S) -- [] -- (8.08 secs, 545043608 bytes) -- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S) -- [] -- (1.96 secs, 205552240 bytes)