{"id":321,"date":"2014-06-19T07:00:46","date_gmt":"2014-06-19T05:00:46","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=321"},"modified":"2021-04-25T17:09:09","modified_gmt":"2021-04-25T15:09:09","slug":"buscaminas-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/buscaminas-1\/","title":{"rendered":"Buscaminas"},"content":{"rendered":"<h4>Enunciado<\/h4>\n<pre lang=\"text\">\n-- El buscaminas es un juego cuyo objetivo es despejar un campo de minas\n-- sin detonar ninguna. \n-- \n-- El campo de minas se representa mediante un cuadrado con NxN\n-- casillas. Algunas casillas tienen un n\u00famero, este n\u00famero indica las\n-- minas que hay en todas las casillas vecinas. Cada casilla tiene como\n-- m\u00e1ximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda\n-- contiene dos minas, cada una representada por el n\u00famero 9, y a la \n-- derecha se muestra el campo obtenido anotando las minas vecinas de\n-- cada casilla\n--    9 0 0 0       9 1 0 0\n--    0 0 0 0       2 2 1 0\n--    0 9 0 0       1 9 1 0\n--    0 0 0 0       1 1 1 0\n-- de la misma forma, la anotaci\u00f3n del siguiente a la izquierda es el de\n-- la derecha \n--    9 9 0 0 0     9 9 1 0 0\n--    0 0 0 0 0     3 3 2 0 0\n--    0 9 0 0 0     1 9 1 0 0\n--\n-- En el ejercicio se usar\u00e1 la librer\u00eda Data.Matrix, cuyo manual se encuentra\n-- en http:\/\/bit.ly\/1hWVNJD\n-- \n-- Los campos de minas se representan mediante matrices: \n--    type Campo = Matrix Int\n-- Por ejemplo, los anteriores campos de la izquierda se definen por\n--    ejCampo1, ejCampo2 :: Campo\n--    ejCampo1 = fromLists [[9,0,0,0],\n--                          [0,0,0,0], \n--                          [0,9,0,0], \n--                          [0,0,0,0]]\n--    ejCampo2 = fromLists [[9,9,0,0,0],\n--                          [0,0,0,0,0],\n--                          [0,9,0,0,0]]\n-- \n-- Definir la funci\u00f3n\n--    buscaminas :: Campo -> Campo\n-- tal que (buscaminas c) es el campo obtenido anotando las minas\n-- vecinas de cada casilla. Por ejemplo,\n--    ghci> buscaminas ejCampo1\n--    ( 9 1 0 0 )\n--    ( 2 2 1 0 )\n--    ( 1 9 1 0 )\n--    ( 1 1 1 0 )\n--\n--    ghci> buscaminas ejCampo2\n--    ( 9 9 1 0 0 )\n--    ( 3 3 2 0 0 )\n--    ( 1 9 1 0 0 )\n-- \n-- Nota. Las funciones de la librer\u00eda de matrices \u00fatiles para este ejercicio\n-- son fromLists, matrix, nrows y ncols. \n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Matrix\n\ntype Campo   = Matrix Int\ntype Casilla = (Int,Int)\n\nejCampo1, ejCampo2 :: Campo\nejCampo1 = fromLists [[9,0,0,0],\n                      [0,0,0,0], \n                      [0,9,0,0], \n                      [0,0,0,0]]\nejCampo2 = fromLists [[9,9,0,0,0],\n                      [0,0,0,0,0],\n                      [0,9,0,0,0]]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nbuscaminas1 :: Campo -> Campo\nbuscaminas1 c = matrix m n (\\(i,j) -> minas c (i,j))\n    where m = nrows c\n          n = ncols c\n\n-- (minas c (i,j)) es el n\u00famero de minas en las casillas vecinas de la\n-- (i,j) en el campo de mina c y es 9 si en (i,j) hay una mina. Por\n-- ejemplo,\n--    minas ejCampo (1,1)  ==  9\n--    minas ejCampo (1,2)  ==  1\n--    minas ejCampo (1,3)  ==  0\n--    minas ejCampo (2,1)  ==  2\nminas :: Campo -> Casilla -> Int\nminas c (i,j) \n    | c!(i,j) == 9 = 9\n    | otherwise    = length (filter (==9) [c!(x,y) | (x,y) <- vecinas m n (i,j)])\n                     where m = nrows c\n                           n = ncols c\n\n-- (vecinas m n (i,j)) es la lista de las casillas vecinas de la (i,j) en\n-- un campo de dimensiones mxn. Por ejemplo,\n--    vecinas 4 (1,1)  ==  [(1,2),(2,1),(2,2)]\n--    vecinas 4 (1,2)  ==  [(1,1),(1,3),(2,1),(2,2),(2,3)]\n--    vecinas 4 (2,3)  ==  [(1,2),(1,3),(1,4),(2,2),(2,4),(3,2),(3,3),(3,4)]\nvecinas :: Int -> Int -> Casilla -> [Casilla]\nvecinas m n (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],\n                             b <- [max 1 (j-1)..min n (j+1)],\n                             (a,b) \/= (i,j)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nbuscaminas2 :: Campo -> Campo\nbuscaminas2 c = matrix m n (\\(i,j) -> minas (i,j))\n    where m = nrows c\n          n = ncols c\n          minas :: Casilla -> Int\n          minas (i,j) \n              | c!(i,j) == 9 = 9\n              | otherwise    = \n                  length (filter (==9) [c!(x,y) | (x,y) <- vecinas (i,j)])\n          vecinas :: Casilla -> [Casilla]\n          vecinas (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],\n                                   b <- [max 1 (j-1)..min n (j+1)],\n                                   (a,b) \/= (i,j)]\n<\/pre>\n<h4>Referencia<\/h4>\n<p>El ejercicio est\u00e1 basado en <a href=\"http:\/\/bit.ly\/1sfq0b8\">Minesweeper<\/a> de <a href=\"http:\/\/uva.onlinejudge.org\">UVa Online Judge<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Enunciado &#8212; El buscaminas es un juego cuyo objetivo es despejar un campo de minas &#8212; sin detonar ninguna. &#8212; &#8212; El campo de minas se representa mediante un cuadrado con NxN &#8212; casillas. Algunas casillas tienen un n\u00famero, este n\u00famero indica las &#8212; minas que hay en todas las casillas vecinas. Cada casilla tiene&#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":[7],"tags":[8,38,96,28,42,97,83,84,99,98,11],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/321"}],"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=321"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/321\/revisions"}],"predecessor-version":[{"id":686,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/321\/revisions\/686"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}