Orden simétrico
Dada una lista de cadenas ordenadas por longitud, se puede ordenar de manera simétrica colocando la primera cadena en primer lugar, la segunda en el último, la tercera en el segundo, la cuarta en el penúltimo y así sucesivamente.
Por ejemplo, dada la lista
|
1 2 3 4 5 6 |
Pi Eva Luis Paula Alberto Francisco |
su ordenación simétrica es
|
1 2 3 4 5 6 |
Pi Luis Alberto Francisco Paula Eva |
Definir la función
|
1 |
simetrica :: [String] -> [String] |
tal que (simetrica xs) es la ordenación simétrica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,
|
1 2 3 4 |
λ> simetrica ["Pi","Eva","Luis","Paula","Alberto","Francisco"] ["Pi","Luis","Alberto","Francisco","Paula","Eva"] λ> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^6]] "a" |
Nota: Este ejercicio está basado en el problema Symmetric order de Kattis.
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ª definición simetrica1 :: [String] -> [String] simetrica1 [] = [] simetrica1 [x] = [x] simetrica1 (x:y:xs) = x : simetrica1 xs ++ [y] -- 2ª definición simetrica2 :: [String] -> [String] simetrica2 xs = aux xs [] where aux (x:y:xs) ys = x : aux xs (y:ys) aux (x:xs) ys = x : aux xs ys aux [] ys = ys -- 3ª definición simetrica3 :: [String] -> [String] simetrica3 xs = aux xs [] where aux (x:y:xs) ys = x : aux xs (y:ys) aux xs ys = xs ++ ys -- Comparación de eficiencia -- ========================= -- λ> minimum $ simetrica1 [replicate k 'a' | k <- [1..2*10^4]] -- "a" -- (11.30 secs, 8,600,879,688 bytes) -- λ> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^4]] -- "a" -- (0.06 secs, 12,419,568 bytes) -- λ> minimum $ simetrica3 [replicate k 'a' | k <- [1..2*10^4]] -- "a" -- (0.06 secs, 11,320,264 bytes) |