I1M2011: Resolución de problemas matemáticos con Haskell

La clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los 6 primeros ejercicios de la 12ª relación en la que se plantea la resolución de distintos problemas matemáticos. En concreto,

el problema de Ullman sobre la existencia de subconjunto del tamaño dado y con su suma acotada,
las descomposiciones de un número como suma de dos cuadrados,
el problema 145 del proyecto Euler,
el grafo de una función sobre los elementos que cumplen una propiedad,
los números semiperfectos,

Además, de los 2 primeros se presentan distintas definiciones y se compara su eficiencia.

Estos ejercicios corresponden a los temas 5, 6 y 7.

Los ejercicios, y sus soluciones, se muestran a continuación.

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Test.QuickCheck
import Data.List

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función 
--    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool
-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k 
-- elementos cuya suma sea menor que t. Por ejemplo,
--    ullman 9 3 [1..10] == True
--    ullman 5 3 [1..10] == False
-- ---------------------------------------------------------------------

-- 1ª solución (corta y eficiente)
ullman :: (Ord a, Num a) => a -> Int -> [a] -> Bool
ullman t k xs = sum (take k (sort xs)) < t

-- 2ª solución (larga e ineficiente)
ullman2 :: (Num a, Ord a) => a -> Int -> [a] -> Bool
ullman2 t k xs = 
    [ys | ys <- subconjuntos xs, length ys == k, sum ys < t] /= []

-- (subconjuntos xs) es la lista de los subconjuntos de xs. Por 
-- ejemplo,
--    subconjuntos "bc"  ==  ["","c","b","bc"]
--    subconjuntos "abc" ==  ["","c","b","bc","a","ac","ab","abc"]
subconjuntos :: [a] -> [[a]]
subconjuntos [] = [[]]
subconjuntos (x:xs) = zss++[x:ys | ys <- zss]
    where zss = subconjuntos xs

-- Los siguientes ejemplos muestran la diferencia en la eficencia:
--    *Main> ullman 9 3 [1..20]
--    True
--    (0.02 secs, 528380 bytes)
--    *Main> ullman2 9 3 [1..20]
--    True
--    (4.08 secs, 135267904 bytes)
--    *Main> ullman 9 3 [1..100]
--    True
--    (0.02 secs, 526360 bytes)
--    *Main> ullman2 9 3 [1..100]
--      C-c C-cInterrupted.
--    Agotado

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]
-- tal que (sumasDe2Cuadrados n) es la lista de los pares de números
-- tales que la suma de sus cuadrados es n y el primer elemento del par
-- es mayor o igual que el segundo. Por ejemplo,
--    sumasDe2Cuadrados 25  ==  [(5,0),(4,3)]
-- ---------------------------------------------------------------------

-- Primera definición:
sumasDe2Cuadrados_1 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados_1 n = 
    [(x,y) | x <- [n,n-1..0],
             y <- [0..x],
             x*x+y*y == n]

-- Segunda definición:
sumasDe2Cuadrados_2 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados_2 n = 
    [(x,y) | x <- [a,a-1..0],
             y <- [0..x],
             x*x+y*y == n]
    where a = ceiling (sqrt (fromIntegral n))

-- Tercera definición:
sumasDe2Cuadrados_3 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados_3 n = aux (ceiling (sqrt (fromIntegral n))) 0 where
    aux x y | x < y          = [] 
            | x*x + y*y <  n = aux x (y+1)
            | x*x + y*y == n = (x,y) : aux (x-1) (y+1)
            | otherwise      = aux (x-1) y

-- Comparación
--    +----------+---------------+---------------+---------------+
--    | n        | 1ª definición | 2ª definición | 3ª definición |
--    +----------+---------------+---------------+---------------+
--    |      999 | 2.17 segs     |   0.02 segs   | 0.01 segs     |  
--    | 48612265 |               | 140.38 segs   | 0.13 segs     |
--    +----------+---------------+---------------+---------------+

-- ---------------------------------------------------------------------
-- Ejercicio 3. (Basado en el problema 145 del Proyecto Euler). Se dice
-- que un número n es reversible si su última cifra es distinta de 0 y
-- la suma de n y el número obtenido escribiendo las cifras de n en
-- orden inverso es un número que tiene todas sus cifras impares. Por
-- ejemplo, 36 es reversible porque 36+63=99 tiene todas sus cifras
-- impares, 409 es reversible porque 409+904=1313 tiene todas sus cifras
-- impares,  243 no es reversible porque 243+342=585 no tiene todas sus
-- cifras impares. 
-- Definir la función 
--    reversiblesMenores :: Int -> Int
-- tal que (reversiblesMenores n) es la cantidad de números reversibles
-- menores que n. Por ejemplo,
--    reversiblesMenores 10   == 0
--    reversiblesMenores 100  == 20
--    reversiblesMenores 1000 == 120
-- ---------------------------------------------------------------------

reversiblesMenores :: Int -> Int
reversiblesMenores n = length [x | x <- [1..n-1], esReversible x]

-- (esReversible n) se verifica si n es reversible; es decir, si su
-- última cifra es distinta de 0 y la suma de n y el número obtenido
-- escribiendo las cifras de n en orden inverso es un número que tiene
-- todas sus cifras impares. Por ejemplo,
--    esReversible 36  == True
--    esReversible 409 == True
esReversible :: Int -> Bool
esReversible n = rem n 10 /= 0 && impares (cifras (n + (inverso n)))

-- (impares xs) se verifica si xs es una lista de números impares. Por
-- ejemplo, 
--    impares [3,5,1] == True
--    impares [3,4,1] == False
impares :: [Int] -> Bool
impares xs = and [odd x | x <- xs]

-- (inverso n) es el número obtenido escribiendo las cifras de n en
-- orden inverso. Por ejemplo,
--    inverso 3034 == 4303
inverso :: Int -> Int
inverso n = read (reverse (show n))

-- (cifras n) es la lista de las cifras del número n. Por ejemplo,
--    cifras 3034 == [3,0,3,4]
cifras :: Int -> [Int]
cifras n = [read [x] | x <- show n]

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir, usando funciones de orden superior, la función
--    grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]
-- tal que (grafoReducido f p xs) es la lista (sin repeticiones) de los
-- pares formados por los elementos de xs que verifican el predicado p
-- y sus imágenes. Por ejemplo, 
--    grafoReducido (^2) even [1..9]  ==  [(2,4),(4,16),(6,36),(8,64)]
--    grafoReducido (+4) even (replicate 40 1) == []
--    grafoReducido (*5) even (replicate 40 2) == [(2,10)]
-- ---------------------------------------------------------------------

grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]
grafoReducido f p xs = [(x,f x) | x <- nub xs, p x]

-- -------------------------------------------------------------------
-- Ejercicio 6.1. Un número natural n se denomina semiperfecto si es la
-- suma de algunos de sus divisores propios. Por ejemplo, 18 es
-- semiperfecto ya que sus divisores son 1, 2, 3, 6, 9 y se cumple que
-- 3+6+9=18.  
-- 
-- Definir la función 
--    esSemiPerfecto :: Int -> Bool
-- tal que (esSemiPerfecto n) se verifica si n es semiperfecto. Por
-- ejemplo, 
--    esSemiPerfecto 18 == True
--    esSemiPerfecto 9  == False
--    esSemiPerfecto 24 == True
-- ---------------------------------------------------------------------

esSemiPerfecto :: Int -> Bool
esSemiPerfecto n =
    or [sum ys == n | ys <- subconjuntos (divisores n)]

-- (divisores n) es la lista de los divisores propios de n. Por ejemplo,
--    divisores 18 == [1,2,3,6,9]
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n-1], mod n x == 0]

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir la constante primerSemiPerfecto tal que su
-- valor es el primer número semiperfecto. 
-- ---------------------------------------------------------------------

primerSemiPerfecto :: Int
primerSemiPerfecto = head [n | n <- [1..], esSemiPerfecto n]

-- La evaluación es
--    *Main> primerSemiPerfecto
--    6

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Definir la función 
--    semiPerfecto :: Int -> Int
-- tal que (semiPerfecto n) es el n-ésimo número semiperfecto. Por
-- ejemplo, 
--    semiPerfecto 1   == 6
--    semiPerfecto 4   == 20
--    semiPerfecto 100 == 414
-- ---------------------------------------------------------------------

semiPerfecto :: Int -> Int
semiPerfecto n = semiPerfectos !! n

-- semiPerfectos es la lista de los números semiPerfectos. Por ejemplo, 
--    take 4 semiPerfectos  ==  [6,12,18,20]
semiPerfectos = [n | n <- [1..], esSemiPerfecto n]

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

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

-- ---------------------------------------------------------------------

-- Importación de librerías auxiliares --

-- ---------------------------------------------------------------------

import Test.QuickCheck

import Data.List

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir la función

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

-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k

-- elementos cuya suma sea menor que t. Por ejemplo,

-- ullman 9 3 [1..10] == True

-- ullman 5 3 [1..10] == False

-- ---------------------------------------------------------------------

-- 1ª solución (corta y eficiente)

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

ullman t k xs = sum (take k (sort xs)) < t

-- 2ª solución (larga e ineficiente)

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

ullman2 t k xs =

[ys | ys <- subconjuntos xs, length ys == k, sum ys < t] /= []

-- (subconjuntos xs) es la lista de los subconjuntos de xs. Por

-- ejemplo,

-- subconjuntos "bc" == ["","c","b","bc"]

-- subconjuntos "abc" == ["","c","b","bc","a","ac","ab","abc"]

subconjuntos :: [a] -> [[a]]

subconjuntos [] = [[]]

subconjuntos (x:xs) = zss++[x:ys | ys <- zss]

where zss = subconjuntos xs

-- Los siguientes ejemplos muestran la diferencia en la eficencia:

-- *Main> ullman 9 3 [1..20]

-- True

-- (0.02 secs, 528380 bytes)

-- *Main> ullman2 9 3 [1..20]

-- True

-- (4.08 secs, 135267904 bytes)

-- *Main> ullman 9 3 [1..100]

-- True

-- (0.02 secs, 526360 bytes)

-- *Main> ullman2 9 3 [1..100]

-- C-c C-cInterrupted.

-- Agotado

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]

-- tal que (sumasDe2Cuadrados n) es la lista de los pares de números

-- tales que la suma de sus cuadrados es n y el primer elemento del par

-- es mayor o igual que el segundo. Por ejemplo,

-- sumasDe2Cuadrados 25 == [(5,0),(4,3)]

-- ---------------------------------------------------------------------

-- Primera definición:

sumasDe2Cuadrados_1 :: Integer -> [(Integer, Integer)]

sumasDe2Cuadrados_1 n =

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

y <- [0..x],

x*x+y*y == n]

-- Segunda definición:

sumasDe2Cuadrados_2 :: Integer -> [(Integer, Integer)]

sumasDe2Cuadrados_2 n =

[(x,y) | x <- [a,a-1..0],

y <- [0..x],

x*x+y*y == n]

where a = ceiling (sqrt (fromIntegral n))

-- Tercera definición:

sumasDe2Cuadrados_3 :: Integer -> [(Integer, Integer)]

sumasDe2Cuadrados_3 n = aux (ceiling (sqrt (fromIntegral n))) 0 where

aux x y | x < y = []

| x*x + y*y < n = aux x (y+1)

| x*x + y*y == n = (x,y) : aux (x-1) (y+1)

| otherwise = aux (x-1) y

-- Comparación

-- +----------+---------------+---------------+---------------+

-- +----------+---------------+---------------+---------------+

-- | 48612265 | | 140.38 segs | 0.13 segs |

-- +----------+---------------+---------------+---------------+

-- ---------------------------------------------------------------------

-- Ejercicio 3. (Basado en el problema 145 del Proyecto Euler). Se dice

-- que un número n es reversible si su última cifra es distinta de 0 y

-- la suma de n y el número obtenido escribiendo las cifras de n en

-- orden inverso es un número que tiene todas sus cifras impares. Por

-- ejemplo, 36 es reversible porque 36+63=99 tiene todas sus cifras

-- impares, 409 es reversible porque 409+904=1313 tiene todas sus cifras

-- impares, 243 no es reversible porque 243+342=585 no tiene todas sus

-- cifras impares.

-- Definir la función

-- reversiblesMenores :: Int -> Int

-- tal que (reversiblesMenores n) es la cantidad de números reversibles

-- menores que n. Por ejemplo,

-- reversiblesMenores 10 == 0

-- reversiblesMenores 100 == 20

-- reversiblesMenores 1000 == 120

-- ---------------------------------------------------------------------

reversiblesMenores :: Int -> Int

reversiblesMenores n = length [x | x <- [1..n-1], esReversible x]

-- (esReversible n) se verifica si n es reversible; es decir, si su

-- última cifra es distinta de 0 y la suma de n y el número obtenido

-- escribiendo las cifras de n en orden inverso es un número que tiene

-- todas sus cifras impares. Por ejemplo,

-- esReversible 36 == True

-- esReversible 409 == True

esReversible :: Int -> Bool

esReversible n = rem n 10 /= 0 && impares (cifras (n + (inverso n)))

-- (impares xs) se verifica si xs es una lista de números impares. Por

-- ejemplo,

-- impares [3,5,1] == True

-- impares [3,4,1] == False

impares :: [Int] -> Bool

impares xs = and [odd x | x <- xs]

-- (inverso n) es el número obtenido escribiendo las cifras de n en

-- orden inverso. Por ejemplo,

-- inverso 3034 == 4303

inverso :: Int -> Int

inverso n = read (reverse (show n))

-- (cifras n) es la lista de las cifras del número n. Por ejemplo,

-- cifras 3034 == [3,0,3,4]

cifras :: Int -> [Int]

cifras n = [read [x] | x <- show n]

-- ---------------------------------------------------------------------

-- Ejercicio 5. Definir, usando funciones de orden superior, la función

-- grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]

-- tal que (grafoReducido f p xs) es la lista (sin repeticiones) de los

-- pares formados por los elementos de xs que verifican el predicado p

-- y sus imágenes. Por ejemplo,

-- grafoReducido (^2) even [1..9] == [(2,4),(4,16),(6,36),(8,64)]

-- grafoReducido (+4) even (replicate 40 1) == []

-- grafoReducido (*5) even (replicate 40 2) == [(2,10)]

-- ---------------------------------------------------------------------

grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]

grafoReducido f p xs = [(x,f x) | x <- nub xs, p x]

-- -------------------------------------------------------------------

-- Ejercicio 6.1. Un número natural n se denomina semiperfecto si es la

-- suma de algunos de sus divisores propios. Por ejemplo, 18 es

-- semiperfecto ya que sus divisores son 1, 2, 3, 6, 9 y se cumple que

-- 3+6+9=18.

-- Definir la función

-- esSemiPerfecto :: Int -> Bool

-- tal que (esSemiPerfecto n) se verifica si n es semiperfecto. Por

-- ejemplo,

-- esSemiPerfecto 18 == True

-- esSemiPerfecto 9 == False

-- esSemiPerfecto 24 == True

-- ---------------------------------------------------------------------

esSemiPerfecto :: Int -> Bool

esSemiPerfecto n =

or [sum ys == n | ys <- subconjuntos (divisores n)]

-- (divisores n) es la lista de los divisores propios de n. Por ejemplo,

-- divisores 18 == [1,2,3,6,9]

divisores :: Int -> [Int]

divisores n = [x | x <- [1..n-1], mod n x == 0]

-- ---------------------------------------------------------------------

-- Ejercicio 6.2. Definir la constante primerSemiPerfecto tal que su

-- valor es el primer número semiperfecto.

-- ---------------------------------------------------------------------

primerSemiPerfecto :: Int

primerSemiPerfecto = head [n | n <- [1..], esSemiPerfecto n]

-- La evaluación es

-- *Main> primerSemiPerfecto

-- 6

-- ---------------------------------------------------------------------

-- Ejercicio 6.3. Definir la función

-- semiPerfecto :: Int -> Int

-- tal que (semiPerfecto n) es el n-ésimo número semiperfecto. Por

-- ejemplo,

-- semiPerfecto 1 == 6

-- semiPerfecto 4 == 20

-- semiPerfecto 100 == 414

-- ---------------------------------------------------------------------

semiPerfecto :: Int -> Int

semiPerfecto n = semiPerfectos !! n

-- semiPerfectos es la lista de los números semiPerfectos. Por ejemplo,

-- take 4 semiPerfectos == [6,12,18,20]

semiPerfectos = [n | n <- [1..], esSemiPerfecto n]

Se puede imprimir o compartir con