and

Menor contenedor de primos

PorJosé A. Alonso 10-diciembre-201817-enero-2019

El n-ésimo menor contenenedor de primos es el menor número que contiene como subcadenas los primeros n primos. Por ejemplo, el 6º menor contenedor de primos es 113257 ya que es el menor que contiene como subcadenas los 6 primeros primos (2, 3, 5, 7, 11 y 13).

Definir la función

   menorContenedor :: Int -> Int

1	menorContenedor :: Int -> Int

tal que (menorContenedor n) es el n-ésimo menor contenenedor de primos. Por ejemplo,

   menorContenedor 1  ==  2
   menorContenedor 2  ==  23
   menorContenedor 3  ==  235
   menorContenedor 4  ==  2357
   menorContenedor 5  ==  112357
   menorContenedor 6  ==  113257

menorContenedor 1 == 2

menorContenedor 2 == 23

menorContenedor 3 == 235

menorContenedor 4 == 2357

menorContenedor 5 == 112357

menorContenedor 6 == 113257

Soluciones

import Data.List           (isInfixOf)
import Data.Numbers.Primes (primes)

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

menorContenedor :: Int -> Int
menorContenedor n =
  head [x | x <- [2..]
          , and [contenido y x | y <- take n primes]]

contenido :: Int -> Int -> Bool
contenido x y =
  show x `isInfixOf` show y

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

menorContenedor2 :: Int -> Int
menorContenedor2 n =
  head [x | x <- [2..]
          , all (`contenido` x) (take n primes)]

import Data.List (isInfixOf)

import Data.Numbers.Primes (primes)

-- 1ª solución

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

menorContenedor :: Int -> Int

menorContenedor n =

head [x | x <- [2..]

, and [contenido y x | y <- take n primes]]

contenido :: Int -> Int -> Bool

contenido x y =

show x `isInfixOf` show y

-- 2ª solución

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

menorContenedor2 :: Int -> Int

menorContenedor2 n =

head [x | x <- [2..]

, all (`contenido` x) (take n primes)]

Pensamiento

¡Ya hay hombres activos!
Soñaba la charca
con sus mosquitos.

Antonio Machado

Números colinas

PorJosé A. Alonso 29-noviembre-201819-enero-2019

Se dice que un número natural n es una colina si su primer dígito es igual a su último dígito, los primeros dígitos son estrictamente creciente hasta llegar al máximo, el máximo se puede repetir y los dígitos desde el máximo al final son estrictamente decrecientes.

Definir la función

   esColina :: Integer -> Bool

1	esColina :: Integer -> Bool

tal que (esColina n) se verifica si n es un número colina. Por ejemplo,

   esColina 12377731  ==  True
   esColina 1237731   ==  True
   esColina 123731    ==  True
   esColina 122731    ==  False
   esColina 12377730  ==  False
   esColina 12377730  ==  False
   esColina 10377731  ==  False
   esColina 12377701  ==  False
   esColina 33333333  ==  True

esColina 12377731 == True

esColina 1237731 == True

esColina 123731 == True

esColina 122731 == False

esColina 12377730 == False

esColina 10377731 == False

esColina 12377701 == False

esColina 33333333 == True

Soluciones

import Data.Char (digitToInt)

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

esColina :: Integer -> Bool
esColina n =
  head ds == last ds &&
  esCreciente xs &&
  esDecreciente ys
  where ds = digitos n
        m  = maximum ds
        xs = takeWhile (<m) ds
        ys = dropWhile (==m) (dropWhile (<m) ds)

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 425  ==  [4,2,5]
digitos :: Integer -> [Int]
digitos n = map digitToInt (show n)

-- (esCreciente xs) se verifica si la lista xs es estrictamente
-- creciente. Por ejemplo,
--    esCreciente [2,4,7]  ==  True
--    esCreciente [2,2,7]  ==  False
--    esCreciente [2,1,7]  ==  False
esCreciente :: [Int] -> Bool
esCreciente xs = and [x < y | (x,y) <- zip xs (tail xs)]

-- (esDecreciente xs) se verifica si la lista xs es estrictamente
-- decreciente. Por ejemplo,
--    esDecreciente [7,4,2]  ==  True
--    esDecreciente [7,2,2]  ==  False
--    esDecreciente [7,1,2]  ==  False
esDecreciente :: [Int] -> Bool
esDecreciente xs = and [x > y | (x,y) <- zip xs (tail xs)]

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

esColina2 :: Integer -> Bool
esColina2 n =
  head ds == last ds &&
  null (dropWhile (==(-1)) (dropWhile (==0) (dropWhile (==1) xs)))
  where ds = digitos n
        xs = [signum (y-x) | (x,y) <- zip ds (tail ds)] 

-- Equivalencia
-- ============

-- La propiedad de equivalencia es
prop_esColina :: Integer -> Property
prop_esColina n =
  n >= 0 ==> esColina n == esColina2 n 

-- La comprobación es
--    λ> quickCheck prop_esColina
--    +++ OK, passed 100 tests.

import Data.Char (digitToInt)

-- 1ª definición

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

esColina :: Integer -> Bool

esColina n =

head ds == last ds &&

esCreciente xs &&

esDecreciente ys

where ds = digitos n

m = maximum ds

xs = takeWhile (<m) ds

ys = dropWhile (==m) (dropWhile (<m) ds)

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 425 == [4,2,5]

digitos :: Integer -> [Int]

digitos n = map digitToInt (show n)

-- (esCreciente xs) se verifica si la lista xs es estrictamente

-- creciente. Por ejemplo,

-- esCreciente [2,4,7] == True

-- esCreciente [2,2,7] == False

-- esCreciente [2,1,7] == False

esCreciente :: [Int] -> Bool

esCreciente xs = and [x < y | (x,y) <- zip xs (tail xs)]

-- (esDecreciente xs) se verifica si la lista xs es estrictamente

-- decreciente. Por ejemplo,

-- esDecreciente [7,4,2] == True

-- esDecreciente [7,2,2] == False

-- esDecreciente [7,1,2] == False

esDecreciente :: [Int] -> Bool

esDecreciente xs = and [x > y | (x,y) <- zip xs (tail xs)]

-- 2ª definición

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

esColina2 :: Integer -> Bool

esColina2 n =

head ds == last ds &&

null (dropWhile (==(-1)) (dropWhile (==0) (dropWhile (==1) xs)))

where ds = digitos n

xs = [signum (y-x) | (x,y) <- zip ds (tail ds)]

-- Equivalencia

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

-- La propiedad de equivalencia es

prop_esColina :: Integer -> Property

prop_esColina n =

n >= 0 ==> esColina n == esColina2 n

-- La comprobación es

-- λ> quickCheck prop_esColina

-- +++ OK, passed 100 tests.

Referencia

Basado en el problema Is this number a hill number? de Code Golf

Pensamiento

Si me tengo que morir
poco me importa aprender.
Y si no puedo saber,
poco me importa vivir.

Antonio Machado

Relación definida por una partición

PorJosé A. Alonso 22-noviembre-201819-enero-2019

Dos elementos están relacionados por una partición xss si pertenecen al mismo elemento de xss.

Definir la función

   relacionados :: Eq a => [[a]] -> a -> a -> Bool

1	relacionados :: Eq a => [[a]] -> a -> a -> Bool

tal que (relacionados xss y z) se verifica si los elementos y y z están relacionados por la partición xss. Por ejemplo,

   relacionados [[1,3],[2],[9,5,7]] 7 9  ==  True
   relacionados [[1,3],[2],[9,5,7]] 3 9  ==  False
   relacionados [[1,3],[2],[9,5,7]] 4 9  ==  False

relacionados [[1,3],[2],[9,5,7]] 7 9 == True

relacionados [[1,3],[2],[9,5,7]] 3 9 == False

relacionados [[1,3],[2],[9,5,7]] 4 9 == False

Soluciones

import Data.List ((\\), intersect)

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

relacionados :: Eq a => [[a]] -> a -> a -> Bool
relacionados [] _ _ = False
relacionados (xs:xss) y z
  | y `elem` xs = z `elem` xs
  | otherwise   = relacionados xss y z

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

relacionados2 :: Eq a => [[a]] -> a -> a -> Bool
relacionados2 xss y z =
  or [elem y xs && elem z xs | xs <- xss]

-- 3ª definición
-- =============

relacionados3 :: Eq a => [[a]] -> a -> a -> Bool
relacionados3 xss y z =
  or [[y,z] `subconjunto` xs | xs <- xss]

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys; es
-- decir, si todos los elementos de xs pertenecen a ys. Por ejemplo,  
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto xs ys = and [elem x ys | x <- xs]

-- 4ª definición
-- =============

relacionados4 :: Eq a => [[a]] -> a -> a -> Bool
relacionados4 xss y z =
  any ([y,z] `subconjunto`) xss

import Data.List ((\\), intersect)

-- 1ª definición

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

relacionados :: Eq a => [[a]] -> a -> a -> Bool

relacionados [] _ _ = False

relacionados (xs:xss) y z

| y `elem` xs = z `elem` xs

| otherwise = relacionados xss y z

-- 2ª definición

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

relacionados2 :: Eq a => [[a]] -> a -> a -> Bool

relacionados2 xss y z =

or [elem y xs && elem z xs | xs <- xss]

-- 3ª definición

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

relacionados3 :: Eq a => [[a]] -> a -> a -> Bool

relacionados3 xss y z =

or [[y,z] `subconjunto` xs | xs <- xss]

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys; es

-- decir, si todos los elementos de xs pertenecen a ys. Por ejemplo,

-- subconjunto [3,2,3] [2,5,3,5] == True

-- subconjunto [3,2,3] [2,5,6,5] == False

subconjunto :: Eq a => [a] -> [a] -> Bool

subconjunto xs ys = and [elem x ys | x <- xs]

-- 4ª definición

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

relacionados4 :: Eq a => [[a]] -> a -> a -> Bool

relacionados4 xss y z =

any ([y,z] `subconjunto`) xss

Pensamiento

No hay lío político que no sea un trueque, una confusión de máscaras, un mal ensayo de comedia, en que nadie sabe su papel.

Antonio Machado

Reconocimiento de particiones

PorJosé A. Alonso 21-noviembre-201819-enero-2019

Una partición de un conjunto es una división del mismo en subconjuntos disjuntos no vacíos.

Definir la función

   esParticion :: Eq a => [[a]] -> Bool

1	esParticion :: Eq a => [[a]] -> Bool

tal que (esParticion xss) se verifica si xss es una partición; es decir sus elementos son listas no vacías disjuntas. Por ejemplo.

   esParticion [[1,3],[2],[9,5,7]]  ==  True
   esParticion [[1,3],[2],[9,5,1]]  ==  False
   esParticion [[1,3],[],[9,5,7]]   ==  False
   esParticion [[2,3,2],[4]]        ==  True

esParticion [[1,3],[2],[9,5,7]] == True

esParticion [[1,3],[2],[9,5,1]] == False

esParticion [[1,3],[],[9,5,7]] == False

esParticion [[2,3,2],[4]] == True

Soluciones

import Data.List ((\\), intersect)

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

esParticion :: Eq a => [[a]] -> Bool
esParticion xss =
  [] `notElem` xss &&
  and [disjuntos xs ys | xs <- xss, ys <- xss \\ [xs]] 

disjuntos :: Eq a => [a] -> [a] -> Bool
disjuntos xs ys = null (xs `intersect` ys)

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

esParticion2 :: Eq a => [[a]] -> Bool
esParticion2 []       = True
esParticion2 (xs:xss) =
  not (null xs) &&
  and [disjuntos xs ys | ys <- xss] &&
  esParticion2 xss

-- 3ª definición
-- =============

esParticion3 :: Eq a => [[a]] -> Bool
esParticion3 []       = True
esParticion3 (xs:xss) =
  not (null xs) &&
  all (disjuntos xs) xss &&
  esParticion3 xss

-- Equivalencia
prop_equiv :: [[Int]] -> Bool
prop_equiv xss =
  and [esParticion xss == f xss | f <- [ esParticion2
                                       , esParticion3]]

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

-- Comparación de eficiencia:
--    λ> esParticion [[x] | x <- [1..3000]]
--    True
--    (4.37 secs, 3,527,956,400 bytes)
--    λ> esParticion2 [[x] | x <- [1..3000]]
--    True
--    (1.26 secs, 1,045,792,552 bytes)
--    λ> esParticion3 [[x] | x <- [1..3000]]
--    True
--    (1.30 secs, 1,045,795,272 bytes)
--    λ> esParticion3 [[x] | x <- [1..3000]]
--    True
--    (1.30 secs, 1,045,795,272 bytes)

import Data.List ((\\), intersect)

-- 1ª definición

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

esParticion :: Eq a => [[a]] -> Bool

esParticion xss =

[] `notElem` xss &&

and [disjuntos xs ys | xs <- xss, ys <- xss \\ [xs]]

disjuntos :: Eq a => [a] -> [a] -> Bool

disjuntos xs ys = null (xs `intersect` ys)

-- 2ª definición

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

esParticion2 :: Eq a => [[a]] -> Bool

esParticion2 [] = True

esParticion2 (xs:xss) =

not (null xs) &&

and [disjuntos xs ys | ys <- xss] &&

esParticion2 xss

-- 3ª definición

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

esParticion3 :: Eq a => [[a]] -> Bool

esParticion3 [] = True

esParticion3 (xs:xss) =

not (null xs) &&

all (disjuntos xs) xss &&

esParticion3 xss

-- Equivalencia

prop_equiv :: [[Int]] -> Bool

prop_equiv xss =

and [esParticion xss == f xss | f <- [ esParticion2

, esParticion3]]

-- Comprobación

-- λ> quickCheck prop_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:

-- λ> esParticion [[x] | x <- [1..3000]]

-- True

-- (4.37 secs, 3,527,956,400 bytes)

-- λ> esParticion2 [[x] | x <- [1..3000]]

-- True

-- (1.26 secs, 1,045,792,552 bytes)

-- λ> esParticion3 [[x] | x <- [1..3000]]

-- True

-- (1.30 secs, 1,045,795,272 bytes)

-- λ> esParticion3 [[x] | x <- [1..3000]]

-- True

-- (1.30 secs, 1,045,795,272 bytes)

Pensamiento

Sentía los cuatro vientos,
en la encrucijada
de su pensamiento.

Antonio Machado

Listas equidigitales

PorJosé A. Alonso 9-noviembre-201817-enero-2019

Una lista de números naturales es equidigital si todos sus elementos tienen el mismo número de dígitos.

Definir la función

   equidigital :: [Int] -> Bool

1	equidigital :: [Int] -> Bool

tal que (equidigital xs) se verifica si xs es una lista equidigital. Por ejemplo,

   equidigital [343,225,777,943]   ==  True
   equidigital [343,225,777,94,3]  ==  False

1 2	equidigital [343,225,777,943] == True equidigital [343,225,777,94,3] == False

Soluciones

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

equidigital :: [Int] -> Bool
equidigital xs = todosIguales (numerosDeDigitos xs)

-- (numerosDeDigitos xs) es la lista de los números de dígitos de
-- los elementos de xs. Por ejemplo, 
--    numerosDeDigitos [343,225,777,943]   ==  [3,3,3,3]
--    numerosDeDigitos [343,225,777,94,3]  ==  [3,3,3,2,1]
numerosDeDigitos :: [Int] -> [Int]
numerosDeDigitos xs = [numeroDeDigitos x | x <- xs]

-- (numeroDeDigitos x) es el número de dígitos de x. Por ejemplo,
--    numeroDeDigitos 475  ==  3
numeroDeDigitos :: Int -> Int
numeroDeDigitos x = length (show x)

-- (todosIguales xs) se verifica si todos los elementos de xs son
-- iguales. Por ejemplo,
--    todosIguales [3,3,3,3]    ==  True
--    todosIguales [3,3,3,2,1]  ==  False
todosIguales (x:y:zs) = x == y && todosIguales (y:zs)
todosIguales _        = True

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

equidigital2 :: [Int] -> Bool
equidigital2 []     = True
equidigital2 (x:xs) = and [numeroDeDigitos y == n | y <- xs]
    where n = numeroDeDigitos x

-- 3ª definición
-- =============

equidigital3 :: [Int] -> Bool
equidigital3 (x:y:zs) = numeroDeDigitos x == numeroDeDigitos y &&
                        equidigital3 (y:zs)
equidigital3 _        = True

-- 1ª definición

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

equidigital :: [Int] -> Bool

equidigital xs = todosIguales (numerosDeDigitos xs)

-- (numerosDeDigitos xs) es la lista de los números de dígitos de

-- los elementos de xs. Por ejemplo,

-- numerosDeDigitos [343,225,777,943] == [3,3,3,3]

-- numerosDeDigitos [343,225,777,94,3] == [3,3,3,2,1]

numerosDeDigitos :: [Int] -> [Int]

numerosDeDigitos xs = [numeroDeDigitos x | x <- xs]

-- (numeroDeDigitos x) es el número de dígitos de x. Por ejemplo,

-- numeroDeDigitos 475 == 3

numeroDeDigitos :: Int -> Int

numeroDeDigitos x = length (show x)

-- (todosIguales xs) se verifica si todos los elementos de xs son

-- iguales. Por ejemplo,

-- todosIguales [3,3,3,3] == True

-- todosIguales [3,3,3,2,1] == False

todosIguales (x:y:zs) = x == y && todosIguales (y:zs)

todosIguales _ = True

-- 2ª definición

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

equidigital2 :: [Int] -> Bool

equidigital2 [] = True

equidigital2 (x:xs) = and [numeroDeDigitos y == n | y <- xs]

where n = numeroDeDigitos x

-- 3ª definición

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

equidigital3 :: [Int] -> Bool

equidigital3 (x:y:zs) = numeroDeDigitos x == numeroDeDigitos y &&

equidigital3 (y:zs)

equidigital3 _ = True

Pensamiento

Se miente más de la cuenta
por falta de fantasía:
también la verdad se inventa.

Antonio Machado

Menor contenedor de primos

Soluciones

Pensamiento

Números colinas

Soluciones

Referencia

Pensamiento

Relación definida por una partición

Soluciones

Pensamiento

Reconocimiento de particiones

Soluciones

Pensamiento

Listas equidigitales

Soluciones

Pensamiento

Entradas recientes

Buscar

Correo electrónico