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

7 Comentarios

import Data.Matrix
 
minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias m
  | m == identity (nrows m) = matrizEspecial m
  | otherwise               = matrizDiferente m

matrizEspecial :: Matrix Int -> Matrix Int  
matrizEspecial m = matrix (nrows m) (ncols m) (\(i,j) -> abs (i-j))

matrizDiferente :: Matrix Int -> Matrix Int    
matrizDiferente m = matrix (nrows m) (ncols m) (\(i,j) -> f i j)
  where f i j | m ! (i,j) == 1 = 0
              | otherwise = minimum [ abs (i-a) + abs (j-b)
                                    | a <- [1..nrows m]
                                    , b <- [1..ncols m]
                                    , m ! (a,b) == 1]
 
sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n = sum [2*(n-k)*k | k <- [1..n-1]]

import Data.Matrix

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias m

| m == identity (nrows m) = matrizEspecial m

| otherwise = matrizDiferente m

matrizEspecial :: Matrix Int -> Matrix Int

matrizEspecial m = matrix (nrows m) (ncols m) (\(i,j) -> abs (i-j))

matrizDiferente :: Matrix Int -> Matrix Int

matrizDiferente m = matrix (nrows m) (ncols m) (\(i,j) -> f i j)

where f i j | m ! (i,j) == 1 = 0

| otherwise = minimum [ abs (i-a) + abs (j-b)

| a <- [1..nrows m]

, b <- [1..ncols m]

, m ! (a,b) == 1]

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n = sum [2*(n-k)*k | k <- [1..n-1]]

Responder

import Data.Matrix
 
minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias v = matrix m n g
  where (m,n) = (nrows v , ncols v)
        g (i,j) = f (i,j) [(i,j)]
        f (i,j) xs
          | v ! (i,j) == 1 = 0
          | null ys        = m*n
          | otherwise      = 1 + minimum ys
          where ys = [ f (x,y) ((x,y):xs)
                     | x <- [i-1..i+1]
                     , y <- [j-1..j+1]
                     , elem x [1..m]
                     , elem y [1..n]
                     , x == i || y == j
                     , notElem (x,y) xs ]
 
sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n = sum [2*(n-k)*k | k <- [1..n-1]]

import Data.Matrix

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias v = matrix m n g

where (m,n) = (nrows v , ncols v)

g (i,j) = f (i,j) [(i,j)]

f (i,j) xs

| v ! (i,j) == 1 = 0

| null ys = m*n

| otherwise = 1 + minimum ys

where ys = [ f (x,y) ((x,y):xs)

| x <- [i-1..i+1]

, y <- [j-1..j+1]

, elem x [1..m]

, elem y [1..n]

, x == i || y == j

, notElem (x,y) xs ]

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n = sum [2*(n-k)*k | k <- [1..n-1]]

Responder

import Data.Matrix
 
minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias p = q
  where q = matrix (nrows p) (ncols p) (\(i,j) -> distanciaUno (i,j) p) 
  
distanciaUno :: (Int,Int) -> Matrix Int -> Int
distanciaUno (a,b) p = minimum [entreDosPuntos (a,b) (c,d) |
                                (c,d) <- buscarUnos p]
 
buscarUnos :: Matrix Int -> [(Int,Int)]
buscarUnos p = [(i,j) | i <- [1..nrows p]
                      , j <- [1..ncols p]
                      , p ! (i,j) == 1]
 
entreDosPuntos :: (Int,Int) -> (Int,Int) -> Int
entreDosPuntos (a,b) (c,d) = abs (c-a) + abs (d-b)
 
sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n =
  sum [2*a*b | (a,b) <- zip [1..n-1] (reverse [1..n-1])]

import Data.Matrix

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias p = q

where q = matrix (nrows p) (ncols p) (\(i,j) -> distanciaUno (i,j) p)

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

distanciaUno (a,b) p = minimum [entreDosPuntos (a,b) (c,d) |

(c,d) <- buscarUnos p]

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

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

, j <- [1..ncols p]

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

entreDosPuntos :: (Int,Int) -> (Int,Int) -> Int

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

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n =

sum [2*a*b | (a,b) <- zip [1..n-1] (reverse [1..n-1])]

Responder

import Data.Matrix

minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias  m = matrix r c (\(i,j) -> f i j)
  where r = nrows m
        c = ncols m
        f i j = aux i j []
        aux i j xs | m ! (i,j) == 1 = 0
                   | null ds        = r*c
                   | otherwise      = 1 + minimum ds
          where ds = [ aux x y ((x,y):xs)
                     | x <- [a..b]
                     , y <- [a'..b']
                     , x == i || y == j
                     , notElem (x,y) xs]
                  where  a  = max (i-1) 1
                         b  = min (i+1) r
                         a' = max (j-1) 1
                         b' = min (j+1) c
 
sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n = sum [2*(n-k)*k | k <- [1..n-1]]

import Data.Matrix

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias m = matrix r c (\(i,j) -> f i j)

where r = nrows m

c = ncols m

f i j = aux i j []

aux i j xs | m ! (i,j) == 1 = 0

| null ds = r*c

| otherwise = 1 + minimum ds

where ds = [ aux x y ((x,y):xs)

| x <- [a..b]

, y <- [a'..b']

, x == i || y == j

, notElem (x,y) xs]

where a = max (i-1) 1

b = min (i+1) r

a' = max (j-1) 1

b' = min (j+1) c

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n = sum [2*(n-k)*k | k <- [1..n-1]]

Responder

import Data.Matrix
import Data.List

minimasDistancias :: Matrix Int -> Matrix Int
minimasDistancias a = aux (sig is is) is 1 (zero m n)
  where m = nrows a
        n = ncols a
        is = [(i,j) | i <- [1..m]
                    , j <-[1..n]
                    , a!(i,j) == 1]
        sig ps vs = nub [(i,j) | (i,j) <- concatMap (vecinos m n) ps
                               , (i,j) `notElem` vs]
        aux ps vis k b | null ps   = b
                       | otherwise = aux qs (ps ++ vis) (k + 1) b'
          where qs = sig ps vis 
                b' = modifica b ps k
 
modifica :: Matrix Int -> [(Int,Int)] -> Int -> Matrix Int
modifica b qs k = snd $ until (null . fst) f (qs, b)
  where f ((p:ps), b) = (ps,setElem k p b)

vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]  
vecinos m n (i,j) =
  [(a,b) | (a,b) <- [(i,j-1), (i,j+1), (i-1,j),(i+1,j)]
         , 1 <= a, a <= m
         , 1 <= b, b <= n]
 
sumaMinimaDistanciasIdentidad :: Int -> Int
sumaMinimaDistanciasIdentidad n = 
  sum (minimasDistancias (identity n))

import Data.Matrix

import Data.List

minimasDistancias :: Matrix Int -> Matrix Int

minimasDistancias a = aux (sig is is) is 1 (zero m n)

where m = nrows a

n = ncols a

is = [(i,j) | i <- [1..m]

, j <-[1..n]

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

sig ps vs = nub [(i,j) | (i,j) <- concatMap (vecinos m n) ps

, (i,j) `notElem` vs]

aux ps vis k b | null ps = b

| otherwise = aux qs (ps ++ vis) (k + 1) b'

where qs = sig ps vis

b' = modifica b ps k

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

modifica b qs k = snd $ until (null . fst) f (qs, b)

where f ((p:ps), b) = (ps,setElem k p b)

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

vecinos m n (i,j) =

[(a,b) | (a,b) <- [(i,j-1), (i,j+1), (i-1,j),(i+1,j)]

, 1 <= a, a <= m

, 1 <= b, b <= n]

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n =

sum (minimasDistancias (identity n))

Responder

guicabgod dice:

25-marzo-2019 a las 13:36

Falla en el 2º ejemplo.

Responder

-- Corregido
minimasDistancias' :: Matrix Int -> Matrix Int
minimasDistancias' a = aux (sig is is) is 1 (zero m n)
  where m = nrows a
        n = ncols a
        is = [(i,j) | i <-[1..m], j <-[1..n], a!(i,j) == 1]
        sig ps vs = nub [(i,j) | (i,j) <- concatMap (vecinos' m n) ps, (i,j) `notElem` vs]
        aux ps vis k b | null ps   = b
                       | otherwise = aux qs (ps++vis) (k+1) b'
          where qs = sig ps (ps ++ vis ) 
                b' = modifica b ps k

modifica :: Matrix Int -> [(Int,Int)] -> Int -> Matrix Int
modifica b qs k = snd $ until (null . fst) f (qs, b)
  where f ((p:ps), b) = (ps,setElem k p b)


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

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

-- Corregido

minimasDistancias' :: Matrix Int -> Matrix Int

minimasDistancias' a = aux (sig is is) is 1 (zero m n)

where m = nrows a

n = ncols a

is = [(i,j) | i <-[1..m], j <-[1..n], a!(i,j) == 1]

sig ps vs = nub [(i,j) | (i,j) <- concatMap (vecinos' m n) ps, (i,j) `notElem` vs]

aux ps vis k b | null ps = b

| otherwise = aux qs (ps++vis) (k+1) b'

where qs = sig ps (ps ++ vis )

b' = modifica b ps k

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

modifica b qs k = snd $ until (null . fst) f (qs, b)

where f ((p:ps), b) = (ps,setElem k p b)

vecinos' m n (i,j) =

[(a,b) | (a,b) <- [(i,j-1), (i,j+1), (i-1,j),(i+1,j)],

a >=1, a<=m, b>=1, b <=n]

sumaMinimaDistanciasIdentidad :: Int -> Int

sumaMinimaDistanciasIdentidad n =

sum (minimasDistancias (identity n))

Responder

Matriz de mínimas distancias

Soluciones

Pensamiento

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico