Sustitución de pares de elementos consecutivos iguales
Dada una lista xs se reemplaza el primer par de elementos consecutivos iguales x por x+1 y se repite el proceso con las listas obtenidas hasta que no haya ningún par de elementos consecutivos iguales. Por ejemplo, para [5,2,1,1,2,2] se tiene el siguiente proceso
|
1 2 3 4 5 |
[5,2,1,1,2,2] ==> [5,2,2, 2,2] ==> [5,3, 2,2] ==> [5,3, 3] ==> [5,4] |
Definir la función
|
1 |
sustitucion :: [Int] -> [Int] |
tal que (sustitucion xs) es la lista obtenida aplicándole a xs el proceso anterior. Por ejemplo,
|
1 2 3 4 5 |
sustitucion [5,2,1,1,2,2] == [5,4] sustitucion [4,2,1,1,2,2] == [5] sustitucion [4,5,11,2,5,7,2] == [4,5,11,2,5,7,2] sustitucion (1:[1..2*10^6]) == [2000001] length (sustitucion [1..2*10^6]) == 2000000 |
Soluciones
|
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 |
-- 1ª solución -- =========== sustitucion :: [Int] -> [Int] sustitucion xs | xs == ys = xs | otherwise = sustitucion ys where ys = sustitucionElemental xs sustitucionElemental :: [Int] -> [Int] sustitucionElemental [] = [] sustitucionElemental [x] = [x] sustitucionElemental (x:y:zs) | x == y = x+1:zs | otherwise = x : sustitucionElemental (y:zs) -- 2ª solución -- =========== sustitucion2 :: [Int] -> [Int] sustitucion2 xs = until esPuntoFijo sustitucionElemental xs where esPuntoFijo ys = sustitucionElemental ys == ys -- Comparación de eficiencia -- ========================= -- λ> sustitucion (1:[1..2*10^6]) -- [2000001] -- (1.54 secs, 800,143,448 bytes) -- λ> sustitucion2 (1:[1..2*10^6]) -- [2000001] -- (2.21 secs, 1,072,143,584 bytes) |