Menu Close

Etiqueta: tail

Mínimos locales

Enunciado

-- Un mínimo local de una lista es un elemento de la lista que es menor
-- que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un
-- mínimo local de [3,2,1,3,7,7,1,0,2] ya que es menor  que 2 (su
-- predecesor) y que 3 (su sucesor). 
-- 
-- Definir la función
--    minimosLocales :: Ord a => [a] -> [a]
-- tal que (minimosLocales xs) es la lista de los mínimos locales de la
-- lista xs. Por ejemplo,
--    minimosLocales [3,2,1,3,7,7,9,6,8]  ==  [1,6]
--    minimosLocales [1..100]             ==  []
--    minimosLocales "mqexvzat"           ==  "eva"

Soluciones

[schedule expon=’2014-11-26′ expat=”06:00″]
  • Las soluciones se pueden escribir en los comentarios hasta el 26 de noviembre.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>
[/schedule] [schedule on=’2014-11-26′ at=”06:00″]
-- 1ª definición (por recursión):
minimosLocales1 :: Ord a => [a] -> [a]
minimosLocales1 (x:y:z:xs) | y < x && y < z = y : minimosLocales1 (z:xs)
                           | otherwise      = minimosLocales1 (y:z:xs)
minimosLocales1 _                           = []
 
-- 2ª definición (por comprensión):
minimosLocales2 :: Ord a => [a] -> [a]
minimosLocales2 xs = 
    [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y < x, y < z]
[/schedule]

Suma de todos los anteriores.

Enunciado

-- Definir la función
--    sumaAnteriores :: [Integer] -> Bool
-- tal que (sumaAnteriores xs) se verifica si cada elemento de la lista
-- xs (excepto el primero) es la suma de sus anteriores elementos en la
-- lista. Por ejemplo,  
--    sumaAnteriores [3,3,6,12]  ==  True
--    sumaAnteriores [3,3,7,10]  ==  False
--    sumaAnteriores [3]         ==  True
--    sumaAnteriores []          ==  True

Soluciones

import Test.QuickCheck
 
-- 1ª definición (por recursión):
sumaAnteriores :: [Integer] -> Bool
sumaAnteriores xs = aux (reverse xs)
    where aux []     = True
          aux [_]    = True
          aux (x:xs) = x == sum xs && aux xs
 
-- 2ª definición (por comprensión):
sumaAnteriores2 :: [Integer] -> Bool
sumaAnteriores2 (x:y:zs) = 
    x == y && and [b == 2*a | (a,b) <- adyacentes (y:zs)]
    where adyacentes xs = zip xs (tail xs)
sumaAnteriores2 _ = True
 
-- La propiedad de equivalencia es
prop_equiv_sumaAnteriores :: [Integer] -> Bool
prop_equiv_sumaAnteriores xs = 
    sumaAnteriores xs == sumaAnteriores2 xs

Representación de Zeckendorf

Los primeros números de Fibonacci son

  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.

El teorema de Zeckendorf establece que todo entero positivo n se puede representar, de manera única, como la suma de números de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representación de Zeckendorf de n. Por ejemplo, la representación de Zeckendorf de 100 es

  100 = 89 + 8 + 3

Hay otras formas de representar 100 como sumas de números de Fibonacci; por ejemplo,

  100 = 89 + 8 + 2 + 1
  100 = 55 + 34 + 8 + 3

pero no son representaciones de Zeckendorf porque 1 y 2 son números de Fibonacci consecutivos, al igual que 34 y 55.

Ejercicio

-- Definir la función
--    zeckendorf :: Integer -> [Integer]
-- tal que (zeckendorf n) es la representación de Zeckendorf de n. Por
-- ejemplo, 
--    zeckendorf 100       == [89,8,3]
--    zeckendorf 2014      == [1597,377,34,5,1]
--    zeckendorf 28656     == [17711,6765,2584,987,377,144,55,21,8,3,1]
--    zeckendorf 14930396  == [14930352,34,8,2]

Soluciones

-- 1ª solución
-- ===========
zeckendorf1 :: Integer -> [Integer]
zeckendorf1 n = reverse (head (aux n (tail fibs)))
    where aux 0 _ = [[]]
          aux n (x:y:zs) 
              | x <= n     = [x:xs | xs <- aux (n-x) zs] ++ aux n (y:zs)
              | otherwise  = []
 
-- fibs es la la sucesión de los números de Fibonacci. Por ejemplo,
--    take 14 fibs  == [1,1,2,3,5,8,13,21,34,55,89,144,233,377]
fibs :: [Integer]
fibs = 1 : scanl (+) 1 fibs
 
-- 2ª solución
-- ===========
zeckendorf2 :: Integer -> [Integer]
zeckendorf2 n = aux n (reverse (takeWhile (<= n) fibs))
    where aux 0 _ = []
          aux n (x:xs) = x : aux (n-x) (dropWhile (>n-x) xs)
 
-- 3ª solución
-- ===========
zeckendorf3 :: Integer -> [Integer]
zeckendorf3 0 = []
zeckendorf3 n = x : zeckendorf3 (n - x) 
    where x = last (takeWhile (<= n) fibs)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    ghci> zeckendorf1 300000
--    [196418,75025,17711,6765,2584,987,377,89,34,8,2]
--    (0.72 secs, 58478576 bytes)
--    ghci> zeckendorf2 300000
--    [196418,75025,17711,6765,2584,987,377,89,34,8,2]
--    (0.00 secs, 517852 bytes)
--    ghci> zeckendorf3 300000
--    [196418,75025,17711,6765,2584,987,377,89,34,8,2]
--    (0.00 secs, 515360 bytes)
-- Se observa que las definiciones más eficientes son la 2ª y la 3ª.

Referencias

Este ejercicio se basa en el problema Zeckendorf representation de Programming Praxis.

La representación de Zeckendorf se describe en el artículo de la Wikipedia Zeckendorf’s theorem.

Número de pares de elementos adyacentes iguales en una matriz

Enunciado

-- Definir la función
--    numeroParesAdyacentesIguales :: Eq a => [[a]] -> Int
-- tal que (numeroParesAdyacentesIguales xss) es el número de pares de
-- elementos adyacentes (en la misma fila o columna) iguales de la
-- matriz xss. Por ejemplo,
--    numeroParesAdyacentesIguales [[0,1],[0,2]]              ==  1
--    numeroParesAdyacentesIguales [[0,0],[1,2]]              ==  1
--    numeroParesAdyacentesIguales [[0,1],[0,0]]              ==  2
--    numeroParesAdyacentesIguales [[1,2],[1,4],[4,4]]        ==  3
--    numeroParesAdyacentesIguales ["ab","aa"]                ==  2
--    numeroParesAdyacentesIguales [[0,0,0],[0,0,0],[0,0,0]]  ==  12
--    numeroParesAdyacentesIguales [[0,0,0],[0,1,0],[0,0,0]]  ==  8

Soluciones

import Data.List
import Data.Array
 
-- 1ª solución (Por comprensión)
-- =============================
 
numeroParesAdyacentesIguales1 :: Eq a => [[a]] -> Int
numeroParesAdyacentesIguales1 xss =
    numeroParesAdyacentesIgualesFilas xss +
    numeroParesAdyacentesIgualesFilas (transpose xss)
 
-- (numeroParesAdyacentesIgualesFilas xss) es el número de pares de
-- elementos consecutivos (en la misma fila) iguales de la matriz
-- xss. Por ejemplo, 
--    ghci> numeroParesAdyacentesIgualesFilas [[0,0,1,0],[0,1,1,0],[0,1,0,1]]
--    2
--    ghci> numeroParesAdyacentesIgualesFilas ["0010","0110","0101"]
--    2
numeroParesAdyacentesIgualesFilas :: Eq a => [[a]] -> Int
numeroParesAdyacentesIgualesFilas xss =
    sum [numeroParesAdyacentesIgualesFila xs | xs <- xss]
 
-- La función anterior se puede definir con map
numeroParesAdyacentesIgualesFilas2 :: Eq a => [[a]] -> Int
numeroParesAdyacentesIgualesFilas2 xss =
    sum (map numeroParesAdyacentesIgualesFila xss)
 
-- y también se puede definir sin argumentos:
numeroParesAdyacentesIgualesFilas3 :: Eq a => [[a]] -> Int
numeroParesAdyacentesIgualesFilas3 =
    sum . (map numeroParesAdyacentesIgualesFila)
 
-- (numeroParesAdyacentesIgualesFila xs) es el número de pares de
-- elementos consecutivos de la lista xs. Por ejemplo, 
numeroParesAdyacentesIgualesFila :: Eq a => [a] -> Int
numeroParesAdyacentesIgualesFila xs =
    length [(x,y) | (x,y) <- zip xs (tail xs), x == y]
 
-- 2ª solución (Por composición)
-- =============================
 
-- numeroParesAdyacentesIguales2 :: Eq a => [[a]] -> Int
numeroParesAdyacentesIguales2 xss =
    length (concatMap tail (concatMap group (xss ++ transpose xss)))
 
-- 3ª solución (con matrices)
-- ==========================
 
numeroParesAdyacentesIguales3 :: Eq a => [[a]] -> Int
numeroParesAdyacentesIguales3 xss =
    length [(i,j) | i <- [1..n-1], j <- [1..m], p!(i,j) == p!(i+1,j)] + 
    length [(i,j) | i <- [1..n], j <- [1..m-1], p!(i,j) == p!(i,j+1)]
    where m = length xss
          n = length (head xss)
          p = listArray ((1,1),(m,n)) (concat xss)

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]