Menu Close

División equitativa

Definir la función

   divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

   divisionEquitativa [1,2,3,4,5,15]  ==  Just ([1,2,3,4,5],[15])
   divisionEquitativa [15,1,2,3,4,5]  ==  Just ([15],[1,2,3,4,5])
   divisionEquitativa [1,2,3,4,7,15]  ==  Nothing
   divisionEquitativa [1,2,3,4,15,5]  ==  Nothing

Soluciones

import Data.Maybe (isNothing, fromJust, listToMaybe)
import Data.List  (elemIndex, inits, tails)
 
-- 1ª solución
divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa1 xs = aux (particiones xs)
 where aux []                              = Nothing
       aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)
                        | otherwise        = aux ys                   
       particiones xs = [splitAt i xs | i <- [1..length xs-1]]
 
-- 2ª solución
divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa2 xs
  | 2 * b == suma = Just $ splitAt (length as + 1) xs
  | otherwise     = Nothing
  where suma        = sum xs
        (as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs
 
-- 3ª solución
divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa3 xs
  | odd n       = Nothing
  | isNothing p = Nothing
  | otherwise   = Just (splitAt (1 + fromJust p) xs)
  where n  = sum xs
        ys = scanl1 (+) xs
        p  = elemIndex (n `div` 2) ys
 
-- 4ª solución
divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa4 xs
  | odd (sum xs) = Nothing
  | otherwise    = aux [] xs
  where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs)
                          | sum as > sum bs  = Nothing
                          | otherwise        = aux (b:as) (bs')
 
-- 5ª solución
divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa5 xs =
  listToMaybe
    [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)
              , sum ys == sum zs ]
Medio

11 soluciones de “División equitativa

  1. alerodrod5
    import Data.List
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa xs | all (==False) (map iguales (aux xs)) = Nothing
                          | otherwise = Just ( head xss, last xss)
                            where xss =busca ( aux3 xs)
     
    iguales :: [Int] -> Bool
    iguales (x:[y]) = x==y
     
    aux  :: [Int] -> [[Int]]
    aux xs = agrupa 2 (map sum (concat(init (tail (map  aux2 [splitAt n xs | n<-[0..length xs]])))))
     
    aux2 :: (a,a) ->[a]
    aux2 (x,y) = [x,y]
     
    aux3 :: [Int] -> [[[Int]]]
    aux3 xs = agrupa 2(concat(init (tail (map  aux2 [splitAt n xs | n<-[0..length xs]]))))
     
    busca xss = concat [xs | xs<- xss, iguales(map sum xs)]
     
    agrupa :: Int -> [a] -> [[a]]
    agrupa n = takeWhile (not . null)
             . map (take n)
             . iterate (drop n)
  2. guigornun
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa xs = aux (particiones xs)
     where aux [] = Nothing
           aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)
                            | otherwise        = aux ys                   
           particiones xs = [splitAt i xs | i <- [1..length xs-1]]
  3. antnavoro
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa xs
      | 2 * b == suma = Just $ splitAt (length as + 1) xs
      | otherwise     = Nothing
      where suma        = sum xs
            (as,(b:bs)) = span (< suma `div` 2) $ scanl1 (+) xs
  4. angruicam1
    import Data.List (inits, tails, find)
     
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa =
      find ((==) . sum . snd <*> sum . fst)
      . (zip . inits <*> tails)
  5. pabhueacu
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa = aux []
      where aux ys []       | sum ys == 0     = Just(ys, [])
                            | otherwise       = Nothing
            aux ys l@(x:xs) | sum ys == sum l = Just(reverse ys,l)
                            | otherwise       = aux (x:ys) xs
  6. anaagumun1
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa xs
      | last h - sum (drop (length h) xs) == 0 = Just (splitAt (aux2 xs) xs)
      | otherwise                              = Nothing
      where aux xs  = [take n xs | n <- [1..length xs]]
            k       = map sum (aux xs)
            h       = takeWhile (<= z) k
            z       = div (sum xs) 2
            aux2 xs = head [x | (x,y) <- zip [1..] k, y == z]
  7. jaibengue
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa ls | odd var   = Nothing
                          | otherwise = aux [] ls 0
       where aux xs p@(y:ys) n | n == var2 = Just (reverse xs,p)
                               | otherwise = aux (y:xs) ys (n+y)
             aux _ [] _                    = Nothing
             var  = sum ls
             var2 = var `div` 2
    • jaibengue

      Solo ligeramente más rápida teniendo en cuenta que la lista es de enteros positivos:

      divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
      divisionEquitativa ls | odd var   = Nothing
                            | otherwise = aux [] ls 0
        where aux xs p@(y:ys) n | n < var2  = aux (y:xs) ys (n+y) 
                                | n == var2 = Just (reverse xs,p)
                                | otherwise = Nothing
              aux _ [] _                    = Nothing
              var  = sum ls
              var2 = var `div` 2
  8. agumaragu1
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa (x:xs) = aux [x] xs
      where aux as bs@(b:bs') | sum as == sum bs = Just (as, bs)
                              | sum as > sum bs  = Nothing
                              | otherwise        = aux (as++[b]) (bs')
  9. Chema Cortés
    import           Data.List (inits, tails)
    import           Data.Maybe (listToMaybe)
     
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa xs =
      listToMaybe
        [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)
                  , sum ys == sum zs ]
  10. carbremor
    import Data.List.Split
    import Data.List
    import Test.Hspec
    import Data.Maybe
     
    divisionEquitativa :: [Int] -> Maybe ([Int],[Int])
    divisionEquitativa xs = find ((x, y) -> sum x == sum y) $ partirLista xs
     
    -- λ> divisionEquitativa [1,3,3,4,3]
    -- Just ([1,3,3],[4,3])
    -- (0.30 secs, 68,640 bytes)
     
    partirLista :: [a] -> [([a], [a])]
    partirLista xs = zipWith splitAt [1..(length xs)-1] $ repeat xs
     
    -- λ>  partirLista [1,2,3,4,5,15]
    -- [([1],[2,3,4,5,15]),([1,2],[3,4,5,15]),([1,2,3],[4,5,15]),([1,2,3,4],[5,15]),([1,2,3,4,5],[15])]
    -- (0.97 secs, 133,384 bytes)
     
    -- ---------------------------------------------------------------------
    -- § Verificación                                                     --
    -- ---------------------------------------------------------------------
     
    verifica :: IO ()
    verifica = hspec $ do
      describe "divisionEquitativa" $ do
        it "e1" $ do 
         divisionEquitativa [1,2,3,4,5,15] `shouldBe`
           Just ([1,2,3,4,5],[15])
        it "e2" $ do
          divisionEquitativa [15,1,2,3,4,5] `shouldBe`
            Just ([15],[1,2,3,4,5])
        it "e3" $ do
          divisionEquitativa [1,2,3,4,7,15] `shouldBe`
            Nothing
        it "e4" $ do
           divisionEquitativa [1,2,3,4,15,5] `shouldBe`
             Nothing
     
    -- λ> verifica
     
    -- divisionEquitativa
      -- e1
      -- e2
      -- e3
      -- e4
     
    -- Finished in 0.1367 seconds
    -- 4 examples, 0 failures
    (0.36 secs, 232,520 bytes)

Escribe tu solución

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