I1M2013: Codificación por longitud y la sucesión de Kolakoski
<
p>En la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones del ejercicios 4 y 5 de la relación 17 correspondiente a la codificación por longitud y a la sucesión de Kolakoski.
<
p>Los ejercicios y sus soluciones son
|
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 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Char import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- § La codificación por longitud -- -- --------------------------------------------------------------------- -- La codificación por longitud, o comprensión RLE (del inglés, -- "Run-length encoding"), es una compresión de datos en la que -- secuencias de datos con el mismo valor consecutivas son almacenadas -- como un único valor más su recuento. Por ejemplo, la cadena -- BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB -- se codifica por -- 12B1N12B3N24B1N14B -- Interpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras -- N, etc. -- -- En los siguientes ejercicios se definirán funciones para codificar y -- descodificar por longitud. -- --------------------------------------------------------------------- -- Ejercicio 4.1. Una lista se puede comprimir indicando el número de -- veces consecutivas que aparece cada elemento. Por ejemplo, la lista -- comprimida de [1,1,7,7,7,5,5,7,7,7,7] es [(2,1),(3,7),(2,5),(4,7)], -- indicando que comienza con dos 1, seguido de tres 7, dos 5 y cuatro -- 7. -- -- Definir la función -- comprimida :: Eq a => [a] -> [(Int,a)] -- tal que (comprimida xs) es la lista obtenida al comprimir por -- longitud la lista xs. Por ejemplo, -- ghci> comprimida [1,1,7,7,7,5,5,7,7,7,7] -- [(2,1),(3,7),(2,5),(4,7)] -- ghci> comprimida "BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBB" -- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')] -- --------------------------------------------------------------------- -- 1ª definición (por recursión) comprimida :: Eq a => [a] -> [(Int,a)] comprimida xs = aux xs 1 where aux (x:y:zs) n | x == y = aux (y:zs) (n+1) | otherwise = (n,x) : aux (y:zs) 1 aux [x] n = [(n,x)] -- 2ª definición (por recursión usando takeWhile): comprimida2 :: Eq a => [a] -> [(Int,a)] comprimida2 [] = [] comprimida2 (x:xs) = (1 + length (takeWhile (==x) xs),x) : comprimida2 (dropWhile (==x) xs) -- 3ª definición (por comprensión usando group): comprimida3 :: Eq a => [a] -> [(Int,a)] comprimida3 xs = [(length ys, head ys) | ys <- group xs] -- 4ª definición (usando map y group): comprimida4 :: Eq a => [a] -> [(Int,a)] comprimida4 = map (\xs -> (length xs, head xs)) . group -- --------------------------------------------------------------------- -- Ejercicio 4.2. Definir la función -- expandida :: [(Int,a)] -> [a] -- tal que (expandida ps) es la lista expandida correspondiente a ps (es -- decir, es la lista xs tal que la comprimida de xs es ps). Por -- ejemplo, -- expandida [(2,1),(3,7),(2,5),(4,7)] == [1,1,7,7,7,5,5,7,7,7,7] -- --------------------------------------------------------------------- -- 1ª definición (por comprensión) expandida :: [(Int,a)] -> [a] expandida ps = concat [replicate k x | (k,x) <- ps] -- 2ª definición (por concatMap) expandida2 :: [(Int,a)] -> [a] expandida2 = concatMap (\(k,x) -> replicate k x) -- 3ª definición (por recursión) expandida3 :: [(Int,a)] -> [a] expandida3 [] = [] expandida3 ((n,x):ps) = replicate n x ++ expandida3 ps -- --------------------------------------------------------------------- -- Ejercicio 4.3. Comprobar con QuickCheck que dada una lista de enteros, -- si se la comprime y después se expande se obtiene la lista inicial. -- --------------------------------------------------------------------- -- La propiedad es prop_expandida_comprimida :: [Int] -> Bool prop_expandida_comprimida xs = expandida (comprimida xs) == xs -- La comprobación es -- ghci> quickCheck prop_expandida_comprimida -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4.4. Comprobar con QuickCheck que dada una lista de pares -- de enteros, si se la expande y después se comprime se obtiene la -- lista inicial. -- --------------------------------------------------------------------- -- La propiedad es prop_comprimida_expandida :: [(Int,Int)] -> Bool prop_comprimida_expandida xs = expandida (comprimida xs) == xs -- La comprobación es -- ghci> quickCheck prop_comprimida_expandida -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4.5. Definir la función -- listaAcadena :: [(Int,Char)] -> String -- tal que (listaAcadena xs) es la cadena correspondiente a la lista de -- pares de xs. Por ejemplo, -- ghci> listaAcadena [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')] -- "12B1N12B3N19B" -- --------------------------------------------------------------------- listaAcadena :: [(Int,Char)] -> String listaAcadena xs = concat [show n ++ [c] | (n,c) <- xs] -- --------------------------------------------------------------------- -- Ejercicio 4.6. Definir la función -- cadenaComprimida :: String -> String -- tal que (cadenaComprimida cs) es la cadena obtenida comprimiendo por -- longitud la cadena cs. Por ejemplo, -- ghci> cadenaComprimida "BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN" -- "12B1N12B3N10B3N" -- --------------------------------------------------------------------- cadenaComprimida :: String -> String cadenaComprimida = listaAcadena . comprimida -- --------------------------------------------------------------------- -- Ejercicio 4.7. Definir la función -- cadenaAlista :: String -> [(Int,Char)] -- tal que (cadenaAlista cs) es la lista de pares correspondientes a la -- cadena cs. Por ejemplo, -- ghci> cadenaAlista "12B1N12B3N10B3N" -- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(10,'B'),(3,'N')] -- --------------------------------------------------------------------- cadenaAlista :: String -> [(Int,Char)] cadenaAlista [] = [] cadenaAlista cs = (read ns,x) : cadenaAlista xs where (ns,(x:xs)) = span isNumber cs -- --------------------------------------------------------------------- -- Ejercicio 4.8. Definir la función -- cadenaExpandida :: String -> String -- tal que (cadenaExpandida cs) es la cadena expandida correspondiente a -- cs (es decir, es la cadena xs que al comprimirse por longitud da cs). -- Por ejemplo, -- ghci> cadenaExpandida "12B1N12B3N10B3N" -- "BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN" -- --------------------------------------------------------------------- cadenaExpandida :: String -> String cadenaExpandida = expandida . cadenaAlista -- --------------------------------------------------------------------- -- § La sucesión de Kolakoski -- -- --------------------------------------------------------------------- -- Dada una sucesión, su contadora es la sucesión de las longitudes de -- de sus bloque de elementos consecutivos iguales. Por ejemplo, la -- sucesión contadora de abbaaabbba es 12331; es decir; 1 vez la a, -- 2 la b, 3 la a, 3 la b y 1 la a. -- -- La sucesión de Kolakoski es una sucesión infinita de los símbolos 1 y -- 2 que es su propia contadora. Los primeros términos de la sucesión -- de Kolakoski son 1221121221221... que coincide con su contadora (es -- decir, 1 vez el 1, 2 veces el 2, 2 veces el 1, ...). -- -- En esta sección se define la sucesión de Kolakoski. -- --------------------------------------------------------------------- -- Ejercicio 5.1. Dados los símbolos a y b, la sucesión contadora de -- abbaaabbba... = a bb aaa bbb a ... -- es -- 1233... = 1 2 3 3... -- es decir; 1 vez la a, 2 la b, 3 la a, 3 la b, 1 la a, ... -- -- Definir la función -- contadora :: Eq a => [a] -> [Int] -- tal que (contadora xs) es la sucesión contadora de xs. Por ejemplo, -- contadora "abbaaabbb" == [1,2,3,3] -- contadora "122112122121121" == [1,2,2,1,1,2,1,1,2,1,1] -- --------------------------------------------------------------------- -- 1ª definición (usando group definida en Data.List) contadora :: Eq a => [a] -> [Int] contadora xs = map length (group xs) -- 2ª definición (por recursión sin group): contadora2 :: Eq a => [a] -> [Int] contadora2 [] = [] contadora2 ys@(x:xs) = length (takeWhile (==x) ys) : contadora2 (dropWhile (==x) xs) -- --------------------------------------------------------------------- -- Ejercicio 5.2. Definir la función -- contada :: [Int] -> [a] -> [a] -- tal que (contada ns xs) es la sucesión formada por los símbolos de xs -- cuya contadora es ns. Por ejemplo, -- contada [1,2,3,3] "ab" == "abbaaabbb" -- contada [1,2,3,3] "abc" == "abbcccaaa" -- contada [1,2,2,1,1,2,1,1,2,1,1] "12" == "122112122121121" -- --------------------------------------------------------------------- contada :: [Int] -> [a] -> [a] contada (n:ns) (x:xs) = replicate n x ++ contada ns (xs++[x]) contada [] _ = [] -- --------------------------------------------------------------------- -- Ejercicio 5.3. La sucesión autocontadora (o sucesión de Kolakoski) es -- la sucesión xs formada por 1 y 2 tal que coincide con su contada; es -- decir (contadora xs) == xs. Los primeros términos de la función -- autocontadora son -- 1221121221221... = 1 22 11 2 1 22 1 22 11 ... -- y su contadora es -- 122112122... = 1 2 2 1 1 2 1 2 2... -- que coincide con la inicial. -- -- Definir la función -- autocontadora :: [Int] -- tal que autocontadora es la sucesión autocondadora con los números 1 -- y 2. Por ejemplo, -- take 11 autocontadora == [1,2,2,1,1,2,1,1,2,1,1] -- take 12 autocontadora == [1,2,2,1,1,2,1,1,2,1,1,2] -- --------------------------------------------------------------------- -- 1ª solución autocontadora :: [Int] autocontadora = [1,2] ++ siguiente [2] 2 -- Los pasos lo da la función siguiente. Por ejemplo, -- take 3 (siguiente [2] 2) == [2,1,1] -- take 4 (siguiente [2,1,1] 1) == [2,1,1,2] -- take 6 (siguiente [2,1,1,2] 2) == [2,1,1,2,1,1] -- take 7 (siguiente [2,1,1,2,1,1] 1) == [2,1,1,2,1,1,2] siguiente (x:xs) y = x : siguiente (xs ++ (nuevos x)) y' where contrario 1 = 2 contrario 2 = 1 y' = contrario y nuevos 1 = [y'] nuevos 2 = [y',y'] -- 2ª solución (usando contada) autocontadora2 :: [Int] autocontadora2 = 1 : 2: xs where xs = 2 : contada xs [1,2] |