Menu Close

Etiqueta: Recursión

Definición por recursión

Lista cuadrada

Enunciado

-- Definir la función
--    listaCuadrada :: Int -> a -> [a] -> [[a]] 
-- tal que (listaCuadrada n x xs) es una lista de n listas de longitud n
-- formadas con los elementos de xs completada con x, si no xs no tiene
-- suficientes elementos. Por ejemplo,
--    listaCuadrada 3 7 [0,3,5,2,4]  ==  [[0,3,5],[2,4,7],[7,7,7]]
--    listaCuadrada 3 7 [0..]        ==  [[0,1,2],[3,4,5],[6,7,8]]
--    listaCuadrada 2 'p' "eva"      ==  ["ev","ap"]
--    listaCuadrada 2 'p' ['a'..]    ==  ["ab","cd"]

Soluciones

-- 1ª definición (por recursión):
listaCuadrada1 :: Int -> a -> [a] -> [[a]] 
listaCuadrada1 n x xs =
    take n (grupos n (xs ++ repeat x))
 
-- (grupos n xs) es la lista obtenida agrupando los elementos de xs en
-- grupos de n elementos, salvo el último que puede tener menos. Por
-- ejemplo, 
--    grupos 2 [4,2,5,7,6]     ==  [[4,2],[5,7],[6]]
--    take 3 (grupos 3 [1..])  ==  [[1,2,3],[4,5,6],[7,8,9]]
grupos :: Int -> [a] -> [[a]]
grupos _ [] = []
grupos n xs = take n xs : grupos n (drop n xs)
 
-- 2ª definición (por comprensión)
listaCuadrada2 :: Int -> a -> [a] -> [[a]]
listaCuadrada2 n x xs = 
    take n [take n ys | m <- [0,n..n^2],
                        ys <- [drop m xs ++ (replicate m x)]]
 
-- 3ª definición (por iteración):
listaCuadrada3 :: Int -> a -> [a] -> [[a]] 
listaCuadrada3 n x xs =
    take n [take n ys | ys <- iterate (drop n) (xs ++ repeat x)]
 
-- 4ª definición (sin el 4º argumento):
listaCuadrada4 :: Int -> a -> [a] -> [[a]] 
listaCuadrada4 n x = 
    take n . map (take n) . iterate (drop n) . (++ repeat x)

Máximos locales

Enunciado

-- Un máximo local de una lista es un elemento de la lista que es mayor
-- que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un
-- máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su
-- predecesor) y que 3 (su sucesor).
-- 
-- Definir la función
--    maximosLocales :: Ord a => [a] -> [a]
-- tal que (maximosLocales xs) es la lista de los máximos locales de la
-- lista xs. Por ejemplo,
--    maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
--    maximosLocales [1..100]             ==  []
--    maximosLocales "adbpmqexyz"         ==  "dpq"

Soluciones

-- 1ª definición (por recursión):
maximosLocales1 :: Ord a => [a] -> [a]
maximosLocales1 (x:y:z:xs) | y > x && y > z = y : maximosLocales1 (z:xs)
                           | otherwise      = maximosLocales1 (y:z:xs)
maximosLocales1 _                           = []
 
-- 2ª definición (por comprensión):
maximosLocales2 :: Ord a => [a] -> [a]
maximosLocales2 xs = 
    [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y > x, y > z]

Primos equidistantes

Enunciado

-- Definir la función 
--    primosEquidistantes :: Integer -> [(Integer,Integer)]
-- tal que (primosEquidistantes k) es la lista de los pares de primos
-- consecutivos cuya diferencia es k. Por ejemplo,
--    take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
--    take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
--    take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
--    take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]

Solución

primosEquidistantes :: Integer -> [(Integer,Integer)]
primosEquidistantes k = aux primos
    where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)
                       | otherwise  = aux (y:ps)
 
-- (primo x) se verifica si x es primo. Por ejemplo,
--    primo 7  ==  True
--    primo 8  ==  False
primo :: Integer -> Bool
primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]
 
-- primos es la lista de los números primos. Por ejemplo,
--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]
primos :: [Integer]
primos = 2 : [x | x <- [3,5..], primo x]

Anagramas

Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, mora y roma son anagramas de amor.

Enunciado

-- Definir la función
--    anagramas :: String -> [String] -> [String]
-- tal que (anagramas x ys) es la lista de los elementos de ys que son
-- anagramas de x. Por ejemplo,
--    anagramas "amor" ["Roma","mola","loma","moRa"] ==  ["Roma","moRa"]

Soluciones

import Data.List
import Data.Char
 
-- 1ª definición (por recursión):
anagramas :: String -> [String] -> [String]
anagramas x [] = []
anagramas x (y:ys) | sonAnagramas x y = y : anagramas x ys
                   | otherwise        = anagramas x ys
 
-- (sonAnagramas xs ys) se verifica si xs e ys son anagramas. Por
-- ejemplo,
--    sonAnagramas "amor" "Roma"  ==  True
--    sonAnagramas "amor" "mola"  ==  False
sonAnagramas :: String -> String -> Bool
sonAnagramas xs ys = 
    sort (map toLower xs) == sort (map toLower ys) 
 
-- 2ª definición de sonAnagramas
sonAnagramas2 :: String -> String -> Bool
sonAnagramas2 xs ys = 
    (sort . map toLower) xs == (sort . map toLower) ys 
 
-- 2ª definición (por comprensión)
anagramas2 :: String -> [String] -> [String]
anagramas2 x ys = [y | y <- ys, sonAnagramas x y]
 
-- 3ª definición (con filter y sin el 2ª argumento)
anagramas3 :: String -> [String] -> [String]
anagramas3 x = filter (`sonAnagramas` x)

Mastermind

Introducción

El Mastermind es un juego que consiste en deducir un código numérico. Cada vez que se empieza un partido, el programa debe eligir un código, que será lo que el jugador debe adivinar en la menor cantidad de intentos posibles. Cada intento consiste en una propuesta de un código posible que propone el jugador, y una respuesta del programa. Las respuestas le darán pistas al jugador para que pueda deducir el código.

Estas pistas indican cuán cerca estuvo el número propuesto de la solución a través de dos valores: la cantidad de aciertos es la cantidad de dígitos que propuso el jugador que también están en el código en la misma posición. La cantidad de coincidencias es la cantidad de digitos que propuso el jugador que también están en el código pero en una posición distinta.

Por ejemplo, si el código que eligió el programa es el [2,6,0,7], y el jugador propone el [1,4,0,6], el programa le debe responder un acierto (el 0, que está en el código original en el mismo lugar, el tercero), y una coincidencia (el 6, que también está en el código original, pero en la segunda posición, no en el cuarto como fue propuesto). Si el jugador hubiera propuesto el [3,5,9,1], habría obtenido como respuesta ningún acierto y ninguna coincidencia, ya que no hay números en común con el código original, y si se obtienen cuatro aciertos es porque el jugador adivinó el código y ganó el juego.

Enunciado

-- Definir la función
--    mastermind :: [Int] -> [Int] -> (Int,Int)
-- tal que (mastermind xs ys) es el par formado por los números de
-- aciertos y de coincidencias entre xs e ys. Por ejemplo,
--    mastermind [2,6,0,7] [1,4,0,6]  ==  (1,1)
--    mastermind [2,6,0,7] [3,5,9,1]  ==  (0,0)
--    mastermind [2,6,0,7] [1,6,0,4]  ==  (2,0)
--    mastermind [2,6,0,7] [2,6,0,7]  ==  (4,0)

Soluciones

import Data.List
 
-- 1ª solución (por comprensión):
mastermind :: [Int] -> [Int] -> (Int,Int)
mastermind xs ys = 
    (length (aciertos xs ys),length (coincidencias xs ys))
 
-- (aciertos xs ys) es la lista de aciertos entre xs e ys. Por ejemplo,
--    aciertos [2,6,0,7] [1,4,0,6]  ==  [0]
aciertos :: Eq a => [a] -> [a] -> [a]
aciertos xs ys = [x | (x,y) <- zip xs ys, x == y]
 
-- (coincidencia xs ys) es la lista de coincidencias entre xs e ys. Por
-- ejemplo, 
--    coincidencias [2,6,0,7] [1,4,0,6]  ==  [6]
coincidencias :: Eq a => [a] -> [a] -> [a]
coincidencias xs ys = 
    [x | x <- xs, x `elem` ys, x `notElem` zs]
    where zs = aciertos xs ys
 
-- 2ª solución (por recursión):
mastermind2 :: [Int] -> [Int] -> (Int,Int)
mastermind2 xs ys = aux xs ys 
    where aux [] [] = (0,0)
          aux (x:xs) (z:zs) 
              | x == z      = (a+1,b)
              | x `elem` ys = (a,b+1)
              | otherwise   = (a,b)
              where (a,b) = aux xs zs
 
-- 3ª solución:
mastermind3 :: [Int] -> [Int] -> (Int,Int)
mastermind3 xs ys = (nAciertos,nCoincidencias)
    where nAciertos = length [(x,y) | (x,y) <- zip xs ys, x == y]
          nCoincidencias = length (xs++ys) - length (nub (xs++ys)) - nAciertos