Medio

Intercalación de n copias

PorJosé A. Alonso 27-junio-201429-noviembre-2014

Enunciado

-- Definir la función 
--    intercala :: Int -> a -> [a] -> [[a]]
-- tal que (intercala n x ys) es la lista de la listas obtenidas
-- intercalando n copias de x en ys. Por ejemplo,
--    intercala 2 'a' "bc" == ["bcaa","baca","baac","abca","abac","aabc"]
--    intercala 2 'a' "c"  == ["caa","aca","aac"]
--    intercala 1 'a' "c"  == ["ca","ac"]
--    intercala 0 'a' "c"  == ["c"]
-- Nota: No importa el orden de los elementos.

-- Definir la función

-- intercala :: Int -> a -> [a] -> [[a]]

-- tal que (intercala n x ys) es la lista de la listas obtenidas

-- intercalando n copias de x en ys. Por ejemplo,

-- intercala 2 'a' "bc" == ["bcaa","baca","baac","abca","abac","aabc"]

-- intercala 2 'a' "c" == ["caa","aca","aac"]

-- intercala 1 'a' "c" == ["ca","ac"]

-- intercala 0 'a' "c" == ["c"]

-- Nota: No importa el orden de los elementos.

Soluciones

import Data.List 

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

intercala1 :: Int -> a -> [a] -> [[a]]
intercala1 0 _ xs     = [xs]
intercala1 n y []     = [replicate n y]
intercala1 n y (x:xs) = 
    concat [[replicate i y ++ (x:zs) | zs <- intercala1 (n-i) y xs]
            | i <- [0..n]]

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

intercala2 :: Eq a => Int -> a -> [a] -> [[a]]
intercala2 n x ys = nub (aux n x ys)
    where 
      aux 0 _ ys = [ys]
      aux n x ys = concat [intercalaUno x zs | zs <- aux (n-1) x ys]

--    intercalaUno 'a' "bc"  == ["abc","bac","bca"]
intercalaUno :: a -> [a] -> [[a]]
intercalaUno x []     = [[x]]
intercalaUno x (y:ys) = (x:y:ys) : [y:zs | zs <- intercalaUno x ys]

import Data.List

-- 1ª solución

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

intercala1 :: Int -> a -> [a] -> [[a]]

intercala1 0 _ xs = [xs]

intercala1 n y [] = [replicate n y]

intercala1 n y (x:xs) =

concat [[replicate i y ++ (x:zs) | zs <- intercala1 (n-i) y xs]

| i <- [0..n]]

-- 2ª solución

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

intercala2 :: Eq a => Int -> a -> [a] -> [[a]]

intercala2 n x ys = nub (aux n x ys)

where

aux 0 _ ys = [ys]

aux n x ys = concat [intercalaUno x zs | zs <- aux (n-1) x ys]

-- intercalaUno 'a' "bc" == ["abc","bac","bca"]

intercalaUno :: a -> [a] -> [[a]]

intercalaUno x [] = [[x]]

intercalaUno x (y:ys) = (x:y:ys) : [y:zs | zs <- intercalaUno x ys]

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

Entero positivo de la cadena

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

Enunciado

-- Definir la función
--    enteroPositivo :: String -> Maybe Int
-- tal que (enteroPositivo cs) es justo el contenido de la cadena cs, si
-- dicho contenido es un entero positivo, y Nothing en caso contrario. 
-- Por ejemplo, 
--    enteroPositivo "235"    ==  Just 235
--    enteroPositivo "-235"   ==  Nothing
--    enteroPositivo "23.5"   ==  Nothing
--    enteroPositivo "235 "   ==  Nothing
--    enteroPositivo "cinco"  ==  Nothing
--    enteroPositivo ""       ==  Nothing

-- Definir la función

-- enteroPositivo :: String -> Maybe Int

-- tal que (enteroPositivo cs) es justo el contenido de la cadena cs, si

-- dicho contenido es un entero positivo, y Nothing en caso contrario.

-- Por ejemplo,

-- enteroPositivo "235" == Just 235

-- enteroPositivo "-235" == Nothing

-- enteroPositivo "23.5" == Nothing

-- enteroPositivo "235 " == Nothing

-- enteroPositivo "cinco" == Nothing

-- enteroPositivo "" == Nothing

Soluciones

enteroPositivo :: String -> Maybe Int
enteroPositivo ""                   = Nothing
enteroPositivo cs | todosDigitos cs = Just (read cs)
                  | otherwise       = Nothing

-- (todosDigitos cs) se verifica si todos los elementos de cs son
-- dígitos. Por ejemplo,
--    todosDigitos "235"    ==  True
--    todosDigitos "-235"   ==  False
--    todosDigitos "23.5"   ==  False
--    todosDigitos "235 "   ==  False
--    todosDigitos "cinco"  ==  False

-- 1ª definición de todosDigitos (por comprensión):
todosDigitos :: String -> Bool
todosDigitos cs = and [esDigito c | c <- cs]

-- 2ª definición de todosDigitos (por recursión):
todosDigitos2 :: String -> Bool
todosDigitos2 []     = True
todosDigitos2 (c:cs) = esDigito c && todosDigitos2 cs

-- 3ª definición de todosDigitos (por recursión):
todosDigitos3 :: String -> Bool
todosDigitos3 = foldr ((&&) . esDigito) True

-- 4ª definición de todosDigitos (con all):
todosDigitos4 :: String -> Bool
todosDigitos4 = all esDigito

-- (esDigito c) se verifica si el carácter c es un dígito. Por ejemplo,
--    esDigito '5'  ==  True
--    esDigito 'a'  ==  False

-- 1ª definición de esDigito:
esDigito1 :: Char -> Bool
esDigito1 c = c `elem` "0123456789"

-- 2ª definición de esDigito:
esDigito2 :: Char -> Bool
esDigito2 c = c `elem` ['0'..'9']

-- 3ª definición de esDigito:
esDigito3 :: Char -> Bool
esDigito3 = (`elem` ['0'..'9'])

-- 4ª definición de esDigito:
esDigito4 :: Char -> Bool
esDigito4 c = '0' <= c && c <= '9'

-- 5ª definición de esDigito:
esDigito5 :: Char -> Bool
esDigito5 = isDigit

-- Usaremos como definición de esDigito la 5ª:
esDigito :: Char -> Bool
esDigito = esDigito5

enteroPositivo :: String -> Maybe Int

enteroPositivo "" = Nothing

enteroPositivo cs | todosDigitos cs = Just (read cs)

| otherwise = Nothing

-- (todosDigitos cs) se verifica si todos los elementos de cs son

-- dígitos. Por ejemplo,

-- todosDigitos "235" == True

-- todosDigitos "-235" == False

-- todosDigitos "23.5" == False

-- todosDigitos "235 " == False

-- todosDigitos "cinco" == False

-- 1ª definición de todosDigitos (por comprensión):

todosDigitos :: String -> Bool

todosDigitos cs = and [esDigito c | c <- cs]

-- 2ª definición de todosDigitos (por recursión):

todosDigitos2 :: String -> Bool

todosDigitos2 [] = True

todosDigitos2 (c:cs) = esDigito c && todosDigitos2 cs

-- 3ª definición de todosDigitos (por recursión):

todosDigitos3 :: String -> Bool

todosDigitos3 = foldr ((&&) . esDigito) True

-- 4ª definición de todosDigitos (con all):

todosDigitos4 :: String -> Bool

todosDigitos4 = all esDigito

-- (esDigito c) se verifica si el carácter c es un dígito. Por ejemplo,

-- esDigito '5' == True

-- esDigito 'a' == False

-- 1ª definición de esDigito:

esDigito1 :: Char -> Bool

esDigito1 c = c `elem` "0123456789"

-- 2ª definición de esDigito:

esDigito2 :: Char -> Bool

esDigito2 c = c `elem` ['0'..'9']

-- 3ª definición de esDigito:

esDigito3 :: Char -> Bool

esDigito3 = (`elem` ['0'..'9'])

-- 4ª definición de esDigito:

esDigito4 :: Char -> Bool

esDigito4 c = '0' <= c && c <= '9'

-- 5ª definición de esDigito:

esDigito5 :: Char -> Bool

esDigito5 = isDigit

-- Usaremos como definición de esDigito la 5ª:

esDigito :: Char -> Bool

esDigito = esDigito5

Selección hasta el primero que falla inclusive

PorJosé A. Alonso 18-junio-201429-noviembre-2014

Enunciado

-- Definir la función
--    seleccionConFallo :: (a -> Bool) -> [a] -> [a]
-- tal que (seleccionConFallo p xs) es la lista de los elementos de xs
-- que cumplen el predicado p hasta el primero que no lo cumple
-- inclusive. Por ejemplo,
--    seleccionConFallo (<5) [3,2,5,7,1,0]  ==  [3,2,5]
--    seleccionConFallo odd [1..4]          ==  [1,2]
--    seleccionConFallo odd [1,3,5]         ==  [1,3,5]
--    seleccionConFallo (<5) [10..20]       ==  [10]

-- Definir la función

-- seleccionConFallo :: (a -> Bool) -> [a] -> [a]

-- tal que (seleccionConFallo p xs) es la lista de los elementos de xs

-- que cumplen el predicado p hasta el primero que no lo cumple

-- inclusive. Por ejemplo,

-- seleccionConFallo (<5) [3,2,5,7,1,0] == [3,2,5]

-- seleccionConFallo odd [1..4] == [1,2]

-- seleccionConFallo odd [1,3,5] == [1,3,5]

-- seleccionConFallo (<5) [10..20] == [10]

Soluciones

-- 1ª solución (por recursión):
seleccionConFallo1 :: (a -> Bool) -> [a] -> [a]
seleccionConFallo1 p []                 = []
seleccionConFallo1 p (x:xs) | p x       = x : seleccionConFallo1 p xs
                            | otherwise = [x]

-- 2ª solución (con span):
seleccionConFallo2 :: (a -> Bool) -> [a] -> [a]
seleccionConFallo2 p xs = ys ++ take 1 zs
    where (ys,zs) = span p xs

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

seleccionConFallo1 :: (a -> Bool) -> [a] -> [a]

seleccionConFallo1 p [] = []

seleccionConFallo1 p (x:xs) | p x = x : seleccionConFallo1 p xs

| otherwise = [x]

-- 2ª solución (con span):

seleccionConFallo2 :: (a -> Bool) -> [a] -> [a]

seleccionConFallo2 p xs = ys ++ take 1 zs

where (ys,zs) = span p xs

Referencia

El ejercicio está basado en el problema del 29 de abril de 1HaskellADay.

Descomposiciones como sumas de n sumandos

PorJosé A. Alonso 17-junio-201429-noviembre-2014

Enunciado

-- Definir la función
--    sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]
-- tal que (sumas n ys x) es la lista de las descomposiciones de x como
-- sumas de n sumandos en la lista ns. Por ejemplo,
--    sumas 2 [1,2] 3    ==  [[1,2],[2,1]]
--    sumas 2 [1,2] 4    ==  [[2,2]]
--    sumas 2 [1,2] 5    ==  []
--    sumas 3 [1,2] 5    ==  [[1,2,2],[2,1,2],[2,2,1]]
--    sumas 3 [1,2] 6    ==  [[2,2,2]]
--    sumas 2 [1,2,5] 6  ==  [[1,5],[5,1]]

-- Definir la función

-- sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]

-- tal que (sumas n ys x) es la lista de las descomposiciones de x como

-- sumas de n sumandos en la lista ns. Por ejemplo,

-- sumas 2 [1,2] 3 == [[1,2],[2,1]]

-- sumas 2 [1,2] 4 == [[2,2]]

-- sumas 2 [1,2] 5 == []

-- sumas 3 [1,2] 5 == [[1,2,2],[2,1,2],[2,2,1]]

-- sumas 3 [1,2] 6 == [[2,2,2]]

-- sumas 2 [1,2,5] 6 == [[1,5],[5,1]]

Soluciones

sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]
sumas 1 ys x | x `elem` ys = [[x]]
             | otherwise   = []
sumas n ys x = 
    concat [[y:zs | zs <- sumas (n-1) ys (x-y)] | y <- ys, y <= x]

sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]

sumas 1 ys x | x `elem` ys = [[x]]

| otherwise = []

sumas n ys x =

concat [[y:zs | zs <- sumas (n-1) ys (x-y)] | y <- ys, y <= x]

Referencia

El ejercicio está basado en el problema del 11 de junio de 1HaskellADay.

Intercalación de n copias

Enunciado

Soluciones

Sopa de letras

Enunciado

Soluciones

Entero positivo de la cadena

Enunciado

Soluciones

Selección hasta el primero que falla inclusive

Enunciado

Soluciones

Referencia

Descomposiciones como sumas de n sumandos

Enunciado

Soluciones

Referencia

Entradas recientes

Buscar

Correo electrónico