filter – Página 3

Agrupación por orden de aparición

PorJosé A. Alonso 13-diciembre-201620-diciembre-2016

Definir la función

   agrupacion :: Eq a => [a] -> [a]

1	agrupacion :: Eq a => [a] -> [a]

tal que (agrupacion xs) es la lista obtenida agrupando los elementos de xs según su primera aparición. Por ejemplo,

   agrupacion [3,1,5,1,7,1,5,3]  ==  [3,3,1,1,1,5,5,7]
   agrupacion "babcacb"          ==  "bbbaacc"

1 2	agrupacion [3,1,5,1,7,1,5,3] == [3,3,1,1,1,5,5,7] agrupacion "babcacb" == "bbbaacc"

Soluciones

import Data.List (nub, partition)

-- 1ª definición
agrupacion :: Eq a => [a] -> [a]
agrupacion [] = []
agrupacion (x:xs) =
  x : filter (==x) xs ++ agrupacion (filter (/=x) xs)

-- 2ª definición
agrupacion2 :: Eq a => [a] -> [a]
agrupacion2 xs = concat [filter (x==) xs | x <- nub xs]

-- 3ª definición
agrupacion3 :: Eq a => [a] -> [a]
agrupacion3 []     = []
agrupacion3 (x:xs) = x : ys ++ agrupacion3 zs
  where (ys,zs) = partition (==x) xs

-- Comparación de eficiencia
--    λ> import Data.List (cycle)
--    λ> :set +s
--    λ> sum (agrupacion (take (10^7) (cycle [0,1,2,3])))
--    15000000
--    (24.40 secs, 3,173,123,368 bytes)
--    λ> sum (agrupacion2 (take (10^7) (cycle [0,1,2,3])))
--    15000000
--    (13.71 secs, 2,333,129,416 bytes)
--    λ> sum (agrupacion3 (take (10^7) (cycle [0,1,2,3])))
--    15000000
--    (22.33 secs, 5,080,127,944 bytes)

import Data.List (nub, partition)

-- 1ª definición

agrupacion :: Eq a => [a] -> [a]

agrupacion [] = []

agrupacion (x:xs) =

x : filter (==x) xs ++ agrupacion (filter (/=x) xs)

-- 2ª definición

agrupacion2 :: Eq a => [a] -> [a]

agrupacion2 xs = concat [filter (x==) xs | x <- nub xs]

-- 3ª definición

agrupacion3 :: Eq a => [a] -> [a]

agrupacion3 [] = []

agrupacion3 (x:xs) = x : ys ++ agrupacion3 zs

where (ys,zs) = partition (==x) xs

-- Comparación de eficiencia

-- λ> import Data.List (cycle)

-- λ> :set +s

-- λ> sum (agrupacion (take (10^7) (cycle [0,1,2,3])))

-- 15000000

-- (24.40 secs, 3,173,123,368 bytes)

-- λ> sum (agrupacion2 (take (10^7) (cycle [0,1,2,3])))

-- 15000000

-- (13.71 secs, 2,333,129,416 bytes)

-- λ> sum (agrupacion3 (take (10^7) (cycle [0,1,2,3])))

-- 15000000

-- (22.33 secs, 5,080,127,944 bytes)

Mayores que la mitad

PorJosé A. Alonso 12-diciembre-201619-diciembre-2016

Definir la función

   mayoresMitad :: Ord a => [a] -> [a]

1	mayoresMitad :: Ord a => [a] -> [a]

tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,

   sort (mayoresMitad [1,6,3,4])    ==  [4,6]
   sort (mayoresMitad [1,6,3,4,7])  ==  [4,6,7]
   sort (mayoresMitad [1,6,3,4,2])  ==  [3,4,6]
   length (mayoresMitad3 [1..10^6]) ==  500000

sort (mayoresMitad [1,6,3,4]) == [4,6]

sort (mayoresMitad [1,6,3,4,7]) == [4,6,7]

sort (mayoresMitad [1,6,3,4,2]) == [3,4,6]

length (mayoresMitad3 [1..10^6]) == 500000

Nota: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.

Soluciones

import Data.List (sort)

-- 1ª solución:
mayoresMitad1 :: Ord a => [a] -> [a]
mayoresMitad1 xs =
  [x | x <- xs
     , length (filter (<=x) xs) > k]
  where k = length xs `div` 2 

-- 2ª solución
mayoresMitad2 :: Ord a => [a] -> [a]
mayoresMitad2 xs = aux xs
  where aux [] = []
        aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys
                   | otherwise                        = aux ys
        k = length xs `div` 2 

-- 3ª solución
mayoresMitad3 :: Ord a => [a] -> [a]
mayoresMitad3 xs = drop k (sort xs)
  where k = length xs `div` 2 

-- Comprobación de eficiencia
--    λ> length (mayoresMitad1 [1..4*10^3])
--    2000
--    (3.79 secs, 442,631,712 bytes)
--    λ> length (mayoresMitad2 [1..4*10^3])
--    2000
--    (11.82 secs, 1,463,762,192 bytes)
--    λ> length (mayoresMitad3 [1..4*10^3])
--    2000
--    (0.02 secs, 0 bytes)

import Data.List (sort)

-- 1ª solución:

mayoresMitad1 :: Ord a => [a] -> [a]

mayoresMitad1 xs =

[x | x <- xs

, length (filter (<=x) xs) > k]

where k = length xs `div` 2

-- 2ª solución

mayoresMitad2 :: Ord a => [a] -> [a]

mayoresMitad2 xs = aux xs

where aux [] = []

aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys

| otherwise = aux ys

k = length xs `div` 2

-- 3ª solución

mayoresMitad3 :: Ord a => [a] -> [a]

mayoresMitad3 xs = drop k (sort xs)

where k = length xs `div` 2

-- Comprobación de eficiencia

-- λ> length (mayoresMitad1 [1..4*10^3])

-- 2000

-- (3.79 secs, 442,631,712 bytes)

-- λ> length (mayoresMitad2 [1..4*10^3])

-- 2000

-- (11.82 secs, 1,463,762,192 bytes)

-- λ> length (mayoresMitad3 [1..4*10^3])

-- 2000

-- (0.02 secs, 0 bytes)

Caracteres en la misma posición que en el alfabeto

PorJosé A. Alonso 9-diciembre-201617-diciembre-2016

Un carácter c de una cadena cs está bien colocado si la posición de c en cs es la misma que en el abecedario (sin distinguir entre mayúsculas y minúsculas). Por ejemplo, los elementos bien colocados de la cadena «aBaCEria» son ‘a’, ‘B’ y ‘E’.

Definir la función

   nBienColocados :: String -> Int

1	nBienColocados :: String -> Int

tal que (nBienColocados cs) es el número de elementos bien colocados de la cadena cs. Por ejemplo,

   nBienColocados "aBaCEria"                    ==  3
   nBienColocados "xBxxExxxIxxxxNxxxxxTxxxXYZ"  ==  8

1 2	nBienColocados "aBaCEria" == 3 nBienColocados "xBxxExxxIxxxxNxxxxxTxxxXYZ" == 8

Soluciones

import Data.Char (toLower)

nBienColocados :: String -> Int
nBienColocados = length . bienColocados

bienColocados :: String -> [Char]
bienColocados cs =
  [c | (c,d) <- zip (map toLower cs) ['a'..'z']
     , c == d]

import Data.Char (toLower)

nBienColocados :: String -> Int

nBienColocados = length . bienColocados

bienColocados :: String -> [Char]

bienColocados cs =

[c | (c,d) <- zip (map toLower cs) ['a'..'z']

, c == d]

Referencias

Basado en el problema Count characters at same position as in English alphabets de Sahil Chhabra en GeeksforGeeks.

Menor potencia de 2 comenzando un número dado

PorJosé A. Alonso 24-noviembre-20161-diciembre-2016

Definir las siguientes funciones

   potenciasDe2  :: Integer -> [Integer]
   menorPotenciaDe2 :: Integer -> Integer

1 2	potenciasDe2 :: Integer -> [Integer] menorPotenciaDe2 :: Integer -> Integer

tales que

(potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,

     λ> take 5 (potenciasDe2 3)
     [32,32768,33554432,34359738368,35184372088832]
     λ> take 2 (potenciasDe2 102)
     [1024,102844034832575377634685573909834406561420991602098741459288064]

λ> take 5 (potenciasDe2 3)

[32,32768,33554432,34359738368,35184372088832]

λ> take 2 (potenciasDe2 102)

[1024,102844034832575377634685573909834406561420991602098741459288064]

(menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,

     λ> menorPotenciaDe2 10
     1024
     λ> menorPotenciaDe2 25
     256
     λ> menorPotenciaDe2 62
     6277101735386680763835789423207666416102355444464034512896
     λ> menorPotenciaDe2 425
     42535295865117307932921825928971026432
     λ> menorPotenciaDe2 967140655691
     9671406556917033397649408
     λ> [menorPotenciaDe2 a | a <- [1..10]]
     [1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

λ> menorPotenciaDe2 10

1024

λ> menorPotenciaDe2 25

256

λ> menorPotenciaDe2 62

6277101735386680763835789423207666416102355444464034512896

λ> menorPotenciaDe2 425

42535295865117307932921825928971026432

λ> menorPotenciaDe2 967140655691

9671406556917033397649408

λ> [menorPotenciaDe2 a | a <- [1..10]]

[1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.

Soluciones

import Data.List (isPrefixOf)
import Test.QuickCheck

-- 1ª definición de potenciasDe2
-- =============================

potenciasDe2A :: Integer -> [Integer]
potenciasDe2A a =
  [x | x <- potenciasA
     , a `esPrefijo` x]

potenciasA :: [Integer]
potenciasA = [2^n | n <- [0..]]

esPrefijo :: Integer -> Integer -> Bool
esPrefijo x y = show x `isPrefixOf` show y

-- 2ª definición de potenciasDe2
-- =============================

potenciasDe2B :: Integer -> [Integer]
potenciasDe2B a = filter (a `esPrefijo`) potenciasA

-- 3ª definición de potenciasDe2
-- =============================

potenciasDe2C :: Integer -> [Integer]
potenciasDe2C a = filter (a `esPrefijo`) potenciasC

potenciasC :: [Integer]
potenciasC = iterate (*2) 1

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

-- λ> length (show (head (potenciasDe2A 123456)))
-- 19054
-- (7.17 secs, 1,591,992,792 bytes)
-- λ> length (show (head (potenciasDe2B 123456)))
-- 19054
-- (5.96 secs, 1,273,295,272 bytes)
-- λ> length (show (head (potenciasDe2C 123456)))
-- 19054
-- (6.24 secs, 1,542,698,392 bytes)

-- Definición de menorPotenciaDe2 
menorPotenciaDe2 :: Integer -> Integer
menorPotenciaDe2 = head . potenciasDe2B

-- Propiedad
prop_potenciasDe2 :: Integer -> Property
prop_potenciasDe2 a =
  a > 0 ==> not (null (potenciasDe2B a))

-- Comprobación
--    λ> quickCheck prop_potenciasDe2
--    +++ OK, passed 100 tests.

import Data.List (isPrefixOf)

import Test.QuickCheck

-- 1ª definición de potenciasDe2

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

potenciasDe2A :: Integer -> [Integer]

potenciasDe2A a =

[x | x <- potenciasA

, a `esPrefijo` x]

potenciasA :: [Integer]

potenciasA = [2^n | n <- [0..]]

esPrefijo :: Integer -> Integer -> Bool

esPrefijo x y = show x `isPrefixOf` show y

-- 2ª definición de potenciasDe2

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

potenciasDe2B :: Integer -> [Integer]

potenciasDe2B a = filter (a `esPrefijo`) potenciasA

-- 3ª definición de potenciasDe2

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

potenciasDe2C :: Integer -> [Integer]

potenciasDe2C a = filter (a `esPrefijo`) potenciasC

potenciasC :: [Integer]

potenciasC = iterate (*2) 1

-- Comparación de eficiencia

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

-- λ> length (show (head (potenciasDe2A 123456)))

-- 19054

-- (7.17 secs, 1,591,992,792 bytes)

-- λ> length (show (head (potenciasDe2B 123456)))

-- 19054

-- (5.96 secs, 1,273,295,272 bytes)

-- λ> length (show (head (potenciasDe2C 123456)))

-- 19054

-- (6.24 secs, 1,542,698,392 bytes)

-- Definición de menorPotenciaDe2

menorPotenciaDe2 :: Integer -> Integer

menorPotenciaDe2 = head . potenciasDe2B

-- Propiedad

prop_potenciasDe2 :: Integer -> Property

prop_potenciasDe2 a =

a > 0 ==> not (null (potenciasDe2B a))

-- Comprobación

-- λ> quickCheck prop_potenciasDe2

-- +++ OK, passed 100 tests.

Referencias

Potencias de 2 por Philippe Chevanne en «Mad Maths».
Sucesión A018802 de la OEIS

Densidad de números no monótonos

PorJosé A. Alonso 11-mayo-201618-mayo-2016

Un número entero positivo se dice que es

creciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 134479.
decreciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 664210.
no monótono si no es creciente ni decreciente; por ejemplo, 155369.

Para cada entero positivo n, la densidad números no monótonos hasta n es el cociente entre la cantidad de n números no monótonos entre menores o iguales que n y el número n. Por ejemplo, hasta 150 hay 19 números no monótonos (101, 102, 103, 104, 105, 106, 107, 108, 109, 120, 121, 130, 131, 132, 140, 141, 142, 143 y 150); por tanto, la densidad hasta 150 es 19/150 = 0.12666667

Definir las siguientes funciones

   densidad              :: Integer -> Float
   menorConDensidadMayor :: Float -> Integer

1 2	densidad :: Integer -> Float menorConDensidadMayor :: Float -> Integer

tales que

(densidad n) es la densidad de números no monótonos hasta n. Por ejemplo,

     densidad 100  ==  0.0
     densidad 200  ==  0.265
     densidad 400  ==  0.4375
     densidad 800  ==  0.53375

densidad 100 == 0.0

densidad 200 == 0.265

densidad 400 == 0.4375

densidad 800 == 0.53375

(menorConDensidadMayor x) es el menor número n tal que la densidad de números no monótonos hasta n es mayor o igual que x. Por ejemplo,

     menorConDensidadMayor 0.5   ==  538
     densidad 537                ==  0.49906892
     densidad 538                ==  0.5
     menorConDensidadMayor 0.9   ==  21780
     densidad 21779              ==  0.8999954
     densidad 21780              ==  0.9
     menorConDensidadMayor 0.99  ==  1586996

menorConDensidadMayor 0.5 == 538

densidad 537 == 0.49906892

densidad 538 == 0.5

menorConDensidadMayor 0.9 == 21780

densidad 21779 == 0.8999954

densidad 21780 == 0.9

menorConDensidadMayor 0.99 == 1586996

Soluciones

import Data.List (genericLength, sort)

-- 1ª definición
-- =============

densidad :: Integer -> Float
densidad n = 
    genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n

esNoMonotono :: Integer -> Bool
esNoMonotono x = not (esCreciente x) && not (esDecreciente x)

esCreciente :: Integer -> Bool
esCreciente x = show x == sort (show x)

esDecreciente :: Integer -> Bool
esDecreciente x = reverse (show x) == sort (show x)

menorConDensidadMayor :: Float -> Integer 
menorConDensidadMayor x  = 
    buscaProporcion x (filter esNoMonotono [1..])
    where buscaProporcion x = 
              snd . head . filter condicion . zip [1..]
              where condicion (a,b) = a >= x * fromIntegral b

import Data.List (genericLength, sort)

-- 1ª definición

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

densidad :: Integer -> Float

densidad n =

genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n

esNoMonotono :: Integer -> Bool

esNoMonotono x = not (esCreciente x) && not (esDecreciente x)

esCreciente :: Integer -> Bool

esCreciente x = show x == sort (show x)

esDecreciente :: Integer -> Bool

esDecreciente x = reverse (show x) == sort (show x)

menorConDensidadMayor :: Float -> Integer

menorConDensidadMayor x =

buscaProporcion x (filter esNoMonotono [1..])

where buscaProporcion x =

snd . head . filter condicion . zip [1..]

where condicion (a,b) = a >= x * fromIntegral b

Productos simultáneos de dos y tres números consecutivos

PorJosé A. Alonso 25-abril-201625-abril-2021

Definir la función

   productos :: Integer -> Integer -> [[Integer]]

1	productos :: Integer -> Integer -> [[Integer]]

tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,

   productos 2 6     ==  [[2,3]]
   productos 3 6     ==  [[1,2,3]]
   productos 4 1680  ==  [[5,6,7,8]]
   productos 2 5     ==  []

productos 2 6 == [[2,3]]

productos 3 6 == [[1,2,3]]

productos 4 1680 == [[5,6,7,8]]

productos 2 5 == []

Comprobar con QuickCheck que si n > 0 y x > 0, entonces

   productos n (product [x..x+n-1]) == [[x..x+n-1]]

1	productos n (product [x..x+n-1]) == [[x..x+n-1]]

Usando productos, definir la función

   productosDe2y3consecutivos :: [Integer]

1	productosDe2y3consecutivos :: [Integer]

cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,

   head productosDe2y3consecutivos  ==  6

1	head productosDe2y3consecutivos == 6

Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.

Soluciones

import Test.QuickCheck

-- 1ª definición
productos1 :: Integer -> Integer -> [[Integer]]
productos1 n x = [[y..y+n-1] | y <- [1..x],
                               product [y..y+n-1] == x]

-- 2ª definición
-- =============

-- Se puede reducir el intervalo de búsqueda teniendo en cuenta las
-- siguientes desigualdades
--    y*(y+1)* ... (y+n-1) = x
--    y^n <= x <= (y+n-1)^n
--    y <= x^(1/n), x^(1/n)-n+1 <= y
--    x^(1/n)-n+1 <= y <= x^(1/n)

productos2 :: Integer -> Integer -> [[Integer]]
productos2 n x = [[z..z+n-1] | z <- [y-n+1..y],
                               product [z..z+n-1] == x]
    where y = floor ((fromIntegral x)**(1/(fromIntegral n)))

productos :: Integer -> Integer -> [[Integer]]
productos = productos2

prop_productos n x =
    n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]]

-- La comprobación es
--    ghci> quickCheck prop_productos
--    +++ OK, passed 100 tests.
--    (0.10 secs, 26409644 bytes)

productosDe2y3consecutivos :: [Integer]
productosDe2y3consecutivos = [x| x <- [1..], 
                                 let ys = productos 2 x,
                                 not (null ys), 
                                 let zs = productos 3 x,
                                 not (null zs)] 

-- El cálculo es
--    ghci> take 2 productosDe2y3consecutivos
--    [6,210]
--    ghci> productos 2 210
--    [[14,15]]
--    ghci> productos 3 210
--    [[5,6,7]]

import Test.QuickCheck

-- 1ª definición

productos1 :: Integer -> Integer -> [[Integer]]

productos1 n x = [[y..y+n-1] | y <- [1..x],

product [y..y+n-1] == x]

-- 2ª definición

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

-- Se puede reducir el intervalo de búsqueda teniendo en cuenta las

-- siguientes desigualdades

-- y*(y+1)* ... (y+n-1) = x

-- y^n <= x <= (y+n-1)^n

-- y <= x^(1/n), x^(1/n)-n+1 <= y

-- x^(1/n)-n+1 <= y <= x^(1/n)

productos2 :: Integer -> Integer -> [[Integer]]

productos2 n x = [[z..z+n-1] | z <- [y-n+1..y],

product [z..z+n-1] == x]

where y = floor ((fromIntegral x)**(1/(fromIntegral n)))

productos :: Integer -> Integer -> [[Integer]]

productos = productos2

prop_productos n x =

n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]]

-- La comprobación es

-- ghci> quickCheck prop_productos

-- +++ OK, passed 100 tests.

-- (0.10 secs, 26409644 bytes)

productosDe2y3consecutivos :: [Integer]

productosDe2y3consecutivos = [x| x <- [1..],

let ys = productos 2 x,

not (null ys),

let zs = productos 3 x,

not (null zs)]

-- El cálculo es

-- ghci> take 2 productosDe2y3consecutivos

-- [6,210]

-- ghci> productos 2 210

-- [[14,15]]

-- ghci> productos 3 210

-- [[5,6,7]]

Mayor sección inicial sin repetidos

PorJosé A. Alonso 15-marzo-20161-mayo-2016

Definir la función

   seccion :: Eq a => [a] -> [a]

1	seccion :: Eq a => [a] -> [a]

tal que (seccion xs) es el mayor sección inicial de xs que no contiene ningún elemento repetido. Por ejemplo:

   seccion [1,2,3,2,4,5]                      == [1,2,3] 
   seccion "caceres"                          == "ca"
   length (seccion ([1..7531] ++ [1..10^9]))  ==  7531

seccion [1,2,3,2,4,5] == [1,2,3]

seccion "caceres" == "ca"

length (seccion ([1..7531] ++ [1..10^9])) == 7531

Soluciones

import Data.List (inits, nub)

-- 1ª solución
-- ===========

seccion1 :: Eq a => [a] -> [a]
seccion1 = last . filter (\ys -> nub ys == ys) . inits

-- 2ª solución
-- ===========

seccion2 :: Eq a => [a] -> [a]
seccion2 xs = aux xs []
    where aux [] ys = reverse ys
          aux (x:xs) ys | x `elem` ys = reverse ys
                        | otherwise   = aux xs (x:ys)

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

--    ghci> last (seccion1 [1..10^3])
--    1000
--    (6.19 secs, 59,174,640 bytes)
--    ghci> last (seccion2 [1..10^3])
--    1000
--    (0.04 secs, 0 bytes)

import Data.List (inits, nub)

-- 1ª solución

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

seccion1 :: Eq a => [a] -> [a]

seccion1 = last . filter (\ys -> nub ys == ys) . inits

-- 2ª solución

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

seccion2 :: Eq a => [a] -> [a]

seccion2 xs = aux xs []

where aux [] ys = reverse ys

aux (x:xs) ys | x `elem` ys = reverse ys

| otherwise = aux xs (x:ys)

-- Comparación de eficiencia

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

-- ghci> last (seccion1 [1..10^3])

-- 1000

-- (6.19 secs, 59,174,640 bytes)

-- ghci> last (seccion2 [1..10^3])

-- 1000

-- (0.04 secs, 0 bytes)

Números N cuyos cuadrados tienen dos copias de cada dígito de N

PorJosé A. Alonso 3-marzo-201610-marzo-2016

La sucesión A114258 de la OEIS está formada por los números n tales que el número de ocurrencia de cada dígito d de n en n² es el doble del número de ocurrencia de d en n. Por ejemplo, 72576 es un elemento de A114258 porque tiene un 2, un 5, un 6 y dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5, dos 6 y cuatro 7.

Un número es especial si pertenece a la sucesión A114258.

Definir la sucesión

   especiales :: [Integer]

1	especiales :: [Integer]

cuyos elementos son los números especiales. Por ejemplo,

   take 5 especiales  ==  [72576,406512,415278,494462,603297]

1	take 5 especiales == [72576,406512,415278,494462,603297]

Soluciones

import Data.List (sort)

especiales :: [Integer]
especiales = filter especial [1..]

especial :: Integer -> Bool
especial x = sort (ys ++ ys) == sort (show (x^2))
    where ys = show x

import Data.List (sort)

especiales :: [Integer]

especiales = filter especial [1..]

especial :: Integer -> Bool

especial x = sort (ys ++ ys) == sort (show (x^2))

where ys = show x

En Maxima

especiales (n) := block ([k:0, r:[], i:1],
  while k < n do
    ( if especial (i)
      then (r : cons (i,r), k : k+1),
      i : i+1),
  reverse (r))$
  
especial (n) := block([ys],
  ys : string(n),
  is (ssort (sconcat(ys,ys)) = ssort (string (n^2))))$

/*
   (%i15) showtime : true$
   Evaluation took 0.0000 seconds (0.0000 elapsed)
   (%i16) especiales (5);
   Evaluation took 29.4800 seconds (29.5400 elapsed)
   (%o16) [72576, 406512, 415278, 494462, 603297]
*/

especiales (n) := block ([k:0, r:[], i:1],

while k < n do

( if especial (i)

then (r : cons (i,r), k : k+1),

i : i+1),

reverse (r))$

especial (n) := block([ys],

ys : string(n),

is (ssort (sconcat(ys,ys)) = ssort (string (n^2))))$

(%i15) showtime : true$

Evaluation took 0.0000 seconds (0.0000 elapsed)

(%i16) especiales (5);

Evaluation took 29.4800 seconds (29.5400 elapsed)

(%o16) [72576, 406512, 415278, 494462, 603297]

Sumas de potencias de 3 primos

PorJosé A. Alonso 24-febrero-201625-marzo-2022

Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son

   28 = 2² + 2³ + 2⁴
   33 = 3² + 2³ + 2⁴
   47 = 2² + 3³ + 2⁴
   49 = 5² + 2³ + 2⁴

28 = 2² + 2³ + 2⁴

33 = 3² + 2³ + 2⁴

47 = 2² + 3³ + 2⁴

49 = 5² + 2³ + 2⁴

Definir la sucesión

   sumas3potencias :: [Integer]

1	sumas3potencias :: [Integer]

cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,

   λ> take 15 sumas3potencias
   [28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]
   λ> sumas3potencias !! 234567
   8953761

λ> take 15 sumas3potencias

[28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]

λ> sumas3potencias !! 234567

8953761

Soluciones

import Data.Numbers.Primes (primes)

-- 1ª solución
-- ===========

sumas3potencias1 :: [Integer]
sumas3potencias1 = filter esTripleSuma [1..]
 
-- (esTripleSuma n) se verifica si n se puede escribir de la forma
-- p²+q³+r⁴, con p, q y r primos. Por ejemplo, 
--    esTripleSuma 33  ==  True
--    esTripleSuma 45  ==  False
esTripleSuma :: Integer -> Bool
esTripleSuma = not . null . triplesSumas  

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales
-- que p²+q³+r⁴ = n. Por ejemplo,
--    triplesSumas 33   ==  [(3,2,2)]
--    triplesSumas 145  ==  [(11,2,2),(2,5,2)]
--    triplesSumas 45   ==  []
triplesSumas :: Integer -> [(Integer,Integer,Integer)]
triplesSumas n =  
    [(p,q,r) 
    | r <- xs, 
      q <- xs, 
      let p2 = n - q^3 - r^4,
      let p = (floor . sqrt . fromIntegral) p2,
      p*p == p2,
      isPrime p]
    where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

-- 2ª solución
-- ===========

sumas3potencias2 :: [Integer]
sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]
sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
    where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys
 
as = map (^2) primes
bs = map (^3) primes
cs = map (^4) primes

import Data.Numbers.Primes (primes)

-- 1ª solución

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

sumas3potencias1 :: [Integer]

sumas3potencias1 = filter esTripleSuma [1..]

-- (esTripleSuma n) se verifica si n se puede escribir de la forma

-- p²+q³+r⁴, con p, q y r primos. Por ejemplo,

-- esTripleSuma 33 == True

-- esTripleSuma 45 == False

esTripleSuma :: Integer -> Bool

esTripleSuma = not . null . triplesSumas

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales

-- que p²+q³+r⁴ = n. Por ejemplo,

-- triplesSumas 33 == [(3,2,2)]

-- triplesSumas 145 == [(11,2,2),(2,5,2)]

-- triplesSumas 45 == []

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

triplesSumas n =

[(p,q,r)

| r <- xs,

q <- xs,

let p2 = n - q^3 - r^4,

let p = (floor . sqrt . fromIntegral) p2,

p*p == p2,

isPrime p]

where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

-- 2ª solución

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

sumas3potencias2 :: [Integer]

sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]

sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]

mezclaTodas = foldr1 xmezcla

where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x == y = x : mezcla xs ys

| x > y = y : mezcla (x:xs) ys

as = map (^2) primes

bs = map (^3) primes

cs = map (^4) primes

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

Números primos de Hilbert

PorJosé A. Alonso 4-febrero-20161-mayo-2016

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …

Definir la sucesión

   primosH :: [Integer]

1	primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

   take 15 primosH  == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
   primosH !! 20000 == 203221

1 2	take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! 20000 == 203221

Soluciones

-- 1ª definición
-- =============

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,
--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]
numerosH :: [Integer]
numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a
-- n. Por ejemplo,
--   divisoresH 117  ==  [1,9,13,117]
--   divisoresH  21  ==  [1,21]
divisoresH :: Integer -> [Integer]
divisoresH n = [x | x <- takeWhile (<=n) numerosH,
                    n `mod` x == 0]

primosH1 :: [Integer]
primosH1 = [n | n <- tail numerosH,
                divisoresH n == [1,n]]

-- 2ª definición
-- =============

primosH2 :: [Integer]
primosH2 = filter esPrimoH (tail numerosH) 
    where esPrimoH n = all noDivideAn [5,9..m]
              where noDivideAn x = n `mod` x /= 0
                    m            = ceiling (sqrt (fromIntegral n))

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

--    λ> primosH1 !! 2000
--    16957
--    (6.93 secs, 750,291,352 bytes)
--    λ> primosH2 !! 2000
--    16957
--    (0.13 secs, 18,066,288 bytes)

-- 1ª definición

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

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,

-- take 15 numerosH == [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]

numerosH :: [Integer]

numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a

-- n. Por ejemplo,

-- divisoresH 117 == [1,9,13,117]

-- divisoresH 21 == [1,21]

divisoresH :: Integer -> [Integer]

divisoresH n = [x | x <- takeWhile (<=n) numerosH,

n `mod` x == 0]

primosH1 :: [Integer]

primosH1 = [n | n <- tail numerosH,

divisoresH n == [1,n]]

-- 2ª definición

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

primosH2 :: [Integer]

primosH2 = filter esPrimoH (tail numerosH)

where esPrimoH n = all noDivideAn [5,9..m]

where noDivideAn x = n `mod` x /= 0

m = ceiling (sqrt (fromIntegral n))

-- Comparación de eficiencia

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

-- λ> primosH1 !! 2000

-- 16957

-- (6.93 secs, 750,291,352 bytes)

-- λ> primosH2 !! 2000

-- 16957

-- (0.13 secs, 18,066,288 bytes)

Cambios de signo

PorJosé A. Alonso 12-enero-201620-enero-2016

En una lista xs se produce un cambio de signo por cada elemento x de la lista junto el primero de los elementos de xs con signo opuesto al de x. Por ejemplo,en la lista [6,5,-4,0,-2,-7,0,-8,-1,4] hay 2 cambios de signo (entre (5,-4) y (-1,4)) y en la lista [6,5,-4,0, 2,-7,0,-8,-1,4] hay 4 cambios de signo (entre (5,-4), (-4,2), (2,-7) y(-1,4)).

Definir la función

   nCambios :: (Num a, Ord a) => [a] -> Int

1	nCambios :: (Num a, Ord a) => [a] -> Int

tal que (nCambios xs) es el número de cambios de signos de la lista xs. Por ejemplo,

   nCambios []                          ==  0
   nCambios [6,5,-4,0,-2,-7,0,-8,-1,4]  ==  2
   nCambios [6,5,-4,0, 2,-7,0,-8,-1,4]  ==  4

nCambios [] == 0

nCambios [6,5,-4,0,-2,-7,0,-8,-1,4] == 2

nCambios [6,5,-4,0, 2,-7,0,-8,-1,4] == 4

Soluciones

import Data.List (group)

-- 1ª definición
nCambios1 :: (Num a, Ord a) => [a] -> Int
nCambios1 = length . cambios

-- (cambios xs) es la lista de los pares de elementos de xs entre los
-- que se producen cambios de signo. Por ejemplo,
--    cambios [6,5,-4,0,-2,-7,0,-8,-1,4]  ==  [(5,-4),(-1,4)]
--    cambios [6,5,-4,0, 2,-7,0,-8,-1,4]  ==  [(5,-4),(-4,2),(2,-7),(-1,4)]
cambios :: (Num a, Ord a) => [a] -> [(a,a)]
cambios xs =
    [(x,y) | (x,y) <- zip ys (tail ys), x*y < 0]
    where ys = filter (/=0) xs

-- 2ª definición
nCambios2 :: (Num a, Ord a) => [a] -> Int
nCambios2 [] = 0
nCambios2 xs = length (group (filter (/=0) (map signum xs))) - 1

-- 3ª definición
nCambios3 :: (Num a, Ord a) => [a] -> Int
nCambios3 = pred . length . group . filter (/=0) . map signum

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

--    λ> nCambios1 (take (2*10^6) (cycle [3,0,-3]))
--    1333332
--    (3.84 secs, 679,805,392 bytes)
--    λ> nCambios2 (take (2*10^6) (cycle [3,0,-3]))
--    1333332
--    (0.98 secs, 694,247,368 bytes)
--    λ> nCambios3 (take (2*10^6) (cycle [3,0,-3]))
--    1333332
--    (0.95 secs, 708,118,976 bytes)

import Data.List (group)

-- 1ª definición

nCambios1 :: (Num a, Ord a) => [a] -> Int

nCambios1 = length . cambios

-- (cambios xs) es la lista de los pares de elementos de xs entre los

-- que se producen cambios de signo. Por ejemplo,

-- cambios [6,5,-4,0,-2,-7,0,-8,-1,4] == [(5,-4),(-1,4)]

-- cambios [6,5,-4,0, 2,-7,0,-8,-1,4] == [(5,-4),(-4,2),(2,-7),(-1,4)]

cambios :: (Num a, Ord a) => [a] -> [(a,a)]

cambios xs =

[(x,y) | (x,y) <- zip ys (tail ys), x*y < 0]

where ys = filter (/=0) xs

-- 2ª definición

nCambios2 :: (Num a, Ord a) => [a] -> Int

nCambios2 [] = 0

nCambios2 xs = length (group (filter (/=0) (map signum xs))) - 1

-- 3ª definición

nCambios3 :: (Num a, Ord a) => [a] -> Int

nCambios3 = pred . length . group . filter (/=0) . map signum

-- Comparación de eficiencia

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

-- λ> nCambios1 (take (2*10^6) (cycle [3,0,-3]))

-- 1333332

-- (3.84 secs, 679,805,392 bytes)

-- λ> nCambios2 (take (2*10^6) (cycle [3,0,-3]))

-- 1333332

-- (0.98 secs, 694,247,368 bytes)

-- λ> nCambios3 (take (2*10^6) (cycle [3,0,-3]))

-- 1333332

-- (0.95 secs, 708,118,976 bytes)

Dígitos visibles y ocultos

PorJosé A. Alonso 16-noviembre-201526-marzo-2022

Una cadena clave es una cadena que contiene dígitos visibles y ocultos. Los dígitos se ocultan mediante las primeras letras minúsculas: la ‘a’ oculta el ‘0’, la ‘b’ el ‘1’ y así sucesivamente hasta la ‘j’ que oculta el ‘9’. Los restantes símbolos de la cadena no tienen significado y se pueden ignorar.

Definir la función

   numeroOculto :: String -> Maybe Integer

1	numeroOculto :: String -> Maybe Integer

tal que (numeroOculto cs) es justo el número formado por los dígitos visibles u ocultos de la cadena clave cs, si cs tiene dígitos y Nothing en caso contrario. Por ejemplo,

   numeroOculto "jihgfedcba"            ==  Just 9876543210
   numeroOculto "JIHGFEDCBA"            ==  Nothing
   numeroOculto "el 23 de Enero"        ==  Just 423344
   numeroOculto "El 23 de Enero"        ==  Just 23344
   numeroOculto "El 23 de enero"        ==  Just 233444
   numeroOculto "Todo para nada"        ==  Just 300030
   numeroOculto (replicate (10^6) 'A')  ==  Nothing

numeroOculto "jihgfedcba" == Just 9876543210

numeroOculto "JIHGFEDCBA" == Nothing

numeroOculto "el 23 de Enero" == Just 423344

numeroOculto "El 23 de Enero" == Just 23344

numeroOculto "El 23 de enero" == Just 233444

numeroOculto "Todo para nada" == Just 300030

numeroOculto (replicate (10^6) 'A') == Nothing

Soluciones

import Data.Char (isDigit, ord, chr)

numeroOculto :: String -> Maybe Integer
numeroOculto cs | null aux  = Nothing
                | otherwise = Just (read aux)
    where aux = filter isDigit (map visible cs)

visible :: Char -> Char
visible c | c `elem` ['a'..'j'] = chr (ord c - n)
          | otherwise           = c
          where n = ord 'a' - ord '0'

import Data.Char (isDigit, ord, chr)

numeroOculto :: String -> Maybe Integer

numeroOculto cs | null aux = Nothing

| otherwise = Just (read aux)

where aux = filter isDigit (map visible cs)

visible :: Char -> Char

visible c | c `elem` ['a'..'j'] = chr (ord c - n)

| otherwise = c

where n = ord 'a' - ord '0'

Ramas a las que pertenece un elemento

PorJosé A. Alonso 1-abril-20151-mayo-2015

Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato

   data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

1	data Arbol a = H a \| N a (Arbol a) (Arbol a) deriving Show

Por ejemplo,

   ej1 :: Arbol Int
   ej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))

1 2	ej1 :: Arbol Int ej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))

Definir la función

   ramasCon :: Eq a => Arbol a -> a -> [[a]]

1	ramasCon :: Eq a => Arbol a -> a -> [[a]]

tal que (ramasCon a x) es la lista de las ramas del árbol a en las que aparece el elemento x. Por ejemplo,

  ramasCon ej1 2 ==  [[5,2,1],[5,2,2],[5,3,2]]

1	ramasCon ej1 2 == [[5,2,1],[5,2,2],[5,3,2]]

Soluciones

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

ej1 :: Arbol Int
ej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))

-- 1ª definición
-- =============

ramasCon :: Eq a => Arbol a -> a -> [[a]]
ramasCon a x = [ys | ys <- ramas a, x `elem` ys]

ramas :: Arbol a -> [[a]]
ramas (H x)     = [[x]]
ramas (N x i d) = [x:ys | ys <- ramas i ++ ramas d]

-- 2ª definición
-- =============

ramasCon2 :: Eq a => Arbol a -> a -> [[a]]
ramasCon2 a x = filter (x `elem`) (ramas2 a)

ramas2 :: Arbol a -> [[a]]
ramas2 (H x)     = [[x]]
ramas2 (N x i d) = map (x:) (ramas2 i ++ ramas2 d)

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

ej1 :: Arbol Int

ej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))

-- 1ª definición

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

ramasCon :: Eq a => Arbol a -> a -> [[a]]

ramasCon a x = [ys | ys <- ramas a, x `elem` ys]

ramas :: Arbol a -> [[a]]

ramas (H x) = [[x]]

ramas (N x i d) = [x:ys | ys <- ramas i ++ ramas d]

-- 2ª definición

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

ramasCon2 :: Eq a => Arbol a -> a -> [[a]]

ramasCon2 a x = filter (x `elem`) (ramas2 a)

ramas2 :: Arbol a -> [[a]]

ramas2 (H x) = [[x]]

ramas2 (N x i d) = map (x:) (ramas2 i ++ ramas2 d)

Productos simultáneos de dos y tres números consecutivos

PorJosé A. Alonso 3-marzo-201525-abril-2021

Definir la función

   productos :: Integer -> Integer -> [[Integer]]

1	productos :: Integer -> Integer -> [[Integer]]

tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,

   productos 2 6     ==  [[2,3]]
   productos 3 6     ==  [[1,2,3]]
   productos 4 1680  ==  [[5,6,7,8]]
   productos 2 5     ==  []

productos 2 6 == [[2,3]]

productos 3 6 == [[1,2,3]]

productos 4 1680 == [[5,6,7,8]]

productos 2 5 == []

Comprobar con QuickCheck que si n > 0 y x > 0, entonces

   productos n (product [x..x+n-1]) == [[x..x+n-1]]

1	productos n (product [x..x+n-1]) == [[x..x+n-1]]

Usando productos, definir la función

   productosDe2y3consecutivos :: [Integer]

1	productosDe2y3consecutivos :: [Integer]

cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,

   head productosDe2y3consecutivos  ==  6

1	head productosDe2y3consecutivos == 6

Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.

Soluciones

import Test.QuickCheck

-- 1ª definición
productos1 :: Integer -> Integer -> [[Integer]]
productos1 n x = [[y..y+n-1] | y <- [1..x],
                               product [y..y+n-1] == x]

-- 2ª definición
-- =============

-- Se puede reducir el intervalo de búsqueda teniendo en cuenta las
-- siguientes desigualdades
--    y*(y+1)* ... (y+n-1) = x
--    y^n <= x <= (y+n-1)^n
--    y <= x^(1/n), x^(1/n)-n+1 <= y
--    x^(1/n)-n+1 <= y <= x^(1/n)

productos2 :: Integer -> Integer -> [[Integer]]
productos2 n x = [[z..z+n-1] | z <- [y-n+1..y],
                               product [z..z+n-1] == x]
    where y = floor ((fromIntegral x)**(1/(fromIntegral n)))

productos :: Integer -> Integer -> [[Integer]]
productos = productos2

prop_productos n x =
    n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]]

-- La comprobación es
--    ghci> quickCheck prop_productos
--    +++ OK, passed 100 tests.
--    (0.10 secs, 26409644 bytes)

productosDe2y3consecutivos :: [Integer]
productosDe2y3consecutivos = [x| x <- [1..], 
                                 let ys = productos 2 x,
                                 not (null ys), 
                                 let zs = productos 3 x,
                                 not (null zs)] 

-- El cálculo es
--    ghci> take 2 productosDe2y3consecutivos
--    [6,210]
--    ghci> productos 2 210
--    [[14,15]]
--    ghci> productos 3 210
--    [[5,6,7]]

import Test.QuickCheck

-- 1ª definición

productos1 :: Integer -> Integer -> [[Integer]]

productos1 n x = [[y..y+n-1] | y <- [1..x],

product [y..y+n-1] == x]

-- 2ª definición

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

-- Se puede reducir el intervalo de búsqueda teniendo en cuenta las

-- siguientes desigualdades

-- y*(y+1)* ... (y+n-1) = x

-- y^n <= x <= (y+n-1)^n

-- y <= x^(1/n), x^(1/n)-n+1 <= y

-- x^(1/n)-n+1 <= y <= x^(1/n)

productos2 :: Integer -> Integer -> [[Integer]]

productos2 n x = [[z..z+n-1] | z <- [y-n+1..y],

product [z..z+n-1] == x]

where y = floor ((fromIntegral x)**(1/(fromIntegral n)))

productos :: Integer -> Integer -> [[Integer]]

productos = productos2

prop_productos n x =

n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]]

-- La comprobación es

-- ghci> quickCheck prop_productos

-- +++ OK, passed 100 tests.

-- (0.10 secs, 26409644 bytes)

productosDe2y3consecutivos :: [Integer]

productosDe2y3consecutivos = [x| x <- [1..],

let ys = productos 2 x,

not (null ys),

let zs = productos 3 x,

not (null zs)]

-- El cálculo es

-- ghci> take 2 productosDe2y3consecutivos

-- [6,210]

-- ghci> productos 2 210

-- [[14,15]]

-- ghci> productos 3 210

-- [[5,6,7]]

Mayor producto de n dígitos consecutivos de un número

PorJosé A. Alonso 12-febrero-201525-abril-2021

Definir la función

   mayorProducto :: Int -> Integer -> Integer

1	mayorProducto :: Int -> Integer -> Integer

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

   mayorProducto 2 325                  ==  10
   mayorProducto 5 11111                ==  1
   mayorProducto 5 113111               ==  3
   mayorProducto 5 110111               ==  0
   mayorProducto 5 10151112             ==  10
   mayorProducto 5 101511124            ==  10
   mayorProducto 5 (product [1..1000])  ==  41472

mayorProducto 2 325 == 10

mayorProducto 5 11111 == 1

mayorProducto 5 113111 == 3

mayorProducto 5 110111 == 0

mayorProducto 5 10151112 == 10

mayorProducto 5 101511124 == 10

mayorProducto 5 (product [1..1000]) == 41472

Soluciones

import Data.List (inits, tails)
import Data.Char (digitToInt)

-- 1ª solución
-- ===========

mayorProducto1 :: Int -> Integer -> Integer
mayorProducto1 n x = 
    maximum [product xs | xs <- segmentos n (cifras x)]

-- (cifras x) es la lista de las cifras del número x, de derecha a
-- izquierda. Por ejemplo, 
--    cifras 325  ==  [5,2,3]
cifras :: Integer -> [Integer]
cifras x 
    | x < 10    = [x]
    | otherwise = r : cifras q
    where (q,r) = quotRem x 10

-- (segmentos n xs) es la lista de los segmentos de longitud n de la
-- lista xs. Por ejemplo,
--    segmentos 2 [3,5,4,6]  ==  [[3,5],[5,4],[4,6]]
segmentos :: Int -> [Integer] -> [[Integer]]
segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs))

-- 2ª solución
-- ===========

mayorProducto2 :: Int -> Integer -> Integer
mayorProducto2 n x = maximum (aux ns)
    where ns     = [read [d] | d <- show x]
          aux xs | length xs < n = []
                 | otherwise     = product (take n xs) : aux (tail xs)

-- 3ª solución
-- ===========

mayorProducto3 :: Int -> Integer -> Integer
mayorProducto3 n = maximum . 
                   map (product . take n) .
                   filter ((>=n) . length) .
                   tails . 
                   cifras

-- 4ª solución
-- ===========

mayorProducto4 :: Int -> Integer -> Integer
mayorProducto4 n = maximum . 
                   map (product . map (fromIntegral . digitToInt)) . 
                   filter ((==n) . length) . 
                   concatMap inits . 
                   tails .
                   show

-- ---------------------------------------------------------------------
-- Comparación de soluciones                                          --
-- ---------------------------------------------------------------------

-- Tiempo (en segundos) del cálculo de (mayorProducto4 5 (product [1..]))
-- 
--    | Def | 10   | 100  | 1000 | 5000  |
--    |-----+------+------+------+-------|
--    | 1   | 0.01 | 0.01 | 0.04 |  0.34 |
--    | 2   | 0.01 | 0.01 | 0.07 |  2.86 |
--    | 3   | 0.01 | 0.01 | 0.06 | 12.48 |
--    | 4   | 0.00 | 0.12 |      |       |
...

import Data.List (inits, tails)

import Data.Char (digitToInt)

-- 1ª solución

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

mayorProducto1 :: Int -> Integer -> Integer

mayorProducto1 n x =

maximum [product xs | xs <- segmentos n (cifras x)]

-- (cifras x) es la lista de las cifras del número x, de derecha a

-- izquierda. Por ejemplo,

-- cifras 325 == [5,2,3]

cifras :: Integer -> [Integer]

cifras x

| x < 10 = [x]

| otherwise = r : cifras q

where (q,r) = quotRem x 10

-- (segmentos n xs) es la lista de los segmentos de longitud n de la

-- lista xs. Por ejemplo,

-- segmentos 2 [3,5,4,6] == [[3,5],[5,4],[4,6]]

segmentos :: Int -> [Integer] -> [[Integer]]

segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs))

-- 2ª solución

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

mayorProducto2 :: Int -> Integer -> Integer

mayorProducto2 n x = maximum (aux ns)

where ns = [read [d] | d <- show x]

aux xs | length xs < n = []

| otherwise = product (take n xs) : aux (tail xs)

-- 3ª solución

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

mayorProducto3 :: Int -> Integer -> Integer

mayorProducto3 n = maximum .

map (product . take n) .

filter ((>=n) . length) .

tails .

cifras

-- 4ª solución

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

mayorProducto4 :: Int -> Integer -> Integer

mayorProducto4 n = maximum .

map (product . map (fromIntegral . digitToInt)) .

filter ((==n) . length) .

concatMap inits .

tails .

show

-- ---------------------------------------------------------------------

-- Comparación de soluciones --

-- ---------------------------------------------------------------------

-- Tiempo (en segundos) del cálculo de (mayorProducto4 5 (product [1..]))

-- | Def | 10 | 100 | 1000 | 5000 |

-- |-----+------+------+------+-------|

-- | 1 | 0.01 | 0.01 | 0.04 | 0.34 |

-- | 2 | 0.01 | 0.01 | 0.07 | 2.86 |

-- | 3 | 0.01 | 0.01 | 0.06 | 12.48 |

-- | 4 | 0.00 | 0.12 | | |

...

Menor número triangular con más de n divisores

PorJosé A. Alonso 6-febrero-201525-abril-2021

La sucesión de los números triangulares se obtiene sumando los números naturales.

Así, el 7º número triangular es

   1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

1	1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Los primeros 10 números triangulares son

   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

1	1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Los divisores de los primeros 7 números triangulares son:

    1: 1
    3: 1,3
    6: 1,2,3,6
   10: 1,2,5,10
   15: 1,3,5,15
   21: 1,3,7,21
   28: 1,2,4,7,14,28

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

Como se puede observar, 28 es el menor número triangular con más de 5 divisores.

Definir la función

   menorTriangularConAlMenosNDivisores :: Int -> Integer

1	menorTriangularConAlMenosNDivisores :: Int -> Integer

tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,

   menorTriangularConAlMenosNDivisores 5    ==  28
   menorTriangularConAlMenosNDivisores 50   ==  25200
   menorTriangularConAlMenosNDivisores 500  ==  76576500

menorTriangularConAlMenosNDivisores 5 == 28

menorTriangularConAlMenosNDivisores 50 == 25200

menorTriangularConAlMenosNDivisores 500 == 76576500

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primes,primeFactors)

-- 1ª definición
-- =============

menorTriangularConAlMenosNDivisores1 :: Int -> Integer
menorTriangularConAlMenosNDivisores1 n = 
    head [x | x <- triangulares, nDivisores x >= n]

-- triangulares es la sucesión de los números triangulares. Por ejemplo,
--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
triangulares :: [Integer]
triangulares = scanl (+) 1 [2..]

-- (nDivisores x) es el número de divisores de x. Por ejemplo,
--    nDivisores 28  ==  6
nDivisores :: Integer -> Int
nDivisores x = 
    1 + length [y | y <- [1..x `div` 2], mod x y == 0]

-- 2ª solución
-- ===========

menorTriangularConAlMenosNDivisores2 :: Int -> Integer
menorTriangularConAlMenosNDivisores2 n = 
    head [x | x <- triangulares, nDivisores2 x >= n]

-- (nDivisores2 x) es el número de divisores de x. Por ejemplo,
--    nDivisores2 28  ==  6
nDivisores2 :: Integer -> Int
nDivisores2 n = product [1 + length xs | xs <- group (factoresPrimos n)]    

-- (factoresPrimos n) es la lista de los factores primos de n. Por
-- ejemplo, 
--    factoresPrimos 28  ==  [2,2,7]
factoresPrimos :: Integer -> [Integer]
factoresPrimos n = aux n primos
    where aux n (p:ps) 
              | p*p > n        = [n]
              | n `mod` p == 0 = p : aux (n `div` p) (p:ps)
              | otherwise      = aux n ps

-- primos es la lista de los números primos. Por ejemplo,
--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]
primos :: [Integer]
primos = 2 : filter ((==1) . length . factoresPrimos) [3,5..]

-- 3ª solución (usando primes)
-- ===========================

menorTriangularConAlMenosNDivisores3 :: Int -> Integer
menorTriangularConAlMenosNDivisores3 n = 
    head [x | x <- triangulares, nDivisores3 x >= n]

-- (nDivisores3 x) es el número de divisores de x. Por ejemplo,
--    nDivisores3 28  ==  6
nDivisores3 :: Integer -> Int
nDivisores3 n = product [1 + length xs | xs <- group (factoresPrimos3 n)]    

-- (factoresPrimos3 n) es la lista de los factores primos de n. Por
-- ejemplo, 
--    factoresPrimos3 28  ==  [2,2,7]
factoresPrimos3 n = aux n primes
  where
    aux n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : aux (n `div` p) (p:ps)
        | otherwise      = aux n ps

-- 4ª solución (usando primeFactors)
-- =================================

menorTriangularConAlMenosNDivisores4 :: Int -> Integer
menorTriangularConAlMenosNDivisores4 n = 
    head [x | x <- triangulares, nDivisores4 x >= n]

-- (nDivisores4 x) es el número de divisores de x. Por ejemplo,
--    nDivisores4 28  ==  6
nDivisores4 :: Integer -> Int
nDivisores4 n = product [1 + length xs | xs <- group (primeFactors n)]    

-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------

-- La comparación es
--    ghci> menorTriangularConAlMenosNDivisores1 50
--    25200
--    (1.25 secs, 200236512 bytes)
--    
--    ghci> menorTriangularConAlMenosNDivisores2 50
--    25200
--    (0.02 secs, 4199904 bytes)
--    
--    ghci> menorTriangularConAlMenosNDivisores3 50
--    25200
--    (0.03 secs, 6265128 bytes)
--    
--    ghci> menorTriangularConAlMenosNDivisores4 50
--    25200
--    (0.01 secs, 5753048 bytes)

100

101

102

import Data.List (group)

import Data.Numbers.Primes (primes,primeFactors)

-- 1ª definición

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

menorTriangularConAlMenosNDivisores1 :: Int -> Integer

menorTriangularConAlMenosNDivisores1 n =

head [x | x <- triangulares, nDivisores x >= n]

-- triangulares es la sucesión de los números triangulares. Por ejemplo,

-- take 10 triangulares == [1,3,6,10,15,21,28,36,45,55]

triangulares :: [Integer]

triangulares = scanl (+) 1 [2..]

-- (nDivisores x) es el número de divisores de x. Por ejemplo,

-- nDivisores 28 == 6

nDivisores :: Integer -> Int

nDivisores x =

1 + length [y | y <- [1..x `div` 2], mod x y == 0]

-- 2ª solución

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

menorTriangularConAlMenosNDivisores2 :: Int -> Integer

menorTriangularConAlMenosNDivisores2 n =

head [x | x <- triangulares, nDivisores2 x >= n]

-- (nDivisores2 x) es el número de divisores de x. Por ejemplo,

-- nDivisores2 28 == 6

nDivisores2 :: Integer -> Int

nDivisores2 n = product [1 + length xs | xs <- group (factoresPrimos n)]

-- (factoresPrimos n) es la lista de los factores primos de n. Por

-- ejemplo,

-- factoresPrimos 28 == [2,2,7]

factoresPrimos :: Integer -> [Integer]

factoresPrimos n = aux n primos

where aux n (p:ps)

| p*p > n = [n]

| n `mod` p == 0 = p : aux (n `div` p) (p:ps)

| otherwise = aux n ps

-- primos es la lista de los números primos. Por ejemplo,

-- take 10 primos == [2,3,5,7,11,13,17,19,23,29]

primos :: [Integer]

primos = 2 : filter ((==1) . length . factoresPrimos) [3,5..]

-- 3ª solución (usando primes)

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

menorTriangularConAlMenosNDivisores3 :: Int -> Integer

menorTriangularConAlMenosNDivisores3 n =

head [x | x <- triangulares, nDivisores3 x >= n]

-- (nDivisores3 x) es el número de divisores de x. Por ejemplo,

-- nDivisores3 28 == 6

nDivisores3 :: Integer -> Int

nDivisores3 n = product [1 + length xs | xs <- group (factoresPrimos3 n)]

-- (factoresPrimos3 n) es la lista de los factores primos de n. Por

-- ejemplo,

-- factoresPrimos3 28 == [2,2,7]

factoresPrimos3 n = aux n primes

where

aux n (p:ps)

| p*p > n = [n]

| n `mod` p == 0 = p : aux (n `div` p) (p:ps)

| otherwise = aux n ps

-- 4ª solución (usando primeFactors)

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

menorTriangularConAlMenosNDivisores4 :: Int -> Integer

menorTriangularConAlMenosNDivisores4 n =

head [x | x <- triangulares, nDivisores4 x >= n]

-- (nDivisores4 x) es el número de divisores de x. Por ejemplo,

-- nDivisores4 28 == 6

nDivisores4 :: Integer -> Int

nDivisores4 n = product [1 + length xs | xs <- group (primeFactors n)]

-- ---------------------------------------------------------------------

-- § Comparación de eficiencia --

-- ---------------------------------------------------------------------

-- La comparación es

-- ghci> menorTriangularConAlMenosNDivisores1 50

-- 25200

-- (1.25 secs, 200236512 bytes)

-- ghci> menorTriangularConAlMenosNDivisores2 50

-- 25200

-- (0.02 secs, 4199904 bytes)

-- ghci> menorTriangularConAlMenosNDivisores3 50

-- 25200

-- (0.03 secs, 6265128 bytes)

-- ghci> menorTriangularConAlMenosNDivisores4 50

-- 25200

-- (0.01 secs, 5753048 bytes)

División según una propiedad

PorJosé A. Alonso 28-enero-20154-febrero-2015

Enunciado

Definir la función

   divideSegun :: (a -> Bool) -> [a] -> [[a]]

1	divideSegun :: (a -> Bool) -> [a] -> [[a]]

tal que (divideSegun p xs) es la lista de los segmentos de xs cuyos elementos no cumplen la propiedad p. Por ejemplo,

   divideSegun even [3,5,2,7,6,8,9,1]  ==  [[3,5],[7],[9,1]]
   divideSegun odd  [3,5,2,7,6,8,9,1]  ==  [[2],[6,8]]

1 2	divideSegun even [3,5,2,7,6,8,9,1] == [[3,5],[7],[9,1]] divideSegun odd [3,5,2,7,6,8,9,1] == [[2],[6,8]]

Comprobar con QuickCheck que, para cualquier lista xs de números enteros, la concatenación de los elementos de (divideSegun even xs) es la lista de los elementos de xs que no son pares.

Soluciones

import Test.QuickCheck

divideSegun :: (a -> Bool) -> [a] -> [[a]]
divideSegun p xs 
    | null ys   = []
    | otherwise = ys : divideSegun p zs
    where (ys,zs) = break p (dropWhile p xs)

-- La propiedad es
prop_divideSegun :: [Int] -> Bool
prop_divideSegun xs =
    concat (divideSegun even xs) == filter (not . even) xs

-- La comprobación es 
--    ghci> quickCheck prop_divideSegun
--    +++ OK, passed 100 tests.

import Test.QuickCheck

divideSegun :: (a -> Bool) -> [a] -> [[a]]

divideSegun p xs

| null ys = []

| otherwise = ys : divideSegun p zs

where (ys,zs) = break p (dropWhile p xs)

-- La propiedad es

prop_divideSegun :: [Int] -> Bool

prop_divideSegun xs =

concat (divideSegun even xs) == filter (not . even) xs

-- La comprobación es

-- ghci> quickCheck prop_divideSegun

-- +++ OK, passed 100 tests.

Elemento más cercano que cumple una propiedad

PorJosé A. Alonso 9-julio-201426-marzo-2022

-- Definir la función
--    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
-- tal que (cercano p n xs) es el elemento de xs más cercano a n que
-- verifica la propiedad p. La búsqueda comienza en n y los elementos se
-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo, 
--    cercano (`elem` "aeiou") 6 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 1 "Sevilla"     ==  Just 'e'
--    cercano (`elem` "aeiou") 2 "Sevilla"     ==  Just 'i'
--    cercano (`elem` "aeiou") 5 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 9 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") (-3) "Sevilla"  ==  Just 'e'
--    cercano (>100) 4 [200,1,150,2,4]         ==  Just 150
--    cercano even 5 [1,3..99]                 ==  Nothing

-- Definir la función

-- cercano :: (a -> Bool) -> Int -> [a] -> Maybe a

-- tal que (cercano p n xs) es el elemento de xs más cercano a n que

-- verifica la propiedad p. La búsqueda comienza en n y los elementos se

-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo,

-- cercano (`elem` "aeiou") 6 "Sevilla" == Just 'a'

-- cercano (`elem` "aeiou") 1 "Sevilla" == Just 'e'

-- cercano (`elem` "aeiou") 2 "Sevilla" == Just 'i'

-- cercano (`elem` "aeiou") 5 "Sevilla" == Just 'a'

-- cercano (`elem` "aeiou") 9 "Sevilla" == Just 'a'

-- cercano (`elem` "aeiou") (-3) "Sevilla" == Just 'e'

-- cercano (>100) 4 [200,1,150,2,4] == Just 150

-- cercano even 5 [1,3..99] == Nothing

Soluciones

import Data.List

-- 1ª solución
-- ===========

cercano1 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano1 p n xs | null ys   = Nothing
                | otherwise = Just (head ys)
    where ys = filter p (ordenaPorCercanos xs n)

-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que
-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo, 
--    ordenaPorCercanos [0..9] 4     ==  [4,5,3,6,2,7,1,8,0,9]
--    ordenaPorCercanos [0..9] 7     ==  [7,8,6,9,5,4,3,2,1,0]
--    ordenaPorCercanos [0..9] 2     ==  [2,3,1,4,0,5,6,7,8,9]
--    ordenaPorCercanos [0..9] (-3)  ==  [0,1,2,3,4,5,6,7,8,9]
--    ordenaPorCercanos [0..9] 20    ==  [9,8,7,6,5,4,3,2,1,0]
ordenaPorCercanos :: [a] -> Int -> [a]
ordenaPorCercanos xs n 
    | n < 0          = xs
    | n >= length xs = reverse xs
    | otherwise      = z : intercala zs (reverse ys)
    where (ys,(z:zs)) = splitAt n xs

-- (intercala xs ys) es la lista obtenida intercalando los elementos de
-- las lista xs e ys. Por ejemplo,
--    intercala [1..4] [5..10]   ==  [1,5,2,6,3,7,4,8,9,10]
--    intercala [5..10] [1..4]   ==  [5,1,6,2,7,3,8,4,9,10]
intercala :: [a] -> [a] -> [a]
intercala [] ys = ys
intercala xs [] = xs
intercala (x:xs) (y:ys) = x : y : intercala xs ys

-- 2ª solución (usando find)
-- =========================

cercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano2 p n xs = find p (ordenaPorCercanos xs n)

import Data.List

-- 1ª solución

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

cercano1 :: (a -> Bool) -> Int -> [a] -> Maybe a

cercano1 p n xs | null ys = Nothing

| otherwise = Just (head ys)

where ys = filter p (ordenaPorCercanos xs n)

-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que

-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo,

-- ordenaPorCercanos [0..9] 4 == [4,5,3,6,2,7,1,8,0,9]

-- ordenaPorCercanos [0..9] 7 == [7,8,6,9,5,4,3,2,1,0]

-- ordenaPorCercanos [0..9] 2 == [2,3,1,4,0,5,6,7,8,9]

-- ordenaPorCercanos [0..9] (-3) == [0,1,2,3,4,5,6,7,8,9]

-- ordenaPorCercanos [0..9] 20 == [9,8,7,6,5,4,3,2,1,0]

ordenaPorCercanos :: [a] -> Int -> [a]

ordenaPorCercanos xs n

| n < 0 = xs

| n >= length xs = reverse xs

| otherwise = z : intercala zs (reverse ys)

where (ys,(z:zs)) = splitAt n xs

-- (intercala xs ys) es la lista obtenida intercalando los elementos de

-- las lista xs e ys. Por ejemplo,

-- intercala [1..4] [5..10] == [1,5,2,6,3,7,4,8,9,10]

-- intercala [5..10] [1..4] == [5,1,6,2,7,3,8,4,9,10]

intercala :: [a] -> [a] -> [a]

intercala [] ys = ys

intercala xs [] = xs

intercala (x:xs) (y:ys) = x : y : intercala xs ys

-- 2ª solución (usando find)

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

cercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a

cercano2 p n xs = find p (ordenaPorCercanos xs n)

Referencia

El ejercicio está basado en el problema del 12 de mayo de 1HaskellADay.

Empiezan con mayúscula

PorJosé A. Alonso 2-julio-201427-diciembre-2014

Enunciado

-- Ejercicio. Definir, por composición, la función
--    conMayuscula :: String -> Int
-- tal que (conMayuscula cs) es el número de palabras de cs que empiezan
-- con mayúscula. Por ejemplo.
--    conMayuscula "Juan vive en Sevilla o en Huelva"  ==  3

-- Ejercicio. Definir, por composición, la función

-- conMayuscula :: String -> Int

-- tal que (conMayuscula cs) es el número de palabras de cs que empiezan

-- con mayúscula. Por ejemplo.

-- conMayuscula "Juan vive en Sevilla o en Huelva" == 3

Soluciones

import Data.Char

conMayuscula :: String -> Int
conMayuscula = length . filter (isUpper . head) . words

import Data.Char

conMayuscula :: String -> Int

conMayuscula = length . filter (isUpper . head) . words

Buscaminas

PorJosé A. Alonso 19-junio-201425-abril-2021

Enunciado

-- El buscaminas es un juego cuyo objetivo es despejar un campo de minas
-- sin detonar ninguna. 
-- 
-- El campo de minas se representa mediante un cuadrado con NxN
-- casillas. Algunas casillas tienen un número, este número indica las
-- minas que hay en todas las casillas vecinas. Cada casilla tiene como
-- máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda
-- contiene dos minas, cada una representada por el número 9, y a la 
-- derecha se muestra el campo obtenido anotando las minas vecinas de
-- cada casilla
--    9 0 0 0       9 1 0 0
--    0 0 0 0       2 2 1 0
--    0 9 0 0       1 9 1 0
--    0 0 0 0       1 1 1 0
-- de la misma forma, la anotación del siguiente a la izquierda es el de
-- la derecha 
--    9 9 0 0 0     9 9 1 0 0
--    0 0 0 0 0     3 3 2 0 0
--    0 9 0 0 0     1 9 1 0 0
--
-- En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra
-- en http://bit.ly/1hWVNJD
-- 
-- Los campos de minas se representan mediante matrices: 
--    type Campo = Matrix Int
-- Por ejemplo, los anteriores campos de la izquierda se definen por
--    ejCampo1, ejCampo2 :: Campo
--    ejCampo1 = fromLists [[9,0,0,0],
--                          [0,0,0,0], 
--                          [0,9,0,0], 
--                          [0,0,0,0]]
--    ejCampo2 = fromLists [[9,9,0,0,0],
--                          [0,0,0,0,0],
--                          [0,9,0,0,0]]
-- 
-- Definir la función
--    buscaminas :: Campo -> Campo
-- tal que (buscaminas c) es el campo obtenido anotando las minas
-- vecinas de cada casilla. Por ejemplo,
--    ghci> buscaminas ejCampo1
--    ( 9 1 0 0 )
--    ( 2 2 1 0 )
--    ( 1 9 1 0 )
--    ( 1 1 1 0 )
--
--    ghci> buscaminas ejCampo2
--    ( 9 9 1 0 0 )
--    ( 3 3 2 0 0 )
--    ( 1 9 1 0 0 )
-- 
-- Nota. Las funciones de la librería de matrices útiles para este ejercicio
-- son fromLists, matrix, nrows y ncols.

-- El buscaminas es un juego cuyo objetivo es despejar un campo de minas

-- sin detonar ninguna.

-- El campo de minas se representa mediante un cuadrado con NxN

-- casillas. Algunas casillas tienen un número, este número indica las

-- minas que hay en todas las casillas vecinas. Cada casilla tiene como

-- máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda

-- contiene dos minas, cada una representada por el número 9, y a la

-- derecha se muestra el campo obtenido anotando las minas vecinas de

-- cada casilla

-- 9 0 0 0 9 1 0 0

-- 0 0 0 0 2 2 1 0

-- 0 9 0 0 1 9 1 0

-- 0 0 0 0 1 1 1 0

-- de la misma forma, la anotación del siguiente a la izquierda es el de

-- la derecha

-- 9 9 0 0 0 9 9 1 0 0

-- 0 0 0 0 0 3 3 2 0 0

-- 0 9 0 0 0 1 9 1 0 0

-- En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra

-- en http://bit.ly/1hWVNJD

-- Los campos de minas se representan mediante matrices:

-- type Campo = Matrix Int

-- Por ejemplo, los anteriores campos de la izquierda se definen por

-- ejCampo1, ejCampo2 :: Campo

-- ejCampo1 = fromLists [[9,0,0,0],

-- [0,0,0,0],

-- [0,9,0,0],

-- [0,0,0,0]]

-- ejCampo2 = fromLists [[9,9,0,0,0],

-- [0,0,0,0,0],

-- [0,9,0,0,0]]

-- Definir la función

-- buscaminas :: Campo -> Campo

-- tal que (buscaminas c) es el campo obtenido anotando las minas

-- vecinas de cada casilla. Por ejemplo,

-- ghci> buscaminas ejCampo1

-- ( 9 1 0 0 )

-- ( 2 2 1 0 )

-- ( 1 9 1 0 )

-- ( 1 1 1 0 )

-- ghci> buscaminas ejCampo2

-- ( 9 9 1 0 0 )

-- ( 3 3 2 0 0 )

-- ( 1 9 1 0 0 )

-- Nota. Las funciones de la librería de matrices útiles para este ejercicio

-- son fromLists, matrix, nrows y ncols.

Soluciones

import Data.Matrix

type Campo   = Matrix Int
type Casilla = (Int,Int)

ejCampo1, ejCampo2 :: Campo
ejCampo1 = fromLists [[9,0,0,0],
                      [0,0,0,0], 
                      [0,9,0,0], 
                      [0,0,0,0]]
ejCampo2 = fromLists [[9,9,0,0,0],
                      [0,0,0,0,0],
                      [0,9,0,0,0]]

-- 1ª solución
-- ===========

buscaminas1 :: Campo -> Campo
buscaminas1 c = matrix m n (\(i,j) -> minas c (i,j))
    where m = nrows c
          n = ncols c

-- (minas c (i,j)) es el número de minas en las casillas vecinas de la
-- (i,j) en el campo de mina c y es 9 si en (i,j) hay una mina. Por
-- ejemplo,
--    minas ejCampo (1,1)  ==  9
--    minas ejCampo (1,2)  ==  1
--    minas ejCampo (1,3)  ==  0
--    minas ejCampo (2,1)  ==  2
minas :: Campo -> Casilla -> Int
minas c (i,j) 
    | c!(i,j) == 9 = 9
    | otherwise    = length (filter (==9) [c!(x,y) | (x,y) <- vecinas m n (i,j)])
                     where m = nrows c
                           n = ncols c

-- (vecinas m n (i,j)) es la lista de las casillas vecinas de la (i,j) en
-- un campo de dimensiones mxn. Por ejemplo,
--    vecinas 4 (1,1)  ==  [(1,2),(2,1),(2,2)]
--    vecinas 4 (1,2)  ==  [(1,1),(1,3),(2,1),(2,2),(2,3)]
--    vecinas 4 (2,3)  ==  [(1,2),(1,3),(1,4),(2,2),(2,4),(3,2),(3,3),(3,4)]
vecinas :: Int -> Int -> Casilla -> [Casilla]
vecinas m n (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],
                             b <- [max 1 (j-1)..min n (j+1)],
                             (a,b) /= (i,j)]

-- 2ª solución
-- ===========

buscaminas2 :: Campo -> Campo
buscaminas2 c = matrix m n (\(i,j) -> minas (i,j))
    where m = nrows c
          n = ncols c
          minas :: Casilla -> Int
          minas (i,j) 
              | c!(i,j) == 9 = 9
              | otherwise    = 
                  length (filter (==9) [c!(x,y) | (x,y) <- vecinas (i,j)])
          vecinas :: Casilla -> [Casilla]
          vecinas (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],
                                   b <- [max 1 (j-1)..min n (j+1)],
                                   (a,b) /= (i,j)]

import Data.Matrix

type Campo = Matrix Int

type Casilla = (Int,Int)

ejCampo1, ejCampo2 :: Campo

ejCampo1 = fromLists [[9,0,0,0],

[0,0,0,0],

[0,9,0,0],

[0,0,0,0]]

ejCampo2 = fromLists [[9,9,0,0,0],

[0,0,0,0,0],

[0,9,0,0,0]]

-- 1ª solución

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

buscaminas1 :: Campo -> Campo

buscaminas1 c = matrix m n (\(i,j) -> minas c (i,j))

where m = nrows c

n = ncols c

-- (minas c (i,j)) es el número de minas en las casillas vecinas de la

-- (i,j) en el campo de mina c y es 9 si en (i,j) hay una mina. Por

-- ejemplo,

-- minas ejCampo (1,1) == 9

-- minas ejCampo (1,2) == 1

-- minas ejCampo (1,3) == 0

-- minas ejCampo (2,1) == 2

minas :: Campo -> Casilla -> Int

minas c (i,j)

| c!(i,j) == 9 = 9

| otherwise = length (filter (==9) [c!(x,y) | (x,y) <- vecinas m n (i,j)])

where m = nrows c

n = ncols c

-- (vecinas m n (i,j)) es la lista de las casillas vecinas de la (i,j) en

-- un campo de dimensiones mxn. Por ejemplo,

-- vecinas 4 (1,1) == [(1,2),(2,1),(2,2)]

-- vecinas 4 (1,2) == [(1,1),(1,3),(2,1),(2,2),(2,3)]

-- vecinas 4 (2,3) == [(1,2),(1,3),(1,4),(2,2),(2,4),(3,2),(3,3),(3,4)]

vecinas :: Int -> Int -> Casilla -> [Casilla]

vecinas m n (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],

b <- [max 1 (j-1)..min n (j+1)],

(a,b) /= (i,j)]

-- 2ª solución

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

buscaminas2 :: Campo -> Campo

buscaminas2 c = matrix m n (\(i,j) -> minas (i,j))

where m = nrows c

n = ncols c

minas :: Casilla -> Int

minas (i,j)

| c!(i,j) == 9 = 9

| otherwise =

length (filter (==9) [c!(x,y) | (x,y) <- vecinas (i,j)])

vecinas :: Casilla -> [Casilla]

vecinas (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],

b <- [max 1 (j-1)..min n (j+1)],

(a,b) /= (i,j)]

Referencia

El ejercicio está basado en Minesweeper de UVa Online Judge.

Soluciones

Soluciones

Soluciones

Referencias

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Soluciones

En Maxima

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Enunciado

Soluciones

Soluciones

Referencia

Enunciado

Soluciones

Enunciado

Soluciones

Referencia

Entradas recientes

Buscar

Correo electrónico