Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.
Definir la función
centro :: (Num a, Eq a) => [a] -> Maybe Int |
centro :: (Num a, Eq a) => [a] -> Maybe Int
tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,
centro [1,3,4,5,-2,1] == Just 2
centro [1,6,4,5,-2,1] == Nothing
centro [1,2,3,4,3,2,1] == Just 3
centro [1,100,50,-51,1,1] == Just 1
centro [1,2,3,4,5,6] == Nothing
centro [20,10,30,10,10,15,35] == Just 3
centro [20,10,-80,10,10,15,35] == Just 0
centro [10,-80,10,10,15,35,20] == Just 6
centro [0,0,0,0,0] == Just 0
centro [-1,-2,-3,-4,-3,-2,-1] == Just 3 |
centro [1,3,4,5,-2,1] == Just 2
centro [1,6,4,5,-2,1] == Nothing
centro [1,2,3,4,3,2,1] == Just 3
centro [1,100,50,-51,1,1] == Just 1
centro [1,2,3,4,5,6] == Nothing
centro [20,10,30,10,10,15,35] == Just 3
centro [20,10,-80,10,10,15,35] == Just 0
centro [10,-80,10,10,15,35,20] == Just 6
centro [0,0,0,0,0] == Just 0
centro [-1,-2,-3,-4,-3,-2,-1] == Just 3
Soluciones
import Data.List (inits, tails)
import Data.Maybe (listToMaybe)
-- 1ª solución
-- ===========
centro1 :: (Num a, Eq a) => [a] -> Maybe Int
centro1 xs
| null ns = Nothing
| otherwise = Just (head ns)
where ns = [n | n <- [0..length xs - 1],
let (ys,_:zs) = splitAt n xs,
sum ys == sum zs]
-- 2ª solución
-- ===========
centro2 :: (Num a, Eq a) => [a] -> Maybe Int
centro2 xs = aux 0 0 (sum xs) xs where
aux _ _ _ [] = Nothing
aux k i d (z:zs) | i == d - z = Just k
| otherwise = aux (k + 1) (i + z) (d - z) zs
-- 3ª solución
-- ===========
centro3 :: (Num a, Eq a) => [a] -> Maybe Int
centro3 xs =
listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
, sum ys == sum zs]
-- Comparación de eficiencia
-- =========================
-- λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))
-- Just 3000
-- (2.70 secs, 2,088,881,728 bytes)
-- λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))
-- Just 3000
-- (0.03 secs, 0 bytes)
-- λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))
-- Just 3000
-- (2.34 secs, 1,727,569,688 bytes) |
import Data.List (inits, tails)
import Data.Maybe (listToMaybe)
-- 1ª solución
-- ===========
centro1 :: (Num a, Eq a) => [a] -> Maybe Int
centro1 xs
| null ns = Nothing
| otherwise = Just (head ns)
where ns = [n | n <- [0..length xs - 1],
let (ys,_:zs) = splitAt n xs,
sum ys == sum zs]
-- 2ª solución
-- ===========
centro2 :: (Num a, Eq a) => [a] -> Maybe Int
centro2 xs = aux 0 0 (sum xs) xs where
aux _ _ _ [] = Nothing
aux k i d (z:zs) | i == d - z = Just k
| otherwise = aux (k + 1) (i + z) (d - z) zs
-- 3ª solución
-- ===========
centro3 :: (Num a, Eq a) => [a] -> Maybe Int
centro3 xs =
listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
, sum ys == sum zs]
-- Comparación de eficiencia
-- =========================
-- λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))
-- Just 3000
-- (2.70 secs, 2,088,881,728 bytes)
-- λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))
-- Just 3000
-- (0.03 secs, 0 bytes)
-- λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))
-- Just 3000
-- (2.34 secs, 1,727,569,688 bytes)