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
[5,2,1,1,2,2] ==> [5,2,2, 2,2] ==> [5,3, 2,2] ==> [5,3, 3] ==> [5,4]
Definir la función
sustitucion :: [Int] -> [Int]
tal que (sustitucion xs) es la lista obtenida aplicándole a xs el proceso anterior. Por ejemplo,
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ª 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)