Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones del ejercicios 4 y 5 de la relaci\u00f3n 17 correspondiente a la codificaci\u00f3n por longitud y a la sucesi\u00f3n de Kolakoski.<\/p>\n<<\/p>\n
p>Los ejercicios y sus soluciones son
\n<\/p>\n
\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares --\n-- ---------------------------------------------------------------------\n\nimport Data.Char \nimport Data.List \nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- \u00a7 La codificaci\u00f3n por longitud --\n-- ---------------------------------------------------------------------\n\n-- La codificaci\u00f3n por longitud, o comprensi\u00f3n RLE (del ingl\u00e9s,\n-- \"Run-length encoding\"), es una compresi\u00f3n de datos en la que\n-- secuencias de datos con el mismo valor consecutivas son almacenadas\n-- como un \u00fanico valor m\u00e1s su recuento. Por ejemplo, la cadena \n-- BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB\n-- se codifica por \n-- 12B1N12B3N24B1N14B\n-- Interpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras\n-- N, etc.\n-- \n-- En los siguientes ejercicios se definir\u00e1n funciones para codificar y\n-- descodificar por longitud.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Una lista se puede comprimir indicando el n\u00famero de\n-- veces consecutivas que aparece cada elemento. Por ejemplo, la lista \n-- comprimida de [1,1,7,7,7,5,5,7,7,7,7] es [(2,1),(3,7),(2,5),(4,7)],\n-- indicando que comienza con dos 1, seguido de tres 7, dos 5 y cuatro\n-- 7. \n-- \n-- Definir la funci\u00f3n\n-- comprimida :: Eq a => [a] -> [(Int,a)]\n-- tal que (comprimida xs) es la lista obtenida al comprimir por\n-- longitud la lista xs. Por ejemplo, \n-- ghci> comprimida [1,1,7,7,7,5,5,7,7,7,7]\n-- [(2,1),(3,7),(2,5),(4,7)]\n-- ghci> comprimida \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBB\"\n-- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\ncomprimida :: Eq a => [a] -> [(Int,a)]\ncomprimida xs = aux xs 1\n where aux (x:y:zs) n | x == y = aux (y:zs) (n+1)\n | otherwise = (n,x) : aux (y:zs) 1\n aux [x] n = [(n,x)]\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n usando takeWhile):\ncomprimida2 :: Eq a => [a] -> [(Int,a)]\ncomprimida2 [] = []\ncomprimida2 (x:xs) = \n (1 + length (takeWhile (==x) xs),x) : comprimida2 (dropWhile (==x) xs)\n\n-- 3\u00aa definici\u00f3n (por comprensi\u00f3n usando group):\ncomprimida3 :: Eq a => [a] -> [(Int,a)]\ncomprimida3 xs = [(length ys, head ys) | ys <- group xs]\n\n-- 4\u00aa definici\u00f3n (usando map y group):\ncomprimida4 :: Eq a => [a] -> [(Int,a)]\ncomprimida4 = map (\\xs -> (length xs, head xs)) . group\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Definir la funci\u00f3n\n-- expandida :: [(Int,a)] -> [a]\n-- tal que (expandida ps) es la lista expandida correspondiente a ps (es\n-- decir, es la lista xs tal que la comprimida de xs es ps). Por\n-- ejemplo, \n-- expandida [(2,1),(3,7),(2,5),(4,7)] == [1,1,7,7,7,5,5,7,7,7,7]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n)\nexpandida :: [(Int,a)] -> [a]\nexpandida ps = concat [replicate k x | (k,x) <- ps]\n\n-- 2\u00aa definici\u00f3n (por concatMap)\nexpandida2 :: [(Int,a)] -> [a]\nexpandida2 = concatMap (\\(k,x) -> replicate k x) \n\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n)\nexpandida3 :: [(Int,a)] -> [a]\nexpandida3 [] = []\nexpandida3 ((n,x):ps) = replicate n x ++ expandida3 ps\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.3. Comprobar con QuickCheck que dada una lista de enteros,\n-- si se la comprime y despu\u00e9s se expande se obtiene la lista inicial. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_expandida_comprimida :: [Int] -> Bool \nprop_expandida_comprimida xs = expandida (comprimida xs) == xs\n\n-- La comprobaci\u00f3n es\n-- ghci> quickCheck prop_expandida_comprimida\n-- +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.4. Comprobar con QuickCheck que dada una lista de pares\n-- de enteros, si se la expande y despu\u00e9s se comprime se obtiene la\n-- lista inicial. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_comprimida_expandida :: [(Int,Int)] -> Bool \nprop_comprimida_expandida xs = expandida (comprimida xs) == xs\n\n-- La comprobaci\u00f3n es\n-- ghci> quickCheck prop_comprimida_expandida\n-- +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.5. Definir la funci\u00f3n\n-- listaAcadena :: [(Int,Char)] -> String\n-- tal que (listaAcadena xs) es la cadena correspondiente a la lista de\n-- pares de xs. Por ejemplo,\n-- ghci> listaAcadena [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')]\n-- \"12B1N12B3N19B\"\n-- ---------------------------------------------------------------------\n\nlistaAcadena :: [(Int,Char)] -> String\nlistaAcadena xs = concat [show n ++ [c] | (n,c) <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.6. Definir la funci\u00f3n\n-- cadenaComprimida :: String -> String\n-- tal que (cadenaComprimida cs) es la cadena obtenida comprimiendo por\n-- longitud la cadena cs. Por ejemplo,\n-- ghci> cadenaComprimida \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN\"\n-- \"12B1N12B3N10B3N\"\n-- ---------------------------------------------------------------------\n\ncadenaComprimida :: String -> String\ncadenaComprimida = listaAcadena . comprimida\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.7. Definir la funci\u00f3n \n-- cadenaAlista :: String -> [(Int,Char)]\n-- tal que (cadenaAlista cs) es la lista de pares correspondientes a la\n-- cadena cs. Por ejemplo,\n-- ghci> cadenaAlista \"12B1N12B3N10B3N\"\n-- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(10,'B'),(3,'N')]\n-- ---------------------------------------------------------------------\n\ncadenaAlista :: String -> [(Int,Char)]\ncadenaAlista [] = []\ncadenaAlista cs = (read ns,x) : cadenaAlista xs\n where (ns,(x:xs)) = span isNumber cs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.8. Definir la funci\u00f3n\n-- cadenaExpandida :: String -> String\n-- tal que (cadenaExpandida cs) es la cadena expandida correspondiente a\n-- cs (es decir, es la cadena xs que al comprimirse por longitud da cs). \n-- Por ejemplo, \n-- ghci> cadenaExpandida \"12B1N12B3N10B3N\"\n-- \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN\"\n-- ---------------------------------------------------------------------\n\ncadenaExpandida :: String -> String\ncadenaExpandida = expandida . cadenaAlista\n\n-- ---------------------------------------------------------------------\n-- \u00a7 La sucesi\u00f3n de Kolakoski --\n-- ---------------------------------------------------------------------\n\n-- Dada una sucesi\u00f3n, su contadora es la sucesi\u00f3n de las longitudes de\n-- de sus bloque de elementos consecutivos iguales. Por ejemplo, la\n-- sucesi\u00f3n contadora de abbaaabbba es 12331; es decir; 1 vez la a,\n-- 2 la b, 3 la a, 3 la b y 1 la a.\n-- \n-- La sucesi\u00f3n de Kolakoski es una sucesi\u00f3n infinita de los s\u00edmbolos 1 y\n-- 2 que es su propia contadora. Los primeros t\u00e9rminos de la sucesi\u00f3n\n-- de Kolakoski son 1221121221221... que coincide con su contadora (es\n-- decir, 1 vez el 1, 2 veces el 2, 2 veces el 1, ...). \n-- \n-- En esta secci\u00f3n se define la sucesi\u00f3n de Kolakoski.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Dados los s\u00edmbolos a y b, la sucesi\u00f3n contadora de\n-- abbaaabbba... = a bb aaa bbb a ... \n-- es\n-- 1233... = 1 2 3 3...\n-- es decir; 1 vez la a, 2 la b, 3 la a, 3 la b, 1 la a, ...\n-- \n-- Definir la funci\u00f3n\n-- contadora :: Eq a => [a] -> [Int]\n-- tal que (contadora xs) es la sucesi\u00f3n contadora de xs. Por ejemplo,\n-- contadora \"abbaaabbb\" == [1,2,3,3]\n-- contadora \"122112122121121\" == [1,2,2,1,1,2,1,1,2,1,1]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (usando group definida en Data.List)\ncontadora :: Eq a => [a] -> [Int]\ncontadora xs = map length (group xs)\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n sin group):\ncontadora2 :: Eq a => [a] -> [Int]\ncontadora2 [] = []\ncontadora2 ys@(x:xs) = \n length (takeWhile (==x) ys) : contadora2 (dropWhile (==x) xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Definir la funci\u00f3n\n-- contada :: [Int] -> [a] -> [a]\n-- tal que (contada ns xs) es la sucesi\u00f3n formada por los s\u00edmbolos de xs\n-- cuya contadora es ns. Por ejemplo,\n-- contada [1,2,3,3] \"ab\" == \"abbaaabbb\"\n-- contada [1,2,3,3] \"abc\" == \"abbcccaaa\"\n-- contada [1,2,2,1,1,2,1,1,2,1,1] \"12\" == \"122112122121121\"\n-- ---------------------------------------------------------------------\n\ncontada :: [Int] -> [a] -> [a]\ncontada (n:ns) (x:xs) = replicate n x ++ contada ns (xs++[x])\ncontada [] _ = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.3. La sucesi\u00f3n autocontadora (o sucesi\u00f3n de Kolakoski) es\n-- la sucesi\u00f3n xs formada por 1 y 2 tal que coincide con su contada; es\n-- decir (contadora xs) == xs. Los primeros t\u00e9rminos de la funci\u00f3n\n-- autocontadora son\n-- 1221121221221... = 1 22 11 2 1 22 1 22 11 ...\n-- y su contadora es\n-- 122112122... = 1 2 2 1 1 2 1 2 2...\n-- que coincide con la inicial. \n-- \n-- Definir la funci\u00f3n\n-- autocontadora :: [Int]\n-- tal que autocontadora es la sucesi\u00f3n autocondadora con los n\u00fameros 1\n-- y 2. Por ejemplo,\n-- take 11 autocontadora == [1,2,2,1,1,2,1,1,2,1,1]\n-- take 12 autocontadora == [1,2,2,1,1,2,1,1,2,1,1,2]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nautocontadora :: [Int]\nautocontadora = [1,2] ++ siguiente [2] 2\n\n-- Los pasos lo da la funci\u00f3n siguiente. Por ejemplo,\n-- take 3 (siguiente [2] 2) == [2,1,1]\n-- take 4 (siguiente [2,1,1] 1) == [2,1,1,2]\n-- take 6 (siguiente [2,1,1,2] 2) == [2,1,1,2,1,1]\n-- take 7 (siguiente [2,1,1,2,1,1] 1) == [2,1,1,2,1,1,2]\nsiguiente (x:xs) y = x : siguiente (xs ++ (nuevos x)) y'\n where contrario 1 = 2\n contrario 2 = 1\n y' = contrario y \n nuevos 1 = [y']\n nuevos 2 = [y',y'] \n\n-- 2\u00aa soluci\u00f3n (usando contada)\nautocontadora2 :: [Int]\nautocontadora2 = 1 : 2: xs \n where xs = 2 : contada xs [1,2]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"< p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones del ejercicios 4 y 5 de la relaci\u00f3n 17 correspondiente a la codificaci\u00f3n por longitud y a la sucesi\u00f3n de Kolakoski. < p>Los ejercicios y sus soluciones son<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[222],"tags":[270,300],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4194"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=4194"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4194\/revisions"}],"predecessor-version":[{"id":4285,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4194\/revisions\/4285"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}