Menu Close

Etiqueta: divMod

Búsqueda de la mina

En este ejercicio, se representa un mapa mediante una lista de listas de la misma longitud donde todos sus elementos son 0 menos uno (que es un 1) que es donde se encuentra la mina. Por ejemplo, en el mapa

   0 0 0 0
   0 0 0 0
   0 1 0 0

la posición de la mina es (2,1).

Definir la función

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

tal que (posicionMina m) es la posición de la mina en el mapa m, Por ejemplo,

   posicionMina [[0,0,0,0],[0,0,0,0],[0,1,0,0]]  ==  (2,1)

Soluciones

import Data.List (elemIndex)
import Data.Array (assocs, listArray)
 
-- 1ª solución
posicionMina :: [[Int]] -> (Int,Int)
posicionMina xss = (length yss, length ys)
  where (yss,xs:_) = break (1 `elem`) xss
        ys         = takeWhile (/= 1) xs
 
-- 2ª solución
posicionMina2 :: [[Int]] -> (Int,Int)
posicionMina2 xss = divMod p (length (head xss))
  where Just p = elemIndex 1 (concat xss)
 
-- 3ª solución
posicionMina3 :: [[Int]] -> (Int,Int)
posicionMina3 xss =
  (fst . head . filter ((1 ==) . snd) . assocs) a
  where m = length xss - 1
        n = length (head xss) - 1
        a = listArray ((0,0),(m,n)) (concat xss)

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

“La vida de un matemático está dominada por una insaciable curiosidad, un deseo que raya en la pasión por resolver los problemas que estudia.”

Jean Dieudonné.

Aritmética lunar

En la aritmética lunar la suma y el producto se hace como en la terrícola salvo que sus tablas de sumar y de multiplicar son distintas. La suma lunar de dos dígitos es su máximo (por ejemplo, 1 + 3 = 3 y 7 + 4 = 7) y el producto lunar de dos dígitos es su mínimo (por ejemplo, 1 x 3 = 1 y 7 x 4 = 4). Por tanto,

     3 5 7        3 5 7
   +   6 4      x   6 4
   -------      -------
     3 6 7        3 4 4
                3 5 6
                -------
                3 5 6 4

Definir las funciones

   suma     :: Integer -> Integer -> Integer
   producto :: Integer -> Integer -> Integer

tales que

  • (suma x y) es la suma lunar de x e y. Por ejemplo,
     suma 357 64  ==  367
     suma 64 357  ==  367
     suma 1 3     ==  3
     suma 7 4     ==  7
  • (producto x y) es el producto lunar de x e y. Por ejemplo,
     producto 357 64  ==  3564
     producto 64 357  ==  3564
     producto 1 3     ==  1
     producto 7 4     ==  4

Comprobar con QuickCheck que la suma y el producto lunar son conmutativos.

Soluciones

import Test.QuickCheck
 
suma :: Integer -> Integer -> Integer
suma 0 0 = 0
suma x y = max x2 y2 + 10 * suma x1 y1
  where (x1,x2) = x `divMod` 10
        (y1,y2) = y `divMod` 10
 
producto :: Integer -> Integer -> Integer
producto 0 _ = 0
producto x y = productoDigitoNumero x2 y `suma` (10 * producto x1 y)
  where (x1, x2) = x `divMod` 10
 
-- (productoDigitoNumero d x) es el producto del dígito d por el número
-- x. Por ejemplo,
--    productoDigitoNumero 4 357  ==  344
--    productoDigitoNumero 6 357  ==  356
productoDigitoNumero :: Integer -> Integer -> Integer
productoDigitoNumero _ 0 = 0
productoDigitoNumero d x = min d x2 + 10 * productoDigitoNumero d x1
  where (x1, x2) = x `divMod` 10
 
-- La propiedad es
prop_conmutativa :: Positive Integer -> Positive Integer -> Bool
prop_conmutativa (Positive x) (Positive y) =
  suma x y == suma y x &&
  producto x y == producto y x
 
-- La comprobación es
--    λ> quickCheck prop_conmutativa
--    +++ OK, passed 100 tests.

Pensamiento

Cantad conmigo en coro: saber, nada sabemos,
de arcano mar vinimos, a ignota mar iremos …
La luz nada ilumina y el sabio nada enseña.
¿Qué dice la palabra? ¿Qué el agua de la peña?

Antonio Machado

Suma de los dígitos de las repeticiones de un número

Dados dos números naturales n y x, su suma reducida se obtiene a partir del número obtenido repitiendo n veces el x sumando sus dígitos hasta obtener un número con sólo un dígito. Por ejemplo, si n es 3 y x es 24 las transformaciones son

   242424 ==> 18 ==> 9

Análogamente, si n es 4 y x es 7988 las transformaciones son

   7988798879887988 ==> 128 ==> 11 ==> 2

Definir las funciones

   sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
   grafica                         :: Integer -> IO ()

tales que

  • (sumaReducidaDigitosRepeticiones n x) es la suma reducida de n repeticiones de x. Por ejemplo
     sumaReducidaDigitosRepeticiones 3 24                    ==  9
     sumaReducidaDigitosRepeticiones 4 7988                  == 2
     sumaReducidaDigitosRepeticiones (12^(10^7)) (12^(10^7)) == 9
  • (grafica n) dibuja la gráfica de los n primeros elementos de la sucesión cuyo elementos k-ésimo es (sumaReducidaDigitosRepeticiones k k). Por ejemplo, (grafica 50) dibuja
    Suma_de_los_digitos_de_las_repeticiones_de_un_numero50

Soluciones

import Data.List (genericReplicate)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
sumaReducidaDigitosRepeticiones n x =
  sumaReducidaDigitos (repeticiones n x) 
 
-- (repeticiones n x) es el número obtenido repitiendo n veces el x. Por
-- ejemplo, 
--    repeticiones 3 24   ==  242424
--    repeticiones 4 325  ==  325325325325
repeticiones :: Integer -> Integer -> Integer
repeticiones n x = read (concat (genericReplicate n (show x)))
 
-- (sumaDigitos x) es la suma de los dígitos de x. Por ejemplo,
--    sumaDigitos 325  ==  10
sumaDigitos :: Integer -> Integer
sumaDigitos x | x < 10    = x
              | otherwise = b + sumaDigitos a
  where (a,b) = divMod x 10
 
-- (sumaReducidaDigitos x) es el número obtenido a partir de x
-- reiterando la suma de los dígitos hasta obtener un número con sólo un
-- dígito. Por ejemplo,
--    sumaReducidaDigitos 24   ==  6
--    sumaReducidaDigitos 325  ==  1
sumaReducidaDigitos :: Integer -> Integer
sumaReducidaDigitos x | x < 10    = x
                      | otherwise = sumaReducidaDigitos (sumaDigitos x)
 
-- 2ª solución
-- ===========
 
sumaReducidaDigitosRepeticiones2 :: Integer -> Integer -> Integer
sumaReducidaDigitosRepeticiones2 n x =
  sumaReducidaDigitos2 (n * sumaReducidaDigitos2 x) 
 
sumaReducidaDigitos2 :: Integer -> Integer
sumaReducidaDigitos2 0 = 0
sumaReducidaDigitos2 x | y == 0    = 9
                       | otherwise = y
  where y = x `mod` 9
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_equiv :: Positive Integer -> Positive Integer -> Bool
prop_equiv (Positive n) (Positive x) =
  sumaReducidaDigitosRepeticiones n x == sumaReducidaDigitosRepeticiones2 n x 
 
-- La comprobación es
--    λ> quickCheck prop_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaReducidaDigitosRepeticiones (10^4) (10^4)
--    1
--    (2.00 secs, 574,667,384 bytes)
--    λ> sumaReducidaDigitosRepeticiones2 (10^4) (10^4)
--    1
--    (0.03 secs, 141,120 bytes)
 
-- Gráfica
-- =======
 
grafica :: Integer -> IO ()
grafica n =
  plotList [Key Nothing]
           [sumaReducidaDigitosRepeticiones2 k k | k <- [1..n]]

Menor con suma de dígitos dada

Definir la función

   minSumDig :: Integer -> Integer

tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,

  minSumDig 1   ==  1
  minSumDig 12  ==  39
  minSumDig 21  ==  399
  (length . show . minSumDig) (3*10^5)  ==  33334
  (length . show . minSumDig) (3*10^6)  ==  333334
  (length . show . minSumDig) (3*10^7)  ==  3333334
  (length . show . minSumDig) (4*10^7)  ==  4444445
  (length . show . minSumDig) (5*10^7)  ==  5555556

Soluciones

import Data.List (genericIndex)
 
-- 1ª definición
-- =============
 
minSumDig1 :: Integer -> Integer
minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n]
 
sumaDigitos :: Integer -> Integer
sumaDigitos n | n < 10    = n
              | otherwise = y + sumaDigitos x
  where (x, y) = divMod n 10
 
-- 2ª definición
minSumDig2 :: Integer -> Integer
minSumDig2 n | n < 10    = n
             | otherwise = 9 + 10 * minSumDig2 (n - 9) 
 
-- 3ª definición
minSumDig3 :: Integer -> Integer
minSumDig3 n = (r + 1) * 10^d - 1
  where (d,r) = divMod n 9
 
-- Comparación de eficiencia
-- =========================
 
--    λ> minSumDig1 46
--    199999
--    (3.21 secs, 542,721,696 bytes)
--    λ> minSumDig2 46
--    199999
--    (0.01 secs, 142,056 bytes)
--    λ> minSumDig3 46
--    199999
--    (0.01 secs, 155,984 bytes)
--    
--    λ> (length . show . minSumDig2) (3*10^5)
--    33334
--    (1.79 secs, 492,200,376 bytes)
--    λ> (length . show . minSumDig3) (3*10^5)
--    33334
--    (0.11 secs, 50,119,840 bytes)

Biparticiones de un número

Definir la función

   biparticiones :: Integer -> [(Integer,Integer)]

tal que (biparticiones n) es la lista de pares de números formados por las primeras cifras de n y las restantes. Por ejemplo,

   biparticiones  2025  ==  [(202,5),(20,25),(2,25)]
   biparticiones 10000  ==  [(1000,0),(100,0),(10,0),(1,0)]

Soluciones

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
biparticiones1 :: Integer -> [(Integer,Integer)]
biparticiones1 x = [(read y, read z) | (y,z) <- biparticionesL1 xs]
  where xs = show x
 
-- (biparticionesL1 xs) es la lista de los pares formados por los
-- prefijos no vacío de xs y su resto. Por ejemplo,
--    biparticionesL1 "2025" == [("2","025"),("20","25"),("202","5")]
biparticionesL1 :: [a] -> [([a],[a])]
biparticionesL1 xs = [splitAt k xs | k <- [1..length xs - 1]]
 
-- 2ª solución
-- ===========
 
biparticiones2 :: Integer -> [(Integer,Integer)]
biparticiones2 x = [(read y, read z) | (y,z) <- biparticionesL2 xs]
  where xs = show x
 
-- (biparticionesL2 xs) es la lista de los pares formados por los
-- prefijos no vacío de xs y su resto. Por ejemplo,
--    biparticionesL2 "2025" == [("2","025"),("20","25"),("202","5")]
biparticionesL2 :: [a] -> [([a],[a])]
biparticionesL2 xs =
  takeWhile (not . null . snd) [splitAt n xs | n <- [1..]]
 
-- 3ª solución
-- ===========
 
biparticiones3 :: Integer -> [(Integer,Integer)]
biparticiones3 a =
  takeWhile ((>0) . fst) [divMod a (10^n) | n <- [1..]] 
 
-- 4ª solución
-- ===========
 
biparticiones4 :: Integer -> [(Integer,Integer)]
biparticiones4 n =
  [quotRem n (10^x) | x <- [1..length (show n) -1]]
 
-- 5ª solución
-- ===========
 
biparticiones5 :: Integer -> [(Integer,Integer)]
biparticiones5 n =
  takeWhile (/= (0,n)) [divMod n (10^x) | x <- [1..]]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> numero n = (read (replicate n '2')) :: Integer
--    (0.00 secs, 0 bytes)
--    λ> length (biparticiones1 (numero 10000))
--    9999
--    (0.03 secs, 10,753,192 bytes)
--    λ> length (biparticiones2 (numero 10000))
--    9999
--    (1.89 secs, 6,410,513,136 bytes)
--    λ> length (biparticiones3 (numero 10000))
--    9999
--    (0.54 secs, 152,777,680 bytes)
--    λ> length (biparticiones4 (numero 10000))
--    9999
--    (0.01 secs, 7,382,816 bytes)
--    λ> length (biparticiones5 (numero 10000))
--    9999
--    (2.11 secs, 152,131,136 bytes)
--    
--    λ> length (biparticiones1 (numero (10^7)))
--    9999999
--    (14.23 secs, 10,401,100,848 bytes)
--    λ> length (biparticiones4 (numero (10^7)))
--    9999999
--    (11.43 secs, 7,361,097,856 bytes)

El problema del reciclado

El problema del reciclado N P consiste en lo siguiente: un grupo de personas disponen de N botellas de refresco vacía y las llevan a reciclar obteniendo una botella llena por cada P vacías; se beben inmediatamente el contenido de las botellas obtenidas y sus botellas vacías, junto con las no recicladas anteriormente, las canjean por botellas llenas. El proceso continúa hasta que no tienen suficientes botellas para canjear. El objetivo del problema es calcular el número de botellas que se han bebido.

Por ejemplo, si disponen de 10 botellas y por cada 2 obtienen 1, se producen cuatro canjeos:

  • en el primer canjeo entregan las 10 y obtienen 5;
  • en el segundo, entregan 4, le quedan 1 y obtienen 2;
  • en el tercero, entregan 2, le queda 1 y obtienen 1;
  • en el cuarto, entregan 2 y obtienen 1.

Por tanto, se han bebido 9 y le quedan 1 que no pueden canjear.

Definir la función

   reciclado :: Int -> Int -> Int

tal que (reciclado n p) es el número de botellas que se beben en el reciclado comenzado con n botellas y canjeando p botellas vacías por una llena. Por ejemplo,

   reciclado  9 3  ==  4
   reciclado 10 2  ==  9

Referencia: Este ejercicio está basado en el problema Soda surpler de Kattis.

Soluciones

reciclado :: Int -> Int -> Int
reciclado n p = aux n 0
  where aux x k | x < p     = k
                | otherwise = aux (a+b) (k+a) 
          where (a,b) = divMod x p

Máximo producto de pares en la lista

Definir la función

  maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir
como producto de dos elementos distintos de xs o Nothing, en el caso de que
ningún elemento de xs se pueda escribir como producto de dos elementos
distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

   maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
   maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
   maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
   maximoProducto [2,4]                    ==  Nothing
   maximoProducto [2, 5, 7, 8]             ==  Nothing
   maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
   maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Soluciones

import Data.List (delete, nub, sort)
 
-- 1ª solución
-- ===========
 
maximoProducto1 :: [Int] -> Maybe Int
maximoProducto1 xs
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where
    ys = reverse (sort xs)
    zs = [y | y <- ys, y `elem` productos xs]
 
-- (productos xs) es la lista de los números que son productos de dos
-- elementos de xs. Por ejemplo, 
--   productos [4,3,5,2]  ==  [12,20,8,15,6,10]
productos :: [Int] -> [Int]
productos xs =
  nub [y * z | y <- xs, z <- delete y xs]
 
-- 2ª solución
-- ===========
 
maximoProducto2 :: [Int] -> Maybe Int
maximoProducto2 xs = aux (reverse (sort xs))
  where aux []     = Nothing
        aux (y:ys) | esProducto y xs = Just y
                   | otherwise       = aux ys
 
esProducto :: Int -> [Int] -> Bool
esProducto y []     = False
esProducto y (x:xs) = 
  (m == 0 && d `elem` xs) || esProducto y xs
  where (d,m) = divMod y x  
 
-- Comparación de eficiencia
-- =========================
 
--    λ> maximoProducto1 [1..10^4]
--    Just 10000
--    (2.60 secs, 0 bytes)
--    λ> maximoProducto2 [1..10^4]
--    Just 10000
--    (0.01 secs, 0 bytes)

Cantidad de números Pentanacci impares

Los números de Pentanacci se definen mediante las ecuaciones

   P(0) = 0
   P(1) = 1
   P(2) = 1
   P(3) = 2
   P(4) = 4
   P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

Los primeros números de Pentanacci son

  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Se obseeva que

  • hasta P(5) hay 1 impar: el 1 (aunque aparece dos veces);
  • hasta P(7) hay 2 impares distintos: 1 y 31;
  • hasta P(10) hay 3 impares distintos: 1, 31 y 61;
  • hasta P(15) hay 5 impares distintos: 1, 31 y 61, 1793 y 3525.

Definir la función

   nPentanacciImpares :: Integer -> Integer

tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,

   nPentanacciImpares 5                             ==  1
   nPentanacciImpares 7                             ==  2
   nPentanacciImpares 10                            ==  3
   nPentanacciImpares 15                            ==  5
   nPentanacciImpares 100                           ==  33
   nPentanacciImpares 1000                          ==  333
   nPentanacciImpares 10000                         ==  3333
   nPentanacciImpares (10^(10^6)) `mod` (10^9)      ==  333333333
   length (show (nPentanacciImpares2 (10^(10^6))))  ==  1000000

Soluciones

import Data.List (genericLength, genericTake)
 
-- 1ª definición 
-- =============
 
nPentanacciImpares1 :: Integer -> Integer
nPentanacciImpares1 0 = 0
nPentanacciImpares1 1 = 1
nPentanacciImpares1 n = 
    genericLength (filter odd (genericTake (n+1) pentanacci)) - 1
 
pentanacci :: [Integer]
pentanacci = p (0, 1, 1, 2, 4)
    where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)
 
-- 2ª definición
-- =============
 
-- λ> map nPentanacciImpares1 [1..31]
-- [1,1,1,1,1,1,2,3,3,3,3,3,4,5,5,5,5,5,6,7,7,7,7,7,8,9,9,9,9,9,10]
-- λ> [(head xs, length xs) | xs <- group (map nPentanacciImpares1 [1..37])]
-- [(1,6),(2,1),(3,5),(4,1),(5,5),(6,1),(7,5),(8,1),(9,5),(10,1),(11,5),(12,1)]
 
nPentanacciImpares2 :: Integer -> Integer
nPentanacciImpares2 0 = 0
nPentanacciImpares2 1 = 1
nPentanacciImpares2 n = 2 * q + min r 2 - 1
    where (q,r) = n `quotRem` 6
 
-- 3ª definición
-- =============
 
nPentanacciImpares3 :: Integer -> Integer
nPentanacciImpares3 0 = 0
nPentanacciImpares3 1 = 1
nPentanacciImpares3 n | r == 5    = 2*q + 2 
                      | otherwise = 2*q + 1 
    where (q,r) = divMod (n-2) 6