Ir al contenido principal

Matrices marco y transiciones

Las posiciones frontera de una matriz de orden mxn son aquellas que están en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dirán posiciones interiores. Observa que cada elemento en una posición interior tiene exactamente 8 vecinos en la matriz.

Dada una matriz, un paso de transición genera una nueva matriz de la misma dimensión pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no varían.

Definir las funciones

marco      :: Int -> Int -> Integer -> Matrix Integer
paso       :: Matrix Integer -> Matrix Integer
itPasos    :: Int -> Matrix Integer -> Matrix Integer
pasosHasta :: Integer -> Int

tales que

  • (marco m n z) genera la matriz de dimensión mxn que contiene el entero z en las posiciones frontera y 0 en las posiciones interiores. Por ejemplo,
λ> marco 5 5 1
( 1 1 1 1 1 )
( 1 0 0 0 1 )
( 1 0 0 0 1 )
( 1 0 0 0 1 )
( 1 1 1 1 1 )
  • (paso t) calcula la matriz generada tras aplicar un paso de transición a la matriz t. Por ejemplo,
λ> paso (marco 5 5 1)
( 1 1 1 1 1 )
( 1 5 3 5 1 )
( 1 3 0 3 1 )
( 1 5 3 5 1 )
( 1 1 1 1 1 )
  • (itPasos k t) es la matriz obtenida tras aplicar k pasos de transición a partir de la matriz t. Por ejemplo,
λ> itPasos 10 (marco 5 5 1)
(       1       1       1       1       1 )
(       1 4156075 5878783 4156075       1 )
(       1 5878783 8315560 5878783       1 )
(       1 4156075 5878783 4156075       1 )
(       1       1       1       1       1 )
  • (pasosHasta k) es el número de pasos de transición a partir de la matriz (marco 5 5 1) necesarios para que en la matriz resultante aparezca un elemento mayor que k. Por ejemplo,
pasosHasta 4         ==  1
pasosHasta 6         ==  2
pasosHasta (2^2015)  ==  887

Soluciones

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer
marco m n z  = matrix m n f
    where f (i,j) | frontera m n (i,j) = z
                  | otherwise          = 0

-- (frontera m n (i,j)) se verifica si (i,j) es una posición de la
-- frontera de las matrices de dimensión mxn.
frontera :: Int -> Int -> (Int,Int) -> Bool
frontera m n (i,j) = or [i == 1, i == m, j == 1, j == n]

paso :: Matrix Integer -> Matrix Integer
paso p = matrix m n f where
    m = nrows p
    n = ncols p
    f (i,j)
        | frontera m n (i,j) = p!(i,j)
        | otherwise          = sum [p!(u,v) | (u,v) <- vecinos m n (i,j)]

-- (vecinos m n (i,j)) es la lista de las posiciones de los vecinos del
-- punto interior (i,j) en las matrices de dimensión mxn.
vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]
vecinos m n (i,j) = [(a,b) | a <- [i-1..i+1]
                           , b <- [j-1..j+1]
                           , (a,b) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer
itPasos k t = (iterate paso t) !! k

pasosHasta :: Integer -> Int
pasosHasta k =
    length (takeWhile (\t -> menores t k) (iterate paso (marco 5 5 1)))

-- (menores p k) se verifica si los elementos de p son menores o
-- iguales que k. Por ejemplo,
--    menores (itPasos 1 (marco 5 5 1)) 6  ==  True
--    menores (itPasos 1 (marco 5 5 1)) 4  ==  False
menores :: Matrix Integer -> Integer -> Bool
menores p k = all (<=k) (toList p)