Segmentos maximales de elementos consecutivos
Definir la función
|
1 |
segmentos :: (Enum a, Eq a) => [a] -> [[a]] |
tal que (segmentos xss) es la lista de los segmentos maximales de xss formados por elementos consecutivos. Por ejemplo,
|
1 2 3 |
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"] |
Soluciones
[schedule expon=’2022-03-18′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 18 de marzo.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
[/schedule]
[schedule on=’2022-03-18′ at=»06:00″]
|
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 |
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) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Segmentos_consecutivos.hs).
La elaboración de las soluciones explica en el siguiente vídeo:
[/schedule]