PeH: 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 la siguiente relación (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) se define la sucesión de Kolakoski.
|
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 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List (group) -- --------------------------------------------------------------------- -- Ejercicio 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, ... -- 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 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 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] |