Menu Close

Hojas con caminos no decrecientes

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol = N Int [Arbol]
     deriving Show

Por ejemplo, los árboles

         1             1             1  
        /  \          / \           / \ 
       /    \        8   3         8   3
      2      6          /|\       /|\  |
     / \    / \        4 2 6     4 5 6 2
    4   5  5   7

se representan por

   ej1, ej2, ej3 :: Arbol
   ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]]
   ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]]
   ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]]

Definir la función

   hojasEnNoDecreciente :: Arbol -> [Int]

tal que (hojasEnNoDecreciente a) es el conjunto de las hojas de a que se encuentran en alguna rama no decreciente. Por ejemplo,

   hojasEnNoDecreciente ej1  ==  [4,5,7]
   hojasEnNoDecreciente ej2  ==  [4,6,8]
   hojasEnNoDecreciente ej3  ==  []

Soluciones

import Data.List (sort, nub)
 
data Arbol = N Int [Arbol]
  deriving Show
 
ej1, ej2, ej3 :: Arbol
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]]
ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]]
ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]]
 
-- 1ª solución
-- ===========
 
hojasEnNoDecreciente :: Arbol -> [Int]
hojasEnNoDecreciente a =
  sort (nub (map last (ramasNoDecrecientes a)))
 
--    ramasNoDecrecientes ej1  ==  [[1,2,4],[1,2,5],[1,6,7]]
--    ramasNoDecrecientes ej2  ==  [[1,8],[1,3,4],[1,3,6]]
--    ramasNoDecrecientes ej3  ==  []
ramasNoDecrecientes :: Arbol -> [[Int]]
ramasNoDecrecientes a =
  filter esNoDecreciente (ramas a)
 
-- (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
--    λ> ramas ej1
--    [[1,2,4],[1,2,5],[1,6,5],[1,6,7]]
--    λ> ramas ej2
--    [[1,8],[1,3,4],[1,3,2],[1,3,6]]
--    λ> ramas ej3
--    [[1,8,4],[1,8,5],[1,8,6],[1,3,2]]
ramas :: Arbol -> [[Int]]
ramas (N x []) = [[x]]
ramas (N x as) = map (x:) (concatMap ramas as)
 
-- (esNoDecreciente xs) se verifica si la lista xs es no
-- decreciente. Por ejemplo, 
--    esNoDecreciente [1,3,3,5]  ==  True
--    esNoDecreciente [1,3,5,3]  ==  False
esNoDecreciente :: [Int] -> Bool
esNoDecreciente xs =
  and (zipWith (<=) xs (tail xs))
 
-- 2ª solución
-- ===========
 
--    hojasEnNoDecreciente ej1  ==  [4,5,7]
--    hojasEnNoDecreciente ej2  ==  [4,6,8]
--    hojasEnNoDecreciente ej3  ==  []
hojasEnNoDecreciente2 :: Arbol -> [Int]
hojasEnNoDecreciente2 = sort . nub . aux
  where
    aux (N x []) = [x]
    aux (N x as) = concat [aux (N y bs) | (N y bs) <- as, x <= y]

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

2 soluciones de “Hojas con caminos no decrecientes

  1. fercarnav
    data Arbol = N Int [Arbol]
               deriving Show
     
    ej1, ej2, ej3 :: Arbol
    ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]]
    ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]]
    ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]]
     
    hojasEnNoDecreciente :: Arbol -> [Int]
    hojasEnNoDecreciente (N a []) = [a]
    hojasEnNoDecreciente (N a xs) = hojasEnNoDecrecienteAux a (N a xs)
     
    hojasEnNoDecrecienteAux :: Int-> Arbol -> [Int]
    hojasEnNoDecrecienteAux b (N a [])
      | b <= a    = [a]
      | otherwise = []
    hojasEnNoDecrecienteAux c (N a xs)
      | c <= a    = concatMap (hojasEnNoDecrecienteAux a) xs
      | otherwise = []
  2. Enrique Zubiría
    data Arbol = N Int [Arbol]
      deriving Show
     
    hojasEnNoDecreciente :: Arbol -> [Int]
    hojasEnNoDecreciente a = map last (filter noDecreciente (ramas a))
     
    noDecreciente :: [Int] -> Bool
    noDecreciente []       = True
    noDecreciente (x:[])   = True
    noDecreciente (x:y:xs) = x <= y && noDecreciente (y:xs)
     
    ramas :: Arbol -> [[Int]]
    ramas (N x []) = [[x]]
    ramas (N x as) = map (x:) (concatMap ramas as)

Leave a Reply

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