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
|
1 2 |
data Direccion = N | S | E | O deriving (Show, Eq) type Camino = [Direccion] |
Definir la función
|
1 |
reducido :: Camino -> Camino |
tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
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
|
1 2 3 4 |
[N,S,S,E,O,N,O] --> [S,E,O,N,O] --> [S,N,O] --> [O] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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 -- (2.17 secs, 379049224 bytes) |