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]

1 2	data Direccion = N \| S \| E \| O deriving (Show, Eq) type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

1	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 [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

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 [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]

[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
--    (2.17 secs, 379049224 bytes)
--    
--    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)

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)

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

5 Comentarios

reducido :: Camino -> Camino
reducido = until esReducido reduce
  where reduce (x:y:xs) | x /= opuesto y = x : reducido (y:xs)
                        | otherwise = reducido xs
        reduce ds = ds
        esReducido (x:y:xs) = x /= opuesto y && esReducido (y:xs)
        esReducido _ = True

opuesto :: Direccion -> Direccion
opuesto N = S
opuesto S = N
opuesto E = O
opuesto O = E

reducido = until esReducido reduce

where reduce (x:y:xs) | x /= opuesto y = x : reducido (y:xs)

| otherwise = reducido xs

reduce ds = ds

esReducido (x:y:xs) = x /= opuesto y && esReducido (y:xs)

esReducido _ = True

opuesto :: Direccion -> Direccion

opuesto N = S

opuesto S = N

opuesto E = O

opuesto O = E

Responder

Cometí un error que solo afectaba a la eficiencia. En reduce, llamaba recursivamente a reducido en vez de a reduce.

reducido' :: Camino -> Camino
reducido' = until esReducido reduce
  where reduce (x:y:xs) | x/= opuesto y = x:reduce (y:xs)
                        | otherwise = reduce xs
        reduce ds = ds
        esReducido (x:y:xs) = x /= opuesto y && esReducido (y:xs)
        esReducido _ = True

reducido' :: Camino -> Camino

reducido' = until esReducido reduce

where reduce (x:y:xs) | x/= opuesto y = x:reduce (y:xs)

| otherwise = reduce xs

En una sola pasada (coste O(n), va desde el final reduciendo hacia el frente)

reducido :: Camino -> Camino
reducido xs = case xs of
               (N:S:x) -> reducido x
               (S:N:x) -> reducido x
               (O:E:x) -> reducido x
               (E:O:x) -> reducido x
               (u:w@(v:_)) -> case reducido w of
                               w'@(v':_) -> if v == v' then u:w' else reducido (u:w')
                               x         -> u:x
               x       -> x

reducido xs = case xs of

(N:S:x) -> reducido x

(S:N:x) -> reducido x

(O:E:x) -> reducido x

(E:O:x) -> reducido x

(u:w@(v:_)) -> case reducido w of

w'@(v':_) -> if v == v' then u:w' else reducido (u:w')

x -> u:x

x -> x

Argh! es cuadrático, la revisión por la derecha recorre toda la cola.
Ahora sí, usando una cremallera (zipper) con coste lineal (es como el anterior pero usando un «hueco móvil»)

reducido :: Camino -> Camino
reducido = reverse . reduce []
    where reduce is ds = case (is, ds) of
                           (N:xs, S:ys) -> reduce xs ys
                           (S:xs, N:ys) -> reduce xs ys
                           (O:xs, E:ys) -> reduce xs ys
                           (E:xs, O:ys) -> reduce xs ys
                           (  xs, y:ys) -> reduce (y:xs) ys
                           (  xs,   []) -> xs

{-
*Main> let xs = take 20000 $ cycle [N,O,N,S,E,N,S,O,S,S]
(0.00 secs, 519052 bytes)
*Main> length xs
20000
(0.00 secs, 1036712 bytes)
*Main> length $ reducido xs
4002
(0.06 secs, 2047884 bytes)
-}

reducido = reverse . reduce []

where reduce is ds = case (is, ds) of

(N:xs, S:ys) -> reduce xs ys

(S:xs, N:ys) -> reduce xs ys

(O:xs, E:ys) -> reduce xs ys

(E:xs, O:ys) -> reduce xs ys

( xs, y:ys) -> reduce (y:xs) ys

( xs, []) -> xs

*Main> let xs = take 20000 $ cycle [N,O,N,S,E,N,S,O,S,S]

(0.00 secs, 519052 bytes)

*Main> length xs

20000

(0.00 secs, 1036712 bytes)

*Main> length $ reducido xs

4002

(0.06 secs, 2047884 bytes)

Con parecido a las otras versiones, esta sería mi versión:

opuesto :: Direccion -> Direccion
opuesto N = S
opuesto S = N
opuesto E = O
opuesto O = E

reducido :: Camino -> Camino
reducido = reverse . reducidoAux []

reducidoAux :: Camino -> Camino -> Camino
reducidoAux acc [] = acc
reducidoAux [] (x:xs) = reducidoAux [x] xs
reducidoAux (c:cs) (x:xs)
    | x == opuesto c = reducidoAux cs xs
    | otherwise = reducidoAux (x:c:cs) xs

reducido = reverse . reducidoAux []

reducidoAux :: Camino -> Camino -> Camino

reducidoAux acc [] = acc

reducidoAux [] (x:xs) = reducidoAux [x] xs

reducidoAux (c:cs) (x:xs)

| x == opuesto c = reducidoAux cs xs

| otherwise = reducidoAux (x:c:cs) xs

Caminos reducidos

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico