José A. Alonso

Números bigenerados

PorJosé A. Alonso 14-enero-202121-enero-2021

Se dice que y es un generador de x si x es igual a la suma de y los dígitos de y. Por ejemplo, 1996 y 2014 son generadores de 2021 ya que

   2021 = 1996 + 1 + 9 + 9 + 6
   2021 = 2014 + 2 + 0 + 1 + 4

1 2	2021 = 1996 + 1 + 9 + 9 + 6 2021 = 2014 + 2 + 0 + 1 + 4

Un número bigenerado es un número que tiene exactamente 2 generadores. Por ejemplo,

2021 es un número bigenerados y sus generadores son 1996 y 2014
20 no es bigenerador porque no tiene ningún generador
21 no es bigenerador porque tiene sólo un generador (el 15).
101 es el menor número bigenerado ysus generadores son 91 y 100.

Definir las funciones

   esBigenerado :: Integer -> Bool
   bigenerados  :: [Integer]

1 2	esBigenerado :: Integer -> Bool bigenerados :: [Integer]

tales que

(esBigenerado x) se verifica si x es bigenerado. Por ejemplo,

     esBigenerado 2021  ==  True
     esBigenerado 20    ==  False
     esBigenerado 21    ==  False
     esBigenerado 101   ==  True

esBigenerado 2021 == True

esBigenerado 20 == False

esBigenerado 21 == False

esBigenerado 101 == True

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

     λ> take 12 bigenerados
     [101,103,105,107,109,111,113,115,117,202,204,206]

1 2	λ> take 12 bigenerados [101,103,105,107,109,111,113,115,117,202,204,206]

Comprobar con QuickCheck que la lista de los números bigenerados es infinita; es decir, para cualquier número positivo n existe un y mayor que x que es bigenerado.

Soluciones

import Test.QuickCheck (Property, (==>), quickCheck)

esBigenerado :: Integer -> Bool
esBigenerado x = length (generadores x) == 2

-- (generadores x) es la lista de los generadores de x. Por ejemplo,
--    generadores 2021  ==  [1996,2014]
--    generadores 20    ==  []
--    generadores 21    ==  [15]
--    generadores 101   ==  [91,100]
generadores :: Integer -> [Integer]
generadores x = filter (esGenerador x) [1..x]

-- (esGenerador x y) se verifica si y es un generador de x. Por ejemplo,
--    esGenerador 818 796  ==  True
--    esGenerador 818 805  ==  True
esGenerador :: Integer -> Integer -> Bool
esGenerador x y = x == y + sumaDigitos y

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitos 2021  ==  5
sumaDigitos :: Integer -> Integer
sumaDigitos = sum . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 2021  ==  [2,0,2,1]
digitos :: Integer -> [Integer]
digitos x = [read [c] | c <- show x]

bigenerados :: [Integer]
bigenerados = filter esBigenerado [1..]

-- La propiedad es
prop_bigenerados :: Integer -> Property
prop_bigenerados n =
  n >= 0 ==> any esBigenerado [n+1..]

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

import Test.QuickCheck (Property, (==>), quickCheck)

esBigenerado :: Integer -> Bool

esBigenerado x = length (generadores x) == 2

-- (generadores x) es la lista de los generadores de x. Por ejemplo,

-- generadores 2021 == [1996,2014]

-- generadores 20 == []

-- generadores 21 == [15]

-- generadores 101 == [91,100]

generadores :: Integer -> [Integer]

generadores x = filter (esGenerador x) [1..x]

-- (esGenerador x y) se verifica si y es un generador de x. Por ejemplo,

-- esGenerador 818 796 == True

-- esGenerador 818 805 == True

esGenerador :: Integer -> Integer -> Bool

esGenerador x y = x == y + sumaDigitos y

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,

-- sumaDigitos 2021 == 5

sumaDigitos :: Integer -> Integer

sumaDigitos = sum . digitos

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

-- digitos 2021 == [2,0,2,1]

digitos :: Integer -> [Integer]

digitos x = [read [c] | c <- show x]

bigenerados :: [Integer]

bigenerados = filter esBigenerado [1..]

-- La propiedad es

prop_bigenerados :: Integer -> Property

prop_bigenerados n =

n >= 0 ==> any esBigenerado [n+1..]

-- La comprobación es

-- λ> quickCheck prop_bigenerados

-- +++ OK, passed 100 tests.

Nuevas soluciones

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

Números cíclicos

PorJosé A. Alonso 13-enero-202120-enero-2021

La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo,

φ(15) = 8 ya que los números menores o iguales a 36 y coprimos con 36 son ocho: 1, 2, 4, 7, 8, 11, 13 y 14.
φ(21) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 y 20.

Un número n es un número cíclico si n y φ(n) no tiene ningún divisor primo común. Por ejemplo, el número 15 es cíclico ya que 15 y 8 (que es φ(15)) no tiene ningún divisor primo común; en cambio, el número 21 no es cíclico ya 21 y 12 (que es φ(21)) son divisibles por 3.

Definir las funciones

   esCiclico :: Integer -> Bool
   ciclicos  :: [Integer]

1 2	esCiclico :: Integer -> Bool ciclicos :: [Integer]

tales que

(esCiclico n) se verifica si n es un número cíclico. Por ejemplo,

     esCiclico 15    ==  True
     esCiclico 16    ==  False
     esCiclico 2021  ==  True
     esCiclico (product [1..10^4])  ==  False

esCiclico 15 == True

esCiclico 16 == False

esCiclico 2021 == True

esCiclico (product [1..10^4]) == False

ciclicos es la lista de los números cíclicos. Por ejemplo,

     λ> take 20 ciclicos
     [2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]
     λ> ciclicos !! (10^5)
     336059

λ> take 20 ciclicos

[2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]

λ> ciclicos !! (10^5)

336059

Comprobar con QuickCheck que todos los números primos mayores que 2 son cíclicos.

Soluciones

module Numeros_ciclicos where

import Data.List (genericLength, group)
import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck (Property, (==>), quickCheck)

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

ciclicos1 :: [Integer]
ciclicos1 = filter esCiclico1 [2..]

esCiclico1 :: Integer -> Bool
esCiclico1 n = gcd n (phi1 n) == 1

-- (phi1 n) es igual a φ(n). Por ejemplo,
--    phi1 15    ==  8
--    phi1 21    ==  12
--    phi1 2021  ==  1932
phi1 :: Integer -> Integer
phi1 n = genericLength [x | x <- [1..n], gcd x n == 1]

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

ciclicos2 :: [Integer]
ciclicos2 = filter esCiclico2 [2..]

esCiclico2 :: Integer -> Bool
esCiclico2 n = gcd n (phi2 n) == 1

-- (phi2 n) es igual a φ(n). Por ejemplo,
--    phi2 15    ==  8
--    phi2 21    ==  12
--    phi2 2021  ==  1932
phi2 :: Integer -> Integer
phi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]

-- (factorizacion n) es la descomposición de n en factores primos como
-- una lista de pares donde los primeros elementos son la base y los
-- segundo son los exponentes. Por ejemplo,
--    factorizacion 3000  ==  [(2,3),(3,1),(5,3)]
-- ya que 3000 = 2^3*3*5^3
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(head xs,genericLength xs) | xs <- group (primeFactors n)]

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

ciclicos3 :: [Integer]
ciclicos3 = filter esCiclico3 [2..]

esCiclico3 :: Integer -> Bool
esCiclico3 n = gcd n (phi3 n) == 1

-- (phi3 n) es igual a φ(n). Por ejemplo,
--    phi3 15    ==  8
--    phi3 21    ==  12
--    phi3 2021  ==  1932
phi3 :: Integer -> Integer
phi3 n =
  product [(x-1) * product xs | (x:xs) <- group (primeFactors n)]

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

-- La comparación es
--    λ> esCiclico1 (4*10^6)
--    False
--    (3.64 secs, 4,448,223,616 bytes)
--    λ> esCiclico2 (4*10^6)
--    False
--    (0.01 secs, 116,144 bytes)
--    λ> esCiclico3 (4*10^6)
--    False
--    (0.01 secs, 111,336 bytes)
--
--    λ> esCiclico2 (product [1..3*10^4])
--    False
--    (2.49 secs, 5,846,361,904 bytes)
--    λ> esCiclico3 (product [1..3*10^4])
--    False
--    (2.50 secs, 5,947,164,552 bytes)


-- Verificación de la propiedad
-- ============================

-- La propiedad es
prop_ciclicos :: Int -> Property
prop_ciclicos n =
    n > 1 ==> esCiclico3 (primes !! n)

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

verificacion :: IO ()
verificacion = quickCheck prop_ciclicos

100

module Numeros_ciclicos where

import Data.List (genericLength, group)

import Data.Numbers.Primes (primeFactors, primes)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª definición

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

ciclicos1 :: [Integer]

ciclicos1 = filter esCiclico1 [2..]

esCiclico1 :: Integer -> Bool

esCiclico1 n = gcd n (phi1 n) == 1

-- (phi1 n) es igual a φ(n). Por ejemplo,

-- phi1 15 == 8

-- phi1 21 == 12

-- phi1 2021 == 1932

phi1 :: Integer -> Integer

phi1 n = genericLength [x | x <- [1..n], gcd x n == 1]

-- 2ª definición

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

ciclicos2 :: [Integer]

ciclicos2 = filter esCiclico2 [2..]

esCiclico2 :: Integer -> Bool

esCiclico2 n = gcd n (phi2 n) == 1

-- (phi2 n) es igual a φ(n). Por ejemplo,

-- phi2 15 == 8

-- phi2 21 == 12

-- phi2 2021 == 1932

phi2 :: Integer -> Integer

phi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]

-- (factorizacion n) es la descomposición de n en factores primos como

-- una lista de pares donde los primeros elementos son la base y los

-- segundo son los exponentes. Por ejemplo,

-- factorizacion 3000 == [(2,3),(3,1),(5,3)]

-- ya que 3000 = 2^3*3*5^3

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

factorizacion n =

[(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- 3ª definición

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

ciclicos3 :: [Integer]

ciclicos3 = filter esCiclico3 [2..]

esCiclico3 :: Integer -> Bool

esCiclico3 n = gcd n (phi3 n) == 1

-- (phi3 n) es igual a φ(n). Por ejemplo,

-- phi3 15 == 8

-- phi3 21 == 12

-- phi3 2021 == 1932

phi3 :: Integer -> Integer

phi3 n =

product [(x-1) * product xs | (x:xs) <- group (primeFactors n)]

-- Comparación de eficiencia

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

-- La comparación es

-- λ> esCiclico1 (4*10^6)

-- False

-- (3.64 secs, 4,448,223,616 bytes)

-- λ> esCiclico2 (4*10^6)

-- False

-- (0.01 secs, 116,144 bytes)

-- λ> esCiclico3 (4*10^6)

-- False

-- (0.01 secs, 111,336 bytes)

-- λ> esCiclico2 (product [1..3*10^4])

-- False

-- (2.49 secs, 5,846,361,904 bytes)

-- λ> esCiclico3 (product [1..3*10^4])

-- False

-- (2.50 secs, 5,947,164,552 bytes)

-- Verificación de la propiedad

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

-- La propiedad es

prop_ciclicos :: Int -> Property

prop_ciclicos n =

n > 1 ==> esCiclico3 (primes !! n)

-- La comprobación es

-- λ> quickCheck prop_ciclicos

-- +++ OK, passed 100 tests.

verificacion :: IO ()

verificacion = quickCheck prop_ciclicos

Nuevas soluciones

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

Números duffinianos

PorJosé A. Alonso 12-enero-202119-enero-2021

Los números duffinianos, llamados así por Richard Duffy, son los números compuestos n que son coprimos con la suma de sus divisores; es decir, n y la suma de los divisores de n no tienen ningún factor primo común.

Por ejemplo, 35 es un número duffiniano ya que la suma de sus divisores es 1 + 5 + 7 + 35 = 48 que es coprimo con 35.

Definir las funciones

   esDuffiniano :: Integer -> Bool
   duffinianos :: [Integer]

1 2	esDuffiniano :: Integer -> Bool duffinianos :: [Integer]

tales que

(esDuffiniano n) se verifica si n es duffiniano. Por ejemplo,

     esDuffiniano 35    ==  True
     esDuffiniano 2021  ==  True
     esDuffiniano 11    ==  False
     esDuffiniano 12    ==  False
     esDuffiniano (product [1..2*10^4])  ==  False

esDuffiniano 35 == True

esDuffiniano 2021 == True

esDuffiniano 11 == False

esDuffiniano 12 == False

esDuffiniano (product [1..2*10^4]) == False

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

     take 12 duffinianos  ==  [4,8,9,16,21,25,27,32,35,36,39,49]
     length (takeWhile (< 10^5) duffinianos)  ==  24434

1 2	take 12 duffinianos == [4,8,9,16,21,25,27,32,35,36,39,49] length (takeWhile (< 10^5) duffinianos) == 24434

Comprobar con QuickCheck que los números de la forma p^k, con p un primo mayor que 2 y k un entero mayor que 1, son duffinianos.

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes (isPrime, primeFactors, primes)
import Test.QuickCheck (Property, (==>), quickCheck)

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

duffinianos :: [Integer]
duffinianos = filter esDuffiniano [1..]

esDuffiniano :: Integer -> Bool
esDuffiniano n =
  n > 1 &&
  not (isPrime n) &&
  gcd n (sumaDivisores n) == 1

-- (sumaDivisores n) es la suma de los divisores de n. Por ejemplo.
--      sumaDivisores 35  ==  48
sumaDivisores :: Integer -> Integer
sumaDivisores = sum . divisores

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--      divisores 35  ==  [1,5,7,35]
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n]
                 , n `mod` x == 0]

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

duffinianos2 :: [Integer]
duffinianos2 = filter esDuffiniano2 [1..]

esDuffiniano2 :: Integer -> Bool
esDuffiniano2 n =
  n > 1 &&
  not (isPrime n) &&
  gcd n (sumaDivisores2 n) == 1

-- Si la descomposición de x en factores primos es
--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
-- entonces la suma de los divisores de x es
--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
--   ------------------- . ------------------- ... -------------------
--        p(1)-1                p(2)-1                  p(n)-1
-- Ver la demostración en http://bit.ly/2zUXZPc

-- (sumaDivisores2 n) es la suma de los divisores de n. Por ejemplo.
--      sumaDivisores2 35  ==  48
sumaDivisores2 :: Integer -> Integer
sumaDivisores2 x =
  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de la
-- descomposición prima de x. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) = (x, 1 + genericLength xs)
primeroYlongitud _      = error "No tiene elementos"

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

-- La comparación es
--    λ> esDuffiniano (product [1..11])
--    False
--    (14.09 secs, 7,983,535,608 bytes)
--    λ> esDuffiniano2 (product [1..11])
--    False
--    (0.01 secs, 125,760 bytes)
--
--    λ> head (dropWhile (<10^4) duffinianos)
--    10000
--    (13.45 secs, 8,872,967,976 bytes)
--    λ> head (dropWhile (<10^4) duffinianos2)
--    10000
--    (0.15 secs, 280,668,240 bytes)
--
--    λ> length (takeWhile (<10^4) duffinianos)
--    2370
--    (13.43 secs, 8,966,138,016 bytes)
--    λ> length (takeWhile (<10^4) duffinianos2)
--    2370
--    (0.15 secs, 286,120,048 bytes)

-- Propiedad
-- =========

-- La propiedad es
prop_duffinianos :: Int -> Int -> Property
prop_duffinianos n k =
  n >= 0 && k > 1 ==> esDuffiniano2 (p^k)
  where p = primes !! n

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

100

101

102

103

import Data.List (genericLength, group)

import Data.Numbers.Primes (isPrime, primeFactors, primes)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución

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

duffinianos :: [Integer]

duffinianos = filter esDuffiniano [1..]

esDuffiniano :: Integer -> Bool

esDuffiniano n =

n > 1 &&

not (isPrime n) &&

gcd n (sumaDivisores n) == 1

-- (sumaDivisores n) es la suma de los divisores de n. Por ejemplo.

-- sumaDivisores 35 == 48

sumaDivisores :: Integer -> Integer

sumaDivisores = sum . divisores

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 35 == [1,5,7,35]

divisores :: Integer -> [Integer]

divisores n = [x | x <- [1..n]

, n `mod` x == 0]

-- 2ª solución

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

duffinianos2 :: [Integer]

duffinianos2 = filter esDuffiniano2 [1..]

esDuffiniano2 :: Integer -> Bool

esDuffiniano2 n =

n > 1 &&

not (isPrime n) &&

gcd n (sumaDivisores2 n) == 1

-- Si la descomposición de x en factores primos es

-- x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)

-- entonces la suma de los divisores de x es

-- p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1

-- ------------------- . ------------------- ... -------------------

-- p(1)-1 p(2)-1 p(n)-1

-- Ver la demostración en http://bit.ly/2zUXZPc

-- (sumaDivisores2 n) es la suma de los divisores de n. Por ejemplo.

-- sumaDivisores2 35 == 48

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 x =

product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de la

-- descomposición prima de x. Por ejemplo,

-- factorizacion 600 == [(2,3),(3,1),(5,2)]

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

factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs

-- y la longitud de xs. Por ejemplo,

-- primeroYlongitud [3,2,5,7] == (3,4)

primeroYlongitud :: [a] -> (a,Integer)

primeroYlongitud (x:xs) = (x, 1 + genericLength xs)

primeroYlongitud _ = error "No tiene elementos"

-- Comparación de eficiencia

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

-- La comparación es

-- λ> esDuffiniano (product [1..11])

-- False

-- (14.09 secs, 7,983,535,608 bytes)

-- λ> esDuffiniano2 (product [1..11])

-- False

-- (0.01 secs, 125,760 bytes)

-- λ> head (dropWhile (<10^4) duffinianos)

-- 10000

-- (13.45 secs, 8,872,967,976 bytes)

-- λ> head (dropWhile (<10^4) duffinianos2)

-- 10000

-- (0.15 secs, 280,668,240 bytes)

-- λ> length (takeWhile (<10^4) duffinianos)

-- 2370

-- (13.43 secs, 8,966,138,016 bytes)

-- λ> length (takeWhile (<10^4) duffinianos2)

-- 2370

-- (0.15 secs, 286,120,048 bytes)

-- Propiedad

-- =========

-- La propiedad es

prop_duffinianos :: Int -> Int -> Property

prop_duffinianos n k =

n >= 0 && k > 1 ==> esDuffiniano2 (p^k)

where p = primes !! n

-- La comprobación es

-- λ> quickCheck prop_duffinianos

-- +++ OK, passed 100 tests.

Nuevas soluciones

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

Caminos reducidos

PorJosé A. Alonso 5-junio-20202-enero-2021

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

   data Direccion = N | S | E | O deriving (Show, Eq)
   type Camino = [Direccion]

1 2	data Direccion = N \| S \| E \| O deriving (Show, Eq) type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

1	reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

   reducido []                              ==  []
   reducido [N]                             ==  [N]
   reducido [N,O]                           ==  [N,O]
   reducido [N,O,E]                         ==  [N]
   reducido [N,O,E,S]                       ==  [] 
   reducido [N,O,S,E]                       ==  [N,O,S,E]
   reducido [S,S,S,N,N,N]                   ==  []
   reducido [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

reducido [] == []

reducido [N] == [N]

reducido [N,O] == [N,O]

reducido [N,O,E] == [N]

reducido [N,O,E,S] == []

reducido [N,O,S,E] == [N,O,S,E]

reducido [S,S,S,N,N,N] == []

reducido [N,S,S,E,O,N] == []

reducido [N,S,S,E,O,N,O] == [O]

reducido (take (10^7) (cycle [N,E,O,S])) == []

Nótese que en el penúltimo ejemplo las reducciones son

       [N,S,S,E,O,N,O]  
   --> [S,E,O,N,O]  
   --> [S,N,O]  
   --> [O]

[N,S,S,E,O,N,O]

--> [S,E,O,N,O]

--> [S,N,O]

--> [O]

Soluciones

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido1 ds

opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E

-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
    where aux N (S:xs) = xs
          aux S (N:xs) = xs
          aux E (O:xs) = xs
          aux O (E:xs) = xs
          aux x xs     = x:xs

-- 3ª solución 
reducido3 :: Camino -> Camino
reducido3 []       = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido3 ds

-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where 
    aux (N:xs, S:ys) = aux (xs,ys)
    aux (S:xs, N:ys) = aux (xs,ys)
    aux (E:xs, O:ys) = aux (xs,ys)
    aux (O:xs, E:ys) = aux (xs,ys)
    aux (  xs, y:ys) = aux (y:xs,ys)
    aux (  xs,   []) = xs

-- Comparación de eficiencia
--    ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (3.87 secs, 460160736 bytes)
--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (1.16 secs, 216582880 bytes)
--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.58 secs, 98561872 bytes)
--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.64 secs, 176154640 bytes)
--    
--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (5.43 secs, 962694784 bytes)
--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (9.29 secs, 1722601528 bytes)
-- 
--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (4.52 secs, 547004960 bytes)
--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    
--    ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)
--    []
--    (7.35 secs, 537797096 bytes)
--    ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)
--    []
--    (2.30 secs, 244553404 bytes)
--    ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)
--    []
--    (8.08 secs, 545043608 bytes)
--    ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)
--    []
--    (1.96 secs, 205552240 bytes)

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):

reducido1 :: Camino -> Camino

reducido1 [] = []

reducido1 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido1 ds

opuesta :: Direccion -> Direccion

opuesta N = S

opuesta S = N

opuesta E = O

opuesta O = E

-- 2ª solución (por plegado)

reducido2 :: Camino -> Camino

reducido2 = foldr aux []

where aux N (S:xs) = xs

aux S (N:xs) = xs

aux E (O:xs) = xs

aux O (E:xs) = xs

aux x xs = x:xs

-- 3ª solución

reducido3 :: Camino -> Camino

reducido3 [] = []

reducido3 (N:S:ds) = reducido3 ds

reducido3 (S:N:ds) = reducido3 ds

reducido3 (E:O:ds) = reducido3 ds

reducido3 (O:E:ds) = reducido3 ds

reducido3 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido3 ds

-- 4ª solución

reducido4 :: Camino -> Camino

reducido4 ds = reverse (aux ([],ds)) where

aux (N:xs, S:ys) = aux (xs,ys)

aux (S:xs, N:ys) = aux (xs,ys)

aux (E:xs, O:ys) = aux (xs,ys)

aux (O:xs, E:ys) = aux (xs,ys)

aux ( xs, y:ys) = aux (y:xs,ys)

aux ( xs, []) = xs

-- Comparación de eficiencia

-- ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (3.87 secs, 460160736 bytes)

-- ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (1.16 secs, 216582880 bytes)

-- ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.58 secs, 98561872 bytes)

-- ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.64 secs, 176154640 bytes)

-- ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (5.43 secs, 962694784 bytes)

-- ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (9.29 secs, 1722601528 bytes)

-- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (4.52 secs, 547004960 bytes)

-- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)

-- []

-- (7.35 secs, 537797096 bytes)

-- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)

-- []

-- (2.30 secs, 244553404 bytes)

-- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)

-- []

-- (8.08 secs, 545043608 bytes)

-- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)

-- []

-- (1.96 secs, 205552240 bytes)

Subexpresiones aritméticas

PorJosé A. Alonso 4-junio-20202-enero-2021

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

   data Expr = N Int | S Expr Expr | P Expr Expr  
     deriving (Eq, Ord, Show)

1 2	data Expr = N Int \| S Expr Expr \| P Expr Expr deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

   P (N 2) (S (N 3) (N 7))

1	P (N 2) (S (N 3) (N 7))

Definir la función

   subexpresiones :: Expr -> Set Expr

1	subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

   λ> subexpresiones (S (N 2) (N 3))
   fromList [N 2,N 3,S (N 2) (N 3)]
   λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
   fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

λ> subexpresiones (S (N 2) (N 3))

fromList [N 2,N 3,S (N 2) (N 3)]

λ> subexpresiones (P (S (N 2) (N 2)) (N 7))

fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Soluciones

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr  
  deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr
subexpresiones (N x)   = singleton (N x)
subexpresiones (S i d) =
  S i d `insert` (subexpresiones i `union` subexpresiones d)
subexpresiones (P i d) =
  P i d `insert` (subexpresiones i `union` subexpresiones d)

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr

deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr

subexpresiones (N x) = singleton (N x)

subexpresiones (S i d) =

S i d `insert` (subexpresiones i `union` subexpresiones d)

subexpresiones (P i d) =

P i d `insert` (subexpresiones i `union` subexpresiones d)

Autor: José A. Alonso

Números bigenerados

Soluciones

Nuevas soluciones

Números cíclicos

Soluciones

Nuevas soluciones

Números duffinianos

Soluciones

Nuevas soluciones

Caminos reducidos

Soluciones

Subexpresiones aritméticas

Soluciones

Entradas recientes

Buscar

Correo electrónico