{"id":1477,"date":"2015-05-21T06:00:59","date_gmt":"2015-05-21T04:00:59","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1477"},"modified":"2015-06-13T16:29:34","modified_gmt":"2015-06-13T14:29:34","slug":"matrices-marco-y-transiciones","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/matrices-marco-y-transiciones\/","title":{"rendered":"Matrices marco y transiciones"},"content":{"rendered":"<p>Las <strong>posiciones frontera<\/strong> de una matriz de orden mxn son aquellas que est\u00e1n en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dir\u00e1n <strong>posiciones interiores<\/strong>. Observa que cada elemento en una posici\u00f3n interior tiene exactamente 8 vecinos en la matriz.<\/p>\n<p>Dada una matriz, un <strong>paso de transici\u00f3n<\/strong> genera una nueva matriz de la misma dimensi\u00f3n pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no var\u00edan.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   marco      :: Int -> Int -> Integer -> Matrix Integer\n   paso       :: Matrix Integer -> Matrix Integer\n   itPasos    :: Int -> Matrix Integer -> Matrix Integer\n   pasosHasta :: Integer -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(marco m n z) genera la matriz de dimensi\u00f3n mxn que contiene el entero z en las posiciones frontera y 0 en las posiciones  interiores. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     ghci> marco 5 5 1\n     ( 1 1 1 1 1 )\n     ( 1 0 0 0 1 )\n     ( 1 0 0 0 1 )\n     ( 1 0 0 0 1 )\n     ( 1 1 1 1 1 )\n<\/pre>\n<ul>\n<li>(paso t) calcula la matriz generada tras aplicar un paso de transici\u00f3n a la matriz t. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     ghci> paso (marco 5 5 1)\n     ( 1 1 1 1 1 )\n     ( 1 5 3 5 1 )\n     ( 1 3 0 3 1 )\n     ( 1 5 3 5 1 )\n     ( 1 1 1 1 1 )\n<\/pre>\n<ul>\n<li>(itPasos k t) es la matriz obtenida tras aplicar k pasos de transici\u00f3n a partir de la matriz t. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     ghci> itPasos 10 (marco 5 5 1)\n     (       1       1       1       1       1 )\n     (       1 4156075 5878783 4156075       1 )\n     (       1 5878783 8315560 5878783       1 )\n     (       1 4156075 5878783 4156075       1 )\n     (       1       1       1       1       1 )\n<\/pre>\n<ul>\n<li>(pasosHasta k) es el n\u00famero de pasos de transici\u00f3n a partir de la matriz (marco 5 5 1) necesarios para que en la matriz resultante aparezca un elemento mayor que k. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     pasosHasta 4         ==  1\n     pasosHasta 6         ==  2\n     pasosHasta (2^2015)  ==  887\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Matrix\n\nmarco :: Int -> Int -> Integer -> Matrix Integer\nmarco m n z  = matrix m n f\n    where f (i,j) | frontera m n (i,j) = z\n                  | otherwise          = 0 \n\n-- (frontera m n (i,j)) se verifica si (i,j) es una posici\u00f3n de la\n-- frontera de las matrices de dimensi\u00f3n mxn.\nfrontera :: Int -> Int -> (Int,Int) -> Bool\nfrontera m n (i,j) = or [i == 1, i == m, j == 1, j == n]\n\npaso :: Matrix Integer -> Matrix Integer\npaso p = matrix m n f where\n    m = nrows p\n    n = ncols p\n    f (i,j) \n        | frontera m n (i,j) = p!(i,j)\n        | otherwise          = sum [p!(u,v) | (u,v) <- vecinos m n (i,j)]\n    \n-- (vecinos m n (i,j)) es la lista de las posiciones de los vecinos del\n-- punto interior (i,j) en las matrices de dimensi\u00f3n mxn.\nvecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]\nvecinos m n (i,j) = [(a,b) | a <- [i-1..i+1]\n                           , b <- [j-1..j+1]\n                           , (a,b) \/= (i,j)]\n\nitPasos :: Int -> Matrix Integer -> Matrix Integer \nitPasos k t = (iterate paso t) !! k \n\npasosHasta :: Integer -> Int\npasosHasta k =\n    length (takeWhile (\\t -> menores t k) (iterate paso (marco 5 5 1)))\n\n-- (menores p k) se verifica si los elementos de p son menores o\n-- iguales que k. Por ejemplo, \n--    menores (itPasos 1 (marco 5 5 1)) 6  ==  True\n--    menores (itPasos 1 (marco 5 5 1)) 4  ==  False\nmenores :: Matrix Integer -> Integer -> Bool\nmenores p k = all (<=k) (toList p)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Las posiciones frontera de una matriz de orden mxn son aquellas que est\u00e1n en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dir\u00e1n posiciones interiores. Observa que cada elemento en una posici\u00f3n interior tiene exactamente 8 vecinos en la matriz. Dada una matriz, un paso&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1477"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=1477"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1477\/revisions"}],"predecessor-version":[{"id":1515,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1477\/revisions\/1515"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1477"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1477"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1477"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}