foldr1

Matriz de mínimas distancias

PorJosé A. Alonso 22-abril-202029-abril-2020

Definir las funciones

   minimasDistancias             :: Matrix Int -> Matrix Int
   sumaMinimaDistanciasIdentidad :: Int -> Int

1 2	minimasDistancias :: Matrix Int -> Matrix Int sumaMinimaDistanciasIdentidad :: Int -> Int

tales que

(mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

     λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])
     ( 1 0 0 )
     ( 2 1 0 )
     λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])
     ( 1 1 0 )
     ( 0 1 1 )
     λ> minimasDistancias (identity 5)
     ( 0 1 2 3 4 )
     ( 1 0 1 2 3 )
     ( 2 1 0 1 2 )
     ( 3 2 1 0 1 )
     ( 4 3 2 1 0 )

λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])

( 1 0 0 )

( 2 1 0 )

λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])

( 1 1 0 )

( 0 1 1 )

λ> minimasDistancias (identity 5)

( 0 1 2 3 4 )

( 1 0 1 2 3 )

( 2 1 0 1 2 )

( 3 2 1 0 1 )

( 4 3 2 1 0 )

(sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

     sumaMinimaDistanciasIdentidad 5       ==  40
     sumaMinimaDistanciasIdentidad (10^2)  ==  333300
     sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000
     sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000

sumaMinimaDistanciasIdentidad 5 == 40

sumaMinimaDistanciasIdentidad (10^2) == 333300

sumaMinimaDistanciasIdentidad (10^4) == 333333330000

sumaMinimaDistanciasIdentidad (10^6) == 333333333333000000

Soluciones

import Data.Matrix     
import Data.Maybe      
import Test.QuickCheck 

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

minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias a = 
  matrix (nrows a) (ncols a) (\(i,j) -> minimaDistancia (i,j) a) 
 
minimaDistancia :: (Int,Int) -> Matrix Int -> Int
minimaDistancia (a,b) p =
  minimum [distancia (a,b) (c,d) | (c,d) <- unos p]
 
unos :: Matrix Int -> [(Int,Int)]
unos p = [(i,j) | i <- [1..nrows p]
                , j <- [1..ncols p]
                , p ! (i,j) == 1]
 
distancia :: (Int,Int) -> (Int,Int) -> Int
distancia (a,b) (c,d) = abs (c - a) + abs (d - b)

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

minimasDistancias2 :: Matrix Int -> Matrix Int
minimasDistancias2 a = fmap fromJust (aux (matrizInicial a))
  where aux b | Nothing `elem` c = aux c
              | otherwise        = c
          where c = propagacion b

-- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de
-- a iguales a 1 y Nothing en los restantes. Por ejemplo,
--    λ> matrizInicial (fromLists [[0,0,1],[1,0,0]])
--    ( Nothing Nothing  Just 0 )
--    (  Just 0 Nothing Nothing )
matrizInicial :: Matrix Int -> Matrix (Maybe Int)
matrizInicial a = matrix m n f
  where m = nrows a
        n = ncols a
        f (i,j) | a ! (i,j) == 1 = Just 0
                | otherwise      = Nothing

-- (propagacion a) es la matriz obtenida cambiando los elementos Nothing
-- de a por el siguiente del mínimo de los valores de sus vecinos. Por
-- ejemplo,
--    λ> propagacion (fromLists [[0,1,1],[0,0,1]])
--    (  Just 1  Just 0  Just 0 )
--    ( Nothing  Just 1  Just 0 )
--    
--    λ> propagacion it
--    ( Just 1 Just 0 Just 0 )
--    ( Just 2 Just 1 Just 0 )
propagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int)
propagacion a = matrix m n f
  where
    m = nrows a
    n = ncols a
    f (i,j) | isJust x  = x
            | otherwise = siguiente (minimo (valoresVecinos a (i,j)))
      where x = a ! (i,j)

-- (valoresVecinos a p) es la lista de los valores de los vecinos la
-- posición p en la matriz a. Por ejemplo,             
--    λ> a = fromList 3 4 [1..]
--    λ> a
--    (  1  2  3  4 )
--    (  5  6  7  8 )
--    (  9 10 11 12 )
--    
--    λ> valoresVecinos a (1,1)
--    [5,2]
--    λ> valoresVecinos a (2,3)
--    [3,11,6,8]
--    λ> valoresVecinos a (2,4)
--    [4,12,7]
valoresVecinos :: Matrix a -> (Int,Int) -> [a]
valoresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)]
  where m = nrows a
        n = ncols a

-- (vecinos m n p) es la lista de las posiciones vecinas de la posición
-- p en la matriz a; es decir, los que se encuentran a su izquierda,
-- derecha, arriba o abajo. por ejemplo,
--    vecinos 3 4 (1,1)  ==  [(2,1),(1,2)]
--    vecinos 3 4 (2,3)  ==  [(1,3),(3,3),(2,2),(2,4)]
--    vecinos 3 4 (2,4)  ==  [(1,4),(3,4),(2,3)]
vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]
vecinos m n (i,j) = [(i - 1,j)     | i > 1] ++
                    [(i + 1,j)     | i < m] ++
                    [(i,    j - 1) | j > 1] ++
                    [(i,    j + 1) | j < n]

-- (minimo xs) es el mínimo de la lista de valores opcionales xs
-- (considerando Nothing como el mayor elemento). Por ejemplo,
--    minimo [Just 3, Nothing, Just 2]  ==  Just 2
minimo :: [Maybe Int] -> Maybe Int
minimo = foldr1 minimo2

-- (minimo2 x y) es el mínimo de los valores opcionales x e y
-- (considerando Nothing como el mayor elemento). Por ejemplo,
--    minimo2 (Just 3) (Just 2)  ==  Just 2
--    minimo2 (Just 1) (Just 2)  ==  Just 1
--    minimo2 (Just 1) Nothing   ==  Just 1
--    minimo2 Nothing (Just 2)   ==  Just 2
--    minimo2 Nothing Nothing    ==  Nothing
minimo2 :: Maybe Int -> Maybe Int -> Maybe Int
minimo2 (Just x) (Just y) = Just (min x y)
minimo2 Nothing  (Just y) = Just y
minimo2 (Just x) Nothing  = Just x
minimo2 Nothing  Nothing  = Nothing

-- (siguiente x) es el siguiente elemento del opcional x (considerando
-- Nothing como el infinito). Por ejemplo, 
--    siguiente (Just 3)  ==  Just 4
--    siguiente Nothing  ==  Nothing
siguiente :: Maybe Int -> Maybe Int
siguiente (Just x) = Just (1 + x)
siguiente Nothing  = Nothing

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

-- La comparación es
--    λ> maximum (minimasDistancias (identity 40))
--    39
--    (3.85 secs, 654,473,496 bytes)
--    λ> maximum (minimasDistancias2 (identity 40))
--    39
--    (0.50 secs, 75,079,912 bytes)

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

sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n =
  sum (minimasDistancias (identity n))

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

sumaMinimaDistanciasIdentidad2 :: Int -> Int
sumaMinimaDistanciasIdentidad2 n =
  n*(n^2-1) `div` 3

-- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad
-- =================================================================

-- La propiedad es
prop_MinimaDistanciasIdentidad :: Positive Int -> Bool
prop_MinimaDistanciasIdentidad (Positive n) =
  sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> sumaMinimaDistanciasIdentidad 50
--    41650
--    (0.24 secs, 149,395,744 bytes)
--    λ> sumaMinimaDistanciasIdentidad 100
--    333300
--    (1.98 secs, 1,294,676,272 bytes)
--    λ> sumaMinimaDistanciasIdentidad 200
--    2666600
--    (17.96 secs, 11,094,515,016 bytes)
--    
--    λ> sumaMinimaDistanciasIdentidad2 50
--    41650
--    (0.00 secs, 126,944 bytes)
--    λ> sumaMinimaDistanciasIdentidad2 100
--    333300
--    (0.00 secs, 126,872 bytes)
--    λ> sumaMinimaDistanciasIdentidad2 200
--    2666600
--    (0.00 secs, 131,240 bytes)
--
-- Resumidamente, el tiempo es
--
--    +-----+---------+--------+
--    |   n | 1ª def. | 2ª def |
--    +-----+---------+--------+
--    |  50 |  0.24   | 0.00   |
--    | 100 |  1.98   | 0.00   |
--    | 200 | 17.96   | 0.00   | 
--    +-----+---------+--------+

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

import Data.Matrix

import Data.Maybe

import Test.QuickCheck

-- 1ª definición de minimasDistancias

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

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias a =

matrix (nrows a) (ncols a) (\(i,j) -> minimaDistancia (i,j) a)

minimaDistancia :: (Int,Int) -> Matrix Int -> Int

minimaDistancia (a,b) p =

minimum [distancia (a,b) (c,d) | (c,d) <- unos p]

unos :: Matrix Int -> [(Int,Int)]

unos p = [(i,j) | i <- [1..nrows p]

, j <- [1..ncols p]

, p ! (i,j) == 1]

distancia :: (Int,Int) -> (Int,Int) -> Int

distancia (a,b) (c,d) = abs (c - a) + abs (d - b)

-- 2ª definición de minimasDistancias

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

minimasDistancias2 :: Matrix Int -> Matrix Int

minimasDistancias2 a = fmap fromJust (aux (matrizInicial a))

where aux b | Nothing `elem` c = aux c

| otherwise = c

where c = propagacion b

-- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de

-- a iguales a 1 y Nothing en los restantes. Por ejemplo,

-- λ> matrizInicial (fromLists [[0,0,1],[1,0,0]])

-- ( Nothing Nothing Just 0 )

-- ( Just 0 Nothing Nothing )

matrizInicial :: Matrix Int -> Matrix (Maybe Int)

matrizInicial a = matrix m n f

where m = nrows a

n = ncols a

f (i,j) | a ! (i,j) == 1 = Just 0

| otherwise = Nothing

-- (propagacion a) es la matriz obtenida cambiando los elementos Nothing

-- de a por el siguiente del mínimo de los valores de sus vecinos. Por

-- ejemplo,

-- λ> propagacion (fromLists [[0,1,1],[0,0,1]])

-- ( Just 1 Just 0 Just 0 )

-- ( Nothing Just 1 Just 0 )

-- λ> propagacion it

-- ( Just 1 Just 0 Just 0 )

-- ( Just 2 Just 1 Just 0 )

propagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int)

propagacion a = matrix m n f

where

m = nrows a

n = ncols a

f (i,j) | isJust x = x

| otherwise = siguiente (minimo (valoresVecinos a (i,j)))

where x = a ! (i,j)

-- (valoresVecinos a p) es la lista de los valores de los vecinos la

-- posición p en la matriz a. Por ejemplo,

-- λ> a = fromList 3 4 [1..]

-- λ> a

-- ( 1 2 3 4 )

-- ( 5 6 7 8 )

-- ( 9 10 11 12 )

-- λ> valoresVecinos a (1,1)

-- [5,2]

-- λ> valoresVecinos a (2,3)

-- [3,11,6,8]

-- λ> valoresVecinos a (2,4)

-- [4,12,7]

valoresVecinos :: Matrix a -> (Int,Int) -> [a]

valoresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)]

where m = nrows a

n = ncols a

-- (vecinos m n p) es la lista de las posiciones vecinas de la posición

-- p en la matriz a; es decir, los que se encuentran a su izquierda,

-- derecha, arriba o abajo. por ejemplo,

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

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

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

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

vecinos m n (i,j) = [(i - 1,j) | i > 1] ++

[(i + 1,j) | i < m] ++

[(i, j - 1) | j > 1] ++

[(i, j + 1) | j < n]

-- (minimo xs) es el mínimo de la lista de valores opcionales xs

-- (considerando Nothing como el mayor elemento). Por ejemplo,

-- minimo [Just 3, Nothing, Just 2] == Just 2

minimo :: [Maybe Int] -> Maybe Int

minimo = foldr1 minimo2

-- (minimo2 x y) es el mínimo de los valores opcionales x e y

-- (considerando Nothing como el mayor elemento). Por ejemplo,

-- minimo2 (Just 3) (Just 2) == Just 2

-- minimo2 (Just 1) (Just 2) == Just 1

-- minimo2 (Just 1) Nothing == Just 1

-- minimo2 Nothing (Just 2) == Just 2

-- minimo2 Nothing Nothing == Nothing

minimo2 :: Maybe Int -> Maybe Int -> Maybe Int

minimo2 (Just x) (Just y) = Just (min x y)

minimo2 Nothing (Just y) = Just y

minimo2 (Just x) Nothing = Just x

minimo2 Nothing Nothing = Nothing

-- (siguiente x) es el siguiente elemento del opcional x (considerando

-- Nothing como el infinito). Por ejemplo,

-- siguiente (Just 3) == Just 4

-- siguiente Nothing == Nothing

siguiente :: Maybe Int -> Maybe Int

siguiente (Just x) = Just (1 + x)

siguiente Nothing = Nothing

-- Comparación de eficiencia

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

-- La comparación es

-- λ> maximum (minimasDistancias (identity 40))

-- 39

-- (3.85 secs, 654,473,496 bytes)

-- λ> maximum (minimasDistancias2 (identity 40))

-- 39

-- (0.50 secs, 75,079,912 bytes)

-- 1ª definición de sumaMinimaDistanciasIdentidad

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

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n =

sum (minimasDistancias (identity n))

-- 2ª definición de sumaMinimaDistanciasIdentidad

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

sumaMinimaDistanciasIdentidad2 :: Int -> Int

sumaMinimaDistanciasIdentidad2 n =

n*(n^2-1) `div` 3

-- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad

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

-- La propiedad es

prop_MinimaDistanciasIdentidad :: Positive Int -> Bool

prop_MinimaDistanciasIdentidad (Positive n) =

sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de sumaMinimaDistanciasIdentidad

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

-- La comparación es

-- λ> sumaMinimaDistanciasIdentidad 50

-- 41650

-- (0.24 secs, 149,395,744 bytes)

-- λ> sumaMinimaDistanciasIdentidad 100

-- 333300

-- (1.98 secs, 1,294,676,272 bytes)

-- λ> sumaMinimaDistanciasIdentidad 200

-- 2666600

-- (17.96 secs, 11,094,515,016 bytes)

-- λ> sumaMinimaDistanciasIdentidad2 50

-- 41650

-- (0.00 secs, 126,944 bytes)

-- λ> sumaMinimaDistanciasIdentidad2 100

-- 333300

-- (0.00 secs, 126,872 bytes)

-- λ> sumaMinimaDistanciasIdentidad2 200

-- 2666600

-- (0.00 secs, 131,240 bytes)

-- Resumidamente, el tiempo es

-- +-----+---------+--------+

-- | n | 1ª def. | 2ª def |

-- +-----+---------+--------+

-- | 50 | 0.24 | 0.00 |

-- | 100 | 1.98 | 0.00 |

-- | 200 | 17.96 | 0.00 |

-- +-----+---------+--------+

Otras soluciones

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

Menor divisible por todos

PorJosé A. Alonso 28-noviembre-20195-diciembre-2019

Definir la función

   menorDivisible :: Integer -> Integer -> Integer

1	menorDivisible :: Integer -> Integer -> Integer

tal que (menorDivisible a b) es el menor número divisible por todos los números desde a hasta b, ambos inclusive. Por ejemplo,

   menorDivisible 1 10                        ==  2520
   length (show (menorDivisible 1 (3*10^5)))  ==  130141

1 2	menorDivisible 1 10 == 2520 length (show (menorDivisible 1 (3*10^5))) == 130141

Nota: Este ejercicio está basado en el problema 5 del Proyecto Euler

Soluciones

import Data.List (foldl')

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

menorDivisible :: Integer -> Integer -> Integer
menorDivisible a b =
  head [x | x <- [b..]
          , and [x `mod` y == 0 | y <- [a..b]]]

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

menorDivisible2 :: Integer -> Integer -> Integer
menorDivisible2 a b  
  | a == b    = a
  | otherwise = lcm a (menorDivisible (a+1) b)

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

menorDivisible3 :: Integer -> Integer -> Integer
menorDivisible3 a b = foldl lcm 1 [a..b] 

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

menorDivisible4 :: Integer -> Integer -> Integer
menorDivisible4 a b = foldl1 lcm [a..b] 

-- 5ª solución
-- ===========

menorDivisible5 :: Integer -> Integer -> Integer
menorDivisible5 a b = foldl' lcm 1 [a..b] 

-- 6ª solución
-- ===========

menorDivisible6 :: Integer -> Integer -> Integer
menorDivisible6 a b = foldr1 lcm [a..b] 

-- 7ª solución
-- ===========

menorDivisible7 :: Integer -> Integer -> Integer
menorDivisible7 a = foldr1 lcm . enumFromTo a

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

--   λ> menorDivisible 1 17
--   12252240
--   (18.63 secs, 15,789,475,488 bytes)
--   λ> menorDivisible2 1 17
--   12252240
--   (13.29 secs, 11,868,764,272 bytes)
--   λ> menorDivisible3 1 17
--   12252240
--   (0.00 secs, 114,688 bytes)
--   λ> menorDivisible4 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible5 1 17
--   12252240
--   (0.01 secs, 110,640 bytes)
--   λ> menorDivisible6 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible7 1 17
--   12252240
--   (0.00 secs, 110,912 bytes)
--   
--   λ> length (show (menorDivisible3 1 (10^5)))
--   43452
--   (1.54 secs, 2,021,887,000 bytes)
--   λ> length (show (menorDivisible4 1 (10^5)))
--   43452
--   (1.47 secs, 2,021,886,616 bytes)
--   λ> length (show (menorDivisible5 1 (10^5)))
--   43452
--   (0.65 secs, 2,009,595,568 bytes)
--   λ> length (show (menorDivisible6 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,840 bytes)
--   λ> length (show (menorDivisible7 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,920 bytes)
--   
--   λ> length (show (menorDivisible5 1 (2*10^5)))
--   86871
--   (2.47 secs, 7,989,147,304 bytes)
--   λ> length (show (menorDivisible6 1 (2*10^5)))
--   86871
--   (0.89 secs, 533,876,496 bytes)
--   λ> length (show (menorDivisible7 1 (2*10^5)))
--   86871
--   (0.88 secs, 533,875,608 bytes)

import Data.List (foldl')

-- 1ª solución

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

menorDivisible :: Integer -> Integer -> Integer

menorDivisible a b =

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

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

-- 2ª solución

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

menorDivisible2 :: Integer -> Integer -> Integer

menorDivisible2 a b

| a == b = a

| otherwise = lcm a (menorDivisible (a+1) b)

-- 3ª solución

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

menorDivisible3 :: Integer -> Integer -> Integer

menorDivisible3 a b = foldl lcm 1 [a..b]

-- 4ª solución

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

menorDivisible4 :: Integer -> Integer -> Integer

menorDivisible4 a b = foldl1 lcm [a..b]

-- 5ª solución

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

menorDivisible5 :: Integer -> Integer -> Integer

menorDivisible5 a b = foldl' lcm 1 [a..b]

-- 6ª solución

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

menorDivisible6 :: Integer -> Integer -> Integer

menorDivisible6 a b = foldr1 lcm [a..b]

-- 7ª solución

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

menorDivisible7 :: Integer -> Integer -> Integer

menorDivisible7 a = foldr1 lcm . enumFromTo a

-- Comparación de eficiencia

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

-- λ> menorDivisible 1 17

-- 12252240

-- (18.63 secs, 15,789,475,488 bytes)

-- λ> menorDivisible2 1 17

-- 12252240

-- (13.29 secs, 11,868,764,272 bytes)

-- λ> menorDivisible3 1 17

-- 12252240

-- (0.00 secs, 114,688 bytes)

-- λ> menorDivisible4 1 17

-- 12252240

-- (0.01 secs, 114,752 bytes)

-- λ> menorDivisible5 1 17

-- 12252240

-- (0.01 secs, 110,640 bytes)

-- λ> menorDivisible6 1 17

-- 12252240

-- (0.01 secs, 114,752 bytes)

-- λ> menorDivisible7 1 17

-- 12252240

-- (0.00 secs, 110,912 bytes)

-- λ> length (show (menorDivisible3 1 (10^5)))

-- 43452

-- (1.54 secs, 2,021,887,000 bytes)

-- λ> length (show (menorDivisible4 1 (10^5)))

-- 43452

-- (1.47 secs, 2,021,886,616 bytes)

-- λ> length (show (menorDivisible5 1 (10^5)))

-- 43452

-- (0.65 secs, 2,009,595,568 bytes)

-- λ> length (show (menorDivisible6 1 (10^5)))

-- 43452

-- (0.30 secs, 172,986,840 bytes)

-- λ> length (show (menorDivisible7 1 (10^5)))

-- 43452

-- (0.30 secs, 172,986,920 bytes)

-- λ> length (show (menorDivisible5 1 (2*10^5)))

-- 86871

-- (2.47 secs, 7,989,147,304 bytes)

-- λ> length (show (menorDivisible6 1 (2*10^5)))

-- 86871

-- (0.89 secs, 533,876,496 bytes)

-- λ> length (show (menorDivisible7 1 (2*10^5)))

-- 86871

-- (0.88 secs, 533,875,608 bytes)

Pensamiento

Será el peor de los malos
bribón que olvide
su vocación de diablo.

Antonio Machado

Matriz de mínimas distancias

PorJosé A. Alonso 22-marzo-201925-abril-2021

Definir las funciones

   minimasDistancias             :: Matrix Int -> Matrix Int
   sumaMinimaDistanciasIdentidad :: Int -> Int

1 2	minimasDistancias :: Matrix Int -> Matrix Int sumaMinimaDistanciasIdentidad :: Int -> Int

tales que

(mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

     λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])
     ( 1 0 0 )
     ( 2 1 0 )
     λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])
     ( 1 1 0 )
     ( 0 1 1 )
     λ> minimasDistancias (identity 5)
     ( 0 1 2 3 4 )
     ( 1 0 1 2 3 )
     ( 2 1 0 1 2 )
     ( 3 2 1 0 1 )
     ( 4 3 2 1 0 )

λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])

( 1 0 0 )

( 2 1 0 )

λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])

( 1 1 0 )

( 0 1 1 )

λ> minimasDistancias (identity 5)

( 0 1 2 3 4 )

( 1 0 1 2 3 )

( 2 1 0 1 2 )

( 3 2 1 0 1 )

( 4 3 2 1 0 )

(sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

     sumaMinimaDistanciasIdentidad 5       ==  40
     sumaMinimaDistanciasIdentidad (10^2)  ==  333300
     sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000
     sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000

sumaMinimaDistanciasIdentidad 5 == 40

sumaMinimaDistanciasIdentidad (10^2) == 333300

sumaMinimaDistanciasIdentidad (10^4) == 333333330000

sumaMinimaDistanciasIdentidad (10^6) == 333333333333000000

Soluciones

import Data.Matrix
import Data.Maybe (isJust, fromJust)
import Test.QuickCheck

-- Definición de minimasDistancias
-- ===============================

minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias a = fmap fromJust (aux (matrizInicial a))
  where aux b | Nothing `elem` c = aux c
              | otherwise        = c
          where c = propagacion b

-- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de
-- a iguales a 1 y Nothing en los restantes. Por ejemplo,
--    λ> matrizInicial (fromLists [[0,0,1],[1,0,0]])
--    ( Nothing Nothing  Just 0 )
--    (  Just 0 Nothing Nothing )
matrizInicial :: Matrix Int -> Matrix (Maybe Int)
matrizInicial a = matrix m n f
  where m = nrows a
        n = ncols a
        f (i,j) | a ! (i,j) == 1 = Just 0
                | otherwise      = Nothing

-- (propagacion a) es la matriz obtenida cambiando los elementos Nothing
-- de a por el sigiente del mínomo de los valores de sus vecinos. Por
-- ejemplo,
--    λ> propagacion (fromLists [[0,1,1],[0,0,1]])
--    (  Just 1  Just 0  Just 0 )
--    ( Nothing  Just 1  Just 0 )
--    
--    λ> propagacion it
--    ( Just 1 Just 0 Just 0 )
--    ( Just 2 Just 1 Just 0 )
propagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int)
propagacion a = matrix m n f
  where
    m = nrows a
    n = ncols a
    f (i,j) | isJust x  = x
            | otherwise = siguiente (minimo (valoresVecinos a (i,j)))
      where x = a ! (i,j)

-- (valoresVecinos a p) es la lista de los valores de los vecinos la
-- posición p en la matriz a. Por ejemplo,             
--    λ> a = fromList 3 4 [1..]
--    λ> a
--    (  1  2  3  4 )
--    (  5  6  7  8 )
--    (  9 10 11 12 )
--    
--    λ> valoresVecinos a (1,1)
--    [5,2]
--    λ> valoresVecinos a (2,3)
--    [3,11,6,8]
--    λ> valoresVecinos a (2,4)
--    [4,12,7]
valoresVecinos :: Matrix a -> (Int,Int) -> [a]
valoresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)]
  where m = nrows a
        n = ncols a

-- (vecinos m n p) es la lista de las posiciones vecinas de la posición
-- p en la matriz a; es decir, los que se encuentran a su izquierda,
-- derecha, arriba o abajo. por ejemplo,
--    vecinos 3 4 (1,1)  ==  [(2,1),(1,2)]
--    vecinos 3 4 (2,3)  ==  [(1,3),(3,3),(2,2),(2,4)]
--    vecinos 3 4 (2,4)  ==  [(1,4),(3,4),(2,3)]
vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]
vecinos m n (i,j) = [(i - 1,j)     | i > 1] ++
                    [(i + 1,j)     | i < m] ++
                    [(i,    j - 1) | j > 1] ++
                    [(i,    j + 1) | j < n]

-- (minimo xs) es el mínimo de la lista de valores opcionales xs
-- (considerando Nothing como el mayor elemento). Por ejemplo,
--    minimo [Just 3, Nothing, Just 2]  ==  Just 2
minimo :: [Maybe Int] -> Maybe Int
minimo = foldr1 minimo2

-- (minimo2 x y) es el mínimo de los valores opcionales x e y
-- (considerando Nothing como el mayor elemento). Por ejemplo,
--    minimo2 (Just 3) (Just 2)  ==  Just 2
--    minimo2 (Just 1) (Just 2)  ==  Just 1
--    minimo2 (Just 1) Nothing   ==  Just 1
--    minimo2 Nothing (Just 2)   ==  Just 2
--    minimo2 Nothing Nothing    ==  Nothing
minimo2 :: Maybe Int -> Maybe Int -> Maybe Int
minimo2 (Just x) (Just y) = Just (min x y)
minimo2 Nothing  (Just y) = Just y
minimo2 (Just x) Nothing  = Just x
minimo2 Nothing  Nothing  = Nothing

-- (siguiente x) es el siguiente elemento del opcional x (considerando
-- Nothing como el infinito). Por ejemplo, 
--    siguiente (Just 3)  ==  Just 4
--    siguiente Nothing  ==  Nothing
siguiente :: Maybe Int -> Maybe Int
siguiente (Just x) = Just (1 + x)
siguiente Nothing  = Nothing

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

sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n =
  sum (minimasDistancias (identity n))

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

sumaMinimaDistanciasIdentidad2 :: Int -> Int
sumaMinimaDistanciasIdentidad2 n =
  n*(n^2-1) `div` 3

-- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad
-- =================================================================

-- La propiedad es
prop_MinimaDistanciasIdentidad :: Positive Int -> Bool
prop_MinimaDistanciasIdentidad (Positive n) =
  sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> sumaMinimaDistanciasIdentidad 50
--    41650
--    (0.24 secs, 149,395,744 bytes)
--    λ> sumaMinimaDistanciasIdentidad 100
--    333300
--    (1.98 secs, 1,294,676,272 bytes)
--    λ> sumaMinimaDistanciasIdentidad 200
--    2666600
--    (17.96 secs, 11,094,515,016 bytes)
--    
--    λ> sumaMinimaDistanciasIdentidad2 50
--    41650
--    (0.00 secs, 126,944 bytes)
--    λ> sumaMinimaDistanciasIdentidad2 100
--    333300
--    (0.00 secs, 126,872 bytes)
--    λ> sumaMinimaDistanciasIdentidad2 200
--    2666600
--    (0.00 secs, 131,240 bytes)
--
-- Resumidamente, el tiempo es
--
--    +-----+---------+--------+
--    |   n | 1ª def. | 2ª def |
--    +-----+---------+--------+
--    |  50 |  0.24   | 0.00   |
--    | 100 |  1.98   | 0.00   |
--    | 200 | 17.96   | 0.00   | 
--    +-----+---------+--------+

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

import Data.Matrix

import Data.Maybe (isJust, fromJust)

import Test.QuickCheck

-- Definición de minimasDistancias

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

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias a = fmap fromJust (aux (matrizInicial a))

where aux b | Nothing `elem` c = aux c

| otherwise = c

where c = propagacion b

-- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de

-- a iguales a 1 y Nothing en los restantes. Por ejemplo,

-- λ> matrizInicial (fromLists [[0,0,1],[1,0,0]])

-- ( Nothing Nothing Just 0 )

-- ( Just 0 Nothing Nothing )

matrizInicial :: Matrix Int -> Matrix (Maybe Int)

matrizInicial a = matrix m n f

where m = nrows a

n = ncols a

f (i,j) | a ! (i,j) == 1 = Just 0

| otherwise = Nothing

-- (propagacion a) es la matriz obtenida cambiando los elementos Nothing

-- de a por el sigiente del mínomo de los valores de sus vecinos. Por

-- ejemplo,

-- λ> propagacion (fromLists [[0,1,1],[0,0,1]])

-- ( Just 1 Just 0 Just 0 )

-- ( Nothing Just 1 Just 0 )

-- λ> propagacion it

-- ( Just 1 Just 0 Just 0 )

-- ( Just 2 Just 1 Just 0 )

propagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int)

propagacion a = matrix m n f

where

m = nrows a

n = ncols a

f (i,j) | isJust x = x

| otherwise = siguiente (minimo (valoresVecinos a (i,j)))

where x = a ! (i,j)

-- (valoresVecinos a p) es la lista de los valores de los vecinos la

-- posición p en la matriz a. Por ejemplo,

-- λ> a = fromList 3 4 [1..]

-- λ> a

-- ( 1 2 3 4 )

-- ( 5 6 7 8 )

-- ( 9 10 11 12 )

-- λ> valoresVecinos a (1,1)

-- [5,2]

-- λ> valoresVecinos a (2,3)

-- [3,11,6,8]

-- λ> valoresVecinos a (2,4)

-- [4,12,7]

valoresVecinos :: Matrix a -> (Int,Int) -> [a]

valoresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)]

where m = nrows a

n = ncols a

-- (vecinos m n p) es la lista de las posiciones vecinas de la posición

-- p en la matriz a; es decir, los que se encuentran a su izquierda,

-- derecha, arriba o abajo. por ejemplo,

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

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

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

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

vecinos m n (i,j) = [(i - 1,j) | i > 1] ++

[(i + 1,j) | i < m] ++

[(i, j - 1) | j > 1] ++

[(i, j + 1) | j < n]

-- (minimo xs) es el mínimo de la lista de valores opcionales xs

-- (considerando Nothing como el mayor elemento). Por ejemplo,

-- minimo [Just 3, Nothing, Just 2] == Just 2

minimo :: [Maybe Int] -> Maybe Int

minimo = foldr1 minimo2

-- (minimo2 x y) es el mínimo de los valores opcionales x e y

-- (considerando Nothing como el mayor elemento). Por ejemplo,

-- minimo2 (Just 3) (Just 2) == Just 2

-- minimo2 (Just 1) (Just 2) == Just 1

-- minimo2 (Just 1) Nothing == Just 1

-- minimo2 Nothing (Just 2) == Just 2

-- minimo2 Nothing Nothing == Nothing

minimo2 :: Maybe Int -> Maybe Int -> Maybe Int

minimo2 (Just x) (Just y) = Just (min x y)

minimo2 Nothing (Just y) = Just y

minimo2 (Just x) Nothing = Just x

minimo2 Nothing Nothing = Nothing

-- (siguiente x) es el siguiente elemento del opcional x (considerando

-- Nothing como el infinito). Por ejemplo,

-- siguiente (Just 3) == Just 4

-- siguiente Nothing == Nothing

siguiente :: Maybe Int -> Maybe Int

siguiente (Just x) = Just (1 + x)

siguiente Nothing = Nothing

-- 1ª definición de sumaMinimaDistanciasIdentidad

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

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n =

sum (minimasDistancias (identity n))

-- 2ª definición de sumaMinimaDistanciasIdentidad

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

sumaMinimaDistanciasIdentidad2 :: Int -> Int

sumaMinimaDistanciasIdentidad2 n =

n*(n^2-1) `div` 3

-- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad

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

-- La propiedad es

prop_MinimaDistanciasIdentidad :: Positive Int -> Bool

prop_MinimaDistanciasIdentidad (Positive n) =

sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> sumaMinimaDistanciasIdentidad 50

-- 41650

-- (0.24 secs, 149,395,744 bytes)

-- λ> sumaMinimaDistanciasIdentidad 100

-- 333300

-- (1.98 secs, 1,294,676,272 bytes)

-- λ> sumaMinimaDistanciasIdentidad 200

-- 2666600

-- (17.96 secs, 11,094,515,016 bytes)

-- λ> sumaMinimaDistanciasIdentidad2 50

-- 41650

-- (0.00 secs, 126,944 bytes)

-- λ> sumaMinimaDistanciasIdentidad2 100

-- 333300

-- (0.00 secs, 126,872 bytes)

-- λ> sumaMinimaDistanciasIdentidad2 200

-- 2666600

-- (0.00 secs, 131,240 bytes)

-- Resumidamente, el tiempo es

-- +-----+---------+--------+

-- | n | 1ª def. | 2ª def |

-- +-----+---------+--------+

-- | 50 | 0.24 | 0.00 |

-- | 100 | 1.98 | 0.00 |

-- | 200 | 17.96 | 0.00 |

-- +-----+---------+--------+

Pensamiento

La primavera ha venido.
Nadie sabe como ha sido.

Antonio Machado

Mayor exponente

PorJosé A. Alonso 20-febrero-201927-febrero-2019

Definir las funciones

   mayorExponente        :: Integer -> Integer
   graficaMayorExponente :: Integer -> IO ()

1 2	mayorExponente :: Integer -> Integer graficaMayorExponente :: Integer -> IO ()

tales que

(mayorExponente n) es el mayor número b para el que existe un a tal que n = a^b. Se supone que n > 1. Por ejemplo,

     mayorExponente 9   ==  2
     mayorExponente 8   ==  3
     mayorExponente 7   ==  1
     mayorExponente 18  ==  1
     mayorExponente 36  ==  2
     mayorExponente (10^(10^5))  ==  100000

mayorExponente 9 == 2

mayorExponente 8 == 3

mayorExponente 7 == 1

mayorExponente 18 == 1

mayorExponente 36 == 2

mayorExponente (10^(10^5)) == 100000

(graficaMayorExponente n) dibuja la gráfica de los mayores exponentes de los números entre 2 y n. Por ejemplo, (graficaMayorExponente 50) dibuja

Soluciones

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


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

mayorExponente :: Integer -> Integer
mayorExponente x =
  last [b | b <- [1..x]
          , a <- [1..x]
          , a^b == x]

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

mayorExponente2 :: Integer -> Integer
mayorExponente2 x =
  head [b | b <- [x,x-1..1]
          , a <- [1..x]
          , a^b == x]

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

mayorExponente3 :: Integer -> Integer
mayorExponente3 x = aux x
  where aux 1 = 1
        aux b | any (\a -> a^b == x) [1..x] = b
              | otherwise                   = aux (b-1)

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

mayorExponente4 :: Integer -> Integer
mayorExponente4 x =
  mcd (exponentes x)

-- (exponentes x) es la lista de los exponentes en la factorizacioń de
-- x. por ejemplo.
--    exponentes 720  ==  [4,2,1]
exponentes :: Integer -> [Integer]
exponentes x =
  map genericLength (group (primeFactors x))

-- (mcd xs) es el máximo común divisor de xs. Por ejemplo,
--    mcd [4,6,10]  ==  2
mcd :: [Integer] -> Integer
mcd = foldr1 gcd

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_mayorExponente :: Integer -> Property
prop_mayorExponente n =
  n >= 0 ==>
  mayorExponente  n == mayorExponente2 n &&
  mayorExponente2 n == mayorExponente3 n

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

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

--    λ> mayorExponente (10^3)
--    3
--    (3.96 secs, 4,671,928,464 bytes)
--    λ> mayorExponente2 (10^3)
--    3
--    (3.99 secs, 4,670,107,024 bytes)
--    λ> mayorExponente3 (10^3)
--    3
--    (3.90 secs, 4,686,383,952 bytes)
--    λ> mayorExponente4 (10^3)
--    3
--    (0.02 secs, 131,272 bytes)

-- Definición de graficaMayorExponente
-- ======================================

graficaMayorExponente :: Integer -> IO ()
graficaMayorExponente n = 
  plotList [ Key Nothing
           , PNG ("MayorExponente.png")
           ]
           (map mayorExponente3 [2..n])

import Data.List (genericLength, group)

import Data.Numbers.Primes (primeFactors)

import Test.QuickCheck

import Graphics.Gnuplot.Simple

-- 1ª solución

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

mayorExponente :: Integer -> Integer

mayorExponente x =

last [b | b <- [1..x]

, a <- [1..x]

, a^b == x]

-- 2ª solución

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

mayorExponente2 :: Integer -> Integer

mayorExponente2 x =

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

, a <- [1..x]

, a^b == x]

-- 3ª solución

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

mayorExponente3 :: Integer -> Integer

mayorExponente3 x = aux x

where aux 1 = 1

aux b | any (\a -> a^b == x) [1..x] = b

| otherwise = aux (b-1)

-- 4ª solución

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

mayorExponente4 :: Integer -> Integer

mayorExponente4 x =

mcd (exponentes x)

-- (exponentes x) es la lista de los exponentes en la factorizacioń de

-- x. por ejemplo.

-- exponentes 720 == [4,2,1]

exponentes :: Integer -> [Integer]

exponentes x =

map genericLength (group (primeFactors x))

-- (mcd xs) es el máximo común divisor de xs. Por ejemplo,

-- mcd [4,6,10] == 2

mcd :: [Integer] -> Integer

mcd = foldr1 gcd

-- Comprobación de equivalencia

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

-- La propiedad es

prop_mayorExponente :: Integer -> Property

prop_mayorExponente n =

n >= 0 ==>

mayorExponente n == mayorExponente2 n &&

mayorExponente2 n == mayorExponente3 n

-- La comprobación es

-- λ> quickCheck prop_mayorExponente

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> mayorExponente (10^3)

-- 3

-- (3.96 secs, 4,671,928,464 bytes)

-- λ> mayorExponente2 (10^3)

-- 3

-- (3.99 secs, 4,670,107,024 bytes)

-- λ> mayorExponente3 (10^3)

-- 3

-- (3.90 secs, 4,686,383,952 bytes)

-- λ> mayorExponente4 (10^3)

-- 3

-- (0.02 secs, 131,272 bytes)

-- Definición de graficaMayorExponente

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

graficaMayorExponente :: Integer -> IO ()

graficaMayorExponente n =

plotList [ Key Nothing

, PNG ("MayorExponente.png")

]

(map mayorExponente3 [2..n])

Pensamiento

Mirando mi calavera
un nuevo Hamlet dirá:
He aquí un lindo fósil de una
careta de carnaval.

Antonio Machado

Números compuestos por un conjunto de primos

PorJosé A. Alonso 20-abril-201830-abril-2018

Los números compuestos por un conjunto de primos son los números cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros números compuestos por [2,5,7] son

   1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...

1	1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...

El 28 es compuesto ya que sus divisores primos son 2 y 7 que están en [2,5,7].

Definir la función

   compuestos :: [Integer] -> [Integer]

1	compuestos :: [Integer] -> [Integer]

tal que (compuesto ps) es la lista de los números compuestos por el conjunto de primos ps. Por ejemplo,

   λ> take 20 (compuestos [2,5,7])
   [1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]
   λ> take 20 (compuestos [2,5])
   [1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]
   λ> take 20 (compuestos [2,3,5])
   [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
   λ> take 20 (compuestos [3,5,7,11,13])
   [1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]
   λ> take 15 (compuestos [2])
   [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
   λ> compuestos [2,7] !! (10^4)
   57399514149595471961908157955229677377312712667508119466382354072731648
   λ> compuestos [2,3,5] !! (10^5)
   290237644800000000000000000000000000000

λ> take 20 (compuestos [2,5,7])

[1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]

λ> take 20 (compuestos [2,5])

[1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]

λ> take 20 (compuestos [2,3,5])

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

λ> take 20 (compuestos [3,5,7,11,13])

[1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]

λ> take 15 (compuestos [2])

[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]

λ> compuestos [2,7] !! (10^4)

57399514149595471961908157955229677377312712667508119466382354072731648

λ> compuestos [2,3,5] !! (10^5)

290237644800000000000000000000000000000

Soluciones

import Data.Numbers.Primes (primeFactors)

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

compuestos1 :: [Integer] -> [Integer]
compuestos1 ps =
  [n | n <- [1..], esCompuesto ps n]

-- (esCompuesto ps n) se verifica si los factores primos de n pertenecen
-- a ps. Por ejemplo, 
--    esCompuesto [2,3,7]    28  ==  True
--    esCompuesto [2,3,7]   140  ==  False
--    esCompuesto [2,3,5,7] 140  ==  True
esCompuesto :: [Integer] -> Integer -> Bool
esCompuesto ps n =
  subconjunto (primeFactors n) ps

-- (subconjunto xs ys) se verifica si todos los elementos de xs
-- pertenecen a ys. Por ejemplo, 
--    subconjunto [2,7,2] [7,5,2]  ==  True
--    subconjunto [2,7,3] [7,5,2]  ==  False
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto xs ys =
  all (`elem` ys) xs

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

compuestos2 :: [Integer] -> [Integer]
compuestos2 ps =
   1 : mezclaTodas (combinaciones ps)

-- (combinaciones ps) es la lista de los productos de cada elemento de
-- ps por los números compuestos con ps. Por ejemplo,
--    λ> take 8 (compuestos4 [2,5,7])
--    [1,2,4,5,7,8,10,14]
--    λ> map (take 6) (combinaciones [2,5,7])
--    [[2,4,8,10,14,16],[5,10,20,25,35,40],[7,14,28,35,49,56]]
combinaciones :: [Integer] -> [[Integer]]
combinaciones ps =
  [[p * q | q <- compuestos2 ps] | p <- ps]

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo, 
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: [[Integer]] -> [Integer]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista
-- ordenadas xs e ys. Por ejemplo,  
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla []     ys              = ys
mezcla xs     []              = xs
mezcla us@(x:xs) vs@(y:ys) | x == y     = x : mezcla xs ys
                           | x < y      = x : mezcla xs vs
                           | otherwise  = y : mezcla us ys

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

compuestos3 :: [Integer] -> [Integer]
compuestos3 [] = [1]
compuestos3 (p:ps) =
  mezclaTodas [map (*y) (compuestos3 ps) | y <- [p^k | k <- [0..]]]

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

compuestos4 :: [Integer] -> [Integer]
compuestos4 ps = foldl aux xs (tail ps)
  where p        = head ps
        xs       = [p^k | k <- [0..]]
        aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 5ª solución
-- ===========

compuestos5 :: [Integer] -> [Integer]
compuestos5 = foldl aux [1] 
  where aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 6ª solución
-- ===========

compuestos6 :: [Integer] -> [Integer]
compuestos6 xs = aux
  where aux = 1 : mezclas xs aux
        mezclas []     _  = []
        mezclas (x:xs) zs = mezcla (map (x*) zs) (mezclas xs zs)

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

--    λ> compuestos1 [2,3,5] !! 300
--    84375
--    (5.85 secs, 2,961,101,088 bytes)
--    λ> compuestos2 [2,3,5] !! 300
--    84375
--    (3.54 secs, 311,137,952 bytes)
--    λ> compuestos2 [2,3,5] !! 400
--    312500
--    (13.01 secs, 1,229,801,184 bytes)
--    λ> compuestos3 [2,3,5] !! 400
--    312500
--    (0.02 secs, 2,066,152 bytes)
--    λ> compuestos3 [2,3,5] !! 20000
--    15441834907098675000000
--    (1.57 secs, 203,061,864 bytes)
--    λ> compuestos4 [2,3,5] !! 20000
--    15441834907098675000000
--    (0.40 secs, 53,335,080 bytes)
--    λ> compuestos4 [2,3,5] !! 50000
--    2379528690747474604574166220800
--    (1.25 secs, 170,058,496 bytes)
--    λ> compuestos5 [2,3,5] !! 50000
--    2379528690747474604574166220800
--    (1.26 secs, 170,104,648 bytes)
--    λ> compuestos6 [2,3,5] !! 50000
--    2379528690747474604574166220800
--    (0.26 secs, 40,490,280 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

import Data.Numbers.Primes (primeFactors)

-- 1ª solución

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

compuestos1 :: [Integer] -> [Integer]

compuestos1 ps =

[n | n <- [1..], esCompuesto ps n]

-- (esCompuesto ps n) se verifica si los factores primos de n pertenecen

-- a ps. Por ejemplo,

-- esCompuesto [2,3,7] 28 == True

-- esCompuesto [2,3,7] 140 == False

-- esCompuesto [2,3,5,7] 140 == True

esCompuesto :: [Integer] -> Integer -> Bool

esCompuesto ps n =

subconjunto (primeFactors n) ps

-- (subconjunto xs ys) se verifica si todos los elementos de xs

-- pertenecen a ys. Por ejemplo,

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

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

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

subconjunto xs ys =

all (`elem` ys) xs

-- 2ª solución

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

compuestos2 :: [Integer] -> [Integer]

compuestos2 ps =

1 : mezclaTodas (combinaciones ps)

-- (combinaciones ps) es la lista de los productos de cada elemento de

-- ps por los números compuestos con ps. Por ejemplo,

-- λ> take 8 (compuestos4 [2,5,7])

-- [1,2,4,5,7,8,10,14]

-- λ> map (take 6) (combinaciones [2,5,7])

-- [[2,4,8,10,14,16],[5,10,20,25,35,40],[7,14,28,35,49,56]]

combinaciones :: [Integer] -> [[Integer]]

combinaciones ps =

[[p * q | q <- compuestos2 ps] | p <- ps]

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como

-- sus elementos son listas infinitas ordenadas. Por ejemplo,

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

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

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

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

mezclaTodas :: [[Integer]] -> [Integer]

mezclaTodas = foldr1 xmezcla

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

-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista

-- ordenadas xs e ys. Por ejemplo,

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

mezcla [] ys = ys

mezcla xs [] = xs

mezcla us@(x:xs) vs@(y:ys) | x == y = x : mezcla xs ys

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- 3ª solución

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

compuestos3 :: [Integer] -> [Integer]

compuestos3 [] = [1]

compuestos3 (p:ps) =

mezclaTodas [map (*y) (compuestos3 ps) | y <- [p^k | k <- [0..]]]

-- 4ª solución

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

compuestos4 :: [Integer] -> [Integer]

compuestos4 ps = foldl aux xs (tail ps)

where p = head ps

xs = [p^k | k <- [0..]]

aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 5ª solución

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

compuestos5 :: [Integer] -> [Integer]

compuestos5 = foldl aux [1]

where aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 6ª solución

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

compuestos6 :: [Integer] -> [Integer]

compuestos6 xs = aux

where aux = 1 : mezclas xs aux

mezclas [] _ = []

mezclas (x:xs) zs = mezcla (map (x*) zs) (mezclas xs zs)

-- Comparación de eficiencia

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

-- λ> compuestos1 [2,3,5] !! 300

-- 84375

-- (5.85 secs, 2,961,101,088 bytes)

-- λ> compuestos2 [2,3,5] !! 300

-- 84375

-- (3.54 secs, 311,137,952 bytes)

-- λ> compuestos2 [2,3,5] !! 400

-- 312500

-- (13.01 secs, 1,229,801,184 bytes)

-- λ> compuestos3 [2,3,5] !! 400

-- 312500

-- (0.02 secs, 2,066,152 bytes)

-- λ> compuestos3 [2,3,5] !! 20000

-- 15441834907098675000000

-- (1.57 secs, 203,061,864 bytes)

-- λ> compuestos4 [2,3,5] !! 20000

-- 15441834907098675000000

-- (0.40 secs, 53,335,080 bytes)

-- λ> compuestos4 [2,3,5] !! 50000

-- 2379528690747474604574166220800

-- (1.25 secs, 170,058,496 bytes)

-- λ> compuestos5 [2,3,5] !! 50000

-- 2379528690747474604574166220800

-- (1.26 secs, 170,104,648 bytes)

-- λ> compuestos6 [2,3,5] !! 50000

-- 2379528690747474604574166220800

-- (0.26 secs, 40,490,280 bytes)

Suma ordenada de listas infinitas ordenadas

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

Definir la función

   sumaOrdenada :: [Integer] -> [Integer] -> [Integer]

1	sumaOrdenada :: [Integer] -> [Integer] -> [Integer]

tal que (sumaOrdenada xs ys) es la suma ordenada de las listas infinitas crecientes xs e ys. Por ejemplo,

   λ> take 15 (sumaOrdenada [5,10..] [7,14..])
   [12,17,19,22,24,26,27,29,31,32,33,34,36,37,38]
   λ> take 15 (sumaOrdenada [2^n | n <- [0..]] [3^n | n <- [0..]])
   [2,3,4,5,7,9,10,11,13,17,19,25,28,29,31]

λ> take 15 (sumaOrdenada [5,10..] [7,14..])

[12,17,19,22,24,26,27,29,31,32,33,34,36,37,38]

λ> take 15 (sumaOrdenada [2^n | n <- [0..]] [3^n | n <- [0..]])

[2,3,4,5,7,9,10,11,13,17,19,25,28,29,31]

Soluciones

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

sumaOrdenada1 :: [Integer] -> [Integer] -> [Integer]
sumaOrdenada1 (x:xs) (y:ys) =
  x+y : map (+x) ys `mezcla` map (+y) xs `mezcla` sumaOrdenada1 ys xs

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys

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

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

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

-- 1ª definición

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

sumaOrdenada1 :: [Integer] -> [Integer] -> [Integer]

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

x+y : map (+x) ys `mezcla` map (+y) xs `mezcla` sumaOrdenada1 ys xs

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

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

| x == y = x : mezcla xs ys

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

-- 2ª definición

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

sumaOrdenada2 :: [Integer] -> [Integer] -> [Integer]

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

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

mezclaTodas = foldr1 xmezcla

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

Mezcla de infinitas listas infinitas

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

Definir la función

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

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

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

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

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

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

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

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

Soluciones

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

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys

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

mezclaTodas = foldr1 xmezcla

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

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

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

| x == y = x : mezcla xs ys

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

Siembra de listas

PorJosé A. Alonso 23-diciembre-201525-marzo-2022

Definir la función

   siembra :: [Int] -> [Int]

1	siembra :: [Int] -> [Int]

tal que (siembra xs) es la lista ys obtenida al repartir cada elemento x de la lista xs poniendo un 1 en las x siguientes posiciones de la lista ys. Por ejemplo,

   siembra [4]      ==  [0,1,1,1,1] 
   siembra [0,2]    ==  [0,0,1,1]
   siembra [4,2]    ==  [0,1,2,2,1]

siembra [4] == [0,1,1,1,1]

siembra [0,2] == [0,0,1,1]

siembra [4,2] == [0,1,2,2,1]

El tercer ejemplo se obtiene sumando la siembra de 4 en la posición 0 (como el ejemplo 1) y el 2 en la posición 1 (como el ejemplo 2). Otros ejemplos son

   siembra [0,4,2]          ==  [0,0,1,2,2,1]
   siembra [3]              ==  [0,1,1,1]
   siembra [3,4,2]          ==  [0,1,2,3,2,1]
   siembra [3,2,1]          ==  [0,1,2,3]
   sum $ siembra [1..2500]  ==  3126250

siembra [0,4,2] == [0,0,1,2,2,1]

siembra [3] == [0,1,1,1]

siembra [3,4,2] == [0,1,2,3,2,1]

siembra [3,2,1] == [0,1,2,3]

sum $ siembra [1..2500] == 3126250

Comprobar con QuickCheck que la suma de los elementos de (siembra xs) es igual que la suma de los de xs.

Nota 1: Se supone que el argumento es una lista de números no negativos y que se puede ampliar tanto como sea necesario para repartir los elementos.

Nota 2: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Soluciones

import Test.QuickCheck

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

siembra1 :: [Int] -> [Int]
siembra1 = suma . brotes

-- (brotes xs) es la lista de los brotes obtenido sembrando los
-- elementos de xs. Por ejemplo,
--    brotes [3,4,2]  ==  [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]]
brotes :: [Int] -> [[Int]]
brotes xs = aux xs 1
    where aux (x:xs) n = (replicate n 0 ++ replicate x 1) : aux xs (n+1)
          aux _ _      = []

-- (suma xss) es la suma de los elementos de xss (suponiendo que al
-- final de cada elemento se continua con ceros). Por ejemplo,
--    suma [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]]  ==  [0,1,2,3,2,1]
suma :: [[Int]] -> [Int]
suma = foldr1 aux
    where aux [] ys = ys
          aux xs [] = xs
          aux (x:xs) (y:ys) = (x+y) : aux xs ys

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

siembra2 :: [Int] -> [Int]
siembra2 [] = []
siembra2 (x:xs) = mezcla (siembraElemento x) (0 : siembra2 xs)

siembraElemento :: Int -> [Int]
siembraElemento x = 0 : replicate x 1

mezcla :: [Int] -> [Int] -> [Int]
mezcla xs ys =
    take (max (length xs) (length ys))
         (zipWith (+) (xs ++ repeat 0) (ys ++ repeat 0))

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

siembra3 :: [Int] -> [Int]
siembra3 [] = []
siembra3 xs = aux xs 0 (repeat 0) where
    aux []     _ ys = cosecha ys
    aux (x:xs) n ys = aux xs (n+1) (zipWith (+) brotes ys) 
        where brotes = replicate (n+1) 0 ++ replicate x 1 ++ repeat 0

-- (cosecha xs) es la lista formada por los ceros iniciales de xs y los
-- elementos siguientes hasta que vuelve a aparecer el 0. Por ejemplo,
--    cosecha [0,0,3,5,2,0,9]            ==  [0,0,3,5,2]
--    cosecha ([0,0,3,5,2] ++ repeat 0)  ==  [0,0,3,5,2]
cosecha :: [Int] -> [Int]              
cosecha xs = ys ++ takeWhile (>0) zs
    where (ys,zs) = span (==0) xs

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

siembra4 :: [Int] -> [Int]
siembra4 [] = []
siembra4 xs = aux xs [] (repeat 0) where
    aux []     ys zs     = reverse ys ++ takeWhile (>0) zs
    aux (x:xs) ys (z:zs) = aux xs (z:ys) (zipWith (+) brotes zs) 
        where brotes = replicate x 1 ++ repeat 0

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

--    λ> sum $ siembra1 [1..2000]
--    2001000
--    (9.44 secs, 1,894,065,928 bytes)
--    ghci> sum $ siembra2 [1..2000]
--    2001000
--    (5.92 secs, 936900576 bytes)
--    ghci> sum $ siembra3 [1..2000]
--    2001000
--    (1.59 secs, 836847072 bytes)
--    ghci> sum $ siembra4 [1..2000]
--    2001000
--    (1.68 secs, 570492392 bytes)

-- En lo que sigue usaremos la 2ª definición
siembra :: [Int] -> [Int]
siembra = siembra2

-- Verificación
-- ============

-- La propiedad es
prop_siembra :: [Int] -> Bool
prop_siembra xs =
    sum (siembra1 ys) == sum ys
    where ys = map (\x -> 1 + abs x) xs

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

100

import Test.QuickCheck

-- 1ª solución

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

siembra1 :: [Int] -> [Int]

siembra1 = suma . brotes

-- (brotes xs) es la lista de los brotes obtenido sembrando los

-- elementos de xs. Por ejemplo,

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

brotes :: [Int] -> [[Int]]

brotes xs = aux xs 1

where aux (x:xs) n = (replicate n 0 ++ replicate x 1) : aux xs (n+1)

aux _ _ = []

-- (suma xss) es la suma de los elementos de xss (suponiendo que al

-- final de cada elemento se continua con ceros). Por ejemplo,

-- suma [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]] == [0,1,2,3,2,1]

suma :: [[Int]] -> [Int]

suma = foldr1 aux

where aux [] ys = ys

aux xs [] = xs

aux (x:xs) (y:ys) = (x+y) : aux xs ys

-- 2ª solución

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

siembra2 :: [Int] -> [Int]

siembra2 [] = []

siembra2 (x:xs) = mezcla (siembraElemento x) (0 : siembra2 xs)

siembraElemento :: Int -> [Int]

siembraElemento x = 0 : replicate x 1

mezcla :: [Int] -> [Int] -> [Int]

mezcla xs ys =

take (max (length xs) (length ys))

(zipWith (+) (xs ++ repeat 0) (ys ++ repeat 0))

-- 3ª solución

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

siembra3 :: [Int] -> [Int]

siembra3 [] = []

siembra3 xs = aux xs 0 (repeat 0) where

aux [] _ ys = cosecha ys

aux (x:xs) n ys = aux xs (n+1) (zipWith (+) brotes ys)

where brotes = replicate (n+1) 0 ++ replicate x 1 ++ repeat 0

-- (cosecha xs) es la lista formada por los ceros iniciales de xs y los

-- elementos siguientes hasta que vuelve a aparecer el 0. Por ejemplo,

-- cosecha [0,0,3,5,2,0,9] == [0,0,3,5,2]

-- cosecha ([0,0,3,5,2] ++ repeat 0) == [0,0,3,5,2]

cosecha :: [Int] -> [Int]

cosecha xs = ys ++ takeWhile (>0) zs

where (ys,zs) = span (==0) xs

-- 4ª solución

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

siembra4 :: [Int] -> [Int]

siembra4 [] = []

siembra4 xs = aux xs [] (repeat 0) where

aux [] ys zs = reverse ys ++ takeWhile (>0) zs

aux (x:xs) ys (z:zs) = aux xs (z:ys) (zipWith (+) brotes zs)

where brotes = replicate x 1 ++ repeat 0

-- Comparación de eficiencia

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

-- λ> sum $ siembra1 [1..2000]

-- 2001000

-- (9.44 secs, 1,894,065,928 bytes)

-- ghci> sum $ siembra2 [1..2000]

-- 2001000

-- (5.92 secs, 936900576 bytes)

-- ghci> sum $ siembra3 [1..2000]

-- 2001000

-- (1.59 secs, 836847072 bytes)

-- ghci> sum $ siembra4 [1..2000]

-- 2001000

-- (1.68 secs, 570492392 bytes)

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

siembra :: [Int] -> [Int]

siembra = siembra2

-- Verificación

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

-- La propiedad es

prop_siembra :: [Int] -> Bool

prop_siembra xs =

sum (siembra1 ys) == sum ys

where ys = map (\x -> 1 + abs x) xs

-- La comprobación es

-- λ> quickCheck prop_siembra

-- +++ OK, passed 100 tests.

Suma de una lista de vectores

PorJosé A. Alonso 19-enero-201530-noviembre-2015

Definir la función

   sumaVec :: Num a => [[a]] -> [a]

1	sumaVec :: Num a => [[a]] -> [a]

tal que (sumaVec xss) es la suma de los vectores de xss. Por ejemplo,

   sumaVec [[4,7,3],[3,1,4],[2,2,5]]  ==  [9,10,12]
   sumaVec [[4,7],[3,3],[1,4],[2,5]]  ==  [10,19]

1 2	sumaVec [[4,7,3],[3,1,4],[2,2,5]] == [9,10,12] sumaVec [[4,7],[3,3],[1,4],[2,5]] == [10,19]

Soluciones

import Data.List (transpose)
import Data.Array (listArray,(!))

-- 1ª definición (por recursión):
sumaVec1 :: Num a => [[a]] -> [a]
sumaVec1 []          = []
sumaVec1 [xs]        = xs
sumaVec1 (xs:ys:zss) = suma xs (sumaVec1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,
--    suma [4,7,3] [1,2,5]  == [5,9,8]
suma :: Num a => [a] -> [a] -> [a]
suma [] []         = []
suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith): 
sumaVec2 :: Num a => [[a]] -> [a]
sumaVec2 []       = []
sumaVec2 [xs]     = xs
sumaVec2 (xs:xss) = zipWith (+) xs (sumaVec2 xss)

-- 3ª definición (por plegado)
sumaVec3 :: Num a => [[a]] -> [a]
sumaVec3 = foldr1 (zipWith (+))

-- 4ª definición (con map y transpose):
sumaVec4 :: Num a => [[a]] -> [a]
sumaVec4 = map sum . transpose 

-- 5ª definición (con array)
-- =========================

sumaVec5 :: Num a => [[a]] -> [a]
sumaVec5 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]] 
    where m = length xss
          n = length (head xss)
          p = listArray ((1,1),(m,n)) (concat xss)

import Data.List (transpose)

import Data.Array (listArray,(!))

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

sumaVec1 :: Num a => [[a]] -> [a]

sumaVec1 [] = []

sumaVec1 [xs] = xs

sumaVec1 (xs:ys:zss) = suma xs (sumaVec1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,

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

suma :: Num a => [a] -> [a] -> [a]

suma [] [] = []

suma (x:xs) (y:ys) = x+y : suma xs ys

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

sumaVec2 :: Num a => [[a]] -> [a]

sumaVec2 [] = []

sumaVec2 [xs] = xs

sumaVec2 (xs:xss) = zipWith (+) xs (sumaVec2 xss)

-- 3ª definición (por plegado)

sumaVec3 :: Num a => [[a]] -> [a]

sumaVec3 = foldr1 (zipWith (+))

-- 4ª definición (con map y transpose):

sumaVec4 :: Num a => [[a]] -> [a]

sumaVec4 = map sum . transpose

-- 5ª definición (con array)

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

sumaVec5 :: Num a => [[a]] -> [a]

sumaVec5 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]]

where m = length xss

n = length (head xss)

p = listArray ((1,1),(m,n)) (concat xss)

Mezcla de infinitas listas infinitas

PorJosé A. Alonso 15-enero-201525-abril-2021

Definir la función

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

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

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

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

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

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

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

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

Soluciones

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

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys

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

mezclaTodas = foldr1 xmezcla

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

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

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

| x == y = x : mezcla xs ys

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

Matriz de mínimas distancias

Soluciones

Otras soluciones

Menor divisible por todos

Soluciones

Pensamiento

Matriz de mínimas distancias

Soluciones

Pensamiento

Números compuestos por un conjunto de primos

Soluciones

Suma ordenada de listas infinitas ordenadas

Soluciones

Mezcla de infinitas listas infinitas

Soluciones

Siembra de listas

Soluciones

Suma de una lista de vectores

Soluciones

Mezcla de infinitas listas infinitas

Soluciones

Entradas recientes

Buscar

Correo electrónico