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
Pi Eva Luis Paula Alberto Francisco
su ordenación simétrica es
Pi Luis Alberto Francisco Paula Eva
Definir la función
simetrica :: [String] -> [String]
tal que (simetrica xs) es la ordenación simétrica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,
λ> 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ª 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)