Índice del menor elemento a eliminar para que la suma sea divisible por K

PorJosé A. Alonso 1-marzo-20218-marzo-2021

Definir la función

   indice :: [Int] -> Int -> Maybe Int

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,

   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

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

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)

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>

5 Comentarios

-- 1ª Definición:
-- =============

indice1 :: [Int] -> Int -> Maybe Int
indice1 xs k
  | null listaAuxiliar = Nothing
  | otherwise          = Just (pos (minimum listaAuxiliar) xs)
      where listaAuxiliar = aux1 xs k (sum xs)

-- aux1 es la lista de los elementos x de xs tales que n-x es divisible por
-- k. Por ejemplo,
--   λ> aux1 [3,7,5,2] 2 17
--   [3,7,5]

aux1 :: [Int] -> Int -> Int -> [Int]
aux1 xs k n = [x | x <- xs, mod (n-x) k == 0]

-- pos y xs es la posición del elemento y en la lista xs. Para la función
-- indice1 en este caso no es necesario definir el caso base en el que y no
-- pertenece a xs. Por ejemplo,
--   λ> pos 4 [1..10]
--   3

pos :: Int -> [Int] -> Int
pos y (x:xs)
  | y == x    = 0
  | otherwise = 1 + pos y xs

-- 2ª Definición:
-- =============

indice2 :: [Int] -> Int -> Maybe Int
indice2 xs k
  | null listaAuxiliar = Nothing
  | otherwise          = Just (snd (minimum listaAuxiliar))
      where listaAuxiliar = aux2 xs k (sum xs)

-- aux2 xs k n es la lista de pares (x,i) tales que n-x es divisible por k,
-- siendo i la posición de cada elemento x que satisface dicha condición. Por
-- ejemplo,
--   λ> aux2 [3,7,5,2] 2 17
--   [(3,0),(7,1),(5,2)]

aux2 :: [Int] -> Int -> Int -> [(Int,Int)]
aux2 xs k n = [(x,i) | (x,i) <- zip xs [0..], mod (n-x) k == 0]

-- Comparación de eficiencia:
-- =========================

-- Ambas funciones tardan bastante en calcular los dos últimos ejemplos. Se
-- observa además que la eficiencia de indice1 varía en gran medida en función
-- de cuál sea la posición buscada, mientras que indice2 parece tener una
-- eficiencia independiente de dicha posición.
--   λ> indice1 [1..10^7] 7
--   Just 5
--   (10.40 secs, 3,979,876,384 bytes)
--   λ> indice2 [1..10^7] 7
--   Just 5
--   (13.43 secs, 5,637,884,632 bytes)
--   λ> indice1 [10^7,10^7-1..1] 7
--   Just 9999994
--   (17.01 secs, 6,244,765,128 bytes)
--   λ> indice2 [10^7,10^7-1..1] 7
--   Just 9999994
--   (13.69 secs, 5,637,890,520 bytes)

-- 1ª Definición:

-- =============

indice1 :: [Int] -> Int -> Maybe Int

indice1 xs k

| null listaAuxiliar = Nothing

| otherwise = Just (pos (minimum listaAuxiliar) xs)

where listaAuxiliar = aux1 xs k (sum xs)

-- aux1 es la lista de los elementos x de xs tales que n-x es divisible por

-- k. Por ejemplo,

-- λ> aux1 [3,7,5,2] 2 17

-- [3,7,5]

aux1 :: [Int] -> Int -> Int -> [Int]

aux1 xs k n = [x | x <- xs, mod (n-x) k == 0]

-- pos y xs es la posición del elemento y en la lista xs. Para la función

-- indice1 en este caso no es necesario definir el caso base en el que y no

-- pertenece a xs. Por ejemplo,

-- λ> pos 4 [1..10]

-- 3

pos :: Int -> [Int] -> Int

pos y (x:xs)

| y == x = 0

| otherwise = 1 + pos y xs

-- 2ª Definición:

-- =============

indice2 :: [Int] -> Int -> Maybe Int

indice2 xs k

| null listaAuxiliar = Nothing

| otherwise = Just (snd (minimum listaAuxiliar))

where listaAuxiliar = aux2 xs k (sum xs)

-- aux2 xs k n es la lista de pares (x,i) tales que n-x es divisible por k,

-- siendo i la posición de cada elemento x que satisface dicha condición. Por

-- ejemplo,

-- λ> aux2 [3,7,5,2] 2 17

-- [(3,0),(7,1),(5,2)]

aux2 :: [Int] -> Int -> Int -> [(Int,Int)]

aux2 xs k n = [(x,i) | (x,i) <- zip xs [0..], mod (n-x) k == 0]

-- Comparación de eficiencia:

-- =========================

-- Ambas funciones tardan bastante en calcular los dos últimos ejemplos. Se

-- observa además que la eficiencia de indice1 varía en gran medida en función

-- de cuál sea la posición buscada, mientras que indice2 parece tener una

-- eficiencia independiente de dicha posición.

-- λ> indice1 [1..10^7] 7

-- Just 5

-- (10.40 secs, 3,979,876,384 bytes)

-- λ> indice2 [1..10^7] 7

-- Just 5

-- (13.43 secs, 5,637,884,632 bytes)

-- λ> indice1 [10^7,10^7-1..1] 7

-- Just 9999994

-- (17.01 secs, 6,244,765,128 bytes)

-- λ> indice2 [10^7,10^7-1..1] 7

-- Just 9999994

-- (13.69 secs, 5,637,890,520 bytes)

Responder

import Data.Maybe
import Data.List

indice :: [Int] -> Int -> Maybe Int
indice xs x | eliminaDivisible xs x == [] = Nothing
            | otherwise                   = Just (minimo (eliminaDivisible xs x))

eliminaDivisible :: [Int] -> Int -> [(Int,Int)]
eliminaDivisible [] x = []
eliminaDivisible xs x = [(y,n) | (y,n) <- zip xs [0..], rem (sum (delete y xs)) x == 0]

minimo :: [(Int,Int)] -> Int
minimo [] = (-1)
minimo xs = snd (head [(y,n) | (y,n) <- xs , y== minimum (map fst xs)])

import Data.Maybe

import Data.List

indice :: [Int] -> Int -> Maybe Int

indice xs x | eliminaDivisible xs x == [] = Nothing

| otherwise = Just (minimo (eliminaDivisible xs x))

eliminaDivisible :: [Int] -> Int -> [(Int,Int)]

eliminaDivisible [] x = []

eliminaDivisible xs x = [(y,n) | (y,n) <- zip xs [0..], rem (sum (delete y xs)) x == 0]

minimo :: [(Int,Int)] -> Int

minimo [] = (-1)

minimo xs = snd (head [(y,n) | (y,n) <- xs , y== minimum (map fst xs)])

Responder

import Data.List

indiceA4 :: [Int] -> Int -> Maybe Int
indiceA4 xs k  | null t = Nothing
               |otherwise = Just (head t)
  where t = indices xs k

-- indices xs k es la lista de los  índices de los elementos de xs tales que al ser
-- eliminados, la suma de los restantes es múltiplo de k
--    λ> indices [4,6,7,5,7] 11
--    [2,4]
indices xs k =  [i | (x,i) <- ys ,(t-x) `mod`k == 0]
  where t  = sumaConPatron xs
        ys = sort (zip xs [0..])

-- sumaConPatron xs es la suma de la lista xs, calculándola por la fórmula de la
-- progresión aritmética en caso de que se pueda
--    λ> sumaConPatron [1..10^7]
--    50000005000000
sumaConPatron xs | x:y:ys == [x,y..z] = (x + z)*(length xs) `div` 2
                 | otherwise          = sum xs
  where (x:y:ys) = xs
        z        = last xs

import Data.List

indiceA4 :: [Int] -> Int -> Maybe Int

indiceA4 xs k | null t = Nothing

|otherwise = Just (head t)

where t = indices xs k

-- indices xs k es la lista de los índices de los elementos de xs tales que al ser

-- eliminados, la suma de los restantes es múltiplo de k

-- λ> indices [4,6,7,5,7] 11

-- [2,4]

indices xs k = [i | (x,i) <- ys ,(t-x) `mod`k == 0]

where t = sumaConPatron xs

ys = sort (zip xs [0..])

-- sumaConPatron xs es la suma de la lista xs, calculándola por la fórmula de la

-- progresión aritmética en caso de que se pueda

-- λ> sumaConPatron [1..10^7]

-- 50000005000000

sumaConPatron xs | x:y:ys == [x,y..z] = (x + z)*(length xs) `div` 2

| otherwise = sum xs

where (x:y:ys) = xs

z = last xs

Responder

José A. Alonso dice:

2-marzo-2021 a las 09:14

La definición es incorrecta. Por ejemplo,

λ> indice [1] 1 *** Exception: Irrefutable pattern failed for pattern x : y : ys

1
2

λ> indice [1] 1
*** Exception: Irrefutable pattern failed for pattern x : y : ys

Responder

-- La funcion quedaria: 
indice :: [Int] -> Int -> Maybe Int
indice xs k | not (algunoDivisible ys k) = Nothing
            | otherwise  =  Just (posicion (maximum (listaDivisibles ys k)) ys)
 where ys = sumaCombinaciones xs



-- La funcion posicion x xs da el lugar en el que se encuentra el elemento x en
-- la lista xs. Por ejemplo:
-- posicion 8 [1..8] == 7

posicion :: Int -> [Int] -> Int
posicion k (x:xs) | k == x    = 0
                  | otherwise = 1 + posicion k xs

                  
-- La funcion algunoDivisible verifica si algun elemento de la lista es
-- divisible entre y. La funcion listaDivisibles toma ese elemento.
-- algunoDivisible [1..5] 2 == True
-- listaDivisibles [1..5] 2 == [2,4]

listaDivisibles :: [Int] -> Int -> [Int]
listaDivisibles []     _                = []
listaDivisibles (x:xs) y | mod x y == 0 = x :(listaDivisibles xs y)
                         | otherwise    = listaDivisibles xs y


algunoDivisible []     _ = False
algunoDivisible (x:xs) y | mod x y == 0 = True
                         | otherwise    = algunoDivisible xs y

-- Con sumaCombinaciones, por su parte, obtenemos la suma de los elementos de las distintas
-- listas formadas con combinaciones. 
sumaCombinaciones :: [Int] -> [Int]
sumaCombinaciones xs = map sum (combinaciones xs) 


-- Por otro lado, la funcion combinaciones nos da las distintas listas que se pueden forman
-- quitando un elemento de la lista original xs. Por ejemplo:
-- combinaciones [1..4] == [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]
combinaciones :: [a] -> [[a]]
combinaciones xs = [elimina n xs | n <- [1..p]]
 where p = length xs

-- Por ultimo, la funcion elimina n xs elimina el n-esimo elemento de la lista xs. Por
-- ejemplo:
-- elimina 5 [1..7] == [1,2,3,4,6,7]
-- elimina 3 [4..8] == [4,5,7,8]
elimina :: (Eq t, Num t) => t -> [a] -> [a]
elimina _ []     = []
elimina n (x:xs) | n == 1    = xs
                 | otherwise = x: elimina (n-1) xs

-- La funcion quedaria:

indice :: [Int] -> Int -> Maybe Int

indice xs k | not (algunoDivisible ys k) = Nothing

| otherwise = Just (posicion (maximum (listaDivisibles ys k)) ys)

where ys = sumaCombinaciones xs

-- La funcion posicion x xs da el lugar en el que se encuentra el elemento x en

-- la lista xs. Por ejemplo:

-- posicion 8 [1..8] == 7

posicion :: Int -> [Int] -> Int

posicion k (x:xs) | k == x = 0

| otherwise = 1 + posicion k xs

-- La funcion algunoDivisible verifica si algun elemento de la lista es

-- divisible entre y. La funcion listaDivisibles toma ese elemento.

-- algunoDivisible [1..5] 2 == True

-- listaDivisibles [1..5] 2 == [2,4]

listaDivisibles :: [Int] -> Int -> [Int]

listaDivisibles [] _ = []

listaDivisibles (x:xs) y | mod x y == 0 = x :(listaDivisibles xs y)

| otherwise = listaDivisibles xs y

algunoDivisible [] _ = False

algunoDivisible (x:xs) y | mod x y == 0 = True

| otherwise = algunoDivisible xs y

-- Con sumaCombinaciones, por su parte, obtenemos la suma de los elementos de las distintas

-- listas formadas con combinaciones.

sumaCombinaciones :: [Int] -> [Int]

sumaCombinaciones xs = map sum (combinaciones xs)

-- Por otro lado, la funcion combinaciones nos da las distintas listas que se pueden forman

-- quitando un elemento de la lista original xs. Por ejemplo:

-- combinaciones [1..4] == [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]

combinaciones :: [a] -> [[a]]

combinaciones xs = [elimina n xs | n <- [1..p]]

where p = length xs

-- Por ultimo, la funcion elimina n xs elimina el n-esimo elemento de la lista xs. Por

-- ejemplo:

-- elimina 5 [1..7] == [1,2,3,4,6,7]

-- elimina 3 [4..8] == [4,5,7,8]

elimina :: (Eq t, Num t) => t -> [a] -> [a]

elimina _ [] = []

elimina n (x:xs) | n == 1 = xs

| otherwise = x: elimina (n-1) xs

Responder

Índice del menor elemento a eliminar para que la suma sea divisible por K

Soluciones

Nuevas soluciones

5 Comentarios

Leave a Reply to Alejandro García AlcaideCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

5 Comentarios

Leave a Reply to Alejandro García AlcaideCancel reply

Entradas recientes

Buscar

Correo electrónico