Matrices

Suma de una lista de vectores

PorJosé A. Alonso 19-enero-201530-noviembre-2015

Definir la función

   sumaVec :: Num a => [[a]] -> [a]

1	sumaVec :: Num a => [[a]] -> [a]

tal que (sumaVec xss) es la suma de los vectores de xss. Por ejemplo,

   sumaVec [[4,7,3],[3,1,4],[2,2,5]]  ==  [9,10,12]
   sumaVec [[4,7],[3,3],[1,4],[2,5]]  ==  [10,19]

1 2	sumaVec [[4,7,3],[3,1,4],[2,2,5]] == [9,10,12] sumaVec [[4,7],[3,3],[1,4],[2,5]] == [10,19]

Soluciones

import Data.List (transpose)
import Data.Array (listArray,(!))

-- 1ª definición (por recursión):
sumaVec1 :: Num a => [[a]] -> [a]
sumaVec1 []          = []
sumaVec1 [xs]        = xs
sumaVec1 (xs:ys:zss) = suma xs (sumaVec1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,
--    suma [4,7,3] [1,2,5]  == [5,9,8]
suma :: Num a => [a] -> [a] -> [a]
suma [] []         = []
suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith): 
sumaVec2 :: Num a => [[a]] -> [a]
sumaVec2 []       = []
sumaVec2 [xs]     = xs
sumaVec2 (xs:xss) = zipWith (+) xs (sumaVec2 xss)

-- 3ª definición (por plegado)
sumaVec3 :: Num a => [[a]] -> [a]
sumaVec3 = foldr1 (zipWith (+))

-- 4ª definición (con map y transpose):
sumaVec4 :: Num a => [[a]] -> [a]
sumaVec4 = map sum . transpose 

-- 5ª definición (con array)
-- =========================

sumaVec5 :: Num a => [[a]] -> [a]
sumaVec5 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]] 
    where m = length xss
          n = length (head xss)
          p = listArray ((1,1),(m,n)) (concat xss)

import Data.List (transpose)

import Data.Array (listArray,(!))

-- 1ª definición (por recursión):

sumaVec1 :: Num a => [[a]] -> [a]

sumaVec1 [] = []

sumaVec1 [xs] = xs

sumaVec1 (xs:ys:zss) = suma xs (sumaVec1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,

-- suma [4,7,3] [1,2,5] == [5,9,8]

suma :: Num a => [a] -> [a] -> [a]

suma [] [] = []

suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith):

sumaVec2 :: Num a => [[a]] -> [a]

sumaVec2 [] = []

sumaVec2 [xs] = xs

sumaVec2 (xs:xss) = zipWith (+) xs (sumaVec2 xss)

-- 3ª definición (por plegado)

sumaVec3 :: Num a => [[a]] -> [a]

sumaVec3 = foldr1 (zipWith (+))

-- 4ª definición (con map y transpose):

sumaVec4 :: Num a => [[a]] -> [a]

sumaVec4 = map sum . transpose

-- 5ª definición (con array)

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

sumaVec5 :: Num a => [[a]] -> [a]

sumaVec5 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]]

where m = length xss

n = length (head xss)

p = listArray ((1,1),(m,n)) (concat xss)

Sopa de letras

PorJosé A. Alonso 26-junio-201426-marzo-2022

Enunciado

-- Las matrices se puede representar mediante tablas cuyos índices son
-- pares de números naturales:  
--    type Matriz a = Array (Int,Int) a
-- 
-- Definir la función 
--    enLaSopa :: Eq a => [a] -> Matriz a -> Bool
-- tal que (enLaSopa c p) se verifica si c está en la matriz p en
-- horizontal o en vertical. Por ejemplo, si p es la matriz siguiente:
--    p :: Matriz Char
--    p = listaMatriz ["mjtholueq",
--                     "juhoolauh",
--                     "dariouhyj",
--                     "rngkploaa"]
-- entonces,
--    enLaSopa "dar"  p  ==  True   -- En horizontal a la derecha en la 3ª fila
--    enLaSopa "oir"  p  ==  True   -- En horizontal a la izquierda en la 3ª fila
--    enLaSopa "juan" p  ==  True   -- En vertical descendente en la 2ª columna
--    enLaSopa "kio"  p  ==  True   -- En vertical ascendente en la 3ª columna
--    enLaSopa "Juan" p  ==  False
--    enLaSopa "hola" p  ==  False
-- 
-- Nota. Para resolverlo, se puede usar la función isInfixOf.

-- Las matrices se puede representar mediante tablas cuyos índices son

-- pares de números naturales:

-- type Matriz a = Array (Int,Int) a

-- Definir la función

-- enLaSopa :: Eq a => [a] -> Matriz a -> Bool

-- tal que (enLaSopa c p) se verifica si c está en la matriz p en

-- horizontal o en vertical. Por ejemplo, si p es la matriz siguiente:

-- p :: Matriz Char

-- p = listaMatriz ["mjtholueq",

-- "juhoolauh",

-- "dariouhyj",

-- "rngkploaa"]

-- entonces,

-- enLaSopa "dar" p == True -- En horizontal a la derecha en la 3ª fila

-- enLaSopa "oir" p == True -- En horizontal a la izquierda en la 3ª fila

-- enLaSopa "juan" p == True -- En vertical descendente en la 2ª columna

-- enLaSopa "kio" p == True -- En vertical ascendente en la 3ª columna

-- enLaSopa "Juan" p == False

-- enLaSopa "hola" p == False

-- Nota. Para resolverlo, se puede usar la función isInfixOf.

Soluciones

-- Auxiliares
-- ==========

type Matriz a = Array (Int,Int) a

p :: Matriz Char
p = listaMatriz ["mjtholueq",
                 "juhoolauh",
                 "dariouhyj",
                 "rngkploaa"]

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

enLaSopa1 :: Eq a => [a] -> Matriz a -> Bool
enLaSopa1 c p = 
    or [isInfixOf c xs | 
        xs <- [[p!(i,j) | j <- [1..n]]     | i <- [1..m]] ++
              [[p!(i,j) | j <- [n,n-1..1]] | i <- [1..m]] ++
              [[p!(i,j) | i <- [1..m]]     | j <- [1..n]] ++
              [[p!(i,j) | i <- [m,m-1..1]] | j <- [1..n]]]
    where (_,(m,n)) = bounds p

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

enLaSopa2 :: Eq a => [a] -> Matriz a -> Bool
enLaSopa2 c p = estaEnHorizontal c p || estaEnVertical c p 

estaEnHorizontal :: Eq a => [a] -> Matriz a -> Bool
estaEnHorizontal c p =
    or [isInfixOf c xs | xs <- filasL p ++ map reverse (filasL p)]

filasL :: Matriz a -> [[a]]
filasL p = [filaMat i p | i <-[1..numFilas p]]

estaEnVertical :: Eq a => [a] -> Matriz a -> Bool
estaEnVertical c p =
    or [isInfixOf c xs | xs <- columnasL p ++ map reverse (columnasL p)]

columnasL :: Matriz a -> [[a]]
columnasL p = [columnaMat j p | j <- [1..numColumnas p]]

listaMatriz :: [[a]] -> Matriz a
listaMatriz xss = listArray ((1,1),(m,n)) (concat xss)
    where m = length xss
          n = length (head xss)

numFilas :: Matriz a -> Int
numFilas = fst . snd . bounds

numColumnas:: Matriz a -> Int
numColumnas = snd . snd . bounds

filaMat :: Int -> Matriz a -> [a]
filaMat i p = [p!(i,j) | j <- [1..n]]
    where n = numColumnas p

columnaMat :: Int -> Matriz a -> [a]
columnaMat j p = [p!(i,j) | i <- [1..m]]
    where m = numFilas p

-- Auxiliares

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

type Matriz a = Array (Int,Int) a

p :: Matriz Char

p = listaMatriz ["mjtholueq",

"juhoolauh",

"dariouhyj",

"rngkploaa"]

-- 1ª solución

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

enLaSopa1 :: Eq a => [a] -> Matriz a -> Bool

enLaSopa1 c p =

or [isInfixOf c xs |

xs <- [[p!(i,j) | j <- [1..n]] | i <- [1..m]] ++

[[p!(i,j) | j <- [n,n-1..1]] | i <- [1..m]] ++

[[p!(i,j) | i <- [1..m]] | j <- [1..n]] ++

[[p!(i,j) | i <- [m,m-1..1]] | j <- [1..n]]]

where (_,(m,n)) = bounds p

-- 2ª solución

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

enLaSopa2 :: Eq a => [a] -> Matriz a -> Bool

enLaSopa2 c p = estaEnHorizontal c p || estaEnVertical c p

estaEnHorizontal :: Eq a => [a] -> Matriz a -> Bool

estaEnHorizontal c p =

or [isInfixOf c xs | xs <- filasL p ++ map reverse (filasL p)]

filasL :: Matriz a -> [[a]]

filasL p = [filaMat i p | i <-[1..numFilas p]]

estaEnVertical :: Eq a => [a] -> Matriz a -> Bool

estaEnVertical c p =

or [isInfixOf c xs | xs <- columnasL p ++ map reverse (columnasL p)]

columnasL :: Matriz a -> [[a]]

columnasL p = [columnaMat j p | j <- [1..numColumnas p]]

listaMatriz :: [[a]] -> Matriz a

listaMatriz xss = listArray ((1,1),(m,n)) (concat xss)

where m = length xss

n = length (head xss)

numFilas :: Matriz a -> Int

numFilas = fst . snd . bounds

numColumnas:: Matriz a -> Int

numColumnas = snd . snd . bounds

filaMat :: Int -> Matriz a -> [a]

filaMat i p = [p!(i,j) | j <- [1..n]]

where n = numColumnas p

columnaMat :: Int -> Matriz a -> [a]

columnaMat j p = [p!(i,j) | i <- [1..m]]

where m = numFilas 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.

Suma de una lista de vectores

Soluciones

Sopa de letras

Enunciado

Soluciones

Buscaminas

Enunciado

Soluciones

Referencia

Entradas recientes

Buscar

Correo electrónico