Índice del menor elemento a eliminar para que la suma sea divisible por K
Definir la función
1 |
indice :: [Int] -> Int -> Maybe Int |
tal que (indice xs k) es el índice del menor elemento a eliminar de la lista de enteros positivos xs para que la suma de los restantes sea divisible por k o Nothing, si no existe dicho elemento. Por ejemplo,
1 2 3 4 5 6 |
indice [1,8,4,1] 2 == Just 2 indice [4,6,7,5,7] 11 == Just 2 indice [4,6,7,5,7] 12 == Just 3 indice [4,6,7,5,7] 13 == Nothing indice [1..10^7] 7 == Just 5 indice [10^7,10^7-1..1] 7 == Just 9999994 |
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 69 70 71 72 73 |
import Test.QuickCheck import Data.List (sort) import Data.Maybe (listToMaybe) -- 1ª solución -- =========== indice :: [Int] -> Int -> Maybe Int indice xs k | null ys = Nothing | otherwise = Just (head ys) where ys = [i | (_,i,zs) <- sort (eliminaciones xs), sum zs `mod` k == 0] -- (eliminaciones xs) es la lista de ternas (x,i,zs) tales que x es un -- elemento de xs, i es la posición de x en xs y zs es la lista de los -- restantes elementos de xs. Por ejemplo, -- λ> eliminaciones [5,7,6,5] -- [(5,0,[7,6,5]),(7,1,[5,6,5]),(6,2,[5,7,5]),(5,3,[5,7,6])] eliminaciones :: [a] -> [(a,Int,[a])] eliminaciones xs = [(z,i,zs) | ((z,zs),i) <- zip (aux xs) [0..]] where aux [] = [] aux [x] = [(x,[])] aux (x:y:zs) = (x,y:zs) : [(v,x:vs) | (v,vs) <- aux (y:zs)] -- 2ª solución -- =========== indice2 :: [Int] -> Int -> Maybe Int indice2 xs k | null ys = Nothing | otherwise = Just (head ys) where d = sum xs `mod` k ys = [i | (x,i) <- sort (zip xs [0..]), x `mod` k == d] -- 3ª solución -- =========== indice3 :: [Int] -> Int -> Maybe Int indice3 xs k = listToMaybe ys where d = sum xs `mod` k ys = [i | (x,i) <- sort (zip xs [0..]), x `mod` k == d] -- Comprobación de la equivalencia -- =============================== -- La propiedad es prop_equivalencia :: [Int] -> Int -> Bool prop_equivalencia xs k = indice xs' k' == indice2 xs' k' && indice2 xs' k' == indice3 xs' k' where xs' = map ((+1) . abs) xs k' = 1 + abs k -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> indice [1..5000] 7 -- Just 2 -- (2.82 secs, 2,458,555,104 bytes) -- λ> indice2 [1..5000] 7 -- Just 2 -- (0.01 secs, 1,991,232 bytes) -- λ> indice3 [1..5000] 7 -- Just 2 -- (0.01 secs, 1,991,072 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>
La definición es incorrecta. Por ejemplo,