Recorrido de árboles en espiral

5 Comentarios

1. Haskell

   data Arbol a = N {rootLabel :: a, subForest :: [Arbol a]} deriving Show espiral :: Arbol a -> [a] espiral = concat . zipWith ($) (cycle [reverse,id]) . levels -- (levels t) es la lista de niveles del árbol t. Por ejemplo, -- levels ej1 == [[1],[2,3],[4,5,6,7]] -- levels ej2 == [[1],[8,3],[4,5,6]] -- levels ej3 == [[1],[8,3],[4,5,6,7]] levels :: Arbol a -> [[a]] levels t = map (map rootLabel) . takeWhile (not . null) . iterate (concatMap subForest) $ [t]

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

   data Arbol a = N {rootLabel :: a,                   subForest :: [Arbol a]}   deriving Show   espiral :: Arbol a -> [a] espiral =   concat . zipWith ($) (cycle [reverse,id]) . levels   -- (levels t) es la lista de niveles del árbol t. Por ejemplo, --    levels ej1  ==  [[1],[2,3],[4,5,6,7]] --    levels ej2  ==  [[1],[8,3],[4,5,6]] --    levels ej3  ==  [[1],[8,3],[4,5,6,7]] levels :: Arbol a -> [[a]] levels t =   map (map rootLabel)   . takeWhile (not . null)   . iterate (concatMap subForest) $ [t]

   Responder

2. Haskell

   data Arbol a = N a [Arbol a] deriving Show espiral :: Arbol a -> [a] espiral a = concat [nivel x a | x <- [1..b]] where b = profundidad a profundidad :: Arbol a -> Int profundidad (N _ []) = 1 profundidad (N _ xs) = 1 + maximum [profundidad a | a <- xs] nivel :: Int -> Arbol a -> [a] nivel 1 (N x _) = [x] nivel x (N _ xs) | odd x = reverse $ concat [nivel (x-1) a| a <- xs] | otherwise = concat [nivel (x-1) a| a <- xs]

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

   data Arbol a = N a [Arbol a]      deriving Show   espiral :: Arbol a -> [a] espiral a = concat [nivel x  a | x <- [1..b]]   where b = profundidad  a    profundidad :: Arbol a -> Int profundidad (N _ []) = 1 profundidad (N _ xs) = 1 + maximum [profundidad a | a <- xs] nivel :: Int -> Arbol a -> [a] nivel 1 (N x _) = [x] nivel x (N _ xs)   | odd x     = reverse $ concat [nivel (x-1) a| a <- xs]   | otherwise = concat [nivel (x-1) a| a <- xs]

   Responder

3. Haskell

   data Arbol a = N a [Arbol a] deriving Show espiral :: Arbol a -> [a] espiral x = concat $ zipWith ($) (cycle [reverse,id]) $ listas [x] listas :: [Arbol a] -> [[a]] listas [] = [] listas xs = a : listas (concat b) where (a,b) = unzip $ map (\(N x y) -> (x,y)) xs

   1 2 3 4 5 6 7 8 9

   data Arbol a = N a [Arbol a]   deriving Show   espiral :: Arbol a -> [a] espiral x = concat $ zipWith ($) (cycle [reverse,id]) $ listas [x] listas :: [Arbol a] -> [[a]] listas [] = [] listas xs = a : listas (concat b)   where (a,b) = unzip $ map (\(N x y) -> (x,y)) xs

   Responder

4. Haskell

   espiral :: Arbol a -> [a] espiral = map fst . concat . espiralizar . groupBy (\(_,b) (_,d)-> b == d) . sortBy (\(a,b) (c,d) -> compare b d) . aux 0 espiralizar :: [[a]] -> [[a]] espiralizar [] = [] espiralizar [x] = [reverse x] espiralizar (x:y:xs) = reverse x : y: espiralizar xs aux :: Int -> Arbol a -> [(a,Int)] aux b (N a []) = [(a,b)] aux b (N a xs) = (a,b) : concatMap (aux (b+1)) xs

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

   espiral :: Arbol a -> [a] espiral = map fst         . concat         . espiralizar         . groupBy (\(_,b) (_,d)-> b == d)         . sortBy (\(a,b) (c,d) -> compare b d)         . aux 0 espiralizar :: [[a]] -> [[a]] espiralizar []       = [] espiralizar [x]      = [reverse x] espiralizar (x:y:xs) = reverse x : y: espiralizar xs aux :: Int -> Arbol a -> [(a,Int)] aux b (N a []) = [(a,b)] aux b (N a xs) = (a,b) : concatMap (aux (b+1)) xs

   Responder

5. Haskell

   data Arbol a = N a [Arbol a] deriving Show espiral :: Arbol a -> [a] espiral = aux . niveles where aux (xs:ys:zss) = reverse xs ++ ys ++ aux zss aux [xs] = reverse xs aux [] = [] niveles :: Arbol a -> [[a]] niveles (N r h) = [r] : aux (map niveles h) where aux (xs:xss) = aux2 xs (aux xss) aux [] = [] aux2 (y:ys) (z:zs) = (y ++ z) : aux2 ys zs aux2 ys [] = ys aux2 [] zs = zs

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

   data Arbol a = N a [Arbol a]              deriving Show   espiral :: Arbol a -> [a] espiral = aux . niveles   where aux (xs:ys:zss) = reverse xs ++ ys ++ aux zss         aux [xs]        = reverse xs         aux []          = [] niveles :: Arbol a -> [[a]] niveles (N r h) = [r] : aux (map niveles h)   where aux (xs:xss)       = aux2 xs (aux xss)         aux []             = []         aux2 (y:ys) (z:zs) = (y ++ z) : aux2 ys zs         aux2 ys []         = ys         aux2 [] zs         = zs

   Responder