Se dice que k es una posición de equilibrio de una lista xs si la suma de los elementos de xs en las posiciones menores que k es igual a la suma de los elementos de xs en las posiciones mayores que k. Por ejemplo, en la lista [-7,1,5,2,-4,3,0] el 3 es una posición de equilibrio ya que -7+1+5 = -4+3+0; también lo es el 6 ya que -7+1+5+2+(-4)+3 = 0.
Definir la función,
equilibrios :: (Num a, Eq a) => [a] -> [Int] |
tal que (equilibrios xs) es la lista de las posiciones de equilibrio de xs. Por ejemplo,
equilibrios [-7,1,5,2,-4,3,0] == [3,6] equilibrios [1..10^6] == [] |
Soluciones
-- 1ª definición -- ============= equilibrios1 :: (Num a, Eq a) => [a] -> [Int] equilibrios1 xs = [n | n <- [0..length xs - 1] , sum (take n xs) == sum (drop (n+1) xs)] -- 2ª definición -- ============= equilibrios2 :: (Num a, Eq a) => [a] -> [Int] equilibrios2 xs = [n | (n,x,y) <- zip3 [0..] (sumasI xs) (sumasD xs) , x == y] sumasI :: (Num a, Eq a) => [a] -> [a] sumasI xs = [sum (take n xs) | n <- [0..length xs - 1]] sumasD :: (Num a, Eq a) => [a] -> [a] sumasD xs = [sum (drop (n+1) xs) | n <- [0..length xs - 1]] -- 3ª definición -- ============= equilibrios3 :: (Num a, Eq a) => [a] -> [Int] equilibrios3 xs = [n | (n,x,y) <- zip3 [0..] (sumasI' xs) (sumasD' xs) , x == y] sumasI' :: (Num a, Eq a) => [a] -> [a] sumasI' = init . scanl (+) 0 sumasD' :: (Num a, Eq a) => [a] -> [a] sumasD' = tail . scanr (+) 0 -- 4ª definición -- ============= equilibrios4 :: (Num a, Eq a) => [a] -> [Int] equilibrios4 xs = [n | (n,x,y) <- zip3 [0..] (scanl1 (+) xs) (scanr1 (+) xs) , x == y] -- Comparación de eficiencia -- λ> let xs = [1..10^4] in equilibrios1 (xs ++ [5] ++ reverse xs) -- [10000] -- (20.92 secs, 46,240,541,256 bytes) -- λ> let xs = [1..10^4] in equilibrios2 (xs ++ [5] ++ reverse xs) -- [10000] -- (21.12 secs, 46,249,562,520 bytes) -- λ> let xs = [1..10^4] in equilibrios3 (xs ++ [5] ++ reverse xs) -- [10000] -- (0.02 secs, 11,858,768 bytes) -- λ> let xs = [1..10^4] in equilibrios4 (xs ++ [5] ++ reverse xs) -- [10000] -- (0.02 secs, 13,963,952 bytes) |
equilibrios :: [Int] -> [Int]
equilibrios xs = [ t | ((n,v),t) [(Int,Int)]
sumas xs = zip (sumasIzquierdas xs) (sumasDerechas xs)
sumasIzquierdas :: [Int] -> [Int]
sumasIzquierdas xs = map sum (map fst (divisiones xs ++ [(init xs, [])]))
sumasDerechas :: [Int] -> [Int]
sumasDerechas xs = map sum (map snd (divisiones xs ++ [(init xs, [])]))
divisiones :: [Int] -> [([Int],[Int])]
divisiones [] = []
divisiones [_] = []
divisiones (x:xs) = ([],xs) : [(x: is,ds) | (is,ds) <- divisiones xs]