Menu Close

Posiciones de equilibrio

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)
Posted in Avanzado

8 Comments

  1. Cescarde
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
    equilibrios [] = []
    equilibrios xs = [i-1 | (x,i) <- zip xs [1..], sumaParticiones i xs]
      where sumaParticiones i [] = False
            sumaParticiones 0 xs = False
            sumaParticiones i xs =
              sum (init (fst (splitAt i xs))) == sum (snd (splitAt i xs))
  2. paumacpar

    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]

  3. enrnarbej
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
    equilibrios xs = aux 0 0 (sum xs) xs
      where
        aux _ _ _ [] = []
        aux p si sd (x:xs)
          | si == sd - x = p : aux (p + 1) (si + x) (sd - x) xs
          | otherwise    =     aux (p + 1) (si + x) (sd - x) xs
  4. albcercid
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
    equilibrios [] = []
    equilibrios (x:xs) = auxEq 0 (sum xs) 0 (x:xs)
      where auxEq a b c [x] | a == b = [c]
                            | otherwise = []
            auxEq a b c (x:y:xs)
              | a == b    = c : auxEq (a+x) (b-y) (c+1) (y:xs)
              | otherwise =     auxEq (a+x) (b-y) (c+1) (y:xs)
  5. josejuan
    equilibrios xs = [i | (i, a, b) <- zip3 [0..] (scanl1 (+) xs) (scanr1 (+) xs), a == b]
  6. Juanjo Ortega (juaorture)
     
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
    equilibrios xs = [x | a <- xs, let x = posicion a xs
                       , sum [xs!!b | b <- [0..x]] == sum [xs!!c | c <- [x..length xs - 1]]]
     
    posicion :: Eq a => a -> [a] -> Int
    posicion a (x:xs) | not ( a `elem` (x:xs)) = undefined
                      | a == x = 0
                      | otherwise = 1 + posicion a xs
     
    eMonotona :: Ord a => [a] -> Bool
    eMonotona (x:y:xs) = eCreciente xs || eDecreciente xs
     
    eCreciente :: Ord a => [a] -> Bool
    eCreciente (x:y:xs) = x < y && eCreciente (y:xs)
    eCreciente _        = True
     
    eDecreciente :: Ord a => [a] -> Bool
    eDecreciente (x:y:xs) = x > y && eDecreciente (y:xs)
    eDecreciente _        = True
     
    equilibrios' :: (Ord a, Eq a, Num a) => [a] -> [Int]
    equilibrios' xs | eMonotona xs = []
                    | otherwise    = equilibrios xs
  7. Pablo Rabán
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
    equilibrios [] = []
    equilibrios xs =
      [n | n <- [1..(length xs - 1)] 
         , sum (take n xs) == sum (drop (n+1) xs)]
     
    -- Inspirándome en la definición de juaorture, completo mi primera definición
    -- añadiendo el concepto de monotonía, que mejora el rendimiento notablemente.
     
    equilibrios2 :: (Ord a, Num a, Eq a) => [a] -> [Int]
    equilibrios2 [] = []
    equilibrios2 xs
      | creciente xs || decreciente xs = []
      | otherwise                      = equilibrios xs
     
    creciente :: Ord a => [a] -> Bool
    creciente (x:y:xs) = x < y && creciente (y:xs)
    creciente _        = True
     
    decreciente :: Ord a => [a] -> Bool
    decreciente (x:y:xs) = x > y && decreciente (y:xs)
    decreciente _        = True
  8. Chema Cortés
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
    equilibrios []     = []
    equilibrios (x:xs) = [ i | (izq,der,i) <- zip3 izqs ders [0..]
                             , izq == der ]
        where izqs = scanl (+) 0 (x:xs)
              ders = scanl (-) (sum xs) xs

Escribe tu solución

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