fromJust

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>

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

Números taxicab

PorJosé A. Alonso 29-mayo-20185-junio-2018

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

   taxicab  :: [Integer]
   taxicab2 :: [Integer]

1 2	taxicab :: [Integer] taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

   take 5 taxicab   ==  [1729,4104,13832,20683,32832]
   take 2 taxicab2  ==  [2,1729]

1 2	take 5 taxicab == [1729,4104,13832,20683,32832] take 2 taxicab2 == [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

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

Soluciones

import Data.List  (find)
import Data.Maybe (fromJust)

taxicab :: [Integer]
taxicab = filter ((> 1) . length . descomposiciones) [1..]

-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.
-- Por ejemplo,
--    descomposiciones 1729  ==  [(10,9),(12,1)]
--    descomposiciones 1728  ==  [(12,0)]
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(x,y) | x <- [1..round (fromIntegral n ** (1/3))],
           let z = n - x^3,
           let z' = round (fromIntegral z ** (1/3)),
           z'^3 == z,
           let y = z',
           y <= x]

-- 2ª definición de descomposiciones
descomposiciones2 :: Integer -> [(Integer,Integer)]
descomposiciones2 n =
  [(x,y) | x <- [1..raizEnt n 3],
           let z = n - x^3,
           let y = raizEnt z 3,
           y <= x,    
           y^3 == z]

-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor
-- número entero y tal que y^n <= x. Por ejemplo, 
--    raizEnt  8 3      ==  2
--    raizEnt  9 3      ==  2
--    raizEnt 26 3      ==  2
--    raizEnt 27 3      ==  3
--    raizEnt (10^50) 2 ==  10000000000000000000000000
-- ---------------------------------------------------------------------

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = aux (1,x)
  where aux (a,b) | d == x    = c
                  | c == a    = c
                  | d < x     = aux (c,b)
                  | otherwise = aux (a,c) 
          where c = (a+b) `div` 2
                d = c^n

taxicab2 :: [Integer]
taxicab2 = aux 1 [2..]
  where aux n xs = fx : aux (n+1) [fx+1..]
          where fx = fromJust (find ((== n) . length . descomposiciones) xs)

import Data.List (find)

import Data.Maybe (fromJust)

taxicab :: [Integer]

taxicab = filter ((> 1) . length . descomposiciones) [1..]

-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.

-- Por ejemplo,

-- descomposiciones 1729 == [(10,9),(12,1)]

-- descomposiciones 1728 == [(12,0)]

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

descomposiciones n =

[(x,y) | x <- [1..round (fromIntegral n ** (1/3))],

let z = n - x^3,

let z' = round (fromIntegral z ** (1/3)),

z'^3 == z,

let y = z',

y <= x]

-- 2ª definición de descomposiciones

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

descomposiciones2 n =

[(x,y) | x <- [1..raizEnt n 3],

let z = n - x^3,

let y = raizEnt z 3,

y <= x,

y^3 == z]

-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor

-- número entero y tal que y^n <= x. Por ejemplo,

-- raizEnt 8 3 == 2

-- raizEnt 9 3 == 2

-- raizEnt 26 3 == 2

-- raizEnt 27 3 == 3

-- raizEnt (10^50) 2 == 10000000000000000000000000

-- ---------------------------------------------------------------------

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = aux (1,x)

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

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

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

d = c^n

taxicab2 :: [Integer]

taxicab2 = aux 1 [2..]

where aux n xs = fx : aux (n+1) [fx+1..]

where fx = fromJust (find ((== n) . length . descomposiciones) xs)

División equitativa

PorJosé A. Alonso 6-febrero-201826-marzo-2022

Definir la función

   divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

1	divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

   divisionEquitativa [1,2,3,4,5,15]  ==  Just ([1,2,3,4,5],[15])
   divisionEquitativa [15,1,2,3,4,5]  ==  Just ([15],[1,2,3,4,5])
   divisionEquitativa [1,2,3,4,7,15]  ==  Nothing
   divisionEquitativa [1,2,3,4,15,5]  ==  Nothing

divisionEquitativa [1,2,3,4,5,15] == Just ([1,2,3,4,5],[15])

divisionEquitativa [15,1,2,3,4,5] == Just ([15],[1,2,3,4,5])

divisionEquitativa [1,2,3,4,7,15] == Nothing

divisionEquitativa [1,2,3,4,15,5] == Nothing

Soluciones

import Data.Maybe (isNothing, fromJust, listToMaybe)
import Data.List  (elemIndex, inits, tails)

-- 1ª solución
divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa1 xs = aux (particiones xs)
 where aux []                              = Nothing
       aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)
                        | otherwise        = aux ys                   
       particiones xs = [splitAt i xs | i <- [1..length xs-1]]

-- 2ª solución
divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa2 xs
  | 2 * b == suma = Just $ splitAt (length as + 1) xs
  | otherwise     = Nothing
  where suma        = sum xs
        (as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs

-- 3ª solución
divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa3 xs
  | odd n       = Nothing
  | isNothing p = Nothing
  | otherwise   = Just (splitAt (1 + fromJust p) xs)
  where n  = sum xs
        ys = scanl1 (+) xs
        p  = elemIndex (n `div` 2) ys

-- 4ª solución
divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa4 xs
  | odd (sum xs) = Nothing
  | otherwise    = aux [] xs
  where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs)
                          | sum as > sum bs  = Nothing
                          | otherwise        = aux (b:as) (bs')

-- 5ª solución
divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa5 xs =
  listToMaybe
    [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)
              , sum ys == sum zs ]

import Data.Maybe (isNothing, fromJust, listToMaybe)

import Data.List (elemIndex, inits, tails)

-- 1ª solución

divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa1 xs = aux (particiones xs)

where aux [] = Nothing

aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)

| otherwise = aux ys

particiones xs = [splitAt i xs | i <- [1..length xs-1]]

-- 2ª solución

divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa2 xs

| 2 * b == suma = Just $ splitAt (length as + 1) xs

| otherwise = Nothing

where suma = sum xs

(as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs

-- 3ª solución

divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa3 xs

| odd n = Nothing

| isNothing p = Nothing

| otherwise = Just (splitAt (1 + fromJust p) xs)

where n = sum xs

ys = scanl1 (+) xs

p = elemIndex (n `div` 2) ys

-- 4ª solución

divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa4 xs

| odd (sum xs) = Nothing

| otherwise = aux [] xs

where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs)

| sum as > sum bs = Nothing

| otherwise = aux (b:as) (bs')

-- 5ª solución

divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa5 xs =

listToMaybe

[(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)

, sum ys == sum zs ]

Ordenación según una cadena

PorJosé A. Alonso 29-diciembre-201726-marzo-2022

Dada una lista xs y una cadena cs de la misma longitud, la ordenación de xs según cs consiste en emparejar los elementos de cs con los de xs (de forma que al menor elemento de cs le corresponde el menor de xs, al segundo de cs el segundo de xs, etc.) y ordenar los elementos de xs en el mismo orden que sus correspondientes elementos de cs. Por ejemplo, si xs es [6,4,2] y cs es «CAB» entonces a ‘A’ le corresponde el 2, a ‘B’ el 4 y a ‘C’ el 6; luego la ordenación es [6,2,4].

Definir la función

   ordenacion :: Ord a => [a] -> String -> [a]

1	ordenacion :: Ord a => [a] -> String -> [a]

tal que (ordenacion xs ys) es la ordenación de la lista xs según la cadena cs. Por ejemplo,

   ordenacion [6,4,2] "CAB"     ==  [6,2,4]
   ordenacion [1,5,3] "ABC"     ==  [1,3,5]
   ordenacion [1,5,3,7] "ABEC"  ==  [1,3,7,5]

ordenacion [6,4,2] "CAB" == [6,2,4]

ordenacion [1,5,3] "ABC" == [1,3,5]

ordenacion [1,5,3,7] "ABEC" == [1,3,7,5]

Soluciones

import Data.List (sort)
import Data.Maybe (fromJust)

ordenacion :: Ord a => [a] -> String -> [a]
ordenacion xs cs =
  [fromJust (lookup y diccionario) | y <- cs]
  where diccionario = zip (sort cs) (sort xs)

import Data.List (sort)

import Data.Maybe (fromJust)

ordenacion :: Ord a => [a] -> String -> [a]

ordenacion xs cs =

[fromJust (lookup y diccionario) | y <- cs]

where diccionario = zip (sort cs) (sort xs)

Matriz de mínimas distancias

Soluciones

Otras soluciones

Matriz de mínimas distancias

Soluciones

Pensamiento

Números taxicab

Soluciones

División equitativa

Soluciones

Ordenación según una cadena

Soluciones

Entradas recientes

Buscar

Correo electrónico