Recursión – Página 9

Exponentes de Hamming

PorJosé A. Alonso 1-febrero-20188-febrero-2018

Los números de Hamming forman una sucesión estrictamente creciente de números que cumplen las siguientes condiciones:

El número 1 está en la sucesión.
Si x está en la sucesión, entonces 2x, 3x y 5x también están.
Ningún otro número está en la sucesión.

Los primeros números de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, …

Los exponentes de un número de Hamming n es una terna (x,y,z) tal que n = 2^x*3^y*5^z. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z.

Definir la sucesión

   sucExponentesHamming :: [(Int,Int,Int)]

1	sucExponentesHamming :: [(Int,Int,Int)]

cuyos elementos son los exponentes de los números de Hamming. Por ejemplo,

   λ> take 21 sucExponentesHamming
   [(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),
    (0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),
    (3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]
   λ> sucExponentesHamming !! (5*10^5)
   (74,82,7)

λ> take 21 sucExponentesHamming

[(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),

(0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),

(3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]

λ> sucExponentesHamming !! (5*10^5)

(74,82,7)

Soluciones

import Data.Numbers.Primes (primeFactors)

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

sucExponentesHamming :: [(Int,Int,Int)]
sucExponentesHamming = map exponentes hamming

-- (exponentes n) es la terna de exponentes del número de Hamming n. Por
-- ejemplo, 
--    exponentes 600  ==  (3,1,2)
exponentes :: Integer -> (Int,Int,Int)
exponentes x = (length as, length cs, length ds)
  where xs = primeFactors x
        (as,bs) = span (==2) xs
        (cs,ds) = span (==3) bs

-- hamming es la sucesión de los números de Hamming. Por ejemplo,
--    λ> take 21 hamming
--    [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40]
hamming :: [Integer]
hamming = 1 : mezcla3 [2*i | i <- hamming]  
                      [3*i | i <- hamming]  
                      [5*i | i <- hamming]  

-- mezcla3 xs ys zs es la lista obtenida mezclando las listas ordenadas
-- xs, ys y zs y eliminando los elementos duplicados. Por ejemplo, 
--    mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]  ==  [2,3,4,5,6,8,9,10,12]
mezcla3 :: Ord a => [a] -> [a] -> [a] -> [a]
mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)  

-- mezcla2 xs ys zs es la lista obtenida mezclando las listas ordenadas
-- xs e ys y eliminando los elementos duplicados. Por ejemplo, 
--    mezcla2 [2,4,6,8,10,12] [3,6,9,12]  ==  [2,3,4,6,8,9,10,12]
mezcla2 :: Ord a => [a] -> [a] -> [a] 
mezcla2 p@(x:xs) q@(y:ys) | x < y     = x:mezcla2 xs q
                          | x > y     = y:mezcla2 p  ys  
                          | otherwise = x:mezcla2 xs ys
mezcla2 []       ys                   = ys
mezcla2 xs       []                   = xs

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

sucExponentesHamming2 :: [(Int,Int,Int)]
sucExponentesHamming2 = map exponentes2 hamming

exponentes2 :: Integer -> (Int,Int,Int)
exponentes2 = aux (0,0,0)
  where aux (a,b,c) 1 = (a,b,c)
        aux (a,b,c) x | mod x 2 == 0 = aux (a+1,b,c) (div x 2)
                      | mod x 3 == 0 = aux (a,b+1,c) (div x 3)
                      | otherwise    = aux (a,b,c+1) (div x 5)

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

sucExponentesHamming3 :: [(Int,Int,Int)]
sucExponentesHamming3 = map exponentes3 hamming

exponentes3 :: Integer -> (Int,Int,Int)
exponentes3 1 = (0,0,0)
exponentes3 x
  | x `mod` 2 == 0 = suma (1,0,0) (descomposicion (x `div` 2))
  | x `mod` 3 == 0 = suma (0,1,0) (descomposicion (x `div` 3))
  | otherwise      = suma (0,0,1) (descomposicion (x `div` 5))
  where suma (x,y,z) (a,b,c) = (x+a,y+b,z+c)

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

type Terna = (Int,Int,Int)

sucExponentesHamming4 :: [Terna]
sucExponentesHamming4 =
  (0,0,0) : mezclaT3 [(x+1,y,z) | (x,y,z) <- sucExponentesHamming4]
                     [(x,y+1,z) | (x,y,z) <- sucExponentesHamming4]
                     [(x,y,z+1) | (x,y,z) <- sucExponentesHamming4]
 
mezclaT3 :: [Terna] -> [Terna] -> [Terna] -> [Terna]
mezclaT3 t1 t2 t3 = mezclaT2 t1 (mezclaT2 t2 t3)

mezclaT2 :: [Terna] -> [Terna] -> [Terna]
mezclaT2 ts1@((i,j,k):xs) ts2@((a,b,c):ys)
  | x < y     = (i,j,k) : mezclaT2 xs ts2
  | x > y     = (a,b,c) : mezclaT2 ts1 ys
  | otherwise = (i,j,k) : mezclaT2 xs ys
  where x = 2^i*3^j*5^k
        y = 2^a*3^b*5^c

import Data.Numbers.Primes (primeFactors)

-- 1ª solución

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

sucExponentesHamming :: [(Int,Int,Int)]

sucExponentesHamming = map exponentes hamming

-- (exponentes n) es la terna de exponentes del número de Hamming n. Por

-- ejemplo,

-- exponentes 600 == (3,1,2)

exponentes :: Integer -> (Int,Int,Int)

exponentes x = (length as, length cs, length ds)

where xs = primeFactors x

(as,bs) = span (==2) xs

(cs,ds) = span (==3) bs

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

-- λ> take 21 hamming

-- [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40]

hamming :: [Integer]

hamming = 1 : mezcla3 [2*i | i <- hamming]

[3*i | i <- hamming]

[5*i | i <- hamming]

-- mezcla3 xs ys zs es la lista obtenida mezclando las listas ordenadas

-- xs, ys y zs y eliminando los elementos duplicados. Por ejemplo,

-- mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10] == [2,3,4,5,6,8,9,10,12]

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

mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)

-- mezcla2 xs ys zs es la lista obtenida mezclando las listas ordenadas

-- xs e ys y eliminando los elementos duplicados. Por ejemplo,

-- mezcla2 [2,4,6,8,10,12] [3,6,9,12] == [2,3,4,6,8,9,10,12]

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

mezcla2 p@(x:xs) q@(y:ys) | x < y = x:mezcla2 xs q

| x > y = y:mezcla2 p ys

| otherwise = x:mezcla2 xs ys

mezcla2 [] ys = ys

mezcla2 xs [] = xs

-- 2ª solución

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

sucExponentesHamming2 :: [(Int,Int,Int)]

sucExponentesHamming2 = map exponentes2 hamming

exponentes2 :: Integer -> (Int,Int,Int)

exponentes2 = aux (0,0,0)

where aux (a,b,c) 1 = (a,b,c)

aux (a,b,c) x | mod x 2 == 0 = aux (a+1,b,c) (div x 2)

| mod x 3 == 0 = aux (a,b+1,c) (div x 3)

| otherwise = aux (a,b,c+1) (div x 5)

-- 3ª solución

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

sucExponentesHamming3 :: [(Int,Int,Int)]

sucExponentesHamming3 = map exponentes3 hamming

exponentes3 :: Integer -> (Int,Int,Int)

exponentes3 1 = (0,0,0)

exponentes3 x

| x `mod` 2 == 0 = suma (1,0,0) (descomposicion (x `div` 2))

| x `mod` 3 == 0 = suma (0,1,0) (descomposicion (x `div` 3))

| otherwise = suma (0,0,1) (descomposicion (x `div` 5))

where suma (x,y,z) (a,b,c) = (x+a,y+b,z+c)

-- 4ª solución

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

type Terna = (Int,Int,Int)

sucExponentesHamming4 :: [Terna]

sucExponentesHamming4 =

(0,0,0) : mezclaT3 [(x+1,y,z) | (x,y,z) <- sucExponentesHamming4]

[(x,y+1,z) | (x,y,z) <- sucExponentesHamming4]

[(x,y,z+1) | (x,y,z) <- sucExponentesHamming4]

mezclaT3 :: [Terna] -> [Terna] -> [Terna] -> [Terna]

mezclaT3 t1 t2 t3 = mezclaT2 t1 (mezclaT2 t2 t3)

mezclaT2 :: [Terna] -> [Terna] -> [Terna]

mezclaT2 ts1@((i,j,k):xs) ts2@((a,b,c):ys)

| x < y = (i,j,k) : mezclaT2 xs ts2

| x > y = (a,b,c) : mezclaT2 ts1 ys

| otherwise = (i,j,k) : mezclaT2 xs ys

where x = 2^i*3^j*5^k

y = 2^a*3^b*5^c

Recorrido del robot

PorJosé A. Alonso 31-enero-20187-febrero-2018

Los puntos de una retícula se representan mediante pares de enteros

   type Punto = (Int,Int)

1	type Punto = (Int,Int)

y los movimientos de un robot mediante el tipo

   data Movimiento = N Int
                   | S Int
                   | E Int
                   | O Int

data Movimiento = N Int

| S Int

| E Int

| O Int

donde (N x) significa que se mueve x unidades en la dirección norte y análogamente para las restantes direcciones (S es sur, E es este y O es oeste).

Definir la función

   posicion :: [Movimiento] -> Punto

1	posicion :: [Movimiento] -> Punto

tal que (posicion ms) es la posición final de un robot que inicialmente está en el el punto (0,0) y realiza los movimientos ms. Por ejemplo,

   posicion [N 3]                           ==  (0,3)
   posicion [N 3, E 5]                      ==  (5,3)
   posicion [N 3, E 5, S 1]                 ==  (5,2)
   posicion [N 3, E 5, S 1, O 4]            ==  (1,2)
   posicion [N 3, E 5, S 1, O 4, N 3]       ==  (1,5)
   posicion [N 3, E 5, S 1, O 4, N 3, S 3]  ==  (1,2)

posicion [N 3] == (0,3)

posicion [N 3, E 5] == (5,3)

posicion [N 3, E 5, S 1] == (5,2)

posicion [N 3, E 5, S 1, O 4] == (1,2)

posicion [N 3, E 5, S 1, O 4, N 3] == (1,5)

posicion [N 3, E 5, S 1, O 4, N 3, S 3] == (1,2)

Soluciones

type Punto = (Int,Int)

data Movimiento = N Int
                | S Int
                | E Int
                | O Int

-- 1ª solución                
posicion :: [Movimiento] -> Punto
posicion ms = aux ms (0,0)
  where aux [] p = p
        aux (N x:ms) (a,b) = aux ms (a,b+x)
        aux (S x:ms) (a,b) = aux ms (a,b-x)
        aux (E x:ms) (a,b) = aux ms (a+x,b)
        aux (O x:ms) (a,b) = aux ms (a-x,b)

-- 2ª solución
posicion2 :: [Movimiento] -> Punto
posicion2 []       = (0,0)
posicion2 (N x:ms) = suma (0 ,x)  (posicion2 ms)
posicion2 (S x:ms) = suma (0 ,-x) (posicion2 ms)
posicion2 (E x:ms) = suma (x ,0)  (posicion2 ms)
posicion2 (O x:ms) = suma (-x,0)  (posicion2 ms)

suma :: Punto -> Punto -> Punto
suma (x,y) (a,b) = (x+a,y+b)

-- 3ª solución
posicion3 :: [Movimiento] -> Punto
posicion3 []     = (0,0)
posicion3 (m:ms) = case m of
                     N x -> (a,b+x)
                     S x -> (a,b-x)
                     E x -> (a+x,b)
                     O x -> (a-x,b)
  where (a,b) = posicion3 ms

-- 4ª solución
posicion4 :: [Movimiento] -> Punto
posicion4 = foldl aux (0,0)
  where
    aux (x,y) (N j) = (x,y+j)
    aux (x,y) (S j) = (x,y-j)
    aux (x,y) (E i) = (x+i,y)
    aux (x,y) (O i) = (x-i,y)

--- 5ª solución
posicion5 :: [Movimiento] -> Punto
posicion5 xs = (sum hs, sum vs)
  where
    (hs,vs)   = unzip (map aux xs)
    aux (N j) = (0,j)
    aux (S j) = (0,-j)
    aux (E i) = (i,0)
    aux (O i) = (-i,0)

type Punto = (Int,Int)

data Movimiento = N Int

| S Int

| E Int

| O Int

-- 1ª solución

posicion :: [Movimiento] -> Punto

posicion ms = aux ms (0,0)

where aux [] p = p

aux (N x:ms) (a,b) = aux ms (a,b+x)

aux (S x:ms) (a,b) = aux ms (a,b-x)

aux (E x:ms) (a,b) = aux ms (a+x,b)

aux (O x:ms) (a,b) = aux ms (a-x,b)

-- 2ª solución

posicion2 :: [Movimiento] -> Punto

posicion2 [] = (0,0)

posicion2 (N x:ms) = suma (0 ,x) (posicion2 ms)

posicion2 (S x:ms) = suma (0 ,-x) (posicion2 ms)

posicion2 (E x:ms) = suma (x ,0) (posicion2 ms)

posicion2 (O x:ms) = suma (-x,0) (posicion2 ms)

suma :: Punto -> Punto -> Punto

suma (x,y) (a,b) = (x+a,y+b)

-- 3ª solución

posicion3 :: [Movimiento] -> Punto

posicion3 [] = (0,0)

posicion3 (m:ms) = case m of

N x -> (a,b+x)

S x -> (a,b-x)

E x -> (a+x,b)

O x -> (a-x,b)

where (a,b) = posicion3 ms

-- 4ª solución

posicion4 :: [Movimiento] -> Punto

posicion4 = foldl aux (0,0)

where

aux (x,y) (N j) = (x,y+j)

aux (x,y) (S j) = (x,y-j)

aux (x,y) (E i) = (x+i,y)

aux (x,y) (O i) = (x-i,y)

--- 5ª solución

posicion5 :: [Movimiento] -> Punto

posicion5 xs = (sum hs, sum vs)

where

(hs,vs) = unzip (map aux xs)

aux (N j) = (0,j)

aux (S j) = (0,-j)

aux (E i) = (i,0)

aux (O i) = (-i,0)

Relaciones arbóreas

PorJosé A. Alonso 30-enero-20186-febrero-2018

Como se explica en el ejercicio Relación definida por un árbol, cada árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y.

Una relación binaria es arbórea si

hay exactamente un elemento que no tiene ningún (la raíz del árbol) y
todos los elementos tienen dos hijos (los nodos internos) o ninguno (las hojas del árbol).

Definir la función

   arborea :: Eq a => [(a,a)] -> Bool

1	arborea :: Eq a => [(a,a)] -> Bool

tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,

   arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]  ==  True
   arborea [(8,3),(8,5),(10,2),(2,2),(2,0)]         ==  False
   arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)]  ==  False

arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] == True

arborea [(8,3),(8,5),(10,2),(2,2),(2,0)] == False

arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)] == False

Soluciones

import Data.List ((\\), elemIndices, isPrefixOf, nub, sort)

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

arborea :: Eq a => [(a,a)] -> Bool
arborea r =
  length [x | x <- nodos r, null (padres r x)] == 1 &&
  all (`elem` [0,2]) [length (hijos r x) | x <- nodos r]

-- (nodos r) es el conjunto de los nodos de la relación r. Por ejemplo,   
--    λ> nodos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
--    [10,8,3,5,2,0]
nodos :: Eq a => [(a,a)] -> [a]
nodos r = nub (concat [[x,y] | (x,y) <- r])

-- (padres r x) es la lista de los padres de x en la relación r. Por
-- ejemplo, 
--    padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 8   ==  [10]
--    padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10  ==  []
padres :: Eq a => [(a,a)] -> a -> [a]
padres r x = [y | (y,x') <- r, x' == x]

-- (hijos r x) es la lista de los hijos de x en la relación r. Por
-- ejemplo, 
--    hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10  ==  [8,2]
--    hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 5   ==  []
hijos :: Eq a => [(a,a)] -> a -> [a]
hijos r x = [y | (x',y) <- r, x' == x]

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

arborea2 :: Eq a => [(a,a)] -> Bool
arborea2 xs =  length (nub padres \\ nub hijos) == 1
            && and [cuenta x padres == 2 | x <- nub padres]
  where
    (padres, hijos) = unzip xs

-- (cuenta x ys) es el número de ocurrencias de x en ys. Por ejemplo,
--    cuenta 7 [7,2,7,7,5]  ==  3
cuenta :: Eq a => a -> [a] -> Int
cuenta i = length . elemIndices i

import Data.List ((\\), elemIndices, isPrefixOf, nub, sort)

-- 1ª solución

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

arborea :: Eq a => [(a,a)] -> Bool

arborea r =

length [x | x <- nodos r, null (padres r x)] == 1 &&

all (`elem` [0,2]) [length (hijos r x) | x <- nodos r]

-- (nodos r) es el conjunto de los nodos de la relación r. Por ejemplo,

-- λ> nodos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]

-- [10,8,3,5,2,0]

nodos :: Eq a => [(a,a)] -> [a]

nodos r = nub (concat [[x,y] | (x,y) <- r])

-- (padres r x) es la lista de los padres de x en la relación r. Por

-- ejemplo,

-- padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 8 == [10]

-- padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10 == []

padres :: Eq a => [(a,a)] -> a -> [a]

padres r x = [y | (y,x') <- r, x' == x]

-- (hijos r x) es la lista de los hijos de x en la relación r. Por

-- ejemplo,

-- hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10 == [8,2]

-- hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 5 == []

hijos :: Eq a => [(a,a)] -> a -> [a]

hijos r x = [y | (x',y) <- r, x' == x]

-- 2ª solución

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

arborea2 :: Eq a => [(a,a)] -> Bool

arborea2 xs = length (nub padres \\ nub hijos) == 1

&& and [cuenta x padres == 2 | x <- nub padres]

where

(padres, hijos) = unzip xs

-- (cuenta x ys) es el número de ocurrencias de x en ys. Por ejemplo,

-- cuenta 7 [7,2,7,7,5] == 3

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

cuenta i = length . elemIndices i

Máxima distancia en árbol

PorJosé A. Alonso 29-enero-20185-febrero-2018

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

         10
        /  \
       /    \
      8      1
     / \    / \
    3   9  2   6

/ \

8 1

/ \ / \

3 9 2 6

se puede representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 9))
                  (N 1 (H 2) (H 6))

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 9))

(N 1 (H 2) (H 6))

La distancia entre un padre y un hijo en el árbol es el valor absoluto de la diferencia de sus valores. Por ejemplo, la distancia de 10 a 8 es 2 y de 1 a 6 es 5.

Definir la función

   maximaDistancia :: (Num a, Ord a) => Arbol a -> a

1	maximaDistancia :: (Num a, Ord a) => Arbol a -> a

tal que (maximaDistancia a) es la máxima distancia entre un padre y un hijo del árbol a. Por ejemplo,

   maximaDistancia ejArbol                                     ==  9
   maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1  (H 2) (H 6)))  ==  7
   maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6)))  ==  8

maximaDistancia ejArbol == 9

maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1 (H 2) (H 6))) == 7

maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6))) == 8

Soluciones

[schedule expon=’2018-02-05′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 05 de febrero.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2018-02-05′ at=»06:00″]

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

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 9))
               (N 1 (H 2) (H 6))


maximaDistancia :: (Num a, Ord a) => Arbol a -> a
maximaDistancia (H _)     = 0
maximaDistancia (N x i d) = maximum [abs (x - raiz i)
                                    , maximaDistancia i
                                    , abs (x - raiz d)
                                    , maximaDistancia d]
                             
raiz :: Arbol a -> a
raiz (H x)     = x
raiz (N x _ _) = x

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 9))

(N 1 (H 2) (H 6))

maximaDistancia :: (Num a, Ord a) => Arbol a -> a

maximaDistancia (H _) = 0

maximaDistancia (N x i d) = maximum [abs (x - raiz i)

, maximaDistancia i

, abs (x - raiz d)

, maximaDistancia d]

raiz :: Arbol a -> a

raiz (H x) = x

raiz (N x _ _) = x

[/schedule]

Relación definida por un árbol

PorJosé A. Alonso 26-enero-20182-febrero-2018

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

         10
        /  \
       /    \
      8      2
     / \    / \
    3   5  2   0

/ \

8 2

/ \ / \

3 5 2 0

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 5))
                  (N 2 (H 2) (H 0))

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 5))

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

Un árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y. Por ejemplo, la relación definida por el árbol anterior es [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)].

Definir la función

   relacionDelArbol :: Arbol a -> [(a,a)]

1	relacionDelArbol :: Arbol a -> [(a,a)]

tal que (relacionDelArbol a) es la relación binaria definida por el árbol a. Por ejemplo,

   λ> relacionDelArbol ejArbol
   [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
   λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))
   [(10,8),(10,2),(2,2),(2,0)]
   λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))
   [(10,8),(8,3),(8,5),(10,2)]
   λ> relacionDelArbol (H 10)
   []

λ> relacionDelArbol ejArbol

[(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]

λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))

[(10,8),(10,2),(2,2),(2,0)]

λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))

[(10,8),(8,3),(8,5),(10,2)]

λ> relacionDelArbol (H 10)

[]

Soluciones

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

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 5))
               (N 2 (H 2) (H 0))

relacionDelArbol :: Arbol a -> [(a,a)]
relacionDelArbol (H _)     = []
relacionDelArbol (N x i d) = ((x,raiz i) : relacionDelArbol i) ++ 
                             ((x,raiz d) : relacionDelArbol d)
                             
raiz :: Arbol a -> a
raiz (H x)     = x
raiz (N x _ _) = x

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 5))

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

relacionDelArbol :: Arbol a -> [(a,a)]

relacionDelArbol (H _) = []

relacionDelArbol (N x i d) = ((x,raiz i) : relacionDelArbol i) ++

((x,raiz d) : relacionDelArbol d)

raiz :: Arbol a -> a

raiz (H x) = x

raiz (N x _ _) = x

Sucesión de Lichtenberg

PorJosé A. Alonso 25-enero-20181-febrero-2018

La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados Los primeros términos de ambas sucesiones son

   Alternada ..... Lichtenberg
   0 ....................... 0
   1 ....................... 1
   10 ...................... 2
   101 ..................... 5
   1010 ................... 10
   10101 .................. 21
   101010 ................. 42
   1010101 ................ 85
   10101010 .............. 170
   101010101 ............. 341
   1010101010 ............ 682
   10101010101 .......... 1365
   101010101010 ......... 2730

Alternada ..... Lichtenberg

0 ....................... 0

1 ....................... 1

10 ...................... 2

101 ..................... 5

1010 ................... 10

10101 .................. 21

101010 ................. 42

1010101 ................ 85

10101010 .............. 170

101010101 ............. 341

1010101010 ............ 682

10101010101 .......... 1365

101010101010 ......... 2730

Definir las funciones

   lichtenberg        :: [Integer]
   graficaLichtenberg :: Int -> IO ()

1 2	lichtenberg :: [Integer] graficaLichtenberg :: Int -> IO ()

tales que

lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo,

     λ> take 17 lichtenberg
     [0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690]

1 2	λ> take 17 lichtenberg [0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690]

(graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja

Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.

Soluciones

import Data.Char (digitToInt)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
import Data.Numbers.Primes (isPrime)

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

lichtenberg1 :: [Integer]
lichtenberg1 = map binarioAdecimal sucAlternada

-- sucAlternada es la lista cuyos elementos son los términos de la
-- sucesión de los dígitos 0 y 1 alternados. Por ejemplo,
--    λ> take 7 sucAlternada
--    ["0","1","10","101","1010","10101","101010"]
sucAlternada :: [String]
sucAlternada =
  ['0'] : [take n cadenaAlternada | n <- [1..]]

-- cadenaAltenada es la cadena formada alternando los caracteres 1 y
-- 0. Por ejemplo,
--    take 20 cadenaAlternada  ==  "10101010101010101010"
cadenaAlternada :: String
cadenaAlternada = cycle ['1','0']

-- (binarioAdecimal cs) es el número decimal correspondiente al número
-- binario cuya cadena de dígitos es cs. Por ejemplo,
--    binarioAdecimal "11101"  ==  29
binarioAdecimal :: String -> Integer
binarioAdecimal =
  foldl (\acc x -> acc * 2 + (toInteger . digitToInt) x) 0
  
-- 2ª solución
lichtenberg2 :: [Integer]
lichtenberg2 = map a [0..]
  where a 0 = 0
        a 1 = 1
        a n = a (n-1) + 2 * a (n-2) + 1

-- 3ª solución
lichtenberg3 :: [Integer]
lichtenberg3 =
  0 : 1 : map (+1) (zipWith (+) (tail lichtenberg3) (map (*2) lichtenberg3)) 

-- Comprobación de eficiencia
--    λ> length (show (lichtenberg1 !! 27))
--    8
--    (0.02 secs, 155,384 bytes)
--    λ> length (show (lichtenberg2 !! 27))
--    8
--    (2.22 secs, 311,157,760 bytes)
--    
--    λ> length (show (lichtenberg1 !! (8*10^4)))
--    24083
--    (1.28 secs, 664,207,040 bytes)
--    λ> length (show (lichtenberg3 !! (8*10^4)))
--    24083
--    (2.59 secs, 1,253,328,200 bytes)

-- La propiedad es
propLichtenberg :: Int -> Property
propLichtenberg n =
  n > 4 ==> not (isPrime (lichtenberg1 !! n))

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

graficaLichtenberg :: Int -> IO ()
graficaLichtenberg n =
  plotList [ Key Nothing
           , Title "Numero de digitos de la sucesion de Lichtenberg"
           , PNG "Sucesion_de_Lichtenberg.png"
           ]
           (take n (map (length . show) lichtenberg1))

import Data.Char (digitToInt)

import Graphics.Gnuplot.Simple

import Test.QuickCheck

import Data.Numbers.Primes (isPrime)

-- 1ª solución

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

lichtenberg1 :: [Integer]

lichtenberg1 = map binarioAdecimal sucAlternada

-- sucAlternada es la lista cuyos elementos son los términos de la

-- sucesión de los dígitos 0 y 1 alternados. Por ejemplo,

-- λ> take 7 sucAlternada

-- ["0","1","10","101","1010","10101","101010"]

sucAlternada :: [String]

sucAlternada =

['0'] : [take n cadenaAlternada | n <- [1..]]

-- cadenaAltenada es la cadena formada alternando los caracteres 1 y

-- 0. Por ejemplo,

-- take 20 cadenaAlternada == "10101010101010101010"

cadenaAlternada :: String

cadenaAlternada = cycle ['1','0']

-- (binarioAdecimal cs) es el número decimal correspondiente al número

-- binario cuya cadena de dígitos es cs. Por ejemplo,

-- binarioAdecimal "11101" == 29

binarioAdecimal :: String -> Integer

binarioAdecimal =

foldl (\acc x -> acc * 2 + (toInteger . digitToInt) x) 0

-- 2ª solución

lichtenberg2 :: [Integer]

lichtenberg2 = map a [0..]

where a 0 = 0

a 1 = 1

a n = a (n-1) + 2 * a (n-2) + 1

-- 3ª solución

lichtenberg3 :: [Integer]

lichtenberg3 =

0 : 1 : map (+1) (zipWith (+) (tail lichtenberg3) (map (*2) lichtenberg3))

-- Comprobación de eficiencia

-- λ> length (show (lichtenberg1 !! 27))

-- 8

-- (0.02 secs, 155,384 bytes)

-- λ> length (show (lichtenberg2 !! 27))

-- 8

-- (2.22 secs, 311,157,760 bytes)

-- λ> length (show (lichtenberg1 !! (8*10^4)))

-- 24083

-- (1.28 secs, 664,207,040 bytes)

-- λ> length (show (lichtenberg3 !! (8*10^4)))

-- 24083

-- (2.59 secs, 1,253,328,200 bytes)

-- La propiedad es

propLichtenberg :: Int -> Property

propLichtenberg n =

n > 4 ==> not (isPrime (lichtenberg1 !! n))

-- La comprobación es

-- λ> quickCheck propLichtenberg

-- +++ OK, passed 100 tests.

graficaLichtenberg :: Int -> IO ()

graficaLichtenberg n =

plotList [ Key Nothing

, Title "Numero de digitos de la sucesion de Lichtenberg"

, PNG "Sucesion_de_Lichtenberg.png"

]

(take n (map (length . show) lichtenberg1))

Sumas parciales de Juzuk

PorJosé A. Alonso 23-enero-201830-enero-2018

En 1939 Dov Juzuk extendió el método de Nicómaco del cálculo de los cubos. La extensión se basaba en los siguientes pasos:

se comienza con la lista de todos los enteros positivos

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

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

se agrupan tomando el primer elemento, los dos siguientes, los tres
siguientes, etc.

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

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

se seleccionan los elementos en posiciones pares

     [[1],         [4, 5, 6],                [11, 12, 13, 14, 15], ...

1	[[1], [4, 5, 6], [11, 12, 13, 14, 15], ...

se suman los elementos de cada grupo

     [1,           15,                       65,                   ...

1	[1, 15, 65, ...

se calculan las sumas acumuladas

     [1,           16,                       81,                   ...

1	[1, 16, 81, ...

Las sumas obtenidas son las cuantas potencias de los números enteros positivos.

Definir las funciones

   listasParcialesJuzuk :: [a] -> [[a]]
   sumasParcialesJuzuk  :: [Integer] -> [Integer]

1 2	listasParcialesJuzuk :: [a] -> [[a]] sumasParcialesJuzuk :: [Integer] -> [Integer]

tal que

(listasParcialesJuzuk xs) es lalista de ls listas parciales de Juzuk; es decir, la selección de los elementos en posiciones pares de la agrupación de los elementos de xs tomando el primer elemento, los dos siguientes, los tres siguientes, etc. Por ejemplo,

     λ> take 4 (listasParcialesJuzuk [1..])
     [[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]]
     λ> take 4 (listasParcialesJuzuk [1,3..])
     [[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]

λ> take 4 (listasParcialesJuzuk [1..])

[[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]]

λ> take 4 (listasParcialesJuzuk [1,3..])

[[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]

(sumasParcialesJuzuk xs) es la lista de las sumas acumuladas de los elementos de las listas de Juzuk generadas por xs. Por ejemplo,

     take 4 (sumasParcialesJuzuk [1..])  ==  [1,16,81,256]
     take 4 (sumasParcialesJuzuk [1,3..])  ==  [1,28,153,496]

1 2	take 4 (sumasParcialesJuzuk [1..]) == [1,16,81,256] take 4 (sumasParcialesJuzuk [1,3..]) == [1,28,153,496]

Comprobar con QuickChek que, para todo entero positivo n,

el elemento de (sumasParcialesJuzuk [1..]) en la posición (n-1) es n^4.
el elemento de (sumasParcialesJuzuk [1,3..]) en la posición (n-1) es n^2*(2*n^2 - 1).
el elemento de (sumasParcialesJuzuk [1,5..]) en la posición (n-1) es 4*n^4-3*n^2.
el elemento de (sumasParcialesJuzuk [2,3..]) en la posición (n-1) es n^2*(n^2+1).

Soluciones

import Data.List (genericIndex)
import Test.QuickCheck

listasParcialesJuzuk :: [a] -> [[a]]
listasParcialesJuzuk = elementosEnPares . listasParciales

-- (listasParciales xs) es la agrupación de los elementos de xs obtenida
-- tomando el primer elemento, los dos siguientes, los tres siguientes,
-- etc. Por ejemplo, 
--    λ> take 5 (listasParciales [1..])
--    [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]
listasParciales :: [a] -> [[a]]
listasParciales = aux 1
  where aux n xs = ys : aux (n+1) zs  
          where (ys,zs) = splitAt n xs

-- (elementosEnPares xs) es la lista de los elementos de xs en
-- posiciones pares. Por ejemplo,
--    λ> elementosEnPares [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]
--    [[1],[4,5,6],[11,12,13,14,15]]
elementosEnPares :: [a] -> [a]
elementosEnPares []       = []
elementosEnPares [x]      = [x]
elementosEnPares (x:_:xs) = x : elementosEnPares xs

sumasParcialesJuzuk :: [Integer] -> [Integer]
sumasParcialesJuzuk xs =
  scanl1 (+) (map sum (listasParcialesJuzuk xs))

-- La primera propiedad es
prop_sumasParcialesJuzuk :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk (Positive n) =
  sumasParcialesJuzuk [1..] `genericIndex` (n-1) == n^4

-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_sumasParcialesJuzuk2 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk2 (Positive n) =
  sumasParcialesJuzuk [1,3..] `genericIndex` (n-1) == n^2*(2*n^2 - 1)

-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk2
--    +++ OK, passed 100 tests.

-- La tercera propiedad es
prop_sumasParcialesJuzuk3 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk3 (Positive n) =
  sumasParcialesJuzuk [1,5..] `genericIndex` (n-1) == 4*n^4-3*n^2

-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk3
--    +++ OK, passed 100 tests.

-- La cuarta propiedad es
prop_sumasParcialesJuzuk4 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk4 (Positive n) =
  sumasParcialesJuzuk [2,3..] `genericIndex` (n-1) == n^2*(n^2+1)
  
-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk4
--    +++ OK, passed 100 tests.

import Data.List (genericIndex)

import Test.QuickCheck

listasParcialesJuzuk :: [a] -> [[a]]

listasParcialesJuzuk = elementosEnPares . listasParciales

-- (listasParciales xs) es la agrupación de los elementos de xs obtenida

-- tomando el primer elemento, los dos siguientes, los tres siguientes,

-- etc. Por ejemplo,

-- λ> take 5 (listasParciales [1..])

-- [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]

listasParciales :: [a] -> [[a]]

listasParciales = aux 1

where aux n xs = ys : aux (n+1) zs

where (ys,zs) = splitAt n xs

-- (elementosEnPares xs) es la lista de los elementos de xs en

-- posiciones pares. Por ejemplo,

-- λ> elementosEnPares [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]

-- [[1],[4,5,6],[11,12,13,14,15]]

elementosEnPares :: [a] -> [a]

elementosEnPares [] = []

elementosEnPares [x] = [x]

elementosEnPares (x:_:xs) = x : elementosEnPares xs

sumasParcialesJuzuk :: [Integer] -> [Integer]

sumasParcialesJuzuk xs =

scanl1 (+) (map sum (listasParcialesJuzuk xs))

-- La primera propiedad es

prop_sumasParcialesJuzuk :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk (Positive n) =

sumasParcialesJuzuk [1..] `genericIndex` (n-1) == n^4

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_sumasParcialesJuzuk2 :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk2 (Positive n) =

sumasParcialesJuzuk [1,3..] `genericIndex` (n-1) == n^2*(2*n^2 - 1)

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk2

-- +++ OK, passed 100 tests.

-- La tercera propiedad es

prop_sumasParcialesJuzuk3 :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk3 (Positive n) =

sumasParcialesJuzuk [1,5..] `genericIndex` (n-1) == 4*n^4-3*n^2

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk3

-- +++ OK, passed 100 tests.

-- La cuarta propiedad es

prop_sumasParcialesJuzuk4 :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk4 (Positive n) =

sumasParcialesJuzuk [2,3..] `genericIndex` (n-1) == n^2*(n^2+1)

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk4

-- +++ OK, passed 100 tests.

Escalada hasta un primo

PorJosé A. Alonso 18-enero-201819-febrero-2018

Este ejercicio está basado en el artículo La conjetura de la «escalada hasta un primo» publicado esta semana por Miguel Ángel Morales en su blog Gaussianos.

La conjetura de escalada hasta un primo trata, propuesta por John Horton Conway, es sencilla de plantear, pero primero vamos a ver qué es eso de escalar hasta un primo. Tomamos un número cualquiera y lo descomponemos en factores primos (colocados en orden ascendente). Si el número era primo, ya hemos acabado; si no era primo, construimos el número formado por los factores primos y los exponentes de los mismos colocados tal cual salen en la factorización. Con el número obtenido hacemos lo mismo que antes. La escalada finaliza cuando obtengamos un número primo. Por ejemplo, para obtener la escalada prima de 1400, como no es primo, se factoriza (obteniéndose 2^3 * 5^2 * 7) y se unen bases y exponentes (obteniéndose 23527). Con el 23527 se repite el proceso obteniéndose la factorización (7 * 3361) y su unión (73361). Como el 73361 es primo, termina la escalada. Por tanto, la escalada de 1400 es [1400,23527,73361].

La conjetura de Conway sobre «escalada hasta un primo» dice que todo número natural mayor o igual que 2 termina su escalada en un número primo.

Definir las funciones

   escaladaPrima                :: Integer -> [Integer]
   longitudEscaladaPrima        :: Integer -> Integer
   longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
   graficaEscalada              :: Integer -> Integer -> IO ()

escaladaPrima :: Integer -> [Integer]

longitudEscaladaPrima :: Integer -> Integer

longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer

graficaEscalada :: Integer -> Integer -> IO ()

tales que

(escaladaPrima n) es la escalada prima de n. Por ejemplo,

     λ> escaladaPrima 1400
     [1400,23527,73361]
     λ> escaladaPrima 333
     [333,3237,31383,3211317,3217139151,39722974813]
     λ> take 10 (escaladaPrima 20)
     [20,225,3252,223271,297699,399233,715623,3263907,32347303,160720129]
     λ> take 3 (escaladaPrima 13532385396179)
     [13532385396179,13532385396179,13532385396179]
     λ> take 2 (escaladaPrima 45214884853168941713016664887087462487)
     [45214884853168941713016664887087462487,13532385396179]

λ> escaladaPrima 1400

[1400,23527,73361]

λ> escaladaPrima 333

[333,3237,31383,3211317,3217139151,39722974813]

λ> take 10 (escaladaPrima 20)

[20,225,3252,223271,297699,399233,715623,3263907,32347303,160720129]

λ> take 3 (escaladaPrima 13532385396179)

[13532385396179,13532385396179,13532385396179]

λ> take 2 (escaladaPrima 45214884853168941713016664887087462487)

[45214884853168941713016664887087462487,13532385396179]

(longitudEscaladaPrima n) es la longitud de la escalada prima de n. Por ejemplo,

     longitudEscaladaPrima 1400  ==  3
     longitudEscaladaPrima 333   ==  6

1 2	longitudEscaladaPrima 1400 == 3 longitudEscaladaPrima 333 == 6

(longitudEscaladaPrimaAcotada n k) es el mínimo entre la longitud de la escalada prima de n y k. Por ejemplo,

     longitudEscaladaPrimaAcotada 333 10  ==  6
     longitudEscaladaPrimaAcotada 333 4   ==  4
     longitudEscaladaPrimaAcotada 20 4    ==  4

longitudEscaladaPrimaAcotada 333 10 == 6

longitudEscaladaPrimaAcotada 333 4 == 4

longitudEscaladaPrimaAcotada 20 4 == 4

(graficaEscalada n k) dibuja la gráfica de (longitudEscaladaPrimaAcotada x k) para x entre 2 y n. Por ejemplo, (graficaEscalada 120 15) dibuja

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes
import Graphics.Gnuplot.Simple

-- Definición de escaladaPrima 
escaladaPrima :: Integer -> [Integer]
escaladaPrima n
  | isPrime n = [n]
  | otherwise = n : escaladaPrima (siguiente n)

-- (siguiente n) es el siguiente de n en la escalada hacia un primo. Por
-- ejemplo, 
--    siguiente 1400  ==  23527
siguiente :: Integer -> Integer
siguiente = paresAnumero . factorizacion

-- (factorizacion n) es la factorizacion prima de n. Por ejemplo,
--    factorizacion 1400  ==  [(2,3),(5,2),(7,1)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(x,genericLength xs) | xs@(x:_) <- group (primeFactors n)]

-- (paAnumero p) es el número obtenido pegando las dos componentes de p
-- (si la segunda es mayor que 1) o sólo la primera componente, en caso
-- contrario. Por ejemplo, 
--    parAnumero (7,1)  ==  7
--    parAnumero (23,5)  ==  235
parAnumero :: (Integer,Integer) -> Integer
parAnumero (n,1) = n
parAnumero (n,k) = read (show n ++ show k)

-- (paresA numeros ps) es el número obtenido aplicando parAnumero a cada
-- uno de los pares de ps. Por ejemplo,
--    paresAnumero [(2,3),(5,2),(7,1)]  ==  23527
paresAnumero :: [(Integer,Integer)] -> Integer
paresAnumero = read . concatMap (show . parAnumero)

-- Definición de longitudEscaladaPrima
longitudEscaladaPrima :: Integer -> Integer
longitudEscaladaPrima n
  | isPrime n = 1
  | otherwise = 1 + longitudEscaladaPrima (siguiente n)

-- Definición de longitudEscaladaPrimaAcotada
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada _ 0 = 0
longitudEscaladaPrimaAcotada n k
  | isPrime n = 1
  | otherwise = 1 + longitudEscaladaPrimaAcotada (siguiente n) (k-1)

-- Definición de graficaEscalada 
graficaEscalada :: Integer -> Integer -> IO ()
graficaEscalada n k =
  plotList [ Key Nothing
           , PNG "Escalada_hasta_un_primo.png"
           , Title ("graficaEscalada " ++ show n ++ " " ++ show k)
           , XLabel "Numeros"
           , YLabel "Longitud de escalada"
           ]
           [(x,longitudEscaladaPrimaAcotada x k) | x <- [2..n]]

import Data.List (genericLength, group)

import Data.Numbers.Primes

import Graphics.Gnuplot.Simple

-- Definición de escaladaPrima

escaladaPrima :: Integer -> [Integer]

escaladaPrima n

| isPrime n = [n]

| otherwise = n : escaladaPrima (siguiente n)

-- (siguiente n) es el siguiente de n en la escalada hacia un primo. Por

-- ejemplo,

-- siguiente 1400 == 23527

siguiente :: Integer -> Integer

siguiente = paresAnumero . factorizacion

-- (factorizacion n) es la factorizacion prima de n. Por ejemplo,

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

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

factorizacion n =

[(x,genericLength xs) | xs@(x:_) <- group (primeFactors n)]

-- (paAnumero p) es el número obtenido pegando las dos componentes de p

-- (si la segunda es mayor que 1) o sólo la primera componente, en caso

-- contrario. Por ejemplo,

-- parAnumero (7,1) == 7

-- parAnumero (23,5) == 235

parAnumero :: (Integer,Integer) -> Integer

parAnumero (n,1) = n

parAnumero (n,k) = read (show n ++ show k)

-- (paresA numeros ps) es el número obtenido aplicando parAnumero a cada

-- uno de los pares de ps. Por ejemplo,

-- paresAnumero [(2,3),(5,2),(7,1)] == 23527

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

paresAnumero = read . concatMap (show . parAnumero)

-- Definición de longitudEscaladaPrima

longitudEscaladaPrima :: Integer -> Integer

longitudEscaladaPrima n

| isPrime n = 1

| otherwise = 1 + longitudEscaladaPrima (siguiente n)

-- Definición de longitudEscaladaPrimaAcotada

longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer

longitudEscaladaPrimaAcotada _ 0 = 0

longitudEscaladaPrimaAcotada n k

| isPrime n = 1

| otherwise = 1 + longitudEscaladaPrimaAcotada (siguiente n) (k-1)

-- Definición de graficaEscalada

graficaEscalada :: Integer -> Integer -> IO ()

graficaEscalada n k =

plotList [ Key Nothing

, PNG "Escalada_hasta_un_primo.png"

, Title ("graficaEscalada " ++ show n ++ " " ++ show k)

, XLabel "Numeros"

, YLabel "Longitud de escalada"

]

[(x,longitudEscaladaPrimaAcotada x k) | x <- [2..n]]

Sumas parciales de Nicómaco

PorJosé A. Alonso 15-enero-201825-marzo-2022

Nicómaco de Gerasa vivió en Palestina entre los siglos I y II de nuestra era. Escribió Arithmetike eisagoge (Introducción a la aritmética) que es el primer trabajo en donde se trata la Aritmética de forma separada a la Geometría. En el tratado se encuentra la siguiente proposición: «si se escriben los números impares

   1, 3, 5, 7, 9, 11, 13, 15, 17, ...

1	1, 3, 5, 7, 9, 11, 13, 15, 17, ...

entonces el primero es el cubo de 1; la suma de los dos siguientes, el cubo de 2; la suma de los tres siguientes, el cubo de 3; y así sucesivamente.»

Definir las siguientes funciones

   listasParciales :: [a] -> [[a]]
   sumasParciales  :: [Int] -> [Int]

1 2	listasParciales :: [a] -> [[a]] sumasParciales :: [Int] -> [Int]

tales que

(listasParciales xs) es la lista obtenido agrupando los elementos de la lista infinita xs de forma que la primera tiene 0 elementos; la segunda, el primer elemento de xs; la tercera, los dos siguientes; y así sucesivamente. Por ejemplo,

     λ> take 7 (listasParciales [1..])
     [[],[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15],[16,17,18,19,20,21]]
     λ> take 7 (listasParciales [1,3..])
     [[],[1],[3,5],[7,9,11],[13,15,17,19],[21,23,25,27,29],[31,33,35,37,39,41]]

λ> take 7 (listasParciales [1..])

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

λ> take 7 (listasParciales [1,3..])

[[],[1],[3,5],[7,9,11],[13,15,17,19],[21,23,25,27,29],[31,33,35,37,39,41]]

(sumasParciales xs) es la lista de las sumas parciales de la lista infinita xs. Por ejemplo,

     λ> take 15 (sumasParciales [1..])
     [0,1,5,15,34,65,111,175,260,369,505,671,870,1105,1379]
     λ> take 15 (sumasParciales [1,3..])
     [0,1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744]

λ> take 15 (sumasParciales [1..])

[0,1,5,15,34,65,111,175,260,369,505,671,870,1105,1379]

λ> take 15 (sumasParciales [1,3..])

[0,1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744]

Comprobar con QuickChek la propiedad de Nicómaco; es decir, que para todo número natural n, el término n-ésimo de (sumasParciales [1,3..]) es el cubo de n.

Soluciones

import Test.QuickCheck

listasParciales :: [a] -> [[a]]
listasParciales = aux 0
  where aux n xs = ys : aux (n+1) zs  
          where (ys,zs) = splitAt n xs

sumasParciales :: [Int] -> [Int]
sumasParciales = map sum . listasParciales

prop_Nicomaco :: (Positive Int) -> Bool
prop_Nicomaco (Positive n) =
  sumasParciales [1,3..] !! n == n^3

import Test.QuickCheck

listasParciales :: [a] -> [[a]]

listasParciales = aux 0

where aux n xs = ys : aux (n+1) zs

where (ys,zs) = splitAt n xs

sumasParciales :: [Int] -> [Int]

sumasParciales = map sum . listasParciales

prop_Nicomaco :: (Positive Int) -> Bool

prop_Nicomaco (Positive n) =

sumasParciales [1,3..] !! n == n^3

Números malvados y odiosos

PorJosé A. Alonso 12-enero-201825-abril-2021

Un número malvado es un número natural cuya expresión en base 2 (binaria) contiene un número par de unos.

Un número odioso es un número natural cuya expresión en base 2 (binaria) contiene un número impar de unos.

Podemos representar los números malvados y odiosos mediante el siguiente tipo de dato

  data MalvadoOdioso = Malvado | Odioso deriving Show

1	data MalvadoOdioso = Malvado \| Odioso deriving Show

Definir la función

  malvadoOdioso :: Integer -> MalvadoOdioso

1	malvadoOdioso :: Integer -> MalvadoOdioso

tal que (malvadoOdioso n) devuelve el tipo de número que es n. Por ejemplo,

   λ> malvadoOdioso 11
   Odioso
   λ> malvadoOdioso 12
   Malvado
   λ> malvadoOdioso3 (10^20000000)
   Odioso
   λ> malvadoOdioso3 (1+10^20000000)
   Malvado

λ> malvadoOdioso 11

Odioso

λ> malvadoOdioso 12

Malvado

λ> malvadoOdioso3 (10^20000000)

Odioso

λ> malvadoOdioso3 (1+10^20000000)

Malvado

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

import Data.List (genericLength)
import Data.Bits (popCount)

data MalvadoOdioso = Malvado | Odioso
  deriving (Eq, Show)

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

malvadoOdioso :: Integer -> MalvadoOdioso
malvadoOdioso n | (even . numeroUnosBin) n = Malvado
                | otherwise                = Odioso

-- (numeroUnosBin n) es el número de unos de la representación binaria
-- del número decimal n. Por ejemplo,
--   numeroUnosBin 11  ==  3
--   numeroUnosBin 12  ==  2
numeroUnosBin :: Integer -> Integer
numeroUnosBin = genericLength . filter (/= 0) . intBin

-- (intBin n) es el número binario correspondiente al número decimal n.
-- Por ejemplo, 
--   intBin 11  ==  [1,1,0,1]
--   intBin 12  ==  [0,0,1,1]
intBin :: Integer -> [Integer]
intBin n | n < 2     = [n]
         | otherwise = n `mod` 2 : intBin (n `div` 2)

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

malvadoOdioso2 :: Integer -> MalvadoOdioso
malvadoOdioso2 n | (even . numeroIntBin) n = Malvado
                 | otherwise               = Odioso

-- (numeroIntBin n) es el número de unos que contiene la representación
-- binaria del número decimal n. Por ejemplo,
--   numeroIntBin 11  ==  3
--   numeroIntBin 12  ==  2
numeroIntBin :: Integer -> Integer
numeroIntBin n | n < 2     = n
               | otherwise = n `mod` 2 + numeroIntBin (n `div` 2)

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

malvadoOdioso3 :: Integer -> MalvadoOdioso
malvadoOdioso3 n | (even . popCount) n = Malvado
                 | otherwise           = Odioso

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

--   λ> malvadoOdioso (10^40000)
--   Odioso
--   (3.25 secs, 1,167,416,968 bytes)
--   λ> malvadoOdioso2 (10^40000)
--   Odioso
--   (4.03 secs, 1,164,863,744 bytes)
--   λ> malvadoOdioso3 (10^40000)
--   Odioso
--   (0.00 secs, 165,312 bytes)

import Data.List (genericLength)

import Data.Bits (popCount)

data MalvadoOdioso = Malvado | Odioso

deriving (Eq, Show)

-- 1ª solución

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

malvadoOdioso :: Integer -> MalvadoOdioso

malvadoOdioso n | (even . numeroUnosBin) n = Malvado

| otherwise = Odioso

-- (numeroUnosBin n) es el número de unos de la representación binaria

-- del número decimal n. Por ejemplo,

-- numeroUnosBin 11 == 3

-- numeroUnosBin 12 == 2

numeroUnosBin :: Integer -> Integer

numeroUnosBin = genericLength . filter (/= 0) . intBin

-- (intBin n) es el número binario correspondiente al número decimal n.

-- Por ejemplo,

-- intBin 11 == [1,1,0,1]

-- intBin 12 == [0,0,1,1]

intBin :: Integer -> [Integer]

intBin n | n < 2 = [n]

| otherwise = n `mod` 2 : intBin (n `div` 2)

-- 2ª solución

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

malvadoOdioso2 :: Integer -> MalvadoOdioso

malvadoOdioso2 n | (even . numeroIntBin) n = Malvado

| otherwise = Odioso

-- (numeroIntBin n) es el número de unos que contiene la representación

-- binaria del número decimal n. Por ejemplo,

-- numeroIntBin 11 == 3

-- numeroIntBin 12 == 2

numeroIntBin :: Integer -> Integer

numeroIntBin n | n < 2 = n

| otherwise = n `mod` 2 + numeroIntBin (n `div` 2)

-- 3ª solución

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

malvadoOdioso3 :: Integer -> MalvadoOdioso

malvadoOdioso3 n | (even . popCount) n = Malvado

| otherwise = Odioso

-- Comparación de eficiencia

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

-- λ> malvadoOdioso (10^40000)

-- Odioso

-- (3.25 secs, 1,167,416,968 bytes)

-- λ> malvadoOdioso2 (10^40000)

-- Odioso

-- (4.03 secs, 1,164,863,744 bytes)

-- λ> malvadoOdioso3 (10^40000)

-- Odioso

-- (0.00 secs, 165,312 bytes)

Padres como sumas de hijos

PorJosé A. Alonso 5-enero-201819-febrero-2018

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

         10
        /  \
       /    \
      8      2
     / \    / \
    3   5  2   0

/ \

8 2

/ \ / \

3 5 2 0

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 5))
                  (N 2 (H 2) (H 0))

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 5))

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

Un árbol cumple la propiedad de la suma si el valor de cada nodo es igual a la suma de los valores de sus hijos. Por ejemplo, el árbol anterior cumple la propiedad de la suma.

Definir la función

   propSuma :: Arbol Int -> Bool

1	propSuma :: Arbol Int -> Bool

tal que (propSuma a) se verifica si el árbol a cumple la propiedad de la suma. Por ejemplo,

   λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0)))
   True
   λ> propSuma (N 10 (N 8 (H 4) (H 5)) (N 2 (H 2) (H 0)))
   False
   λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 1)))
   False

λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0)))

True

λ> propSuma (N 10 (N 8 (H 4) (H 5)) (N 2 (H 2) (H 0)))

False

λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 1)))

False

Soluciones

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

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 5))
               (N 2 (H 2) (H 0))

propSuma :: Arbol Int -> Bool
propSuma (H _)     = True
propSuma (N x i d) = x == raiz i + raiz d && propSuma i && propSuma d
             
raiz :: Arbol Int -> Int
raiz (H x)     = x
raiz (N x _ _) = x

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 5))

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

propSuma :: Arbol Int -> Bool

propSuma (H _) = True

propSuma (N x i d) = x == raiz i + raiz d && propSuma i && propSuma d

raiz :: Arbol Int -> Int

raiz (H x) = x

raiz (N x _ _) = x

Problema del cambio de monedas

PorJosé A. Alonso 4-enero-201819-febrero-2018

El problema del cambio de monedas consiste en dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el número de formas de obtener y usando los tipos de monedas de ms. Por ejemplo, con monedas de 1, 5 y 10 céntimos se puede obtener 12 céntimos de 4 formas

   1,1,1,1,1,1,1,1,1,1,1,1
   1,1,1,1,1,1,1,5
   1,1,5,5
   1,1,10

1,1,1,1,1,1,1,1,1,1,1,1

1,1,1,1,1,1,1,5

1,1,5,5

1,1,10

Definir las funciones

   numeroCambios :: [Int] -> Int -> Int
   sucCambios :: [Int]
   grafica_cambios :: Int -> IO ()

numeroCambios :: [Int] -> Int -> Int

sucCambios :: [Int]

grafica_cambios :: Int -> IO ()

tales que

(numeroCambios ms x) es el número de formas de obtener x usando los tipos de monedas de ms. Por ejemplo,

     numeroCambios [1,5,10] 12  ==  4
     numeroCambios [4,1,3] 6    ==  4
     numeroCambios [1,5,10] 50  ==  36

numeroCambios [1,5,10] 12 == 4

numeroCambios [4,1,3] 6 == 4

numeroCambios [1,5,10] 50 == 36

sucCambios es la sucesión cuyo k-ésimo término es el número de cambios de k usando monedas de 1, 2, 5 y 10 céntimos. Por ejemplo,

   λ> take 20 sucCambios
   [1,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34]

1 2	λ> take 20 sucCambios [1,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34]

(grafica_cambios n) dibuja la gráfica de los n primeros términos de la sucesión sucCambios. Por ejemplo, (grafica_cambios 50) dibuja

Soluciones

import Data.List (sort)
import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int
numeroCambios ms = aux (sort ms) 
  where
    aux _      0 = 1
    aux []     _ = 0
    aux (m:ms) x | x < m     = 0
                 | otherwise = aux (m:ms) (x - m) + aux ms x

cambios :: [Int] -> Int -> [[Int]]
cambios xs y = aux (sort xs) y
  where
    aux _      0 = [[]]
    aux []     _ = []
    aux (k:ks) m | m < k     = []
                 | otherwise = [k:zs | zs <- aux (k:ks) (m - k)] ++
                               aux ks m
                               
sucCambios :: [Int]
sucCambios = [numeroCambios [1,2,5,10] k | k <- [0..]]

grafica_cambios :: Int -> IO ()
grafica_cambios n =
  plotList [ Title "Cambios con monedas de 1, 2, 5 y 10"
           , Key Nothing
           , XLabel "Objetivo"
           , YLabel "Numero de cambios"
           , PNG "Problema_del_cambio_de_monedas.png"
           ]
           (take n sucCambios)

import Data.List (sort)

import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int

numeroCambios ms = aux (sort ms)

where

aux _ 0 = 1

aux [] _ = 0

aux (m:ms) x | x < m = 0

| otherwise = aux (m:ms) (x - m) + aux ms x

cambios :: [Int] -> Int -> [[Int]]

cambios xs y = aux (sort xs) y

where

aux _ 0 = [[]]

aux [] _ = []

aux (k:ks) m | m < k = []

| otherwise = [k:zs | zs <- aux (k:ks) (m - k)] ++

aux ks m

sucCambios :: [Int]

sucCambios = [numeroCambios [1,2,5,10] k | k <- [0..]]

grafica_cambios :: Int -> IO ()

grafica_cambios n =

plotList [ Title "Cambios con monedas de 1, 2, 5 y 10"

, Key Nothing

, XLabel "Objetivo"

, YLabel "Numero de cambios"

, PNG "Problema_del_cambio_de_monedas.png"

]

(take n sucCambios)

Ofertas 3 por 2

PorJosé A. Alonso 3-enero-201825-abril-2021

En una tienda tienen la «oferta 3 por 2» de forma que cada cliente que elige 3 artículos obtiene el más barato de forma gratuita. Por ejemplo, si los precios de los artículos elegidos por un cliente son 10, 2, 4, 5 euros pagará 19 euros si agrupa los artículos en (10,2,4) y (5) o pagará 17 si lo agupa en (5,10,4) y (2).

Definir la función

   minimoConOferta :: [Int] -> Int

1	minimoConOferta :: [Int] -> Int

tal que (minimoConOferta xs) es lo mínimo que pagará el cliente si los precios de la compra son xs; es decir, lo que pagará agrupando los artículos de forma óptima para aplicar la oferta 3 por 2. Por ejemplo,

   minimoConOferta [10,2,4,5]     ==  17
   minimoConOferta [3,2,3,2]      ==  8
   minimoConOferta [6,4,5,5,5,5]  ==  21

minimoConOferta [10,2,4,5] == 17

minimoConOferta [3,2,3,2] == 8

minimoConOferta [6,4,5,5,5,5] == 21

Soluciones

import Data.List (sort)

minimoConOferta :: [Int] -> Int
minimoConOferta xs = aux (reverse (sort xs)) 0
  where aux (a:b:_:ds) n = aux ds (a+b+n)
        aux as         n = n + sum as

import Data.List (sort)

minimoConOferta :: [Int] -> Int

minimoConOferta xs = aux (reverse (sort xs)) 0

where aux (a:b:_:ds) n = aux ds (a+b+n)

aux as n = n + sum as

Recorrido por niveles de árboles binarios

PorJosé A. Alonso 27-diciembre-201719-febrero-2018

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

         1 
       /   \
      2     3
     / \   / \
    4   5 6   7
       / \
      8   9

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 1 (N 2 (H 4)
                      (N 5 (H 8) (H 9)))
                 (N 3 (H 6) (H 7))

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

Definir la función

   recorrido :: Arbol t -> [t]

1	recorrido :: Arbol t -> [t]

tal que (recorrido a) es el recorrido del árbol a por niveles desde la raíz a las hojas y de izquierda a derecha. Por ejemplo,

   λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
   [1,2,3,4,5,6,7,8,9]
   λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9))))
   [1,3,2,6,7,4,5,8,9]
   λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5)))
   [1,3,2,6,7,4,5]
   λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))
   [1,2,3,4,5,6,7]
   λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3))
   [1,2,3,4,5]
   λ> recorrido (N 1 (H 4) (H 3))
   [1,4,3]
   λ> recorrido (H 3)
   [3]

λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

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

λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9))))

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

λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5)))

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

λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))

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

λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3))

[1,2,3,4,5]

λ> recorrido (N 1 (H 4) (H 3))

[1,4,3]

λ> recorrido (H 3)

[3]

Soluciones

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

ejArbol :: Arbol Int
ejArbol = N 1 (N 2 (H 4)
                   (N 5 (H 8) (H 9)))
              (N 3 (H 6) (H 7))

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

recorrido :: Arbol t -> [t]
recorrido = concat . niveles

-- (niveles a) es la lista de los niveles del árbol a. Por ejemplo,
--    λ> niveles (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    [[1],[2,3],[4,5,6,7],[8,9]]
niveles :: Arbol t -> [[t]]
niveles (H x)     = [[x]]
niveles (N x i d) = [x] : mezcla (niveles i) (niveles d)

-- (mezcla xss yss) es la lista obtenida concatenando los
-- correspondientes elementos de xss e yss. Por ejemplo,
--    λ> mezcla [[1,3],[2,5,7]] [[4],[1,9],[0,14]]
--    [[1,3,4],[2,5,7,1,9],[0,14]]
--    λ> mezcla [[1,3],[2,5,7]] [[4]]
--    [[1,3,4],[2,5,7]]
mezcla :: [[a]] -> [[a]] -> [[a]]
mezcla [] yss            = yss
mezcla xss []            = xss
mezcla (xs:xss) (ys:yss) = (xs ++ ys) : mezcla xss yss

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

recorrido2 :: Arbol t -> [t]
recorrido2 = concat . niveles2

-- (niveles2 a) es la lista de los niveles del árbol a. Por ejemplo,
--    λ> niveles2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    [[1],[2,3],[4,5,6,7],[8,9]]
niveles2 :: Arbol t -> [[t]]
niveles2 a = takeWhile (not . null) [nivel n a | n <- [0..]]

-- (nivel n a) es el nivel iésimo del árbol a. Por ejemplo,
--    λ> nivel 2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    [4,5,6,7]
--    λ> nivel 5 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    []
nivel :: Int -> Arbol t -> [t]
nivel 0 (H x)      = [x]
nivel n (H _)      = []
nivel 0 (N x _ _)  = [x]
nivel n (N x i d)  = nivel (n-1) i ++ nivel (n-1) d

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

-- 1ª definición

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

recorrido :: Arbol t -> [t]

recorrido = concat . niveles

-- (niveles a) es la lista de los niveles del árbol a. Por ejemplo,

-- λ> niveles (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

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

niveles :: Arbol t -> [[t]]

niveles (H x) = [[x]]

niveles (N x i d) = [x] : mezcla (niveles i) (niveles d)

-- (mezcla xss yss) es la lista obtenida concatenando los

-- correspondientes elementos de xss e yss. Por ejemplo,

-- λ> mezcla [[1,3],[2,5,7]] [[4],[1,9],[0,14]]

-- [[1,3,4],[2,5,7,1,9],[0,14]]

-- λ> mezcla [[1,3],[2,5,7]] [[4]]

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

mezcla :: [[a]] -> [[a]] -> [[a]]

mezcla [] yss = yss

mezcla xss [] = xss

mezcla (xs:xss) (ys:yss) = (xs ++ ys) : mezcla xss yss

-- 2ª definición

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

recorrido2 :: Arbol t -> [t]

recorrido2 = concat . niveles2

-- (niveles2 a) es la lista de los niveles del árbol a. Por ejemplo,

-- λ> niveles2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

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

niveles2 :: Arbol t -> [[t]]

niveles2 a = takeWhile (not . null) [nivel n a | n <- [0..]]

-- (nivel n a) es el nivel iésimo del árbol a. Por ejemplo,

-- λ> nivel 2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

-- [4,5,6,7]

-- λ> nivel 5 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

-- []

nivel :: Int -> Arbol t -> [t]

nivel 0 (H x) = [x]

nivel n (H _) = []

nivel 0 (N x _ _) = [x]

nivel n (N x i d) = nivel (n-1) i ++ nivel (n-1) d

Sumable sin vecinos

PorJosé A. Alonso 21-diciembre-201719-febrero-2018

En la lista [3,2,5,7,4] el número 12 se puede escribir como una suma de elementos de la lista sin incluir sus vecinos (ya que es la suma de 3, 5 y 4); en cambio, 14 no lo es (porque es la suma de 3, 7 y 4, pero 7 y 4 son vecinos).

Definir la función

   esSumableSinVecinos :: [Int] -> Int -> Bool

1	esSumableSinVecinos :: [Int] -> Int -> Bool

tal que (esSumableSinVecinos xs n) se verifica si n se puede escribir como una suma de elementos de xs que no incluye a ninguno de sus vecinos. Por ejemplo,

   esSumableSinVecinos [3,2,5,7,4] 12  ==  True
   esSumableSinVecinos [3,2,5,7,4] 9   ==  True
   esSumableSinVecinos [3,2,5,7,4] 6   ==  True
   esSumableSinVecinos [3,2,5,7,4] 14  ==  False
   esSumableSinVecinos [3,2,5,7,4] 1   ==  False

esSumableSinVecinos [3,2,5,7,4] 12 == True

esSumableSinVecinos [3,2,5,7,4] 9 == True

esSumableSinVecinos [3,2,5,7,4] 6 == True

esSumableSinVecinos [3,2,5,7,4] 14 == False

esSumableSinVecinos [3,2,5,7,4] 1 == False

Soluciones

esSumableSinVecinos :: [Int] -> Int -> Bool
esSumableSinVecinos _  0       = True
esSumableSinVecinos []  _      = False
esSumableSinVecinos [x] n      = x == n
esSumableSinVecinos (x:y:zs) n = esSumableSinVecinos zs (n - x) ||
                                 esSumableSinVecinos (y:zs) n

esSumableSinVecinos :: [Int] -> Int -> Bool

esSumableSinVecinos _ 0 = True

esSumableSinVecinos [] _ = False

esSumableSinVecinos [x] n = x == n

esSumableSinVecinos (x:y:zs) n = esSumableSinVecinos zs (n - x) ||

esSumableSinVecinos (y:zs) n

Suma de las hojas de mínimo nivel

PorJosé A. Alonso 20-diciembre-201727-diciembre-2017

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

         1 
       /   \
      2     3
     / \   / \
    4   5 6   7
       / \
      8   9

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 1 (N 2 (H 4)
                      (N 5 (H 8) (H 9)))
                 (N 3 (H 6) (H 7))

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.

Definir la función

   suma :: Num t => Arbol t -> t

1	suma :: Num t => Arbol t -> t

tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,

   suma ejArbol                                    ==  17
   suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))  ==  22
   suma (N 1 (H 2) (N 3 (H 6) (H 7)))              ==  2
   suma (N 1 (H 2) (H 3))                          ==  5
   suma (H 2)                                      ==  2

suma ejArbol == 17

suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7))) == 22

suma (N 1 (H 2) (N 3 (H 6) (H 7))) == 2

suma (N 1 (H 2) (H 3)) == 5

suma (H 2) == 2

Soluciones

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

ejArbol :: Arbol Int
ejArbol = N 1 (N 2 (H 4)
                   (N 5 (H 8) (H 9)))
              (N 3 (H 6) (H 7))
                      
suma :: Num t => Arbol t -> t
suma a = aux [a]
  where aux as | null xs   = aux (concat [[i,d] | (N _ i d) <- as])
               | otherwise = sum xs
          where xs = [x | (H x) <- as]

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

suma :: Num t => Arbol t -> t

suma a = aux [a]

where aux as | null xs = aux (concat [[i,d] | (N _ i d) <- as])

| otherwise = sum xs

where xs = [x | (H x) <- as]

Cadenas opuestas

PorJosé A. Alonso 18-diciembre-201725-diciembre-2017

La opuesta de una cadena de letras es la cadena obtenida cambiando las minúsculas por mayúsculas y las minúsculas por mayúsculas. Por ejemplo, la opuesta de «SeViLLa» es «sEvIllA».

Definir la función

   esOpuesta :: String -> String -> Bool

1	esOpuesta :: String -> String -> Bool

tal que (esOpuesta s1 s2) se verifica si las cadenas de letras s1 y s2 son opuestas. Por ejemplo,

   esOpuesta "ab" "AB"      `== True
   esOpuesta "aB" "Ab"      `== True
   esOpuesta "aBcd" "AbCD"  `== True
   esOpuesta "aBcde" "AbCD" `== False
   esOpuesta "AB" "Ab"      `== False
   esOpuesta "" ""          `== True

esOpuesta "ab" "AB" `== True

esOpuesta "aB" "Ab" `== True

esOpuesta "aBcd" "AbCD" `== True

esOpuesta "aBcde" "AbCD" `== False

esOpuesta "AB" "Ab" `== False

esOpuesta "" "" `== True

Soluciones

import Data.Char (isLower, isUpper, ord, toLower, toUpper)

-- 1ª solución (por comprensión)
-- =============================

esOpuesta1 :: String -> String -> Bool
esOpuesta1 s1 s2 = [opuesto c | c <- s1] == s2

opuesto :: Char -> Char
opuesto c
  | isLower c = toUpper c
  | otherwise = toLower c

-- 2ª solución (con map)
-- =====================

esOpuesta2 :: String -> String -> Bool
esOpuesta2 s1 s2 = map opuesto s1 == s2

-- 3ª solución (por recursión)
-- ===========================

esOpuesta3 :: String -> String -> Bool
esOpuesta3 "" ""           = True
esOpuesta3 (c1:s1) (c2:s2) = esOpuesto c1 c2 && esOpuesta3 s1 s2
esOpuesta3 _ _             = False

esOpuesto :: Char -> Char -> Bool
esOpuesto c1 c2 = abs (ord c1 - ord c2) == 32

import Data.Char (isLower, isUpper, ord, toLower, toUpper)

-- 1ª solución (por comprensión)

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

esOpuesta1 :: String -> String -> Bool

esOpuesta1 s1 s2 = [opuesto c | c <- s1] == s2

opuesto :: Char -> Char

opuesto c

| isLower c = toUpper c

| otherwise = toLower c

-- 2ª solución (con map)

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

esOpuesta2 :: String -> String -> Bool

esOpuesta2 s1 s2 = map opuesto s1 == s2

-- 3ª solución (por recursión)

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

esOpuesta3 :: String -> String -> Bool

esOpuesta3 "" "" = True

esOpuesta3 (c1:s1) (c2:s2) = esOpuesto c1 c2 && esOpuesta3 s1 s2

esOpuesta3 _ _ = False

esOpuesto :: Char -> Char -> Bool

esOpuesto c1 c2 = abs (ord c1 - ord c2) == 32

Menor con suma de dígitos dada

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

Definir la función

   minSumDig :: Integer -> Integer

1	minSumDig :: Integer -> Integer

tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,

  minSumDig 1   ==  1
  minSumDig 12  ==  39
  minSumDig 21  ==  399
  (length . show . minSumDig) (3*10^5)  ==  33334
  (length . show . minSumDig) (3*10^6)  ==  333334
  (length . show . minSumDig) (3*10^7)  ==  3333334
  (length . show . minSumDig) (4*10^7)  ==  4444445
  (length . show . minSumDig) (5*10^7)  ==  5555556

minSumDig 1 == 1

minSumDig 12 == 39

minSumDig 21 == 399

(length . show . minSumDig) (3*10^5) == 33334

(length . show . minSumDig) (3*10^6) == 333334

(length . show . minSumDig) (3*10^7) == 3333334

(length . show . minSumDig) (4*10^7) == 4444445

(length . show . minSumDig) (5*10^7) == 5555556

Soluciones

import Data.List (genericIndex)

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

minSumDig1 :: Integer -> Integer
minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n]

sumaDigitos :: Integer -> Integer
sumaDigitos n | n < 10    = n
              | otherwise = y + sumaDigitos x
  where (x, y) = divMod n 10

-- 2ª definición
minSumDig2 :: Integer -> Integer
minSumDig2 n | n < 10    = n
             | otherwise = 9 + 10 * minSumDig2 (n - 9) 

-- 3ª definición
minSumDig3 :: Integer -> Integer
minSumDig3 n = (r + 1) * 10^d - 1
  where (d,r) = divMod n 9

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

--    λ> minSumDig1 46
--    199999
--    (3.21 secs, 542,721,696 bytes)
--    λ> minSumDig2 46
--    199999
--    (0.01 secs, 142,056 bytes)
--    λ> minSumDig3 46
--    199999
--    (0.01 secs, 155,984 bytes)
--    
--    λ> (length . show . minSumDig2) (3*10^5)
--    33334
--    (1.79 secs, 492,200,376 bytes)
--    λ> (length . show . minSumDig3) (3*10^5)
--    33334
--    (0.11 secs, 50,119,840 bytes)

import Data.List (genericIndex)

-- 1ª definición

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

minSumDig1 :: Integer -> Integer

minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n]

sumaDigitos :: Integer -> Integer

sumaDigitos n | n < 10 = n

| otherwise = y + sumaDigitos x

where (x, y) = divMod n 10

-- 2ª definición

minSumDig2 :: Integer -> Integer

minSumDig2 n | n < 10 = n

| otherwise = 9 + 10 * minSumDig2 (n - 9)

-- 3ª definición

minSumDig3 :: Integer -> Integer

minSumDig3 n = (r + 1) * 10^d - 1

where (d,r) = divMod n 9

-- Comparación de eficiencia

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

-- λ> minSumDig1 46

-- 199999

-- (3.21 secs, 542,721,696 bytes)

-- λ> minSumDig2 46

-- 199999

-- (0.01 secs, 142,056 bytes)

-- λ> minSumDig3 46

-- 199999

-- (0.01 secs, 155,984 bytes)

-- λ> (length . show . minSumDig2) (3*10^5)

-- 33334

-- (1.79 secs, 492,200,376 bytes)

-- λ> (length . show . minSumDig3) (3*10^5)

-- 33334

-- (0.11 secs, 50,119,840 bytes)

Bosque de recorridos del autobús

PorJosé A. Alonso 13-diciembre-201720-diciembre-2017

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []]
   ejArbol2 = Node 8 [Node 4 []]

1 2	ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []] ejArbol2 = Node 8 [Node 4 []]

También se pueden definir bosques. Por ejemplo,

   ejBosque = [ejArbol1, ejArbol2]

1	ejBosque = [ejArbol1, ejArbol2]

Se pueden dibujar los bosques con la función drawForest. Por ejemplo,

   λ> putStrLn (drawForest (map (fmap show) ejBosque))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7
   
   8
   |
   `- 4

λ> putStrLn (drawForest (map (fmap show) ejBosque))

+- 5

| |

| `- 9

`- 7

`- 4

Usando la notación de los ejercicios anteriores para las subidas y bajadas en el autobús, definir la función

   bosqueRecorridos :: Int -> Int -> Forest (Int,Int)

1	bosqueRecorridos :: Int -> Int -> Forest (Int,Int)

tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autobús de capacidad n y usando m paradas. Por ejemplo,

   λ> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))
   (0,0)
   |
   +- (0,0)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  `- (2,0)
   |
   +- (1,0)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  `- (2,1)
   |
   `- (2,0)
      |
      +- (0,0)
      |
      +- (0,1)
      |
      +- (1,1)
      |
      +- (0,2)
      |
      +- (1,2)
      |
      `- (2,2)
   
   (1,0)
   |
   +- (0,0)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  `- (2,1)
   |
   +- (1,0)
   |  |
   |  +- (0,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  +- (0,2)
   |  |
   |  +- (1,2)
   |  |
   |  `- (2,2)
   |
   +- (0,1)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  `- (2,0)
   |
   +- (1,1)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  `- (2,1)
   |
   `- (2,1)
      |
      +- (0,0)
      |
      +- (0,1)
      |
      +- (1,1)
      |
      +- (0,2)
      |
      +- (1,2)
      |
      `- (2,2)
   
   (2,0)
   |
   +- (0,0)
   |  |
   |  +- (0,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  +- (0,2)
   |  |
   |  +- (1,2)
   |  |
   |  `- (2,2)
   |
   +- (0,1)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  `- (2,1)
   |
   +- (1,1)
   |  |
   |  +- (0,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  +- (0,2)
   |  |
   |  +- (1,2)
   |  |
   |  `- (2,2)
   |
   +- (0,2)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  `- (2,0)
   |
   +- (1,2)
   |  |
   |  +- (0,0)
   |  |
   |  +- (1,0)
   |  |
   |  +- (0,1)
   |  |
   |  +- (1,1)
   |  |
   |  `- (2,1)
   |
   `- (2,2)
      |
      +- (0,0)
      |
      +- (0,1)
      |
      +- (1,1)
      |
      +- (0,2)
      |
      +- (1,2)
      |
      `- (2,2)

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

λ> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))

(0,0)

+- (0,0)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| `- (2,0)

+- (1,0)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| `- (2,1)

`- (2,0)

+- (0,0)

+- (0,1)

+- (1,1)

+- (0,2)

+- (1,2)

`- (2,2)

(1,0)

+- (0,0)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| `- (2,1)

+- (1,0)

| |

| +- (0,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| +- (0,2)

| |

| +- (1,2)

| |

| `- (2,2)

+- (0,1)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| `- (2,0)

+- (1,1)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| `- (2,1)

`- (2,1)

+- (0,0)

+- (0,1)

+- (1,1)

+- (0,2)

+- (1,2)

`- (2,2)

(2,0)

+- (0,0)

| |

| +- (0,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| +- (0,2)

| |

| +- (1,2)

| |

| `- (2,2)

+- (0,1)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| `- (2,1)

+- (1,1)

| |

| +- (0,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| +- (0,2)

| |

| +- (1,2)

| |

| `- (2,2)

+- (0,2)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| `- (2,0)

+- (1,2)

| |

| +- (0,0)

| |

| +- (1,0)

| |

| +- (0,1)

| |

| +- (1,1)

| |

| `- (2,1)

`- (2,2)

+- (0,0)

+- (0,1)

+- (1,1)

+- (0,2)

+- (1,2)

`- (2,2)

en donde la última rama representa el recorrido [(2,0),(2,2),(2,2)].

Soluciones

import Data.Tree

bosqueRecorridos :: Int -> Int -> Forest (Int, Int)
bosqueRecorridos c p = aux p 0
  where aux 0 _ = []
        aux p' a = [Node (s,b) (aux (p'-1) (a+s-b))
                   | b <- [0..a]
                   , s <- [0..c-a+b]]

import Data.Tree

bosqueRecorridos :: Int -> Int -> Forest (Int, Int)

bosqueRecorridos c p = aux p 0

where aux 0 _ = []

aux p' a = [Node (s,b) (aux (p'-1) (a+s-b))

| b <- [0..a]

, s <- [0..c-a+b]]

Reconocimiento de recorridos correctos

PorJosé A. Alonso 12-diciembre-201719-diciembre-2017

Se usará la misma representación del ejercicio anterior para las subidas y bajadas en el autobús; es decir, una lista de pares donde los primeros elementos es el número de viajeros que suben y los segundo es el de los que bajan.

Un recorrido es correcto si en cada bajada tanto el número de viajeros que suben como los que bajan son positivos, el número de viajeros en el autobús no puede ser mayor que su capacidad y el número de viajeros que bajan no puede ser mayor que el número de viajeros en el autobús. Se supone que en la primera parada el autobús no tiene viajeros.

Definir la función

   recorridoCorrecto :: Int -> [(Int,Int)] -> Bool

1	recorridoCorrecto :: Int -> [(Int,Int)] -> Bool

tal que (recorridoCorrecto n ps) se verifica si ps es un recorrido correcto en un autobús cuya capacidad es n. Por ejemplo,

  recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  True
  recorridoCorrecto 15 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  False
  recorridoCorrecto 15 [(3,2),(9,1),(4,10),(12,2),(6,1)]  ==  False
  recorridoCorrecto 15 [(3,0),(2,7),(4,10),(12,2),(6,1)]  ==  False

recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)] == True

recorridoCorrecto 15 [(3,0),(9,1),(4,10),(12,2),(6,1)] == False

recorridoCorrecto 15 [(3,2),(9,1),(4,10),(12,2),(6,1)] == False

recorridoCorrecto 15 [(3,0),(2,7),(4,10),(12,2),(6,1)] == False

el segundo ejemplo es incorrecto porque en la última para se supera la capacidad del autobús; el tercero, porque en la primera para no hay viajeros en el autobús que se puedan bajar y el cuarto, porque en la 2ª parada el autobús tiene 3 viajeros por lo que es imposible que se bajen 7.

Soluciones

-- 1ª definición
recorridoCorrecto1 :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto1 _ [] = True
recorridoCorrecto1 n ps = aux 0 ps
  where aux _ []         = True
        aux k ((a,b):ps) = 0 <= a && a <= n - k + b &&
                           0 <= b && b <= k &&
                           aux (k + a - b) ps

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

recorridoCorrecto2 :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto2 n ps =
  all (\(x,y) -> x >= 0 && y >= 0) ps &&
  all (\k -> 0 <= k && k <= n) (viajeros ps)

-- (viajeros ps) es el número de viajeros después de cada parada del
-- recorrido ps. Por ejemplo,
--   viajeros [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  [0,3,11,5,15,20]
--   viajeros [(3,0),(2,7),(4,10),(12,2),(6,1)]  ==  [0,3,-2,-8,2,7]
viajeros :: [(Int,Int)] -> [Int]
viajeros ps = aux [0] ps
  where aux ns     []         = reverse ns
        aux (n:ns) ((a,b):ps) = aux (n+a-b:n:ns) ps 

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

recorridoCorrecto3 :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto3 n ps =
  all (\(x,y) -> x >= 0 && y >= 0) ps &&
  all (\k -> 0 <= k && k <= n) (viajeros3 ps)

-- (viajeros3 ps) es el número de viajeros después de cada parada del
-- recorrido ps. Por ejemplo,
--   viajeros3 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  [0,3,11,5,15,20]
--   viajeros3 [(3,0),(2,7),(4,10),(12,2),(6,1)]  ==  [0,3,-2,-8,2,7]
viajeros3 :: [(Int,Int)] -> [Int]
viajeros3 = scanl (\k (a,b) -> k+a-b) 0

-- 1ª definición

recorridoCorrecto1 :: Int -> [(Int,Int)] -> Bool

recorridoCorrecto1 _ [] = True

recorridoCorrecto1 n ps = aux 0 ps

where aux _ [] = True

aux k ((a,b):ps) = 0 <= a && a <= n - k + b &&

0 <= b && b <= k &&

aux (k + a - b) ps

-- 2ª definición

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

recorridoCorrecto2 :: Int -> [(Int,Int)] -> Bool

recorridoCorrecto2 n ps =

all (\(x,y) -> x >= 0 && y >= 0) ps &&

all (\k -> 0 <= k && k <= n) (viajeros ps)

-- (viajeros ps) es el número de viajeros después de cada parada del

-- recorrido ps. Por ejemplo,

-- viajeros [(3,0),(9,1),(4,10),(12,2),(6,1)] == [0,3,11,5,15,20]

-- viajeros [(3,0),(2,7),(4,10),(12,2),(6,1)] == [0,3,-2,-8,2,7]

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

viajeros ps = aux [0] ps

where aux ns [] = reverse ns

aux (n:ns) ((a,b):ps) = aux (n+a-b:n:ns) ps

-- 3ª definición

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

recorridoCorrecto3 :: Int -> [(Int,Int)] -> Bool

recorridoCorrecto3 n ps =

all (\(x,y) -> x >= 0 && y >= 0) ps &&

all (\k -> 0 <= k && k <= n) (viajeros3 ps)

-- (viajeros3 ps) es el número de viajeros después de cada parada del

-- recorrido ps. Por ejemplo,

-- viajeros3 [(3,0),(9,1),(4,10),(12,2),(6,1)] == [0,3,11,5,15,20]

-- viajeros3 [(3,0),(2,7),(4,10),(12,2),(6,1)] == [0,3,-2,-8,2,7]

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

viajeros3 = scanl (\k (a,b) -> k+a-b) 0

Número de viajeros en el autobús

PorJosé A. Alonso 11-diciembre-201719-diciembre-2017

Un autobús inicia su recorrido con 0 viajeros. El número de viajeros que se suben y bajan en cada parada se representa por un par (x,y) donde x es el número de las que suben e y el de las que bajan. Un recorrido del autobús se representa por una lista de pares representando los números de viajeros que suben o bajan en cada parada.

Definir la función

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

1	nViajerosEnBus :: [(Int, Int)] -> Int

tal que (nViajerosEnBus ps) es el número de viajeros en el autobús tras el recorrido ps. Por ejemplo,

  nViajerosEnBus []                                        ==  0
  nViajerosEnBus [(10,0),(3,5),(5,8)]                      ==  5
  nViajerosEnBus [(3,0),(9,1),(4,10),(12,2),(6,1),(7,10)]  ==  17
  nViajerosEnBus [(3,0),(9,1),(4,8),(12,2),(6,1),(7,8)]    ==  21

nViajerosEnBus [] == 0

nViajerosEnBus [(10,0),(3,5),(5,8)] == 5

nViajerosEnBus [(3,0),(9,1),(4,10),(12,2),(6,1),(7,10)] == 17

nViajerosEnBus [(3,0),(9,1),(4,8),(12,2),(6,1),(7,8)] == 21

Soluciones

import Data.List (foldl')

-- 1ª solución (por comprensión)
nViajerosEnBus1 :: [(Int, Int)] -> Int
nViajerosEnBus1 ps = sum [a - b | (a,b) <- ps]

-- 2ª solucioń (por recursión)
nViajerosEnBus2 :: [(Int, Int)] -> Int
nViajerosEnBus2 []         = 0
nViajerosEnBus2 ((a,b):ps) = a - b + nViajerosEnBus2 ps

-- 3ª solución (por recursión con acumulador)
nViajerosEnBus3 :: [(Int, Int)] -> Int
nViajerosEnBus3 = aux 0
  where aux n []         = n
        aux n ((a,b):xs) = aux (n+a-b) xs

-- 4ª solución (por plegado por la derecha):
nViajerosEnBus4 :: [(Int, Int)] -> Int
nViajerosEnBus4 = foldr (\(a,b) n -> a-b+n) 0

-- 5ª solución (por plegado por la derecha):
nViajerosEnBus5 :: [(Int, Int)] -> Int
nViajerosEnBus5 = foldl' (\n (a,b) -> a-b+n) 0

-- 6ª solución (con map)
nViajerosEnBus6 :: [(Int, Int)] -> Int
nViajerosEnBus6 xs = sum (map (\(x,y) -> x-y) xs)

-- 7ª solución (por composición y sin argumentos) 
nViajerosEnBus7 :: [(Int, Int)] -> Int
nViajerosEnBus7 = sum . map (uncurry (-))

import Data.List (foldl')

-- 1ª solución (por comprensión)

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

nViajerosEnBus1 ps = sum [a - b | (a,b) <- ps]

-- 2ª solucioń (por recursión)

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

nViajerosEnBus2 [] = 0

nViajerosEnBus2 ((a,b):ps) = a - b + nViajerosEnBus2 ps

-- 3ª solución (por recursión con acumulador)

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

nViajerosEnBus3 = aux 0

where aux n [] = n

aux n ((a,b):xs) = aux (n+a-b) xs

-- 4ª solución (por plegado por la derecha):

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

nViajerosEnBus4 = foldr (\(a,b) n -> a-b+n) 0

-- 5ª solución (por plegado por la derecha):

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

nViajerosEnBus5 = foldl' (\n (a,b) -> a-b+n) 0

-- 6ª solución (con map)

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

nViajerosEnBus6 xs = sum (map (\(x,y) -> x-y) xs)

-- 7ª solución (por composición y sin argumentos)

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

nViajerosEnBus7 = sum . map (uncurry (-))

Ordenación valle

PorJosé A. Alonso 8-diciembre-201715-diciembre-2017

La ordenación valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutación de la primera y cumple las siguientes condiciones

se compone de una parte decreciente ([79,35,25]), un elemento mínimo (12) y una parte creciente ([19,35,54]);
las dos partes tienen el mismo número de elementos;
cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 ≥ 54, 35 ≥ 35 y 25 ≥ 19;
además, la diferencia entre dichos elementos es la menor posible.

En el caso, de que la longitud de la lista sea par, la división tiene sólo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].

Definir la función

   valle :: [Int] -> [Int]

1	valle :: [Int] -> [Int]

tal que (valle xs) es la ordenación valle de la lista xs. Por ejemplo,

   valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]
   valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]
   valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]
   valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]
   valle [14,14,14,14,14]             ==  [14,14,14,14,14]
   valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]

valle [79,35,54,19,35,25,12] == [79,35,25,12,19,35,54]

valle [79,35,54,19,35,25] == [79,35,25,19,35,54]

valle [67,93,100,-16,65,97,92] == [100,93,67,-16,65,92,97]

valle [14,14,14,14,7,14] == [14,14,14,7,14,14]

valle [14,14,14,14,14] == [14,14,14,14,14]

valle [17,17,15,14,8,7,7,5,4,4,1] == [17,15,8,7,4,1,4,5,7,14,17]

En el último ejemplo se muestra cómo la última condición descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] también sea solución ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la solución; por ejemplo, 17 – 7 > 17 – 17.

Soluciones

import Data.List (sort, sortBy)

-- 1ª solución
valle1 :: [Int] -> [Int]
valle1 xs = ys ++ reverse zs
  where (ys,zs) = aux (reverse (sort xs))
        aux []       = ([],[])
        aux [x]      = ([x],[])
        aux [x,y]    = ([x,y],[])
        aux (x:y:zs) = (x:as,y:bs)
          where (as,bs) = aux zs

-- 2ª solución
valle2 :: [Int] -> [Int]
valle2 = aux . reverse . sort
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]

-- 3ª solución
valle3 :: [Int] -> [Int]
valle3 = aux . sortBy (flip compare)
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]
        
-- Comparación de eficiencia
-- =========================

-- λ> length (valle1 [1..2*10^4])
-- 20000
-- (0.02 secs, 8,621,240 bytes)
-- λ> length (valle2 [1..2*10^4])
-- 20000
-- (2.68 secs, 8,595,637,880 bytes)
-- λ> length (valle3 [1..2*10^4])
-- 20000
-- (2.67 secs, 8,594,678,104 bytes)

import Data.List (sort, sortBy)

-- 1ª solución

valle1 :: [Int] -> [Int]

valle1 xs = ys ++ reverse zs

where (ys,zs) = aux (reverse (sort xs))

aux [] = ([],[])

aux [x] = ([x],[])

aux [x,y] = ([x,y],[])

aux (x:y:zs) = (x:as,y:bs)

where (as,bs) = aux zs

-- 2ª solución

valle2 :: [Int] -> [Int]

valle2 = aux . reverse . sort

where aux [] = []

aux [x] = [x]

aux (x:y:xs) = x : aux xs ++ [y]

-- 3ª solución

valle3 :: [Int] -> [Int]

valle3 = aux . sortBy (flip compare)

where aux [] = []

aux [x] = [x]

aux (x:y:xs) = x : aux xs ++ [y]

-- Comparación de eficiencia

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

-- λ> length (valle1 [1..2*10^4])

-- 20000

-- (0.02 secs, 8,621,240 bytes)

-- λ> length (valle2 [1..2*10^4])

-- 20000

-- (2.68 secs, 8,595,637,880 bytes)

-- λ> length (valle3 [1..2*10^4])

-- 20000

-- (2.67 secs, 8,594,678,104 bytes)

Caminos minimales en un árbol numérico

PorJosé A. Alonso 7-diciembre-201725-abril-2021

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

1	ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

λ> putStrLn (drawTree (fmap show ej))

+- 5

| |

| `- 9

`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

/ \

5 3

| |

4 2

/ \ |

3 2 1

| |

2 1

Definir las siguientes funciones

   mayoresDivisores :: Int -> [Int]
   arbol            :: Int -> Tree Int
   caminos          :: Int -> [[Int]]
   caminosMinimales :: Int -> [[Int]]

mayoresDivisores :: Int -> [Int]

arbol :: Int -> Tree Int

caminos :: Int -> [[Int]]

caminosMinimales :: Int -> [[Int]]

tales que

(mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

     mayoresDivisores 24  ==  [12,8,6]
     mayoresDivisores 16  ==  [8,4]
     mayoresDivisores 10  ==  [5]
     mayoresDivisores 17  ==  []

mayoresDivisores 24 == [12,8,6]

mayoresDivisores 16 == [8,4]

mayoresDivisores 10 == [5]

mayoresDivisores 17 == []

(arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbol 6)))
     6
     |
     +- 5
     |  |
     |  `- 4
     |     |
     |     +- 3
     |     |  |
     |     |  `- 2
     |     |     |
     |     |     `- 1
     |     |
     |     `- 2
     |        |
     |        `- 1
     |
     `- 3
        |
        `- 2
           |
           `- 1

λ> putStrLn (drawTree (fmap show (arbol 6)))

+- 5

| |

| `- 4

| |

| +- 3

| | |

| | `- 2

| | |

| | `- 1

| |

| `- 2

| |

| `- 1

`- 3

`- 2

`- 1

(caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminos 6
     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

1 2	λ> caminos 6 [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

(caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminosMinimales 6
     [[6,3,2,1]]
     λ> caminosMinimales 17
     [[17,16,4,2,1]]
     λ> caminosMinimales 50
     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

λ> caminosMinimales 6

[[6,3,2,1]]

λ> caminosMinimales 17

[[17,16,4,2,1]]

λ> caminosMinimales 50

[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Soluciones

import Data.Tree

mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  [max u v | u <- [2..floor (sqrt (fromIntegral x))]
           , x `mod` u == 0
           , let v = x `div` u]  

arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]
caminos = caminosArbol . arbol

--    λ> caminosArbol (arbol 6)
--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
caminosArbol :: Tree a -> [[a]]
caminosArbol (Node x []) = [[x]]
caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]
caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ys | ys <- yss, length ys == m]
  where yss = caminos x
        m   = minimum (map length yss)

import Data.Tree

mayoresDivisores :: Int -> [Int]

mayoresDivisores x =

[max u v | u <- [2..floor (sqrt (fromIntegral x))]

, x `mod` u == 0

, let v = x `div` u]

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]

caminos = caminosArbol . arbol

-- λ> caminosArbol (arbol 6)

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

caminosArbol :: Tree a -> [[a]]

caminosArbol (Node x []) = [[x]]

caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]

caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = [ys | ys <- yss, length ys == m]

where yss = caminos x

m = minimum (map length yss)

Máximo de las rotaciones restringidas

PorJosé A. Alonso 6-diciembre-201713-diciembre-2017

Rotar un número a la iquierda significa pasar su primer dígito al final. Por ejemplo, rotando a la izquierda el 56789 se obtiene 67895.

Las rotaciones restringidas del número 56789 se obtienen como se indica a continución:

Se inicia con el propio número: 56789
El anterior se rota a la izquierda y se obtiene el 67895.
Del anterior se fija el primer dígito y se rota a la iquierda los otros. Se obtiene 68957.
Del anterior se fijan los 2 primeros dígito y se rota a la iquierda los otros. Se obtiene 68579.
Del anterior se fijan los 3 primeros dígito y se rota a la iquierda los otros. Se obtiene 68597.

El proceso ha terminado ya que conservando los cuatro primeros queda sólo un dígito que al girar es él mismo. Por tanto, la sucesión de las rotaciones restringidas de 56789 es

   56789 -> 67895 -> 68957 -> 68579 -> 68597

1	56789 -> 67895 -> 68957 -> 68579 -> 68597

y su mayor elemento es 68957.

Definir la función

   maxRotaciones :: Integer -> Integer

1	maxRotaciones :: Integer -> Integer

tal que (maxRotaciones n) es el máximo de las rotaciones restringidas del número n. Por ejemplo,

   maxRotaciones 56789       ==  68957
   maxRotaciones 1347902468  ==  3790246814
   maxRotaciones 6           ==  6
   maxRotaciones 2017        ==  2017

maxRotaciones 56789 == 68957

maxRotaciones 1347902468 == 3790246814

maxRotaciones 6 == 6

maxRotaciones 2017 == 2017

Soluciones

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

maxRotaciones :: Integer -> Integer
maxRotaciones = read . aux . show
  where aux n@[_]        = n
        aux n@(x1:x2:xs) = max n (x2:aux (xs ++ [x1]))

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

maxRotaciones2 :: Integer -> Integer
maxRotaciones2 n
  | n < 10    = n
  | otherwise = maximum [ read (us ++ vs)
                        | (us,vs) <- take m (iterate siguiente ("",xs)) ]
  where xs = show n
        m  = length xs

-- siguiente ("","56789")  ==  ("6","7895")
-- siguiente ("6","7895")  ==  ("68","957")
-- siguiente ("68","957")  ==  ("685","79")
-- siguiente ("685","79")  ==  ("6859","7")
-- siguiente ("6859","7")  ==  ("6859","7")
siguiente :: (String,String) -> (String,String)
siguiente (xs,a:b:ys) = (xs ++ [b], ys ++ [a])
siguiente (xs,[a])    = (xs,[a])

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

maxRotaciones3 :: Integer -> Integer
maxRotaciones3 = read . aux . show
  where aux (x:y:xs) | x > y     = x : y : xs
                     | otherwise = y : (aux $ xs ++ [x])
        aux [x]                  = [x]
        aux _                    = []

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

--    λ> length (show (maxRotaciones (n (5*10^3))))
--    5001
--    (2.74 secs, 802,282,616 bytes)
--    λ> length (show (maxRotaciones2 (n (5*10^3))))
--    5001
--    (18.23 secs, 12,375,579,216 bytes)
--    λ> length (show (maxRotaciones3 (n (5*10^3))))
--    5001
--    (0.67 secs, 729,155,056 bytes)

-- 1ª solución

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

maxRotaciones :: Integer -> Integer

maxRotaciones = read . aux . show

where aux n@[_] = n

aux n@(x1:x2:xs) = max n (x2:aux (xs ++ [x1]))

-- 2ª solución

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

maxRotaciones2 :: Integer -> Integer

maxRotaciones2 n

| n < 10 = n

| otherwise = maximum [ read (us ++ vs)

| (us,vs) <- take m (iterate siguiente ("",xs)) ]

where xs = show n

m = length xs

-- siguiente ("","56789") == ("6","7895")

-- siguiente ("6","7895") == ("68","957")

-- siguiente ("68","957") == ("685","79")

-- siguiente ("685","79") == ("6859","7")

-- siguiente ("6859","7") == ("6859","7")

siguiente :: (String,String) -> (String,String)

siguiente (xs,a:b:ys) = (xs ++ [b], ys ++ [a])

siguiente (xs,[a]) = (xs,[a])

-- 3ª solución

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

maxRotaciones3 :: Integer -> Integer

maxRotaciones3 = read . aux . show

where aux (x:y:xs) | x > y = x : y : xs

| otherwise = y : (aux $ xs ++ [x])

aux [x] = [x]

aux _ = []

-- Comparación de eficiencia

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

-- λ> length (show (maxRotaciones (n (5*10^3))))

-- 5001

-- (2.74 secs, 802,282,616 bytes)

-- λ> length (show (maxRotaciones2 (n (5*10^3))))

-- 5001

-- (18.23 secs, 12,375,579,216 bytes)

-- λ> length (show (maxRotaciones3 (n (5*10^3))))

-- 5001

-- (0.67 secs, 729,155,056 bytes)

Aplicación de lista de funciones a lista de elementos

PorJosé A. Alonso 5-diciembre-201712-diciembre-2017

Definir la función

   aplicaLista :: [a -> b] -> [a] -> [b]

1	aplicaLista :: [a -> b] -> [a] -> [b]

tal que (aplicaLista fs xs) es la lista de los valores de las funciones de fs
aplicadas a los correspondientes elementos de xs. Por ejemplo,

   aplicaLista [(+2),(`div` 3),(*5)] [4,6,2]    ==  [6,2,10]
   aplicaLista [(+2),(`div` 3),(*5)] [4,6,2,8]  ==  [6,2,10]
   aplicaLista [(>2),(==3),(<5)]     [4,6,2,9]  ==  [True,False,True]

aplicaLista [(+2),(`div` 3),(*5)] [4,6,2] == [6,2,10]

aplicaLista [(+2),(`div` 3),(*5)] [4,6,2,8] == [6,2,10]

aplicaLista [(>2),(==3),(<5)] [4,6,2,9] == [True,False,True]

Soluciones

-- 1ª definición (por comprensión)
aplicaLista :: [a -> b] -> [a] -> [b]
aplicaLista fs xs =
  [f x | (f,x) <- zip fs xs]

-- 2ª definición (por recursión)
aplicaLista2 :: [a -> b] -> [a] -> [b]
aplicaLista2 (f:fs) (x:xs) = f x : aplicaLista2 fs xs
aplicaLista2 _      _     = []

-- 3ª definición (por orden superior)
aplicaLista3 :: [a -> b] -> [a] -> [b]
aplicaLista3 = zipWith ($)

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

aplicaLista :: [a -> b] -> [a] -> [b]

aplicaLista fs xs =

[f x | (f,x) <- zip fs xs]

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

aplicaLista2 :: [a -> b] -> [a] -> [b]

aplicaLista2 (f:fs) (x:xs) = f x : aplicaLista2 fs xs

aplicaLista2 _ _ = []

-- 3ª definición (por orden superior)

aplicaLista3 :: [a -> b] -> [a] -> [b]

aplicaLista3 = zipWith ($)

Mayúsculas y minúsculas alternadas

PorJosé A. Alonso 4-diciembre-201712-diciembre-2017

Definir la función

   alternadas :: String -> (String,String)

1	alternadas :: String -> (String,String)

tal que (alternadas cs) es el par de cadenas (xs,ys) donde xs es la cadena obtenida escribiendo alternativamente en mayúscula o minúscula las letras de la palabra cs (que se supone que es una cadena de letras minúsculas) e ys se obtiene análogamente pero empezando en minúscula. Por ejemplo,

   λ> alternadas "salamandra"
   ("SaLaMaNdRa","sAlAmAnDrA")
   λ> alternadas "solosequenosenada"
   ("SoLoSeQuEnOsEnAdA","sOlOsEqUeNoSeNaDa")
   λ> alternadas (replicate 30 'a')
   ("AaAaAaAaAaAaAaAaAaAaAaAaAaAaAa","aAaAaAaAaAaAaAaAaAaAaAaAaAaAaA")

λ> alternadas "salamandra"

("SaLaMaNdRa","sAlAmAnDrA")

λ> alternadas "solosequenosenada"

("SoLoSeQuEnOsEnAdA","sOlOsEqUeNoSeNaDa")

λ> alternadas (replicate 30 'a')

("AaAaAaAaAaAaAaAaAaAaAaAaAaAaAa","aAaAaAaAaAaAaAaAaAaAaAaAaAaAaA")

Soluciones

import Data.Char (toUpper)

-- 1ª solución
alternadas :: String -> (String,String)
alternadas []     = ([],[])
alternadas (x:xs) = (toUpper x : zs, x : ys)
  where (ys,zs) = alternadas xs

-- 2ª solución
alternadas2 :: String -> (String,String)
alternadas2 xs =
  ( [f x | (f,x) <- zip (cycle [toUpper,id]) xs]
  , [f x | (f,x) <- zip (cycle [id,toUpper]) xs]
  )

-- Comparación de eficiencia
--    λ> import Data.List
--    λ> let (xs,ys) = alternadas (replicate (10^6) 'a') in nub (xs ++ ys)
--    "Aa"
--    (4.81 secs, 616,143,320 bytes)
--    λ> let (xs,ys) = alternadas2 (replicate (10^6) 'a') in nub (xs ++ ys)
--    "Aa"
--    (3.23 secs, 528,144,752 bytes)

import Data.Char (toUpper)

-- 1ª solución

alternadas :: String -> (String,String)

alternadas [] = ([],[])

alternadas (x:xs) = (toUpper x : zs, x : ys)

where (ys,zs) = alternadas xs

-- 2ª solución

alternadas2 :: String -> (String,String)

alternadas2 xs =

( [f x | (f,x) <- zip (cycle [toUpper,id]) xs]

, [f x | (f,x) <- zip (cycle [id,toUpper]) xs]

)

-- Comparación de eficiencia

-- λ> import Data.List

-- λ> let (xs,ys) = alternadas (replicate (10^6) 'a') in nub (xs ++ ys)

-- "Aa"

-- (4.81 secs, 616,143,320 bytes)

-- λ> let (xs,ys) = alternadas2 (replicate (10^6) 'a') in nub (xs ++ ys)

-- "Aa"

-- (3.23 secs, 528,144,752 bytes)

Conjunto de funciones entre dos conjuntos

PorJosé A. Alonso 1-diciembre-20178-diciembre-2017

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

[(1,2),(3,6)] es una función de [1,3] en [2,4,6];
[(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
[(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir las funciones

   funciones  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
   nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

1 2	funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]] nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

(funciones xs ys) es el conjunto de las funciones del conjunto xs en el conjunto ys. Por ejemplo,

     λ> funciones [1] [2]
     [[(1,2)]]
     λ> funciones [1] [2,4]
     [[(1,2)],[(1,4)]]
     λ> funciones [1,3] [2]
     [[(1,2),(3,2)]]
     λ> funciones [1,3] [2,4]
     [[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]
     λ> funciones [1,3] [2,4,6]
     [[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],
      [(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],
      [(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]
     λ> funciones [1,3,5] [2,4]
     [[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],
      [(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],
      [(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]
     λ> funciones [] []
     [[]]
     λ> funciones [] [2]
     [[]]
     λ> funciones [1] []
     []

λ> funciones [1] [2]

[[(1,2)]]

λ> funciones [1] [2,4]

[[(1,2)],[(1,4)]]

λ> funciones [1,3] [2]

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

λ> funciones [1,3] [2,4]

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

λ> funciones [1,3] [2,4,6]

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

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

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

λ> funciones [1,3,5] [2,4]

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

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

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

λ> funciones [] []

[[]]

λ> funciones [] [2]

[[]]

λ> funciones [1] []

[]

(nFunciones xs ys) es el número de funciones del conjunto xs en el conjunto ys. Por ejemplo,

     nFunciones [1,3] [2,4,6]  ==  9
     nFunciones [1,3,5] [2,4]  ==  8
     length (show (nFunciones2 [1..10^6] [1..10^3]))  ==  3000001

nFunciones [1,3] [2,4,6] == 9

nFunciones [1,3,5] [2,4] == 8

length (show (nFunciones2 [1..10^6] [1..10^3])) == 3000001

Soluciones

import Data.List (genericLength, nub, sort, subsequences)

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

funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones xs ys =
  conjunto [r | r <- relaciones xs ys
              , esFuncion r xs ys]

-- (relaciones xs ys) es el conjunto de las relaciones binarias entre xs
-- e ys. Por ejemplo,
--    λ> relaciones [1,3] [2,4]
--    [[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],
--     [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],
--     [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],
--     [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],
--     [(1,2),(1,4),(3,2),(3,4)]]
relaciones :: [a] -> [b] -> [[(a,b)]]
relaciones xs ys =
  subsequences (producto xs ys)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,
--    producto [1,3] [2,4]  ==  [(1,2),(1,4),(3,2),(3,4)]
producto :: [a] -> [b] -> [(a,b)]
producto xs ys =
  [(x,y) | x <- xs, y <- ys]

-- (esFuncional r) r se verifica si la relación r es funcional. Por
-- ejemplo, 
--    esFuncional [(2,4),(1,5),(3,4)]        ==  True
--    esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False
esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
esFuncional r =
  and [esUnitario (imagen r x) | x <- dominio r] 

-- (dominio r) es el dominio de la relación r. Por ejemplo,
--    dominio [(5,4),(1,4),(1,2),(3,4)]  ==  [1,3,5]
dominio :: Ord a => [(a,b)] -> [a]
dominio = sort . nub . map fst

-- (imagen r x) es la imagen de x en la relación r. Por ejemplo,
--    imagen [(5,4),(1,4),(1,2),(3,4)] 1  ==  [2,4]
--    imagen [(5,4),(1,4),(1,2),(3,4)] 2  ==  []
imagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b]
imagen r x =
  conjunto [y | (x1,y) <- r, x1 == x]

-- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos
-- distintos) correspondiente a la lista xs. Por ejemplo, 
--    conjunto [7,2,3,2,7,3]  ==  [2,3,7]
conjunto :: Ord a => [a] -> [a]
conjunto = sort . nub

-- (esUnitario xs) se verifica si xs tiene sólo un elemento.
esUnitario :: [a] -> Bool
esUnitario xs =
  length xs == 1

-- (esFuncion r xs ys) se verifica si r es una función con dominio xs y
-- codominio ys. Por ejemplo,
--    esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,5,7]   ==  True
--    esFuncion [(2,4),(1,5),(3,4)] [1,3] [4,5,7]     ==  False
--    esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,7]     ==  False
--    esFuncion [(1,4),(1,5),(3,4)] [1,2,3] [4,5,7]   ==  False
esFuncion :: (Ord a, Ord b) => [(a,b)] -> [a] -> [b] -> Bool
esFuncion r xs ys =
     conjunto xs == dominio r 
  && rango r `contenido` conjunto ys
  && esFuncional r

-- (rango r) es el rango de la relación r. Por ejemplo,
--    rango [(5,4),(1,4),(1,2),(3,4)]  ==  [2,4]
rango :: Ord b => [(a,b)] -> [b]
rango = sort . nub . map snd

-- (contenido xs ys) se verifica si el conjunto xs está contenido en el
-- ys. Por ejemplo,
--    [1,3] `contenido` [1,2,3,5]  ==  True
--    [1,3] `contenido` [1,2,4,5]  ==  False
contenido :: Ord a => [a] -> [a] -> Bool 
contenido xs ys =
  all (`elem` ys) xs

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

funciones2 :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones2 xs ys =
  conjunto (aux xs ys)
  where aux [] _      = [[]]
        aux [x] ys    = [[(x,y)] | y <- ys]
        aux (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]
          where fs = aux xs ys

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

--    λ> length (funciones [1..4] [1..4]) 
--    256
--    (2.69 secs, 754,663,072 bytes)
--    λ> length (funciones2 [1..4] [1..4]) 
--    256
--    (0.04 secs, 243,600 bytes)

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

nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys =
  genericLength (funciones2 xs ys)

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

nFunciones2 :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones2 xs ys =
  (genericLength ys)^(genericLength xs)

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

--    λ> nFunciones [1..5] [1..5] 
--    3125
--    (1.35 secs, 1,602,872 bytes)
--    λ> nFunciones2 [1..5] [1..5] 
--    3125
--    (0.03 secs, 140,480 bytes)

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

import Data.List (genericLength, nub, sort, subsequences)

-- 1ª definición de funciones

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

funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]

funciones xs ys =

conjunto [r | r <- relaciones xs ys

, esFuncion r xs ys]

-- (relaciones xs ys) es el conjunto de las relaciones binarias entre xs

-- e ys. Por ejemplo,

-- λ> relaciones [1,3] [2,4]

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

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

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

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

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

relaciones :: [a] -> [b] -> [[(a,b)]]

relaciones xs ys =

subsequences (producto xs ys)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,

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

producto :: [a] -> [b] -> [(a,b)]

producto xs ys =

[(x,y) | x <- xs, y <- ys]

-- (esFuncional r) r se verifica si la relación r es funcional. Por

-- ejemplo,

-- esFuncional [(2,4),(1,5),(3,4)] == True

-- esFuncional [(3,4),(1,4),(1,2),(3,4)] == False

esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool

esFuncional r =

and [esUnitario (imagen r x) | x <- dominio r]

-- (dominio r) es el dominio de la relación r. Por ejemplo,

-- dominio [(5,4),(1,4),(1,2),(3,4)] == [1,3,5]

dominio :: Ord a => [(a,b)] -> [a]

dominio = sort . nub . map fst

-- (imagen r x) es la imagen de x en la relación r. Por ejemplo,

-- imagen [(5,4),(1,4),(1,2),(3,4)] 1 == [2,4]

-- imagen [(5,4),(1,4),(1,2),(3,4)] 2 == []

imagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b]

imagen r x =

conjunto [y | (x1,y) <- r, x1 == x]

-- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos

-- distintos) correspondiente a la lista xs. Por ejemplo,

-- conjunto [7,2,3,2,7,3] == [2,3,7]

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

conjunto = sort . nub

-- (esUnitario xs) se verifica si xs tiene sólo un elemento.

esUnitario :: [a] -> Bool

esUnitario xs =

length xs == 1

-- (esFuncion r xs ys) se verifica si r es una función con dominio xs y

-- codominio ys. Por ejemplo,

-- esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,5,7] == True

-- esFuncion [(2,4),(1,5),(3,4)] [1,3] [4,5,7] == False

-- esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,7] == False

-- esFuncion [(1,4),(1,5),(3,4)] [1,2,3] [4,5,7] == False

esFuncion :: (Ord a, Ord b) => [(a,b)] -> [a] -> [b] -> Bool

esFuncion r xs ys =

conjunto xs == dominio r

&& rango r `contenido` conjunto ys

&& esFuncional r

-- (rango r) es el rango de la relación r. Por ejemplo,

-- rango [(5,4),(1,4),(1,2),(3,4)] == [2,4]

rango :: Ord b => [(a,b)] -> [b]

rango = sort . nub . map snd

-- (contenido xs ys) se verifica si el conjunto xs está contenido en el

-- ys. Por ejemplo,

-- [1,3] `contenido` [1,2,3,5] == True

-- [1,3] `contenido` [1,2,4,5] == False

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

contenido xs ys =

all (`elem` ys) xs

-- 2ª definición de funciones

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

funciones2 :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]

funciones2 xs ys =

conjunto (aux xs ys)

where aux [] _ = [[]]

aux [x] ys = [[(x,y)] | y <- ys]

aux (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]

where fs = aux xs ys

-- Comparación de eficiencia de funciones

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

-- λ> length (funciones [1..4] [1..4])

-- 256

-- (2.69 secs, 754,663,072 bytes)

-- λ> length (funciones2 [1..4] [1..4])

-- 256

-- (0.04 secs, 243,600 bytes)

-- 1ª definición de nFunciones

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

nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

nFunciones xs ys =

genericLength (funciones2 xs ys)

-- 2ª definición de nFunciones

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

nFunciones2 :: (Ord a, Ord b) => [a] -> [b] -> Integer

nFunciones2 xs ys =

(genericLength ys)^(genericLength xs)

-- Comparación de eficiencia de nFunciones

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

-- λ> nFunciones [1..5] [1..5]

-- 3125

-- (1.35 secs, 1,602,872 bytes)

-- λ> nFunciones2 [1..5] [1..5]

-- 3125

-- (0.03 secs, 140,480 bytes)

Expresiones equilibradas

PorJosé A. Alonso 30-noviembre-20178-diciembre-2017

Una cadena de paréntesis abiertos y cerrados está equilibrada si a cada paréntesis abierto le corresponde uno cerrado y los restantes están equilibrados. Por ejemplo, «(()())» está equilibrada, pero «())(()» no lo está.

Definir la función

   equilibrada :: String -> Bool

1	equilibrada :: String -> Bool

tal que (equilibrada cs) se verifica si la cadena cs está equilibrada. Por ejemplo,

   equilibrada "(()())"          ==  True
   equilibrada "())(()"          ==  False
   equilibrada "()"              ==  True
   equilibrada ")(()))"          ==  False
   equilibrada "("               ==  False
   equilibrada "(())((()())())"  == True

equilibrada "(()())" == True

equilibrada "())(()" == False

equilibrada "()" == True

equilibrada ")(()))" == False

equilibrada "(" == False

equilibrada "(())((()())())" == True

Soluciones

import Data.List (foldl')
import Test.Hspec

-- 1ª definición
equilibrada :: String -> Bool
equilibrada = aux 0 where
  aux 0 []       = True
  aux n ('(':cs) = aux (n + 1) cs 
  aux n (')':cs) = n > 0 && aux (n - 1) cs 
  aux _ _        = False

-- 2ª definición
equilibrada2 :: String -> Bool
equilibrada2 = aux 0 where
  aux n []       = n == 0
  aux n ('(':ps) = aux (n+1) ps
  aux n (')':ps) = n > 0 && aux (n-1) ps

-- 3ª definición
equilibrada3 :: String -> Bool
equilibrada3 xs = null $ foldl' op [] xs where
  op ('(':xs) ')' = xs
  op xs x = x:xs

import Data.List (foldl')

import Test.Hspec

-- 1ª definición

equilibrada :: String -> Bool

equilibrada = aux 0 where

aux 0 [] = True

aux n ('(':cs) = aux (n + 1) cs

aux n (')':cs) = n > 0 && aux (n - 1) cs

aux _ _ = False

-- 2ª definición

equilibrada2 :: String -> Bool

equilibrada2 = aux 0 where

aux n [] = n == 0

aux n ('(':ps) = aux (n+1) ps

aux n (')':ps) = n > 0 && aux (n-1) ps

-- 3ª definición

equilibrada3 :: String -> Bool

equilibrada3 xs = null $ foldl' op [] xs where

op ('(':xs) ')' = xs

op xs x = x:xs

Menor x tal que los x múltiplos de n contienen todos los dígitos

PorJosé A. Alonso 28-noviembre-20178-diciembre-2017

Definir la función

   menorX :: Integer -> Integer

1	menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, … y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

   92                                    contiene  [2,9]
   92 y 92×2                             contienen [1,2,4,8,9]
   92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
   92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

92 contiene [2,9]

92 y 92×2 contienen [1,2,4,8,9]

92, 92×2 y 92×3 contienen [1,2,4,6,7,8,9]

92, 92×2, 92×3 y 92×4 contienen [1,2,3,4,6,7,8,9]

92, 92×2, 92×3, 92×4 y 92×5 contienen [0,1,2,3,4,6,7,8,9]

92, 92×2, 92×3, 92×4, 92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

   menorX 92          ==  6
   menorX 2967        ==  3
   menorX 266         ==  4
   menorX 18          ==  5
   menorX 2           ==  45
   menorX 125         ==  72
   menorX 1234567890  ==  1
   maximum [menorX n | n <- [1..3000]]  ==  72
   minimum [menorX n | n <- [1..3000]]  ==  3

menorX 92 == 6

menorX 2967 == 3

menorX 266 == 4

menorX 18 == 5

menorX 2 == 45

menorX 125 == 72

menorX 1234567890 == 1

maximum [menorX n | n <- [1..3000]] == 72

minimum [menorX n | n <- [1..3000]] == 3

Soluciones

import Data.List ((\\))

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

menorX :: Integer -> Integer
menorX n =
  head [x | x <- [1..]
          , [0..9] `contenido` digitosMultiplos n x]

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

digitosMultiplos :: Integer -> Integer -> [Integer]
digitosMultiplos n x =
  concatMap digitos [n,2*n..x*n]

digitos :: Integer -> [Integer]
digitos n =
  [read [c] | c <- show n]

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

menorX2 :: Integer -> Integer
menorX2 n = aux [] 0
  where aux xs x
          | [0..9] `contenido` xs = x
          | otherwise             = aux (digitos (n*(x+1)) ++ xs) (x+1)

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

menorX3 :: Integer -> Integer
menorX3 n = aux ['0'..'9'] 0
  where aux xs x
          | null xs   = x
          | otherwise = aux (xs \\ show (n*(x+1))) (x+1)

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

menorX4 :: Integer -> Integer
menorX4 n = aux "0123456789" 1 n
  where aux xs x nx | null ys   = x
                    | otherwise = aux ys (1+x) (nx+n)
          where ys = xs \\ show nx

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

--    λ> maximum [menorX n | n <- [1..6000]]
--    72
--    (2.04 secs, 3,737,579,888 bytes)
--    λ> maximum [menorX2 n | n <- [1..6000]]
--    72
--    (0.52 secs, 818,602,736 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.10 secs, 67,090,800 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.08 secs, 67,090,800 bytes)
--    
--    λ> maximum [menorX3 n | n <- [1..10^5]]
--    72
--    (0.81 secs, 1,044,781,216 bytes)
--    λ> maximum [menorX4 n | n <- [1..10^5]]
--    72
--    (0.71 secs, 1,009,113,304 bytes)

import Data.List ((\\))

-- 1ª definición

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

menorX :: Integer -> Integer

menorX n =

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

, [0..9] `contenido` digitosMultiplos n x]

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

contenido xs ys =

all (`elem` ys) xs

digitosMultiplos :: Integer -> Integer -> [Integer]

digitosMultiplos n x =

concatMap digitos [n,2*n..x*n]

digitos :: Integer -> [Integer]

digitos n =

[read [c] | c <- show n]

-- 2ª definición

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

menorX2 :: Integer -> Integer

menorX2 n = aux [] 0

where aux xs x

| [0..9] `contenido` xs = x

| otherwise = aux (digitos (n*(x+1)) ++ xs) (x+1)

-- 3ª definición

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

menorX3 :: Integer -> Integer

menorX3 n = aux ['0'..'9'] 0

where aux xs x

| null xs = x

| otherwise = aux (xs \\ show (n*(x+1))) (x+1)

-- 4ª definición

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

menorX4 :: Integer -> Integer

menorX4 n = aux "0123456789" 1 n

where aux xs x nx | null ys = x

| otherwise = aux ys (1+x) (nx+n)

where ys = xs \\ show nx

-- Comparación de eficiencia

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

-- λ> maximum [menorX n | n <- [1..6000]]

-- 72

-- (2.04 secs, 3,737,579,888 bytes)

-- λ> maximum [menorX2 n | n <- [1..6000]]

-- 72

-- (0.52 secs, 818,602,736 bytes)

-- λ> maximum [menorX3 n | n <- [1..6000]]

-- 72

-- (0.10 secs, 67,090,800 bytes)

-- λ> maximum [menorX3 n | n <- [1..6000]]

-- 72

-- (0.08 secs, 67,090,800 bytes)

-- λ> maximum [menorX3 n | n <- [1..10^5]]

-- 72

-- (0.81 secs, 1,044,781,216 bytes)

-- λ> maximum [menorX4 n | n <- [1..10^5]]

-- 72

-- (0.71 secs, 1,009,113,304 bytes)

Sumas de dos cuadrados

PorJosé A. Alonso 24-noviembre-20174-diciembre-2017

Definir la función

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

1	sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

   sumasDe2Cuadrados 25                ==  [(5,0),(4,3)]
   sumasDe2Cuadrados 32                ==  [(4,4)]
   sumasDe2Cuadrados 55                ==  []
   sumasDe2Cuadrados 850               ==  [(29,3),(27,11),(25,15)]
   length (sumasDe2Cuadrados (10^12))  ==  7

sumasDe2Cuadrados 25 == [(5,0),(4,3)]

sumasDe2Cuadrados 32 == [(4,4)]

sumasDe2Cuadrados 55 == []

sumasDe2Cuadrados 850 == [(29,3),(27,11),(25,15)]

length (sumasDe2Cuadrados (10^12)) == 7

Soluciones

-- 1ª definición
sumasDe2Cuadrados1 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados1 n = 
  [(x,y) | x <- [n,n-1..0]
         , y <- [0..x]
         , x*x+y*y == n]

-- 2ª definición:
sumasDe2Cuadrados2 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados2 n = 
  [(x,y) | x <- [a,a-1..0]
         , y <- [0..x]
         , x*x+y*y == n]
  where a = (floor . sqrt . fromIntegral) n

-- 3ª definición
sumasDe2Cuadrados3 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados3 n =
  [(raizEntera x, raizEntera y)
  | y <- takeWhile (<= n `div` 2) cuadrados
  , let x = n - y
  , esCuadrado x]

cuadrados :: [Integer]
cuadrados = map (^2) [0..]

esCuadrado :: Integer -> Bool
esCuadrado x =
  x == y * y
  where y = raizEntera x
  
raizEntera :: Integer -> Integer
raizEntera x =
  (floor . sqrt . fromIntegral) x

-- 4ª definición
sumasDe2Cuadrados4 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados4 n = aux ((floor . sqrt . fromIntegral) n) 0 
  where aux x y | x < y          = [] 
                | x*x + y*y <  n = aux x (y+1)
                | x*x + y*y == n = (x,y) : aux (x-1) (y+1)
                | otherwise      = aux (x-1) y

-- Comparación de eficiencia
--    λ> sumasDe2Cuadrados1 2020
--    [(42,16),(38,24)]
--    (4.29 secs, 621,601,336 bytes)
--    λ> sumasDe2Cuadrados2 2020
--    [(42,16),(38,24)]
--    (0.01 secs, 488,496 bytes)
--    λ> sumasDe2Cuadrados3 2020
--    [(42,16),(38,24)]
--    (0.02 secs, 197,256 bytes)
--    λ> sumasDe2Cuadrados4 2020
--    [(42,16),(38,24)]
--    (0.01 secs, 175,088 bytes)
--
--    λ> length (sumasDe2Cuadrados2 48612265)
--    32
--    (51.25 secs, 7,395,035,904 bytes)
--    λ> length (sumasDe2Cuadrados3 48612265)
--    32
--    (0.06 secs, 8,368,296 bytes)
--    λ> length (sumasDe2Cuadrados4 48612265)
--    32
--    (0.04 secs, 3,483,168 bytes)
--    
--    λ> length (sumasDe2Cuadrados3 (10^12))
--    7
--    (7.32 secs, 1,137,167,688 bytes)
--    λ> length (sumasDe2Cuadrados4 (10^12))
--    7
--    (3.64 secs, 480,776,736 bytes)

-- 1ª definición

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

sumasDe2Cuadrados1 n =

[(x,y) | x <- [n,n-1..0]

, y <- [0..x]

, x*x+y*y == n]

-- 2ª definición:

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

sumasDe2Cuadrados2 n =

[(x,y) | x <- [a,a-1..0]

, y <- [0..x]

, x*x+y*y == n]

where a = (floor . sqrt . fromIntegral) n

-- 3ª definición

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

sumasDe2Cuadrados3 n =

[(raizEntera x, raizEntera y)

| y <- takeWhile (<= n `div` 2) cuadrados

, let x = n - y

, esCuadrado x]

cuadrados :: [Integer]

cuadrados = map (^2) [0..]

esCuadrado :: Integer -> Bool

esCuadrado x =

x == y * y

where y = raizEntera x

raizEntera :: Integer -> Integer

raizEntera x =

(floor . sqrt . fromIntegral) x

-- 4ª definición

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

sumasDe2Cuadrados4 n = aux ((floor . sqrt . fromIntegral) n) 0

where aux x y | x < y = []

| x*x + y*y < n = aux x (y+1)

| x*x + y*y == n = (x,y) : aux (x-1) (y+1)

| otherwise = aux (x-1) y

-- Comparación de eficiencia

-- λ> sumasDe2Cuadrados1 2020

-- [(42,16),(38,24)]

-- (4.29 secs, 621,601,336 bytes)

-- λ> sumasDe2Cuadrados2 2020

-- [(42,16),(38,24)]

-- (0.01 secs, 488,496 bytes)

-- λ> sumasDe2Cuadrados3 2020

-- [(42,16),(38,24)]

-- (0.02 secs, 197,256 bytes)

-- λ> sumasDe2Cuadrados4 2020

-- [(42,16),(38,24)]

-- (0.01 secs, 175,088 bytes)

-- λ> length (sumasDe2Cuadrados2 48612265)

-- 32

-- (51.25 secs, 7,395,035,904 bytes)

-- λ> length (sumasDe2Cuadrados3 48612265)

-- 32

-- (0.06 secs, 8,368,296 bytes)

-- λ> length (sumasDe2Cuadrados4 48612265)

-- 32

-- (0.04 secs, 3,483,168 bytes)

-- λ> length (sumasDe2Cuadrados3 (10^12))

-- 7

-- (7.32 secs, 1,137,167,688 bytes)

-- λ> length (sumasDe2Cuadrados4 (10^12))

-- 7

-- (3.64 secs, 480,776,736 bytes)

[/schedule]

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico