Recursión – Página 12

Mínimo número de operaciones para transformar un número en otro

PorJosé A. Alonso 25-noviembre-201625-marzo-2022

Se considera el siguiente par de operaciones sobre los números:

multiplicar por dos
restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

   4 ------> 8 ------> 7
      (x2)      (-1)

1 2	4 ------> 8 ------> 7 (x2) (-1)

y el menor número de operaciones para transformar 2 en 5 es 4

   2 ------> 4 ------> 3 ------> 6 ------> 5
      (x2)      (-1)      (x2)      (-1)

1 2	2 ------> 4 ------> 3 ------> 6 ------> 5 (x2) (-1) (x2) (-1)

Definir las siguientes funciones

   arbolOp :: Int -> Int -> Arbol
   minNOp  :: Int -> Int -> Int

1 2	arbolOp :: Int -> Int -> Arbol minNOp :: Int -> Int -> Int

tales que

(arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

    λ> arbolOp 4 1
    N 4 (H 8) (H 3)
    λ> arbolOp 4 2
    N 4 (N 8 (H 16) (H 7))
        (N 3 (H 6) (H 2))
    λ> arbolOp 2 3
    N 2 (N 4
           (N 8 (H 16) (H 7))
           (N 3 (H 6) (H 2)))
        (N 1
           (N 2 (H 4) (H 1))
           (H 0))
    λ> arbolOp 2 4
    N 2 (N 4 (N 8
                (N 16 (H 32) (H 15))
                (N 7 (H 14) (H 6)))
             (N 3
                (N 6 (H 12) (H 5))
                (N 2 (H 4) (H 1))))
        (N 1 (N 2
                (N 4 (H 8) (H 3))
                (N 1 (H 2) (H 0)))
             (H 0))

λ> arbolOp 4 1

N 4 (H 8) (H 3)

λ> arbolOp 4 2

N 4 (N 8 (H 16) (H 7))

(N 3 (H 6) (H 2))

λ> arbolOp 2 3

N 2 (N 4

(N 8 (H 16) (H 7))

(N 3 (H 6) (H 2)))

(N 1

(N 2 (H 4) (H 1))

(H 0))

λ> arbolOp 2 4

N 2 (N 4 (N 8

(N 16 (H 32) (H 15))

(N 7 (H 14) (H 6)))

(N 3

(N 6 (H 12) (H 5))

(N 2 (H 4) (H 1))))

(N 1 (N 2

(N 4 (H 8) (H 3))

(N 1 (H 2) (H 0)))

(H 0))

(minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

     minNOp 4 7  ==  2
     minNOp 2 5  ==  4

1 2	minNOp 4 7 == 2 minNOp 2 5 == 4

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol
           deriving Show

arbolOp :: Int -> Int -> Arbol
arbolOp 0 _ = H 0
arbolOp x 0 = H x
arbolOp x n = N x (arbolOp (2 * x) (n - 1)) (arbolOp (x - 1) (n - 1))

ocurre :: Int -> Arbol -> Bool
ocurre x (H y)     = x == y
ocurre x (N y i d) = x == y || ocurre x i || ocurre x d

minNOp :: Int -> Int -> Int
minNOp x y =
  head [n | n <- [0..]
          , ocurre y (arbolOp x n)]

data Arbol = H Int

| N Int Arbol Arbol

deriving Show

arbolOp :: Int -> Int -> Arbol

arbolOp 0 _ = H 0

arbolOp x 0 = H x

arbolOp x n = N x (arbolOp (2 * x) (n - 1)) (arbolOp (x - 1) (n - 1))

ocurre :: Int -> Arbol -> Bool

ocurre x (H y) = x == y

ocurre x (N y i d) = x == y || ocurre x i || ocurre x d

minNOp :: Int -> Int -> Int

minNOp x y =

head [n | n <- [0..]

, ocurre y (arbolOp x n)]

Referencias

Basado en el artículo Minimum number of operation required to
convert number x into y de Vipin Khushu en
GeeksforGeeks.

Máxima ramificación

PorJosé A. Alonso 23-noviembre-201630-noviembre-2016

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
                  deriving Show

1 2	data Arbol a = N a [Arbol a] deriving Show

Por ejemplo, los árboles

     1         1             1          
    / \       / \           / \   
   2   3     2   3         2   3  
       |        /|\       /|\  |   
       4       4 5 6     4 5 6 7

1 1 1

/ \ / \ / \

2 3 2 3 2 3

| /|\ /|\ |

4 4 5 6 4 5 6 7

se representan por

   ej1, ej2, ej3 :: Arbol Int
   ej1 = N 1 [N 2 [],N 3 [N 4 []]]
   ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]
   ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

ej1, ej2, ej3 :: Arbol Int

ej1 = N 1 [N 2 [],N 3 [N 4 []]]

ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]

ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

En el primer ejemplo la máxima ramificación es 2 (en el nodo 1 que tiene 2 hijos), la del segundo es 3 (en el nodo 3 que tiene 3 hijos) y la del tercero es 3 (en el nodo 3 que tiene 3 hijos).

Definir la función

   maximaRamificacion :: Arbol a -> Int

1	maximaRamificacion :: Arbol a -> Int

tal que (maximaRamificacion a) es la máxima ramificación del árbol a. Por ejemplo,

   maximaRamificacion ej1  ==  2
   maximaRamificacion ej2  ==  3
   maximaRamificacion ej3  ==  3

maximaRamificacion ej1 == 2

maximaRamificacion ej2 == 3

maximaRamificacion ej3 == 3

Soluciones

data Arbol a = N a [Arbol a]
  deriving Show

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]]
ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]] 

maximaRamificacion :: Arbol a -> Int
maximaRamificacion (N _ []) = 0
maximaRamificacion (N x xs) =
  max (length xs) (maximum (map maximaRamificacion xs))

data Arbol a = N a [Arbol a]

deriving Show

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [],N 3 [N 4 []]]

ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]]

ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

maximaRamificacion :: Arbol a -> Int

maximaRamificacion (N _ []) = 0

maximaRamificacion (N x xs) =

max (length xs) (maximum (map maximaRamificacion xs))

Conmutaciones ondulantes

PorJosé A. Alonso 21-noviembre-201628-noviembre-2016

Una lista binaria es ondulante si sus elementos son alternativamente 0 y 1. Por ejemplo, las listas [0,1,0,1,0] y [1,0,1,0] son ondulantes.

Definir la función

   minConmutacionesOndulante :: [Int] -> Int

1	minConmutacionesOndulante :: [Int] -> Int

tal que (minConmutacionesOndulante xs) es el mínimo número de conmutaciones (es decir, cambios de 0 a 1 o de 1 a 0) necesarias para transformar xs en una lista ondulante. Por ejemplo,

   minConmutacionesOndulante [1,1,1]                ==  1
   minConmutacionesOndulante [0,0,0,1,0,1,0,1,1,1]  ==  2

1 2	minConmutacionesOndulante [1,1,1] == 1 minConmutacionesOndulante [0,0,0,1,0,1,0,1,1,1] == 2

En el primer ejemplo basta conmutar el elemento en la posición 1 para obtener [1,0,1] y el segundo ejemplo los elementos en las posiciones 1 y 8 para obtener [0,1,0,1,0,1,0,1,0,1].

Soluciones

minConmutacionesOndulante :: [Int] -> Int
minConmutacionesOndulante xs =
  min (diferencia xs ondulante0)
      (diferencia xs ondulante1)

-- (diferencia xs ys) es el número de posiciones con elementos
-- distintos. Por ejemplo,
--    diferencia [1,1,1] [1,0,1]            ==  1
--    diferencia "0001010111" "0101010101"  ==  2
diferencia :: Eq a => [a] -> [a] -> Int
diferencia xs ys =
  sum [1 | (x,y) <- zip xs ys, x /= y]

-- ondulante0 es la lista binaria ondulante cuyo primer elemento es
-- 0. Por ejemplo,
--    take 10 ondulante0  ==  [0,1,0,1,0,1,0,1,0,1]
ondulante0 :: [Int]
ondulante0 = 0 : ondulante1

-- ondulante1 es la lista binaria ondulante cuyo primer elemento es
-- 1. Por ejemplo,
--    take 10 ondulante1  ==  [1,0,1,0,1,0,1,0,1,0]
ondulante1 :: [Int]
ondulante1 = 1 : ondulante0

minConmutacionesOndulante :: [Int] -> Int

minConmutacionesOndulante xs =

min (diferencia xs ondulante0)

(diferencia xs ondulante1)

-- (diferencia xs ys) es el número de posiciones con elementos

-- distintos. Por ejemplo,

-- diferencia [1,1,1] [1,0,1] == 1

-- diferencia "0001010111" "0101010101" == 2

diferencia :: Eq a => [a] -> [a] -> Int

diferencia xs ys =

sum [1 | (x,y) <- zip xs ys, x /= y]

-- ondulante0 es la lista binaria ondulante cuyo primer elemento es

-- 0. Por ejemplo,

-- take 10 ondulante0 == [0,1,0,1,0,1,0,1,0,1]

ondulante0 :: [Int]

ondulante0 = 0 : ondulante1

-- ondulante1 es la lista binaria ondulante cuyo primer elemento es

-- 1. Por ejemplo,

-- take 10 ondulante1 == [1,0,1,0,1,0,1,0,1,0]

ondulante1 :: [Int]

ondulante1 = 1 : ondulante0

Máximo producto en la partición de un número

PorJosé A. Alonso 16-noviembre-201623-noviembre-2016

El artículo de esta semana de Antonio Roldán en su blog Números y hoja de cálculo es Máximo producto en la partición de un número (1)

Una partición de un entero positivo n es una forma de descomponer n como suma de enteros positivos. Dos sumas se considerarán iguales si solo difieren en el orden de los sumandos. Por ejemplo, las 11 particiones de 6 (con sus correspondientes productos) son

   6 = 6                      |  6                     = 6
   6 = 5 + 1                  |  5 x 1                 = 5
   6 = 4 + 2                  |  4 x 2                 = 8
   6 = 4 + 1 + 1              |  4 x 1 x 1             = 4
   6 = 3 + 3                  |  3 x 3                 = 9
   6 = 3 + 2 + 1              |  3 x 2 x 1             = 6
   6 = 3 + 1 + 1 + 1          |  3 x 1 x 1 x 1         = 3
   6 = 2 + 2 + 2              |  2 x 2 x 2             = 8
   6 = 2 + 2 + 1 + 1          |  2 x 2 x 1 x 1         = 4
   6 = 2 + 1 + 1 + 1 + 1      |  2 x 1 x 1 x 1 x 1     = 2
   6 = 1 + 1 + 1 + 1 + 1 + 1  |  1 x 1 x 1 x 1 x 1 x 1 = 1

6 = 6 | 6 = 6

6 = 5 + 1 | 5 x 1 = 5

6 = 4 + 2 | 4 x 2 = 8

6 = 4 + 1 + 1 | 4 x 1 x 1 = 4

6 = 3 + 3 | 3 x 3 = 9

6 = 3 + 2 + 1 | 3 x 2 x 1 = 6

6 = 3 + 1 + 1 + 1 | 3 x 1 x 1 x 1 = 3

6 = 2 + 2 + 2 | 2 x 2 x 2 = 8

6 = 2 + 2 + 1 + 1 | 2 x 2 x 1 x 1 = 4

6 = 2 + 1 + 1 + 1 + 1 | 2 x 1 x 1 x 1 x 1 = 2

6 = 1 + 1 + 1 + 1 + 1 + 1 | 1 x 1 x 1 x 1 x 1 x 1 = 1

Se observa que el máximo producto de las particiones de 6 es 9.

Definir la función

   maximoProductoParticiones :: Int -> Int

1	maximoProductoParticiones :: Int -> Int

tal que (maximoProductoParticiones n) es el máximo de los productos de las particiones de n. Por ejemplo,

   maximoProductoParticiones 4     ==  4
   maximoProductoParticiones 5     ==  6
   maximoProductoParticiones 6     ==  9
   maximoProductoParticiones 7     ==  12
   maximoProductoParticiones 8     ==  18
   maximoProductoParticiones 9     ==  27
   maximoProductoParticiones 50    ==  86093442
   maximoProductoParticiones 100   ==  7412080755407364
   maximoProductoParticiones 200   ==  61806308765265224723841283607058
   length (show (maximoProductoParticiones (10^7)))  ==  1590405

maximoProductoParticiones 4 == 4

maximoProductoParticiones 5 == 6

maximoProductoParticiones 6 == 9

maximoProductoParticiones 7 == 12

maximoProductoParticiones 8 == 18

maximoProductoParticiones 9 == 27

maximoProductoParticiones 50 == 86093442

maximoProductoParticiones 100 == 7412080755407364

maximoProductoParticiones 200 == 61806308765265224723841283607058

length (show (maximoProductoParticiones (10^7))) == 1590405

Comprobar con QuickChek que los únicos posibles factores de (maximoProductoParticiones n) son 2 y 3.

Soluciones

import Data.List (genericIndex, sort)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck

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

maximoProductoParticiones1 :: Integer -> Integer
maximoProductoParticiones1 n =
  maximum [product xs | xs <- particiones1 n]

-- (particiones1 n) es la lista de las particiones de n. Por ejemplo,  
--    λ> particiones1 4
--    [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
--    λ> particiones1 5
--    [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
particiones1 :: Integer -> [[Integer]]
particiones1 0 = [[]]
particiones1 n = [x:y | x <- [n,n-1..1]
                      , y <- particiones1 (n-x) 
                      , [x] >= take 1 y]
 
-- 2ª definición
-- =============

maximoProductoParticiones2 :: Integer -> Integer
maximoProductoParticiones2 n =
  maximum [product xs | xs <- particiones2 n]

-- (particiones2 n) es la lista de las particiones de n. Por ejemplo,  
--    λ> particiones2 4
--    [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
--    λ> particiones2 5
--    [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
particiones2 :: Integer -> [[Integer]]
particiones2 n = aux `genericIndex` n
  where aux = [] : map particiones [1..]
          where particiones n = [n] : [x:p | x <- [n,n-1..1]
                                           , p <- aux `genericIndex` (n-x) 
                                           , x >= head p]

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

maximoProductoParticiones3 :: Integer -> Integer
maximoProductoParticiones3 0 = 1
maximoProductoParticiones3 n =
  maximum [(n-i) * maximoProductoParticiones3 i | i <- [0..n-1]]

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

maximoProductoParticiones4 :: Integer -> Integer
maximoProductoParticiones4 n =
  maximosProductosParticiones `genericIndex` n

maximosProductosParticiones :: [Integer]
maximosProductosParticiones = 1 : f [1]
  where f xs = y : f (y:xs)
          where y = maximum (zipWith (*) [1..] xs)

-- 5ª definición
-- =============

maximoProductoParticiones5 :: Integer -> Integer
maximoProductoParticiones5 1 = 1
maximoProductoParticiones5 n
  | r == 0 = 3^q
  | r == 1 = 4 * 3^(q-1)
  | r == 2 = 2 * 3 ^q
  where (q,r) = quotRem n 3
        
-- Comparación de eficiencia                                        
-- =========================

-- La comparación es
--    λ> maximoProductoParticiones1 20
--    1458
--    (5.42 secs, 832,283,184 bytes)
--    λ> maximoProductoParticiones2 20
--    1458
--    (0.02 secs, 0 bytes)
--    λ> maximoProductoParticiones3 20
--    1458
--    (3.18 secs, 524,500,000 bytes)
--    λ> maximoProductoParticiones4 20
--    1458
--    (0.00 secs, 0 bytes)
--    
--    λ> maximoProductoParticiones2 50
--    86093442
--    (9.18 secs, 980,524,320 bytes)
--    λ> maximoProductoParticiones4 50
--    86093442
--    (0.01 secs, 1,381,192 bytes)
--    λ> maximoProductoParticiones5 50
--    86093442
--    (0.00 secs, 0 bytes)
--    
--    λ> length (show (maximoProductoParticiones4 2000))
--    319
--    (2.93 secs, 638,270,872 bytes)
--    λ> length (show (maximoProductoParticiones5 2000))
--    319
--    (0.01 secs, 0 bytes)

-- Comprobación
-- ============

-- La propiedad es
prop_factores :: Integer -> Property
prop_factores n =
  n > 0 ==> primeFactors (maximoProductoParticiones5 n) `contenido` [2,3]

contenido :: Eq a => [a] -> [a] -> Bool
contenido xs ys = all (`elem` ys) xs

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

import Data.List (genericIndex, sort)

import Data.Numbers.Primes (primeFactors)

import Test.QuickCheck

-- 1ª definición

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

maximoProductoParticiones1 :: Integer -> Integer

maximoProductoParticiones1 n =

maximum [product xs | xs <- particiones1 n]

-- (particiones1 n) es la lista de las particiones de n. Por ejemplo,

-- λ> particiones1 4

-- [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]

-- λ> particiones1 5

-- [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]

particiones1 :: Integer -> [[Integer]]

particiones1 0 = [[]]

particiones1 n = [x:y | x <- [n,n-1..1]

, y <- particiones1 (n-x)

, [x] >= take 1 y]

-- 2ª definición

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

maximoProductoParticiones2 :: Integer -> Integer

maximoProductoParticiones2 n =

maximum [product xs | xs <- particiones2 n]

-- (particiones2 n) es la lista de las particiones de n. Por ejemplo,

-- λ> particiones2 4

-- [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]

-- λ> particiones2 5

-- [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]

particiones2 :: Integer -> [[Integer]]

particiones2 n = aux `genericIndex` n

where aux = [] : map particiones [1..]

where particiones n = [n] : [x:p | x <- [n,n-1..1]

, p <- aux `genericIndex` (n-x)

, x >= head p]

-- 3ª definición

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

maximoProductoParticiones3 :: Integer -> Integer

maximoProductoParticiones3 0 = 1

maximoProductoParticiones3 n =

maximum [(n-i) * maximoProductoParticiones3 i | i <- [0..n-1]]

-- 4ª definición

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

maximoProductoParticiones4 :: Integer -> Integer

maximoProductoParticiones4 n =

maximosProductosParticiones `genericIndex` n

maximosProductosParticiones :: [Integer]

maximosProductosParticiones = 1 : f [1]

where f xs = y : f (y:xs)

where y = maximum (zipWith (*) [1..] xs)

-- 5ª definición

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

maximoProductoParticiones5 :: Integer -> Integer

maximoProductoParticiones5 1 = 1

maximoProductoParticiones5 n

| r == 0 = 3^q

| r == 1 = 4 * 3^(q-1)

| r == 2 = 2 * 3 ^q

where (q,r) = quotRem n 3

-- Comparación de eficiencia

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

-- La comparación es

-- λ> maximoProductoParticiones1 20

-- 1458

-- (5.42 secs, 832,283,184 bytes)

-- λ> maximoProductoParticiones2 20

-- 1458

-- (0.02 secs, 0 bytes)

-- λ> maximoProductoParticiones3 20

-- 1458

-- (3.18 secs, 524,500,000 bytes)

-- λ> maximoProductoParticiones4 20

-- 1458

-- (0.00 secs, 0 bytes)

-- λ> maximoProductoParticiones2 50

-- 86093442

-- (9.18 secs, 980,524,320 bytes)

-- λ> maximoProductoParticiones4 50

-- 86093442

-- (0.01 secs, 1,381,192 bytes)

-- λ> maximoProductoParticiones5 50

-- 86093442

-- (0.00 secs, 0 bytes)

-- λ> length (show (maximoProductoParticiones4 2000))

-- 319

-- (2.93 secs, 638,270,872 bytes)

-- λ> length (show (maximoProductoParticiones5 2000))

-- 319

-- (0.01 secs, 0 bytes)

-- Comprobación

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

-- La propiedad es

prop_factores :: Integer -> Property

prop_factores n =

n > 0 ==> primeFactors (maximoProductoParticiones5 n) `contenido` [2,3]

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

contenido xs ys = all (`elem` ys) xs

-- La comprobación es

-- λ> quickCheck prop_factores

-- +++ OK, passed 100 tests.

Referencia

Máximo producto en la partición de un número (1) de Antonio Roldán en el blog Números y hoja de cálculo.
Sucesión A000792 de la OEIS.

Persistencia multiplicativa de un número

PorJosé A. Alonso 14-noviembre-201621-noviembre-2016

La persistencia multiplicativa de un número es la cantidad de pasos requeridos para reducirlo a una cifra multiplicando sus dígitos. Por ejemplo, la persistencia de 39 es 3 porque 3×9 = 27, 2×7 = 14 y 1×4 = 4.

Definir las funciones

   persistencia     :: Integer -> Integer
   menorPersistente :: Integer -> Integer

1 2	persistencia :: Integer -> Integer menorPersistente :: Integer -> Integer

tales que

(persistencia x) es la persistencia de x. Por ejemplo,

     persistencia 39                             ==   3
     persistencia 2677889                        ==   8
     persistencia 26888999                       ==   9
     persistencia 3778888999                     ==  10
     persistencia 277777788888899                ==  11
     persistencia 77777733332222222222222222222  ==  11

persistencia 39 == 3

persistencia 2677889 == 8

persistencia 26888999 == 9

persistencia 3778888999 == 10

persistencia 277777788888899 == 11

persistencia 77777733332222222222222222222 == 11

(menorPersistente n) es el menor número con persistencia n. Por ejemplo,

     menorPersistente 0  ==  1
     menorPersistente 1  ==  10
     menorPersistente 2  ==  25
     menorPersistente 3  ==  39
     menorPersistente 4  ==  77
     menorPersistente 5  ==  679
     menorPersistente 6  ==  6788
     menorPersistente 7  ==  68889

menorPersistente 0 == 1

menorPersistente 1 == 10

menorPersistente 2 == 25

menorPersistente 3 == 39

menorPersistente 4 == 77

menorPersistente 5 == 679

menorPersistente 6 == 6788

menorPersistente 7 == 68889

Comprobar con QuickCheck si todos los números menores que 10^233 tienen una persistencia multiplicativa menor o igual que 11.

Nota: Este ejercicio ha sido propuesto por Marcos Giráldez.

Soluciones

import Test.QuickCheck

persistencia :: Integer -> Integer
persistencia x
  | x < 10    = 0
  | otherwise = 1 + persistencia (productoDigitos x)

productoDigitos :: Integer -> Integer
productoDigitos x 
  | x < 10    = x
  | otherwise = r * productoDigitos y
  where (y,r) = quotRem x 10

menorPersistente :: Integer -> Integer
menorPersistente n =
  head [x | x <- [1..]
          , persistencia x == n]

-- La propiedad es
prop_persistencia :: Integer -> Property
prop_persistencia x =
  x <= y ==> persistencia x <= 11
  where y = 10^233

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

import Test.QuickCheck

persistencia :: Integer -> Integer

persistencia x

| x < 10 = 0

| otherwise = 1 + persistencia (productoDigitos x)

productoDigitos :: Integer -> Integer

productoDigitos x

| x < 10 = x

| otherwise = r * productoDigitos y

where (y,r) = quotRem x 10

menorPersistente :: Integer -> Integer

menorPersistente n =

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

, persistencia x == n]

-- La propiedad es

prop_persistencia :: Integer -> Property

prop_persistencia x =

x <= y ==> persistencia x <= 11

where y = 10^233

-- La comprobación es

-- λ> quickCheck prop_persistencia

-- +++ OK, passed 100 tests.

Referencias

Persistencia multiplicativa y el número 77777733332222222222222222222 por M. Macho
Multiplicative persistence por Eric W. Weisstein en MathWorld.
Sucesión A003001 de la OEIS.

Subconjuntos acotados

PorJosé A. Alonso 10-noviembre-201617-noviembre-2016

Definir la función

   subconjuntosAcotados :: [a] -> Int -> [[a]]

1	subconjuntosAcotados :: [a] -> Int -> [[a]]

tal que (subconjuntosAcotados xs k) es la lista de los subconjuntos de xs con k elementos como máximo. Por ejemplo,

   λ> subconjuntosAcotados "abcd" 1
   ["a","b","c","d",""]
   λ> subconjuntosAcotados "abcd" 2
   ["ab","ac","ad","a","bc","bd","b","cd","c","d",""]
   λ> subconjuntosAcotados "abcd" 3
   ["abc","abd","ab","acd","ac","ad","a",
    "bcd","bc","bd","b","cd","c","d",""]
   λ> length (subconjuntosAcotados [1..1000] 2)
   500501
   λ> length (subconjuntosAcotados2 [1..2000] 2)
   2001001

λ> subconjuntosAcotados "abcd" 1

["a","b","c","d",""]

λ> subconjuntosAcotados "abcd" 2

["ab","ac","ad","a","bc","bd","b","cd","c","d",""]

λ> subconjuntosAcotados "abcd" 3

["abc","abd","ab","acd","ac","ad","a",

"bcd","bc","bd","b","cd","c","d",""]

λ> length (subconjuntosAcotados [1..1000] 2)

500501

λ> length (subconjuntosAcotados2 [1..2000] 2)

2001001

Soluciones

import Data.List (subsequences)

-- 1ª definición
subconjuntosAcotados1 :: [a] -> Int -> [[a]]
subconjuntosAcotados1 xs k =
  [ys | ys <- subsequences xs
      , length ys <= k]

-- 2ª definición
subconjuntosAcotados2 :: [a] -> Int -> [[a]]
subconjuntosAcotados2 _ 0  = [[]]
subconjuntosAcotados2 [] _ = [[]]
subconjuntosAcotados2 (x:xs) k =
  [x:ys | ys <- subconjuntosAcotados2 xs (k-1)]
  ++ subconjuntosAcotados2 xs k

-- Comparación de eficiencia
--    λ> length (subconjuntosAcotados1 [1..25] 2)
--    326
--    (10.48 secs, 6,968,637,480 bytes)
--    λ> length (subconjuntosAcotados2 [1..25] 2)
--    326
--    (0.00 secs, 0 bytes)

import Data.List (subsequences)

-- 1ª definición

subconjuntosAcotados1 :: [a] -> Int -> [[a]]

subconjuntosAcotados1 xs k =

[ys | ys <- subsequences xs

, length ys <= k]

-- 2ª definición

subconjuntosAcotados2 :: [a] -> Int -> [[a]]

subconjuntosAcotados2 _ 0 = [[]]

subconjuntosAcotados2 [] _ = [[]]

subconjuntosAcotados2 (x:xs) k =

[x:ys | ys <- subconjuntosAcotados2 xs (k-1)]

++ subconjuntosAcotados2 xs k

-- Comparación de eficiencia

-- λ> length (subconjuntosAcotados1 [1..25] 2)

-- 326

-- (10.48 secs, 6,968,637,480 bytes)

-- λ> length (subconjuntosAcotados2 [1..25] 2)

-- 326

-- (0.00 secs, 0 bytes)

Números de Harshad hereditarios

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

Un número de Harshad es un entero divisible entre la suma de sus dígitos. Por ejemplo, 201 es un número de Harshad porque es divisible por 3 (la suma de sus dígitos). Cuando se elimina el último dígito de 201 se obtiene 20 que también es un número de Harshad. Cuando se elimina el último dígito de 20 se obtiene 2 que también es un número de Harshad. Los números como el 201 que son de Harshad y que los números obtenidos eliminando sus últimos dígitos siguen siendo de Harshad se llaman números de Harshad hereditarios por la derecha. Definir la función

   numeroHHD :: Int -> Bool

1	numeroHHD :: Int -> Bool

tal que (numeroHHD n) se verifica si n es un número de Harshad hereditario por la derecha. Por ejemplo,

   numeroHHD 201  ==  True
   numeroHHD 140  ==  False
   numeroHHD 1104 ==  False

numeroHHD 201 == True

numeroHHD 140 == False

numeroHHD 1104 == False

Calcular el mayor número de Harshad hereditario por la derecha con tres dígitos.

Soluciones

-- (numeroH n) se verifica si n es un número de Harshad.
--    numeroH 201  ==  True
numeroH :: Int -> Bool
numeroH n = rem n (sum (digitos n)) == 0

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

numeroHHD :: Int -> Bool 
numeroHHD n | n < 10    = True
            | otherwise = numeroH n && numeroHHD (div n 10) 

-- El cálculo es
--    ghci> head [n | n <- [999,998..100], numeroHHD n]
--    902

-- (numeroH n) se verifica si n es un número de Harshad.

-- numeroH 201 == True

numeroH :: Int -> Bool

numeroH n = rem n (sum (digitos n)) == 0

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

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

digitos :: Int -> [Int]

digitos n = [read [d] | d <- show n]

numeroHHD :: Int -> Bool

numeroHHD n | n < 10 = True

| otherwise = numeroH n && numeroHHD (div n 10)

-- El cálculo es

-- ghci> head [n | n <- [999,998..100], numeroHHD n]

-- 902

Caminos en una retícula

PorJosé A. Alonso 26-mayo-20162-junio-2016

El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.

Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.

Para representar los caminos se definen los siguientes tipos de datos:

    data Direccion = D | A deriving (Show, Eq)
    type Camino = [Direccion]

1 2	data Direccion = D \| A deriving (Show, Eq) type Camino = [Direccion]

Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].

Definir las funciones

   caminos  :: Int -> Int -> [Camino]
   nCaminos :: Int -> Int -> Integer

1 2	caminos :: Int -> Int -> [Camino] nCaminos :: Int -> Int -> Integer

tales que

(caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     λ> caminos 2 2
     [[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]
     λ> caminos 1 3
     [[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]
     λ> caminos 2 3
     [[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],
      [D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

λ> caminos 2 2

[[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]

λ> caminos 1 3

[[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]

λ> caminos 2 3

[[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],

[D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

(nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     nCaminos 2 2  ==  6
     nCaminos 1 3  ==  4
     nCaminos 2 3  ==  10
     length (show (nCaminos 20000 30000))  ==  14612
     length (show (nCaminos 30000 20000))  ==  14612

nCaminos 2 2 == 6

nCaminos 1 3 == 4

nCaminos 2 3 == 10

length (show (nCaminos 20000 30000)) == 14612

length (show (nCaminos 30000 20000)) == 14612

Soluciones

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos
-- =====================

caminos :: Int -> Int -> [Camino]
caminos 0 n = [replicate n A]
caminos m 0 = [replicate m D]
caminos m n = [A:xs | xs <- caminos m (n-1)] ++
              [D:xs | xs <- caminos (m-1) n]

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

nCaminos1 :: Int -> Int -> Integer
nCaminos1 m n = genericLength (caminos m n)

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

nCaminos2 :: Int -> Int -> Integer
nCaminos2 0 n = 1
nCaminos2 m 0 = 1
nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

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

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición
-- de m veces la D y n veces la A. Por tanto, su número es
--    (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer
nCaminos3 m n = 
    fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer
fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos
-- =======================

nCaminos4 :: Int -> Int -> Integer
nCaminos4 m n = 
    product [a+1..a+b] `div` product [2..b]
    where m' = fromIntegral m
          n' = fromIntegral n
          a  = max m' n'
          b  = min m' n'

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

--    λ> nCaminos1 10 10
--    184756
--    (3.50 secs, 656,909,648 bytes)
--    λ> nCaminos2 10 10
--    184756
--    (0.50 secs, 47,330,272 bytes)
--    λ> nCaminos3 10 10
--    184756
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 10
--    184756
--    (0.01 secs, 0 bytes)
-- 
--    λ> nCaminos2 10 15
--    3268760
--    (8.83 secs, 1,142,623,080 bytes)
--    λ> nCaminos3 10 15
--    3268760
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 15
--    3268760
--    (0.00 secs, 0 bytes)
--
--    λ> let n = 2*10^4 
--    (0.01 secs, 0 bytes)
--    λ> length (show (nCaminos3 n n))
--    12039
--    (8.41 secs, 2,369,767,480 bytes)
--    λ> length (show (nCaminos4 n n))
--    12039
--    (2.98 secs, 833,386,648 bytes)

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos

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

caminos :: Int -> Int -> [Camino]

caminos 0 n = [replicate n A]

caminos m 0 = [replicate m D]

caminos m n = [A:xs | xs <- caminos m (n-1)] ++

[D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos

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

nCaminos1 :: Int -> Int -> Integer

nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos

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

nCaminos2 :: Int -> Int -> Integer

nCaminos2 0 n = 1

nCaminos2 m 0 = 1

nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos

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

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición

-- de m veces la D y n veces la A. Por tanto, su número es

-- (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer

nCaminos3 m n =

fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer

fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos

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

nCaminos4 :: Int -> Int -> Integer

nCaminos4 m n =

product [a+1..a+b] `div` product [2..b]

where m' = fromIntegral m

n' = fromIntegral n

a = max m' n'

b = min m' n'

-- Comparación de eficiencia

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

-- λ> nCaminos1 10 10

-- 184756

-- (3.50 secs, 656,909,648 bytes)

-- λ> nCaminos2 10 10

-- 184756

-- (0.50 secs, 47,330,272 bytes)

-- λ> nCaminos3 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos2 10 15

-- 3268760

-- (8.83 secs, 1,142,623,080 bytes)

-- λ> nCaminos3 10 15

-- 3268760

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 15

-- 3268760

-- (0.00 secs, 0 bytes)

-- λ> let n = 2*10^4

-- (0.01 secs, 0 bytes)

-- λ> length (show (nCaminos3 n n))

-- 12039

-- (8.41 secs, 2,369,767,480 bytes)

-- λ> length (show (nCaminos4 n n))

-- 12039

-- (2.98 secs, 833,386,648 bytes)

Centro de gravedad de una lista

PorJosé A. Alonso 25-mayo-201626-marzo-2022

Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.

Definir la función

   centro :: (Num a, Eq a) => [a] -> Maybe Int

1	centro :: (Num a, Eq a) => [a] -> Maybe Int

tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,

   centro [1,3,4,5,-2,1]           ==  Just 2
   centro [1,6,4,5,-2,1]           ==  Nothing
   centro [1,2,3,4,3,2,1]          ==  Just 3
   centro [1,100,50,-51,1,1]       ==  Just 1
   centro [1,2,3,4,5,6]            ==  Nothing
   centro [20,10,30,10,10,15,35]   ==  Just 3
   centro [20,10,-80,10,10,15,35]  ==  Just 0
   centro [10,-80,10,10,15,35,20]  ==  Just 6
   centro [0,0,0,0,0]              ==  Just 0
   centro [-1,-2,-3,-4,-3,-2,-1]   ==  Just 3

centro [1,3,4,5,-2,1] == Just 2

centro [1,6,4,5,-2,1] == Nothing

centro [1,2,3,4,3,2,1] == Just 3

centro [1,100,50,-51,1,1] == Just 1

centro [1,2,3,4,5,6] == Nothing

centro [20,10,30,10,10,15,35] == Just 3

centro [20,10,-80,10,10,15,35] == Just 0

centro [10,-80,10,10,15,35,20] == Just 6

centro [0,0,0,0,0] == Just 0

centro [-1,-2,-3,-4,-3,-2,-1] == Just 3

Soluciones

import Data.List (inits, tails)
import Data.Maybe (listToMaybe)

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

centro1 :: (Num a, Eq a) => [a] -> Maybe Int
centro1 xs 
    | null ns   = Nothing
    | otherwise = Just (head ns)
    where ns = [n | n <- [0..length xs - 1],
                    let (ys,_:zs) = splitAt n xs,
                    sum ys == sum zs]

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

centro2 :: (Num a, Eq a) => [a] -> Maybe Int
centro2 xs = aux 0 0 (sum xs) xs where
    aux _ _ _ [] = Nothing
    aux k i d (z:zs) | i == d - z = Just k
                     | otherwise  = aux (k + 1) (i + z) (d - z) zs

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

centro3 :: (Num a, Eq a) => [a] -> Maybe Int
centro3 xs =
  listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
                  , sum ys == sum zs]

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

--    λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))
--    Just 3000
--    (2.70 secs, 2,088,881,728 bytes)
--    λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))
--    Just 3000
--    (0.03 secs, 0 bytes)
--    λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))
--    Just 3000
--    (2.34 secs, 1,727,569,688 bytes)

import Data.List (inits, tails)

import Data.Maybe (listToMaybe)

-- 1ª solución

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

centro1 :: (Num a, Eq a) => [a] -> Maybe Int

centro1 xs

| null ns = Nothing

| otherwise = Just (head ns)

where ns = [n | n <- [0..length xs - 1],

let (ys,_:zs) = splitAt n xs,

sum ys == sum zs]

-- 2ª solución

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

centro2 :: (Num a, Eq a) => [a] -> Maybe Int

centro2 xs = aux 0 0 (sum xs) xs where

aux _ _ _ [] = Nothing

aux k i d (z:zs) | i == d - z = Just k

| otherwise = aux (k + 1) (i + z) (d - z) zs

-- 3ª solución

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

centro3 :: (Num a, Eq a) => [a] -> Maybe Int

centro3 xs =

listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)

, sum ys == sum zs]

-- Comparación de eficiencia

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

-- λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))

-- Just 3000

-- (2.70 secs, 2,088,881,728 bytes)

-- λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))

-- Just 3000

-- (0.03 secs, 0 bytes)

-- λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))

-- Just 3000

-- (2.34 secs, 1,727,569,688 bytes)

Sucesiones de listas de números

PorJosé A. Alonso 20-mayo-201626-marzo-2022

En la Olimpiada Internacional de Matemáticas del 2012 se propuso el siguiente problema:

Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos números adyacentes x e y tales que x > y y x está a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que sólo puede aplicar un número finito de dichas iteraciones.

Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformación).

Definir las funciones

   soluciones       :: [Int] -> [Estado]
   finales          :: [Int] -> [[Int]]
   finalesMaximales :: [Int] -> (Int,[[Int]])

soluciones :: [Int] -> [Estado]

finales :: [Int] -> [[Int]]

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

tales que

(soluciones xs) es la lista de pares (n,ys) tales que ys es una lista obtenida aplicándole n transformaciones a xs. Por ejemplo,

     λ> soluciones [1,3,2]
     [(1,[1,3,3]),(1,[1,2,3])]
     λ> sort (nub (soluciones [3,3,2]))
     [(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]
     λ> sort (nub (soluciones [3,2,1]))
     [(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]

λ> soluciones [1,3,2]

[(1,[1,3,3]),(1,[1,2,3])]

λ> sort (nub (soluciones [3,3,2]))

[(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]

λ> sort (nub (soluciones [3,2,1]))

[(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]

(finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar más transformaciones. Por ejemplo,

     finales [1,2,3]               ==  [[1,2,3]]
     finales [1,3,2]               ==  [[1,2,3],[1,3,3]]
     finales [3,2,1]               ==  [[2,2,3],[2,3,3],[3,3,3]]
     finales [1,3,2,4]             ==  [[1,2,3,4],[1,3,3,4]]
     finales [1,3,2,3]             ==  [[1,2,3,3],[1,3,3,3]]
     length (finales [9,6,0,7,2])  ==  19
     length (finales [80,60..0])   ==  420

finales [1,2,3] == [[1,2,3]]

finales [1,3,2] == [[1,2,3],[1,3,3]]

finales [3,2,1] == [[2,2,3],[2,3,3],[3,3,3]]

finales [1,3,2,4] == [[1,2,3,4],[1,3,3,4]]

finales [1,3,2,3] == [[1,2,3,3],[1,3,3,3]]

length (finales [9,6,0,7,2]) == 19

length (finales [80,60..0]) == 420

(finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas más largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo,

     finalesMaximales [9,5,7]   ==  (2,[[6,8,9],[8,8,9]])
     finalesMaximales [3,2,1]   ==  (4,[[2,3,3],[3,3,3]])
     finalesMaximales [3,2..0]  ==  (10,[[2,3,3,3],[3,3,3,3]])
     finalesMaximales [4,3..0]  ==  (20,[[3,4,4,4,4],[4,4,4,4,4]])

finalesMaximales [9,5,7] == (2,[[6,8,9],[8,8,9]])

finalesMaximales [3,2,1] == (4,[[2,3,3],[3,3,3]])

finalesMaximales [3,2..0] == (10,[[2,3,3,3],[3,3,3,3]])

finalesMaximales [4,3..0] == (20,[[3,4,4,4,4],[4,4,4,4,4]])

Soluciones

import Data.List (nub, sort)
import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

type Estado = (Int,[Int])

inicial :: [Int] -> Estado
inicial xs = (0,xs)

esFinal :: Estado -> Bool
esFinal e = null (sucesores e)

--    λ> sucesores [9,6,0,7,2]
--    [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]
sucesores :: Estado -> [Estado]
sucesores (_,[])  = []
sucesores (_,[_]) = []
sucesores (n,x:y:xs) | x > y     = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss
                     | otherwise = yss
    where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]
                       

soluciones :: [Int] -> [Estado]
soluciones xs =
    buscaEE sucesores esFinal (inicial xs)

finales :: [Int] -> [[Int]]
finales xs =
    sort (nub (map snd (soluciones xs)))
            
finalesMaximales :: [Int] -> (Int,[[Int]])
finalesMaximales xs =
    (m, [xs | (n,xs) <- es, n == m])
    where es    = sort (nub (soluciones xs))
          (m,_) = maximum es

import Data.List (nub, sort)

import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

type Estado = (Int,[Int])

inicial :: [Int] -> Estado

inicial xs = (0,xs)

esFinal :: Estado -> Bool

esFinal e = null (sucesores e)

-- λ> sucesores [9,6,0,7,2]

-- [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]

sucesores :: Estado -> [Estado]

sucesores (_,[]) = []

sucesores (_,[_]) = []

sucesores (n,x:y:xs) | x > y = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss

| otherwise = yss

where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]

soluciones :: [Int] -> [Estado]

soluciones xs =

buscaEE sucesores esFinal (inicial xs)

finales :: [Int] -> [[Int]]

finales xs =

sort (nub (map snd (soluciones xs)))

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

finalesMaximales xs =

(m, [xs | (n,xs) <- es, n == m])

where es = sort (nub (soluciones xs))

(m,_) = maximum es

Particiones de longitud fija

PorJosé A. Alonso 19-mayo-201626-mayo-2016

Definir la función

   particionesFijas :: Int -> Int -> [[Int]]

1	particionesFijas :: Int -> Int -> [[Int]]

tal que (particionesFijas n k) es la lista de listas de k números naturales no crecientes cuya suma es n. Por ejemplo,

   ghci> particionesFijas 8 2
   [[4,4],[5,3],[6,2],[7,1]]
   ghci> particionesFijas 8 3
   [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]
   ghci> particionesFijas 9 3
   [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]
   ghci> length (particionesFijas 67 5)
   8056

ghci> particionesFijas 8 2

[[4,4],[5,3],[6,2],[7,1]]

ghci> particionesFijas 8 3

[[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]

ghci> particionesFijas 9 3

[[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]

ghci> length (particionesFijas 67 5)

8056

Soluciones

-- 1ª definición
particionesFijas :: Int -> Int -> [[Int]]
particionesFijas n 1 = [[n]]
particionesFijas n k 
    | k < 1     = []
    | otherwise = [x:y:ys | x <- [1..n-1], 
                            (y:ys) <- particionesFijas (n-x) (k-1),
                            x >= y]

-- 2ª definición
particionesFijas2 :: Int -> Int -> [[Int]]
particionesFijas2 n k
    | k <= 0    = []
    | k == 1    = [[n]]
    | k == n    = [replicate k 1]
    | k > n     = []
    | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++
                  [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:
--    ghci> length (particionesFijas 800 3)
--    53333
--    (1.01 secs, 97696476 bytes)
--    
--    ghci> length (particionesFijas2 800 3)
--    53333
--    (4.52 secs, 693969028 bytes)

-- 1ª definición

particionesFijas :: Int -> Int -> [[Int]]

particionesFijas n 1 = [[n]]

particionesFijas n k

| k < 1 = []

| otherwise = [x:y:ys | x <- [1..n-1],

(y:ys) <- particionesFijas (n-x) (k-1),

x >= y]

-- 2ª definición

particionesFijas2 :: Int -> Int -> [[Int]]

particionesFijas2 n k

| k <= 0 = []

| k == 1 = [[n]]

| k == n = [replicate k 1]

| k > n = []

| otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++

[[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:

-- ghci> length (particionesFijas 800 3)

-- 53333

-- (1.01 secs, 97696476 bytes)

-- ghci> length (particionesFijas2 800 3)

-- 53333

-- (4.52 secs, 693969028 bytes)

Juego de bloques con letras

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

Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.

Definir la función

   soluciones :: [String] -> String -> [[String]]

1	soluciones :: [String] -> String -> [[String]]

tal que (soluciones bs cs) es la lista de las soluciones del juego de los bloque usando los bloques bs (cada bloque es una cadena de dos letras mayúsculas) para formar la palabra cs. Por ejemplo,

   ghci> soluciones ["AB","NO","OA"] "ANA"
   [["AB","NO","OA"],["OA","NO","AB"]]
   ghci> soluciones ["AB","NE","OA"] "Bea"
   [["AB","NE","OA"]]
   ghci> soluciones ["AB","NE","OA"] "EvA"
   []
   ghci> soluciones ["AB","NO","OA","NC"] "ANA"
   [["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]
   ghci> soluciones ["AB","NO","OA","NC"] "Anca"
   [["AB","NO","NC","OA"],["OA","NO","NC","AB"]]
   ghci> soluciones (["AB","NO","OA"] ++ replicate (10^6) "PQ") "ANA"
   [["AB","NO","OA"],["OA","NO","AB"]]

ghci> soluciones ["AB","NO","OA"] "ANA"

[["AB","NO","OA"],["OA","NO","AB"]]

ghci> soluciones ["AB","NE","OA"] "Bea"

[["AB","NE","OA"]]

ghci> soluciones ["AB","NE","OA"] "EvA"

[]

ghci> soluciones ["AB","NO","OA","NC"] "ANA"

[["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]

ghci> soluciones ["AB","NO","OA","NC"] "Anca"

[["AB","NO","NC","OA"],["OA","NO","NC","AB"]]

ghci> soluciones (["AB","NO","OA"] ++ replicate (10^6) "PQ") "ANA"

[["AB","NO","OA"],["OA","NO","AB"]]

Soluciones

import Data.List (delete)
import Data.Char (toUpper)

soluciones :: [String] -> String -> [[String]]
soluciones _ []      = [[]]
soluciones bs (c:cs) = [b:rs | b <- bs, 
                               toUpper c `elem` b,
                               rs <- soluciones (delete b bs) cs]

import Data.List (delete)

import Data.Char (toUpper)

soluciones :: [String] -> String -> [[String]]

soluciones _ [] = [[]]

soluciones bs (c:cs) = [b:rs | b <- bs,

toUpper c `elem` b,

rs <- soluciones (delete b bs) cs]

Sucesión fractal

PorJosé A. Alonso 10-mayo-201625-abril-2021

La sucesión fractal

   0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 
   10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

1 2	0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

los términos pares forman la sucesión de los números naturales

     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

1	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

los términos impares forman la misma sucesión original

     0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

1	0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

   sucFractal     :: [Integer]
   sumaSucFractal :: Integer -> Integer

1 2	sucFractal :: [Integer] sumaSucFractal :: Integer -> Integer

tales que

sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

     take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
     sucFractal !! 30     == 15
     sucFractal !! (10^7) == 5000000

take 20 sucFractal == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]

sucFractal !! 30 == 15

sucFractal !! (10^7) == 5000000

(sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

     sumaSucFractal 10      ==  13
     sumaSucFractal (10^5)  == 1666617368
     sumaSucFractal (10^10) == 16666666661668691669
     sumaSucFractal (10^15) == 166666666666666166673722792954
     sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
     length (show (sumaSucFractal (10^15000))) == 30000
     sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

sumaSucFractal 10 == 13

sumaSucFractal (10^5) == 1666617368

sumaSucFractal (10^10) == 16666666661668691669

sumaSucFractal (10^15) == 166666666666666166673722792954

sumaSucFractal (10^20) == 1666666666666666666616666684103392376198

length (show (sumaSucFractal (10^15000))) == 30000

sumaSucFractal (10^15000) `mod` (10^9) == 455972157

Soluciones

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

sucFractal1 :: [Integer]
sucFractal1 = 
    map termino [0..]

-- (termino n) es el término n de la secuencia anterior. Por ejemplo,
--   termino 0            ==  0
--   termino 1            ==  0
--   map termino [0..10]  ==  [0,0,1,0,2,1,3,0,4,2,5]
termino :: Integer -> Integer
termino 0 = 0
termino n 
    | even n    = n `div` 2
    | otherwise = termino (n `div` 2)

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

sucFractal2 :: [Integer]
sucFractal2 =
    0 : 0 : mezcla [1..] (tail sucFractal2)

-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas
-- xs e ys. Por ejemplo,
--    take 10 (mezcla [0,2..] [0,-2..])  ==  [0,0,2,-2,4,-4,6,-6,8,-8]
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla (x:xs) (y:ys) =
    x:y:mezcla xs ys

-- Comparación de eficiencia de definiciones de sucFractal
-- =======================================================

--    λ> sum (take (10^6) sucFractal1)
--    166666169612
--    (5.56 secs, 842,863,264 bytes)
--    λ> sum (take (10^6) sucFractal2)
--    166666169612
--    (1.81 secs, 306,262,616 bytes)

-- En lo que sigue usaremos la 2ª definición
sucFractal :: [Integer]
sucFractal = sucFractal2

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

sumaSucFractal1 :: Integer -> Integer
sumaSucFractal1 n =
    sum (map termino [0..n-1])

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

sumaSucFractal2 :: Integer -> Integer
sumaSucFractal2 n =
    sum (take (fromIntegral n) sucFractal)

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

sumaSucFractal3 :: Integer -> Integer
sumaSucFractal3 0 = 0
sumaSucFractal3 1 = 0
sumaSucFractal3 n
    | even n    = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)
    | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)
    where sumaN n = (n*(n-1)) `div` 2

-- Comparación de eficiencia de definiciones de sumaSucFractal
-- ===========================================================

--    λ> sumaSucFractal1 (10^6)
--    166666169612
--    (5.25 secs, 810,622,504 bytes)
--    λ> sumaSucFractal2 (10^6)
--    166666169612
--    (1.72 secs, 286,444,048 bytes)
--    λ> sumaSucFractal3 (10^6)
--    166666169612
--    (0.01 secs, 0 bytes)
--    
--    λ> sumaSucFractal2 (10^7)
--    16666661685034
--    (17.49 secs, 3,021,580,920 bytes)
--    λ> sumaSucFractal3 (10^7)
--    16666661685034
--    (0.01 secs, 0 bytes)

-- 1ª definición de sucFractal

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

sucFractal1 :: [Integer]

sucFractal1 =

map termino [0..]

-- (termino n) es el término n de la secuencia anterior. Por ejemplo,

-- termino 0 == 0

-- termino 1 == 0

-- map termino [0..10] == [0,0,1,0,2,1,3,0,4,2,5]

termino :: Integer -> Integer

termino 0 = 0

termino n

| even n = n `div` 2

| otherwise = termino (n `div` 2)

-- 2ª definición de sucFractal

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

sucFractal2 :: [Integer]

sucFractal2 =

0 : 0 : mezcla [1..] (tail sucFractal2)

-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas

-- xs e ys. Por ejemplo,

-- take 10 (mezcla [0,2..] [0,-2..]) == [0,0,2,-2,4,-4,6,-6,8,-8]

mezcla :: [Integer] -> [Integer] -> [Integer]

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

x:y:mezcla xs ys

-- Comparación de eficiencia de definiciones de sucFractal

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

-- λ> sum (take (10^6) sucFractal1)

-- 166666169612

-- (5.56 secs, 842,863,264 bytes)

-- λ> sum (take (10^6) sucFractal2)

-- 166666169612

-- (1.81 secs, 306,262,616 bytes)

-- En lo que sigue usaremos la 2ª definición

sucFractal :: [Integer]

sucFractal = sucFractal2

-- 1ª definición de sumaSucFractal

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

sumaSucFractal1 :: Integer -> Integer

sumaSucFractal1 n =

sum (map termino [0..n-1])

-- 2ª definición de sumaSucFractal

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

sumaSucFractal2 :: Integer -> Integer

sumaSucFractal2 n =

sum (take (fromIntegral n) sucFractal)

-- 3ª definición de sumaSucFractal

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

sumaSucFractal3 :: Integer -> Integer

sumaSucFractal3 0 = 0

sumaSucFractal3 1 = 0

sumaSucFractal3 n

| even n = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)

| otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)

where sumaN n = (n*(n-1)) `div` 2

-- Comparación de eficiencia de definiciones de sumaSucFractal

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

-- λ> sumaSucFractal1 (10^6)

-- 166666169612

-- (5.25 secs, 810,622,504 bytes)

-- λ> sumaSucFractal2 (10^6)

-- 166666169612

-- (1.72 secs, 286,444,048 bytes)

-- λ> sumaSucFractal3 (10^6)

-- 166666169612

-- (0.01 secs, 0 bytes)

-- λ> sumaSucFractal2 (10^7)

-- 16666661685034

-- (17.49 secs, 3,021,580,920 bytes)

-- λ> sumaSucFractal3 (10^7)

-- 16666661685034

-- (0.01 secs, 0 bytes)

Referencia

Fractal sequences and restricted Nim por Lionel Levine.

Conjuntos de primos emparejables

PorJosé A. Alonso 9-mayo-201625-abril-2021

Un conjunto de primos emparejables es un conjunto S de números primos tales que al concatenar cualquier par de elementos de S se obtiene un número primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.

Definir la función

   emparejables :: Integer -> Integer -> [[Integer]]

1	emparejables :: Integer -> Integer -> [[Integer]]

tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,

   take 5 (emparejables 2   10)  ==  [[3,7]]
   take 5 (emparejables 3   10)  ==  []
   take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]
   take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]
   take 5 (emparejables 4  100)  ==  []
   take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]

take 5 (emparejables 2 10) == [[3,7]]

take 5 (emparejables 3 10) == []

take 5 (emparejables 2 100) == [[3,7],[3,11],[3,17],[3,31],[3,37]]

take 5 (emparejables 3 100) == [[3,37,67],[7,19,97]]

take 5 (emparejables 4 100) == []

take 5 (emparejables 4 1000) == [[3,7,109,673],[23,311,677,827]]

Soluciones

import Data.Numbers.Primes (primes, isPrime)
import Data.List (nub, sort)
import qualified Data.Set as S

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

emparejables :: Integer -> Integer -> [[Integer]]
emparejables 0 _ = [[]]
emparejables n m = 
    nub [sort (x:xs) | x <- takeWhile (<=m) primes,
                       xs <- xss,
                       all (x `emparejable`) xs]
    where xss = emparejables (n-1) m

emparejable :: Integer -> Integer -> Bool
emparejable x y =
    isPrime (concatenacion x y) &&
    isPrime (concatenacion y x)

concatenacion :: Integer -> Integer -> Integer
concatenacion x y =
    read (show x ++ show y)

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

emparejables2 :: Integer -> Integer -> [[Integer]]
emparejables2 n m = map reverse (aux n m)
    where aux 1 m = [[x] | x <- takeWhile (<=m) primes]
          aux n m = 
              [p:ys | ys@(x:xs) <- xss,
                      p <- dropWhile (<x) ps,
                      all (p `emparejable`) ys]
              where ps  = takeWhile (<=m) primes
                    xss = aux (n-1) m

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

emparejables3 :: Integer -> Integer -> [[Integer]]
emparejables3 n m = map S.toList (aux n m)
    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]
          aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,
                                     xs <- xss,
                                     all (x `emparejable`) xs]
              where xss = aux (n-1) m

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

emparejables4 :: Integer -> Integer -> [[Integer]]
emparejables4 n m = map S.toList (aux n m)
    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]
          aux n m = 
              [S.insert p ys | ys <- xss,
                               let (x,xs) = S.deleteFindMax ys,
                               p <- dropWhile (<x) ps,
                               all (p `emparejable`) ys]
              where ps  = takeWhile (<=m) primes
                    xss = aux (n-1) m

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

--    λ> head (emparejables 4 1000)
--    [3,7,109,673]
--    (20.36 secs, 11,781,891,120 bytes)
--    
--    λ> head (emparejables2 4 1000)
--    [3,7,109,673]
--    (0.02 secs, 0 bytes)
--    
--    λ> head (emparejables3 4 1000)
--    [3,7,109,673]
--    (38.04 secs, 21,542,334,024 bytes)
--    
--    λ> head (emparejables4 4 1000)
--    [3,7,109,673]
--    (0.03 secs, 0 bytes)

import Data.Numbers.Primes (primes, isPrime)

import Data.List (nub, sort)

import qualified Data.Set as S

-- 1ª definición

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

emparejables :: Integer -> Integer -> [[Integer]]

emparejables 0 _ = [[]]

emparejables n m =

nub [sort (x:xs) | x <- takeWhile (<=m) primes,

xs <- xss,

all (x `emparejable`) xs]

where xss = emparejables (n-1) m

emparejable :: Integer -> Integer -> Bool

emparejable x y =

isPrime (concatenacion x y) &&

isPrime (concatenacion y x)

concatenacion :: Integer -> Integer -> Integer

concatenacion x y =

read (show x ++ show y)

-- 2ª definición

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

emparejables2 :: Integer -> Integer -> [[Integer]]

emparejables2 n m = map reverse (aux n m)

where aux 1 m = [[x] | x <- takeWhile (<=m) primes]

aux n m =

[p:ys | ys@(x:xs) <- xss,

p <- dropWhile (<x) ps,

all (p `emparejable`) ys]

where ps = takeWhile (<=m) primes

xss = aux (n-1) m

-- 3ª definición

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

emparejables3 :: Integer -> Integer -> [[Integer]]

emparejables3 n m = map S.toList (aux n m)

where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]

aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,

xs <- xss,

all (x `emparejable`) xs]

where xss = aux (n-1) m

-- 2ª definición

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

emparejables4 :: Integer -> Integer -> [[Integer]]

emparejables4 n m = map S.toList (aux n m)

where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]

aux n m =

[S.insert p ys | ys <- xss,

let (x,xs) = S.deleteFindMax ys,

p <- dropWhile (<x) ps,

all (p `emparejable`) ys]

where ps = takeWhile (<=m) primes

xss = aux (n-1) m

-- Comparación de eficiencia

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

-- λ> head (emparejables 4 1000)

-- [3,7,109,673]

-- (20.36 secs, 11,781,891,120 bytes)

-- λ> head (emparejables2 4 1000)

-- [3,7,109,673]

-- (0.02 secs, 0 bytes)

-- λ> head (emparejables3 4 1000)

-- [3,7,109,673]

-- (38.04 secs, 21,542,334,024 bytes)

-- λ> head (emparejables4 4 1000)

-- [3,7,109,673]

-- (0.03 secs, 0 bytes)

Cadenas de divisores

PorJosé A. Alonso 6-mayo-201625-abril-2021

Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].

Definir la función

   cadenasDivisores :: Int -> [[Int]]

1	cadenasDivisores :: Int -> [[Int]]

tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,

   λ> cadenasDivisores 12
   [[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]
   λ> length (cadenaDivisores 48)
   48
   λ> length (cadenaDivisores 120)
   132

λ> cadenasDivisores 12

[[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]

λ> length (cadenaDivisores 48)

λ> length (cadenaDivisores 120)

132

Soluciones

import Data.List (sort)
import Data.Numbers.Primes (isPrime)

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

cadenasDivisores :: Int -> [[Int]]
cadenasDivisores n = sort (extiendeLista [[n]])
    where extiendeLista []           = []
          extiendeLista ((1:xs):yss) = xs : extiendeLista yss
          extiendeLista ((x:xs):yss) =
              extiendeLista ([y:x:xs | y <- divisores x] ++ yss)

-- (divisores x) es la lista decreciente de los divisores de x distintos
-- de x. Por ejemplo,
--    divisores 12  ==  [6,4,3,2,1]
divisores :: Int -> [Int]
divisores x = 
    [y | y <- [a,a-1..1], x `mod` y == 0]
    where a = x `div` 2

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

cadenasDivisores2 :: Int -> [[Int]]
cadenasDivisores2 = sort . aux
    where aux 1 = [[]]
          aux n = [xs ++ [n] | xs <- concatMap aux (divisores n)]

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

cadenasDivisores3 :: Int -> [[Int]]
cadenasDivisores3 = sort . map reverse . aux
    where aux 1 = [[]]
          aux n = map (n:) (concatMap aux (divisores3 n))

-- (divisores3 x) es la lista creciente de los divisores de x distintos
-- de x. Por ejemplo,
--    divisores3 12  ==  [1,2,3,4,6]
divisores3 :: Int -> [Int]
divisores3 x = 
    [y | y <- [1..a], x `mod` y == 0]
    where a = x `div` 2

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

nCadenasDivisores1 :: Int -> Int
nCadenasDivisores1 = length . cadenasDivisores

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

nCadenasDivisores2 :: Int -> Int
nCadenasDivisores2 1 = 1
nCadenasDivisores2 n = 
    sum [nCadenasDivisores2 x | x <- divisores n]

import Data.List (sort)

import Data.Numbers.Primes (isPrime)

-- 1ª definición

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

cadenasDivisores :: Int -> [[Int]]

cadenasDivisores n = sort (extiendeLista [[n]])

where extiendeLista [] = []

extiendeLista ((1:xs):yss) = xs : extiendeLista yss

extiendeLista ((x:xs):yss) =

extiendeLista ([y:x:xs | y <- divisores x] ++ yss)

-- (divisores x) es la lista decreciente de los divisores de x distintos

-- de x. Por ejemplo,

-- divisores 12 == [6,4,3,2,1]

divisores :: Int -> [Int]

divisores x =

[y | y <- [a,a-1..1], x `mod` y == 0]

where a = x `div` 2

-- 2ª definición

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

cadenasDivisores2 :: Int -> [[Int]]

cadenasDivisores2 = sort . aux

where aux 1 = [[]]

aux n = [xs ++ [n] | xs <- concatMap aux (divisores n)]

-- 3ª definición

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

cadenasDivisores3 :: Int -> [[Int]]

cadenasDivisores3 = sort . map reverse . aux

where aux 1 = [[]]

aux n = map (n:) (concatMap aux (divisores3 n))

-- (divisores3 x) es la lista creciente de los divisores de x distintos

-- de x. Por ejemplo,

-- divisores3 12 == [1,2,3,4,6]

divisores3 :: Int -> [Int]

divisores3 x =

[y | y <- [1..a], x `mod` y == 0]

where a = x `div` 2

-- 1ª definición de nCadenasDivisores

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

nCadenasDivisores1 :: Int -> Int

nCadenasDivisores1 = length . cadenasDivisores

-- 2ª definición de nCadenasDivisores

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

nCadenasDivisores2 :: Int -> Int

nCadenasDivisores2 1 = 1

nCadenasDivisores2 n =

sum [nCadenasDivisores2 x | x <- divisores n]

Referencias

Sucesión A163272 de OEIS.
Ordered and unordered factorizations of integers por A. Knopfmacher y M. Mays

Número de divisiones en el algoritmo de Euclides

PorJosé A. Alonso 5-mayo-201612-mayo-2016

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = b,                   si a = 0               
            = mcd (a módulo b, b), si a > b
            = mcd (a, b módulo a), si b >= a

mcd(a,b) = a, si b = 0

= b, si a = 0

= mcd (a módulo b, b), si a > b

= mcd (a, b módulo a), si b >= a

Definir la función

   mcdYdivisiones :: Int -> Int -> (Int,Int)

1	mcdYdivisiones :: Int -> Int -> (Int,Int)

tal que (mcdYdivisiones a b) es el número de divisiones usadas en el cálculo del máximo común divisor de a y b mediante el algoritmo de Euclides. Por ejemplo,

   mcdYdivisiones 252 198 == (18,4)

1	mcdYdivisiones 252 198 == (18,4)

ya que los 4 divisiones del cálculo son

     mcd 252 198
   = mcd  54 198
   = mcd  54  36
   = mcd  18  36
   = mcd  18   0

mcd 252 198

= mcd 54 198

= mcd 54 36

= mcd 18 36

= mcd 18 0

Comprobar con QuickCheck que el número de divisiones requeridas por el algoritmo de Euclides para calcular el MCD de a y b es igual o menor que cinco veces el número de dígitos de menor de los números a y b.

Soluciones

import Test.QuickCheck
import Debug.Trace 

mcdYdivisiones :: Int -> Int -> (Int,Int)
mcdYdivisiones a b = mcd a b 0
    where mcd a 0 n = (a,n)
          mcd 0 b n = (b,n)
          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)
                    | otherwise = mcd a (b `mod` a) (n+1) 

-- La propiedad es
prop_mcdYdivisiones :: Int -> Int -> Property
prop_mcdYdivisiones a b =
    a > 0 && b > 0 ==>
      n < 5 * length (show (min a b))  
    where (_,n) = mcdYdivisiones a b
                 
-- La comprobación es
--    λ> quickCheck prop_mcdYdivisiones
--    +++ OK, passed 100 tests.

-- 2ª definición (con traza)
mcdYdivisiones2 :: Int -> Int -> (Int,Int)
mcdYdivisiones2 a b = mcd a b 0
    where mcd a b n
              | trace (show a ++ ", " ++ show b) False = undefined
          mcd a 0 n = (a,n)
          mcd 0 b n = (b,n)
          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)
                    | otherwise = mcd a (b `mod` a) (n+1) 

-- Por ejemplo,
--    λ> mcdYdivisiones2 252 198
--    252, 198
--    54, 198
--    54, 36
--    18, 36
--    18, 0
--    (18,4)

import Test.QuickCheck

import Debug.Trace

mcdYdivisiones :: Int -> Int -> (Int,Int)

mcdYdivisiones a b = mcd a b 0

where mcd a 0 n = (a,n)

mcd 0 b n = (b,n)

mcd a b n | a > b = mcd (a `mod` b) b (n+1)

| otherwise = mcd a (b `mod` a) (n+1)

-- La propiedad es

prop_mcdYdivisiones :: Int -> Int -> Property

prop_mcdYdivisiones a b =

a > 0 && b > 0 ==>

n < 5 * length (show (min a b))

where (_,n) = mcdYdivisiones a b

-- La comprobación es

-- λ> quickCheck prop_mcdYdivisiones

-- +++ OK, passed 100 tests.

-- 2ª definición (con traza)

mcdYdivisiones2 :: Int -> Int -> (Int,Int)

mcdYdivisiones2 a b = mcd a b 0

where mcd a b n

| trace (show a ++ ", " ++ show b) False = undefined

mcd a 0 n = (a,n)

mcd 0 b n = (b,n)

mcd a b n | a > b = mcd (a `mod` b) b (n+1)

| otherwise = mcd a (b `mod` a) (n+1)

-- Por ejemplo,

-- λ> mcdYdivisiones2 252 198

-- 252, 198

-- 54, 198

-- 54, 36

-- 18, 36

-- 18, 0

-- (18,4)

Mezcla de infinitas listas infinitas

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

Definir la función

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

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

tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,

   ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
   [2,3,4,5,6,7,8,9,10,11]
   ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
   [2,4,6,8,9,10,12,14,16,18]

ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])

[2,3,4,5,6,7,8,9,10,11]

ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])

[2,4,6,8,9,10,12,14,16,18]

Soluciones

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

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

Expresiones aritmética normalizadas

PorJosé A. Alonso 2-mayo-201625-abril-2021

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

   data Expr = Var String
             | S Expr Expr
             | P Expr Expre

data Expr = Var String

| S Expr Expr

| P Expr Expre

Por ejemplo, x.(y+z) se representa por (P (V «x») (S (V «y») (V «z»)))

Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.

Definir las funciones

   esTermino, esNormal :: Expr -> Bool

1	esTermino, esNormal :: Expr -> Bool

tales que

(esTermino a) se verifica si a es un término. Por ejemplo,

     esTermino (V "x")                                    == True
     esTermino (P (V "x") (P (V "y") (V "z")))            == True
     esTermino (P (V "x") (S (V "y") (V "z")))            == False
     esTermino (S (V "x") (P (V "y") (V "z")))            == False

esTermino (V "x") == True

esTermino (P (V "x") (P (V "y") (V "z"))) == True

esTermino (P (V "x") (S (V "y") (V "z"))) == False

esTermino (S (V "x") (P (V "y") (V "z"))) == False

(esNormal a) se verifica si a está en forma normal. Por ejemplo,

     esNormal (V "x")                                     == True
     esNormal (P (V "x") (P (V "y") (V "z")))             == True
     esNormal (S (V "x") (P (V "y") (V "z")))             == True
     esNormal (P (V "x") (S (V "y") (V "z")))             == False
     esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

esNormal (V "x") == True

esNormal (P (V "x") (P (V "y") (V "z"))) == True

esNormal (S (V "x") (P (V "y") (V "z"))) == True

esNormal (P (V "x") (S (V "y") (V "z"))) == False

esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

Soluciones

data Expr = V String
          | S Expr Expr
          | P Expr Expr

esTermino :: Expr -> Bool
esTermino (V _)   = True
esTermino (S _ _) = False
esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool
esNormal (S a b) = esNormal a && esNormal b
esNormal a       = esTermino a

data Expr = V String

| S Expr Expr

| P Expr Expr

esTermino :: Expr -> Bool

esTermino (V _) = True

esTermino (S _ _) = False

esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool

esNormal (S a b) = esNormal a && esNormal b

esNormal a = esTermino a

Mínima diferencia entre elementos de una lista

PorJosé A. Alonso 18-abril-201625-abril-2016

Definir la función

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

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

tal que (minimaDiferencia xs) es el menor valor absoluto de las diferencias entre todos los pares de elementos de xs (que se supone que tiene al menos 2 elementos). Por ejemplo,

   minimaDiferencia [1,5,3,19,18,25]  ==  1
   minimaDiferencia [30,5,20,9]       ==  4
   minimaDiferencia [30,5,20,9,5]     ==  0
   minimaDiferencia [1..10^6]         ==  1

minimaDiferencia [1,5,3,19,18,25] == 1

minimaDiferencia [30,5,20,9] == 4

minimaDiferencia [30,5,20,9,5] == 0

minimaDiferencia [1..10^6] == 1

En el primer ejemplo la menor diferencia es 1 y se da entre los elementos 19 y 18; en el 2ª es 4 entre los elementos 5 y 9 y en la 3ª es 0 porque el elemento 5 está repetido.

Soluciones

import Data.List (delete, sort)

-- 1ª definición    
minimaDiferencia1 :: (Num a, Ord a) => [a] -> a
minimaDiferencia1 xs =
    minimum [abs (x - y) | x <- xs, y <- delete x xs]

-- 2ª definición    
minimaDiferencia2 :: (Num a, Ord a) => [a] -> a
minimaDiferencia2 [x,y]  = abs (x - y)
minimaDiferencia2 (x:xs) = min (minimum [abs (x - y) | y <- xs])
                               (minimaDiferencia2 xs)      

-- 3ª definición    
minimaDiferencia3 :: (Num a, Ord a) => [a] -> a
minimaDiferencia3 xs =
    minimum [y - x | (x,y) <- zip ys (tail ys)]
    where ys = sort xs

-- Comparación de eficiencia
--    λ> minimaDiferencia1 [1..2*10^3]
--    1
--    (3.47 secs, 1,419,790,688 bytes)
--    λ> minimaDiferencia2 [1..2*10^3]
--    1
--    (0.78 secs, 684,030,712 bytes)
--    λ> minimaDiferencia3 [1..2*10^3]
--    1
--    (0.02 secs, 0 bytes)
--    
--    λ> minimaDiferencia2 [1..5*10^3]
--    1
--    (5.14 secs, 4,233,952,776 bytes)
--    λ> minimaDiferencia3 [1..5*10^3]
--    1
--    (0.02 secs, 0 bytes)

import Data.List (delete, sort)

-- 1ª definición

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

minimaDiferencia1 xs =

minimum [abs (x - y) | x <- xs, y <- delete x xs]

-- 2ª definición

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

minimaDiferencia2 [x,y] = abs (x - y)

minimaDiferencia2 (x:xs) = min (minimum [abs (x - y) | y <- xs])

(minimaDiferencia2 xs)

-- 3ª definición

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

minimaDiferencia3 xs =

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

where ys = sort xs

-- Comparación de eficiencia

-- λ> minimaDiferencia1 [1..2*10^3]

-- 1

-- (3.47 secs, 1,419,790,688 bytes)

-- λ> minimaDiferencia2 [1..2*10^3]

-- 1

-- (0.78 secs, 684,030,712 bytes)

-- λ> minimaDiferencia3 [1..2*10^3]

-- 1

-- (0.02 secs, 0 bytes)

-- λ> minimaDiferencia2 [1..5*10^3]

-- 1

-- (5.14 secs, 4,233,952,776 bytes)

-- λ> minimaDiferencia3 [1..5*10^3]

-- 1

-- (0.02 secs, 0 bytes)

Caminos reducidos

PorJosé A. Alonso 12-abril-201625-abril-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
--    (2.17 secs, 379049224 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

-- (2.17 secs, 379049224 bytes)

Raíz entera

PorJosé A. Alonso 8-abril-20161-mayo-2016

Definir la función

   raizEnt :: Integer -> Integer -> Integer

1	raizEnt :: Integer -> Integer -> Integer

tal que (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que y^n <= x. Por ejemplo,

   raizEnt  8 3      ==  2
   raizEnt  9 3      ==  2
   raizEnt 26 3      ==  2
   raizEnt 27 3      ==  3
   raizEnt (10^50) 2 ==  10000000000000000000000000

raizEnt 8 3 == 2

raizEnt 9 3 == 2

raizEnt 26 3 == 2

raizEnt 27 3 == 3

raizEnt (10^50) 2 == 10000000000000000000000000

Comprobar con QuickCheck que para todo número natural n,

    raizEnt (10^(2*n)) 2 == 10^n

1	raizEnt (10^(2*n)) 2 == 10^n

Soluciones

import Test.QuickCheck

-- 1ª definición
raizEnt1 :: Integer -> Integer -> Integer
raizEnt1 x n =
    last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición         
raizEnt2 :: Integer -> Integer -> Integer
raizEnt2 x n =
    floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,
--    λ> raizEnt2 (10^50) 2 == 10^25
--    False
          
-- 3ª definición          
raizEnt3 :: Integer -> Integer -> Integer
raizEnt3 x n = aux (1,x)
    where aux (a,b) | d == x    = c
                    | c == a    = c
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^n

-- Comparación de eficiencia
--    λ> raizEnt1 (10^14) 2
--    10000000
--    (6.15 secs, 6,539,367,976 bytes)
--    λ> raizEnt2 (10^14) 2
--    10000000
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^14) 2
--    10000000
--    (0.00 secs, 25,871,944 bytes)
--    
--    λ> raizEnt2 (10^50) 2
--    9999999999999998758486016
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^50) 2
--    10000000000000000000000000
--    (0.00 secs, 0 bytes)
                        
-- La propiedad es                        
prop_raizEnt :: Integer -> Bool
prop_raizEnt n =
    raizEnt3 (10^(2*m)) 2 == 10^m
    where m = abs n

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

import Test.QuickCheck

-- 1ª definición

raizEnt1 :: Integer -> Integer -> Integer

raizEnt1 x n =

last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición

raizEnt2 :: Integer -> Integer -> Integer

raizEnt2 x n =

floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,

-- λ> raizEnt2 (10^50) 2 == 10^25

-- False

-- 3ª definición

raizEnt3 :: Integer -> Integer -> Integer

raizEnt3 x n = aux (1,x)

where aux (a,b) | d == x = c

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

where c = (a+b) `div` 2

d = c^n

-- Comparación de eficiencia

-- λ> raizEnt1 (10^14) 2

-- 10000000

-- (6.15 secs, 6,539,367,976 bytes)

-- λ> raizEnt2 (10^14) 2

-- 10000000

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^14) 2

-- 10000000

-- (0.00 secs, 25,871,944 bytes)

-- λ> raizEnt2 (10^50) 2

-- 9999999999999998758486016

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^50) 2

-- 10000000000000000000000000

-- (0.00 secs, 0 bytes)

-- La propiedad es

prop_raizEnt :: Integer -> Bool

prop_raizEnt n =

raizEnt3 (10^(2*m)) 2 == 10^m

where m = abs n

-- La comprobación es

-- λ> quickCheck prop_raizEnt

-- +++ OK, passed 100 tests.

Soluciones en Maxima

raizEnt (x,n) := inrt (x,n)$

1	raizEnt (x,n) := inrt (x,n)$

Números de Lucas

PorJosé A. Alonso 7-abril-201614-abril-2016

Los números de Lucas son los elementos de la sucesión L(n) definida por

   L(0) = 2
   L(1) = 1
   L(n) = L(n-1) + L(n-2), si n > 1.

L(0) = 2

L(1) = 1

L(n) = L(n-1) + L(n-2), si n > 1.

Los primeros números de Lucas son

   2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

1	2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

Definir las funciones

   nLucas :: Integer -> Integer 
   lucas  :: [Integer]

1 2	nLucas :: Integer -> Integer lucas :: [Integer]

tales que

(nLucas n) es el n-ésimo número de Lucas. Por ejemplo,

   nLucas 5                       ==  11
   nLucas 32                      ==  4870847
   length (show (nLucas (10^5)))  ==  20899

nLucas 5 == 11

nLucas 32 == 4870847

length (show (nLucas (10^5))) == 20899

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

   take 11 lucas ==  [2,1,3,4,7,11,18,29,47,76,123]

1	take 11 lucas == [2,1,3,4,7,11,18,29,47,76,123]

Soluciones

import Data.List (genericIndex)

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

nLucas1 :: Integer -> Integer
nLucas1 0 = 2
nLucas1 1 = 1
nLucas1 n = nLucas1 (n-1) + nLucas1 (n-2)

lucas1 :: [Integer]
lucas1 = [nLucas1 n | n <- [0..]]

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

lucas2 :: [Integer]
lucas2 = 2 : 1 : zipWith (+) lucas2 (tail lucas2)

nLucas2 :: Integer -> Integer
nLucas2 n = lucas2 `genericIndex` n

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

lucas3  :: [Integer]
lucas3 = 2 : scanl (+) 1 lucas3
 
nLucas3 :: Integer -> Integer
nLucas3 = genericIndex lucas3
            
-- Comparación de eficiencia
-- =========================

--    λ> nLucas1 32
--    4870847
--    (3.22 secs, 1,467,677,208 bytes)
--    λ> nLucas2 32
--    4870847
--    (0.00 secs, 0 bytes)
--    λ> nLucas3 32
--    4870847
--    (0.00 secs, 0 bytes)
--    
--    λ> length (show (nLucas2 230000))
--    48068
--    (1.57 secs, 2,415,008,392 bytes)
--    λ> length (show (nLucas3 230000))
--    48068
--    (2.08 secs, 2,411,107,352 bytes)

import Data.List (genericIndex)

-- 1ª definición

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

nLucas1 :: Integer -> Integer

nLucas1 0 = 2

nLucas1 1 = 1

nLucas1 n = nLucas1 (n-1) + nLucas1 (n-2)

lucas1 :: [Integer]

lucas1 = [nLucas1 n | n <- [0..]]

-- 2ª definición

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

lucas2 :: [Integer]

lucas2 = 2 : 1 : zipWith (+) lucas2 (tail lucas2)

nLucas2 :: Integer -> Integer

nLucas2 n = lucas2 `genericIndex` n

-- 3ª definición

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

lucas3 :: [Integer]

lucas3 = 2 : scanl (+) 1 lucas3

nLucas3 :: Integer -> Integer

nLucas3 = genericIndex lucas3

-- Comparación de eficiencia

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

-- λ> nLucas1 32

-- 4870847

-- (3.22 secs, 1,467,677,208 bytes)

-- λ> nLucas2 32

-- 4870847

-- (0.00 secs, 0 bytes)

-- λ> nLucas3 32

-- 4870847

-- (0.00 secs, 0 bytes)

-- λ> length (show (nLucas2 230000))

-- 48068

-- (1.57 secs, 2,415,008,392 bytes)

-- λ> length (show (nLucas3 230000))

-- 48068

-- (2.08 secs, 2,411,107,352 bytes)

Soluciones en Maxima

nLucas (n) := lucas (n)$

1	nLucas (n) := lucas (n)$

La evaluación de los ejemplos es

(%i5) nLucas (5);
(%o5) 11
(%i6) nLucas (32);
(%o6) 4870847

(%i5) nLucas (5);

(%o5) 11

(%i6) nLucas (32);

(%o6) 4870847

Inverso multiplicativo modular

PorJosé A. Alonso 6-abril-201626-marzo-2022

El inverso multiplicativo modular de un entero n módulo p es el número m, entre 1 y p-1, tal que

   mn = 1 (mod p)

1	mn = 1 (mod p)

Por ejemplo, el inverso multiplicativo de 2 módulo 5 es 3, ya que 1 <= 3 <= 4 y 2×3 = 1 (mod 5).

El inverso multipicativo de n módulo p existe si y sólo si n y p son coprimos; es decir, si mcd(n,p) = 1.

Definir la función

   invMod :: Integer -> Integer -> Maybe Integer

1	invMod :: Integer -> Integer -> Maybe Integer

tal que (invMod n p) es justo el inverso multiplicativo de n módulo p, si existe y Nothing en caso contrario. Por ejemplo,

   λ> invMod 2 5
   Just 3
   λ> invMod 2 6
   Nothing
   λ> [(x,invMod x 5) | x <- [0..4]]
   [(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]
   λ> [(x,invMod x 6) | x <- [0..5]]
   [(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]
   λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)
   True

λ> invMod 2 5

Just 3

λ> invMod 2 6

Nothing

λ> [(x,invMod x 5) | x <- [0..4]]

[(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]

λ> [(x,invMod x 6) | x <- [0..5]]

[(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]

λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)

True

Soluciones

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

invMod1 :: Integer -> Integer -> Maybe Integer
invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])
            | otherwise    = Nothing

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

invMod2 :: Integer -> Integer -> Maybe Integer
invMod2 n p | m /= 1    = Nothing
            | x < 0     = Just (x + p)
            | otherwise = Just x
    where (x,_,m) = mcdExt n p

-- [Algoritmo extendido de Euclides]
-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor
-- de a y b y se cumple que ax + by = g. Por ejemplo,
--    mcdExt  2  5  ==  (-2,1,1)
--    mcdExt  2  6  ==  ( 1,0,2)
--    mcdExt 12 15  ==  (-1,1,3)
mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)
mcdExt a 0 = (1, 0, a)
mcdExt a b = (t, s - q * t, g)
  where (q, r)    = a `quotRem` b
        (s, t, g) = mcdExt b r

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

invMod3 :: Integer -> Integer -> Maybe Integer
invMod3 n p | gcd n p == 1 = Just (aux n p)
            | otherwise    = Nothing
  where aux 1 p = 1
        aux n p = (x * p + 1) `div` n
          where x = n - aux (p `mod` n) n                    

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

--    λ> invMod1 (10^7) (1+10^7)
--    Just 10000000
--    (5.05 secs, 2,872,350,896 bytes)
--    λ> invMod2 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    λ> invMod3 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    
--    λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)
--    True
--    (0.88 secs, 55,728,120 bytes)
--    λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)
--    True
--    (1.99 secs, 80,644,352 bytes)

-- 1ª definición

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

invMod1 :: Integer -> Integer -> Maybe Integer

invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])

| otherwise = Nothing

-- 2ª definición

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

invMod2 :: Integer -> Integer -> Maybe Integer

invMod2 n p | m /= 1 = Nothing

| x < 0 = Just (x + p)

| otherwise = Just x

where (x,_,m) = mcdExt n p

-- [Algoritmo extendido de Euclides]

-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor

-- de a y b y se cumple que ax + by = g. Por ejemplo,

-- mcdExt 2 5 == (-2,1,1)

-- mcdExt 2 6 == ( 1,0,2)

-- mcdExt 12 15 == (-1,1,3)

mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)

mcdExt a 0 = (1, 0, a)

mcdExt a b = (t, s - q * t, g)

where (q, r) = a `quotRem` b

(s, t, g) = mcdExt b r

-- 3ª definición

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

invMod3 :: Integer -> Integer -> Maybe Integer

invMod3 n p | gcd n p == 1 = Just (aux n p)

| otherwise = Nothing

where aux 1 p = 1

aux n p = (x * p + 1) `div` n

where x = n - aux (p `mod` n) n

-- Comparación de eficiencia

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

-- λ> invMod1 (10^7) (1+10^7)

-- Just 10000000

-- (5.05 secs, 2,872,350,896 bytes)

-- λ> invMod2 (10^7) (1+10^7)

-- Just 10000000

-- (0.00 secs, 0 bytes)

-- λ> invMod3 (10^7) (1+10^7)

-- Just 10000000

-- (0.00 secs, 0 bytes)

-- λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)

-- True

-- (0.88 secs, 55,728,120 bytes)

-- λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)

-- True

-- (1.99 secs, 80,644,352 bytes)

Solución en Maxima

invMod (n,p) := block ([r],
  r : inv_mod (n,p),
  if integerp (r)
  then Just (r)
  else Nothing)$

invMod (n,p) := block ([r],

r : inv_mod (n,p),

if integerp (r)

then Just (r)

else Nothing)$

La evaluación de los ejemplos es

(%i2) invMod (2,5);
(%o2) Just(3)
(%i3) invMod (2,6);
(%o3) Nothing
(%i4) makelist([x,invMod(x,5)],x,0,4);
(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]
(%i5) makelist([x,invMod(x,6)],x,0,5);
(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]
(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));
(%o6) true

(%i2) invMod (2,5);

(%o2) Just(3)

(%i3) invMod (2,6);

(%o3) Nothing

(%i4) makelist([x,invMod(x,5)],x,0,4);

(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]

(%i5) makelist([x,invMod(x,6)],x,0,5);

(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]

(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));

(%o6) true

Referencia

Calculating multiplicative inverses in modular arithmetic

Clases de equivalencia

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

Definir la función

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

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

tal que (clasesEquivalencia xs r) es la lista de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

   λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3)
   [[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]]
   λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0)
   [[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]]
   λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y)
   [[-4,4],[-3,3],[-2,2],[-1,1],[0]]

λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3)

[[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]]

λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0)

[[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]]

λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y)

[[-4,4],[-3,3],[-2,2],[-1,1],[0]]

Soluciones

import Data.List (partition)

clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]
clasesEquivalencia [] r = []
clasesEquivalencia ys@(x:xs) r =
    us : clasesEquivalencia vs r
    where (us,vs) = partition (r x) ys

import Data.List (partition)

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

clasesEquivalencia [] r = []

clasesEquivalencia ys@(x:xs) r =

us : clasesEquivalencia vs r

where (us,vs) = partition (r x) ys

Solución en Maxima

clasesEquivalencia (xs,r) :=
  equiv_classes (setify (xs),r)$

1 2	clasesEquivalencia (xs,r) := equiv_classes (setify (xs),r)$

La evaluación de los ejemplos es

(%i6) xs : makelist (k,k,1,10)$
(%i7) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,3) = 0)));
(%o7) {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}}
(%i8) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,5) = 0)));
(%o8) {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}
(%i9) clasesEquivalencia (makelist(k,k,-4,4), lambda ([x,y], is (abs (x) = abs (y))));
(%o9) {{- 4, 4}, {- 3, 3}, {- 2, 2}, {- 1, 1}, {0}}

(%i6) xs : makelist (k,k,1,10)$

(%i7) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,3) = 0)));

(%o7) {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}}

(%i8) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,5) = 0)));

(%o8) {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}

(%i9) clasesEquivalencia (makelist(k,k,-4,4), lambda ([x,y], is (abs (x) = abs (y))));

(%o9) {{- 4, 4}, {- 3, 3}, {- 2, 2}, {- 1, 1}, {0}}

Factorial generalizado

PorJosé A. Alonso 4-abril-201611-abril-2016

El factorial generalizado de x respecto de y y z es el producto x(x-z)(x-2z) … (x-(y-1)z). Por ejemplo, el factorial generalizado de 7 respecto de 3 y 2 es 7x5x3 = 105 y el de 7 respecto de 2 y 3 es 7×4 = 28

Definir la función

   factGen :: Integer -> Integer -> Integer -> Integer

1	factGen :: Integer -> Integer -> Integer -> Integer

tal que (factGen x y z) es el factorial generalizado de x respecto de y y z. Por ejemplo,

   factGen 7 3 2  ==  105
   factGen 7 2 3  ==  28

1 2	factGen 7 3 2 == 105 factGen 7 2 3 == 28

Nota: Se supone que x, y y z son positivos y z < x.

Comprobar con QuickCheck que (factGen x x 1) es el factorial de x.

Soluciones

import Test.QuickCheck

-- 1ª definición (por comprensión):
factGen :: Integer -> Integer -> Integer -> Integer
factGen x y z = product [x,x-z..x-(y-1)*z]

-- 2ª definición (por recursión):
factGen2 :: Integer -> Integer -> Integer -> Integer
factGen2 x 1 _ = x
factGen2 x y z = x * factGen2 (x-z) (y-1) z

-- Propiedad de equivalencia
prop_equiv :: Positive Integer
           -> Positive Integer -> Positive Integer -> Property
prop_equiv (Positive x) (Positive y) (Positive z) =
    z < x ==> factGen x y z == factGen2 x y z

-- La comprobación es
--    λ> quickCheck prop_equiv
--    +++ OK, passed 100 tests.
      
-- La propiedad es       
prop_factGen :: Positive Integer -> Bool
prop_factGen (Positive x) =
    factGen x x 1 == product [1..x]

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

import Test.QuickCheck

-- 1ª definición (por comprensión):

factGen :: Integer -> Integer -> Integer -> Integer

factGen x y z = product [x,x-z..x-(y-1)*z]

-- 2ª definición (por recursión):

factGen2 :: Integer -> Integer -> Integer -> Integer

factGen2 x 1 _ = x

factGen2 x y z = x * factGen2 (x-z) (y-1) z

-- Propiedad de equivalencia

prop_equiv :: Positive Integer

-> Positive Integer -> Positive Integer -> Property

prop_equiv (Positive x) (Positive y) (Positive z) =

z < x ==> factGen x y z == factGen2 x y z

-- La comprobación es

-- λ> quickCheck prop_equiv

-- +++ OK, passed 100 tests.

-- La propiedad es

prop_factGen :: Positive Integer -> Bool

prop_factGen (Positive x) =

factGen x x 1 == product [1..x]

-- La comprobación es

-- λ> quickCheck prop_factGen

-- +++ OK, passed 100 tests.

Solución en Maxima

factGen (x,y,z) := genfact (x,y,z)$

1	factGen (x,y,z) := genfact (x,y,z)$

Representación decimal de números racionales

PorJosé A. Alonso 1-abril-20168-abril-2016

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

    6/2  = 3                  se representa por (3,[],[])
    1/2  = 0.5                se representa por (0,[5],[])
    1/3  = 0.333333...        se representa por (0,[],[3])  
   23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

6/2 = 3 se representa por (3,[],[])

1/2 = 0.5 se representa por (0,[5],[])

1/3 = 0.333333... se representa por (0,[],[3])

23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

1	type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Racional = (Integer,Integer)

1	type Racional = (Integer,Integer)

Definir las funciones

   decimal  :: Racional -> Decimal
   racional :: Decimal -> Racional

1 2	decimal :: Racional -> Decimal racional :: Decimal -> Racional

tales que

(decimal r) es la representación decimal del número racional r. Por ejemplo,

        decimal (1,4)    ==  (0,[2,5],[])
        decimal (1,3)    ==  (0,[],[3])
        decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

decimal (1,4) == (0,[2,5],[])

decimal (1,3) == (0,[],[3])

decimal (23,14) == (1,[6],[4,2,8,5,7,1])

(racional d) es el número racional cuya representación decimal es d. Por ejemplo,

        racional (0,[2,5],[])           ==  (1,4)
        racional (0,[],[3])             ==  (1,3)
        racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

racional (0,[2,5],[]) == (1,4)

racional (0,[],[3]) == (1,3)

racional (1,[6],[4,2,8,5,7,1]) == (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

   ghci> let (_,_,p) = decimal (23,14) in concatMap show p
   "428571"
   ghci> let (_,_,p) = decimal (1,47) in concatMap show p
   "0212765957446808510638297872340425531914893617"
   ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)
   540

ghci> let (_,_,p) = decimal (23,14) in concatMap show p

"428571"

ghci> let (_,_,p) = decimal (1,47) in concatMap show p

"0212765957446808510638297872340425531914893617"

ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)

540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- § Tipos                                                            --
-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------
-- § De racional a decimal                                            --
-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
--    mayorExponente 2 40  ==  3
--    mayorExponente 5 40  ==  1
--    mayorExponente 5 41  ==  0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudAnteperiodo 2   ==  1
--    longitudAnteperiodo 3   ==  0
--    longitudAnteperiodo 14  ==  1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudPeriodo 2  ==  0
--    longitudPeriodo 3  ==  1
--    longitudPeriodo 7  ==  6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
    | m == 1    = 0 
    | otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
    where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
--    parteEntera (125,3)  ==  41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
--    antePeriodo (23,14)  ==  [6]
--    antePeriodo (1,5)    ==  [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que
-- se encuentran entre la parte entera y el primer período de a/b. Por
-- ejemplo, 
--    periodo (1,3)                   ==  [3]
--    periodo (1,5)                   ==  []
--    periodo (1,7)                   ==  [1,4,2,8,5,7]
--    periodo (23,14)                 ==  [4,2,8,5,7,1]
--    concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
          t  = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo, 
--    reducido (40,80)  ==  (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m) 
    where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo, 
--    decimal (1,4)    ==  (0,[2,5],[])
--    decimal (1,3)    ==  (0,[],[3])
--    decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
    where r = reducido (a,b)

-- ---------------------------------------------------------------------
-- § De decimal a racional                                            --
-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
    where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
--    racional (0,[2,5],[])           ==  (1,4)
--    racional (0,[],[3])             ==  (1,3)
--    racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
    a = digitosAnumero (x:ys)
    b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where 
    a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
    b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------
-- § Propiedades                                                      --
-- ---------------------------------------------------------------------

-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
    a >= 0 && b > 0  ==>
    racional (decimal (a,b)) == reducido (a,b)

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

-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
                    b <- arbitrary
                    return (reducido (abs a, 1+ abs b))

-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
    forAll numeroRacional
           (\(a,b) -> racional (decimal (a,b)) == (a,b))

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

-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
                   b <- arbitrary
                   return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
    forAll numeroDecimal 
           (\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

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

-- § Librerías auxiliares --

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

import Data.List

import Test.QuickCheck

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

-- § Tipos --

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

-- Un número racional se representa por un par de enteros, donde el

-- primer elemento es el numerador y el segundo el denominador.

type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte

-- entera, el segundo es el anteperíodo y el tercero es el período.

type Decimal = (Integer,[Integer],[Integer])

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

-- § De racional a decimal --

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

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,

-- mayorExponente 2 40 == 3

-- mayorExponente 5 40 == 1

-- mayorExponente 5 41 == 0

mayorExponente :: Integer -> Integer -> Integer

mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudAnteperiodo 2 == 1

-- longitudAnteperiodo 3 == 0

-- longitudAnteperiodo 14 == 1

longitudAnteperiodo :: Integer -> Integer

longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudPeriodo 2 == 0

-- longitudPeriodo 3 == 1

-- longitudPeriodo 7 == 6

longitudPeriodo :: Integer -> Integer

longitudPeriodo n

| m == 1 = 0

| otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]

where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: Racional -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,

-- parteEntera (125,3) == 41

parteEntera :: Racional -> Integer

parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de

-- cifras que se encuentran entre la parte entera y el primer período de

-- a/b. Por ejemplo,

-- antePeriodo (23,14) == [6]

-- antePeriodo (1,5) == [2]

antePeriodo :: Racional -> [Integer]

antePeriodo (a,b) = genericTake s (tail xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que

-- se encuentran entre la parte entera y el primer período de a/b. Por

-- ejemplo,

-- periodo (1,3) == [3]

-- periodo (1,5) == []

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (23,14) == [4,2,8,5,7,1]

-- concatMap show $ periodo (1,29) == "0344827586206896551724137931"

periodo :: Racional -> [Integer]

periodo (a,b) = genericTake t (genericDrop (1+s) xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

t = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por

-- ejemplo,

-- reducido (40,80) == (1,2)

reducido :: Racional -> Racional

reducido (a,b) = (a `div` m, b `div` m)

where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna

-- formada por la parte entera, la parte decimal pura y la parte decimal

-- periódica. Por ejemplo,

-- decimal (1,4) == (0,[2,5],[])

-- decimal (1,3) == (0,[],[3])

-- decimal (23,14) == (1,[6],[4,2,8,5,7,1])

decimal :: Racional -> Decimal

decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)

where r = reducido (a,b)

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

-- § De decimal a racional --

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

-- (digitosAnumero xs) es el número correspondiente a la lista de

-- dígitos xs. Por ejemplo,

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

digitosAnumero :: [Integer] -> Integer

digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]

where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación

-- decimal es (x,ys,zs). Por ejemplo,

-- racional (0,[2,5],[]) == (1,4)

-- racional (0,[],[3]) == (1,3)

-- racional (1,[6],[4,2,8,5,7,1]) == (23,14)

racional :: Decimal -> Racional

racional (x,ys,[]) = reducido (a,b) where

a = digitosAnumero (x:ys)

b = 10^(length ys)

racional (x,ys,zs) = reducido (a,b) where

a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)

b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

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

-- § Propiedades --

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

-- La 1ª propiedad es

prop_RacionalDecimal :: Racional -> Property

prop_RacionalDecimal (a,b) =

a >= 0 && b > 0 ==>

racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal

-- +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales

numeroRacional :: Gen Racional

numeroRacional = do a <- arbitrary

b <- arbitrary

return (reducido (abs a, 1+ abs b))

-- La propiedad es

prop_RacionalDecimal2 :: Property

prop_RacionalDecimal2 =

forAll numeroRacional

(\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal2

-- +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales

numeroDecimal :: Gen Decimal

numeroDecimal = do a <- arbitrary

b <- arbitrary

return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es

prop_DecimalRacional :: Property

prop_DecimalRacional =

forAll numeroDecimal

(\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es

-- ghci> quickCheck prop_DecimalRacional

-- +++ OK, passed 100 tests.

Evaluación de expresiones aritméticas

PorJosé A. Alonso 29-marzo-201626-marzo-2022

Las expresiones aritméticas se pueden definir mediante el siguiente tipo de dato

   data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr 
                deriving Show

1 2	data Expr = N Int \| V Char \| Sum Expr Expr \| Mul Expr Expr deriving Show

Por ejemplo, (x+3)+(7*y) se representa por

   ejExpr :: Expr
   ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

1 2	ejExpr :: Expr ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

Definir la función

   valor :: Expr -> Maybe Int

1	valor :: Expr -> Maybe Int

tal que (valor e) es ‘Just v’ si la expresión e es numérica y v es su valor, o bien ‘Nothing’ si e no es numérica. Por ejemplo:

   valor (Sum (N 7) (N 9))                            == Just 16
   valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing
   valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2)))     == Just 18

valor (Sum (N 7) (N 9)) == Just 16

valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing

valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2))) == Just 18

Soluciones

data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr 
             deriving Show

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

valor1 :: Expr -> Maybe Int
valor1 e | null (aux e) = Nothing
         | otherwise    = Just (head (aux e))
    where aux (N x)       = [x]
          aux (V _)       = []
          aux (Sum e1 e2) = [x+y| x <- aux e1, y <- aux e2]
          aux (Mul e1 e2) = [x*y| x <- aux e1, y <- aux e2]

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

valor2 :: Expr -> Maybe Int
valor2 e | numerico e = Just (aux e)
         | otherwise  = Nothing
    where aux (N x)       = x
          aux (Sum e1 e2) = aux e1 + aux e2
          aux (Mul e1 e2) = aux e1 * aux e2

numerico :: Expr -> Bool
numerico (N _)       = True
numerico (V _)       = False
numerico (Sum e1 e2) = numerico e1 && numerico e2
numerico (Mul e1 e2) = numerico e1 && numerico e2

data Expr = N Int | V Char | Sum Expr Expr | Mul Expr Expr

deriving Show

-- 1ª solución

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

valor1 :: Expr -> Maybe Int

valor1 e | null (aux e) = Nothing

| otherwise = Just (head (aux e))

where aux (N x) = [x]

aux (V _) = []

aux (Sum e1 e2) = [x+y| x <- aux e1, y <- aux e2]

aux (Mul e1 e2) = [x*y| x <- aux e1, y <- aux e2]

-- 2ª solución

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

valor2 :: Expr -> Maybe Int

valor2 e | numerico e = Just (aux e)

| otherwise = Nothing

where aux (N x) = x

aux (Sum e1 e2) = aux e1 + aux e2

aux (Mul e1 e2) = aux e1 * aux e2

numerico :: Expr -> Bool

numerico (N _) = True

numerico (V _) = False

numerico (Sum e1 e2) = numerico e1 && numerico e2

numerico (Mul e1 e2) = numerico e1 && numerico e2

Máxima suma de elementos consecutivos

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

Definir la función

   sumaMaxima :: [Integer] -> Integer

1	sumaMaxima :: [Integer] -> Integer

tal que (sumaMaxima xs) es el valor máximo de la suma de elementos consecutivos de la lista xs. Por ejemplo,

   sumaMaxima []             ==  0 
   sumaMaxima [2,-2,3,-3,4]  ==  4
   sumaMaxima [-1,-2,-3]     ==  0
   sumaMaxima [2,-1,3,-2,3]  ==  5
   sumaMaxima [1,-1,3,-2,4]  ==  5
   sumaMaxima [2,-1,3,-2,4]  ==  6
   sumaMaxima [1..10^6]      ==  500000500000

sumaMaxima [] == 0

sumaMaxima [2,-2,3,-3,4] == 4

sumaMaxima [-1,-2,-3] == 0

sumaMaxima [2,-1,3,-2,3] == 5

sumaMaxima [1,-1,3,-2,4] == 5

sumaMaxima [2,-1,3,-2,4] == 6

sumaMaxima [1..10^6] == 500000500000

Comprobar con QuickCheck que

   sumaMaxima xs == sumaMaxima (reverse xs)

1	sumaMaxima xs == sumaMaxima (reverse xs)

Soluciones

import Data.List (inits, tails)
import Test.QuickCheck

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

sumaMaxima1 :: [Integer] -> Integer
sumaMaxima1 [] = 0
sumaMaxima1 xs =
    maximum (0 : map sum [sublista xs i j | i <- [0..length xs - 1],
                                            j <- [i..length xs - 1]])

sublista :: [Integer] -> Int -> Int -> [Integer]
sublista xs i j =
    [xs!!k | k <- [i..j]]

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

sumaMaxima2 :: [Integer] -> Integer
sumaMaxima2 [] = 0
sumaMaxima2 xs = sumaMaximaAux 0 0 xs
    where m = maximum xs

sumaMaximaAux :: Integer -> Integer -> [Integer] -> Integer
sumaMaximaAux m v [] = max m v
sumaMaximaAux m v (x:xs)
    | x >= 0    = sumaMaximaAux m (v+x) xs
    | v+x > 0   = sumaMaximaAux (max m v) (v+x) xs
    | otherwise = sumaMaximaAux (max m v) 0 xs

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

sumaMaxima3 :: [Integer] -> Integer
sumaMaxima3 [] = 0
sumaMaxima3 xs = maximum (map sum (segmentos xs))

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo 
--    segmentos "abc"  ==  ["", "a","ab","abc","b","bc","c"]
segmentos :: [a] -> [[a]]
segmentos xs =
    [] : concat [tail (inits ys) | ys <- init (tails xs)]

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

sumaMaxima4 :: [Integer] -> Integer
sumaMaxima4 [] = 0
sumaMaxima4 xs = 
    maximum (concat [scanl (+) 0 ys | ys <- tails xs])

-- Comprobación
-- ============

-- La propiedad es
prop_sumaMaxima :: [Integer] -> Bool
prop_sumaMaxima xs =
    sumaMaxima2 xs == n &&
    sumaMaxima3 xs == n &&
    sumaMaxima4 xs == n
    where n = sumaMaxima1 xs

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

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

--    λ> let n = 10^2 in sumaMaxima1 [-n..n] 
--    5050
--    (2.10 secs, 390,399,104 bytes)
--    λ> let n = 10^2 in sumaMaxima2 [-n..n] 
--    5050
--    (0.02 secs, 0 bytes)
--    λ> let n = 10^2 in sumaMaxima3 [-n..n] 
--    5050
--    (0.27 secs, 147,705,184 bytes)
--    λ> let n = 10^2 in sumaMaxima4 [-n..n] 
--    5050
--    (0.04 secs, 11,582,520 bytes)

prop_inversa :: [Integer] -> Bool
prop_inversa xs =
    sumaMaxima2 xs == sumaMaxima2 (reverse xs)

import Data.List (inits, tails)

import Test.QuickCheck

-- 1ª definición

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

sumaMaxima1 :: [Integer] -> Integer

sumaMaxima1 [] = 0

sumaMaxima1 xs =

maximum (0 : map sum [sublista xs i j | i <- [0..length xs - 1],

j <- [i..length xs - 1]])

sublista :: [Integer] -> Int -> Int -> [Integer]

sublista xs i j =

[xs!!k | k <- [i..j]]

-- 2ª definición

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

sumaMaxima2 :: [Integer] -> Integer

sumaMaxima2 [] = 0

sumaMaxima2 xs = sumaMaximaAux 0 0 xs

where m = maximum xs

sumaMaximaAux :: Integer -> Integer -> [Integer] -> Integer

sumaMaximaAux m v [] = max m v

sumaMaximaAux m v (x:xs)

| x >= 0 = sumaMaximaAux m (v+x) xs

| v+x > 0 = sumaMaximaAux (max m v) (v+x) xs

| otherwise = sumaMaximaAux (max m v) 0 xs

-- 3ª definición

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

sumaMaxima3 :: [Integer] -> Integer

sumaMaxima3 [] = 0

sumaMaxima3 xs = maximum (map sum (segmentos xs))

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo

-- segmentos "abc" == ["", "a","ab","abc","b","bc","c"]

segmentos :: [a] -> [[a]]

segmentos xs =

[] : concat [tail (inits ys) | ys <- init (tails xs)]

-- 4ª definición

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

sumaMaxima4 :: [Integer] -> Integer

sumaMaxima4 [] = 0

sumaMaxima4 xs =

maximum (concat [scanl (+) 0 ys | ys <- tails xs])

-- Comprobación

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

-- La propiedad es

prop_sumaMaxima :: [Integer] -> Bool

prop_sumaMaxima xs =

sumaMaxima2 xs == n &&

sumaMaxima3 xs == n &&

sumaMaxima4 xs == n

where n = sumaMaxima1 xs

-- La comprobación es

-- λ> quickCheck prop_sumaMaxima

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> let n = 10^2 in sumaMaxima1 [-n..n]

-- 5050

-- (2.10 secs, 390,399,104 bytes)

-- λ> let n = 10^2 in sumaMaxima2 [-n..n]

-- 5050

-- (0.02 secs, 0 bytes)

-- λ> let n = 10^2 in sumaMaxima3 [-n..n]

-- 5050

-- (0.27 secs, 147,705,184 bytes)

-- λ> let n = 10^2 in sumaMaxima4 [-n..n]

-- 5050

-- (0.04 secs, 11,582,520 bytes)

prop_inversa :: [Integer] -> Bool

prop_inversa xs =

sumaMaxima2 xs == sumaMaxima2 (reverse xs)

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)

Máxima suma en una matriz

PorJosé A. Alonso 11-marzo-201628-marzo-2016

Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales:

   type Matriz = Array (Int,Int) Int

1	type Matriz = Array (Int,Int) Int

Definir la función

   maximaSuma :: Matriz -> Int

1	maximaSuma :: Matriz -> Int

tal que (maximaSuma p) es el máximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece sólo a una fila y a una columna. Por ejemplo,

   ghci> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
   17

1 2	ghci> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7]) 17

ya que las selecciones, y sus sumas, de la matriz

   |1 2 3|
   |8 4 9|
   |5 6 7|

|1 2 3|

|8 4 9|

|5 6 7|

son

   [1,4,7] --> 12
   [1,9,6] --> 16
   [2,8,7] --> 17
   [2,9,5] --> 16
   [3,8,6] --> 17
   [3,4,5] --> 12

[1,4,7] --> 12

[1,9,6] --> 16

[2,8,7] --> 17

[2,9,5] --> 16

[3,8,6] --> 17

[3,4,5] --> 12

Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].

Soluciones

import Data.Array
import Data.List (permutations)

type Matriz = Array (Int,Int) Int

maximaSuma :: Matriz -> Int
maximaSuma p = maximum [sum xs | xs <- selecciones p]

-- (selecciones p) es la lista de las selecciones en las que cada
-- elemento pertenece a un única fila y a una única columna de la matriz
-- p. Por ejemplo,
--    ghci> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
--    [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]]
selecciones :: Matriz -> [[Int]]
selecciones p = 
    [[p!(i,j) | (i,j) <- ijs] | 
     ijs <- [zip [1..n] xs | xs <- permutations [1..n]]] 
    where (_,(m,n)) = bounds p

-- 2ª solución (mediante submatrices):
maximaSuma2 :: Matriz -> Int
maximaSuma2 p 
    | (m,n) == (1,1) = p!(1,1)
    | otherwise = maximum [p!(1,j) 
                  + maximaSuma2 (submatriz 1 j p) | j <- [1..n]]
    where (_,(m,n)) = bounds p

-- (submatriz i j p) es la matriz obtenida a partir de la p eliminando
-- la fila i y la columna j. Por ejemplo, 
--    ghci> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
--    array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)]
submatriz :: Int -> Int -> Matriz -> Matriz
submatriz i j p = 
    array ((1,1), (m-1,n -1))
          [((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]]
    where (_,(m,n)) = bounds p
          f k l | k < i  && l < j  = (k,l)
                | k >= i && l < j  = (k+1,l)
                | k < i  && l >= j = (k,l+1)
                | otherwise        = (k+1,l+1)

import Data.Array

import Data.List (permutations)

type Matriz = Array (Int,Int) Int

maximaSuma :: Matriz -> Int

maximaSuma p = maximum [sum xs | xs <- selecciones p]

-- (selecciones p) es la lista de las selecciones en las que cada

-- elemento pertenece a un única fila y a una única columna de la matriz

-- p. Por ejemplo,

-- ghci> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])

-- [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]]

selecciones :: Matriz -> [[Int]]

selecciones p =

[[p!(i,j) | (i,j) <- ijs] |

ijs <- [zip [1..n] xs | xs <- permutations [1..n]]]

where (_,(m,n)) = bounds p

-- 2ª solución (mediante submatrices):

maximaSuma2 :: Matriz -> Int

maximaSuma2 p

| (m,n) == (1,1) = p!(1,1)

| otherwise = maximum [p!(1,j)

+ maximaSuma2 (submatriz 1 j p) | j <- [1..n]]

where (_,(m,n)) = bounds p

-- (submatriz i j p) es la matriz obtenida a partir de la p eliminando

-- la fila i y la columna j. Por ejemplo,

-- ghci> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])

-- array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)]

submatriz :: Int -> Int -> Matriz -> Matriz

submatriz i j p =

array ((1,1), (m-1,n -1))

[((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]]

where (_,(m,n)) = bounds p

f k l | k < i && l < j = (k,l)

| k >= i && l < j = (k+1,l)

| k < i && l >= j = (k,l+1)

| otherwise = (k+1,l+1)

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Referencia

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencia

Soluciones

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones en Maxima

Soluciones

Soluciones en Maxima

Soluciones

Solución en Maxima

Referencia

Soluciones

Solución en Maxima

Soluciones

Solución en Maxima

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico