Menor prefijo con suma positiva
Definir la función
|
1 |
menorPrefijoSumaPositiva1 :: [[Int]] -> Maybe [[Int]] |
tal que (menorPrefijoSumaPositiva1 xss) es justamente el menor prejijo de xss tal que la suma de lsas sumas de sus elementos es positivo y es Nothing si tal prefijo no existe. Por ejemplo,
|
1 2 3 4 5 6 |
menorPrefijoSumaPositiva [[1],[-3],[2,4]] == Just [[1]] menorPrefijoSumaPositiva [[-2,1],[-3],[2,4]] == Just [[-2,1],[-3],[2,4]] menorPrefijoSumaPositiva [[-2,1],[3],[2,4]] == Just [[-2,1],[3]] menorPrefijoSumaPositiva [[-2,1],[-3],[2,-4]] == Nothing menorPrefijoSumaPositiva [[-k..k] | k <- [1..5000]] == Nothing fmap length (menorPrefijoSumaPositiva [[-3000..k] | k <- [0..]]) == Just 5198 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
import Data.List (inits) import Data.Maybe (listToMaybe) import Test.QuickCheck -- 1ª solución -- =========== menorPrefijoSumaPositiva1 :: [[Int]] -> Maybe [[Int]] menorPrefijoSumaPositiva1 xss = listToMaybe [xs | xs <- tail (inits xss), sum (concat xs) > 0] -- 2ª solución -- =========== menorPrefijoSumaPositiva2 :: [[Int]] -> Maybe [[Int]] menorPrefijoSumaPositiva2 xss = aux [] xss where aux yss _ | sum (concat yss) > 0 = Just (reverse yss) aux _ [] = Nothing aux yss (zs:zss) = aux (zs : yss) zss -- 3ª solución -- =========== menorPrefijoSumaPositiva3 :: [[Int]] -> Maybe [[Int]] menorPrefijoSumaPositiva3 xss = aux (0,[]) (zip (map sum xss) xss) where aux (s,yss) _ | s > 0 = Just (reverse yss) aux _ [] = Nothing aux (s,yss) ((t,zs):zss) = aux (s+t,zs:yss) zss -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equivalencia :: [[Int]] -> Bool prop_equivalencia xss = all (== (menorPrefijoSumaPositiva1 xss)) [ menorPrefijoSumaPositiva2 xss, menorPrefijoSumaPositiva3 xss ] -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- -- La comparación es -- λ> fmap length (menorPrefijoSumaPositiva1 [[-200..k] | k <- [0..]]) -- Just 348 -- (2.40 secs, 2,801,967,392 bytes) -- λ> fmap length (menorPrefijoSumaPositiva2 [[-200..k] | k <- [0..]]) -- Just 348 -- (2.46 secs, 2,800,717,720 bytes) -- λ> fmap length (menorPrefijoSumaPositiva3 [[-200..k] | k <- [0..]]) -- Just 348 -- (0.01 secs, 18,128,464 bytes) -- λ> menorPrefijoSumaPositiva1 [[-k..k] | k <- [1..500]] -- Nothing -- (6.39 secs, 6,127,124,136 bytes) -- λ> menorPrefijoSumaPositiva2 [[-k..k] | k <- [1..500]] -- Nothing -- (6.47 secs, 6,124,201,288 bytes) -- λ> menorPrefijoSumaPositiva3 [[-k..k] | k <- [1..500]] -- Nothing -- (0.03 secs, 37,944,760 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>