Nodos con máxima suma de hijos

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

   data Arbol a = N a [Arbol a]
                  deriving Show

1 2	data Arbol a = N a [Arbol a] deriving Show

Por ejemplo, los árboles

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

1 3

/ \ /|\

2 3 / | \

| 5 4 7

4 | /|\

6 2 8 6

se representan por

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

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [], N 3 [N 4 []]]

ej2 = N 3 [N 5 [N 6 []],

N 4 [],

N 7 [N 2 [], N 8 [], N 6 []]]

Definir la función

   nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

1	nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

tal que (nodosSumaMaxima a) es la lista de los nodos del árbol a cuyos hijos tienen máxima suma. Por ejemplo,

   nodosSumaMaxima ej1  ==  [1]
   nodosSumaMaxima ej2  ==  [7,3]

1 2	nodosSumaMaxima ej1 == [1] nodosSumaMaxima ej2 == [7,3]

Soluciones

import Data.List     (groupBy, sort)
import Data.Function (on)

data Arbol a = N a [Arbol a]
  deriving Show

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

-- 1ª solución
-- ===========

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima a =
  [x | (s,x) <- ns, s == m]
  where ns = reverse (sort (nodosSumas a))
        m  = fst (head ns)

-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es la suma de sus hijos. Por ejemplo,  
--    λ> nodosSumas ej1
--    [(5,1),(0,2),(4,3),(0,4)]
--    λ> nodosSumas ej2
--    [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]
nodosSumas :: Num t => Arbol t -> [(t,t)]
nodosSumas (N x []) = [(0,x)]
nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as

-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,
--    raices [ej1,ej2]  ==  [1,3]
raices :: [Arbol t] -> [t]
raices = map raiz

-- (raiz a) es la raíz del árbol a. Por ejemplo,
--    raiz ej1  ==  1
--    raiz ej2  ==  3
raiz :: Arbol t -> t
raiz (N x _) = x

-- 2ª solución
-- ===========

nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima2 a =
  [x | (s,x) <- ns, s == m]
  where ns = sort (nodosOpSumas a)
        m  = fst (head ns)

-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,  
--    λ> nodosOpSumas ej1
--    [(-5,1),(0,2),(-4,3),(0,4)]
--    λ> nodosOpSumas ej2
--    [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]
nodosOpSumas :: Num t => Arbol t -> [(t,t)]
nodosOpSumas (N x []) = [(0,x)]
nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as


-- 3ª solución
-- ===========

nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima3 a =
  [x | (s,x) <- ns, s == m]
  where ns = sort (nodosOpSumas a)
        m  = fst (head ns)

-- 4ª solución
-- ===========

nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima4 a =
  map snd (head (groupBy (\p q -> fst p == fst q)
                         (sort (nodosOpSumas a))))

-- 5ª solución
-- ===========

nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima5 a =
  map snd (head (groupBy ((==) `on` fst)
                         (sort (nodosOpSumas a))))

-- 6ª solución
-- ===========

nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima6 =
  map snd
  . head
  . groupBy ((==) `on` fst)
  . sort
  . nodosOpSumas

import Data.List (groupBy, sort)

import Data.Function (on)

data Arbol a = N a [Arbol a]

deriving Show

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [], N 3 [N 4 []]]

ej2 = N 3 [N 5 [N 6 []],

N 4 [],

N 7 [N 2 [], N 8 [], N 6 []]]

-- 1ª solución

-- ===========

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima a =

[x | (s,x) <- ns, s == m]

where ns = reverse (sort (nodosSumas a))

m = fst (head ns)

-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del

-- árbol x y s es la suma de sus hijos. Por ejemplo,

-- λ> nodosSumas ej1

-- [(5,1),(0,2),(4,3),(0,4)]

-- λ> nodosSumas ej2

-- [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]

nodosSumas :: Num t => Arbol t -> [(t,t)]

nodosSumas (N x []) = [(0,x)]

nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as

-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,

-- raices [ej1,ej2] == [1,3]

raices :: [Arbol t] -> [t]

raices = map raiz

-- (raiz a) es la raíz del árbol a. Por ejemplo,

-- raiz ej1 == 1

-- raiz ej2 == 3

raiz :: Arbol t -> t

raiz (N x _) = x

-- 2ª solución

-- ===========

nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima2 a =

[x | (s,x) <- ns, s == m]

where ns = sort (nodosOpSumas a)

m = fst (head ns)

-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del

-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,

-- λ> nodosOpSumas ej1

-- [(-5,1),(0,2),(-4,3),(0,4)]

-- λ> nodosOpSumas ej2

-- [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]

nodosOpSumas :: Num t => Arbol t -> [(t,t)]

nodosOpSumas (N x []) = [(0,x)]

nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as

-- 3ª solución

-- ===========

nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima3 a =

[x | (s,x) <- ns, s == m]

where ns = sort (nodosOpSumas a)

m = fst (head ns)

-- 4ª solución

-- ===========

nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima4 a =

map snd (head (groupBy (\p q -> fst p == fst q)

(sort (nodosOpSumas a))))

-- 5ª solución

-- ===========

nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima5 a =

map snd (head (groupBy ((==) `on` fst)

(sort (nodosOpSumas a))))

-- 6ª solución

-- ===========

nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima6 =

map snd

. head

. groupBy ((==) `on` fst)

. sort

. nodosOpSumas

5 Comentarios

sumaHijos :: Num a => Arbol a -> a
sumaHijos (N _ xs) = sum (map tomaRaiz xs)

tomaRaiz :: Num a => Arbol a -> a
tomaRaiz (N a _) = a

listaRaicesConSumaHijos :: Num a => Arbol a -> [(a,a)]
listaRaicesConSumaHijos (N a []) = [(a,0)]
listaRaicesConSumaHijos (N a xs) = (a,(sumaHijos (N a xs))):(concatMap listaRaicesConSumaHijos xs)


nodosSumaMaxima a = [x | (x,m)<-y , m==(maximum(map snd y))]
  where y= listaRaicesConSumaHijos a

sumaHijos :: Num a => Arbol a -> a

sumaHijos (N _ xs) = sum (map tomaRaiz xs)

tomaRaiz :: Num a => Arbol a -> a

tomaRaiz (N a _) = a

listaRaicesConSumaHijos :: Num a => Arbol a -> [(a,a)]

listaRaicesConSumaHijos (N a []) = [(a,0)]

listaRaicesConSumaHijos (N a xs) = (a,(sumaHijos (N a xs))):(concatMap listaRaicesConSumaHijos xs)

nodosSumaMaxima a = [x | (x,m)<-y , m==(maximum(map snd y))]

where y= listaRaicesConSumaHijos a

Responder

import Data.List

data Arbol a = N a [Arbol a]
             deriving Show

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima = map snd.aux
  where aux (N a hs) = (aux2.sortBy (flip compare)) (((sum.map (\(N a' hs') -> a')) hs,a):concatMap aux hs)
          where aux2((a,b):(c,d):xs) | a == c    = (a,b) : aux2 ((c,d):xs)
                                     | otherwise = [(a,b)]
                aux2 [(a,b)] = [(a,b)]
                aux2 [] = []

import Data.List

nodosSumaMaxima = map snd.aux

where aux (N a hs) = (aux2.sortBy (flip compare)) (((sum.map (\(N a' hs') -> a')) hs,a):concatMap aux hs)

where aux2((a,b):(c,d):xs) | a == c = (a,b) : aux2 ((c,d):xs)

| otherwise = [(a,b)]

aux2 [(a,b)] = [(a,b)]

aux2 [] = []

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima x = map fst (filter ((==k).snd) cand)
 where k = maximum (map snd cand)
       cand = nodosHijosSum x
       
--(nodosHijosSum x) es la lista de pares (n,m) donde n es el nodo y s la suma de sus hijos
--   nodosHijosSum ej1 == [(1,5),(2,0),(3,4),(4,0)]
--   nodosHijosSum ej2 == [(3,16),(5,6),(6,0),(4,0),(7,16),(2,0),(8,0),(6,0)]
nodosHijosSum (N n arb) = (n,sum [valor x | x <- arb]):(concat[nodosHijosSum x | x <- arb])
  where valor (N n _) = n

nodosSumaMaxima x = map fst (filter ((==k).snd) cand)

where k = maximum (map snd cand)

cand = nodosHijosSum x

--(nodosHijosSum x) es la lista de pares (n,m) donde n es el nodo y s la suma de sus hijos

-- nodosHijosSum ej1 == [(1,5),(2,0),(3,4),(4,0)]

-- nodosHijosSum ej2 == [(3,16),(5,6),(6,0),(4,0),(7,16),(2,0),(8,0),(6,0)]

nodosHijosSum (N n arb) = (n,sum [valor x | x <- arb]):(concat[nodosHijosSum x | x <- arb])

where valor (N n _) = n

data Arbol a = N {rootLabel :: a,
                  subForest :: [Arbol a]}
             deriving Show

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima = snd . head . aux2 . aux
  where aux (N a as) = (sum (map rootLabel as),[a]) : concatMap aux as
        aux2 [] = []
        aux2 [x] = [x]
        aux2 ((x,xs):(y,ys):zs) | x == y    = aux2 ((x,ys++xs):zs)
                                | x >  y    = aux2 ((x,xs):zs)
                                | otherwise = aux2 ((y,ys):zs)

data Arbol a = N {rootLabel :: a,

subForest :: [Arbol a]}

nodosSumaMaxima = snd . head . aux2 . aux

where aux (N a as) = (sum (map rootLabel as),[a]) : concatMap aux as

aux2 [x] = [x]

aux2 ((x,xs):(y,ys):zs) | x == y = aux2 ((x,ys++xs):zs)

| x > y = aux2 ((x,xs):zs)

| otherwise = aux2 ((y,ys):zs)

nodosSumaMaxima a1 = map fst $ filter (\(a,v) -> v == vm) av
  where av = aux a1
        vm = maximum $ map snd av
        aux (N x []) = [(x,0)]
        aux (N x a1) = (x,sumN a1):concatMap aux (a1)
           where sumN a1 = sum [a | (N a a2) <- a1]

nodosSumaMaxima a1 = map fst $ filter (\(a,v) -> v == vm) av

where av = aux a1

vm = maximum $ map snd av

aux (N x []) = [(x,0)]

aux (N x a1) = (x,sumN a1):concatMap aux (a1)

where sumN a1 = sum [a | (N a a2) <- a1]

Nodos con máxima suma de hijos

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