La semana en Exercitium (del 14 al 18 de marzo)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Diagonales principales de una matriz.
- 2. Matrices de Toepliz
- 3. Máximos locales
- 4. Lista cuadrada
- 5. Segmentos de elementos consecutivos
A continuación se muestran las soluciones.
1. Diagonales principales de una matriz.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
-- --------------------------------------------------------------------- -- La lista de las diagonales principales de la matriz -- 1 2 3 4 -- 5 6 7 8 -- 9 10 11 12 -- es -- [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] -- -- Definir la función -- diagonalesPrincipales :: Array (Int,Int) a -> [[a]] -- tal que (diagonalesPrincipales p) es la lista de las diagonales -- principales de p. Por ejemplo, -- λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) -- [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] -- --------------------------------------------------------------------- module Diagonales_principales where import Data.Array (Array, (!), bounds, listArray) import Test.QuickCheck -- 1ª solución -- =========== diagonalesPrincipales1 :: Array (Int,Int) a -> [[a]] diagonalesPrincipales1 p = [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales1 m n] where (_,(m,n)) = bounds p posicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales1 m n = [extension ij | ij <- iniciales] where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]] extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]] -- 2ª solución -- =========== diagonalesPrincipales2 :: Array (Int,Int) a -> [[a]] diagonalesPrincipales2 p = [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales2 m n] where (_,(m,n)) = bounds p posicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales2 m n = [zip [i..m] [1..n] | i <- [m,m-1..1]] ++ [zip [1..m] [j..n] | j <- [2..n]] -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_diagonalesPrincipales :: Positive Int -> Positive Int -> Bool prop_diagonalesPrincipales (Positive m) (Positive n) = diagonalesPrincipales1 p == diagonalesPrincipales2 p where p = listArray ((1,1),(m,n)) [1..] -- La comprobación es -- λ> quickCheck prop_diagonalesPrincipales -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (diagonalesPrincipales1 (listArray ((1,1),(10^4,10^4)) [1..])) -- 19999 -- (6.90 secs, 8,010,369,224 bytes) -- λ> length (diagonalesPrincipales2 (listArray ((1,1),(10^4,10^4)) [1..])) -- 19999 -- (6.78 secs, 8,008,289,224 bytes) |
2. Matrices de Toepliz
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
-- --------------------------------------------------------------------- -- Una [matriz de Toeplitz](https://bit.ly/3pqjY9D) es una matriz -- cuadrada que es constante a lo largo de las diagonales paralelas a la -- diagonal principal. Por ejemplo, -- |2 5 1 6| |2 5 1 6| -- |4 2 5 1| |4 2 6 1| -- |7 4 2 5| |7 4 2 5| -- |9 7 4 2| |9 7 4 2| -- la primera es una matriz de Toeplitz y la segunda no lo es. -- -- Las anteriores matrices se pueden definir por -- ej1, ej2 :: Array (Int,Int) Int -- ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2] -- ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2] -- -- Definir la función -- esToeplitz :: Eq a => Array (Int,Int) a -> Bool -- tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por -- ejemplo, -- esToeplitz ej1 == True -- esToeplitz ej2 == False -- --------------------------------------------------------------------- module Matriz_Toeplitz where import Data.Array (Array, (!), bounds, listArray) ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2] ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2] -- 1ª solución -- =========== esToeplitz1 :: Eq a => Array (Int,Int) a -> Bool esToeplitz1 p = esCuadrada p && all todosIguales (diagonalesPrincipales p) -- (esCuadrada p) se verifica si la matriz p es cuadrada. Por ejemplo, -- esCuadrada (listArray ((1,1),(4,4)) [1..]) == True -- esCuadrada (listArray ((1,1),(3,4)) [1..]) == False esCuadrada :: Eq a => Array (Int,Int) a -> Bool esCuadrada p = m == n where (_,(m,n)) = bounds p -- (diagonalesPrincipales p) es la lista de las diagonales principales -- de p. Por ejemplo, -- λ> diagonalesPrincipales ej1 -- [[2,2,2,2],[5,5,5],[1,1],[6],[2,2,2,2],[4,4,4],[7,7],[9]] -- λ> diagonalesPrincipales ej2 -- [[2,2,2,2],[5,6,5],[1,1],[6],[2,2,2,2],[4,4,4],[7,7],[9]] diagonalesPrincipales :: Array (Int,Int) a -> [[a]] diagonalesPrincipales p = [[p ! i |i <- is] | is <- posicionesDiagonalesPrincipales m n] where (_,(m,n)) = bounds p -- (posicionesDiagonalesPrincipales m n) es la lista de las -- posiciones de las diagonales principales de una matriz con m filas y -- n columnas. Por ejemplo, -- λ> mapM_ print (posicionesDiagonalesPrincipales 3 4) -- [(3,1)] -- [(2,1),(3,2)] -- [(1,1),(2,2),(3,3)] -- [(1,2),(2,3),(3,4)] -- [(1,3),(2,4)] -- [(1,4)] -- λ> mapM_ print (posicionesDiagonalesPrincipales 4 4) -- [(4,1)] -- [(3,1),(4,2)] -- [(2,1),(3,2),(4,3)] -- [(1,1),(2,2),(3,3),(4,4)] -- [(1,2),(2,3),(3,4)] -- [(1,3),(2,4)] -- [(1,4)] -- λ> mapM_ print (posicionesDiagonalesPrincipales 4 3) -- [(4,1)] -- [(3,1),(4,2)] -- [(2,1),(3,2),(4,3)] -- [(1,1),(2,2),(3,3)] -- [(1,2),(2,3)] -- [(1,3)] posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales m n = [zip [i..m] [1..n] | i <- [m,m-1..1]] ++ [zip [1..m] [j..n] | j <- [2..n]] -- (todosIguales xs) se verifica si todos los elementos de xs son -- iguales. Por ejemplo, -- todosIguales [5,5,5] == True -- todosIguales [5,4,5] == False todosIguales :: Eq a => [a] -> Bool todosIguales [] = True todosIguales (x:xs) = all (== x) xs -- 2ª solución -- =========== esToeplitz2 :: Eq a => Array (Int,Int) a -> Bool esToeplitz2 p = m == n && and [p!(i,j) == p!(i+1,j+1) | i <- [1..n-1], j <- [1..n-1]] where (_,(m,n)) = bounds p -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esToeplitz1 (listArray ((1,1),(2*10^3,2*10^3)) (repeat 1)) -- True -- (2.26 secs, 2,211,553,888 bytes) -- λ> esToeplitz2 (listArray ((1,1),(2*10^3,2*10^3)) (repeat 1)) -- True -- (4.26 secs, 3,421,651,032 bytes) |
3. Máximos locales
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
-- --------------------------------------------------------------------- -- Un máximo local de una lista es un elemento de la lista que es mayor -- que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un -- máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su -- predecesor) y que 3 (su sucesor). -- -- Definir la función -- maximosLocales :: Ord a => [a] -> [a] -- tal que (maximosLocales xs) es la lista de los máximos locales de la -- lista xs. Por ejemplo, -- maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6] -- maximosLocales [1..100] == [] -- maximosLocales "adbpmqexyz" == "dpq" -- --------------------------------------------------------------------- import Test.QuickCheck -- 1ª solución -- =========== maximosLocales1 :: Ord a => [a] -> [a] maximosLocales1 (x:y:z:xs) | y > x && y > z = y : maximosLocales1 (z:xs) | otherwise = maximosLocales1 (y:z:xs) maximosLocales1 _ = [] -- 2ª solución -- =========== maximosLocales2 :: Ord a => [a] -> [a] maximosLocales2 xs = [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y > x, y > z] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_maximosLocales :: [Int] -> Property prop_maximosLocales xs = maximosLocales1 xs === maximosLocales2 xs -- La comprobación es -- λ> quickCheck prop_maximosLocales -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (maximosLocales1 (take (6*10^6) (cycle "abc"))) -- 'c' -- (3.26 secs, 1,904,464,984 bytes) -- λ> last (maximosLocales2 (take (6*10^6) (cycle "abc"))) -- 'c' -- (2.79 secs, 1,616,465,088 bytes) |
La elaboración de las soluciones se explica en el siguiente vídeo:
4. Lista cuadrada
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
-- --------------------------------------------------------------------- -- Definir la función -- listaCuadrada :: Int -> a -> [a] -> [[a]] -- tal que (listaCuadrada n x xs) es una lista de n listas de longitud n -- formadas con los elementos de xs completada con x, si no xs no tiene -- suficientes elementos. Por ejemplo, -- listaCuadrada 3 7 [0,3,5,2,4] == [[0,3,5],[2,4,7],[7,7,7]] -- listaCuadrada 3 7 [0..] == [[0,1,2],[3,4,5],[6,7,8]] -- listaCuadrada 2 'p' "eva" == ["ev","ap"] -- listaCuadrada 2 'p' ['a'..] == ["ab","cd"] -- --------------------------------------------------------------------- {-# OPTIONS_GHC -fno-warn-unused-imports #-} module Lista_cuadrada where import Data.List.Split (chunksOf) import Test.QuickCheck -- 1ª solución -- =========== listaCuadrada1 :: Int -> a -> [a] -> [[a]] listaCuadrada1 n x xs = take n (grupos n (xs ++ repeat x)) -- (grupos n xs) es la lista obtenida agrupando los elementos de xs en -- grupos de n elementos, salvo el último que puede tener menos. Por -- ejemplo, -- grupos 2 [4,2,5,7,6] == [[4,2],[5,7],[6]] -- take 3 (grupos 3 [1..]) == [[1,2,3],[4,5,6],[7,8,9]] grupos :: Int -> [a] -> [[a]] grupos _ [] = [] grupos n xs = take n xs : grupos n (drop n xs) -- 2ª solución -- =========== listaCuadrada2 :: Int -> a -> [a] -> [[a]] listaCuadrada2 n x xs = take n (grupos2 n (xs ++ repeat x)) grupos2 :: Int -> [a] -> [[a]] grupos2 _ [] = [] grupos2 n xs = ys : grupos n zs where (ys,zs) = splitAt n xs -- 3ª solución -- =========== listaCuadrada3 :: Int -> a -> [a] -> [[a]] listaCuadrada3 n x xs = take n (chunksOf n (xs ++ repeat x)) -- Comprobación de la equivalencia -- =============================== -- La propiedad es prop_listaCuadrada :: Int -> Int -> [Int] -> Bool prop_listaCuadrada n x xs = all (== listaCuadrada1 n x xs) [listaCuadrada2 n x xs, listaCuadrada3 n x xs] -- La comprobación es -- λ> quickCheck prop_listaCuadrada -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (listaCuadrada1 (10^4) 5 [1..]) -- 10000 -- (2.02 secs, 12,801,918,616 bytes) -- λ> length (listaCuadrada2 (10^4) 5 [1..]) -- 10000 -- (1.89 secs, 12,803,198,576 bytes) -- λ> length (listaCuadrada3 (10^4) 5 [1..]) -- 10000 -- (1.85 secs, 12,801,518,728 bytes) |
La elaboración de las soluciones se explica en el siguiente vídeo:
5. Segmentos de elementos consecutivos
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
-- --------------------------------------------------------------------- -- Definir la función -- segmentos :: (Enum a, Eq a) => [a] -> [[a]] -- tal que (segmentos xss) es la lista de los segmentos de xss formados -- por elementos consecutivos. Por ejemplo, -- segmentos [1,2,5,6,4] == [[1,2],[5,6],[4]] -- segmentos [1,2,3,4,7,8,9] == [[1,2,3,4],[7,8,9]] -- segmentos "abbccddeeebc" == ["ab","bc","cd","de","e","e","bc"] -- --------------------------------------------------------------------- {-# OPTIONS_GHC -fno-warn-unused-imports #-} module Segmentos_consecutivos where import Test.QuickCheck -- 1ª solución -- =========== segmentos1 :: (Enum a, Eq a) => [a] -> [[a]] segmentos1 [] = [] segmentos1 xs = ys : segmentos1 zs where ys = inicial xs n = length ys zs = drop n xs -- (inicial xs) es el segmento inicial de xs formado por elementos -- consecutivos. Por ejemplo, -- inicial [1,2,5,6,4] == [1,2] -- inicial "abccddeeebc" == "abc" inicial :: (Enum a, Eq a) => [a] -> [a] inicial [] = [] inicial [x] = [x] inicial (x:y:xs) | succ x == y = x : inicial (y:xs) | otherwise = [x] -- 2ª solución -- =========== segmentos2 :: (Enum a, Eq a) => [a] -> [[a]] segmentos2 [] = [] segmentos2 xs = ys : segmentos2 zs where (ys,zs) = inicialYresto xs -- (inicialYresto xs) es par formado por el segmento inicial de xs -- con elementos consecutivos junto con los restantes elementos. Por -- ejemplo, -- inicialYresto [1,2,5,6,4] == ([1,2],[5,6,4]) -- inicialYresto "abccddeeebc" == ("abc","cddeeebc") inicialYresto :: (Enum a, Eq a) => [a] -> ([a],[a]) inicialYresto [] = ([],[]) inicialYresto [x] = ([x],[]) inicialYresto (x:y:xs) | succ x == y = (x:us,vs) | otherwise = ([x],y:xs) where (us,vs) = inicialYresto (y:xs) -- 3ª solución -- =========== segmentos3 :: (Enum a, Eq a) => [a] -> [[a]] segmentos3 [] = [] segmentos3 [x] = [[x]] segmentos3 (x:xs) | y == succ x = (x:y:ys):zs | otherwise = [x] : (y:ys):zs where ((y:ys):zs) = segmentos3 xs -- 4ª solución -- =========== segmentos4 :: (Enum a, Eq a) => [a] -> [[a]] segmentos4 [] = [] segmentos4 xs = ys : segmentos4 zs where ys = inicial4 xs n = length ys zs = drop n xs inicial4 :: (Enum a, Eq a) => [a] -> [a] inicial4 [] = [] inicial4 (x:xs) = map fst (takeWhile (\(u,v) -> u == v) (zip (x:xs) [x..])) -- 5ª solución -- =========== segmentos5 :: (Enum a, Eq a) => [a] -> [[a]] segmentos5 [] = [] segmentos5 xs = ys : segmentos5 zs where ys = inicial5 xs n = length ys zs = drop n xs inicial5 :: (Enum a, Eq a) => [a] -> [a] inicial5 [] = [] inicial5 (x:xs) = map fst (takeWhile (uncurry (==)) (zip (x:xs) [x..])) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_segmentos :: [Int] -> Bool prop_segmentos xs = all (== segmentos1 xs) [segmentos2 xs, segmentos3 xs, segmentos4 xs, segmentos5 xs] -- La comprobación es -- λ> quickCheck prop_segmentos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (segmentos1 (take (10^6) (cycle [1..10^3]))) -- 1000 -- (0.69 secs, 416,742,208 bytes) -- λ> length (segmentos2 (take (10^6) (cycle [1..10^3]))) -- 1000 -- (0.66 secs, 528,861,976 bytes) -- λ> length (segmentos3 (take (10^6) (cycle [1..10^3]))) -- 1000 -- (2.35 secs, 1,016,276,896 bytes) -- λ> length (segmentos4 (take (10^6) (cycle [1..10^3]))) -- 1000 -- (0.27 secs, 409,438,368 bytes) -- λ> length (segmentos5 (take (10^6) (cycle [1..10^3]))) -- 1000 -- (0.13 secs, 401,510,360 bytes) -- -- λ> length (segmentos4 (take (10^7) (cycle [1..10^3]))) -- 10000 -- (2.35 secs, 4,088,926,920 bytes) -- λ> length (segmentos5 (take (10^7) (cycle [1..10^3]))) -- 10000 -- (1.02 secs, 4,009,646,928 bytes) |