divMod

Búsqueda de la mina

PorJosé A. Alonso 24-marzo-202031-marzo-2020

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

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)

1	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)

1	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)

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

PorJosé A. Alonso 7-febrero-201914-febrero-2019

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

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

1 2	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

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

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.

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

PorJosé A. Alonso 6-marzo-201814-marzo-2018

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

1	242424 ==> 18 ==> 9

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

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

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

Definir las funciones

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

1 2	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

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

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]]

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

PorJosé A. Alonso 15-diciembre-201722-diciembre-2017

Definir la función

   minSumDig :: Integer -> Integer

1	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

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)

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

PorJosé A. Alonso 9-noviembre-201716-noviembre-2017

Definir la función

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

1	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)]

1 2	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)

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

PorJosé A. Alonso 28-marzo-20174-abril-2017

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

1	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

1 2	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

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

PorJosé A. Alonso 30-enero-201726-marzo-2022

Definir la función

  maximoProducto :: [Int] -> Maybe Int

1	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

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)

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

PorJosé A. Alonso 18-febrero-20162-mayo-2016

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

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, ...

1	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

1	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

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

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

Búsqueda de la mina

Soluciones

Otras soluciones

Pensamiento

Aritmética lunar

Soluciones

Pensamiento

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

Soluciones

Menor con suma de dígitos dada

Soluciones

Biparticiones de un número

Soluciones

El problema del reciclado

Soluciones

Máximo producto de pares en la lista

Soluciones

Cantidad de números Pentanacci impares

Soluciones

Entradas recientes

Buscar

Correo electrónico