Menu Close

Centro de gravedad de una lista

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

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

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)

8 soluciones de “Centro de gravedad de una lista

  1. Chema Cortés
    import Data.List
    import Data.Maybe
     
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro xs =
      listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
                      , sum ys == sum zs]
  2. manpende
    import Data.List
     
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro xs 
         | null ys = Nothing
         | otherwise = Just $ fst (head ys)
               where l = length xs
                     ys = equilibrios xs
     
    equilibrios :: (Num a, Eq a) => [a] -> [(Int,(a,a))]
    equilibrios xs = filter ((_,(x,y)) -> x==y) $ sumas xs
     
    sumas :: (Num a, Eq a) => [a] -> [(Int,(a,a))]
    sumas [] = []
    sumas xs = zip ys [(sum $ take (n+1) xs, sum $ take (l-n) (reverse xs)) | n <- ys]
            where l = length xs
                  ys = [0..l-1]
  3. juanarcon
     
    import Data.List
     
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro xs | null ys = Nothing
              | otherwise = Just (head ys)
                            where ys = [ n | n<- [0..n-1],
                                         sum (take n xs) == sum (drop (n+1) xs)]
                                  n = length xs
  4. manvermor
     
    -- Mismo fundamento que juanarcon pero usando auxiliar y sin guardas.
     
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro xs = aux ([ n | n <- [0..length xs-1], sum (take n xs) == sum (drop (n+1) xs)])
        where aux [] = Nothing
              aux zs = Just (head zs)
  5. fracruzam

    Intentando no repetir la misma suma varias veces:

    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro (x:xs) | null ys   = Nothing
                  | otherwise = Just a
      where ys = dropWhile ((_,x,y,_) -> x /= y) $ 
                 scanl ((x,y,z,w) n -> (x+1,y+w,z-n,n)) (0,0,sum xs,x) xs
            ((a,_,_,_):_) = ys
    centro  _     = Just 0
  6. Paola Cabrera Perza
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro (x:xs)|x==sum (x:xs)=Just 0
                 |cogerHasta (x:xs)==centros (x:xs)=Nothing
                 |otherwise = Just(length(cogerHasta (x:xs))+1)
    centro1 :: (Eq a, Num a) => [a] -> Int -> Bool
    centro1 xs n = sum(take n xs)==sum(take(a-(n+1))(reverse(xs)))
                  where a =length xs
    centros :: (Eq a, Num a) => [a] -> [Bool]
    centros []=[]
    centros xs=[centro1 xs n|n<-[1..(length xs)]]
    cogerHasta :: (Eq a, Num a) => [a] -> [Bool]
    cogerHasta xs=takeWhile(/=(True))(centros xs)
  7. carmengar
    import Data.List
     
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro xs | hayCentro xs = Just $ head [k | (x,y,k) <- pares xs, x == y]
              | otherwise    = Nothing
     
    hayCentro :: (Num a, Eq a) => [a] -> Bool
    hayCentro = any ((x,y,z) -> x == y) . pares
     
     
    pares :: (Num a, Eq a) => [a] -> [(a,a,Int)]
    pares xs = (0,sum $ tail xs, 0) : [(s1 k,s2 k,k) | k <- [1..l-1]]
               where l    = length xs
                     s1 k = sum [xs !! i | i <- [0..k-1]]
                     s2 k = sum [xs !! i | i <- [k+1..l-1]]
  8. alvalvdom1
    centro :: (Num a, Eq a) => [a] -> Maybe Int
    centro (x:xs) | sum xs == 0 = Just 0
                  | otherwise = aux [x] xs 1
              where aux :: (Num a, Eq a) => [a] -> [a] -> Int -> Maybe Int
                    aux _ [] _ = Nothing
                    aux ys (z:zs) m | sum ys == sum zs = Just m
                                    | otherwise = aux (ys++[z]) zs (m+1)

Leave a Reply to Paola Cabrera Perza Cancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.