Data.Maybe – Exercitium

Ordenada cíclicamente

PorJosé A. Alonso 22-abril-202230-abril-2022

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)

1	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

1	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

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.

Soluciones

module Ordenada_ciclicamente where

import Test.QuickCheck (Arbitrary, Gen, NonEmptyList (NonEmpty), Property,
                        arbitrary, chooseInt, collect, quickCheck)
import Data.List       (nub, sort)
import Data.Maybe      (isJust, listToMaybe)

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

ordenadaCiclicamente1 :: Ord a => [a] -> Maybe Int
ordenadaCiclicamente1 xs = aux 0 xs
  where n = length xs
        aux i zs
          | i == n      = Nothing
          | ordenada zs = Just i
          | otherwise   = aux (i+1) (siguienteCiclo zs)

-- (ordenada xs) se verifica si la lista xs está ordenada
-- crecientemente. Por ejemplo,
--   ordenada "acd"   ==  True
--   ordenada "acdb"  ==  False
ordenada :: Ord a => [a] -> Bool
ordenada []     = True
ordenada (x:xs) = all (x <) xs && ordenada xs

-- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento
-- de xs al final del resto de xs. Por ejemplo,
--   siguienteCiclo [3,2,5]  =>  [2,5,3]
siguienteCiclo :: [a] -> [a]
siguienteCiclo []     = []
siguienteCiclo (x:xs) = xs ++ [x]

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

ordenadaCiclicamente2 :: Ord a => [a] -> Maybe Int
ordenadaCiclicamente2 xs =
  listToMaybe [n | n <- [0..length xs-1],
                   ordenada (drop n xs ++ take n xs)]

-- 3ª solución
-- ===========

ordenadaCiclicamente3 :: Ord a => [a] -> Maybe Int
ordenadaCiclicamente3 xs
  | ordenada (bs ++ as) = Just k
  | otherwise           = Nothing
  where (_,k)   = minimum (zip xs [0..])
        (as,bs) = splitAt k xs

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_ordenadaCiclicamente1 :: NonEmptyList Int -> Bool
prop_ordenadaCiclicamente1 (NonEmpty xs) =
  ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- La comprobación es
--    λ> quickCheck prop_ordenadaCiclicamente1
--    +++ OK, passed 100 tests.

-- La propiedad para analizar los casos de prueba
prop_ordenadaCiclicamente2 :: NonEmptyList Int -> Property
prop_ordenadaCiclicamente2 (NonEmpty xs) =
  collect (isJust (ordenadaCiclicamente1 xs)) $
  ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- El análisis es
--    λ> quickCheck prop_ordenadaCiclicamente2
--    +++ OK, passed 100 tests:
--    89% False
--    11% True

-- Tipo para generar listas
newtype Lista = L [Int]
  deriving Show

-- Generador de listas.
listaArbitraria :: Gen Lista
listaArbitraria = do
  x <- arbitrary
  xs <- arbitrary
  let ys = x : xs
  k <- chooseInt (0, length ys)
  let (as,bs) = splitAt k (sort (nub ys))
  return (L (bs ++ as))

-- Lista es una subclase de Arbitrary.
instance Arbitrary Lista where
  arbitrary = listaArbitraria

-- La propiedad para analizar los casos de prueba
prop_ordenadaCiclicamente3 :: Lista -> Property
prop_ordenadaCiclicamente3 (L xs) =
  collect (isJust (ordenadaCiclicamente1 xs)) $
  ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- El análisis es
--    λ> quickCheck prop_ordenadaCiclicamente3
--    +++ OK, passed 100 tests (100% True).

-- Tipo para generar
newtype Lista2 = L2 [Int]
  deriving Show

-- Generador de listas
listaArbitraria2 :: Gen Lista2
listaArbitraria2 = do
  x' <- arbitrary
  xs <- arbitrary
  let ys = x' : xs
  k <- chooseInt (0, length ys)
  let (as,bs) = splitAt k (sort (nub ys))
  n <- chooseInt (0,1)
  return (if even n
          then L2 (bs ++ as)
          else L2 ys)

-- Lista es una subclase de Arbitrary.
instance Arbitrary Lista2 where
  arbitrary = listaArbitraria2

-- La propiedad para analizar los casos de prueba
prop_ordenadaCiclicamente4 :: Lista2 -> Property
prop_ordenadaCiclicamente4 (L2 xs) =
  collect (isJust (ordenadaCiclicamente1 xs)) $
  ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- El análisis es
--    λ> quickCheck prop_ordenadaCiclicamente4
--    +++ OK, passed 100 tests:
--    51% True
--    49% False

-- La propiedad es
prop_ordenadaCiclicamente :: Lista2 -> Bool
prop_ordenadaCiclicamente (L2 xs) =
  all (== ordenadaCiclicamente1 xs)
      [ordenadaCiclicamente2 xs,
       ordenadaCiclicamente3 xs]

-- La comprobación es
--    λ> quickCheck prop_ordenadaCiclicamente
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> ordenadaCiclicamente1 ([100..4000] ++ [1..99])
--    Just 3901
--    (3.27 secs, 2,138,864,568 bytes)
--    λ> ordenadaCiclicamente2 ([100..4000] ++ [1..99])
--    Just 3901
--    (2.44 secs, 1,430,040,008 bytes)
--    λ> ordenadaCiclicamente3 ([100..4000] ++ [1..99])
--    Just 3901
--    (1.18 secs, 515,549,200 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

module Ordenada_ciclicamente where

import Test.QuickCheck (Arbitrary, Gen, NonEmptyList (NonEmpty), Property,

arbitrary, chooseInt, collect, quickCheck)

import Data.List (nub, sort)

import Data.Maybe (isJust, listToMaybe)

-- 1ª solución

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

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

ordenadaCiclicamente1 xs = aux 0 xs

where n = length xs

aux i zs

| i == n = Nothing

| ordenada zs = Just i

| otherwise = aux (i+1) (siguienteCiclo zs)

-- (ordenada xs) se verifica si la lista xs está ordenada

-- crecientemente. Por ejemplo,

-- ordenada "acd" == True

-- ordenada "acdb" == False

ordenada :: Ord a => [a] -> Bool

ordenada [] = True

ordenada (x:xs) = all (x <) xs && ordenada xs

-- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento

-- de xs al final del resto de xs. Por ejemplo,

-- siguienteCiclo [3,2,5] => [2,5,3]

siguienteCiclo :: [a] -> [a]

siguienteCiclo [] = []

siguienteCiclo (x:xs) = xs ++ [x]

-- 2ª solución

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

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

ordenadaCiclicamente2 xs =

listToMaybe [n | n <- [0..length xs-1],

ordenada (drop n xs ++ take n xs)]

-- 3ª solución

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

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

ordenadaCiclicamente3 xs

| ordenada (bs ++ as) = Just k

| otherwise = Nothing

where (_,k) = minimum (zip xs [0..])

(as,bs) = splitAt k xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_ordenadaCiclicamente1 :: NonEmptyList Int -> Bool

prop_ordenadaCiclicamente1 (NonEmpty xs) =

ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- La comprobación es

-- λ> quickCheck prop_ordenadaCiclicamente1

-- +++ OK, passed 100 tests.

-- La propiedad para analizar los casos de prueba

prop_ordenadaCiclicamente2 :: NonEmptyList Int -> Property

prop_ordenadaCiclicamente2 (NonEmpty xs) =

collect (isJust (ordenadaCiclicamente1 xs)) $

ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- El análisis es

-- λ> quickCheck prop_ordenadaCiclicamente2

-- +++ OK, passed 100 tests:

-- 89% False

-- 11% True

-- Tipo para generar listas

newtype Lista = L [Int]

deriving Show

-- Generador de listas.

listaArbitraria :: Gen Lista

listaArbitraria = do

x <- arbitrary

xs <- arbitrary

let ys = x : xs

k <- chooseInt (0, length ys)

let (as,bs) = splitAt k (sort (nub ys))

return (L (bs ++ as))

-- Lista es una subclase de Arbitrary.

instance Arbitrary Lista where

arbitrary = listaArbitraria

-- La propiedad para analizar los casos de prueba

prop_ordenadaCiclicamente3 :: Lista -> Property

prop_ordenadaCiclicamente3 (L xs) =

collect (isJust (ordenadaCiclicamente1 xs)) $

ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- El análisis es

-- λ> quickCheck prop_ordenadaCiclicamente3

-- +++ OK, passed 100 tests (100% True).

-- Tipo para generar

newtype Lista2 = L2 [Int]

deriving Show

-- Generador de listas

listaArbitraria2 :: Gen Lista2

listaArbitraria2 = do

x' <- arbitrary

xs <- arbitrary

let ys = x' : xs

k <- chooseInt (0, length ys)

let (as,bs) = splitAt k (sort (nub ys))

n <- chooseInt (0,1)

return (if even n

then L2 (bs ++ as)

else L2 ys)

-- Lista es una subclase de Arbitrary.

instance Arbitrary Lista2 where

arbitrary = listaArbitraria2

-- La propiedad para analizar los casos de prueba

prop_ordenadaCiclicamente4 :: Lista2 -> Property

prop_ordenadaCiclicamente4 (L2 xs) =

collect (isJust (ordenadaCiclicamente1 xs)) $

ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs

-- El análisis es

-- λ> quickCheck prop_ordenadaCiclicamente4

-- +++ OK, passed 100 tests:

-- 51% True

-- 49% False

-- La propiedad es

prop_ordenadaCiclicamente :: Lista2 -> Bool

prop_ordenadaCiclicamente (L2 xs) =

all (== ordenadaCiclicamente1 xs)

[ordenadaCiclicamente2 xs,

ordenadaCiclicamente3 xs]

-- La comprobación es

-- λ> quickCheck prop_ordenadaCiclicamente

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> ordenadaCiclicamente1 ([100..4000] ++ [1..99])

-- Just 3901

-- (3.27 secs, 2,138,864,568 bytes)

-- λ> ordenadaCiclicamente2 ([100..4000] ++ [1..99])

-- Just 3901

-- (2.44 secs, 1,430,040,008 bytes)

-- λ> ordenadaCiclicamente3 ([100..4000] ++ [1..99])

-- Just 3901

-- (1.18 secs, 515,549,200 bytes)

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Nuevas soluciones

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

Numeración de las ternas de números naturales

PorJosé A. Alonso 17-marzo-202215-abril-2022

Las ternas de números naturales se pueden ordenar como sigue

   (0,0,0),
   (0,0,1),(0,1,0),(1,0,0),
   (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),
   (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...
   ...

(0,0,0),

(0,0,1),(0,1,0),(1,0,0),

(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),

(0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...

...

Definir la función

   posicion :: (Int,Int,Int) -> Int

1	posicion :: (Int,Int,Int) -> Int

tal que (posicion (x,y,z)) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,

   posicion (0,1,0)  ==  2
   posicion (0,0,2)  ==  4
   posicion (0,1,1)  ==  5

posicion (0,1,0) == 2

posicion (0,0,2) == 4

posicion (0,1,1) == 5

Comprobar con QuickCheck que

la posición de (x,0,0) es x(x²+6x+11)/6
la posición de (0,y,0) es y(y²+3y+ 8)/6
la posición de (0,0,z) es z(z²+3z+ 2)/6
la posición de (x,x,x) es x(9x²+14x+7)/2

Soluciones

import Data.List (elemIndex)
import Data.Maybe (fromJust)
import Test.QuickCheck

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

posicion1 :: (Int,Int,Int) -> Int
posicion1 t = aux 0 ternas
  where aux n (t':ts) | t' == t   = n
                      | otherwise = aux (n+1) ts

-- ternas es la lista ordenada de las ternas de números naturales. Por ejemplo,
--    λ> take 9 ternas
--    [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)]
ternas :: [(Int,Int,Int)]
ternas = [(x,y,n-x-y) | n <- [0..], x <- [0..n], y <- [0..n-x]]

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

posicion2 :: (Int,Int,Int) -> Int
posicion2 t =
  head [n | (n,t') <- zip [0..] ternas, t' == t]

-- 3ª solución
-- ===========

posicion3 :: (Int,Int,Int) -> Int
posicion3 t = indice t ternas

-- (indice x ys) es el índice de x en ys. Por ejemplo,
--    indice 5 [0..]  ==  5
indice :: Eq a => a -> [a] -> Int
indice x ys = length (takeWhile (/= x) ys)

-- 4ª solución
-- ===========

posicion4 :: (Int,Int,Int) -> Int
posicion4 t = fromJust (elemIndex t ternas)

-- 5ª solución
-- ===========

posicion5 :: (Int,Int,Int) -> Int
posicion5 = fromJust . (`elemIndex` ternas)

-- Equivalencia
-- ============

-- La propiedad es
prop_posicion_equiv :: NonNegative Int
                    -> NonNegative Int
                    -> NonNegative Int
                    -> Bool
prop_posicion_equiv (NonNegative x) (NonNegative y) (NonNegative z) =
  all (== posicion1 (x,y,z))
      [f (x,y,z) | f <- [ posicion2
                        , posicion3
                        , posicion4
                        , posicion5 ]]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion_equiv
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> posicion1 (147,46,116)
--    5000000
--    (5.84 secs, 2,621,428,184 bytes)
--    λ> posicion2 (147,46,116)
--    5000000
--    (3.63 secs, 2,173,230,200 bytes)
--    λ> posicion3 (147,46,116)
--    5000000
--    (2.48 secs, 1,453,229,880 bytes)
--    λ> posicion4 (147,46,116)
--    5000000
--    (1.91 secs, 1,173,229,840 bytes)
--    λ> posicion5 (147,46,116)
--    5000000
--    (1.94 secs, 1,173,229,960 bytes)

-- En lo que sigue, usaremos la 5ª definición
posicion :: (Int,Int,Int) -> Int
posicion = posicion5

-- Propiedades
-- ===========

-- La 1ª propiedad es
prop_posicion1 :: NonNegative Int -> Bool
prop_posicion1 (NonNegative x) =
  posicion (x,0,0) == x * (x^2 + 6*x + 11) `div` 6

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion1
--    +++ OK, passed 100 tests.

-- La 2ª propiedad es
prop_posicion2 :: NonNegative Int -> Bool
prop_posicion2 (NonNegative y) =
  posicion (0,y,0) == y * (y^2 + 3*y + 8) `div` 6

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion2
--    +++ OK, passed 100 tests.

-- La 3ª propiedad es
prop_posicion3 :: NonNegative Int -> Bool
prop_posicion3 (NonNegative z) =
  posicion (0,0,z) == z * (z^2 + 3*z + 2) `div` 6

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion3
--    +++ OK, passed 100 tests.

-- La 4ª propiedad es
prop_posicion4 :: NonNegative Int -> Bool
prop_posicion4 (NonNegative x) =
  posicion (x,x,x) == x * (9 * x^2 + 14 * x + 7) `div` 2

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion4
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

import Data.List (elemIndex)

import Data.Maybe (fromJust)

import Test.QuickCheck

-- 1ª solución

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

posicion1 :: (Int,Int,Int) -> Int

posicion1 t = aux 0 ternas

where aux n (t':ts) | t' == t = n

| otherwise = aux (n+1) ts

-- ternas es la lista ordenada de las ternas de números naturales. Por ejemplo,

-- λ> take 9 ternas

-- [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)]

ternas :: [(Int,Int,Int)]

ternas = [(x,y,n-x-y) | n <- [0..], x <- [0..n], y <- [0..n-x]]

-- 2ª solución

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

posicion2 :: (Int,Int,Int) -> Int

posicion2 t =

head [n | (n,t') <- zip [0..] ternas, t' == t]

-- 3ª solución

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

posicion3 :: (Int,Int,Int) -> Int

posicion3 t = indice t ternas

-- (indice x ys) es el índice de x en ys. Por ejemplo,

-- indice 5 [0..] == 5

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

indice x ys = length (takeWhile (/= x) ys)

-- 4ª solución

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

posicion4 :: (Int,Int,Int) -> Int

posicion4 t = fromJust (elemIndex t ternas)

-- 5ª solución

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

posicion5 :: (Int,Int,Int) -> Int

posicion5 = fromJust . (`elemIndex` ternas)

-- Equivalencia

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

-- La propiedad es

prop_posicion_equiv :: NonNegative Int

-> NonNegative Int

-> Bool

prop_posicion_equiv (NonNegative x) (NonNegative y) (NonNegative z) =

all (== posicion1 (x,y,z))

[f (x,y,z) | f <- [ posicion2

, posicion3

, posicion4

, posicion5 ]]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> posicion1 (147,46,116)

-- 5000000

-- (5.84 secs, 2,621,428,184 bytes)

-- λ> posicion2 (147,46,116)

-- 5000000

-- (3.63 secs, 2,173,230,200 bytes)

-- λ> posicion3 (147,46,116)

-- 5000000

-- (2.48 secs, 1,453,229,880 bytes)

-- λ> posicion4 (147,46,116)

-- 5000000

-- (1.91 secs, 1,173,229,840 bytes)

-- λ> posicion5 (147,46,116)

-- 5000000

-- (1.94 secs, 1,173,229,960 bytes)

-- En lo que sigue, usaremos la 5ª definición

posicion :: (Int,Int,Int) -> Int

posicion = posicion5

-- Propiedades

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

-- La 1ª propiedad es

prop_posicion1 :: NonNegative Int -> Bool

prop_posicion1 (NonNegative x) =

posicion (x,0,0) == x * (x^2 + 6*x + 11) `div` 6

-- Su comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion1

-- +++ OK, passed 100 tests.

-- La 2ª propiedad es

prop_posicion2 :: NonNegative Int -> Bool

prop_posicion2 (NonNegative y) =

posicion (0,y,0) == y * (y^2 + 3*y + 8) `div` 6

-- Su comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion2

-- +++ OK, passed 100 tests.

-- La 3ª propiedad es

prop_posicion3 :: NonNegative Int -> Bool

prop_posicion3 (NonNegative z) =

posicion (0,0,z) == z * (z^2 + 3*z + 2) `div` 6

-- Su comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion3

-- +++ OK, passed 100 tests.

-- La 4ª propiedad es

prop_posicion4 :: NonNegative Int -> Bool

prop_posicion4 (NonNegative x) =

posicion (x,x,x) == x * (9 * x^2 + 14 * x + 7) `div` 2

-- Su comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion4

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

La elaboración de las soluciones se muestra en el siguiente vídeo:

Suma si todos los valores son justos

PorJosé A. Alonso 3-marzo-202210-marzo-2022

Definir la función

   sumaSiTodosJustos :: (Num a, Eq a) => [Maybe a] -> Maybe a

1	sumaSiTodosJustos :: (Num a, Eq a) => [Maybe a] -> Maybe a

tal que (sumaSiTodosJustos xs) es justo la suma de todos los elementos de xs si todos son justos (es decir, si Nothing no pertenece a xs) y Nothing en caso contrario. Por ejemplo,

   sumaSiTodosJustos [Just 2, Just 5]           == Just 7
   sumaSiTodosJustos [Just 2, Just 5, Nothing]  == Nothing

1 2	sumaSiTodosJustos [Just 2, Just 5] == Just 7 sumaSiTodosJustos [Just 2, Just 5, Nothing] == Nothing

Soluciones

import Data.Maybe (catMaybes, isJust, fromJust)
import Test.QuickCheck (quickCheck)

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

sumaSiTodosJustos1 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos1 xs
  | todosJustos xs = Just (sum [x | (Just x) <- xs])
  | otherwise      = Nothing

-- (todosJustos xs) se verifica si todos los elementos de xs son justos
-- (es decir, si Nothing no pertenece a xs) y Nothing en caso
-- contrario. Por ejemplo,
--    todosJustos [Just 2, Just 5]           == True
--    todosJustos [Just 2, Just 5, Nothing]  == False

-- 1ª definición de todosJustos:
todosJustos1 :: Eq a => [Maybe a] -> Bool
todosJustos1 = notElem Nothing

-- 2ª definición de todosJustos:
todosJustos :: Eq a => [Maybe a] -> Bool
todosJustos = all isJust

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

sumaSiTodosJustos2 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos2 xs
  | todosJustos xs = Just (sum [fromJust x | x <- xs])
  | otherwise      = Nothing

-- 3ª solución
-- ===========

sumaSiTodosJustos3 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos3 xs
  | todosJustos xs = Just (sum (map fromJust xs))
  | otherwise      = Nothing

-- 4ª solución

sumaSiTodosJustos4 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos4 xs
  | todosJustos xs = Just (sum (catMaybes xs))
  | otherwise      = Nothing

-- 5ª solución
-- ===========

sumaSiTodosJustos5 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos5 xs = suma (sequence xs)
  where suma Nothing   = Nothing
        suma (Just ys) = Just (sum ys)

-- Nota. En la solución anterior se usa la función
--    sequence :: Monad m => [m a] -> m [a]
-- tal que (sequence xs) es la mónada obtenida evaluando cada una de las
-- de xs de izquierda a derecha. Por ejemplo,
--    sequence [Just 2, Just 5]   ==  Just [2,5]
--    sequence [Just 2, Nothing]  ==  Nothing
--    sequence [[2,4],[5,7]]      ==  [[2,5],[2,7],[4,5],[4,7]]
--    sequence [[2,4],[5,7],[6]]  ==  [[2,5,6],[2,7,6],[4,5,6],[4,7,6]]
--    sequence [[2,4],[5,7],[]]   ==  []

-- 6ª solución
-- ===========

sumaSiTodosJustos6 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos6 xs = fmap sum (sequence xs)

-- 7ª solución
-- ===========

sumaSiTodosJustos7 :: (Num a, Eq a) => [Maybe a] -> Maybe a
sumaSiTodosJustos7 = fmap sum . sequence

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_sumaSiTodosJustos :: [Maybe Integer] -> Bool
prop_sumaSiTodosJustos xs =
  all (== sumaSiTodosJustos1 xs)
      [sumaSiTodosJustos2 xs,
       sumaSiTodosJustos3 xs,
       sumaSiTodosJustos4 xs,
       sumaSiTodosJustos5 xs,
       sumaSiTodosJustos6 xs,
       sumaSiTodosJustos7 xs]

verifica_sumaSiTodosJustos :: IO ()
verifica_sumaSiTodosJustos =
  quickCheck prop_sumaSiTodosJustos

-- La comprobación es
--    λ> verifica_sumaSiTodosJustos
--    +++ OK, passed 100 tests.

import Data.Maybe (catMaybes, isJust, fromJust)

import Test.QuickCheck (quickCheck)

-- 1ª solución

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

sumaSiTodosJustos1 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos1 xs

| todosJustos xs = Just (sum [x | (Just x) <- xs])

| otherwise = Nothing

-- (todosJustos xs) se verifica si todos los elementos de xs son justos

-- (es decir, si Nothing no pertenece a xs) y Nothing en caso

-- contrario. Por ejemplo,

-- todosJustos [Just 2, Just 5] == True

-- todosJustos [Just 2, Just 5, Nothing] == False

-- 1ª definición de todosJustos:

todosJustos1 :: Eq a => [Maybe a] -> Bool

todosJustos1 = notElem Nothing

-- 2ª definición de todosJustos:

todosJustos :: Eq a => [Maybe a] -> Bool

todosJustos = all isJust

-- 2ª solución

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

sumaSiTodosJustos2 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos2 xs

| todosJustos xs = Just (sum [fromJust x | x <- xs])

| otherwise = Nothing

-- 3ª solución

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

sumaSiTodosJustos3 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos3 xs

| todosJustos xs = Just (sum (map fromJust xs))

| otherwise = Nothing

-- 4ª solución

sumaSiTodosJustos4 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos4 xs

| todosJustos xs = Just (sum (catMaybes xs))

| otherwise = Nothing

-- 5ª solución

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

sumaSiTodosJustos5 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos5 xs = suma (sequence xs)

where suma Nothing = Nothing

suma (Just ys) = Just (sum ys)

-- Nota. En la solución anterior se usa la función

-- sequence :: Monad m => [m a] -> m [a]

-- tal que (sequence xs) es la mónada obtenida evaluando cada una de las

-- de xs de izquierda a derecha. Por ejemplo,

-- sequence [Just 2, Just 5] == Just [2,5]

-- sequence [Just 2, Nothing] == Nothing

-- sequence [[2,4],[5,7]] == [[2,5],[2,7],[4,5],[4,7]]

-- sequence [[2,4],[5,7],[6]] == [[2,5,6],[2,7,6],[4,5,6],[4,7,6]]

-- sequence [[2,4],[5,7],[]] == []

-- 6ª solución

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

sumaSiTodosJustos6 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos6 xs = fmap sum (sequence xs)

-- 7ª solución

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

sumaSiTodosJustos7 :: (Num a, Eq a) => [Maybe a] -> Maybe a

sumaSiTodosJustos7 = fmap sum . sequence

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_sumaSiTodosJustos :: [Maybe Integer] -> Bool

prop_sumaSiTodosJustos xs =

all (== sumaSiTodosJustos1 xs)

[sumaSiTodosJustos2 xs,

sumaSiTodosJustos3 xs,

sumaSiTodosJustos4 xs,

sumaSiTodosJustos5 xs,

sumaSiTodosJustos6 xs,

sumaSiTodosJustos7 xs]

verifica_sumaSiTodosJustos :: IO ()

verifica_sumaSiTodosJustos =

quickCheck prop_sumaSiTodosJustos

-- La comprobación es

-- λ> verifica_sumaSiTodosJustos

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Número de ocurrencias de elementos

PorJosé A. Alonso 7-febrero-202223-febrero-2022

Definir la función

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

1	ocurrenciasElementos :: Ord a => [a] -> [(a,Int)]

tal que (ocurrencias xs) es el conjunto de los elementos de xs junto con sus números de ocurrencias. Por ejemplo,

   ocurrenciasElementos1 [3,2,3,1,2,3,5,3] == [(3,4),(2,2),(1,1),(5,1)]
   ocurrenciasElementos1 "tictac"          == [('t',2),('i',1),('c',2),('a',1)]

1 2	ocurrenciasElementos1 [3,2,3,1,2,3,5,3] == [(3,4),(2,2),(1,1),(5,1)] ocurrenciasElementos1 "tictac" == [('t',2),('i',1),('c',2),('a',1)]

Soluciones

import Data.List (group, nub, sort)
import Data.Maybe (fromJust)
import qualified Data.Map as M
import Test.QuickCheck

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

ocurrenciasElementos1 :: Ord a => [a] -> [(a,Int)]
ocurrenciasElementos1 xs =
  [(x,ocurrencias x xs) | x <- nub xs]

-- (ocurrencias x xs) es el número de ocurrencias de x en xs. Por
-- ejemplo,
--    ocurrencias 'a' "Salamanca"  ==  4
ocurrencias :: Ord a => a -> [a] -> Int
ocurrencias x xs = length (filter (==x) xs)

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

ocurrenciasElementos2 :: Ord a => [a] -> [(a,Int)]
ocurrenciasElementos2 xs = map ocurrencias (nub xs)
  where ocurrencias x = (x,fromJust (lookup x (frecuencias xs)))

-- (frecuencias xs) es la lista ordenada de los elementos de xs juntos
-- con sus números de ocurrencias. Por ejemplo,
--    frecuencias [3,2,3,1,2,3,5,3]  ==  [(1,1),(2,2),(3,4),(5,1)]
frecuencias :: Ord a => [a] -> [(a, Int)]
frecuencias xs = [(head ys, length ys) | ys <- group (sort xs)]

-- 3ª solución
-- ===========

ocurrenciasElementos3 :: Ord a => [a] -> [(a,Int)]
ocurrenciasElementos3 xs = map ocurrencias (nub xs)
  where diccionario   = dicFrecuencias xs
        ocurrencias x = (x, diccionario M.! x)

-- (dicFrecuencias xs) es el diccionario de los elementos de xs juntos
-- con sus números de ocurrencias. Por ejemplo,
--    λ> dicFrecuencias [3,2,3,1,2,3,5,3]
--    fromList [(1,1),(2,2),(3,4),(5,1)]
dicFrecuencias :: Ord a => [a] -> M.Map a Int
dicFrecuencias xs = M.fromListWith (+) (zip xs (repeat 1))

-- 4ª solución
-- ===========

ocurrenciasElementos4 :: Ord a => [a] -> [(a,Int)]
ocurrenciasElementos4 = foldl aux []
  where
    aux [] y                     = [(y,1)]
    aux ((x,k):xs) y | x == y    = (x, k + 1) : xs
                     | otherwise = (x, k) : aux xs y

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_ocurrenciasElementos :: [Integer] -> Bool
prop_ocurrenciasElementos xs =
  all (== (ocurrenciasElementos1 xs))
      [f xs | f <- [ocurrenciasElementos2,
                    ocurrenciasElementos3,
                    ocurrenciasElementos4]]

-- La comprobación es
--    λ> quickCheck prop_ocurrenciasElementos
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> last (ocurrenciasElementos1 (show (product [1..10^5])))
--    ('5',42935)
--    (7.93 secs, 11,325,169,512 bytes)
--    λ> last (ocurrenciasElementos2 (show (product [1..10^5])))
--    ('5',42935)
--    (8.46 secs, 11,750,911,592 bytes)
--    λ> last (ocurrenciasElementos3 (show (product [1..10^5])))
--    ('5',42935)
--    (8.29 secs, 11,447,015,896 bytes)
--    λ> last (ocurrenciasElementos4 (show (product [1..10^5])))
--    ('5',42935)
--    (9.97 secs, 12,129,527,912 bytes)

import Data.List (group, nub, sort)

import Data.Maybe (fromJust)

import qualified Data.Map as M

import Test.QuickCheck

-- 1ª solución

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

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

ocurrenciasElementos1 xs =

[(x,ocurrencias x xs) | x <- nub xs]

-- (ocurrencias x xs) es el número de ocurrencias de x en xs. Por

-- ejemplo,

-- ocurrencias 'a' "Salamanca" == 4

ocurrencias :: Ord a => a -> [a] -> Int

ocurrencias x xs = length (filter (==x) xs)

-- 2ª solución

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

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

ocurrenciasElementos2 xs = map ocurrencias (nub xs)

where ocurrencias x = (x,fromJust (lookup x (frecuencias xs)))

-- (frecuencias xs) es la lista ordenada de los elementos de xs juntos

-- con sus números de ocurrencias. Por ejemplo,

-- frecuencias [3,2,3,1,2,3,5,3] == [(1,1),(2,2),(3,4),(5,1)]

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

frecuencias xs = [(head ys, length ys) | ys <- group (sort xs)]

-- 3ª solución

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

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

ocurrenciasElementos3 xs = map ocurrencias (nub xs)

where diccionario = dicFrecuencias xs

ocurrencias x = (x, diccionario M.! x)

-- (dicFrecuencias xs) es el diccionario de los elementos de xs juntos

-- con sus números de ocurrencias. Por ejemplo,

-- λ> dicFrecuencias [3,2,3,1,2,3,5,3]

-- fromList [(1,1),(2,2),(3,4),(5,1)]

dicFrecuencias :: Ord a => [a] -> M.Map a Int

dicFrecuencias xs = M.fromListWith (+) (zip xs (repeat 1))

-- 4ª solución

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

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

ocurrenciasElementos4 = foldl aux []

where

aux [] y = [(y,1)]

aux ((x,k):xs) y | x == y = (x, k + 1) : xs

| otherwise = (x, k) : aux xs y

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_ocurrenciasElementos :: [Integer] -> Bool

prop_ocurrenciasElementos xs =

all (== (ocurrenciasElementos1 xs))

[f xs | f <- [ocurrenciasElementos2,

ocurrenciasElementos3,

ocurrenciasElementos4]]

-- La comprobación es

-- λ> quickCheck prop_ocurrenciasElementos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> last (ocurrenciasElementos1 (show (product [1..10^5])))

-- ('5',42935)

-- (7.93 secs, 11,325,169,512 bytes)

-- λ> last (ocurrenciasElementos2 (show (product [1..10^5])))

-- ('5',42935)

-- (8.46 secs, 11,750,911,592 bytes)

-- λ> last (ocurrenciasElementos3 (show (product [1..10^5])))

-- ('5',42935)

-- (8.29 secs, 11,447,015,896 bytes)

-- λ> last (ocurrenciasElementos4 (show (product [1..10^5])))

-- ('5',42935)

-- (9.97 secs, 12,129,527,912 bytes)

El código se encuentra en GitHub.

Cambio con el menor número de monedas

PorJosé A. Alonso 2-junio-202026-marzo-2022

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

   1, 1, 1, 1, 1, 1
   1, 1, 1, 3
   1, 1, 4
   3, 3

1, 1, 1, 1, 1, 1

1, 1, 1, 3

1, 1, 4

3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

   monedas :: [Int] -> Int -> Maybe Int

1	monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

   monedas [1,3,4]  6                    ==  Just 2
   monedas [2,5,10] 3                    ==  Nothing
   monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

monedas [1,3,4] 6 == Just 2

monedas [2,5,10] 3 == Nothing

monedas [1,2,5,10,20,50,100,200] 520 == Just 4

Soluciones

import Data.Array ((!), array)

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

monedas :: [Int] -> Int -> Maybe Int
monedas ms x
  | null cs   = Nothing
  | otherwise = Just (minimum (map length cs))
  where cs = cambios ms x

-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas
-- de ms. Por ejemplo,
--   λ> cambios [1,5,10] 12
--   [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]
--   λ> cambios [2,5,10] 3
--   []
--   λ> cambios [1,3,4] 6
--   [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]
cambios :: [Int] -> Int -> [[Int]]
cambios _      0 = [[]]
cambios []     _ = []
cambios (k:ks) m
  | m < k     = []
  | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++
                cambios ks m

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

monedas2 :: [Int] -> Int -> Maybe Int
monedas2 ms n
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = aux n
    aux 0 = 0
    aux k = siguiente (minimo [aux (k - x) | x <- ms,  k >= x])

infinito :: Int
infinito = 10^30

minimo :: [Int] -> Int
minimo [] = infinito
minimo xs = minimum xs

siguiente :: Int -> Int
siguiente x | x == infinito = infinito
            | otherwise     = 1 + x

-- 3ª solución
-- ===========

monedas3 :: [Int] -> Int -> Maybe Int
monedas3 ms n  
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = v ! n
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])

-- Comparación de eficiencia
-- =========================

--    λ> monedas [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.02 secs, 871,144 bytes)
--    λ> monedas2 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (15.44 secs, 1,866,519,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.01 secs, 157,232 bytes)
--    
--    λ> monedas [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (14.20 secs, 1,845,293,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (0.01 secs, 623,376 bytes)

import Data.Array ((!), array)

-- 1ª solución

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

monedas :: [Int] -> Int -> Maybe Int

monedas ms x

| null cs = Nothing

| otherwise = Just (minimum (map length cs))

where cs = cambios ms x

-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas

-- de ms. Por ejemplo,

-- λ> cambios [1,5,10] 12

-- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]

-- λ> cambios [2,5,10] 3

-- []

-- λ> cambios [1,3,4] 6

-- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]

cambios :: [Int] -> Int -> [[Int]]

cambios _ 0 = [[]]

cambios [] _ = []

cambios (k:ks) m

| m < k = []

| otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++

cambios ks m

-- 2ª solución

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

monedas2 :: [Int] -> Int -> Maybe Int

monedas2 ms n

| sol == infinito = Nothing

| otherwise = Just sol

where

sol = aux n

aux 0 = 0

aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x])

infinito :: Int

infinito = 10^30

minimo :: [Int] -> Int

minimo [] = infinito

minimo xs = minimum xs

siguiente :: Int -> Int

siguiente x | x == infinito = infinito

| otherwise = 1 + x

-- 3ª solución

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

monedas3 :: [Int] -> Int -> Maybe Int

monedas3 ms n

| sol == infinito = Nothing

| otherwise = Just sol

where

sol = v ! n

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 0

f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])

-- Comparación de eficiencia

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

-- λ> monedas [1,2,5,10,20,50,100,200] 27

-- Just 3

-- (0.02 secs, 871,144 bytes)

-- λ> monedas2 [1,2,5,10,20,50,100,200] 27

-- Just 3

-- (15.44 secs, 1,866,519,080 bytes)

-- λ> monedas3 [1,2,5,10,20,50,100,200] 27

-- Just 3

-- (0.01 secs, 157,232 bytes)

-- λ> monedas [1,2,5,10,20,50,100,200] 188

-- Just 7

-- (14.20 secs, 1,845,293,080 bytes)

-- λ> monedas3 [1,2,5,10,20,50,100,200] 188

-- Just 7

-- (0.01 secs, 623,376 bytes)

Primero no consecutivo

PorJosé A. Alonso 9-marzo-202026-marzo-2022

Definir la función

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

1	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

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

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

PorJosé A. Alonso 30-enero-202026-marzo-2022

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)

1	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])

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])

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

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

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

1 2	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])

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

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.

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

PorJosé A. Alonso 28-enero-202026-marzo-2022

Definir la función

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

1	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

1 2	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)

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.

El problema del número perdido

PorJosé A. Alonso 25-marzo-201926-marzo-2022

Sea xs una lista de números consecutivos (creciente o decreciente), en la que puede faltar algún número. El problema del número perdido en xs consiste en lo siguiente:

si falta un único número z, devolver Just z
si no falta ninguno, devolver Nothing

Definir la función

   numeroPerdido :: [Int] -> Maybe Int

1	numeroPerdido :: [Int] -> Maybe Int

tal que (numeroPerdido xs) es el resultado del problema del número perdidio en xs. Por ejemplo,

   numeroPerdido [7,6,4,3]                     == Just 5
   numeroPerdido [1,2,4,5,6]                   == Just 3
   numeroPerdido [6,5..3]                      == Nothing
   numeroPerdido [1..6]                        == Nothing
   numeroPerdido ([5..10^6] ++ [10^6+2..10^7]) == Just 1000001

numeroPerdido [7,6,4,3] == Just 5

numeroPerdido [1,2,4,5,6] == Just 3

numeroPerdido [6,5..3] == Nothing

numeroPerdido [1..6] == Nothing

numeroPerdido ([5..10^6] ++ [10^6+2..10^7]) == Just 1000001

Soluciones

import Data.List (tails, sort)
import Data.Maybe (listToMaybe)

-- 1ª solución
numeroPerdido :: [Int] -> Maybe Int
numeroPerdido (x:y:xs)
  | abs (y - x) == 1 = numeroPerdido (y:xs)
  | otherwise        = Just (div (x+y) 2)
numeroPerdido _      = Nothing

-- 2ª solución
numeroPerdido2 :: [Int] -> Maybe Int
numeroPerdido2 xs = aux z (z:zs) 
  where (z:zs) = sort xs
        aux _ [] = Nothing
        aux y (x:xs) | y == x    = aux (y+1) xs
                     | otherwise = Just y

-- 3ª solución
-- ===========

numeroPerdido3 :: [Int] -> Maybe Int
numeroPerdido3 xs =
  listToMaybe [(a+b) `div` 2 | (a:b:_) <- tails xs, abs(a-b) /= 1]

import Data.List (tails, sort)

import Data.Maybe (listToMaybe)

-- 1ª solución

numeroPerdido :: [Int] -> Maybe Int

numeroPerdido (x:y:xs)

| abs (y - x) == 1 = numeroPerdido (y:xs)

| otherwise = Just (div (x+y) 2)

numeroPerdido _ = Nothing

-- 2ª solución

numeroPerdido2 :: [Int] -> Maybe Int

numeroPerdido2 xs = aux z (z:zs)

where (z:zs) = sort xs

aux _ [] = Nothing

aux y (x:xs) | y == x = aux (y+1) xs

| otherwise = Just y

-- 3ª solución

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

numeroPerdido3 :: [Int] -> Maybe Int

numeroPerdido3 xs =

listToMaybe [(a+b) `div` 2 | (a:b:_) <- tails xs, abs(a-b) /= 1]

Pensamiento

¡Reventó de risa!
¡Un hombre tan serio!
… Nadie lo diría.

Antonio Machado

Siguiente mayor

PorJosé A. Alonso 20-marzo-201926-marzo-2022

Definir la función

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

1	siguienteMayor :: Ord a => [a] -> [Maybe a]

tal que (siguienteMayos xs) es la lista obtenida sustiyendo cada elemento de xs por el primer elemento de xs a la derechha de x que sea mayor que x, si existe y Nothing en caso contrario. Por ejemplo,

   λ> siguienteMayor [4,5,2,3,9]
   [Just 5,Just 9,Just 3,Just 9,Nothing]
   λ> siguienteMayor [9,5,2,3,4]
   [Nothing,Nothing,Just 3,Just 4,Nothing]
   λ> siguienteMayor [9,5,2,2,4]
   [Nothing,Nothing,Just 4,Just 4,Nothing]
   λ> siguienteMayor "betis"
   [Just 'e',Just 't',Nothing,Just 's',Nothing]
   λ> siguienteMayor "sevilla"
   [Just 'v',Just 'v',Nothing,Just 'l',Nothing,Nothing,Nothing]

λ> siguienteMayor [4,5,2,3,9]

[Just 5,Just 9,Just 3,Just 9,Nothing]

λ> siguienteMayor [9,5,2,3,4]

[Nothing,Nothing,Just 3,Just 4,Nothing]

λ> siguienteMayor [9,5,2,2,4]

[Nothing,Nothing,Just 4,Just 4,Nothing]

λ> siguienteMayor "betis"

[Just 'e',Just 't',Nothing,Just 's',Nothing]

λ> siguienteMayor "sevilla"

[Just 'v',Just 'v',Nothing,Just 'l',Nothing,Nothing,Nothing]

Soluciones

import Data.Maybe (listToMaybe)

-- 1ª solución
siguienteMayor :: Ord a => [a] -> [Maybe a]
siguienteMayor [] = []
siguienteMayor (x:xs)
  | null ys   = Nothing : siguienteMayor xs
  | otherwise = Just (head ys) : siguienteMayor xs
  where ys = [y | y <- xs, y > x]

-- 2ª solución
siguienteMayor2 :: Ord a => [a] -> [Maybe a]
siguienteMayor2 []     = []
siguienteMayor2 (x:xs) = listToMaybe [y | y <- xs, y > x] : siguienteMayor2 xs

-- 3ª solución
siguienteMayor3 :: Ord a => [a] -> [Maybe a]
siguienteMayor3 []     = []
siguienteMayor3 (x:xs) = listToMaybe (dropWhile (<=x) xs) : siguienteMayor3 xs

import Data.Maybe (listToMaybe)

-- 1ª solución

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

siguienteMayor [] = []

siguienteMayor (x:xs)

| null ys = Nothing : siguienteMayor xs

| otherwise = Just (head ys) : siguienteMayor xs

where ys = [y | y <- xs, y > x]

-- 2ª solución

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

siguienteMayor2 [] = []

siguienteMayor2 (x:xs) = listToMaybe [y | y <- xs, y > x] : siguienteMayor2 xs

-- 3ª solución

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

siguienteMayor3 [] = []

siguienteMayor3 (x:xs) = listToMaybe (dropWhile (<=x) xs) : siguienteMayor3 xs

Pensamiento

Si vivir es bueno
es mejor soñar,
y mejor que todo,
madre, despertar.

Antonio Machado

Cambio con el menor número de monedas

PorJosé A. Alonso 15-marzo-201926-marzo-2022

   1, 1, 1, 1, 1, 1
   1, 1, 1, 3
   1, 1, 4
   3, 3

1, 1, 1, 1, 1, 1

1, 1, 1, 3

1, 1, 4

3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

   monedas :: [Int] -> Int -> Maybe Int

1	monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

   monedas [1,3,4]  6                    ==  Just 2
   monedas [2,5,10] 3                    ==  Nothing
   monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

monedas [1,3,4] 6 == Just 2

monedas [2,5,10] 3 == Nothing

monedas [1,2,5,10,20,50,100,200] 520 == Just 4

Soluciones

import Data.Array ((!), array)

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

monedas :: [Int] -> Int -> Maybe Int
monedas ms x
  | null cs   = Nothing
  | otherwise = Just (minimum (map length cs))
  where cs = cambios ms x

-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas
-- de ms. Por ejemplo,
--   λ> cambios [1,5,10] 12
--   [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]
--   λ> cambios [2,5,10] 3
--   []
--   λ> cambios [1,3,4] 6
--   [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]
cambios :: [Int] -> Int -> [[Int]]
cambios _      0 = [[]]
cambios []     _ = []
cambios (k:ks) m
  | m < k     = []
  | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++
                cambios ks m

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

monedas2 :: [Int] -> Int -> Maybe Int
monedas2 ms n
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = aux n
    aux 0 = 0
    aux k = siguiente (minimo [aux (k - x) | x <- ms,  k >= x])

infinito :: Int
infinito = 10^30

minimo :: [Int] -> Int
minimo [] = infinito
minimo xs = minimum xs

siguiente :: Int -> Int
siguiente x | x == infinito = infinito
            | otherwise     = 1 + x

-- 3ª solución
-- ===========

monedas3 :: [Int] -> Int -> Maybe Int
monedas3 ms n  
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = v ! n
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])

-- Comparación de eficiencia
-- =========================

--    λ> monedas [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.02 secs, 871,144 bytes)
--    λ> monedas2 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (15.44 secs, 1,866,519,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.01 secs, 157,232 bytes)
--    
--    λ> monedas [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (14.20 secs, 1,845,293,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (0.01 secs, 623,376 bytes)

import Data.Array ((!), array)

-- 1ª solución

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

monedas :: [Int] -> Int -> Maybe Int

monedas ms x

| null cs = Nothing

| otherwise = Just (minimum (map length cs))

where cs = cambios ms x

-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas

-- de ms. Por ejemplo,

-- λ> cambios [1,5,10] 12

-- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]

-- λ> cambios [2,5,10] 3

-- []

-- λ> cambios [1,3,4] 6

-- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]

cambios :: [Int] -> Int -> [[Int]]

cambios _ 0 = [[]]

cambios [] _ = []

cambios (k:ks) m

| m < k = []

| otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++

cambios ks m

-- 2ª solución

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

monedas2 :: [Int] -> Int -> Maybe Int

monedas2 ms n

| sol == infinito = Nothing

| otherwise = Just sol

where

sol = aux n

aux 0 = 0

aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x])

infinito :: Int

infinito = 10^30

minimo :: [Int] -> Int

minimo [] = infinito

minimo xs = minimum xs

siguiente :: Int -> Int

siguiente x | x == infinito = infinito

| otherwise = 1 + x

-- 3ª solución

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

monedas3 :: [Int] -> Int -> Maybe Int

monedas3 ms n

| sol == infinito = Nothing

| otherwise = Just sol

where

sol = v ! n

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 0

f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])

-- Comparación de eficiencia

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

-- λ> monedas [1,2,5,10,20,50,100,200] 27

-- Just 3

-- (0.02 secs, 871,144 bytes)

-- λ> monedas2 [1,2,5,10,20,50,100,200] 27

-- Just 3

-- (15.44 secs, 1,866,519,080 bytes)

-- λ> monedas3 [1,2,5,10,20,50,100,200] 27

-- Just 3

-- (0.01 secs, 157,232 bytes)

-- λ> monedas [1,2,5,10,20,50,100,200] 188

-- Just 7

-- (14.20 secs, 1,845,293,080 bytes)

-- λ> monedas3 [1,2,5,10,20,50,100,200] 188

-- Just 7

-- (0.01 secs, 623,376 bytes)

Pensamiento

Demos tiempo al tiempo:
para que el vaso rebose
hay que llenarlo primero.

Antonio Machado

Raíz cúbica entera

PorJosé A. Alonso 30-noviembre-201826-marzo-2022

Un número x es un cubo si existe un y tal que x = y^3. Por ejemplo, 8 es un cubo porque 8 = 2^3.

Definir la función

   raizCubicaEntera :: Integer -> Maybe Integer.

1	raizCubicaEntera :: Integer -> Maybe Integer.

tal que (raizCubicaEntera x n) es justo la raíz cúbica del número natural x, si x es un cubo y Nothing en caso contrario. Por ejemplo,

   raizCubicaEntera 8             ==  Just 2
   raizCubicaEntera 9             ==  Nothing
   raizCubicaEntera 27            ==  Just 3
   raizCubicaEntera 64            ==  Just 4
   raizCubicaEntera (2^30)        ==  Just 1024
   raizCubicaEntera (10^9000)     ==  Just (10^3000)
   raizCubicaEntera (5 + 10^9000) ==  Nothing

raizCubicaEntera 8 == Just 2

raizCubicaEntera 9 == Nothing

raizCubicaEntera 27 == Just 3

raizCubicaEntera 64 == Just 4

raizCubicaEntera (2^30) == Just 1024

raizCubicaEntera (10^9000) == Just (10^3000)

raizCubicaEntera (5 + 10^9000) == Nothing

Soluciones

import Test.QuickCheck

-- 1ª definición
-- =============

raizCubicaEntera :: Integer -> Maybe Integer
raizCubicaEntera x = aux 0
  where aux y | y^3 > x   = Nothing
              | y^3 == x  = Just y
              | otherwise = aux (y+1)

-- 2ª definición
-- =============

raizCubicaEntera2 :: Integer -> Maybe Integer
raizCubicaEntera2 x 
  | y^3 == x  = Just y
  | otherwise = Nothing
  where (y:_) = dropWhile (\y -> y^3 < x) [0..]

-- 3ª definición
-- =============

raizCubicaEntera3 :: Integer -> Maybe Integer 
raizCubicaEntera3 1 = Just 1
raizCubicaEntera3 x = aux (0,x)
    where aux (a,b) | d == x    = Just c
                    | c == a    = Nothing
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^3

-- 4ª definición
-- =============

raizCubicaEntera4 :: Integer -> Maybe Integer
raizCubicaEntera4 x 
  | y^3 == x  = Just y
  | otherwise = Nothing
  where y = floor ((fromIntegral x)**(1 / 3))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,
--    λ> raizCubicaEntera4 (2^30)
--    Nothing
--    λ> raizCubicaEntera (2^30)
--    Just 1024

-- Equivalencia
-- ============

-- La propiedad es                        
prop_raizCubicaEntera :: Integer -> Property
prop_raizCubicaEntera x =
  x >= 0 ==>
  and [raizCubicaEntera x == f x | f <- [ raizCubicaEntera2
                                        , raizCubicaEntera3]]

-- La comprobación es              
--    λ> quickCheck prop_raizCubicaEntera
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================
  
--    λ> raizCubicaEntera (10^18)
--    Just 1000000
--    (1.80 secs, 1,496,137,192 bytes)
--    λ> raizCubicaEntera2 (10^18)
--    Just 1000000
--    (0.71 secs, 712,134,128 bytes)
--    λ> raizCubicaEntera3 (10^18)
--    Just 1000000
--    (0.01 secs, 196,424 bytes)
--
--    λ> raizCubicaEntera2 (5^27)
--    Just 1953125
--    (1.42 secs, 1,390,760,920 bytes)
--    λ> raizCubicaEntera3 (5^27)
--    Just 1953125
--    (0.00 secs, 195,888 bytes)
--
--    λ> raizCubicaEntera3 (10^9000) == Just (10^3000)
--    True
--    (2.05 secs, 420,941,368 bytes)
--    λ> raizCubicaEntera3 (5 + 10^9000) == Nothing
--    True
--    (2.08 secs, 420,957,576 bytes)

import Test.QuickCheck

-- 1ª definición

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

raizCubicaEntera :: Integer -> Maybe Integer

raizCubicaEntera x = aux 0

where aux y | y^3 > x = Nothing

| y^3 == x = Just y

| otherwise = aux (y+1)

-- 2ª definición

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

raizCubicaEntera2 :: Integer -> Maybe Integer

raizCubicaEntera2 x

| y^3 == x = Just y

| otherwise = Nothing

where (y:_) = dropWhile (\y -> y^3 < x) [0..]

-- 3ª definición

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

raizCubicaEntera3 :: Integer -> Maybe Integer

raizCubicaEntera3 1 = Just 1

raizCubicaEntera3 x = aux (0,x)

where aux (a,b) | d == x = Just c

| c == a = Nothing

| d < x = aux (c,b)

| otherwise = aux (a,c)

where c = (a+b) `div` 2

d = c^3

-- 4ª definición

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

raizCubicaEntera4 :: Integer -> Maybe Integer

raizCubicaEntera4 x

| y^3 == x = Just y

| otherwise = Nothing

where y = floor ((fromIntegral x)**(1 / 3))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,

-- λ> raizCubicaEntera4 (2^30)

-- Nothing

-- λ> raizCubicaEntera (2^30)

-- Just 1024

-- Equivalencia

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

-- La propiedad es

prop_raizCubicaEntera :: Integer -> Property

prop_raizCubicaEntera x =

x >= 0 ==>

and [raizCubicaEntera x == f x | f <- [ raizCubicaEntera2

, raizCubicaEntera3]]

-- La comprobación es

-- λ> quickCheck prop_raizCubicaEntera

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> raizCubicaEntera (10^18)

-- Just 1000000

-- (1.80 secs, 1,496,137,192 bytes)

-- λ> raizCubicaEntera2 (10^18)

-- Just 1000000

-- (0.71 secs, 712,134,128 bytes)

-- λ> raizCubicaEntera3 (10^18)

-- Just 1000000

-- (0.01 secs, 196,424 bytes)

-- λ> raizCubicaEntera2 (5^27)

-- Just 1953125

-- (1.42 secs, 1,390,760,920 bytes)

-- λ> raizCubicaEntera3 (5^27)

-- Just 1953125

-- (0.00 secs, 195,888 bytes)

-- λ> raizCubicaEntera3 (10^9000) == Just (10^3000)

-- True

-- (2.05 secs, 420,941,368 bytes)

-- λ> raizCubicaEntera3 (5 + 10^9000) == Nothing

-- True

-- (2.08 secs, 420,957,576 bytes)

Pensamiento

Tras el vivir y el soñar,
está lo que más importa:
despertar.

Antonio Machado

Búsqueda en los dígitos de pi

PorJosé A. Alonso 13-abril-201826-marzo-2022

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

   posicion :: String -> IO (Maybe Int)

1	posicion :: String -> IO (Maybe Int)

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

   λ> posicion "15"
   Just 3
   λ> posicion "2017"
   Just 8897
   λ> posicion "022017"
   Just 382052
   λ> posicion "14022017"
   Nothing
   λ> posicion "999999"
   Just 762
   λ> posicion "458151"
   Just 999995

λ> posicion "15"

Just 3

λ> posicion "2017"

Just 8897

λ> posicion "022017"

Just 382052

λ> posicion "14022017"

Nothing

λ> posicion "999999"

Just 762

λ> posicion "458151"

Just 999995

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)
posicion ns = do
  ds <- readFile "Digitos_de_pi.txt"
  return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int
posicionEnLista xs ys = aux xs 1
  where aux [] _ = Nothing
        aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n
                     | otherwise              = aux xs (n+1)

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)

posicion ns = do

ds <- readFile "Digitos_de_pi.txt"

return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int

posicionEnLista xs ys = aux xs 1

where aux [] _ = Nothing

aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n

| otherwise = aux xs (n+1)

División equitativa

PorJosé A. Alonso 6-febrero-201826-marzo-2022

Definir la función

   divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

1	divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

   divisionEquitativa [1,2,3,4,5,15]  ==  Just ([1,2,3,4,5],[15])
   divisionEquitativa [15,1,2,3,4,5]  ==  Just ([15],[1,2,3,4,5])
   divisionEquitativa [1,2,3,4,7,15]  ==  Nothing
   divisionEquitativa [1,2,3,4,15,5]  ==  Nothing

divisionEquitativa [1,2,3,4,5,15] == Just ([1,2,3,4,5],[15])

divisionEquitativa [15,1,2,3,4,5] == Just ([15],[1,2,3,4,5])

divisionEquitativa [1,2,3,4,7,15] == Nothing

divisionEquitativa [1,2,3,4,15,5] == Nothing

Soluciones

import Data.Maybe (isNothing, fromJust, listToMaybe)
import Data.List  (elemIndex, inits, tails)

-- 1ª solución
divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa1 xs = aux (particiones xs)
 where aux []                              = Nothing
       aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)
                        | otherwise        = aux ys                   
       particiones xs = [splitAt i xs | i <- [1..length xs-1]]

-- 2ª solución
divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa2 xs
  | 2 * b == suma = Just $ splitAt (length as + 1) xs
  | otherwise     = Nothing
  where suma        = sum xs
        (as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs

-- 3ª solución
divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa3 xs
  | odd n       = Nothing
  | isNothing p = Nothing
  | otherwise   = Just (splitAt (1 + fromJust p) xs)
  where n  = sum xs
        ys = scanl1 (+) xs
        p  = elemIndex (n `div` 2) ys

-- 4ª solución
divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa4 xs
  | odd (sum xs) = Nothing
  | otherwise    = aux [] xs
  where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs)
                          | sum as > sum bs  = Nothing
                          | otherwise        = aux (b:as) (bs')

-- 5ª solución
divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int])
divisionEquitativa5 xs =
  listToMaybe
    [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)
              , sum ys == sum zs ]

import Data.Maybe (isNothing, fromJust, listToMaybe)

import Data.List (elemIndex, inits, tails)

-- 1ª solución

divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa1 xs = aux (particiones xs)

where aux [] = Nothing

aux ((as,bs):ys) | sum as == sum bs = Just (as,bs)

| otherwise = aux ys

particiones xs = [splitAt i xs | i <- [1..length xs-1]]

-- 2ª solución

divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa2 xs

| 2 * b == suma = Just $ splitAt (length as + 1) xs

| otherwise = Nothing

where suma = sum xs

(as,(b:bs)) = span (<suma `div` 2) $ scanl1 (+) xs

-- 3ª solución

divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa3 xs

| odd n = Nothing

| isNothing p = Nothing

| otherwise = Just (splitAt (1 + fromJust p) xs)

where n = sum xs

ys = scanl1 (+) xs

p = elemIndex (n `div` 2) ys

-- 4ª solución

divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa4 xs

| odd (sum xs) = Nothing

| otherwise = aux [] xs

where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs)

| sum as > sum bs = Nothing

| otherwise = aux (b:as) (bs')

-- 5ª solución

divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int])

divisionEquitativa5 xs =

listToMaybe

[(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs)

, sum ys == sum zs ]

Ordenación según una cadena

PorJosé A. Alonso 29-diciembre-201726-marzo-2022

Dada una lista xs y una cadena cs de la misma longitud, la ordenación de xs según cs consiste en emparejar los elementos de cs con los de xs (de forma que al menor elemento de cs le corresponde el menor de xs, al segundo de cs el segundo de xs, etc.) y ordenar los elementos de xs en el mismo orden que sus correspondientes elementos de cs. Por ejemplo, si xs es [6,4,2] y cs es «CAB» entonces a ‘A’ le corresponde el 2, a ‘B’ el 4 y a ‘C’ el 6; luego la ordenación es [6,2,4].

Definir la función

   ordenacion :: Ord a => [a] -> String -> [a]

1	ordenacion :: Ord a => [a] -> String -> [a]

tal que (ordenacion xs ys) es la ordenación de la lista xs según la cadena cs. Por ejemplo,

   ordenacion [6,4,2] "CAB"     ==  [6,2,4]
   ordenacion [1,5,3] "ABC"     ==  [1,3,5]
   ordenacion [1,5,3,7] "ABEC"  ==  [1,3,7,5]

ordenacion [6,4,2] "CAB" == [6,2,4]

ordenacion [1,5,3] "ABC" == [1,3,5]

ordenacion [1,5,3,7] "ABEC" == [1,3,7,5]

Soluciones

import Data.List (sort)
import Data.Maybe (fromJust)

ordenacion :: Ord a => [a] -> String -> [a]
ordenacion xs cs =
  [fromJust (lookup y diccionario) | y <- cs]
  where diccionario = zip (sort cs) (sort xs)

import Data.List (sort)

import Data.Maybe (fromJust)

ordenacion :: Ord a => [a] -> String -> [a]

ordenacion xs cs =

[fromJust (lookup y diccionario) | y <- cs]

where diccionario = zip (sort cs) (sort xs)

Vecino en lista circular

PorJosé A. Alonso 19-diciembre-201726-marzo-2022

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

1	data Direccion = I \| D deriving Eq

Definir la función

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

1	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

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)))

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

PorJosé A. Alonso 22-noviembre-201726-marzo-2022

Definir las siguientes funciones

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

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

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]

λ> 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

λ> 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)

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

PorJosé A. Alonso 21-noviembre-201726-marzo-2022

Definir la función

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

1	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

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

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)

Búsqueda en los dígitos de pi

PorJosé A. Alonso 15-febrero-201726-marzo-2022

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

   posicion :: String -> IO (Maybe Int)

1	posicion :: String -> IO (Maybe Int)

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

   λ> posicion "15"
   Just 3
   λ> posicion "2017"
   Just 8897
   λ> posicion "022017"
   Just 382052
   λ> posicion "14022017"
   Nothing
   λ> posicion "999999"
   Just 762
   λ> posicion "458151"
   Just 999995

λ> posicion "15"

Just 3

λ> posicion "2017"

Just 8897

λ> posicion "022017"

Just 382052

λ> posicion "14022017"

Nothing

λ> posicion "999999"

Just 762

λ> posicion "458151"

Just 999995

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)
posicion ns = do
  ds <- readFile "Digitos_de_pi.txt"
  return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int
posicionEnLista xs ys = aux xs 1
  where aux [] _ = Nothing
        aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n
                     | otherwise              = aux xs (n+1)

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)

posicion ns = do

ds <- readFile "Digitos_de_pi.txt"

return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int

posicionEnLista xs ys = aux xs 1

where aux [] _ = Nothing

aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n

| otherwise = aux xs (n+1)

Máximo producto de pares en la lista

PorJosé A. Alonso 30-enero-201726-marzo-2022

Definir la función

  maximoProducto :: [Int] -> Maybe Int

1	maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir
como producto de dos elementos distintos de xs o Nothing, en el caso de que
ningún elemento de xs se pueda escribir como producto de dos elementos
distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

   maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
   maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
   maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
   maximoProducto [2,4]                    ==  Nothing
   maximoProducto [2, 5, 7, 8]             ==  Nothing
   maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
   maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

maximoProducto [10, 3, 5, 30, 35] == Just 30

maximoProducto [10, 2, 2, 4, 30, 35] == Just 4

maximoProducto [17, 2, 1, 35, 30] == Just 35

maximoProducto [2,4] == Nothing

maximoProducto [2, 5, 7, 8] == Nothing

maximoProducto [10, 2, 4, 30, 35] == Nothing

maximoProducto [1+2^n | n <- [1..10^6]] == Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Soluciones

import Data.List (delete, nub, sort)

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

maximoProducto1 :: [Int] -> Maybe Int
maximoProducto1 xs
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where
    ys = reverse (sort xs)
    zs = [y | y <- ys, y `elem` productos xs]

-- (productos xs) es la lista de los números que son productos de dos
-- elementos de xs. Por ejemplo, 
--   productos [4,3,5,2]  ==  [12,20,8,15,6,10]
productos :: [Int] -> [Int]
productos xs =
  nub [y * z | y <- xs, z <- delete y xs]

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

maximoProducto2 :: [Int] -> Maybe Int
maximoProducto2 xs = aux (reverse (sort xs))
  where aux []     = Nothing
        aux (y:ys) | esProducto y xs = Just y
                   | otherwise       = aux ys

esProducto :: Int -> [Int] -> Bool
esProducto y []     = False
esProducto y (x:xs) = 
  (m == 0 && d `elem` xs) || esProducto y xs
  where (d,m) = divMod y x  

-- Comparación de eficiencia
-- =========================

--    λ> maximoProducto1 [1..10^4]
--    Just 10000
--    (2.60 secs, 0 bytes)
--    λ> maximoProducto2 [1..10^4]
--    Just 10000
--    (0.01 secs, 0 bytes)

import Data.List (delete, nub, sort)

-- 1ª solución

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

maximoProducto1 :: [Int] -> Maybe Int

maximoProducto1 xs

| null zs = Nothing

| otherwise = Just (head zs)

where

ys = reverse (sort xs)

zs = [y | y <- ys, y `elem` productos xs]

-- (productos xs) es la lista de los números que son productos de dos

-- elementos de xs. Por ejemplo,

-- productos [4,3,5,2] == [12,20,8,15,6,10]

productos :: [Int] -> [Int]

productos xs =

nub [y * z | y <- xs, z <- delete y xs]

-- 2ª solución

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

maximoProducto2 :: [Int] -> Maybe Int

maximoProducto2 xs = aux (reverse (sort xs))

where aux [] = Nothing

aux (y:ys) | esProducto y xs = Just y

| otherwise = aux ys

esProducto :: Int -> [Int] -> Bool

esProducto y [] = False

esProducto y (x:xs) =

(m == 0 && d `elem` xs) || esProducto y xs

where (d,m) = divMod y x

-- Comparación de eficiencia

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

-- λ> maximoProducto1 [1..10^4]

-- Just 10000

-- (2.60 secs, 0 bytes)

-- λ> maximoProducto2 [1..10^4]

-- Just 10000

-- (0.01 secs, 0 bytes)

Inversa del factorial

PorJosé A. Alonso 16-enero-201726-marzo-2022

Definir la función

   inversaFactorial :: Integer -> Maybe Integer

1	inversaFactorial :: Integer -> Maybe Integer

tal que (inversaFactorial x) es (Just n) si el factorial de n es x y es Nothing si no existe ningún número n tal que el factorial de n es x. Por ejemplo,

   inversaFactorial 24  ==  Just 4
   inversaFactorial 25  ==  Nothing

1 2	inversaFactorial 24 == Just 4 inversaFactorial 25 == Nothing

Soluciones

-- 1ª definición
-- =============

inversaFactorial :: Integer -> Maybe Integer
inversaFactorial 1 = Just 1
inversaFactorial x = aux 2 x
  where aux n 1 = Just (n-1)
        aux n y | y `mod` n == 0 = aux (n+1) (y `div` n)
                | otherwise      = Nothing

-- 2ª definición
-- =============

inversaFactorial2 :: Integer -> Maybe Integer
inversaFactorial2 x
  | y == x   = Just n
  |otherwise = Nothing  
  where ((n,y):_) = dropWhile (\(k,z) -> z < x) factorialesAnotados

-- factorialesAnotados es la lista de los factoriales anotados con sus
-- posiciones. Por ejemplo, 
--    take 5 factorialesAnotados  ==  [(0,1),(1,1),(2,2),(3,6),(4,24)]
factorialesAnotados :: [(Integer, Integer)]
factorialesAnotados = zip [0..] factoriales
    
-- factoriales es la lista de los factoriales. Por ejemplo,
--    take 5 factoriales  ==  [1,1,2,6,24]
factoriales :: [Integer]
factoriales =
  1 : scanl1 (*) [1..]

-- Comparación de eficiencia
--    λ> inversaFactorial (product [1..4*10^4])
--    Just 40000
--    (2.76 secs, 3,105,158,528 bytes)
--    λ> inversaFactorial2 (product [1..4*10^4])
--    Just 40000
--    (2.60 secs, 3,261,722,960 bytes)
--
--    λ> inversaFactorial (1 + product [1..4*10^4])
--    Nothing
--    (1.80 secs, 1,626,433,432 bytes)
--    λ> inversaFactorial2 (1 + product [1..4*10^4])
--    Nothing
--    (2.56 secs, 3,257,388,296 bytes)

-- 1ª definición

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

inversaFactorial :: Integer -> Maybe Integer

inversaFactorial 1 = Just 1

inversaFactorial x = aux 2 x

where aux n 1 = Just (n-1)

aux n y | y `mod` n == 0 = aux (n+1) (y `div` n)

| otherwise = Nothing

-- 2ª definición

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

inversaFactorial2 :: Integer -> Maybe Integer

inversaFactorial2 x

| y == x = Just n

|otherwise = Nothing

where ((n,y):_) = dropWhile (\(k,z) -> z < x) factorialesAnotados

-- factorialesAnotados es la lista de los factoriales anotados con sus

-- posiciones. Por ejemplo,

-- take 5 factorialesAnotados == [(0,1),(1,1),(2,2),(3,6),(4,24)]

factorialesAnotados :: [(Integer, Integer)]

factorialesAnotados = zip [0..] factoriales

-- factoriales es la lista de los factoriales. Por ejemplo,

-- take 5 factoriales == [1,1,2,6,24]

factoriales :: [Integer]

factoriales =

1 : scanl1 (*) [1..]

-- Comparación de eficiencia

-- λ> inversaFactorial (product [1..4*10^4])

-- Just 40000

-- (2.76 secs, 3,105,158,528 bytes)

-- λ> inversaFactorial2 (product [1..4*10^4])

-- Just 40000

-- (2.60 secs, 3,261,722,960 bytes)

-- λ> inversaFactorial (1 + product [1..4*10^4])

-- Nothing

-- (1.80 secs, 1,626,433,432 bytes)

-- λ> inversaFactorial2 (1 + product [1..4*10^4])

-- Nothing

-- (2.56 secs, 3,257,388,296 bytes)

Centro de gravedad de una lista

PorJosé A. Alonso 25-mayo-201626-marzo-2022

Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.

Definir la función

   centro :: (Num a, Eq a) => [a] -> Maybe Int

1	centro :: (Num a, Eq a) => [a] -> Maybe Int

tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,

   centro [1,3,4,5,-2,1]           ==  Just 2
   centro [1,6,4,5,-2,1]           ==  Nothing
   centro [1,2,3,4,3,2,1]          ==  Just 3
   centro [1,100,50,-51,1,1]       ==  Just 1
   centro [1,2,3,4,5,6]            ==  Nothing
   centro [20,10,30,10,10,15,35]   ==  Just 3
   centro [20,10,-80,10,10,15,35]  ==  Just 0
   centro [10,-80,10,10,15,35,20]  ==  Just 6
   centro [0,0,0,0,0]              ==  Just 0
   centro [-1,-2,-3,-4,-3,-2,-1]   ==  Just 3

centro [1,3,4,5,-2,1] == Just 2

centro [1,6,4,5,-2,1] == Nothing

centro [1,2,3,4,3,2,1] == Just 3

centro [1,100,50,-51,1,1] == Just 1

centro [1,2,3,4,5,6] == Nothing

centro [20,10,30,10,10,15,35] == Just 3

centro [20,10,-80,10,10,15,35] == Just 0

centro [10,-80,10,10,15,35,20] == Just 6

centro [0,0,0,0,0] == Just 0

centro [-1,-2,-3,-4,-3,-2,-1] == Just 3

Soluciones

import Data.List (inits, tails)
import Data.Maybe (listToMaybe)

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

centro1 :: (Num a, Eq a) => [a] -> Maybe Int
centro1 xs 
    | null ns   = Nothing
    | otherwise = Just (head ns)
    where ns = [n | n <- [0..length xs - 1],
                    let (ys,_:zs) = splitAt n xs,
                    sum ys == sum zs]

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

centro2 :: (Num a, Eq a) => [a] -> Maybe Int
centro2 xs = aux 0 0 (sum xs) xs where
    aux _ _ _ [] = Nothing
    aux k i d (z:zs) | i == d - z = Just k
                     | otherwise  = aux (k + 1) (i + z) (d - z) zs

-- 3ª solución
-- ===========

centro3 :: (Num a, Eq a) => [a] -> Maybe Int
centro3 xs =
  listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
                  , sum ys == sum zs]

-- Comparación de eficiencia
-- =========================

--    λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))
--    Just 3000
--    (2.70 secs, 2,088,881,728 bytes)
--    λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))
--    Just 3000
--    (0.03 secs, 0 bytes)
--    λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))
--    Just 3000
--    (2.34 secs, 1,727,569,688 bytes)

import Data.List (inits, tails)

import Data.Maybe (listToMaybe)

-- 1ª solución

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

centro1 :: (Num a, Eq a) => [a] -> Maybe Int

centro1 xs

| null ns = Nothing

| otherwise = Just (head ns)

where ns = [n | n <- [0..length xs - 1],

let (ys,_:zs) = splitAt n xs,

sum ys == sum zs]

-- 2ª solución

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

centro2 :: (Num a, Eq a) => [a] -> Maybe Int

centro2 xs = aux 0 0 (sum xs) xs where

aux _ _ _ [] = Nothing

aux k i d (z:zs) | i == d - z = Just k

| otherwise = aux (k + 1) (i + z) (d - z) zs

-- 3ª solución

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

centro3 :: (Num a, Eq a) => [a] -> Maybe Int

centro3 xs =

listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)

, sum ys == sum zs]

-- Comparación de eficiencia

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

-- λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))

-- Just 3000

-- (2.70 secs, 2,088,881,728 bytes)

-- λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))

-- Just 3000

-- (0.03 secs, 0 bytes)

-- λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))

-- Just 3000

-- (2.34 secs, 1,727,569,688 bytes)

Inverso multiplicativo modular

PorJosé A. Alonso 6-abril-201626-marzo-2022

El inverso multiplicativo modular de un entero n módulo p es el número m, entre 1 y p-1, tal que

   mn = 1 (mod p)

1	mn = 1 (mod p)

Por ejemplo, el inverso multiplicativo de 2 módulo 5 es 3, ya que 1 <= 3 <= 4 y 2×3 = 1 (mod 5).

El inverso multipicativo de n módulo p existe si y sólo si n y p son coprimos; es decir, si mcd(n,p) = 1.

Definir la función

   invMod :: Integer -> Integer -> Maybe Integer

1	invMod :: Integer -> Integer -> Maybe Integer

tal que (invMod n p) es justo el inverso multiplicativo de n módulo p, si existe y Nothing en caso contrario. Por ejemplo,

   λ> invMod 2 5
   Just 3
   λ> invMod 2 6
   Nothing
   λ> [(x,invMod x 5) | x <- [0..4]]
   [(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]
   λ> [(x,invMod x 6) | x <- [0..5]]
   [(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]
   λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)
   True

λ> invMod 2 5

Just 3

λ> invMod 2 6

Nothing

λ> [(x,invMod x 5) | x <- [0..4]]

[(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]

λ> [(x,invMod x 6) | x <- [0..5]]

[(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]

λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)

True

Soluciones

-- 1ª definición
-- =============

invMod1 :: Integer -> Integer -> Maybe Integer
invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])
            | otherwise    = Nothing

-- 2ª definición
-- =============

invMod2 :: Integer -> Integer -> Maybe Integer
invMod2 n p | m /= 1    = Nothing
            | x < 0     = Just (x + p)
            | otherwise = Just x
    where (x,_,m) = mcdExt n p

-- [Algoritmo extendido de Euclides]
-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor
-- de a y b y se cumple que ax + by = g. Por ejemplo,
--    mcdExt  2  5  ==  (-2,1,1)
--    mcdExt  2  6  ==  ( 1,0,2)
--    mcdExt 12 15  ==  (-1,1,3)
mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)
mcdExt a 0 = (1, 0, a)
mcdExt a b = (t, s - q * t, g)
  where (q, r)    = a `quotRem` b
        (s, t, g) = mcdExt b r

-- 3ª definición
-- =============

invMod3 :: Integer -> Integer -> Maybe Integer
invMod3 n p | gcd n p == 1 = Just (aux n p)
            | otherwise    = Nothing
  where aux 1 p = 1
        aux n p = (x * p + 1) `div` n
          where x = n - aux (p `mod` n) n                    

-- Comparación de eficiencia
-- =========================

--    λ> invMod1 (10^7) (1+10^7)
--    Just 10000000
--    (5.05 secs, 2,872,350,896 bytes)
--    λ> invMod2 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    λ> invMod3 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    
--    λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)
--    True
--    (0.88 secs, 55,728,120 bytes)
--    λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)
--    True
--    (1.99 secs, 80,644,352 bytes)

-- 1ª definición

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

invMod1 :: Integer -> Integer -> Maybe Integer

invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])

| otherwise = Nothing

-- 2ª definición

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

invMod2 :: Integer -> Integer -> Maybe Integer

invMod2 n p | m /= 1 = Nothing

| x < 0 = Just (x + p)

| otherwise = Just x

where (x,_,m) = mcdExt n p

-- [Algoritmo extendido de Euclides]

-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor

-- de a y b y se cumple que ax + by = g. Por ejemplo,

-- mcdExt 2 5 == (-2,1,1)

-- mcdExt 2 6 == ( 1,0,2)

-- mcdExt 12 15 == (-1,1,3)

mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)

mcdExt a 0 = (1, 0, a)

mcdExt a b = (t, s - q * t, g)

where (q, r) = a `quotRem` b

(s, t, g) = mcdExt b r

-- 3ª definición

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

invMod3 :: Integer -> Integer -> Maybe Integer

invMod3 n p | gcd n p == 1 = Just (aux n p)

| otherwise = Nothing

where aux 1 p = 1

aux n p = (x * p + 1) `div` n

where x = n - aux (p `mod` n) n

-- Comparación de eficiencia

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

-- λ> invMod1 (10^7) (1+10^7)

-- Just 10000000

-- (5.05 secs, 2,872,350,896 bytes)

-- λ> invMod2 (10^7) (1+10^7)

-- Just 10000000

-- (0.00 secs, 0 bytes)

-- λ> invMod3 (10^7) (1+10^7)

-- Just 10000000

-- (0.00 secs, 0 bytes)

-- λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)

-- True

-- (0.88 secs, 55,728,120 bytes)

-- λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)

-- True

-- (1.99 secs, 80,644,352 bytes)

Solución en Maxima

invMod (n,p) := block ([r],
  r : inv_mod (n,p),
  if integerp (r)
  then Just (r)
  else Nothing)$

invMod (n,p) := block ([r],

r : inv_mod (n,p),

if integerp (r)

then Just (r)

else Nothing)$

La evaluación de los ejemplos es

(%i2) invMod (2,5);
(%o2) Just(3)
(%i3) invMod (2,6);
(%o3) Nothing
(%i4) makelist([x,invMod(x,5)],x,0,4);
(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]
(%i5) makelist([x,invMod(x,6)],x,0,5);
(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]
(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));
(%o6) true

(%i2) invMod (2,5);

(%o2) Just(3)

(%i3) invMod (2,6);

(%o3) Nothing

(%i4) makelist([x,invMod(x,5)],x,0,4);

(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]

(%i5) makelist([x,invMod(x,6)],x,0,5);

(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]

(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));

(%o6) true

Referencia

Calculating multiplicative inverses in modular arithmetic

Evaluación de expresiones aritméticas

PorJosé A. Alonso 29-marzo-201626-marzo-2022

Las expresiones aritméticas se pueden definir mediante el siguiente tipo de dato

   data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr 
                deriving Show

1 2	data Expr = N Int \| V Char \| Sum Expr Expr \| Mul Expr Expr deriving Show

Por ejemplo, (x+3)+(7*y) se representa por

   ejExpr :: Expr
   ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

1 2	ejExpr :: Expr ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

Definir la función

   valor :: Expr -> Maybe Int

1	valor :: Expr -> Maybe Int

tal que (valor e) es ‘Just v’ si la expresión e es numérica y v es su valor, o bien ‘Nothing’ si e no es numérica. Por ejemplo:

   valor (Sum (N 7) (N 9))                            == Just 16
   valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing
   valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2)))     == Just 18

valor (Sum (N 7) (N 9)) == Just 16

valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing

valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2))) == Just 18

Soluciones

data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr 
             deriving Show

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

valor1 :: Expr -> Maybe Int
valor1 e | null (aux e) = Nothing
         | otherwise    = Just (head (aux e))
    where aux (N x)       = [x]
          aux (V _)       = []
          aux (Sum e1 e2) = [x+y| x <- aux e1, y <- aux e2]
          aux (Mul e1 e2) = [x*y| x <- aux e1, y <- aux e2]

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

valor2 :: Expr -> Maybe Int
valor2 e | numerico e = Just (aux e)
         | otherwise  = Nothing
    where aux (N x)       = x
          aux (Sum e1 e2) = aux e1 + aux e2
          aux (Mul e1 e2) = aux e1 * aux e2

numerico :: Expr -> Bool
numerico (N _)       = True
numerico (V _)       = False
numerico (Sum e1 e2) = numerico e1 && numerico e2
numerico (Mul e1 e2) = numerico e1 && numerico e2

data Expr = N Int | V Char | Sum Expr Expr | Mul Expr Expr

deriving Show

-- 1ª solución

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

valor1 :: Expr -> Maybe Int

valor1 e | null (aux e) = Nothing

| otherwise = Just (head (aux e))

where aux (N x) = [x]

aux (V _) = []

aux (Sum e1 e2) = [x+y| x <- aux e1, y <- aux e2]

aux (Mul e1 e2) = [x*y| x <- aux e1, y <- aux e2]

-- 2ª solución

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

valor2 :: Expr -> Maybe Int

valor2 e | numerico e = Just (aux e)

| otherwise = Nothing

where aux (N x) = x

aux (Sum e1 e2) = aux e1 + aux e2

aux (Mul e1 e2) = aux e1 * aux e2

numerico :: Expr -> Bool

numerico (N _) = True

numerico (V _) = False

numerico (Sum e1 e2) = numerico e1 && numerico e2

numerico (Mul e1 e2) = numerico e1 && numerico e2

Índices de números de Fibonacci

PorJosé A. Alonso 2-marzo-201626-marzo-2022

Los primeros términos de la sucesión de Fibonacci son

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Se observa que el 6º término de la sucesión (comenzando a contar en 0) es el número 8.

Definir la función

   indiceFib :: Integer -> Maybe Integer

1	indiceFib :: Integer -> Maybe Integer

tal que (indiceFib x) es justo el número n si x es el n-ésimo términos de la sucesión de Fibonacci o Nothing en el caso de que x no pertenezca a la sucesión. Por ejemplo,

    indiceFib 8                                           == Just 6
    indiceFib 9                                           == Nothing
    indiceFib 21                                          == Just 8
    indiceFib 22                                          == Nothing
    indiceFib 280571172992510140037611932413038677189525  == Just 200
    indiceFib 123456789012345678901234567890123456789012  == Nothing

indiceFib 8 == Just 6

indiceFib 9 == Nothing

indiceFib 21 == Just 8

indiceFib 22 == Nothing

indiceFib 280571172992510140037611932413038677189525 == Just 200

indiceFib 123456789012345678901234567890123456789012 == Nothing

Soluciones

indiceFib :: Integer -> Maybe Integer
indiceFib x | y == x    = Just n
            | otherwise = Nothing
    where (y,n) = head (dropWhile (\(z,m) -> z < x) fibsNumerados)

-- fibs es la lista de los términos de la sucesión de Fibonacci. Por
-- ejemplo, 
--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]
fibs :: [Integer]
fibs = 0 : 1 : [x+y | (x,y) <- zip fibs (tail fibs)]

-- fibsNumerados es la lista de los términos de la sucesión de Fibonacci
-- juntos con sus posiciones. Por ejemplo,
--    ghci> take 10 fibsNumerados
--    [(0,0),(1,1),(1,2),(2,3),(3,4),(5,5),(8,6),(13,7),(21,8),(34,9)]
fibsNumerados :: [(Integer,Integer)]
fibsNumerados = zip fibs [0..]

indiceFib :: Integer -> Maybe Integer

indiceFib x | y == x = Just n

| otherwise = Nothing

where (y,n) = head (dropWhile (\(z,m) -> z < x) fibsNumerados)

-- fibs es la lista de los términos de la sucesión de Fibonacci. Por

-- ejemplo,

-- take 10 fibs == [0,1,1,2,3,5,8,13,21,34]

fibs :: [Integer]

fibs = 0 : 1 : [x+y | (x,y) <- zip fibs (tail fibs)]

-- fibsNumerados es la lista de los términos de la sucesión de Fibonacci

-- juntos con sus posiciones. Por ejemplo,

-- ghci> take 10 fibsNumerados

-- [(0,0),(1,1),(1,2),(2,3),(3,4),(5,5),(8,6),(13,7),(21,8),(34,9)]

fibsNumerados :: [(Integer,Integer)]

fibsNumerados = zip fibs [0..]

En Maxima

indiceFib (n) := block([a:0,b:1,c:1,p:0],
  unless n <= a do
   (a : b,
    b : c,
    c : a + b,
    p : p + 1),
  if n = a
  then Just (p)
  else Nothing)$

indiceFib (n) := block([a:0,b:1,c:1,p:0],

unless n <= a do

(a : b,

b : c,

c : a + b,

p : p + 1),

if n = a

then Just (p)

else Nothing)$

Compactación de listas

PorJosé A. Alonso 11-febrero-201626-marzo-2022

Definir la función

   compactada :: [Maybe Int] -> [Int]

1	compactada :: [Maybe Int] -> [Int]

tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:

se eliminan los elementos Nothing;
si dos elementos consecutivos tienen el mismo valor, se sustituyen por el sucesor de su valor y
los restantes elementos no se cambian.

Por ejemplo,

    λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]
    [2,5,3,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]
    [2,1,4,3,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]
    [2,1,5,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]
    [2,1,4,3,4]
    λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]
    [2,2,4,3,4]

λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]

[2,5,3,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]

[2,1,4,3,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]

[2,1,5,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]

[2,1,4,3,4]

λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]

[2,2,4,3,4]

Soluciones

-- 1ª definición
compactada1 :: [Maybe Int] -> [Int]
compactada1 xs = aux (valores xs)
    where aux (x:y:xs) | x == y    = x+1 : aux xs
                       | otherwise = x : aux (y:xs)
          aux xs                   = xs

-- (valores vs) es la lista de los valores de vs. Por ejemplo,
--    ghci> valores [Just 1,Nothing,Just 1,Nothing,Just 3,Just 6]
--    [1,1,3,6]
valores :: [Maybe Int] -> [Int]
valores xs = [x | Just x <- xs]

-- 2ª definición de valores (por recursión):
valores2 :: [Maybe Int] -> [Int]
valores2 []            = []
valores2 ((Just v):vs) = v: valores2 vs
valores2 (Nothing:vs)  = valores2 vs

-- 1ª definición

compactada1 :: [Maybe Int] -> [Int]

compactada1 xs = aux (valores xs)

where aux (x:y:xs) | x == y = x+1 : aux xs

| otherwise = x : aux (y:xs)

aux xs = xs

-- (valores vs) es la lista de los valores de vs. Por ejemplo,

-- ghci> valores [Just 1,Nothing,Just 1,Nothing,Just 3,Just 6]

-- [1,1,3,6]

valores :: [Maybe Int] -> [Int]

valores xs = [x | Just x <- xs]

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

valores2 :: [Maybe Int] -> [Int]

valores2 [] = []

valores2 ((Just v):vs) = v: valores2 vs

valores2 (Nothing:vs) = valores2 vs

Antiimágenes en una función creciente

PorJosé A. Alonso 20-enero-201626-marzo-2022

Definir la función

   antiimagen :: (Int -> Int) -> Int -> Maybe Int

1	antiimagen :: (Int -> Int) -> Int -> Maybe Int

tal que (antiimagen f y) es justo el x tal que f(x) = y, si y pertenece a la imagen de la función creciente f, o nada, en caso contrario. Por ejemplo,

   antiimagen (^2) 25  ==  Just 5
   antiimagen (^3) 25  ==  Nothing

1 2	antiimagen (^2) 25 == Just 5 antiimagen (^3) 25 == Nothing

Nota. Se supone que f está definida sobre los números naturales.

Soluciones

-- 1ª definición
-- =============

antiimagen1 :: (Int -> Int) -> Int -> Maybe Int
antiimagen1 f y 
    | estaEnImagen f y = Just x
    | otherwise        = Nothing
    where x = head [x | x <- [0..], f x == y]

-- (estaEnImagen f y) se verifica si pertenece a la imagen de f. Por
-- ejemplo, 
--    estaEnImagen (^2) 25 == True
--    estaEnImagen (^2) 30 == False
estaEnImagen :: (Int -> Int) -> Int -> Bool
estaEnImagen f y = elem y (takeWhile (<=y) (imagen f)) 

-- (imagen f) es la imagen de f. Por ejemplo,
--    take 10 (imagen (^2))  ==  [0,1,4,9,16,25,36,49,64,81]
--    take 10 (imagen (*3))  ==  [0,3,6,9,12,15,18,21,24,27]
imagen :: (Int -> Int) -> [Int]
imagen f = map f [0..]

-- 2ª definición (con lookup y maxBound)
-- =====================================

antiimagen2 :: (Int -> Int) -> Int -> Maybe Int
antiimagen2 f y =
    lookup y (takeWhile (<= (y,maxBound)) [(f x, x) | x <- [0..]])

-- 1ª definición

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

antiimagen1 :: (Int -> Int) -> Int -> Maybe Int

antiimagen1 f y

| estaEnImagen f y = Just x

| otherwise = Nothing

where x = head [x | x <- [0..], f x == y]

-- (estaEnImagen f y) se verifica si pertenece a la imagen de f. Por

-- ejemplo,

-- estaEnImagen (^2) 25 == True

-- estaEnImagen (^2) 30 == False

estaEnImagen :: (Int -> Int) -> Int -> Bool

estaEnImagen f y = elem y (takeWhile (<=y) (imagen f))

-- (imagen f) es la imagen de f. Por ejemplo,

-- take 10 (imagen (^2)) == [0,1,4,9,16,25,36,49,64,81]

-- take 10 (imagen (*3)) == [0,3,6,9,12,15,18,21,24,27]

imagen :: (Int -> Int) -> [Int]

imagen f = map f [0..]

-- 2ª definición (con lookup y maxBound)

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

antiimagen2 :: (Int -> Int) -> Int -> Maybe Int

antiimagen2 f y =

lookup y (takeWhile (<= (y,maxBound)) [(f x, x) | x <- [0..]])

Productos de N números consecutivos

PorJosé A. Alonso 17-noviembre-201526-marzo-2022

La semana pasada se planteó en Twitter el siguiente problema

Se observa que

      1x2x3x4 = 2x3x4 
      2x3x4x5 = 4x5x6

1 2	1x2x3x4 = 2x3x4 2x3x4x5 = 4x5x6

¿Existen ejemplos de otros productos de cuatro enteros consecutivos iguales a un producto de tres enteros consecutivos?

Definir la función

   esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer

1	esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer

tal que (esProductoDeNconsecutivos n x) es (Just m) si x es el producto de n enteros consecutivos a partir de m y es Nothing si x no es el producto de n enteros consecutivos. Por ejemplo,

   esProductoDeNconsecutivos 3   6  == Just 1
   esProductoDeNconsecutivos 4   6  == Nothing
   esProductoDeNconsecutivos 4  24  == Just 1
   esProductoDeNconsecutivos 3  24  == Just 2
   esProductoDeNconsecutivos 3 120  == Just 4
   esProductoDeNconsecutivos 4 120  == Just 2

esProductoDeNconsecutivos 3 6 == Just 1

esProductoDeNconsecutivos 4 6 == Nothing

esProductoDeNconsecutivos 4 24 == Just 1

esProductoDeNconsecutivos 3 24 == Just 2

esProductoDeNconsecutivos 3 120 == Just 4

esProductoDeNconsecutivos 4 120 == Just 2

Para ejemplos mayores,

   λ> esProductoDeNconsecutivos 3 (product [10^20..2+10^20])
   Just 100000000000000000000
   λ> esProductoDeNconsecutivos2 4 (product [10^20..2+10^20])
   Nothing
   λ> esProductoDeNconsecutivos2 4 (product [10^20..3+10^20])
   Just 100000000000000000000

λ> esProductoDeNconsecutivos 3 (product [10^20..2+10^20])

Just 100000000000000000000

λ> esProductoDeNconsecutivos2 4 (product [10^20..2+10^20])

Nothing

λ> esProductoDeNconsecutivos2 4 (product [10^20..3+10^20])

Just 100000000000000000000

Usando la función esProductoDeNconsecutivos resolver el problema.

Soluciones

import Data.Maybe

-- 1ª definición
esProductoDeNconsecutivos1 :: Integer -> Integer -> Maybe Integer
esProductoDeNconsecutivos1 n x 
    | null productos = Nothing
    | otherwise      = Just (head productos)
    where productos = [m | m <- [1..x-n], product [m..m+n-1] == x]

-- 2ª definición
esProductoDeNconsecutivos2 :: Integer -> Integer -> Maybe Integer
esProductoDeNconsecutivos2 n x = aux k
    where k = floor (fromIntegral x ** (1/(fromIntegral n))) - (n `div` 2)
          aux m | y == x    = Just m
                | y <  x    = aux (m+1)
                | otherwise = Nothing
                where y = product [m..m+n-1]

-- Comparación de eficiencia
--    λ> esProductoDeNconsecutivos1 3 (product [10^7..2+10^7])
--    Just 10000000
--    (12.37 secs, 5678433692 bytes)
--    λ> esProductoDeNconsecutivos2 3 (product [10^7..2+10^7])
--    Just 10000000
--    (0.00 secs, 1554932 bytes)

-- Solución del problema
-- =====================

soluciones :: [Integer]
soluciones = [x | x <- [121..]
                , isJust (esProductoDeNconsecutivos2 4 x)
                , isJust (esProductoDeNconsecutivos2 3 x)]

-- El cálculo es
--    λ> head soluciones
--    175560
--    λ> esProductoDeNconsecutivos2 4 175560
--    Just 19
--    λ> esProductoDeNconsecutivos2 3 175560
--    Just 55
--    λ> product [19,20,21,22] 
--    175560
--    λ> product [55,56,57]
--    175560
--    λ> product [19,20,21,22] == product [55,56,57]
--    True

-- Se puede definir una función para automatizar el proceso anterior:
soluciones2 :: [(Integer,[Integer],[Integer])]
soluciones2 = [(x,[a..a+3],[b..b+2]) 
               | x <- [121..]
               , let y = esProductoDeNconsecutivos2 4 x
               , isJust y
               , let z = esProductoDeNconsecutivos2 3 x
               , isJust z
               , let a = fromJust y
               , let b = fromJust z
               ]

-- El cálculo es 
--    λ> head soluciones2
--    (175560,[19,20,21,22],[55,56,57])

import Data.Maybe

-- 1ª definición

esProductoDeNconsecutivos1 :: Integer -> Integer -> Maybe Integer

esProductoDeNconsecutivos1 n x

| null productos = Nothing

| otherwise = Just (head productos)

where productos = [m | m <- [1..x-n], product [m..m+n-1] == x]

-- 2ª definición

esProductoDeNconsecutivos2 :: Integer -> Integer -> Maybe Integer

esProductoDeNconsecutivos2 n x = aux k

where k = floor (fromIntegral x ** (1/(fromIntegral n))) - (n `div` 2)

aux m | y == x = Just m

| y < x = aux (m+1)

| otherwise = Nothing

where y = product [m..m+n-1]

-- Comparación de eficiencia

-- λ> esProductoDeNconsecutivos1 3 (product [10^7..2+10^7])

-- Just 10000000

-- (12.37 secs, 5678433692 bytes)

-- λ> esProductoDeNconsecutivos2 3 (product [10^7..2+10^7])

-- Just 10000000

-- (0.00 secs, 1554932 bytes)

-- Solución del problema

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

soluciones :: [Integer]

soluciones = [x | x <- [121..]

, isJust (esProductoDeNconsecutivos2 4 x)

, isJust (esProductoDeNconsecutivos2 3 x)]

-- El cálculo es

-- λ> head soluciones

-- 175560

-- λ> esProductoDeNconsecutivos2 4 175560

-- Just 19

-- λ> esProductoDeNconsecutivos2 3 175560

-- Just 55

-- λ> product [19,20,21,22]

-- 175560

-- λ> product [55,56,57]

-- 175560

-- λ> product [19,20,21,22] == product [55,56,57]

-- True

-- Se puede definir una función para automatizar el proceso anterior:

soluciones2 :: [(Integer,[Integer],[Integer])]

soluciones2 = [(x,[a..a+3],[b..b+2])

| x <- [121..]

, let y = esProductoDeNconsecutivos2 4 x

, isJust y

, let z = esProductoDeNconsecutivos2 3 x

, isJust z

, let a = fromJust y

, let b = fromJust z

]

-- El cálculo es

-- λ> head soluciones2

-- (175560,[19,20,21,22],[55,56,57])

Dígitos visibles y ocultos

PorJosé A. Alonso 16-noviembre-201526-marzo-2022

Una cadena clave es una cadena que contiene dígitos visibles y ocultos. Los dígitos se ocultan mediante las primeras letras minúsculas: la ‘a’ oculta el ‘0’, la ‘b’ el ‘1’ y así sucesivamente hasta la ‘j’ que oculta el ‘9’. Los restantes símbolos de la cadena no tienen significado y se pueden ignorar.

Definir la función

   numeroOculto :: String -> Maybe Integer

1	numeroOculto :: String -> Maybe Integer

tal que (numeroOculto cs) es justo el número formado por los dígitos visibles u ocultos de la cadena clave cs, si cs tiene dígitos y Nothing en caso contrario. Por ejemplo,

   numeroOculto "jihgfedcba"            ==  Just 9876543210
   numeroOculto "JIHGFEDCBA"            ==  Nothing
   numeroOculto "el 23 de Enero"        ==  Just 423344
   numeroOculto "El 23 de Enero"        ==  Just 23344
   numeroOculto "El 23 de enero"        ==  Just 233444
   numeroOculto "Todo para nada"        ==  Just 300030
   numeroOculto (replicate (10^6) 'A')  ==  Nothing

numeroOculto "jihgfedcba" == Just 9876543210

numeroOculto "JIHGFEDCBA" == Nothing

numeroOculto "el 23 de Enero" == Just 423344

numeroOculto "El 23 de Enero" == Just 23344

numeroOculto "El 23 de enero" == Just 233444

numeroOculto "Todo para nada" == Just 300030

numeroOculto (replicate (10^6) 'A') == Nothing

Soluciones

import Data.Char (isDigit, ord, chr)

numeroOculto :: String -> Maybe Integer
numeroOculto cs | null aux  = Nothing
                | otherwise = Just (read aux)
    where aux = filter isDigit (map visible cs)

visible :: Char -> Char
visible c | c `elem` ['a'..'j'] = chr (ord c - n)
          | otherwise           = c
          where n = ord 'a' - ord '0'

import Data.Char (isDigit, ord, chr)

numeroOculto :: String -> Maybe Integer

numeroOculto cs | null aux = Nothing

| otherwise = Just (read aux)

where aux = filter isDigit (map visible cs)

visible :: Char -> Char

visible c | c `elem` ['a'..'j'] = chr (ord c - n)

| otherwise = c

where n = ord 'a' - ord '0'

Siguiente elemento en una lista

PorJosé A. Alonso 2-febrero-201526-marzo-2022

Definir la función

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

1	siguiente :: Eq a => a -> [a] -> Maybe a

tal que (siguiente x ys) es justo el elemento siguiente a la primera ocurrencia de x en ys o Nothing si x no pertenece a ys. Por ejemplo,

   siguiente 5 [3,5,2,5,7]                       ==  Just 2
   siguiente 9 [3,5,2,5,7]                       ==  Nothing
   siguiente 'd' "afdegdb"                       ==  Just 'e'
   siguiente "todo" ["En","todo","la","medida"]  ==  Just "la"
   siguiente "nada" ["En","todo","la","medida"]  ==  Nothing
   siguiente 999999 [1..1000000]                 ==  Just 1000000
   siguiente 1000000 [1..1000000]                ==  Nothing

siguiente 5 [3,5,2,5,7] == Just 2

siguiente 9 [3,5,2,5,7] == Nothing

siguiente 'd' "afdegdb" == Just 'e'

siguiente "todo" ["En","todo","la","medida"] == Just "la"

siguiente "nada" ["En","todo","la","medida"] == Nothing

siguiente 999999 [1..1000000] == Just 1000000

siguiente 1000000 [1..1000000] == Nothing

Soluciones

import Data.Maybe (listToMaybe) -- Para la 4ª solución

-- 1ª solución (por recursión):
siguiente1 :: Eq a => a -> [a] -> Maybe a
siguiente1 x (y1:y2:ys) | x == y1   = Just y2
                        | otherwise = siguiente1 x (y2:ys)
siguiente1 x _ = Nothing

-- 2ª solución (por comprensión):
siguiente2 :: Eq a => a -> [a] -> Maybe a
siguiente2 x ys 
    | null zs   = Nothing
    | otherwise = Just (snd (head zs))
    where zs = [(u,v) | (u,v) <- zip ys (tail ys), u == x]  

-- 3ª solución (con dropWhile)
siguiente3 :: Eq a => a -> [a] -> Maybe a
siguiente3 x = aux . drop 1 . dropWhile (/=x)
    where aux []    = Nothing
          aux (y:_) = Just y

-- 4ª solución (con dropWhile y listToMaybe):
siguiente4 :: Eq a => a -> [a] -> Maybe a
siguiente4 x = listToMaybe . drop 1 . dropWhile (/=x)

-- Nota: En la librería Data.Maybe está definida la función 
--    listToMaybe :: [a] -> Maybe a 
-- tal que (listToMaybe xs) es Nothing si la lista xs está vacía y es
-- justo el primer elemento, en caso contrario, Por ejemplo,
--    listToMaybe []       ==  Nothing
--    listToMaybe [3,2,5]  ==  Just 3

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    ghci> let n=10^6 in siguiente1 (n-1) [1..n]
--    Just 1000000
--    (1.34 secs, 277352616 bytes)
--    
--    ghci> let n=10^6 in siguiente2 (n-1) [1..n]
--    Just 1000000
--    (1.45 secs, 340836576 bytes)
--    
--    ghci> let n=10^6 in siguiente3 (n-1) [1..n]
--    Just 1000000
--    (0.26 secs, 84987544 bytes)
--    
--    ghci> let n=10^6 in siguiente4 (n-1) [1..n]
--    Just 1000000
--    (0.26 secs, 84987440 bytes)

import Data.Maybe (listToMaybe) -- Para la 4ª solución

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

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

siguiente1 x (y1:y2:ys) | x == y1 = Just y2

| otherwise = siguiente1 x (y2:ys)

siguiente1 x _ = Nothing

-- 2ª solución (por comprensión):

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

siguiente2 x ys

| null zs = Nothing

| otherwise = Just (snd (head zs))

where zs = [(u,v) | (u,v) <- zip ys (tail ys), u == x]

-- 3ª solución (con dropWhile)

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

siguiente3 x = aux . drop 1 . dropWhile (/=x)

where aux [] = Nothing

aux (y:_) = Just y

-- 4ª solución (con dropWhile y listToMaybe):

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

siguiente4 x = listToMaybe . drop 1 . dropWhile (/=x)

-- Nota: En la librería Data.Maybe está definida la función

-- listToMaybe :: [a] -> Maybe a

-- tal que (listToMaybe xs) es Nothing si la lista xs está vacía y es

-- justo el primer elemento, en caso contrario, Por ejemplo,

-- listToMaybe [] == Nothing

-- listToMaybe [3,2,5] == Just 3

-- Comparación de eficiencia

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

-- La comparación es

-- ghci> let n=10^6 in siguiente1 (n-1) [1..n]

-- Just 1000000

-- (1.34 secs, 277352616 bytes)

-- ghci> let n=10^6 in siguiente2 (n-1) [1..n]

-- Just 1000000

-- (1.45 secs, 340836576 bytes)

-- ghci> let n=10^6 in siguiente3 (n-1) [1..n]

-- Just 1000000

-- (0.26 secs, 84987544 bytes)

-- ghci> let n=10^6 in siguiente4 (n-1) [1..n]

-- Just 1000000

-- (0.26 secs, 84987440 bytes)

Soluciones

Nuevas soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Otras soluciones

Pensamiento

Soluciones

Otras soluciones

Pensamiento

Soluciones

Otras soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Solución en Maxima

Referencia

Soluciones

Soluciones

En Maxima

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico