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
1 2 3 4 |
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,
1 2 3 4 5 6 |
ghci> 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,
1 2 3 4 5 6 |
ghci> 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,
1 2 3 4 5 6 |
ghci> 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,
1 2 3 |
pasosHasta 4 == 1 pasosHasta 6 == 2 pasosHasta (2^2015) == 887 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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) |
4 Comentarios