matrix

Matrices de Pascal

PorJosé A. Alonso 9-marzo-201816-marzo-2018

El triángulo de Pascal es un triángulo de números

         1
        1 1
       1 2 1
     1  3 3  1
    1 4  6  4 1
   1 5 10 10 5 1
  ...............

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

...............

construido de la siguiente forma

la primera fila está formada por el número 1;
las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La matriz de Pascal es la matriz cuyas filas son los elementos de la
correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es

   |1 0  0  0 0 0|
   |1 1  0  0 0 0|
   |1 2  1  0 0 0|
   |1 3  3  1 0 0|
   |1 4  6  4 1 0|
   |1 5 10 10 5 1|

|1 0 0 0 0 0|

|1 1 0 0 0 0|

|1 2 1 0 0 0|

|1 3 3 1 0 0|

|1 4 6 4 1 0|

|1 5 10 10 5 1|

Definir la función

   matrizPascal :: Int -> Matrix Integer

1	matrizPascal :: Int -> Matrix Integer

tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,

   λ> matrizPascal 6
   (  1  0  0  0  0  0 )
   (  1  1  0  0  0  0 )
   (  1  2  1  0  0  0 )
   (  1  3  3  1  0  0 )
   (  1  4  6  4  1  0 )
   (  1  5 10 10  5  1 )

λ> matrizPascal 6

( 1 0 0 0 0 0 )

( 1 1 0 0 0 0 )

( 1 2 1 0 0 0 )

( 1 3 3 1 0 0 )

( 1 4 6 4 1 0 )

( 1 5 10 10 5 1 )

Soluciones

import Data.Matrix

-- 1ª solución
-- ===========

matrizPascal :: Int -> Matrix Integer 
matrizPascal 1 = fromList 1 1 [1]
matrizPascal n = matrix n n f 
  where f (i,j) | i < n && j <  n  = p!(i,j)
                | i < n && j == n  = 0
                | j == 1 || j == n = 1
                | otherwise        = p!(i-1,j-1) + p!(i-1,j)
        p = matrizPascal (n-1)

-- 2ª solución
-- ===========

matrizPascal2 :: Int -> Matrix Integer
matrizPascal2 n = fromLists xss
  where yss = take n pascal
        xss = map (take n) (map (++ repeat 0) yss)
        
pascal :: [[Integer]]
pascal = [1] : map f pascal
    where f xs = zipWith (+) (0:xs) (xs ++ [0])

-- 3ª solución
-- ===========

matrizPascal3 :: Int -> Matrix Integer
matrizPascal3 n =  matrix n n f
  where f (i,j) | i >=  j   = comb (i-1) (j-1)
                | otherwise = 0

-- (comb n k) es el número de combinaciones (o coeficiente binomial) de
-- n sobre k. Por ejemplo,
comb :: Int -> Int -> Integer
comb n k = product [n',n'-1..n'-k'+1] `div` product [1..k']
  where n' = fromIntegral n
        k' = fromIntegral k

-- 4ª solución
-- ===========

matrizPascal4 :: Int -> Matrix Integer
matrizPascal4 n = p
  where p = matrix n n (\(i,j) -> f i j)
        f i 1 = 1
        f i j
          | j >  i    = 0
          | i == j    = 1
          | otherwise = p!(i-1,j) + p!(i-1,j-1)

-- Comparación de eficiencia
-- =========================

--    λ> maximum (matrizPascal 150)
--    46413034868354394849492907436302560970058760
--    (2.58 secs, 394,030,504 bytes)
--    λ> maximum (matrizPascal2 150)
--    46413034868354394849492907436302560970058760
--    (0.03 secs, 8,326,784 bytes)
--    λ> maximum (matrizPascal3 150)
--    46413034868354394849492907436302560970058760
--    (0.38 secs, 250,072,360 bytes)
--    λ> maximum (matrizPascal4 150)
--    46413034868354394849492907436302560970058760
--    (0.10 secs, 13,356,360 bytes)
--    
--    λ> length (show (maximum (matrizPascal2 300)))
--    89
--    (0.06 secs, 27,286,296 bytes)
--    λ> length (show (maximum (matrizPascal3 300)))
--    89
--    (2.74 secs, 2,367,037,536 bytes)
--    λ> length (show (maximum (matrizPascal4 300)))
--    89
--    (0.36 secs, 53,934,792 bytes)
--    
--    λ> length (show (maximum (matrizPascal2 700)))
--    209
--    (0.83 secs, 207,241,080 bytes)
--    λ> length (show (maximum (matrizPascal4 700)))
--    209
--    (2.22 secs, 311,413,008 bytes)

import Data.Matrix

-- 1ª solución

-- ===========

matrizPascal :: Int -> Matrix Integer

matrizPascal 1 = fromList 1 1 [1]

matrizPascal n = matrix n n f

where f (i,j) | i < n && j < n = p!(i,j)

| i < n && j == n = 0

| j == 1 || j == n = 1

| otherwise = p!(i-1,j-1) + p!(i-1,j)

p = matrizPascal (n-1)

-- 2ª solución

-- ===========

matrizPascal2 :: Int -> Matrix Integer

matrizPascal2 n = fromLists xss

where yss = take n pascal

xss = map (take n) (map (++ repeat 0) yss)

pascal :: [[Integer]]

pascal = [1] : map f pascal

where f xs = zipWith (+) (0:xs) (xs ++ [0])

-- 3ª solución

-- ===========

matrizPascal3 :: Int -> Matrix Integer

matrizPascal3 n = matrix n n f

where f (i,j) | i >= j = comb (i-1) (j-1)

| otherwise = 0

-- (comb n k) es el número de combinaciones (o coeficiente binomial) de

-- n sobre k. Por ejemplo,

comb :: Int -> Int -> Integer

comb n k = product [n',n'-1..n'-k'+1] `div` product [1..k']

where n' = fromIntegral n

k' = fromIntegral k

-- 4ª solución

-- ===========

matrizPascal4 :: Int -> Matrix Integer

matrizPascal4 n = p

where p = matrix n n (\(i,j) -> f i j)

f i 1 = 1

f i j

| j > i = 0

| i == j = 1

| otherwise = p!(i-1,j) + p!(i-1,j-1)

-- Comparación de eficiencia

-- =========================

-- λ> maximum (matrizPascal 150)

-- 46413034868354394849492907436302560970058760

-- (2.58 secs, 394,030,504 bytes)

-- λ> maximum (matrizPascal2 150)

-- 46413034868354394849492907436302560970058760

-- (0.03 secs, 8,326,784 bytes)

-- λ> maximum (matrizPascal3 150)

-- 46413034868354394849492907436302560970058760

-- (0.38 secs, 250,072,360 bytes)

-- λ> maximum (matrizPascal4 150)

-- 46413034868354394849492907436302560970058760

-- (0.10 secs, 13,356,360 bytes)

-- λ> length (show (maximum (matrizPascal2 300)))

-- 89

-- (0.06 secs, 27,286,296 bytes)

-- λ> length (show (maximum (matrizPascal3 300)))

-- 89

-- (2.74 secs, 2,367,037,536 bytes)

-- λ> length (show (maximum (matrizPascal4 300)))

-- 89

-- (0.36 secs, 53,934,792 bytes)

-- λ> length (show (maximum (matrizPascal2 700)))

-- 209

-- (0.83 secs, 207,241,080 bytes)

-- λ> length (show (maximum (matrizPascal4 700)))

-- 209

-- (2.22 secs, 311,413,008 bytes)

Ampliación de una matriz

PorJosé A. Alonso 12-abril-201720-abril-2017

Definir, usando Data.Matrix, la función

   ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

1	ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

   ej1 :: Matrix Char
   ej1 = fromLists [" x ",
                    "x x",
                    " x "]

ej1 :: Matrix Char

ej1 = fromLists [" x ",

"x x",

" x "]

entonces

   λ> ampliaMatriz ej1 1 2
   ( ' ' ' ' 'x' 'x' ' ' ' ' )
   ( 'x' 'x' ' ' ' ' 'x' 'x' )
   ( ' ' ' ' 'x' 'x' ' ' ' ' )
   
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)
     xx  
   xx  xx
     xx  
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)
    x 
    x 
   x x
   x x
    x 
    x 
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)
     xx  
     xx  
   xx  xx
   xx  xx
     xx  
     xx  
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)
      xxx   
      xxx   
   xxx   xxx
   xxx   xxx
      xxx   
      xxx

λ> ampliaMatriz ej1 1 2

( ' ' ' ' 'x' 'x' ' ' ' ' )

( 'x' 'x' ' ' ' ' 'x' 'x' )

( ' ' ' ' 'x' 'x' ' ' ' ' )

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)

xx xx

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)

x x

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)

xx xx

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)

xxx

xxx xxx

xxx

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Soluciones

import Data.Matrix

ej1 :: Matrix Char
ej1 = fromLists [" x ",
                 "x x",
                 " x "]

-- 1ª definición
-- =============

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz p f c =
  ampliaColumnas (ampliaFilas p f) c

ampliaFilas :: Matrix a -> Int -> Matrix a
ampliaFilas p f =
  matrix (f*m) n (\(i,j) -> p!(1 + (i-1) `div` f, j))
  where m = nrows p
        n = ncols p

ampliaColumnas :: Matrix a -> Int -> Matrix a
ampliaColumnas p c =
  matrix m (c*n) (\(i,j) -> p!(i,1 + (j-1) `div` c))
  where m = nrows p
        n = ncols p

-- 2ª definición
-- =============

ampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz2 p f c =
  ampliaColumnas2 (ampliaFilas2 p f) c

ampliaFilas2 :: Matrix a -> Int -> Matrix a
ampliaFilas2 p f =
  fromLists (concatMap (replicate f) (toLists p))

ampliaColumnas2 :: Matrix a -> Int -> Matrix a
ampliaColumnas2 p c =
  fromLists (map (concatMap (replicate c)) (toLists p))

-- 3ª definición
-- =============

ampliaMatriz3 :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz3 p f c =
  ( fromLists
  . concatMap (map (concatMap (replicate c)) . replicate f)
  . toLists) p

-- Comparación de eficiencia
-- =========================

ejemplo :: Int -> Matrix Int
ejemplo n = fromList n n [1..]

--    λ> maximum (ampliaMatriz (ejemplo 10) 100 200)
--    100
--    (6.64 secs, 1,026,559,296 bytes)
--    λ> maximum (ampliaMatriz2 (ejemplo 10) 100 200)
--    100
--    (1.90 secs, 513,211,144 bytes)
--    λ> maximum (ampliaMatriz3 (ejemplo 10) 100 200)
--    100
--    (1.89 secs, 644,928,024 bytes)
--    λ> maximum (ampliaMatriz2 (ejemplo 10) 200 200)
--    100
--    (5.13 secs, 1,248,173,384 bytes)
--    λ> maximum (ampliaMatriz3 (ejemplo 10) 200 200)
--    100
--    (4.67 secs, 1,431,540,344 bytes)

import Data.Matrix

ej1 :: Matrix Char

ej1 = fromLists [" x ",

"x x",

" x "]

-- 1ª definición

-- =============

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz p f c =

ampliaColumnas (ampliaFilas p f) c

ampliaFilas :: Matrix a -> Int -> Matrix a

ampliaFilas p f =

matrix (f*m) n (\(i,j) -> p!(1 + (i-1) `div` f, j))

where m = nrows p

n = ncols p

ampliaColumnas :: Matrix a -> Int -> Matrix a

ampliaColumnas p c =

matrix m (c*n) (\(i,j) -> p!(i,1 + (j-1) `div` c))

where m = nrows p

n = ncols p

-- 2ª definición

-- =============

ampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz2 p f c =

ampliaColumnas2 (ampliaFilas2 p f) c

ampliaFilas2 :: Matrix a -> Int -> Matrix a

ampliaFilas2 p f =

fromLists (concatMap (replicate f) (toLists p))

ampliaColumnas2 :: Matrix a -> Int -> Matrix a

ampliaColumnas2 p c =

fromLists (map (concatMap (replicate c)) (toLists p))

-- 3ª definición

-- =============

ampliaMatriz3 :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz3 p f c =

( fromLists

. concatMap (map (concatMap (replicate c)) . replicate f)

. toLists) p

-- Comparación de eficiencia

-- =========================

ejemplo :: Int -> Matrix Int

ejemplo n = fromList n n [1..]

-- λ> maximum (ampliaMatriz (ejemplo 10) 100 200)

-- 100

-- (6.64 secs, 1,026,559,296 bytes)

-- λ> maximum (ampliaMatriz2 (ejemplo 10) 100 200)

-- 100

-- (1.90 secs, 513,211,144 bytes)

-- λ> maximum (ampliaMatriz3 (ejemplo 10) 100 200)

-- 100

-- (1.89 secs, 644,928,024 bytes)

-- λ> maximum (ampliaMatriz2 (ejemplo 10) 200 200)

-- 100

-- (5.13 secs, 1,248,173,384 bytes)

-- λ> maximum (ampliaMatriz3 (ejemplo 10) 200 200)

-- 100

-- (4.67 secs, 1,431,540,344 bytes)

El problema de las N torres

PorJosé A. Alonso 10-abril-201725-abril-2021

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

   ( 0 1 0 )
   ( 1 0 0 )
   ( 0 0 1 )

( 0 1 0 )

( 1 0 0 )

( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

   torres  :: Int -> [Matrix Int]
   nTorres :: Int -> Integer

1 2	torres :: Int -> [Matrix Int] nTorres :: Int -> Integer

tales que
+ (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

      λ> torres 3
      [( 1 0 0 )
       ( 0 1 0 )
       ( 0 0 1 )
      ,( 1 0 0 )
       ( 0 0 1 )
       ( 0 1 0 )
      ,( 0 1 0 )
       ( 1 0 0 )
       ( 0 0 1 )
      ,( 0 1 0 )
       ( 0 0 1 )
       ( 1 0 0 )
      ,( 0 0 1 )
       ( 1 0 0 )
       ( 0 1 0 )
      ,( 0 0 1 )
       ( 0 1 0 )
       ( 1 0 0 )
      ]

λ> torres 3

[( 1 0 0 )

( 0 1 0 )

( 0 0 1 )

,( 1 0 0 )

( 0 0 1 )

( 0 1 0 )

,( 0 1 0 )

( 1 0 0 )

( 0 0 1 )

,( 0 1 0 )

( 0 0 1 )

( 1 0 0 )

,( 0 0 1 )

( 1 0 0 )

( 0 1 0 )

,( 0 0 1 )

( 0 1 0 )

( 1 0 0 )

]

(nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,

      λ> nTorres 3
      6
      λ> length (show (nTorres (10^4)))
      35660

λ> nTorres 3

λ> length (show (nTorres (10^4)))

35660

Soluciones

import Data.List (genericLength, sort, permutations)
import Data.Matrix 

-- 1ª definición de torres
-- =======================

torres1 :: Int -> [Matrix Int]
torres1 n = 
    [permutacionAmatriz n p | p <- sort (permutations [1..n])]

permutacionAmatriz :: Int -> [Int] -> Matrix Int
permutacionAmatriz n p =
    matrix n n f
    where f (i,j) | (i,j) `elem` posiciones = 1
                  | otherwise               = 0
          posiciones = zip [1..n] p    

-- 2ª definición de torres
-- =======================

torres2 :: Int -> [Matrix Int]
torres2 = map fromLists . permutations . toLists . identity

-- El cálculo con la definición anterior es:
--    λ> identity 3
--    ( 1 0 0 )
--    ( 0 1 0 )
--    ( 0 0 1 )
--    
--    λ> toLists it
--    [[1,0,0],[0,1,0],[0,0,1]]
--    λ> permutations it
--    [[[1,0,0],[0,1,0],[0,0,1]],
--     [[0,1,0],[1,0,0],[0,0,1]],
--     [[0,0,1],[0,1,0],[1,0,0]],
--     [[0,1,0],[0,0,1],[1,0,0]],
--     [[0,0,1],[1,0,0],[0,1,0]],
--     [[1,0,0],[0,0,1],[0,1,0]]]
--    λ> map fromLists it
--    [( 1 0 0 )
--     ( 0 1 0 )
--     ( 0 0 1 )
--    ,( 0 1 0 )
--     ( 1 0 0 )
--     ( 0 0 1 )
--    ,( 0 0 1 )
--     ( 0 1 0 )
--     ( 1 0 0 )
--    ,( 0 1 0 )
--     ( 0 0 1 )
--     ( 1 0 0 )
--    ,( 0 0 1 )
--     ( 1 0 0 )
--     ( 0 1 0 )
--    ,( 1 0 0 )
--     ( 0 0 1 )
--     ( 0 1 0 )
--    ]

-- 1ª definición de nTorres
-- ========================

nTorres1 :: Int -> Integer
nTorres1 = genericLength . torres1

-- 2ª definición de nTorres
-- ========================

nTorres2 :: Int -> Integer
nTorres2 n = product [1..fromIntegral n]

-- Comparación de eficiencia
-- =========================

--    λ> nTorres1 9
--    362880
--    (4.22 secs, 693,596,128 bytes)
--    λ> nTorres2 9
--    362880
--    (0.00 secs, 0 bytes)

import Data.List (genericLength, sort, permutations)

import Data.Matrix

-- 1ª definición de torres

-- =======================

torres1 :: Int -> [Matrix Int]

torres1 n =

[permutacionAmatriz n p | p <- sort (permutations [1..n])]

permutacionAmatriz :: Int -> [Int] -> Matrix Int

permutacionAmatriz n p =

matrix n n f

where f (i,j) | (i,j) `elem` posiciones = 1

| otherwise = 0

posiciones = zip [1..n] p

-- 2ª definición de torres

-- =======================

torres2 :: Int -> [Matrix Int]

torres2 = map fromLists . permutations . toLists . identity

-- El cálculo con la definición anterior es:

-- λ> identity 3

-- ( 1 0 0 )

-- ( 0 1 0 )

-- ( 0 0 1 )

-- λ> toLists it

-- [[1,0,0],[0,1,0],[0,0,1]]

-- λ> permutations it

-- [[[1,0,0],[0,1,0],[0,0,1]],

-- [[0,1,0],[1,0,0],[0,0,1]],

-- [[0,0,1],[0,1,0],[1,0,0]],

-- [[0,1,0],[0,0,1],[1,0,0]],

-- [[0,0,1],[1,0,0],[0,1,0]],

-- [[1,0,0],[0,0,1],[0,1,0]]]

-- λ> map fromLists it

-- [( 1 0 0 )

-- ( 0 1 0 )

-- ( 0 0 1 )

-- ,( 0 1 0 )

-- ( 1 0 0 )

-- ( 0 0 1 )

-- ,( 0 0 1 )

-- ( 0 1 0 )

-- ( 1 0 0 )

-- ,( 0 1 0 )

-- ( 0 0 1 )

-- ( 1 0 0 )

-- ,( 0 0 1 )

-- ( 1 0 0 )

-- ( 0 1 0 )

-- ,( 1 0 0 )

-- ( 0 0 1 )

-- ( 0 1 0 )

-- ]

-- 1ª definición de nTorres

-- ========================

nTorres1 :: Int -> Integer

nTorres1 = genericLength . torres1

-- 2ª definición de nTorres

-- ========================

nTorres2 :: Int -> Integer

nTorres2 n = product [1..fromIntegral n]

-- Comparación de eficiencia

-- =========================

-- λ> nTorres1 9

-- 362880

-- (4.22 secs, 693,596,128 bytes)

-- λ> nTorres2 9

-- 362880

-- (0.00 secs, 0 bytes)

Rotación de una matriz

PorJosé A. Alonso 16-marzo-201630-marzo-2016

En la siguiente figura, al rotar girando 90 grados en el sentido del reloj la matriz de la izquierda, obtenemos la de la derecha

   1 2 3        7 4 1
   4 5 6        8 5 2
   7 8 9        9 6 3

1 2 3 7 4 1

4 5 6 8 5 2

7 8 9 9 6 3

Definir la función

   rota :: Matrix Int -> Matrix Int

1	rota :: Matrix Int -> Matrix Int

tal que (rota p) es la matriz obtenida girando en el sentido del reloj la matriz cuadrada p. Por ejemplo,

   λ> rota (fromList 3 3 [1..9])
   ( 7 4 1 )
   ( 8 5 2 )
   ( 9 6 3 )
   
   λ> rota (fromList 3 3 [7,4,1,8,5,2,9,6,3])
   ( 9 8 7 )
   ( 6 5 4 )
   ( 3 2 1 )

λ> rota (fromList 3 3 [1..9])

( 7 4 1 )

( 8 5 2 )

( 9 6 3 )

λ> rota (fromList 3 3 [7,4,1,8,5,2,9,6,3])

( 9 8 7 )

( 6 5 4 )

( 3 2 1 )

Soluciones

import Data.Matrix

rota :: Matrix Int -> Matrix Int
rota p = matrix n m (\(i,j) -> p ! (n+1-j,i))
    where m = nrows p
          n = ncols p

import Data.Matrix

rota :: Matrix Int -> Matrix Int

rota p = matrix n m (\(i,j) -> p ! (n+1-j,i))

where m = nrows p

n = ncols p

Buscaminas

PorJosé A. Alonso 19-junio-201425-abril-2021

Enunciado

-- El buscaminas es un juego cuyo objetivo es despejar un campo de minas
-- sin detonar ninguna. 
-- 
-- El campo de minas se representa mediante un cuadrado con NxN
-- casillas. Algunas casillas tienen un número, este número indica las
-- minas que hay en todas las casillas vecinas. Cada casilla tiene como
-- máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda
-- contiene dos minas, cada una representada por el número 9, y a la 
-- derecha se muestra el campo obtenido anotando las minas vecinas de
-- cada casilla
--    9 0 0 0       9 1 0 0
--    0 0 0 0       2 2 1 0
--    0 9 0 0       1 9 1 0
--    0 0 0 0       1 1 1 0
-- de la misma forma, la anotación del siguiente a la izquierda es el de
-- la derecha 
--    9 9 0 0 0     9 9 1 0 0
--    0 0 0 0 0     3 3 2 0 0
--    0 9 0 0 0     1 9 1 0 0
--
-- En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra
-- en http://bit.ly/1hWVNJD
-- 
-- Los campos de minas se representan mediante matrices: 
--    type Campo = Matrix Int
-- Por ejemplo, los anteriores campos de la izquierda se definen por
--    ejCampo1, ejCampo2 :: Campo
--    ejCampo1 = fromLists [[9,0,0,0],
--                          [0,0,0,0], 
--                          [0,9,0,0], 
--                          [0,0,0,0]]
--    ejCampo2 = fromLists [[9,9,0,0,0],
--                          [0,0,0,0,0],
--                          [0,9,0,0,0]]
-- 
-- Definir la función
--    buscaminas :: Campo -> Campo
-- tal que (buscaminas c) es el campo obtenido anotando las minas
-- vecinas de cada casilla. Por ejemplo,
--    ghci> buscaminas ejCampo1
--    ( 9 1 0 0 )
--    ( 2 2 1 0 )
--    ( 1 9 1 0 )
--    ( 1 1 1 0 )
--
--    ghci> buscaminas ejCampo2
--    ( 9 9 1 0 0 )
--    ( 3 3 2 0 0 )
--    ( 1 9 1 0 0 )
-- 
-- Nota. Las funciones de la librería de matrices útiles para este ejercicio
-- son fromLists, matrix, nrows y ncols.

-- El buscaminas es un juego cuyo objetivo es despejar un campo de minas

-- sin detonar ninguna.

-- El campo de minas se representa mediante un cuadrado con NxN

-- casillas. Algunas casillas tienen un número, este número indica las

-- minas que hay en todas las casillas vecinas. Cada casilla tiene como

-- máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda

-- contiene dos minas, cada una representada por el número 9, y a la

-- derecha se muestra el campo obtenido anotando las minas vecinas de

-- cada casilla

-- 9 0 0 0 9 1 0 0

-- 0 0 0 0 2 2 1 0

-- 0 9 0 0 1 9 1 0

-- 0 0 0 0 1 1 1 0

-- de la misma forma, la anotación del siguiente a la izquierda es el de

-- la derecha

-- 9 9 0 0 0 9 9 1 0 0

-- 0 0 0 0 0 3 3 2 0 0

-- 0 9 0 0 0 1 9 1 0 0

-- En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra

-- en http://bit.ly/1hWVNJD

-- Los campos de minas se representan mediante matrices:

-- type Campo = Matrix Int

-- Por ejemplo, los anteriores campos de la izquierda se definen por

-- ejCampo1, ejCampo2 :: Campo

-- ejCampo1 = fromLists [[9,0,0,0],

-- [0,0,0,0],

-- [0,9,0,0],

-- [0,0,0,0]]

-- ejCampo2 = fromLists [[9,9,0,0,0],

-- [0,0,0,0,0],

-- [0,9,0,0,0]]

-- Definir la función

-- buscaminas :: Campo -> Campo

-- tal que (buscaminas c) es el campo obtenido anotando las minas

-- vecinas de cada casilla. Por ejemplo,

-- ghci> buscaminas ejCampo1

-- ( 9 1 0 0 )

-- ( 2 2 1 0 )

-- ( 1 9 1 0 )

-- ( 1 1 1 0 )

-- ghci> buscaminas ejCampo2

-- ( 9 9 1 0 0 )

-- ( 3 3 2 0 0 )

-- ( 1 9 1 0 0 )

-- Nota. Las funciones de la librería de matrices útiles para este ejercicio

-- son fromLists, matrix, nrows y ncols.

Soluciones

import Data.Matrix

type Campo   = Matrix Int
type Casilla = (Int,Int)

ejCampo1, ejCampo2 :: Campo
ejCampo1 = fromLists [[9,0,0,0],
                      [0,0,0,0], 
                      [0,9,0,0], 
                      [0,0,0,0]]
ejCampo2 = fromLists [[9,9,0,0,0],
                      [0,0,0,0,0],
                      [0,9,0,0,0]]

-- 1ª solución
-- ===========

buscaminas1 :: Campo -> Campo
buscaminas1 c = matrix m n (\(i,j) -> minas c (i,j))
    where m = nrows c
          n = ncols c

-- (minas c (i,j)) es el número de minas en las casillas vecinas de la
-- (i,j) en el campo de mina c y es 9 si en (i,j) hay una mina. Por
-- ejemplo,
--    minas ejCampo (1,1)  ==  9
--    minas ejCampo (1,2)  ==  1
--    minas ejCampo (1,3)  ==  0
--    minas ejCampo (2,1)  ==  2
minas :: Campo -> Casilla -> Int
minas c (i,j) 
    | c!(i,j) == 9 = 9
    | otherwise    = length (filter (==9) [c!(x,y) | (x,y) <- vecinas m n (i,j)])
                     where m = nrows c
                           n = ncols c

-- (vecinas m n (i,j)) es la lista de las casillas vecinas de la (i,j) en
-- un campo de dimensiones mxn. Por ejemplo,
--    vecinas 4 (1,1)  ==  [(1,2),(2,1),(2,2)]
--    vecinas 4 (1,2)  ==  [(1,1),(1,3),(2,1),(2,2),(2,3)]
--    vecinas 4 (2,3)  ==  [(1,2),(1,3),(1,4),(2,2),(2,4),(3,2),(3,3),(3,4)]
vecinas :: Int -> Int -> Casilla -> [Casilla]
vecinas m n (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],
                             b <- [max 1 (j-1)..min n (j+1)],
                             (a,b) /= (i,j)]

-- 2ª solución
-- ===========

buscaminas2 :: Campo -> Campo
buscaminas2 c = matrix m n (\(i,j) -> minas (i,j))
    where m = nrows c
          n = ncols c
          minas :: Casilla -> Int
          minas (i,j) 
              | c!(i,j) == 9 = 9
              | otherwise    = 
                  length (filter (==9) [c!(x,y) | (x,y) <- vecinas (i,j)])
          vecinas :: Casilla -> [Casilla]
          vecinas (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],
                                   b <- [max 1 (j-1)..min n (j+1)],
                                   (a,b) /= (i,j)]

import Data.Matrix

type Campo = Matrix Int

type Casilla = (Int,Int)

ejCampo1, ejCampo2 :: Campo

ejCampo1 = fromLists [[9,0,0,0],

[0,0,0,0],

[0,9,0,0],

[0,0,0,0]]

ejCampo2 = fromLists [[9,9,0,0,0],

[0,0,0,0,0],

[0,9,0,0,0]]

-- 1ª solución

-- ===========

buscaminas1 :: Campo -> Campo

buscaminas1 c = matrix m n (\(i,j) -> minas c (i,j))

where m = nrows c

n = ncols c

-- (minas c (i,j)) es el número de minas en las casillas vecinas de la

-- (i,j) en el campo de mina c y es 9 si en (i,j) hay una mina. Por

-- ejemplo,

-- minas ejCampo (1,1) == 9

-- minas ejCampo (1,2) == 1

-- minas ejCampo (1,3) == 0

-- minas ejCampo (2,1) == 2

minas :: Campo -> Casilla -> Int

minas c (i,j)

| c!(i,j) == 9 = 9

| otherwise = length (filter (==9) [c!(x,y) | (x,y) <- vecinas m n (i,j)])

where m = nrows c

n = ncols c

-- (vecinas m n (i,j)) es la lista de las casillas vecinas de la (i,j) en

-- un campo de dimensiones mxn. Por ejemplo,

-- vecinas 4 (1,1) == [(1,2),(2,1),(2,2)]

-- vecinas 4 (1,2) == [(1,1),(1,3),(2,1),(2,2),(2,3)]

-- vecinas 4 (2,3) == [(1,2),(1,3),(1,4),(2,2),(2,4),(3,2),(3,3),(3,4)]

vecinas :: Int -> Int -> Casilla -> [Casilla]

vecinas m n (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],

b <- [max 1 (j-1)..min n (j+1)],

(a,b) /= (i,j)]

-- 2ª solución

-- ===========

buscaminas2 :: Campo -> Campo

buscaminas2 c = matrix m n (\(i,j) -> minas (i,j))

where m = nrows c

n = ncols c

minas :: Casilla -> Int

minas (i,j)

| c!(i,j) == 9 = 9

| otherwise =

length (filter (==9) [c!(x,y) | (x,y) <- vecinas (i,j)])

vecinas :: Casilla -> [Casilla]

vecinas (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],

b <- [max 1 (j-1)..min n (j+1)],

(a,b) /= (i,j)]

Referencia

El ejercicio está basado en Minesweeper de UVa Online Judge.

Matrices de Pascal

Soluciones

Ampliación de una matriz

Soluciones

El problema de las N torres

Soluciones

Rotación de una matriz

Soluciones

Buscaminas

Enunciado

Soluciones

Referencia

Entradas recientes

Buscar

Correo electrónico