Caminos en un árbol binario con suma dada

7 Comentarios

1. Haskell

   caminos :: Arbol -> [[Int]] caminos t = snd (aux t) where aux H = ([],[]) aux (N a x y) = (z,z ++ b ++ c) where z = [a]:[a:xs | xs <- p ++ q] (p,b) = aux x (q,c) = aux y caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma t x = filter p (caminos t) where p xs = x == sum xs

   1 2 3 4 5 6 7 8 9 10 11

   caminos :: Arbol -> [[Int]] caminos t = snd (aux t)   where aux H = ([],[])         aux (N a x y) = (z,z ++ b ++ c)           where z = [a]:[a:xs | xs <- p ++ q]                 (p,b) = aux x                 (q,c) = aux y   caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma t x = filter p (caminos t)   where p xs = x == sum xs

   Responder

2. Haskell

   caminosDesdeRaiz :: Arbol -> [[Int]] caminosDesdeRaiz (N a H H) = [[a]] caminosDesdeRaiz (N a H d) = [[a]] ++ [a: x | x <- caminosDesdeRaiz d] caminosDesdeRaiz (N a i H) = [[a]] ++ [a: x | x <- caminosDesdeRaiz i] caminosDesdeRaiz (N a i d) = [[a]] ++ [a:x | x <- caminosDesdeRaiz i] ++ [a:x | x <- caminosDesdeRaiz d] caminos :: Arbol -> [[Int]] caminos (N a H H) = caminosDesdeRaiz (N a H H) caminos (N a H d) = caminosDesdeRaiz (N a H d) ++ caminos d caminos (N a i H) = caminosDesdeRaiz (N a i H) ++ caminos i caminos (N a i d) = caminosDesdeRaiz (N a i d) ++ caminos i ++ caminos d caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = filter (\x -> sum x == k) (caminos a)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   caminosDesdeRaiz :: Arbol -> [[Int]] caminosDesdeRaiz (N a H H) = [[a]] caminosDesdeRaiz (N a H d) = [[a]] ++ [a: x | x <- caminosDesdeRaiz d] caminosDesdeRaiz (N a i H) = [[a]] ++ [a: x | x <- caminosDesdeRaiz i] caminosDesdeRaiz (N a i d) =      [[a]]   ++ [a:x | x <- caminosDesdeRaiz i]   ++ [a:x | x <- caminosDesdeRaiz d]   caminos :: Arbol -> [[Int]] caminos (N a H H) = caminosDesdeRaiz (N a H H) caminos (N a H d) = caminosDesdeRaiz (N a H d) ++ caminos d caminos (N a i H) = caminosDesdeRaiz (N a i H) ++ caminos i caminos (N a i d) = caminosDesdeRaiz (N a i d) ++ caminos i ++ caminos d   caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = filter (\x -> sum x == k) (caminos a)

   Responder

3. Haskell

   -- El orden de los resultados es diferente al de los ejemplos caminos :: Arbol -> [[Int]] caminos as = map fst (caminosAux as 0) caminosAux :: Arbol -> Int -> [([Int],Int)] caminosAux (H) n = [] caminosAux (N a is ds) n = ([a],n) : concat (map (\(xs,k) -> if n + 1 == k then [(a:xs,n),(xs,k)] else [(xs,k)]) (caminosAux is (n+1) ++ caminosAux ds (n+1))) caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma as k = filter ((k==).sum) (caminos as)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   -- El orden de los resultados es diferente al de los ejemplos   caminos :: Arbol -> [[Int]] caminos as = map fst (caminosAux as 0)   caminosAux :: Arbol -> Int -> [([Int],Int)] caminosAux (H) n = [] caminosAux (N a is ds) n =   ([a],n) : concat (map (\(xs,k) ->                            if n + 1 == k                            then [(a:xs,n),(xs,k)]                            else [(xs,k)]) (caminosAux is (n+1) ++                                            caminosAux ds (n+1)))   caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma as k = filter ((k==).sum) (caminos as)

   Responder

4. Haskell

   ramas :: Arbol -> [[Int]] ramas H = [[]] ramas (N r H d) = map (r:) (ramas d) ramas (N r i H) = map (r:) (ramas i) ramas (N r i d) = map (r:) (ramas i ++ ramas d) caminosDesdeRaiz:: Arbol -> [[Int]] caminosDesdeRaiz = nub . concatMap (tail . inits) . ramas caminos:: Arbol -> [[Int]] caminos H = [] caminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a n = filter ((==n) . sum) (caminos a)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   ramas :: Arbol -> [[Int]] ramas H = [[]] ramas (N r H d) = map (r:) (ramas d) ramas (N r i H) = map (r:) (ramas i) ramas (N r i d) = map (r:) (ramas i ++ ramas d)           caminosDesdeRaiz:: Arbol -> [[Int]] caminosDesdeRaiz = nub . concatMap (tail . inits) . ramas    caminos:: Arbol -> [[Int]] caminos H = [] caminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d   caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a n = filter ((==n) . sum) (caminos a)

   Responder

5. Haskell

   caminos :: Arbol -> [[Int]] caminos H = [] caminos (N a i d) = aux (N a i d) ++ caminos i ++ caminos d where aux H = [] aux (N a i d) = [a] : [a:xs | xs <- aux i] ++ [a:xs | xs <- aux d] caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a x = filtraN x sum (caminos a) filtraN :: Eq b => b -> ([a] -> b) -> [[a]] -> [[a]] filtraN _ _ [] = [] filtraN n p (xs:xss) | p xs == n = xs : filtraN n p xss | otherwise = filtraN n p xss

   1 2 3 4 5 6 7 8 9 10 11 12 13

   caminos :: Arbol -> [[Int]] caminos H         = [] caminos (N a i d) = aux (N a i d) ++ caminos i ++ caminos d         where aux H         = []               aux (N a i d) = [a] : [a:xs | xs <- aux i] ++ [a:xs | xs <- aux d]   caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a x = filtraN x sum (caminos a)   filtraN :: Eq b => b -> ([a] -> b) -> [[a]] -> [[a]] filtraN _ _ []       = [] filtraN n p (xs:xss) | p xs == n = xs : filtraN n p xss                      | otherwise = filtraN n p xss

   Responder

6. Haskell

   caminos :: Arbol -> [[Int]] caminos H = [] caminos a@(N _ i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = filter ((==k).sum) (caminos a) caminosDesdeRaiz :: Arbol -> [[Int]] caminosDesdeRaiz H = [] caminosDesdeRaiz (N n i d) = [n] : map (n:) (caminosDesdeRaiz i ++ caminosDesdeRaiz d)

   1 2 3 4 5 6 7 8 9 10

   caminos :: Arbol -> [[Int]] caminos H = [] caminos a@(N _ i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d    caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = filter ((==k).sum) (caminos a)   caminosDesdeRaiz :: Arbol -> [[Int]] caminosDesdeRaiz H = [] caminosDesdeRaiz (N n i d) = [n] : map (n:) (caminosDesdeRaiz i ++ caminosDesdeRaiz d)

   Responder

7. Haskell

   listasArbol :: Arbol -> [[Int]] listasArbol (H) = [] listasArbol (N a i d) = [[a]] ++ (map (a:) (listasArbol i)) ++ (map (a:) (listasArbol d)) listas :: [[Int]] -> [[Int]] listas xs = xs ++ [drop n ys | ys <- xs, n <- [1..(length ys -1)], length ys >= 2] caminos :: Arbol -> [[Int]] caminos (H) = [] caminos (N a i d) = listas (listasArbol (N a i d)) caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = [xs | xs <- caminos a , sum xs == k]

   1 2 3 4 5 6 7 8 9 10 11 12 13

   listasArbol :: Arbol -> [[Int]] listasArbol (H) = [] listasArbol (N a i d) = [[a]] ++ (map (a:) (listasArbol i)) ++ (map (a:) (listasArbol d))   listas :: [[Int]] -> [[Int]] listas xs = xs ++ [drop n ys | ys <- xs, n <- [1..(length ys -1)], length ys >= 2]   caminos :: Arbol -> [[Int]] caminos (H) = [] caminos (N a i d) = listas (listasArbol (N a i d))   caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = [xs | xs <- caminos a , sum xs == k]

   Responder