Menu Close

Caminos reducidos

José A. Alonso,

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)
Medio
, , , ,

4 soluciones de “Caminos reducidos”

  1. Responder
    pabserpoz 
    data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]
 
reducido :: Camino -> Camino
reducido xs
 | reducir xs /= xs = reducido (reducir xs)
 | otherwise = xs
 
reducir :: Camino -> Camino
reducir [] = []
reducir [x] = [x]
reducir (x:y:xs)
  | (x==N && y ==S) || (x==S && y== N) || (x==E && y ==O) || (x==O && y== E) = reducir xs
  | otherwise = x : reducir (y:xs)
  2. Responder
    rebgongor 
    data Direccion = N | S | E | O deriving (Show, Eq)
 
type Camino = [Direccion]
 
reducido :: Camino -> Camino
reducido [] = []
reducido (d:ds) | xs == [] = [d]
                | d == dOpuesta (head xs) = tail xs
                | otherwise = d:xs
                  where xs = reducido ds
                        dOpuesta N = S
                        dOpuesta S = N
                        dOpuesta E = O
                        dOpuesta O = E
  3. Responder
    Enrique Zubiría 
    data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]
 
reducido :: Camino -> Camino
reducido xs = reducidoAux xs []
  where reducidoAux []       ys = ys
        reducidoAux (x:[])   ys = ys ++ [x]
        reducidoAux (y:x:xs) ys
          | ((x == E && y == O) || (x == O && y == E)) && null ys = reducidoAux xs []
          | ((x == S && y == N) || (x == N && y == S)) && null ys = reducidoAux xs []
          |  (x == E && y == O) || (x == O && y == E)             = reducidoAux (last ys : xs) (init ys)
          |  (x == S && y == N) || (x == N && y == S)             = reducidoAux (last ys : xs) (init ys)
          | otherwise = reducidoAux (x:xs) (ys ++ [y])
  4. Responder
    rebgongor 
    data Direccion = N | S | E | O deriving (Show, Eq)
 
type Camino = [Direccion]
 
reducido :: Camino -> Camino
reducido = foldr reducir []
  where reducir N (S:xs) = xs
        reducir S (N:xs) = xs
        reducir O (E:xs) = xs
        reducir E (O:xs) = xs
        reducir x xs = x:xs

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.