Sopa de letras
Enunciado
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
-- 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
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
-- 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 |