Menu Close

Hojas con caminos no decrecientes

José A. Alonso,

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]

Pensamiento

Para dialogar,
preguntad, primero;
después … escuchad.

Antonio Machado

Inicial
, , , , , , , , , ,

4 soluciones de “Hojas con caminos no decrecientes”

  1. Responder
    frahidzam 
    data Arbol = N Int [Arbol] deriving Show
 
hojasEnNoDecreciente :: Arbol -> [Int]
hojasEnNoDecreciente a = sort [last xs | xs <- ramas a, esCreciente xs]
 
esCreciente :: [Int] -> Bool
esCreciente xs = and [signum (a-b) == -1 | (a,b) <- zip xs (tail xs)]
 
ramas :: Arbol -> [[Int]]
ramas (N x []) = [[x]]
ramas (N x as) = [x : xs | a <- as, xs <- ramas a]
  2. Responder
    adogargon 
    hojasEnNoDecreciente :: Arbol -> [Int]
hojasEnNoDecreciente (N x xs) =
  map last [ ys | ys <- (caminos (N x xs)), nodecreciente ys] 
 
caminos :: Arbol -> [[Int]]
caminos (N x []) = [[x]]
caminos (N x xs) = map (x:) (concatMap caminos xs)
 
nodecreciente :: [Int] -> Bool
nodecreciente [] = True
nodecreciente [x] = True
nodecreciente (x:y:xs) = x <= y && nodecreciente (y:xs)
  3. Responder
    luipromor 
    hojasEnNoDecrecienteA3 :: Arbol -> [Int]
hojasEnNoDecrecienteA3  =
  sort . map last . filter creciente . aux
  where
    creciente (x:y:xs) = x <= y && creciente (y:xs)
    creciente [_]      = True
    aux (N x [])       = [[x]]
    aux (N x xss)      = concat [map (x:) (aux ys) | ys <-  xss]
  4. Responder
    javmarcha1 
    data Arbol = N Int [Arbol]
     deriving Show
 
hojasEnNoDecreciente :: Arbol -> [Int]
hojasEnNoDecreciente (N x xs) = [last xs | xs <- ramas (N x xs), esCreciente xs]
 
ramas :: Arbol -> [[Int]]
ramas (N x []) = [[x]]
ramas (N x xs) = map (x:) (concatMap ramas xs)
 
esCreciente :: [Int] -> Bool
esCreciente [_]      = True
esCreciente (x:y:xs) = x <= y && esCreciente (y:xs)

Escribe tu solución

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