Menu Close

Etiqueta: Nothing

Ordenada cíclicamente

Se dice que una sucesión x(1), …, x(n) está ordenada cíclicamente si existe un índice i tal que la sucesión

   x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)

está ordenada crecientemente de forma estricta.

Definir la función

   ordenadaCiclicamente :: Ord a => [a] -> Maybe Int

tal que (ordenadaCiclicamente xs) es el índice a partir del cual está ordenada, si la lista está ordenado cíclicamente y Nothing en caso contrario. Por ejemplo,

   ordenadaCiclicamente [1,2,3,4]      ==  Just 0
   ordenadaCiclicamente [5,8,1,3]      ==  Just 2
   ordenadaCiclicamente [4,6,7,5,1,3]  ==  Nothing
   ordenadaCiclicamente [1,0,3,2]      ==  Nothing
   ordenadaCiclicamente [1,2,0]        ==  Just 2
   ordenadaCiclicamente "cdeab"        ==  Just 3

Nota: Se supone que el argumento es una lista no vacía sin elementos repetidos.

Primero no consecutivo

Definir la función

   primeroNoConsecutivo :: (Eq a,Enum a) => [a] -> Maybe a

tal que (primeroNoConsecutivo xs) es el primer elemento de la lista xs que no es igual al siguiente de su elemento anterior en xs o Nothing si tal elemento no existe. Por ejemplo

   primeroNoConsecutivo [1,2,3,4,6,7,8] == Just 6
   primeroNoConsecutivo "bcdfg"         == Just 'f'
   primeroNoConsecutivo "bcdef"         == Nothing

Soluciones

import Data.Maybe (listToMaybe)
 
-- 1ª solución
primeroNoConsecutivo1 :: (Eq a, Enum a) => [a] -> Maybe a
primeroNoConsecutivo1 xs
  | null ys   = Nothing
  | otherwise = Just (head ys)
  where ys = [y | (z,y) <- zip xs (tail xs), y /= succ z]
 
-- 2ª solución
primeroNoConsecutivo2 :: (Eq a, Enum a) => [a] -> Maybe a
primeroNoConsecutivo2 xs = 
  listToMaybe [y | (z,y) <- zip xs (tail xs), y /= succ z]
 
-- 3ª solución
primeroNoConsecutivo3 :: (Eq a,Enum a) => [a] -> Maybe a
primeroNoConsecutivo3 (x:y:zs)
  | succ x /= y = Just y 
  | otherwise   = primeroNoConsecutivo3 (y:zs)
primeroNoConsecutivo3 _ = Nothing
 
-- 4ª solución
primeroNoConsecutivo :: (Eq a,Enum a) => [a] -> Maybe a
primeroNoConsecutivo [] = Nothing
primeroNoConsecutivo (x:ys) = aux x ys
  where aux _ [] = Nothing
        aux x' (z:zs) | z == succ x' = aux z zs
                      | otherwise    = Just z

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

“La única enseñanza que un profesor puede dar, en mi opinión, es la de pensar delante de sus alumnos.”

Henri Lebesgue.

Longitud de la parte periódica

La propiedad de la longitud de la parte periódica afirma que

Si p es un número primo distinto de 2 y de 5, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a 10^n - 1.

El objetivo de este ejercicio es la verificación de dicha propiedad.

Las fracciones se representan por un par de enteros. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Fraccion = (Integer,Integer)

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])  
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

Definir, usando las funciones cocientesRestos y primerRepetido de los ejercicios anteriores, las funciones

   decimal :: Fraccion -> Decimal
   longitudPeriodo :: Fraccion -> Integer

tales que

  • (decimal f) es la representación decimal de la fracción f. Por ejemplo,
     decimal (6,2)          ==  (3,[],[])
     decimal (3,4)          ==  (0,[7,5],[])
     decimal (1,3)          ==  (0,[],[3])
     decimal (23,14)        ==  (1,[6],[4,2,8,5,7,1])
     decimal (247813,19980) ==  (12,[4,0],[3,0,5])
     decimal (1,101)        ==  (0,[],[0,0,9,9])
  • (longitudPeriodo f) es la longitud de la parte periódica de la representación decimal de la fracción f. Por ejemplo,
     longitudPeriodo (6,2)           ==  0
     longitudPeriodo (3,4)           ==  0
     longitudPeriodo (1,3)           ==  1
     longitudPeriodo (23,14)         ==  6
     longitudPeriodo (247813,19980)  ==  3
     longitudPeriodo (1,101)         ==  4
     longitudPeriodo (1,1229)        ==  1228

Comprobar con QuickCheck la propiedad de la longitud de la parte periódica; es decir, k es un número natural distinto de 0 y 2 y p es el primo k-ésimo, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a 10^n - 1..

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck
 
type Fraccion = (Integer,Integer)
type Decimal = (Integer,[Integer],[Integer])
 
decimal :: Fraccion -> Decimal
decimal (n,d) 
  | snd y == 0 = (fst x, map fst xs, [])
  | otherwise  = (fst x, map fst xs, map fst (y:zs))
  where
    qrs         = cocientesRestos (n,d)
    Just (q,r)  = primerRepetido qrs
    (x:xs,y:ys) = break (==(q,r)) qrs
    zs          = takeWhile (/=(q,r)) ys
 
cocientesRestos :: Fraccion -> [(Integer,Integer)]
cocientesRestos (n,d) =
  (q,r) : cocientesRestos (10*r, d)
  where (q,r) = quotRem n d
 
primerRepetido :: Eq a => [a] -> Maybe a
primerRepetido xs = aux xs []
  where
    aux [] _                     = Nothing
    aux (x:xs') ys | x `elem` ys = Just x
                   | otherwise   = aux xs' (x:ys) 
 
longitudPeriodo :: Fraccion -> Int
longitudPeriodo (n,d) = length xs
  where (_,_,xs) = decimal (n,d)
 
-- La propiedad es
prop_LongitudPeriodo :: Int -> Property
prop_LongitudPeriodo k =
  k > 0 && k /= 2 
  ==>
  longitudPeriodo (1,p) ==
  head [n | n <- [1..], (10^n-1) `mod` p == 0]
  where p = primes !! k
 
-- La comprobación es
--    λ> quickCheck prop_LongitudPeriodo
--    +++ OK, passed 100 tests.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

“En el desarrollo de la comprensión de los fenómenos complejos, la herramienta más poderosa de que dispone el intelecto humano es la abstracción. La abstracción surge del reconocimiento de las similitudes entre ciertos objetos, situaciones o procesos en el mundo real y de la decisión de concentrarse en estas similitudes e ignorar, por el momento, sus diferencias.”

Tony Hoare

Primer elemento repetido

Definir la función

   primerRepetido :: Eq a => [a] -> Maybe a

tal que (primerRepetido xs) es justo el primer elemento repetido de la lista xs o Nothing si no tiene elementos repetidos. Por ejemplo,

   primerRepetido [3,7,5,7,2]  ==  Just 7
   primerRepetido [3,9,5,6,2]  ==  Nothing

Soluciones

primerRepetido :: Eq a => [a] -> Maybe a
primerRepetido xs = aux xs []
  where
    aux [] _                     = Nothing
    aux (x:xs') ys | x `elem` ys = Just x
                   | otherwise   = aux xs' (x:ys)

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

“¿Cuál es el núcleo central de la ciencia de la computación? ¿Qué es lo que lo diferencia de los otros temas con los que se relaciona? ¿Qué es lo que el hilo de unión que reúne estas ramas dispares en una sola disciplina? Mi respuesta a estas preguntas es simple: es el arte de programar un ordenador. Es el arte de diseñar métodos eficientes y elegantes para conseguir que un ordenador resuelva problemas, teóricos o prácticos, pequeños o grandes, simples o complejos. Es el arte de traducir estos diseños programas correctos y eficientes.”

Tony Hoare.

Vecino en lista circular

En la lista circular [3,2,5,7,9]

  • el vecino izquierdo de 5 es 2 y su vecino derecho es 7,
  • el vecino izquierdo de 9 es 7 y su vecino derecho es 3,
  • el vecino izquierdo de 3 es 9 y su vecino derecho es 2,
  • el elemento 4 no tiene vecinos (porque no está en la lista).

Para indicar las direcciones se define el tipo de datos

   data Direccion = I | D deriving Eq

Definir la función

   vecino :: Eq a => Direccion -> [a] -> a -> Maybe a

tal que (vecino d xs x) es el vecino de x en la lista de elementos distintos xs según la dirección d. Por ejemplo,

   vecino I [3,2,5,7,9] 5  ==  Just 2
   vecino D [3,2,5,7,9] 5  ==  Just 7
   vecino I [3,2,5,7,9] 9  ==  Just 7
   vecino D [3,2,5,7,9] 9  ==  Just 3
   vecino I [3,2,5,7,9] 3  ==  Just 9
   vecino D [3,2,5,7,9] 3  ==  Just 2
   vecino I [3,2,5,7,9] 4  ==  Nothing
   vecino D [3,2,5,7,9] 4  ==  Nothing

Soluciones

data Direccion = I | D deriving Eq
 
-- 1ª solución
-- ===========
 
vecino1 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino1 d xs x = busca x (vecinos d xs)
 
-- (vecinos d xs) es la lista de elementos de xs y sus vecinos según la
-- direccioń d. Por ejemplo,
--    vecinos I [1..5]  ==  [(2,1),(3,2),(4,3),(5,4),(1,5)]
--    vecinos D [1..5]  ==  [(1,2),(2,3),(3,4),(4,5),(5,1)]
vecinos :: Direccion -> [a] -> [(a,a)]
vecinos I xs = zip (tail (cycle xs)) xs
vecinos D xs = zip xs (tail (cycle xs))
 
-- (busca x ps) es el la segunda componente de primer par de ps cuya
-- primera componente es igual a x. Por ejemplo, 
--    busca 3 [(4,1),(3,2),(3,7)]  ==  Just 2
--    busca 7 [(4,1),(3,2),(3,7)]  ==  Nothing
busca :: Eq a => a -> [(a,b)] -> Maybe b
busca x ps
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where zs = [z | (x',z) <- ps, x' == x]
 
-- 2ª solución
-- ===========
 
vecino2 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino2 d xs x = lookup x (vecinos d xs)
 
-- 3ª solución
-- ===========
 
vecino3 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino3 I xs x = lookup x (zip (tail (cycle xs)) xs) 
vecino3 D xs x = lookup x (zip xs (tail (cycle xs)))

Sucesión contadora

Definir las siguientes funciones

   numeroContado           :: Integer -> Integer
   contadora               :: Integer -> [Integer]
   lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

tales que

  • (numeroContado n) es el número obtenido al contar las repeticiones de cada una de las cifras de n. Por ejemplo,
     numeroContado 1                 == 11
     numeroContado 114213            == 31121314
     numeroContado 1111111111111111  == 161
     numeroContado 555555555500      == 20105
  • (contadora n) es la sucesión cuyo primer elemento es n y los restantes se obtienen contando el número anterior de la sucesión. Por ejemplo,
     λ> take 14 (contadora 1)
     [1,11,21,1112,3112,211213,312213,212223,114213,31121314,41122314,
      31221324,21322314,21322314]
     λ> take 14 (contadora 5)
     [5,15,1115,3115,211315,31121315,41122315,3122131415,4122231415,
      3132132415,3122331415,3122331415,3122331415,3122331415]
  • (lugarPuntoFijoContadora n k) es el menor i <= k tal que son iguales los elementos en las posiciones i e i+1 de la sucesión contadora que cominza con n. Por ejemplo,
      λ> lugarPuntoFijoContadora 1 100
      Just 12
      λ> contadora 1 !! 11
      31221324
      λ> contadora 1 !! 12
      21322314
      λ> contadora 1 !! 13
      21322314
      λ> lugarPuntoFijoContadora 1 10
      Nothing
      λ> lugarPuntoFijoContadora 5 20
      Just 10
      λ> lugarPuntoFijoContadora 40 200
      Nothing

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz.

Soluciones

import Data.List ( genericLength
                 , genericTake
                 , group
                 , nub
                 , sort
                 )
 
-- Definición de numeroContado
numeroContado :: Integer -> Integer
numeroContado n =
  (read . concat . map concat) [[(show . length) m,nub m]
                               | m <- (group . sort . show) n]
 
-- 1ª definición de contadora
contadora :: Integer -> [Integer]
contadora n = n : map numeroContado (contadora n)
 
-- 2ª definición de contadora
contadora2 :: Integer ->  [Integer]
contadora2 = iterate numeroContado 
 
-- Definición de lugarPuntoFijoContadora
lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer
lugarPuntoFijoContadora n k
  | m == k-1  = Nothing
  | otherwise = Just m
  where xs = genericTake k (contadora n)
        ds = zipWith (-) xs (tail xs)
        m  = genericLength (takeWhile (/=0) ds)

Punto de inflexión

Definir la función

   inflexion :: Ord a => [a] -> Maybe a

tal que (inflexion xs) es el primer elemento de la lista en donde se cambia de creciente a decreciente o de decreciente a creciente y Nothing si no se cambia. Por ejemplo,

   inflexion [2,2,3,5,4,6]    ==  Just 4
   inflexion [9,8,6,7,10,10]  ==  Just 7
   inflexion [2,2,3,5]        ==  Nothing
   inflexion [5,3,2,2]        ==  Nothing

Soluciones

import Data.List (find)       
import Data.Maybe (isJust, fromJust)  
 
-- 1ª solución
-- ===========
 
inflexion :: Ord a => [a] -> Maybe a
inflexion (x:y:zs) 
  | x == y    = inflexion (y:zs)
  | x <  y    = decreciente (y:zs)
  | otherwise = creciente (y:zs)
inflexion _   = Nothing
 
-- (creciente xs) es el segundo elemento de la primera parte creciente
-- de xs y Nothing, en caso contrario. Por ejemplo,
--    creciente [4,3,5,6]    ==  Just 5
--    creciente [4,3,5,2,7]  ==  Just 5
--    creciente [4,3,2]      ==  Nothing
creciente (x:y:zs) 
  | x >= y    = creciente (y:zs)
  | otherwise = Just y
creciente _   = Nothing
 
-- (decreciente xs) es el segundo elemento de la primera parte
-- decreciente de xs y Nothing, en caso contrario. Por ejemplo,
--    decreciente [4,2,3,1,0]  ==  Just 2
--    decreciente [4,5,3,1,0]  ==  Just 3
--    decreciente [4,5,7]      ==  Nothing
decreciente (x:y:zs) 
  | x <= y    = decreciente (y:zs)
  | otherwise = Just y
decreciente _ = Nothing
 
-- 2ª solución
-- ===========
 
inflexion2 :: Ord a => [a] -> Maybe a
inflexion2 = aux . signos 
  where aux [] = Nothing
        aux ((s,_):ys) | null zs   = Nothing
                       | otherwise = Just (snd (head zs))
          where zs = dropWhile (\(p,_) -> p == s) ys
 
-- (signos xs) es la lista de los pares dormado por el signo de
-- crecimiento o decrecimiento de cada elemento de xs respecto de su
-- anterior. Por ejemplo,                 
--    λ> signos [2,2,2,3,5,5,4,5,2]
--    [(1,3),(1,5),(-1,4),(1,5),(-1,2)]
signos :: Ord a => [a] -> [(Int,a)]
signos xs = [(signo x y,y) | (x,y) <- zip xs (tail xs), x /= y] 
 
-- (signo x y) es el signo de crecimiento o decrecimiento de y respecto
-- de x. 
signo :: Ord a => a -> a -> Int
signo x y | x > y     = 1
          | x < y     = -1
          | otherwise = 0
 
-- 3ª solución
-- ===========
 
inflexion3 :: Ord  a => [a] -> Maybe a
inflexion3 (x:y:xs)
  | x == y    = inflexion3 $ y:xs
  | x < y     = buscaMenor $ y:xs
  | otherwise = buscaMayor $ y:xs
inflexion3 _  = Nothing
 
buscaMenor :: Ord a => [a] -> Maybe a
buscaMenor (y:xs)
  | isJust busca = Just (snd (fromJust busca))
  | otherwise    = Nothing
  where busca = find parDecreciente (zip (y:xs) xs)
 
buscaMayor :: Ord a => [a] -> Maybe a
buscaMayor (y:xs)
  | isJust busca = Just (snd (fromJust busca))
  | otherwise    = Nothing
  where busca = find parCreciente (zip (y:xs) xs)
 
parCreciente :: Ord a => (a,a) -> Bool
parCreciente (a,b) = a < b
 
parDecreciente :: Ord a => (a,a) -> Bool
parDecreciente (a,b) = a > b
 
-- Comparación de eficiencia
-- =========================
 
--    λ> inflexion (replicate (10^7) 5 ++ [0,1])
--    Just 1
--    (4.73 secs, 3,360,141,912 bytes)
--    λ> inflexion2 (replicate (10^7) 5 ++ [0,1])
--    Just 1
--    (2.71 secs, 2,480,144,352 bytes)
--    λ> inflexion3 (replicate (10^7) 5 ++ [0,1])
--    Just 1
--    (5.06 secs, 3,360,143,680 bytes)
--    
--    λ> inflexion ([1..10^7] ++ [0,1])
--    Just 0
--    (3.60 secs, 3,120,146,728 bytes)
--    λ> inflexion2 ([1..10^7] ++ [0,1])
--    Just 0
--    (11.33 secs, 6,480,143,376 bytes)
--    λ> inflexion3 ([1..10^7] ++ [0,1])
--    Just 0
--    (3.28 secs, 3,280,140,784 bytes)
--    
--    λ> inflexion ([10^7,10^7-1..1] ++ [2,1])
--    Just 2
--    (3.62 secs, 3,200,141,784 bytes)
--    λ> inflexion2 ([10^7,10^7-1..1] ++ [2,1])
--    Just 2
--    (10.01 secs, 5,840,144,200 bytes)
--    λ> inflexion3 ([10^7,10^7-1..1] ++ [2,1])
--    Just 2
--    (3.56 secs, 3,360,145,728 bytes)