La bandera tricolor
El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista ys que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.
Definir el tipo de dato Color para representar los colores con los constructores R, A y M correspondientes al rojo, azul y morado y la función
|
1 |
banderaTricolor :: [Color] -> [Color] |
tal que (banderaTricolor xs) es la bandera tricolor formada con los elementos de xs. Por ejemplo,
|
1 2 |
bandera [M,R,A,A,R,R,A,M,M] == [R,R,R,A,A,A,M,M,M] bandera [M,R,A,R,R,A] == [R,R,R,A,A,M] |
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 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 |
import Data.List (sort) import Test.QuickCheck (Arbitrary(arbitrary), elements, quickCheck) data Color = R | A | M deriving (Show, Eq, Ord, Enum) -- 1ª solución -- =========== banderaTricolor1 :: [Color] -> [Color] banderaTricolor1 xs = [x | x <- xs, x == R] ++ [x | x <- xs, x == A] ++ [x | x <- xs, x == M] -- 2ª solución -- =========== banderaTricolor2 :: [Color] -> [Color] banderaTricolor2 xs = colores R ++ colores A ++ colores M where colores c = filter (== c) xs -- 3ª solución -- =========== banderaTricolor3 :: [Color] -> [Color] banderaTricolor3 xs = concat [[x | x <- xs, x == c] | c <- [R,A,M]] -- 4ª solución -- =========== banderaTricolor4 :: [Color] -> [Color] banderaTricolor4 xs = aux xs ([],[],[]) where aux [] (rs,as,ms) = rs ++ as ++ ms aux (R:ys) (rs,as,ms) = aux ys (R:rs, as, ms) aux (A:ys) (rs,as,ms) = aux ys ( rs, A:as, ms) aux (M:ys) (rs,as,ms) = aux ys ( rs, as, M:ms) -- 5ª solución -- =========== banderaTricolor5 :: [Color] -> [Color] banderaTricolor5 = sort -- Comprobación de equivalencia -- ============================ instance Arbitrary Color where arbitrary = elements [A,R,M] -- La propiedad es prop_banderaTricolor :: [Color] -> Bool prop_banderaTricolor xs = all (== banderaTricolor1 xs) [banderaTricolor2 xs, banderaTricolor3 xs, banderaTricolor4 xs, banderaTricolor5 xs] verifica_banderaTricolor :: IO () verifica_banderaTricolor = quickCheck prop_banderaTricolor -- La comprobación es -- λ> verifica_banderaTricolor -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> bandera n = concat [replicate n c | c <- [M,R,A]] -- λ> length (banderaTricolor1 (bandera (10^6))) -- 3000000 -- (1.51 secs, 1,024,454,768 bytes) -- λ> length (banderaTricolor1 (bandera (2*10^6))) -- 6000000 -- (2.94 secs, 2,048,454,832 bytes) -- λ> length (banderaTricolor2 (bandera (2*10^6))) -- 6000000 -- (2.35 secs, 1,232,454,920 bytes) -- λ> length (banderaTricolor3 (bandera (2*10^6))) -- 6000000 -- (4.28 secs, 2,304,455,360 bytes) -- λ> length (banderaTricolor4 (bandera (2*10^6))) -- 6000000 -- (3.01 secs, 1,904,454,672 bytes) -- λ> length (banderaTricolor5 (bandera (2*10^6))) -- 6000000 -- (2.47 secs, 1,248,454,744 bytes) |
El código se encuentra en GitHub.