map – Página 6 – Exercitium

Números dígito potenciales

PorJosé A. Alonso 15-noviembre-201725-noviembre-2017

Un número entero x es dígito potencial de orden n si x es la suma de los dígitos de x elevados a n. Por ejemplo,

153 es un dígito potencial de orden 3 ya que 153 = 1^3+5^3+3^3
4150 es un dígito potencial de orden 5 ya que 4150 = 4^5+1^5+5^5+0^5

Un número x es dígito auto potencial si es un dígito potencial de orden n, donde n es el número de dígitos de n. Por ejemplo, 153 es un número dígito auto potencial.

Definir las funciones

   digitosPotencialesOrden :: Integer -> [Integer]
   digitosAutoPotenciales  :: [Integer]

1 2	digitosPotencialesOrden :: Integer -> [Integer] digitosAutoPotenciales :: [Integer]

tales que

(digitosPotencialesOrden n) es la lista de los números dígito potenciales de orden n. Por ejemplo,

     take 6 (digitosPotencialesOrden 3)  ==  [0,1,153,370,371,407]
     take 5 (digitosPotencialesOrden 4)  ==  [0,1,1634,8208,9474]
     take 8 (digitosPotencialesOrden 5)  ==  [0,1,4150,4151,54748,92727,93084,194979]
     take 3 (digitosPotencialesOrden 6)  ==  [0,1,548834]

take 6 (digitosPotencialesOrden 3) == [0,1,153,370,371,407]

take 5 (digitosPotencialesOrden 4) == [0,1,1634,8208,9474]

take 8 (digitosPotencialesOrden 5) == [0,1,4150,4151,54748,92727,93084,194979]

take 3 (digitosPotencialesOrden 6) == [0,1,548834]

digitosAutoPotenciales es la lista de los números dígito auto potenciales. Por ejemplo,

     λ> take 20 digitosAutoPotenciales
     [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

1 2	λ> take 20 digitosAutoPotenciales [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

Soluciones

import Data.List (genericLength)
import Data.Char (digitToInt)

-- 1ª definición de digitosPotencialesOrden
-- ========================================

digitosPotencialesOrden :: Integer -> [Integer]
digitosPotencialesOrden n =
  [x | x <- [0..]
     , esDigitoPotencialOrden n x]

esDigitoPotencialOrden :: Integer -> Integer -> Bool
esDigitoPotencialOrden n x =
  x == sum [y^n | y <- digitos x]

digitos :: Integer -> [Integer]
digitos x = [read [d] | d <- show x] 

-- 2ª definición de digitosPotencialesOrden
-- ========================================

digitosPotencialesOrden2 :: Integer -> [Integer]
digitosPotencialesOrden2 n =
  filter (esDigitoPotencialOrden2 n) [0..]

esDigitoPotencialOrden2 :: Integer -> Integer -> Bool
esDigitoPotencialOrden2 n x =
  x == sum (map (^n) (digitos2 x))

digitos2 :: Integer -> [Integer]
digitos2 = map (toInteger . digitToInt) . show

-- 3ª definición de digitosPotencialesOrden
-- ========================================

--    digitosPotencialesOrden3 3  ==  [0,1,153,370,371,407]
--    digitosPotencialesOrden3 4  ==  [0,1,1634,8208,9474]
digitosPotencialesOrden3 :: Integer -> [Integer]
digitosPotencialesOrden3 n =
  filter (esDigitoPotencialOrden2 n) [0..10^d-1]
  where d = maximoNDigitosPotencialesOrden n 

-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de
-- los números dígitos potenciales de orden d. Por ejemplo,
--    maximoNDigitosPotencialesOrden 3  ==  5
--    maximoNDigitosPotencialesOrden 5  ==  7
maximoNDigitosPotencialesOrden :: Integer -> Integer
maximoNDigitosPotencialesOrden n =
  head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])

-- 1ª definición de esDigitoAutoPotencial
-- ======================================

esDigitoAutoPotencial :: Integer -> Bool
esDigitoAutoPotencial x =
  esDigitoPotencialOrden (genericLength (show x)) x

digitosAutoPotenciales :: [Integer]
digitosAutoPotenciales =
  filter esDigitoAutoPotencial [0..]

-- 2ª definición de esDigitoAutoPotencial
-- ======================================

digitosAutoPotenciales2 :: [Integer]
digitosAutoPotenciales2 =
  0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]
            | k <- [0..]]

import Data.List (genericLength)

import Data.Char (digitToInt)

-- 1ª definición de digitosPotencialesOrden

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

digitosPotencialesOrden :: Integer -> [Integer]

digitosPotencialesOrden n =

[x | x <- [0..]

, esDigitoPotencialOrden n x]

esDigitoPotencialOrden :: Integer -> Integer -> Bool

esDigitoPotencialOrden n x =

x == sum [y^n | y <- digitos x]

digitos :: Integer -> [Integer]

digitos x = [read [d] | d <- show x]

-- 2ª definición de digitosPotencialesOrden

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

digitosPotencialesOrden2 :: Integer -> [Integer]

digitosPotencialesOrden2 n =

filter (esDigitoPotencialOrden2 n) [0..]

esDigitoPotencialOrden2 :: Integer -> Integer -> Bool

esDigitoPotencialOrden2 n x =

x == sum (map (^n) (digitos2 x))

digitos2 :: Integer -> [Integer]

digitos2 = map (toInteger . digitToInt) . show

-- 3ª definición de digitosPotencialesOrden

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

-- digitosPotencialesOrden3 3 == [0,1,153,370,371,407]

-- digitosPotencialesOrden3 4 == [0,1,1634,8208,9474]

digitosPotencialesOrden3 :: Integer -> [Integer]

digitosPotencialesOrden3 n =

filter (esDigitoPotencialOrden2 n) [0..10^d-1]

where d = maximoNDigitosPotencialesOrden n

-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de

-- los números dígitos potenciales de orden d. Por ejemplo,

-- maximoNDigitosPotencialesOrden 3 == 5

-- maximoNDigitosPotencialesOrden 5 == 7

maximoNDigitosPotencialesOrden :: Integer -> Integer

maximoNDigitosPotencialesOrden n =

head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])

-- 1ª definición de esDigitoAutoPotencial

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

esDigitoAutoPotencial :: Integer -> Bool

esDigitoAutoPotencial x =

esDigitoPotencialOrden (genericLength (show x)) x

digitosAutoPotenciales :: [Integer]

digitosAutoPotenciales =

filter esDigitoAutoPotencial [0..]

-- 2ª definición de esDigitoAutoPotencial

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

digitosAutoPotenciales2 :: [Integer]

digitosAutoPotenciales2 =

0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]

| k <- [0..]]

Pares definidos por su MCD y su MCM

PorJosé A. Alonso 10-noviembre-201725-abril-2021

Definir las siguientes funciones

   pares  :: Integer -> Integer -> [(Integer,Integer)]
   nPares :: Integer -> Integer -> Integer

1 2	pares :: Integer -> Integer -> [(Integer,Integer)] nPares :: Integer -> Integer -> Integer

tales que

(pares a b) es la lista de los pares de números enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,

     pares 3 3  == [(3,3)]
     pares 4 12 == [(4,12),(12,4)]
     pares 2 12 == [(2,12),(4,6),(6,4),(12,2)]
     pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]
     pares 2 7  == []
     pares 12 3 == []
     length (pares 3 (product [3,5..91]))  ==  8388608

pares 3 3 == [(3,3)]

pares 4 12 == [(4,12),(12,4)]

pares 2 12 == [(2,12),(4,6),(6,4),(12,2)]

pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]

pares 2 7 == []

pares 12 3 == []

length (pares 3 (product [3,5..91])) == 8388608

(nPares a b) es el número de pares de enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,

     nPares 3 3   ==  1
     nPares 4 12  ==  2
     nPares 2 12  ==  4
     nPares 2 60  ==  8
     nPares 2 7   ==  0
     nPares 12 3  ==  0
     nPares 3 (product [3..3*10^4]) `mod` (10^12)  ==  477999992832
     length (show (nPares 3 (product [3..3*10^4])))  ==  977

nPares 3 3 == 1

nPares 4 12 == 2

nPares 2 12 == 4

nPares 2 60 == 8

nPares 2 7 == 0

nPares 12 3 == 0

nPares 3 (product [3..3*10^4]) `mod` (10^12) == 477999992832

length (show (nPares 3 (product [3..3*10^4]))) == 977

Soluciones

import Data.Numbers.Primes (primeFactors)
import Data.List (genericLength, group, nub, sort, subsequences)
import Test.QuickCheck

-- 1ª definición de pares
-- ======================

pares1 :: Integer -> Integer -> [(Integer,Integer)]
pares1 a b = [(x,y) | x <- [1..b]
                    , y <- [1..b]
                    , gcd x y == a
                    , lcm x y == b]

-- 2ª definición de pares
-- ======================

pares2 :: Integer -> Integer -> [(Integer,Integer)]
pares2 a b = [(x,y) | x <- [a,a+a..b]
                    , y <- [a,a+a..b]
                    , gcd x y == a
                    , lcm x y == b]

-- Comparacioń de eficiencia
--    λ> length (pares1 3 (product [3,5..11]))
--    16
--    (95.12 secs, 86,534,165,528 bytes)
--    λ> length (pares2 3 (product [3,5..11]))
--    16
--    (15.80 secs, 14,808,762,128 bytes)

-- 3ª definición de pares
-- ======================

pares3 :: Integer -> Integer -> [(Integer,Integer)]
pares3 a b = [(x,y) | x <- [a,a+a..b]
                    , c `rem` x == 0
                    , let y = c `div` x
                    , gcd x y == a
                    ]
  where c = a * b

-- Comparacioń de eficiencia
--    λ> length (pares2 3 (product [3,5..11]))
--    16
--    (15.80 secs, 14,808,762,128 bytes)
--    λ> length (pares3 3 (product [3,5..11]))
--    16
--    (0.01 secs, 878,104 bytes)

-- 4ª definición de pares
-- ======================

-- Para la cuarta definición de pares se observa la relación con los
-- factores primos
--    λ> [(primeFactors x, primeFactors y) | (x,y) <- pares1 2 12]
--    [([2],[2,2,3]),([2,2],[2,3]),([2,3],[2,2]),([2,2,3],[2])]
--    λ> [primeFactors x | (x,y) <- pares1 2 12]
--    [[2],[2,2],[2,3],[2,2,3]]
--    λ> [primeFactors x | (x,y) <- pares1 2 60]
--    [[2],[2,2],[2,3],[2,5],[2,2,3],[2,2,5],[2,3,5],[2,2,3,5]]
--    λ> [primeFactors x | (x,y) <- pares1 6 60]
--    [[2,3],[2,2,3],[2,3,5],[2,2,3,5]]
--    λ> [primeFactors x | (x,y) <- pares1 2 24]
--    [[2],[2,3],[2,2,2],[2,2,2,3]]
-- Se observa que cada pare se obtiene de uno de los subconjuntos de los
-- divisores primos de b/a. Por ejemplo,
--    λ> (a,b) = (2,24)
--    λ> b `div` a
--    12
--    λ> primeFactors it
--    [2,2,3]
--    λ> group it
--    [[2,2],[3]]
--    λ> subsequences it
--    [[],[[2,2]],[[3]],[[2,2],[3]]]
--    λ> map concat it
--    [[],[2,2],[3],[2,2,3]]
--    λ> map product it
--    [1,4,3,12]
--    λ> [(a * x, b `div` x) | x <- it]
--    [(2,24),(8,6),(6,8),(24,2)]
-- A partir de la observación se construye la siguiente definición

pares4 :: Integer -> Integer -> [(Integer,Integer)]
pares4 a b
  | b `mod` a /= 0 = []
  | otherwise =
    [(a * x, b `div` x)
    | x <- map (product . concat)
               ((subsequences . group . primeFactors) (b `div` a))]

-- Nota. La función pares4 calcula el mismo conjunto que las anteriores,
-- pero no necesariamente en el mismo orde. Por ejemplo,
--    λ> pares3 2 60 
--    [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]
--    λ> pares4 2 60 
--    [(2,60),(4,30),(6,20),(12,10),(10,12),(20,6),(30,4),(60,2)]
--    λ> pares3 2 60 == sort (pares4 2 60)
--    True

-- Comparacioń de eficiencia
--    λ> length (pares3 3 (product [3,5..17]))
--    64
--    (4.44 secs, 2,389,486,440 bytes)
--    λ> length (pares4 3 (product [3,5..17]))
--    64
--    (0.00 secs, 177,704 bytes)
  
-- Propiedades de equivalencia de pares
-- ====================================

prop_pares :: Integer -> Integer -> Property
prop_pares a b =
  a > 0 && b > 0 ==>
  all (== pares1 a b)
      [sort (f a b) | f <- [ pares2
                           , pares3
                           , pares4
                           ]]
  
prop_pares2 :: Integer -> Integer -> Property
prop_pares2 a b =
  a > 0 && b > 0 ==>
  all (== pares1 a (a * b))
      [sort (f a (a * b)) | f <- [ pares2
                                 , pares3
                                 , pares4
                                 ]]
  
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares
--    +++ OK, passed 100 tests.
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares
--    +++ OK, passed 100 tests.
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares2
--    +++ OK, passed 100 tests.
             
-- 1ª definición de nPares
-- =======================

nPares1 :: Integer -> Integer -> Integer
nPares1 a b = genericLength (pares4 a b)

-- 2ª definición de nPares
-- =======================

nPares2 :: Integer -> Integer -> Integer
nPares2 a b = 2^(length (nub (primeFactors (b `div` a))))

-- Comparación de eficiencia
--    λ> nPares1 3 (product [3,5..91])
--    8388608
--    (4.68 secs, 4,178,295,920 bytes)
--    λ> nPares2 3 (product [3,5..91])
--    8388608
--    (0.00 secs, 234,688 bytes)

-- Propiedad de equivalencia de nPares
-- ===================================

prop_nPares :: Integer -> Integer -> Property
prop_nPares a b =
  a > 0 && b > 0 ==>
  nPares1 a (a * b) == nPares2 a (a * b)
  
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_nPares
--    +++ 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

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

import Data.Numbers.Primes (primeFactors)

import Data.List (genericLength, group, nub, sort, subsequences)

import Test.QuickCheck

-- 1ª definición de pares

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

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

pares1 a b = [(x,y) | x <- [1..b]

, y <- [1..b]

, gcd x y == a

, lcm x y == b]

-- 2ª definición de pares

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

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

pares2 a b = [(x,y) | x <- [a,a+a..b]

, y <- [a,a+a..b]

, gcd x y == a

, lcm x y == b]

-- Comparacioń de eficiencia

-- λ> length (pares1 3 (product [3,5..11]))

-- 16

-- (95.12 secs, 86,534,165,528 bytes)

-- λ> length (pares2 3 (product [3,5..11]))

-- 16

-- (15.80 secs, 14,808,762,128 bytes)

-- 3ª definición de pares

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

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

pares3 a b = [(x,y) | x <- [a,a+a..b]

, c `rem` x == 0

, let y = c `div` x

, gcd x y == a

]

where c = a * b

-- Comparacioń de eficiencia

-- λ> length (pares2 3 (product [3,5..11]))

-- 16

-- (15.80 secs, 14,808,762,128 bytes)

-- λ> length (pares3 3 (product [3,5..11]))

-- 16

-- (0.01 secs, 878,104 bytes)

-- 4ª definición de pares

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

-- Para la cuarta definición de pares se observa la relación con los

-- factores primos

-- λ> [(primeFactors x, primeFactors y) | (x,y) <- pares1 2 12]

-- [([2],[2,2,3]),([2,2],[2,3]),([2,3],[2,2]),([2,2,3],[2])]

-- λ> [primeFactors x | (x,y) <- pares1 2 12]

-- [[2],[2,2],[2,3],[2,2,3]]

-- λ> [primeFactors x | (x,y) <- pares1 2 60]

-- [[2],[2,2],[2,3],[2,5],[2,2,3],[2,2,5],[2,3,5],[2,2,3,5]]

-- λ> [primeFactors x | (x,y) <- pares1 6 60]

-- [[2,3],[2,2,3],[2,3,5],[2,2,3,5]]

-- λ> [primeFactors x | (x,y) <- pares1 2 24]

-- [[2],[2,3],[2,2,2],[2,2,2,3]]

-- Se observa que cada pare se obtiene de uno de los subconjuntos de los

-- divisores primos de b/a. Por ejemplo,

-- λ> (a,b) = (2,24)

-- λ> b `div` a

-- 12

-- λ> primeFactors it

-- [2,2,3]

-- λ> group it

-- [[2,2],[3]]

-- λ> subsequences it

-- [[],[[2,2]],[[3]],[[2,2],[3]]]

-- λ> map concat it

-- [[],[2,2],[3],[2,2,3]]

-- λ> map product it

-- [1,4,3,12]

-- λ> [(a * x, b `div` x) | x <- it]

-- [(2,24),(8,6),(6,8),(24,2)]

-- A partir de la observación se construye la siguiente definición

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

pares4 a b

| b `mod` a /= 0 = []

| otherwise =

[(a * x, b `div` x)

| x <- map (product . concat)

((subsequences . group . primeFactors) (b `div` a))]

-- Nota. La función pares4 calcula el mismo conjunto que las anteriores,

-- pero no necesariamente en el mismo orde. Por ejemplo,

-- λ> pares3 2 60

-- [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]

-- λ> pares4 2 60

-- [(2,60),(4,30),(6,20),(12,10),(10,12),(20,6),(30,4),(60,2)]

-- λ> pares3 2 60 == sort (pares4 2 60)

-- True

-- Comparacioń de eficiencia

-- λ> length (pares3 3 (product [3,5..17]))

-- 64

-- (4.44 secs, 2,389,486,440 bytes)

-- λ> length (pares4 3 (product [3,5..17]))

-- 64

-- (0.00 secs, 177,704 bytes)

-- Propiedades de equivalencia de pares

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

prop_pares :: Integer -> Integer -> Property

prop_pares a b =

a > 0 && b > 0 ==>

all (== pares1 a b)

[sort (f a b) | f <- [ pares2

, pares3

, pares4

]]

prop_pares2 :: Integer -> Integer -> Property

prop_pares2 a b =

a > 0 && b > 0 ==>

all (== pares1 a (a * b))

[sort (f a (a * b)) | f <- [ pares2

, pares3

, pares4

]]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares

-- +++ OK, passed 100 tests.

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares

-- +++ OK, passed 100 tests.

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares2

-- +++ OK, passed 100 tests.

-- 1ª definición de nPares

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

nPares1 :: Integer -> Integer -> Integer

nPares1 a b = genericLength (pares4 a b)

-- 2ª definición de nPares

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

nPares2 :: Integer -> Integer -> Integer

nPares2 a b = 2^(length (nub (primeFactors (b `div` a))))

-- Comparación de eficiencia

-- λ> nPares1 3 (product [3,5..91])

-- 8388608

-- (4.68 secs, 4,178,295,920 bytes)

-- λ> nPares2 3 (product [3,5..91])

-- 8388608

-- (0.00 secs, 234,688 bytes)

-- Propiedad de equivalencia de nPares

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

prop_nPares :: Integer -> Integer -> Property

prop_nPares a b =

a > 0 && b > 0 ==>

nPares1 a (a * b) == nPares2 a (a * b)

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_nPares

-- +++ OK, passed 100 tests.

El problema de las celebridades

PorJosé A. Alonso 9-mayo-201725-abril-2021

La celebridad de una reunión es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reunión hay tres personas tales que la 1 conoce a la 3 y la 2 conoce a la 1 y a la 3, entonces la celebridad de la reunión es la 3.

La relación de conocimiento se puede representar mediante una lista de pares (x,y) indicando que x conoce a y. Por ejemplo, ka reunioń anterior se puede representar por [(1,3),(2,1),(2,3)].

Definir la función

   celebridad :: Ord a => [(a,a)] -> Maybe a

1	celebridad :: Ord a => [(a,a)] -> Maybe a

tal que (celebridad r) es el justo la celebridad de r, si en r hay una celebridad y Nothing, en caso contrario. Por ejemplo,

   celebridad [(1,3),(2,1),(2,3)]            ==  Just 3
   celebridad [(1,3),(2,1),(3,2)]            ==  Nothing
   celebridad [(1,3),(2,1),(2,3),(3,1)]      ==  Nothing
   celebridad [(x,1) | x <- [2..10^6]]       ==  Just 1
   celebridad [(x,10^6) | x <- [1..10^6-1]]  ==  Just 1000000

celebridad [(1,3),(2,1),(2,3)] == Just 3

celebridad [(1,3),(2,1),(3,2)] == Nothing

celebridad [(1,3),(2,1),(2,3),(3,1)] == Nothing

celebridad [(x,1) | x <- [2..10^6]] == Just 1

celebridad [(x,10^6) | x <- [1..10^6-1]] == Just 1000000

Soluciones

[schedule expon=’2017-05-16′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 16 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-16′ at=»06:00″]

import Data.List (delete, nub)
import Data.Maybe (listToMaybe)
import qualified Data.Set as S

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

celebridad1 :: Ord a => [(a,a)] -> Maybe a
celebridad1 r =
  listToMaybe [x | x <- personas r, esCelebridad r x]

personas :: Ord a => [(a,a)] -> [a]
personas r =
  nub (map fst r ++ map snd r)

esCelebridad :: Ord a => [(a,a)] -> a -> Bool
esCelebridad r x =
     [y | y <- ys, (y,x) `elem` r] == ys
  && null [y | y <- ys, (x,y) `elem` r]
  where ys = delete x (personas r)

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

celebridad2 :: Ord a => [(a,a)] -> Maybe a
celebridad2 r =
  listToMaybe [x | x <- personas2 c, esCelebridad2 c x]
  where c = S.fromList r

--    λ> personas2 (S.fromList [(1,3),(2,1),(2,3)])
--    [1,2,3]
personas2 :: Ord a => S.Set (a,a) -> [a]
personas2 c =
  S.toList (S.map fst c `S.union` S.map snd c)

esCelebridad2 :: Ord a => S.Set (a,a) -> a -> Bool
esCelebridad2 c x = 
      [y | y <- ys, (y,x) `S.member` c] == ys
   && null [y | y <- ys, (x,y) `S.member` c]
   where ys = delete x (personas2 c)

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

celebridad3 :: Ord a => [(a,a)] -> Maybe a
celebridad3 r
  | S.null candidatos = Nothing
  | esCelebridad      = Just candidato
  | otherwise         = Nothing
  where
    conjunto          = S.fromList r
    dominio           = S.map fst conjunto
    rango             = S.map snd conjunto
    total             = dominio `S.union` rango
    candidatos        = rango `S.difference` dominio
    candidato         = S.findMin candidatos
    noCandidatos      = S.delete candidato total
    esCelebridad      =
      S.filter (\x -> (x,candidato) `S.member` conjunto) total == noCandidatos
     
-- Comparación de eficiencia
-- =========================

--    λ> celebridad1 [(x,1) | x <- [2..300]]
--    Just 1
--    (2.70 secs, 38,763,888 bytes)
--    λ> celebridad2 [(x,1) | x <- [2..300]]
--    Just 1
--    (0.01 secs, 0 bytes)
-- 
--    λ> celebridad2 [(x,1000) | x <- [1..999]]
--    Just 1000
--    (2.23 secs, 483,704,224 bytes)
--    λ> celebridad3 [(x,1000) | x <- [1..999]]
--    Just 1000
--    (0.02 secs, 0 bytes)
-- 
--    λ> celebridad3 [(x,10^6) | x <- [1..10^6-1]]
--    Just 1000000
--    (9.56 secs, 1,572,841,088 bytes)
--    λ> celebridad3 [(x,1) | x <- [2..10^6]]
--    Just 1
--    (6.17 secs, 696,513,320 bytes)

import Data.List (delete, nub)

import Data.Maybe (listToMaybe)

import qualified Data.Set as S

-- 1ª solución

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

celebridad1 :: Ord a => [(a,a)] -> Maybe a

celebridad1 r =

listToMaybe [x | x <- personas r, esCelebridad r x]

personas :: Ord a => [(a,a)] -> [a]

personas r =

nub (map fst r ++ map snd r)

esCelebridad :: Ord a => [(a,a)] -> a -> Bool

esCelebridad r x =

[y | y <- ys, (y,x) `elem` r] == ys

&& null [y | y <- ys, (x,y) `elem` r]

where ys = delete x (personas r)

-- 2ª solución

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

celebridad2 :: Ord a => [(a,a)] -> Maybe a

celebridad2 r =

listToMaybe [x | x <- personas2 c, esCelebridad2 c x]

where c = S.fromList r

-- λ> personas2 (S.fromList [(1,3),(2,1),(2,3)])

-- [1,2,3]

personas2 :: Ord a => S.Set (a,a) -> [a]

personas2 c =

S.toList (S.map fst c `S.union` S.map snd c)

esCelebridad2 :: Ord a => S.Set (a,a) -> a -> Bool

esCelebridad2 c x =

[y | y <- ys, (y,x) `S.member` c] == ys

&& null [y | y <- ys, (x,y) `S.member` c]

where ys = delete x (personas2 c)

-- 3ª definición

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

celebridad3 :: Ord a => [(a,a)] -> Maybe a

celebridad3 r

| S.null candidatos = Nothing

| esCelebridad = Just candidato

| otherwise = Nothing

where

conjunto = S.fromList r

dominio = S.map fst conjunto

rango = S.map snd conjunto

total = dominio `S.union` rango

candidatos = rango `S.difference` dominio

candidato = S.findMin candidatos

noCandidatos = S.delete candidato total

esCelebridad =

S.filter (\x -> (x,candidato) `S.member` conjunto) total == noCandidatos

-- Comparación de eficiencia

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

-- λ> celebridad1 [(x,1) | x <- [2..300]]

-- Just 1

-- (2.70 secs, 38,763,888 bytes)

-- λ> celebridad2 [(x,1) | x <- [2..300]]

-- Just 1

-- (0.01 secs, 0 bytes)

-- λ> celebridad2 [(x,1000) | x <- [1..999]]

-- Just 1000

-- (2.23 secs, 483,704,224 bytes)

-- λ> celebridad3 [(x,1000) | x <- [1..999]]

-- Just 1000

-- (0.02 secs, 0 bytes)

-- λ> celebridad3 [(x,10^6) | x <- [1..10^6-1]]

-- Just 1000000

-- (9.56 secs, 1,572,841,088 bytes)

-- λ> celebridad3 [(x,1) | x <- [2..10^6]]

-- Just 1

-- (6.17 secs, 696,513,320 bytes)

[/schedule]

Sucesión de Recamán

PorJosé A. Alonso 24-abril-201726-marzo-2022

La sucesión de Recamán está definida como sigue:

   a(0) = 0
   a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
   a(n) = a(n-1) + n, en caso contrario.

a(0) = 0

a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión

a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

   sucRecaman :: [Int]
   invRecaman :: Int -> Int
   graficaSucRecaman :: Int -> IO ()
   graficaInvRecaman :: Int -> IO ()

sucRecaman :: [Int]

invRecaman :: Int -> Int

graficaSucRecaman :: Int -> IO ()

graficaInvRecaman :: Int -> IO ()

tales que

sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,

      λ> take 25 sucRecaman3
      [0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
      λ> sucRecaman !! 1000
      3686
      λ> sucRecaman !! 1000001
      1057163

λ> take 25 sucRecaman3

[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]

λ> sucRecaman !! 1000

3686

λ> sucRecaman !! 1000001

1057163

(invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,

      invRecaman 10       ==  12
      invRecaman 3686     ==  1000
      invRecaman 1057163  ==  1000001

invRecaman 10 == 12

invRecaman 3686 == 1000

invRecaman 1057163 == 1000001

(graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja
(graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja

y (graficaInvRecaman 100) dibuja

Soluciones

import qualified Data.Set as S

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

sucRecaman1 :: [Int]
sucRecaman1 = map suc1 [0..]

suc1 :: Int -> Int
suc1 0 = 0
suc1 n | y > n && y - n `notElem` ys = y - n
       | otherwise                   = y + n
  where y  = suc1 (n - 1)
        ys = [suc1 k | k <- [0..n - 1]]

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

sucRecaman2 :: [Int]
sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)
  where f y n ys | y > n && y - n `notElem` take n ys = y - n
                 | otherwise                          = y + n

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

sucRecaman3 :: [Int]
sucRecaman3 = 0 : recaman (S.singleton 0) 1 0

recaman :: S.Set Int -> Int -> Int -> [Int]
recaman s n x
  | x > n && (x-n) `S.notMember` s =
    (x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)
  | otherwise =
    (x+n):recaman (S.insert (x+n) s) (n+1) (x+n) 

-- Comparación de eficiencia:
--    λ> sucRecaman1 !! 25
--    17
--    (3.76 secs, 2,394,593,952 bytes)
--    λ> sucRecaman2 !! 25
--    17
--    (0.00 secs, 0 bytes)
--    λ> sucRecaman3 !! 25
--    17
--    (0.00 secs, 0 bytes)
--
--    λ> sucRecaman2 !! (2*10^4)
--    14358
--    (2.69 secs, 6,927,559,784 bytes)
--    λ> sucRecaman3 !! (2*10^4)
--    14358
--    (0.04 secs, 0 bytes)

-- Definición de invRecaman
invRecaman :: Int -> Int
invRecaman n =
  length (takeWhile (/=n) sucRecaman3)

graficaSucRecaman :: Int -> IO ()
graficaSucRecaman n =
  plotList [Key Nothing]
           (take n sucRecaman3)

graficaInvRecaman :: Int -> IO ()
graficaInvRecaman n =
  plotList [Key Nothing]
           [invRecaman k | k <- [0..n]]

import qualified Data.Set as S

-- 1ª solución

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

sucRecaman1 :: [Int]

sucRecaman1 = map suc1 [0..]

suc1 :: Int -> Int

suc1 0 = 0

suc1 n | y > n && y - n `notElem` ys = y - n

| otherwise = y + n

where y = suc1 (n - 1)

ys = [suc1 k | k <- [0..n - 1]]

-- 2ª solución

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

sucRecaman2 :: [Int]

sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)

where f y n ys | y > n && y - n `notElem` take n ys = y - n

| otherwise = y + n

-- 3ª solución

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

sucRecaman3 :: [Int]

sucRecaman3 = 0 : recaman (S.singleton 0) 1 0

recaman :: S.Set Int -> Int -> Int -> [Int]

recaman s n x

| x > n && (x-n) `S.notMember` s =

(x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)

| otherwise =

(x+n):recaman (S.insert (x+n) s) (n+1) (x+n)

-- Comparación de eficiencia:

-- λ> sucRecaman1 !! 25

-- 17

-- (3.76 secs, 2,394,593,952 bytes)

-- λ> sucRecaman2 !! 25

-- 17

-- (0.00 secs, 0 bytes)

-- λ> sucRecaman3 !! 25

-- 17

-- (0.00 secs, 0 bytes)

-- λ> sucRecaman2 !! (2*10^4)

-- 14358

-- (2.69 secs, 6,927,559,784 bytes)

-- λ> sucRecaman3 !! (2*10^4)

-- 14358

-- (0.04 secs, 0 bytes)

-- Definición de invRecaman

invRecaman :: Int -> Int

invRecaman n =

length (takeWhile (/=n) sucRecaman3)

graficaSucRecaman :: Int -> IO ()

graficaSucRecaman n =

plotList [Key Nothing]

(take n sucRecaman3)

graficaInvRecaman :: Int -> IO ()

graficaInvRecaman n =

plotList [Key Nothing]

[invRecaman k | k <- [0..n]]

Operaciones con series de potencias

PorJosé A. Alonso 21-abril-201725-marzo-2022

Una serie de potencias es una serie de la forma

   a₀ + a₁x + a₂x² + a₃x³ + ...

1	a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

   e^x = 1 + x + x²/2! + x³/3! + ...

1	e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

   type Serie a = [a]

1	type Serie a = [a]

Definir las siguientes funciones

   opuesta      :: Num a => Serie a -> Serie a
   suma         :: Num a => Serie a -> Serie a -> Serie a
   resta        :: Num a => Serie a -> Serie a -> Serie a
   producto     :: Num a => Serie a -> Serie a -> Serie a
   cociente     :: Fractional a => Serie a -> Serie a -> Serie a
   derivada     :: (Num a, Enum a) => Serie a -> Serie a
   integral     :: (Fractional a, Enum a) => Serie a -> Serie a
   expx         :: Serie Rational

opuesta :: Num a => Serie a -> Serie a

suma :: Num a => Serie a -> Serie a -> Serie a

resta :: Num a => Serie a -> Serie a -> Serie a

producto :: Num a => Serie a -> Serie a -> Serie a

cociente :: Fractional a => Serie a -> Serie a -> Serie a

derivada :: (Num a, Enum a) => Serie a -> Serie a

integral :: (Fractional a, Enum a) => Serie a -> Serie a

expx :: Serie Rational

tales que

(opuesta xs) es la opuesta de la serie xs. Por ejemplo,

     λ> take 7 (opuesta [-6,-4..])
     [6,4,2,0,-2,-4,-6]

1 2	λ> take 7 (opuesta [-6,-4..]) [6,4,2,0,-2,-4,-6]

(suma xs ys) es la suma de las series xs e ys. Por ejemplo,

     λ> take 7 (suma [1,3..] [2,4..])
     [3,7,11,15,19,23,27]

1 2	λ> take 7 (suma [1,3..] [2,4..]) [3,7,11,15,19,23,27]

(resta xs ys) es la resta de las series xs es ys. Por ejemplo,

     λ> take 7 (resta [3,5..] [2,4..])
     [1,1,1,1,1,1,1]
     λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
     [2,4,6,8,10,12,14]

λ> take 7 (resta [3,5..] [2,4..])

[1,1,1,1,1,1,1]

λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])

[2,4,6,8,10,12,14]

(producto xs ys) es el producto de las series xs e ys. Por ejemplo,

     λ> take 7 (producto [3,5..] [2,4..])
     [6,22,52,100,170,266,392]

1 2	λ> take 7 (producto [3,5..] [2,4..]) [6,22,52,100,170,266,392]

(cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

     λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
     [2.0,4.0,6.0,8.0,10.0,12.0,14.0]

1 2	λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..]) [2.0,4.0,6.0,8.0,10.0,12.0,14.0]

(derivada xs) es la derivada de la serie xs. Por ejemplo,

     λ> take 7 (derivada [2,4..])
     [4,12,24,40,60,84,112]

1 2	λ> take 7 (derivada [2,4..]) [4,12,24,40,60,84,112]

(integral xs) es la integral de la serie xs. Por ejemplo,

     λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
     [0.0,4.0,6.0,8.0,10.0,12.0,14.0]

1 2	λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0)) [0.0,4.0,6.0,8.0,10.0,12.0,14.0]

expx es la serie de la función exponencial. Por ejemplo,

     λ> take 8 expx
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (derivada expx)
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (integral expx)
     [0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

λ> take 8 expx

[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

λ> take 8 (derivada expx)

[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

λ> take 8 (integral expx)

[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Soluciones

type Serie a = [a] 

opuesta :: Num a => Serie a -> Serie a
opuesta = map negate

suma :: Num a => Serie a -> Serie a -> Serie a
suma = zipWith (+)

resta :: Num a => Serie a -> Serie a -> Serie a
resta xs ys = suma xs (opuesta ys)

producto :: Num a => Serie a -> Serie a -> Serie a
producto (x:xs) zs@(y:ys) = 
    x*y : suma (producto xs zs) (map (x*) ys)

cociente :: Fractional a => Serie a -> Serie a -> Serie a
cociente (x:xs) (y:ys) = zs 
    where zs = x/y : map (/y) (resta xs (producto zs ys))  

derivada :: (Num a, Enum a) => Serie a -> Serie a
derivada (_:xs) = zipWith (*) xs [1..]

integral :: (Fractional a, Enum a) => Serie a -> Serie a
integral xs = 0 : zipWith (/) xs [1..]

expx :: Serie Rational
expx = map (1/) (map fromIntegral factoriales)

-- factoriales es la lista de los factoriales. Por ejemplo, 
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

type Serie a = [a]

opuesta :: Num a => Serie a -> Serie a

opuesta = map negate

suma :: Num a => Serie a -> Serie a -> Serie a

suma = zipWith (+)

resta :: Num a => Serie a -> Serie a -> Serie a

resta xs ys = suma xs (opuesta ys)

producto :: Num a => Serie a -> Serie a -> Serie a

producto (x:xs) zs@(y:ys) =

x*y : suma (producto xs zs) (map (x*) ys)

cociente :: Fractional a => Serie a -> Serie a -> Serie a

cociente (x:xs) (y:ys) = zs

where zs = x/y : map (/y) (resta xs (producto zs ys))

derivada :: (Num a, Enum a) => Serie a -> Serie a

derivada (_:xs) = zipWith (*) xs [1..]

integral :: (Fractional a, Enum a) => Serie a -> Serie a

integral xs = 0 : zipWith (/) xs [1..]

expx :: Serie Rational

expx = map (1/) (map fromIntegral factoriales)

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

-- take 7 factoriales == [1,1,2,6,24,120,720]

factoriales :: [Integer]

factoriales = 1 : scanl1 (*) [1..]

Elementos con su doble en el conjunto

PorJosé A. Alonso 17-abril-201724-abril-2017

Definir la función

   conDoble :: [Int] -> [Int]

1	conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

   conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
   conDoble [2, 4, 8, 10]               ==  [2,4]
   conDoble [7, 5, 11, 13, 1, 3]        ==  []
   length (conDoble4 [1..10^6])         ==  500000

conDoble [1, 4, 3, 2, 9, 7, 18, 22] == [1,2,9]

conDoble [2, 4, 8, 10] == [2,4]

conDoble [7, 5, 11, 13, 1, 3] == []

length (conDoble4 [1..10^6]) == 500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Soluciones

import Data.List (intersect, sort)
import qualified Data.Set as S

-- 1ª Definición
conDoble :: [Int] -> [Int]
conDoble xs =
  [x | x <- xs, 2 * x `elem` xs]

-- 2ª Definición
conDoble2 :: [Int] -> [Int]
conDoble2 xs = aux (sort xs)
  where aux [] = []
        aux (y:ys) | 2 * y `elem` xs = y : aux ys
                   | otherwise       = aux ys

-- 3ª definición
conDoble3 :: [Int] -> [Int]
conDoble3 xs =
  sort (map (`div` 2) (xs `intersect` (map (*2) xs)))

-- 4ª definición
conDoble4 :: [Int] -> [Int]
conDoble4 xs =
  S.toList (S.map (`div` 2) (ys `S.intersection` (S.map (*2) ys)))
  where ys = S.fromList xs

-- Comparación de eficiencia
--    λ> length (conDoble [1..10^4])
--    5000
--    (3.27 secs, 0 bytes)
--    λ> length (conDoble2 [1..10^4])
--    5000
--    (3.42 secs, 0 bytes)
--    λ> length (conDoble3 [1..10^4])
--    5000
--    (4.78 secs, 0 bytes)
--    λ> length (conDoble4 [1..10^4])
--    5000
--    (0.02 secs, 0 bytes)

import Data.List (intersect, sort)

import qualified Data.Set as S

-- 1ª Definición

conDoble :: [Int] -> [Int]

conDoble xs =

[x | x <- xs, 2 * x `elem` xs]

-- 2ª Definición

conDoble2 :: [Int] -> [Int]

conDoble2 xs = aux (sort xs)

where aux [] = []

aux (y:ys) | 2 * y `elem` xs = y : aux ys

| otherwise = aux ys

-- 3ª definición

conDoble3 :: [Int] -> [Int]

conDoble3 xs =

sort (map (`div` 2) (xs `intersect` (map (*2) xs)))

-- 4ª definición

conDoble4 :: [Int] -> [Int]

conDoble4 xs =

S.toList (S.map (`div` 2) (ys `S.intersection` (S.map (*2) ys)))

where ys = S.fromList xs

-- Comparación de eficiencia

-- λ> length (conDoble [1..10^4])

-- 5000

-- (3.27 secs, 0 bytes)

-- λ> length (conDoble2 [1..10^4])

-- 5000

-- (3.42 secs, 0 bytes)

-- λ> length (conDoble3 [1..10^4])

-- 5000

-- (4.78 secs, 0 bytes)

-- λ> length (conDoble4 [1..10^4])

-- 5000

-- (0.02 secs, 0 bytes)

Ampliación de una matriz

PorJosé A. Alonso 12-abril-201720-abril-2017

Definir, usando Data.Matrix, la función

   ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

1	ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

   ej1 :: Matrix Char
   ej1 = fromLists [" x ",
                    "x x",
                    " x "]

ej1 :: Matrix Char

ej1 = fromLists [" x ",

"x x",

" x "]

entonces

   λ> ampliaMatriz ej1 1 2
   ( ' ' ' ' 'x' 'x' ' ' ' ' )
   ( 'x' 'x' ' ' ' ' 'x' 'x' )
   ( ' ' ' ' 'x' 'x' ' ' ' ' )
   
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)
     xx  
   xx  xx
     xx  
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)
    x 
    x 
   x x
   x x
    x 
    x 
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)
     xx  
     xx  
   xx  xx
   xx  xx
     xx  
     xx  
   λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)
      xxx   
      xxx   
   xxx   xxx
   xxx   xxx
      xxx   
      xxx

λ> ampliaMatriz ej1 1 2

( ' ' ' ' 'x' 'x' ' ' ' ' )

( 'x' 'x' ' ' ' ' 'x' 'x' )

( ' ' ' ' 'x' 'x' ' ' ' ' )

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)

xx xx

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)

x x

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)

xx xx

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)

xxx

xxx xxx

xxx

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Soluciones

import Data.Matrix

ej1 :: Matrix Char
ej1 = fromLists [" x ",
                 "x x",
                 " x "]

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

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz p f c =
  ampliaColumnas (ampliaFilas p f) c

ampliaFilas :: Matrix a -> Int -> Matrix a
ampliaFilas p f =
  matrix (f*m) n (\(i,j) -> p!(1 + (i-1) `div` f, j))
  where m = nrows p
        n = ncols p

ampliaColumnas :: Matrix a -> Int -> Matrix a
ampliaColumnas p c =
  matrix m (c*n) (\(i,j) -> p!(i,1 + (j-1) `div` c))
  where m = nrows p
        n = ncols p

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

ampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz2 p f c =
  ampliaColumnas2 (ampliaFilas2 p f) c

ampliaFilas2 :: Matrix a -> Int -> Matrix a
ampliaFilas2 p f =
  fromLists (concatMap (replicate f) (toLists p))

ampliaColumnas2 :: Matrix a -> Int -> Matrix a
ampliaColumnas2 p c =
  fromLists (map (concatMap (replicate c)) (toLists p))

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

ampliaMatriz3 :: Matrix a -> Int -> Int -> Matrix a
ampliaMatriz3 p f c =
  ( fromLists
  . concatMap (map (concatMap (replicate c)) . replicate f)
  . toLists) p

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

ejemplo :: Int -> Matrix Int
ejemplo n = fromList n n [1..]

--    λ> maximum (ampliaMatriz (ejemplo 10) 100 200)
--    100
--    (6.64 secs, 1,026,559,296 bytes)
--    λ> maximum (ampliaMatriz2 (ejemplo 10) 100 200)
--    100
--    (1.90 secs, 513,211,144 bytes)
--    λ> maximum (ampliaMatriz3 (ejemplo 10) 100 200)
--    100
--    (1.89 secs, 644,928,024 bytes)
--    λ> maximum (ampliaMatriz2 (ejemplo 10) 200 200)
--    100
--    (5.13 secs, 1,248,173,384 bytes)
--    λ> maximum (ampliaMatriz3 (ejemplo 10) 200 200)
--    100
--    (4.67 secs, 1,431,540,344 bytes)

import Data.Matrix

ej1 :: Matrix Char

ej1 = fromLists [" x ",

"x x",

" x "]

-- 1ª definición

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

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz p f c =

ampliaColumnas (ampliaFilas p f) c

ampliaFilas :: Matrix a -> Int -> Matrix a

ampliaFilas p f =

matrix (f*m) n (\(i,j) -> p!(1 + (i-1) `div` f, j))

where m = nrows p

n = ncols p

ampliaColumnas :: Matrix a -> Int -> Matrix a

ampliaColumnas p c =

matrix m (c*n) (\(i,j) -> p!(i,1 + (j-1) `div` c))

where m = nrows p

n = ncols p

-- 2ª definición

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

ampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz2 p f c =

ampliaColumnas2 (ampliaFilas2 p f) c

ampliaFilas2 :: Matrix a -> Int -> Matrix a

ampliaFilas2 p f =

fromLists (concatMap (replicate f) (toLists p))

ampliaColumnas2 :: Matrix a -> Int -> Matrix a

ampliaColumnas2 p c =

fromLists (map (concatMap (replicate c)) (toLists p))

-- 3ª definición

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

ampliaMatriz3 :: Matrix a -> Int -> Int -> Matrix a

ampliaMatriz3 p f c =

( fromLists

. concatMap (map (concatMap (replicate c)) . replicate f)

. toLists) p

-- Comparación de eficiencia

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

ejemplo :: Int -> Matrix Int

ejemplo n = fromList n n [1..]

-- λ> maximum (ampliaMatriz (ejemplo 10) 100 200)

-- 100

-- (6.64 secs, 1,026,559,296 bytes)

-- λ> maximum (ampliaMatriz2 (ejemplo 10) 100 200)

-- 100

-- (1.90 secs, 513,211,144 bytes)

-- λ> maximum (ampliaMatriz3 (ejemplo 10) 100 200)

-- 100

-- (1.89 secs, 644,928,024 bytes)

-- λ> maximum (ampliaMatriz2 (ejemplo 10) 200 200)

-- 100

-- (5.13 secs, 1,248,173,384 bytes)

-- λ> maximum (ampliaMatriz3 (ejemplo 10) 200 200)

-- 100

-- (4.67 secs, 1,431,540,344 bytes)

Problema de las jarras

PorJosé A. Alonso 11-abril-201725-abril-2021

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

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

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

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

   λ> jarras (5,3,4)
   Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]

1 2	λ> jarras (5,3,4) Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]

La interpretación de la solución anterior es

   (0,0) se inicia con las dos jarras vacías,
   (5,0) se llena la jarra de 5 con el grifo,
   (2,3) se llena la de 3 con la de 5,
   (2,0) se vacía la de 3,
   (0,2) se pasa el contenido de la primera a la segunda,
   (5,2) se llena la primera con el grifo,
   (4,3) se llena la segunda con la primera.

(0,0) se inicia con las dos jarras vacías,

(5,0) se llena la jarra de 5 con el grifo,

(2,3) se llena la de 3 con la de 5,

(2,0) se vacía la de 3,

(0,2) se pasa el contenido de la primera a la segunda,

(5,2) se llena la primera con el grifo,

(4,3) se llena la segunda con la primera.

Otros ejemplos:

   λ> jarras (3,5,4)
   Just [(0,0),(0,5),(3,2),(0,2),(2,0),(2,5),(3,4)]
   λ> jarras (15,10,5)
   Just [(0,0),(15,0),(5,10)]
   λ> jarras (15,10,4)
   Nothing
   λ> length <$> jarras (181,179,100)
   Just 199

λ> jarras (3,5,4)

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

λ> jarras (15,10,5)

Just [(0,0),(15,0),(5,10)]

λ> jarras (15,10,4)

Nothing

λ> length <$> jarras (181,179,100)

Just 199

Soluciones

import Data.Maybe (listToMaybe, isJust)

-- Para simplificar la notación se definen los tipos Problema y Estado
-- como sigue.

-- Un problema es una terna de números. El primero es la capacidad de la
-- primera jarra, el segundo el de la segunda y el tercero es el número
-- de litros que hay que obtener.
type Problema = (Int,Int,Int)

-- Un estado es un par de números. El primero es el contenido de la
-- jarra de A litros y el segundo el de la de B litros.  
type Estado = (Int,Int)

jarras :: Problema -> Maybe [Estado]
jarras p | null ns   = Nothing
         | otherwise = Just (head ns)
  where ns = soluciones p

-- (soluciones p) es la lista de soluciones del problema p. Por ejemplo, 
--    λ> take 2 (soluciones (15,10,5))
--    [[(0,0),(15,0),(5,10)],[(0,0),(0,10),(15,10),(15,0),(5,10)]]
--    λ> length (soluciones (15,10,5))
--    6
--    λ> soluciones (15,10,4)
--    []
soluciones :: Problema -> [[Estado]]
soluciones p = busca [[inicial]]
  where
    busca []        = []
    busca ((e:es):ns)  
      | esFinal p e = (reverse (e:es)) : busca ns
      | otherwise   = busca (ns ++ [e1:e:es | e1 <- sucesores p e
                                            , e1 `notElem` es])

-- inicial es el estado inicial
inicial :: Estado
inicial = (0,0)

-- (esFinal p e) es verifica si e es un estado final del problema de las
-- jarras p. Por ejemplo,
--    esFinal (5,4,3) (3,2)  ==  True
--    esFinal (5,4,3) (2,3)  ==  True
--    esFinal (5,4,1) (2,3)  ==  False
esFinal :: Problema -> Estado -> Bool
esFinal (_,_,c) (x,y) = x == c || y == c

-- (sucesores p e) es la lista de los sucesores del estado e. Por
-- ejemplo, 
--    λ> sucesores (7,4,3) (1,2)
--    [(7,2),(1,4),(0,2),(1,0),(3,0),(0,3)]
--    λ> sucesores (7,4,3) (6,3)
--    [(7,3),(6,4),(0,3),(6,0),(7,2),(5,4)]
sucesores :: Problema -> Estado -> [Estado]
sucesores (a,b,_) (x,y) =
    [(a,y) | x < a] ++
    [(x,b) | y < b] ++
    [(0,y) | x > 0] ++
    [(x,0) | y > 0] ++
    [(a,y-(a-x)) | x < a, y > a - x] ++
    [(x-(b-y),b) | y < b, x > b - y] ++
    [(x+y,0) | y > 0, x + y <= a] ++ 
    [(0,x+y) | x > 0, x + y <= b]

-- La definición de jarras se puede simplificar usando listToMaybe
jarras2 :: Problema -> Maybe [Estado]
jarras2 p = listToMaybe (soluciones p)

import Data.Maybe (listToMaybe, isJust)

-- Para simplificar la notación se definen los tipos Problema y Estado

-- como sigue.

-- Un problema es una terna de números. El primero es la capacidad de la

-- primera jarra, el segundo el de la segunda y el tercero es el número

-- de litros que hay que obtener.

type Problema = (Int,Int,Int)

-- Un estado es un par de números. El primero es el contenido de la

-- jarra de A litros y el segundo el de la de B litros.

type Estado = (Int,Int)

jarras :: Problema -> Maybe [Estado]

jarras p | null ns = Nothing

| otherwise = Just (head ns)

where ns = soluciones p

-- (soluciones p) es la lista de soluciones del problema p. Por ejemplo,

-- λ> take 2 (soluciones (15,10,5))

-- [[(0,0),(15,0),(5,10)],[(0,0),(0,10),(15,10),(15,0),(5,10)]]

-- λ> length (soluciones (15,10,5))

-- 6

-- λ> soluciones (15,10,4)

-- []

soluciones :: Problema -> [[Estado]]

soluciones p = busca [[inicial]]

where

busca [] = []

busca ((e:es):ns)

| esFinal p e = (reverse (e:es)) : busca ns

| otherwise = busca (ns ++ [e1:e:es | e1 <- sucesores p e

, e1 `notElem` es])

-- inicial es el estado inicial

inicial :: Estado

inicial = (0,0)

-- (esFinal p e) es verifica si e es un estado final del problema de las

-- jarras p. Por ejemplo,

-- esFinal (5,4,3) (3,2) == True

-- esFinal (5,4,3) (2,3) == True

-- esFinal (5,4,1) (2,3) == False

esFinal :: Problema -> Estado -> Bool

esFinal (_,_,c) (x,y) = x == c || y == c

-- (sucesores p e) es la lista de los sucesores del estado e. Por

-- ejemplo,

-- λ> sucesores (7,4,3) (1,2)

-- [(7,2),(1,4),(0,2),(1,0),(3,0),(0,3)]

-- λ> sucesores (7,4,3) (6,3)

-- [(7,3),(6,4),(0,3),(6,0),(7,2),(5,4)]

sucesores :: Problema -> Estado -> [Estado]

sucesores (a,b,_) (x,y) =

[(a,y) | x < a] ++

[(x,b) | y < b] ++

[(0,y) | x > 0] ++

[(x,0) | y > 0] ++

[(a,y-(a-x)) | x < a, y > a - x] ++

[(x-(b-y),b) | y < b, x > b - y] ++

[(x+y,0) | y > 0, x + y <= a] ++

[(0,x+y) | x > 0, x + y <= b]

-- La definición de jarras se puede simplificar usando listToMaybe

jarras2 :: Problema -> Maybe [Estado]

jarras2 p = listToMaybe (soluciones p)

Distancias entre primos consecutivos

PorJosé A. Alonso 4-abril-201711-abril-2017

Los 15 primeros números primos son

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

   1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

1	1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4

La distribución de las distancias es

   (1,1), (2,6), (4,5), (6,2)

1	(1,1), (2,6), (4,5), (6,2)

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

   (1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

1	(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

  cuentaDistancias        :: Int -> [(Int,Int)]
  frecuenciasDistancias   :: Int -> [(Int,Float)]
  graficas                :: [Int] -> IO ()
  distanciasMasFrecuentes :: Int -> [Int]

cuentaDistancias :: Int -> [(Int,Int)]

frecuenciasDistancias :: Int -> [(Int,Float)]

graficas :: [Int] -> IO ()

distanciasMasFrecuentes :: Int -> [Int]

tales que

(cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> cuentaDistancias 15
     [(1,1),(2,6),(4,5),(6,2)]
     λ> cuentaDistancias 100
     [(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

λ> cuentaDistancias 15

[(1,1),(2,6),(4,5),(6,2)]

λ> cuentaDistancias 100

[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

(frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> frecuenciasDistancias 15
     [(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
     λ> frecuenciasDistancias 30
     [(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

λ> frecuenciasDistancias 15

[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]

λ> frecuenciasDistancias 30

[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

(graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

(graficas [1000,2000,3000]) dibuja

y (graficas [100000,200000,300000]) dibuja
(distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,

     distanciasMasFrecuentes 15     ==  [2]
     distanciasMasFrecuentes 26     ==  [2,4]
     distanciasMasFrecuentes 32     ==  [4]
     distanciasMasFrecuentes 41     ==  [2,4,6]
     distanciasMasFrecuentes 77     ==  [6]
     distanciasMasFrecuentes 160    ==  [4,6]
     distanciasMasFrecuentes (10^6) == [6]

distanciasMasFrecuentes 15 == [2]

distanciasMasFrecuentes 26 == [2,4]

distanciasMasFrecuentes 32 == [4]

distanciasMasFrecuentes 41 == [2,4,6]

distanciasMasFrecuentes 77 == [6]

distanciasMasFrecuentes 160 == [4,6]

distanciasMasFrecuentes (10^6) == [6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Soluciones

import Data.Numbers.Primes
import qualified Data.Map as M 
import Graphics.Gnuplot.Simple
import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]
cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int
dicDistancias n =
  M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]
distancias n =
  zipWith (-) (tail xs) xs
  where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]
frecuenciasDistancias n =
  [(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]
  where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()
graficas ns =
  plotLists [Key Nothing]
            (map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]
distanciasMasFrecuentes n =
  M.keys (M.filter (==m) d)
  where d = dicDistancias n
        m = maximum (M.elems d)

-- La propiedad es
prop_distanciasMasFrecuentes :: Int -> Bool
prop_distanciasMasFrecuentes n =
  distanciasMasFrecuentes (161 + abs n) == [6]

import Data.Numbers.Primes

import qualified Data.Map as M

import Graphics.Gnuplot.Simple

import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]

cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int

dicDistancias n =

M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]

distancias n =

zipWith (-) (tail xs) xs

where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]

frecuenciasDistancias n =

[(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]

where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()

graficas ns =

plotLists [Key Nothing]

(map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]

distanciasMasFrecuentes n =

M.keys (M.filter (==m) d)

where d = dicDistancias n

m = maximum (M.elems d)

-- La propiedad es

prop_distanciasMasFrecuentes :: Int -> Bool

prop_distanciasMasFrecuentes n =

distanciasMasFrecuentes (161 + abs n) == [6]

Rotaciones divisibles por 4

PorJosé A. Alonso 3-abril-201710-abril-2017

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816. De las cuales, las divisibles por 4 son 928160, 816092, 160928 y 92816.

Definir la función

   nRotacionesDivisibles :: Integer -> Int

1	nRotacionesDivisibles :: Integer -> Int

tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,

   nRotacionesDivisibles 928160          ==  4
   nRotacionesDivisibles 44              ==  2
   nRotacionesDivisibles (1234^50000)    ==  38684
   nRotacionesDivisibles (1234^300000)   ==  231853

nRotacionesDivisibles 928160 == 4

nRotacionesDivisibles 44 == 2

nRotacionesDivisibles (1234^50000) == 38684

nRotacionesDivisibles (1234^300000) == 231853

Soluciones

import Data.Char (digitToInt)

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

nRotacionesDivisibles :: Integer -> Int
nRotacionesDivisibles n =
  length [x | x <- rotacionesNumero n, x `mod` 4 == 0]


-- (rotacionesNumero) es la lista de la rotaciones del número n. Por
-- ejemplo,
--    rotacionesNumero 235  ==  [235,352,523]
rotacionesNumero :: Integer -> [Integer]
rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando
-- el primer elemento xs al final. Por ejemplo,
--    rotaciones [2,3,5]  ==  [[2,3,5],[3,5,2],[5,2,3]]
rotaciones :: [a] -> [[a]]
rotaciones xs = take (length xs) (iterate rota xs)

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

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

nRotacionesDivisibles2 :: Integer -> Int
nRotacionesDivisibles2 n = 
  length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo
-- el último con el primero. Por ejemplo,
--    pares 928160  ==  [9,92,28,81,16,60]
pares :: Integer -> [Int]
pares n =
  read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]
  where ns = show n

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

nRotacionesDivisibles3 :: Integer -> Int
nRotacionesDivisibles3 n =
  ( length
  . filter (0 ==)
  . map (`mod` 4)
  . zipWith (\x y -> 2*x + y) d
  . tail
  . (++[i])) d
  where
    d@(i:dn) = (map digitToInt . show) n

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

--    λ> nRotacionesDivisibles (123^1500)
--    803
--    (8.15 secs, 7,109,852,800 bytes)
--    λ> nRotacionesDivisibles2 (123^1500)
--    803
--    (0.05 secs, 0 bytes)
--    λ> nRotacionesDivisibles3 (123^1500)
--    803
--    (0.02 secs, 0 bytes)
--
--    λ> nRotacionesDivisibles2 (1234^50000)
--    38684
--    (2.24 secs, 1,160,467,472 bytes)
--    λ> nRotacionesDivisibles3 (1234^50000)
--    38684
--    (0.31 secs, 68,252,040 bytes)

import Data.Char (digitToInt)

-- 1ª definición

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

nRotacionesDivisibles :: Integer -> Int

nRotacionesDivisibles n =

length [x | x <- rotacionesNumero n, x `mod` 4 == 0]

-- (rotacionesNumero) es la lista de la rotaciones del número n. Por

-- ejemplo,

-- rotacionesNumero 235 == [235,352,523]

rotacionesNumero :: Integer -> [Integer]

rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando

-- el primer elemento xs al final. Por ejemplo,

-- rotaciones [2,3,5] == [[2,3,5],[3,5,2],[5,2,3]]

rotaciones :: [a] -> [[a]]

rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al

-- final. Por ejemplo,

-- rota [3,2,5,7] == [2,5,7,3]

rota :: [a] -> [a]

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

-- 2ª definición

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

nRotacionesDivisibles2 :: Integer -> Int

nRotacionesDivisibles2 n =

length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo

-- el último con el primero. Por ejemplo,

-- pares 928160 == [9,92,28,81,16,60]

pares :: Integer -> [Int]

pares n =

read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]

where ns = show n

-- 3ª definición

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

nRotacionesDivisibles3 :: Integer -> Int

nRotacionesDivisibles3 n =

( length

. filter (0 ==)

. map (`mod` 4)

. zipWith (\x y -> 2*x + y) d

. tail

. (++[i])) d

where

d@(i:dn) = (map digitToInt . show) n

-- Comparación de eficiencia

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

-- λ> nRotacionesDivisibles (123^1500)

-- 803

-- (8.15 secs, 7,109,852,800 bytes)

-- λ> nRotacionesDivisibles2 (123^1500)

-- 803

-- (0.05 secs, 0 bytes)

-- λ> nRotacionesDivisibles3 (123^1500)

-- 803

-- (0.02 secs, 0 bytes)

-- λ> nRotacionesDivisibles2 (1234^50000)

-- 38684

-- (2.24 secs, 1,160,467,472 bytes)

-- λ> nRotacionesDivisibles3 (1234^50000)

-- 38684

-- (0.31 secs, 68,252,040 bytes)

Sumas con sumandos distintos o con sumandos impares

PorJosé A. Alonso 30-marzo-20176-abril-2017

El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:

   6 = 1 + 2 + 3
   6 = 1 + 5
   6 = 2 + 4
   6 = 6

6 = 1 + 2 + 3

6 = 1 + 5

6 = 2 + 4

6 = 6

y también se puede descomponer de 4 formas distintas como suma con sumandos impares:

   6 = 1 + 1 + 1 + 1 + 1 + 1
   6 = 1 + 1 + 1 + 3
   6 = 1 + 5
   6 = 3 + 3

6 = 1 + 1 + 1 + 1 + 1 + 1

6 = 1 + 1 + 1 + 3

6 = 1 + 5

6 = 3 + 3

Definir las siguientes funciones

   sumasSumandosDistintos  :: Integer -> [[Integer]]
   nSumasSumandosDistintos :: Integer -> Int
   sumasSumandosImpares    :: Integer -> [[Integer]]
   nSumasSumandosImpares   :: Integer -> Int
   igualdadDeSumas         :: Integer -> Bool

sumasSumandosDistintos :: Integer -> [[Integer]]

nSumasSumandosDistintos :: Integer -> Int

sumasSumandosImpares :: Integer -> [[Integer]]

nSumasSumandosImpares :: Integer -> Int

igualdadDeSumas :: Integer -> Bool

tales que

(sumasSumandosDistintos n) es la lista de las descomposiciones de n como sumas con sumandos distintos. Por ejemplo,

     sumasSumandosDistintos 5  ==  [[1,4],[2,3],[5]]
     sumasSumandosDistintos 6  ==  [[1,2,3],[1,5],[2,4],[6]]

1 2	sumasSumandosDistintos 5 == [[1,4],[2,3],[5]] sumasSumandosDistintos 6 == [[1,2,3],[1,5],[2,4],[6]]

(nSumasSumandosDistintos n) es el número de descomposiciones de n como sumas con sumandos distintos. Por ejemplo,

     nSumasSumandosDistintos 6  ==  4
     nSumasSumandosDistintos 7  ==  5

1 2	nSumasSumandosDistintos 6 == 4 nSumasSumandosDistintos 7 == 5

(sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,

     sumasSumandosImpares 5  ==  [[1,1,1,1,1],[1,1,3],[5]]
     sumasSumandosImpares 6  ==  [[1,1,1,1,1,1],[1,1,1,3],[1,5],[3,3]]

1 2	sumasSumandosImpares 5 == [[1,1,1,1,1],[1,1,3],[5]] sumasSumandosImpares 6 == [[1,1,1,1,1,1],[1,1,1,3],[1,5],[3,3]]

(nSumasSumandosImpares n) es el número de descomposiciones de n como sumas con sumandos impares. Por ejemplo,

     nSumasSumandosImpares 6  ==  4
     nSumasSumandosImpares 7  ==  5

1 2	nSumasSumandosImpares 6 == 4 nSumasSumandosImpares 7 == 5

(igualdadDeSumas n) se verifica si, para todo k entre 1 y n, las funciones nSumasSumandosDistintos y nSumasSumandosImpares son iguales. Por ejemplo,

     igualdadDeSumas 40  ==  True

1	igualdadDeSumas 40 == True

Soluciones

import Data.List (delete, nub)

-- Definiciones de sumasSumandosDistintos
-- ======================================

-- 1ª definición sumasSumandosDistintos
sumasSumandosDistintos :: Integer -> [[Integer]]
sumasSumandosDistintos n = aux n [1..n]
  where aux 0 _ = [[]]
        aux _ [] = []
        aux x ys@(y:_)
          | x < y     = []
          | x == y    = [[x]]
          | otherwise = [z : zs | z <- ys
                                , zs <- aux (x - z) (dropWhile (<=z) ys)]

-- 2ª definición de sumasSumandosDistintos
sumasSumandosDistintos2 :: Integer ->[[Integer]]
sumasSumandosDistintos2 = aux 0
  where aux i z
          | z < 0  = []
          | z == 0 = [[]]
          | z > 0  = concat [map (j:) (aux j (z-j)) | j <- [i+1..z]]

-- Definición de nSumasSumandosDistintos
-- =====================================

nSumasSumandosDistintos :: Integer -> Int
nSumasSumandosDistintos =
  length . sumasSumandosDistintos

-- Definiciones de sumasSumandosImpares
-- ====================================

-- 1ª definición de sumasSumandosImpares
sumasSumandosImpares :: Integer -> [[Integer]]
sumasSumandosImpares n = aux n [1,3..n]
  where aux n _ | n < 0 = []
        aux 0 _  = [[]]
        aux _ [] = []
        aux x zs@(y:ys) = [y:zs | zs <- aux (x-y) zs] ++ aux x ys 

-- 2ª definición de sumasSumandosImpares
sumasSumandosImpares2 :: Integer ->[[Integer]]
sumasSumandosImpares2 = aux 1
  where aux i z
          | z < 0  = []
          | z == 0 = [[]]
          | z > 0  = concat [map (j:) (aux j (z-j)) | j <-[i,i+2..z]]

-- Definición de nSumasSumandosImpares
-- ===================================

nSumasSumandosImpares :: Integer -> Int
nSumasSumandosImpares =
  length . sumasSumandosImpares

-- Definición conjunta (de josejuan)
-- =================================

-- podemos definir una gran familia de generadores de la siguiente forma
sumas :: Integer ->Integer ->Integer ->Integer ->Integer ->[[Integer]]
sumas u a b k n = s u n where
  s i z | z < 0 = []
        | z == 0 = [[]]
        | z > 0 = concat [map (j:) (s j (z - j)) | j <-[k*i+a,k*i+b..z]]
 
-- así, si queremos los distintos
sumasSumandosDistintos3 :: Integer ->[[Integer]]
sumasSumandosDistintos3 = sumas 0 1 2 1
 
-- o queremos los impares repetidos
sumasSumandosImpares3 :: Integer ->[[Integer]]
sumasSumandosImpares3 = sumas 1 0 2 1

-- Igualdad de las sumas
-- =====================

igualdadDeSumas :: Integer -> Bool
igualdadDeSumas n =
  and [nSumasSumandosDistintos k == nSumasSumandosImpares k | k <- [1..n]]

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

--    λ> length (sumasSumandosDistintos2 70)
--    29927
--    (0.57 secs, 374,604,848 bytes)
--    λ> length (sumasSumandosDistintos3 70)
--    29927
--    (0.57 secs, 352,658,200 bytes)
--    λ> length (sumasSumandosImpares 70)
--    29927
--    (8.87 secs, 5,221,638,688 bytes)
--    λ> length (sumasSumandosImpares2 70)
--    29927
--    (0.61 secs, 422,132,696 bytes)
--    λ> length (sumasSumandosImpares3 70)
--    29927
--    (0.56 secs, 412,289,336 bytes)

100

import Data.List (delete, nub)

-- Definiciones de sumasSumandosDistintos

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

-- 1ª definición sumasSumandosDistintos

sumasSumandosDistintos :: Integer -> [[Integer]]

sumasSumandosDistintos n = aux n [1..n]

where aux 0 _ = [[]]

aux _ [] = []

aux x ys@(y:_)

| x < y = []

| x == y = [[x]]

| otherwise = [z : zs | z <- ys

, zs <- aux (x - z) (dropWhile (<=z) ys)]

-- 2ª definición de sumasSumandosDistintos

sumasSumandosDistintos2 :: Integer ->[[Integer]]

sumasSumandosDistintos2 = aux 0

where aux i z

| z < 0 = []

| z == 0 = [[]]

| z > 0 = concat [map (j:) (aux j (z-j)) | j <- [i+1..z]]

-- Definición de nSumasSumandosDistintos

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

nSumasSumandosDistintos :: Integer -> Int

nSumasSumandosDistintos =

length . sumasSumandosDistintos

-- Definiciones de sumasSumandosImpares

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

-- 1ª definición de sumasSumandosImpares

sumasSumandosImpares :: Integer -> [[Integer]]

sumasSumandosImpares n = aux n [1,3..n]

where aux n _ | n < 0 = []

aux 0 _ = [[]]

aux _ [] = []

aux x zs@(y:ys) = [y:zs | zs <- aux (x-y) zs] ++ aux x ys

-- 2ª definición de sumasSumandosImpares

sumasSumandosImpares2 :: Integer ->[[Integer]]

sumasSumandosImpares2 = aux 1

where aux i z

| z < 0 = []

| z == 0 = [[]]

| z > 0 = concat [map (j:) (aux j (z-j)) | j <-[i,i+2..z]]

-- Definición de nSumasSumandosImpares

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

nSumasSumandosImpares :: Integer -> Int

nSumasSumandosImpares =

length . sumasSumandosImpares

-- Definición conjunta (de josejuan)

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

-- podemos definir una gran familia de generadores de la siguiente forma

sumas :: Integer ->Integer ->Integer ->Integer ->Integer ->[[Integer]]

sumas u a b k n = s u n where

s i z | z < 0 = []

| z == 0 = [[]]

| z > 0 = concat [map (j:) (s j (z - j)) | j <-[k*i+a,k*i+b..z]]

-- así, si queremos los distintos

sumasSumandosDistintos3 :: Integer ->[[Integer]]

sumasSumandosDistintos3 = sumas 0 1 2 1

-- o queremos los impares repetidos

sumasSumandosImpares3 :: Integer ->[[Integer]]

sumasSumandosImpares3 = sumas 1 0 2 1

-- Igualdad de las sumas

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

igualdadDeSumas :: Integer -> Bool

igualdadDeSumas n =

and [nSumasSumandosDistintos k == nSumasSumandosImpares k | k <- [1..n]]

-- Comparación de eficiencia

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

-- λ> length (sumasSumandosDistintos2 70)

-- 29927

-- (0.57 secs, 374,604,848 bytes)

-- λ> length (sumasSumandosDistintos3 70)

-- 29927

-- (0.57 secs, 352,658,200 bytes)

-- λ> length (sumasSumandosImpares 70)

-- 29927

-- (8.87 secs, 5,221,638,688 bytes)

-- λ> length (sumasSumandosImpares2 70)

-- 29927

-- (0.61 secs, 422,132,696 bytes)

-- λ> length (sumasSumandosImpares3 70)

-- 29927

-- (0.56 secs, 412,289,336 bytes)

Número de dígitos del factorial

PorJosé A. Alonso 23-marzo-201731-marzo-2017

Definir las funciones

   nDigitosFact :: Integer -> Integer
   graficas     :: [Integer] -> IO ()

1 2	nDigitosFact :: Integer -> Integer graficas :: [Integer] -> IO ()

tales que

(nDigitosFact n) es el número de dígitos de n!. Por ejemplo,

     nDigitosFact 0        ==  1
     nDigitosFact 4        ==  2
     nDigitosFact 5        ==  3
     nDigitosFact 10       ==  7
     nDigitosFact 100      ==  158
     nDigitosFact 1000     ==  2568
     nDigitosFact 10000    ==  35660
     nDigitosFact 100000   ==  456574
     nDigitosFact 1000000  ==  5565709

nDigitosFact 0 == 1

nDigitosFact 4 == 2

nDigitosFact 5 == 3

nDigitosFact 10 == 7

nDigitosFact 100 == 158

nDigitosFact 1000 == 2568

nDigitosFact 10000 == 35660

nDigitosFact 100000 == 456574

nDigitosFact 1000000 == 5565709

(graficas xs) dibuja las gráficas de los números de dígitos del factorial de k (para k en xs) y de la recta y = 5.5 x. Por ejemplo, (graficas [0,500..10^6]) dibuja

Nota: Este ejercicio está basado en el problema How many digits? de Kattis en donde se impone la restricción de calcular, en menos de 1 segundo, el número de dígitos de los factoriales de 10.000 números del rango [0,1.000.000].

Se puede simular como sigue

   λ> import System.Random 
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> maximum (map nDigitosFact xs)
   5561492
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> maximum (map nDigitosFact xs)
   5563303

λ> import System.Random

λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]

λ> maximum (map nDigitosFact xs)

5561492

λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]

λ> maximum (map nDigitosFact xs)

5563303

Soluciones

import Data.List (genericLength, genericIndex)
import Graphics.Gnuplot.Simple

-- 1ª definición
nDigitosFact1 :: Integer -> Integer
nDigitosFact1 n =
  genericLength (show (product [1..n]))

-- 2ª definición (usando logaritmos)
-- =================================

-- Basado en
--    nDigitos (n!) = 1 + floor (log (n!))
--                  = 1 + floor (log (1*2*3*...*n))
--                  = 1 + floor (log(1) + log(2) + log(3) +...+ log(n))

nDigitosFact2 :: Integer -> Integer
nDigitosFact2 n =
  1 + floor (sum [logBase 10 (fromIntegral k) | k <- [1..n]])

-- 3ª definición (usando logaritmos y programación dinámica)
-- =========================================================

nDigitosFact3 :: Integer -> Integer
nDigitosFact3 0 = 1
nDigitosFact3 n = 1 + floor ((sumLogs `genericIndex` (n-1)) / log 10)

logs :: [Double]
logs = map log [1..]

sumLogs :: [Double]
sumLogs = scanl1 (+) logs

-- 4ª definición (Usando la fórmula de Kamenetsky)
-- ===============================================

-- La fórmula se encuentra en https://oeis.org/A034886

nDigitosFact4 :: Integer -> Integer
nDigitosFact4 0 = 1
nDigitosFact4 1 = 1
nDigitosFact4 n =
  1 + floor (m * logBase 10 (m/e) + logBase 10 (2*pi*m)/2)
  where m = fromIntegral n
        e = exp 1

--    λ> nDigitosFact1 (4*10^4)
--    166714
--    (5.61 secs, 1,649,912,864 bytes)
--    λ> nDigitosFact2 (4*10^4)
--    166714
--    (0.10 secs, 13,741,360 bytes)
--
--    λ> nDigitosFact2 (7*10^5)
--    3787566
--    (1.86 secs, 187,666,328 bytes)
--    λ> nDigitosFact3 (7*10^5)
--    3787566
--    (0.02 secs, 0 bytes)
--    λ> nDigitosFact3 (7*10^5)
--    3787566
--    (1.01 secs, 238,682,064 bytes)
--    λ> nDigitosFact4 (7*10^5)
--    3787566
--    (0.01 secs, 0 bytes)
-- 
--    λ> import System.Random 
--    λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^2]]
--    λ> maximum (map nDigitosFact3 xs)
--    5565097
--    (11.19 secs, 7,336,595,440 bytes)
--    λ> maximum (map nDigitosFact4 xs)
--    5565097
--    (0.01 secs, 0 bytes)

graficas :: [Integer] -> IO ()
graficas xs = 
    plotLists [Key Nothing]
              [p1, p2]
    where p1, p2 :: [(Float, Float)]
          p1 = [(fi k, fi (nDigitosFact4 k)) | k <- xs]
          p2 = [(k',5.5*k') | k <- xs, let k' = fi k]
          fi = fromIntegral

import Data.List (genericLength, genericIndex)

import Graphics.Gnuplot.Simple

-- 1ª definición

nDigitosFact1 :: Integer -> Integer

nDigitosFact1 n =

genericLength (show (product [1..n]))

-- 2ª definición (usando logaritmos)

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

-- Basado en

-- nDigitos (n!) = 1 + floor (log (n!))

-- = 1 + floor (log (1*2*3*...*n))

-- = 1 + floor (log(1) + log(2) + log(3) +...+ log(n))

nDigitosFact2 :: Integer -> Integer

nDigitosFact2 n =

1 + floor (sum [logBase 10 (fromIntegral k) | k <- [1..n]])

-- 3ª definición (usando logaritmos y programación dinámica)

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

nDigitosFact3 :: Integer -> Integer

nDigitosFact3 0 = 1

nDigitosFact3 n = 1 + floor ((sumLogs `genericIndex` (n-1)) / log 10)

logs :: [Double]

logs = map log [1..]

sumLogs :: [Double]

sumLogs = scanl1 (+) logs

-- 4ª definición (Usando la fórmula de Kamenetsky)

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

-- La fórmula se encuentra en https://oeis.org/A034886

nDigitosFact4 :: Integer -> Integer

nDigitosFact4 0 = 1

nDigitosFact4 1 = 1

nDigitosFact4 n =

1 + floor (m * logBase 10 (m/e) + logBase 10 (2*pi*m)/2)

where m = fromIntegral n

e = exp 1

-- λ> nDigitosFact1 (4*10^4)

-- 166714

-- (5.61 secs, 1,649,912,864 bytes)

-- λ> nDigitosFact2 (4*10^4)

-- 166714

-- (0.10 secs, 13,741,360 bytes)

-- λ> nDigitosFact2 (7*10^5)

-- 3787566

-- (1.86 secs, 187,666,328 bytes)

-- λ> nDigitosFact3 (7*10^5)

-- 3787566

-- (0.02 secs, 0 bytes)

-- λ> nDigitosFact3 (7*10^5)

-- 3787566

-- (1.01 secs, 238,682,064 bytes)

-- λ> nDigitosFact4 (7*10^5)

-- 3787566

-- (0.01 secs, 0 bytes)

-- λ> import System.Random

-- λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^2]]

-- λ> maximum (map nDigitosFact3 xs)

-- 5565097

-- (11.19 secs, 7,336,595,440 bytes)

-- λ> maximum (map nDigitosFact4 xs)

-- 5565097

-- (0.01 secs, 0 bytes)

graficas :: [Integer] -> IO ()

graficas xs =

plotLists [Key Nothing]

[p1, p2]

where p1, p2 :: [(Float, Float)]

p1 = [(fi k, fi (nDigitosFact4 k)) | k <- xs]

p2 = [(k',5.5*k') | k <- xs, let k' = fi k]

fi = fromIntegral

Representación de conjuntos mediante intervalos

PorJosé A. Alonso 22-marzo-201725-abril-2021

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

   intervalos :: [Int] -> [(Int,Int)]

1	intervalos :: [Int] -> [(Int,Int)]

tal que (intervalos xs) es lista ordenada de intervalos que representa al conjunto xs. Por ejemplo,

   intervalos [2,7,4,3,9,6]  ==  [(2,4),(6,7),(9,9)]

1	intervalos [2,7,4,3,9,6] == [(2,4),(6,7),(9,9)]

Nota: Este ejercicio está basado en el problema Bus numbers de Kattis

Soluciones

import Data.List (sort)

intervalos :: [Int] -> [(Int,Int)]
intervalos = map intervalo . segmentos

-- (segmentos xs) es la lista de segmentos formados por elementos
-- consecutivos de xs. Por ejemplo,
--    segmentos [2,7,4,3,9,6]  ==  [[2,3,4],[6,7],[9]]
segmentos :: [Int] -> [[Int]]
segmentos xs = aux as [[a]]
  where aux [] zs = zs
        aux (y:ys) ((a:as):zs) | y == a-1  = aux ys ((y:a:as):zs)
                               | otherwise = aux ys ([y]:(a:as):zs)
        (a:as) = reverse (sort xs)

-- (intervalo xs) es el intervalo correspondiente al segmento xs. Por
-- ejemplo, 
--    intervalo [2,3,4]  ==  (2,4)
--    intervalo [6,7]    ==  (6,7)
--    intervalo [9]      ==  (9,9)
intervalo :: [Int] -> (Int,Int)
intervalo xs = (head xs, last xs)

import Data.List (sort)

intervalos :: [Int] -> [(Int,Int)]

intervalos = map intervalo . segmentos

-- (segmentos xs) es la lista de segmentos formados por elementos

-- consecutivos de xs. Por ejemplo,

-- segmentos [2,7,4,3,9,6] == [[2,3,4],[6,7],[9]]

segmentos :: [Int] -> [[Int]]

segmentos xs = aux as [[a]]

where aux [] zs = zs

aux (y:ys) ((a:as):zs) | y == a-1 = aux ys ((y:a:as):zs)

| otherwise = aux ys ([y]:(a:as):zs)

(a:as) = reverse (sort xs)

-- (intervalo xs) es el intervalo correspondiente al segmento xs. Por

-- ejemplo,

-- intervalo [2,3,4] == (2,4)

-- intervalo [6,7] == (6,7)

-- intervalo [9] == (9,9)

intervalo :: [Int] -> (Int,Int)

intervalo xs = (head xs, last xs)

Reducción de repeticiones consecutivas

PorJosé A. Alonso 20-marzo-201727-marzo-2017

Definir la función

   reducida :: Eq a => [a] -> [a]

1	reducida :: Eq a => [a] -> [a]

tal que (reducida xs) es la lista obtenida a partir de xs de forma que si hay dos o más elementos idénticos consecutivos, borra las repeticiones y deja sólo el primer elemento. Por ejemplo,

   ghci> reducida "eesssooo essss   toodddooo"
   "eso es todo"

1 2	ghci> reducida "eesssooo essss toodddooo" "eso es todo"

Nota: Basado en el ejercicio Apaxiaaaaaaaaaaaans! de Kattis.

Soluciones

import Data.List (group)

-- 1ª solución (por recursión):
reducida1 :: Eq a => [a] -> [a]
reducida1 []     = []
reducida1 (x:xs) = x : reducida1 (dropWhile (==x) xs)

-- 2ª solución (por comprensión):
reducida2 :: Eq a => [a] -> [a]
reducida2 xs = [x | (x:_) <- group xs]

-- 3ª solución (sin argumentos):
reducida3 :: Eq a => [a] -> [a]
reducida3 = map head . group

import Data.List (group)

-- 1ª solución (por recursión):

reducida1 :: Eq a => [a] -> [a]

reducida1 [] = []

reducida1 (x:xs) = x : reducida1 (dropWhile (==x) xs)

-- 2ª solución (por comprensión):

reducida2 :: Eq a => [a] -> [a]

reducida2 xs = [x | (x:_) <- group xs]

-- 3ª solución (sin argumentos):

reducida3 :: Eq a => [a] -> [a]

reducida3 = map head . group

Suma de subconjuntos

PorJosé A. Alonso 17-marzo-201724-marzo-2017

Los subconjuntos de [1, 4, 2] son

   [], [1], [4], [1, 4], [2], [1, 2], [4, 2], [1, 4, 2]

1	[], [1], [4], [1, 4], [2], [1, 2], [4, 2], [1, 4, 2]

Las sumas de sus elementos son

   0, 1, 4, 5, 2, 3, 6, 7

1	0, 1, 4, 5, 2, 3, 6, 7

Y la suma de las sumas es 28.

Definir la función

   sumaSubconjuntos :: [Integer] -> Integer

1	sumaSubconjuntos :: [Integer] -> Integer

tal que (sumaSubconjuntos xs) es la suma de las sumas de los
subconjuntos de xs. Por ejemplo,

   sumaSubconjuntos [1,2]                     == 6
   sumaSubconjuntos [1,4,2]                   == 28
   length (show (sumaSubconjuntos [1..10^6])) == 301042

sumaSubconjuntos [1,2] == 6

sumaSubconjuntos [1,4,2] == 28

length (show (sumaSubconjuntos [1..10^6])) == 301042

Soluciones

import Data.List (subsequences)

-- 1ª definición
sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs =
  sum [sum ys | ys <- subsequences xs]

-- 2ª definición
sumaSubconjuntos2 :: [Integer] -> Integer
sumaSubconjuntos2 =
  sum . map sum . subsequences

-- 3ª definición
sumaSubconjuntos3 :: [Integer] -> Integer
sumaSubconjuntos3 xs =
  2^(n-1) * sum xs
  where n = length xs

import Data.List (subsequences)

-- 1ª definición

sumaSubconjuntos :: [Integer] -> Integer

sumaSubconjuntos xs =

sum [sum ys | ys <- subsequences xs]

-- 2ª definición

sumaSubconjuntos2 :: [Integer] -> Integer

sumaSubconjuntos2 =

sum . map sum . subsequences

-- 3ª definición

sumaSubconjuntos3 :: [Integer] -> Integer

sumaSubconjuntos3 xs =

2^(n-1) * sum xs

where n = length xs

Caminos minimales en un arbol numérico

PorJosé A. Alonso 10-marzo-201725-abril-2021

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

1	ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

λ> putStrLn (drawTree (fmap show ej))

+- 5

| |

| `- 9

`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

/ \

5 3

| |

4 2

/ \ |

3 2 1

| |

2 1

Definir las siguientes funciones

   mayoresDivisores :: Int -> [Int]
   arbol            :: Int -> Tree Int
   caminos          :: Int -> [[Int]]
   caminosMinimales :: Int -> [[Int]]

mayoresDivisores :: Int -> [Int]

arbol :: Int -> Tree Int

caminos :: Int -> [[Int]]

caminosMinimales :: Int -> [[Int]]

tales que

(mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

     mayoresDivisores 24  ==  [12,8,6]
     mayoresDivisores 16  ==  [8,4]
     mayoresDivisores 10  ==  [5]
     mayoresDivisores 17  ==  []

mayoresDivisores 24 == [12,8,6]

mayoresDivisores 16 == [8,4]

mayoresDivisores 10 == [5]

mayoresDivisores 17 == []

(arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbol 6)))
     6
     |
     +- 5
     |  |
     |  `- 4
     |     |
     |     +- 3
     |     |  |
     |     |  `- 2
     |     |     |
     |     |     `- 1
     |     |
     |     `- 2
     |        |
     |        `- 1
     |
     `- 3
        |
        `- 2
           |
           `- 1

λ> putStrLn (drawTree (fmap show (arbol 6)))

+- 5

| |

| `- 4

| |

| +- 3

| | |

| | `- 2

| | |

| | `- 1

| |

| `- 2

| |

| `- 1

`- 3

`- 2

`- 1

(caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminos 6
     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

1 2	λ> caminos 6 [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

(caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminosMinimales 6
     [[6,3,2,1]]
     λ> caminosMinimales 17
     [[17,16,4,2,1]]
     λ> caminosMinimales 50
     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

λ> caminosMinimales 6

[[6,3,2,1]]

λ> caminosMinimales 17

[[17,16,4,2,1]]

λ> caminosMinimales 50

[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Soluciones

import Data.Tree

mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  [max u v | u <- [2..floor (sqrt (fromIntegral x))]
           , x `mod` u == 0
           , let v = x `div` u]  

arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]
caminos = caminosArbol . arbol

--    λ> caminosArbol (arbol 6)
--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
caminosArbol :: Tree a -> [[a]]
caminosArbol (Node x []) = [[x]]
caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]
caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ys | ys <- yss, length ys == m]
  where yss = caminos x
        m   = minimum (map length yss)

import Data.Tree

mayoresDivisores :: Int -> [Int]

mayoresDivisores x =

[max u v | u <- [2..floor (sqrt (fromIntegral x))]

, x `mod` u == 0

, let v = x `div` u]

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]

caminos = caminosArbol . arbol

-- λ> caminosArbol (arbol 6)

-- [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

caminosArbol :: Tree a -> [[a]]

caminosArbol (Node x []) = [[x]]

caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]

caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = [ys | ys <- yss, length ys == m]

where yss = caminos x

m = minimum (map length yss)

Contando en la arena

PorJosé A. Alonso 2-marzo-20179-marzo-2017

El problema de ayer de ¡Acepta el reto! fue Contando en la arena cuyo enunciado es el siguiente:

Es ampliamente conocido que escribimos los números utilizando base 10, en la que expresamos las cantidades utilizando 10 dígitos distintos (0…9). El valor de cada uno de ellos depende de la posición que ocupe dentro del número, pues cada dígito se multiplica por una potencia de 10 distinta según cuál sea esa posición.

La descomposición, por ejemplo, del número 1.234 es: 1.234 = 1×10^3 + 2×10^2 + 3×10^1 + 4×10^0

Otra base muy conocida es la base 2 al ser la utilizada por los dispositivos electrónicos. En ella sólo hay dos dígitos distintos (0 y 1), que se ven multiplicados por potencias de 2.

Mucho antes de que llegaran la base 2, la base 10 e incluso los números romanos, los primeros seres humanos contaban haciendo surcos en la arena, muescas en un trozo de madera o colocando palos en línea. Estaban, sin saberlo, usando base 1. En ella sólo hay un símbolo y cada dígito es multiplicado por una potencia de 1. Dado que 1^n = 1 el resultado es que todos los dígitos tienen el mismo peso.

Definir la función

   transformaAbase1 :: FilePath -> FilePath -> IO ()

1	transformaAbase1 :: FilePath -> FilePath -> IO ()

tal que al evaluar (transformaAbase1 f1 f2) lee el contenido del fichero f1 (que estará compuesto por distintos números mayores que 0, cada uno en una línea) y escribe en el fichero f2 una línea con la representación en base 1 de cada uno de los números de f1 excepto el 0 final. Por ejemplo, si el contenido de «Entrada.txt» es

al evaluar (transformaAbase1 «Entrada.txt» «Salida.txt») el contenido de «Salida.txt» debe de ser

1
1111
111111

1111

111111

Soluciones

transformaAbase1 :: FilePath -> FilePath -> IO ()
transformaAbase1 f1 f2 = do
  cs <- readFile f1
  writeFile f2 (transformaAbase1Aux cs)

-- (transformaAbase1Aux cs) es la cadena obtenida transformando a base 1
-- cada uno de los números de cs. Por ejemplo,
--    λ> transformaAbase1Aux "1\n4\n6\n0\n" 
--    "1\n1111\n111111\n"
transformaAbase1Aux :: String -> String
transformaAbase1Aux cs =
  unlines (map (show . enBase1) (numeros cs))

-- (numeros cs) es la lista de los números de cs, excepto el último. Por
-- ejemplo, 
--    numeros "1\n4\n6\n0\n"  ==  [1,4,6]
numeros :: String -> [Integer]
numeros cs  =
  init (map read (lines cs))

-- (enBsase1 x) es la representación de x en base 1. Por ejemplo,
--    enBase1 4  ==  1111
enBase1 :: Integer -> Integer
enBase1 x = (10^x - 1) `div` 9

transformaAbase1 :: FilePath -> FilePath -> IO ()

transformaAbase1 f1 f2 = do

cs <- readFile f1

writeFile f2 (transformaAbase1Aux cs)

-- (transformaAbase1Aux cs) es la cadena obtenida transformando a base 1

-- cada uno de los números de cs. Por ejemplo,

-- λ> transformaAbase1Aux "1\n4\n6\n0\n"

-- "1\n1111\n111111\n"

transformaAbase1Aux :: String -> String

transformaAbase1Aux cs =

unlines (map (show . enBase1) (numeros cs))

-- (numeros cs) es la lista de los números de cs, excepto el último. Por

-- ejemplo,

-- numeros "1\n4\n6\n0\n" == [1,4,6]

numeros :: String -> [Integer]

numeros cs =

init (map read (lines cs))

-- (enBsase1 x) es la representación de x en base 1. Por ejemplo,

-- enBase1 4 == 1111

enBase1 :: Integer -> Integer

enBase1 x = (10^x - 1) `div` 9

Precisión de aproximaciones de pi

PorJosé A. Alonso 27-febrero-20176-marzo-2017

La precisión de una aproximación x de pi es el número de dígitos comunes entre el inicio de x y de pi. Por ejemplo, puesto que 355/113 es 3.1415929203539825 y pi es 3.141592653589793, la precisión de 355/113 es 7.

Definir las siguientes funciones

   mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
   precisionPi       :: Double -> Int
   precisionPiCR     :: CReal -> Int

mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]

precisionPi :: Double -> Int

precisionPiCR :: CReal -> Int

tales que

(mayorPrefijoComun xs ys) es el mayor prefijo común de xs e ys. Por ejemplo,

     mayorPrefijoComun []      [2,3,4,5]  ==  []
     mayorPrefijoComun [2,3,5] []         ==  []
     mayorPrefijoComun [2,3,5] [2,3,4,5]  ==  [2,3]
     mayorPrefijoComun [2,3,5] [2,5,3,4]  ==  [2]
     mayorPrefijoComun [2,3,5] [5,2,3,4]  ==  []

mayorPrefijoComun [] [2,3,4,5] == []

mayorPrefijoComun [2,3,5] [] == []

mayorPrefijoComun [2,3,5] [2,3,4,5] == [2,3]

mayorPrefijoComun [2,3,5] [2,5,3,4] == [2]

mayorPrefijoComun [2,3,5] [5,2,3,4] == []

(precisionPi x) es la precisión de la aproximación de pi x. Por ejemplo,

     precisionPi (25/8)              ==  2
     precisionPi (22/7)              ==  3
     precisionPi (sqrt 2 + sqrt 3)   ==  3
     precisionPi (377/120)           ==  4
     precisionPi (31**(1/3))         ==  4
     precisionPi (7^7/4^9)           ==  5
     precisionPi (355/113)           ==  7
     precisionPi ((2143/22)**(1/4))  ==  9

precisionPi (25/8) == 2

precisionPi (22/7) == 3

precisionPi (sqrt 2 + sqrt 3) == 3

precisionPi (377/120) == 4

precisionPi (31**(1/3)) == 4

precisionPi (7^7/4^9) == 5

precisionPi (355/113) == 7

precisionPi ((2143/22)**(1/4)) == 9

(precisionPiCR x) es la precisión de la aproximación de pi x, como números reales. Por ejemplo,

     precisionPiCR (log (640320^3+744)/(sqrt 163))                        == 31
     precisionPiCR (log (5280^3*(236674+30303*sqrt 61)^3+744)/(sqrt 427)) == 53

1 2	precisionPiCR (log (640320^3+744)/(sqrt 163)) == 31 precisionPiCR (log (5280^3(236674+30303sqrt 61)^3+744)/(sqrt 427)) == 53

Nota: Para la definición precisionPiCR se usa la librería Data.Number.CReal que se instala con

   cabal install numbers

1	cabal install numbers

Soluciones

import Data.Number.CReal

-- mayorPrefijoComún
-- =================

-- 1ª definición
mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun [] _ = []
mayorPrefijoComun _ [] = []
mayorPrefijoComun (x:xs) (y:ys)
  | x == y    = x : mayorPrefijoComun xs ys
  | otherwise = []

-- 2ª definición
mayorPrefijoComun2 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun2 xs ys =
  [x | (x,y) <- takeWhile (\(x,y) -> x == y) (zip xs ys)] 

-- 3ª definición
mayorPrefijoComun3 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun3 xs ys =
  [x | (x,y) <- takeWhile (uncurry (==)) (zip xs ys)] 

-- 4ª definición
mayorPrefijoComun4 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun4 xs =
  map fst . takeWhile (uncurry (==)) . zip xs

-- 5ª definición
mayorPrefijoComun5 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun5 =
  ((map fst . takeWhile (uncurry (==))) .) . zip

-- precisionPi
-- ===========

-- 1ª definición
precisionPi :: Double -> Int
precisionPi x =
  length (mayorPrefijoComun xs ys) - 1
  where xs = show x
        ys = show pi

-- 2ª definición
precisionPi2 :: Double -> Int
precisionPi2 =
  pred . length . mayorPrefijoComun (show pi) . show

-- precisionPiCR
-- =============

precisionPiCR :: CReal -> Int
precisionPiCR = aux 50
  where aux n x | p < n-1   = p
                | otherwise = aux (n+50) x
          where p = precisionPiCRHasta n x

-- (precisionPiCRHasta n x) es la precisión de pi acotada por n. Por
-- ejemplo,
--    precisionPiCRHasta 1 3.14   ==  2
--    precisionPiCRHasta 5 3.14   ==  3
--    precisionPiCRHasta 5 3.142  ==  3
--    precisionPiCRHasta 5 3.141  ==  4
precisionPiCRHasta :: Int -> CReal -> Int
precisionPiCRHasta n x =
  length (mayorPrefijoComun xs ys) - 1
  where xs = showCReal n x
        ys = showCReal n pi

import Data.Number.CReal

-- mayorPrefijoComún

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

-- 1ª definición

mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun [] _ = []

mayorPrefijoComun _ [] = []

mayorPrefijoComun (x:xs) (y:ys)

| x == y = x : mayorPrefijoComun xs ys

| otherwise = []

-- 2ª definición

mayorPrefijoComun2 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun2 xs ys =

[x | (x,y) <- takeWhile (\(x,y) -> x == y) (zip xs ys)]

-- 3ª definición

mayorPrefijoComun3 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun3 xs ys =

[x | (x,y) <- takeWhile (uncurry (==)) (zip xs ys)]

-- 4ª definición

mayorPrefijoComun4 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun4 xs =

map fst . takeWhile (uncurry (==)) . zip xs

-- 5ª definición

mayorPrefijoComun5 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun5 =

((map fst . takeWhile (uncurry (==))) .) . zip

-- precisionPi

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

-- 1ª definición

precisionPi :: Double -> Int

precisionPi x =

length (mayorPrefijoComun xs ys) - 1

where xs = show x

ys = show pi

-- 2ª definición

precisionPi2 :: Double -> Int

precisionPi2 =

pred . length . mayorPrefijoComun (show pi) . show

-- precisionPiCR

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

precisionPiCR :: CReal -> Int

precisionPiCR = aux 50

where aux n x | p < n-1 = p

| otherwise = aux (n+50) x

where p = precisionPiCRHasta n x

-- (precisionPiCRHasta n x) es la precisión de pi acotada por n. Por

-- ejemplo,

-- precisionPiCRHasta 1 3.14 == 2

-- precisionPiCRHasta 5 3.14 == 3

-- precisionPiCRHasta 5 3.142 == 3

-- precisionPiCRHasta 5 3.141 == 4

precisionPiCRHasta :: Int -> CReal -> Int

precisionPiCRHasta n x =

length (mayorPrefijoComun xs ys) - 1

where xs = showCReal n x

ys = showCReal n pi

Cálculo de pi mediante la fracción continua de Lange

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

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange$

La primeras aproximaciones son

   a(1) = 3+1                = 4.0
   a(2) = 3+(1/(6+9))        = 3.066666666666667
   a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

a(1) = 3+1 = 4.0

a(2) = 3+(1/(6+9)) = 3.066666666666667

a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

1 2	aproximacionPi :: Int -> Double grafica :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

     aproximacionPi 1     ==  4.0
     aproximacionPi 2     ==  3.066666666666667
     aproximacionPi 3     ==  3.158974358974359
     aproximacionPi 10    ==  3.141287132741557
     aproximacionPi 100   ==  3.141592398533554
     aproximacionPi 1000  ==  3.1415926533392926

aproximacionPi 1 == 4.0

aproximacionPi 2 == 3.066666666666667

aproximacionPi 3 == 3.158974358974359

aproximacionPi 10 == 3.141287132741557

aproximacionPi 100 == 3.141592398533554

aproximacionPi 1000 == 3.1415926533392926

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_2$
(grafica [10..100]) dibuja
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_3$
y (grafica [100..200]) dibuja
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_4$

Nota: Este ejercicio ha sido propuesto por Antonio Morales.

Soluciones

import Graphics.Gnuplot.Simple
 
-- fraccionPi es la representación de la fracción continua de pi como un
-- par de listas infinitas.
fraccionPi :: [(Integer, Integer)]
fraccionPi = zip (3 : [6,6..]) (map (^2) [1,3..])

-- (aproximacionFC n fc) es la n-ésima aproximación de la fracción
-- continua fc (como un par de listas).  
aproximacionFC :: Int -> [(Integer, Integer)] -> Double
aproximacionFC n =
  foldr (\(a,b) z -> fromIntegral a + fromIntegral b / z) 1 . take n

aproximacionPi :: Int -> Double
aproximacionPi n =
  aproximacionFC n fraccionPi
 
grafica :: [Int] -> IO ()
grafica xs = 
    plotList [Key Nothing]
             [(k,aproximacionPi k) | k <- xs]

import Graphics.Gnuplot.Simple

-- fraccionPi es la representación de la fracción continua de pi como un

-- par de listas infinitas.

fraccionPi :: [(Integer, Integer)]

fraccionPi = zip (3 : [6,6..]) (map (^2) [1,3..])

-- (aproximacionFC n fc) es la n-ésima aproximación de la fracción

-- continua fc (como un par de listas).

aproximacionFC :: Int -> [(Integer, Integer)] -> Double

aproximacionFC n =

foldr (\(a,b) z -> fromIntegral a + fromIntegral b / z) 1 . take n

aproximacionPi :: Int -> Double

aproximacionPi n =

aproximacionFC n fraccionPi

grafica :: [Int] -> IO ()

grafica xs =

plotList [Key Nothing]

[(k,aproximacionPi k) | k <- xs]

Cálculo de pi mediante la variante de Euler de la serie armónica

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

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro «Introductio in Analysis Infinitorum» (1748).

El desarrollo es el siguiente

y se obtiene a partir de la serie armónica

modificando sólo el signo de algunos términos según el siguiente criterio:

Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
Cambiamos a – si el denominador de la fracción es un primo de la forma 4m+1.
Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

la de denominador 3 = 4×1-1 lleva un +,
la de denominador 5 = 4×1+1 lleva un -,
la de denominador 13 = 4×3+1 lleva un -,
la de denominador 6 = 2×3 lleva un + (porque los dos llevan un +),
la de denominador 10 = 2×5 lleva un – (porque el 2 lleva un + y el 5 lleva un -) y
la de denominador 50 = 5x5x2 lleva un + (un – por el primer 5, otro – por el segundo 5 y un + por el 2).

Definir las funciones

  aproximacionPi :: Int -> Double
  grafica        :: Int -> IO ()

1 2	aproximacionPi :: Int -> Double grafica :: Int -> IO ()

tales que

(aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

     aproximacionPi 1        ==  1.0
     aproximacionPi 10       ==  2.3289682539682537
     aproximacionPi 100      ==  2.934318000847734
     aproximacionPi 1000     ==  3.0603246224585128
     aproximacionPi 10000    ==  3.1105295744825403
     aproximacionPi 100000   ==  3.134308801935256
     aproximacionPi 1000000  ==  3.1395057903490806

aproximacionPi 1 == 1.0

aproximacionPi 10 == 2.3289682539682537

aproximacionPi 100 == 2.934318000847734

aproximacionPi 1000 == 3.0603246224585128

aproximacionPi 10000 == 3.1105295744825403

aproximacionPi 100000 == 3.134308801935256

aproximacionPi 1000000 == 3.1395057903490806

(grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Nota: Este ejercicio ha sido propuesto por Paula Macías.

Soluciones

import Data.Numbers.Primes
import Graphics.Gnuplot.Simple

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

aproximacionPi :: Int -> Double
aproximacionPi n =
  sum [1 / fromIntegral (k * signo k) | k <- [1..n]] 

signoPrimo :: Int -> Int
signoPrimo 2 = 1
signoPrimo p | p `mod` 4 == 3 = 1
             | otherwise      = -1

signo :: Int -> Int
signo n | isPrime n = signoPrimo n
        | otherwise = product (map signoPrimo (primeFactors n))

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

aproximacionPi2 :: Int -> Double
aproximacionPi2 n = serieEuler !! (n-1)

serieEuler :: [Double]
serieEuler =
  scanl1 (+) [1 / fromIntegral (n * signo n) | n <- [1..]]

-- Definición de grafica
-- =====================

grafica :: Int -> IO ()
grafica n = 
    plotList [Key Nothing]
             [(k,aproximacionPi2 k) | k <- [100,110..n]]

import Data.Numbers.Primes

import Graphics.Gnuplot.Simple

-- 1ª definición

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

aproximacionPi :: Int -> Double

aproximacionPi n =

sum [1 / fromIntegral (k * signo k) | k <- [1..n]]

signoPrimo :: Int -> Int

signoPrimo 2 = 1

signoPrimo p | p `mod` 4 == 3 = 1

| otherwise = -1

signo :: Int -> Int

signo n | isPrime n = signoPrimo n

| otherwise = product (map signoPrimo (primeFactors n))

-- 2ª definición

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

aproximacionPi2 :: Int -> Double

aproximacionPi2 n = serieEuler !! (n-1)

serieEuler :: [Double]

serieEuler =

scanl1 (+) [1 / fromIntegral (n * signo n) | n <- [1..]]

-- Definición de grafica

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

grafica :: Int -> IO ()

grafica n =

plotList [Key Nothing]

[(k,aproximacionPi2 k) | k <- [100,110..n]]

Sucesión de trazas de dígitos de pi

PorJosé A. Alonso 17-febrero-201724-febrero-2017

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

Las matrices de orden 1×1, 2×2, …, 5×5 formadas por los primeros dígitos de pi son

   ( 3 )  ( 3 1 )  ( 3 1 4 )  ( 3 1 4 1 )  ( 3 1 4 1 5 )
          ( 4 1 )  ( 1 5 9 )  ( 5 9 2 6 )  ( 9 2 6 5 3 )
                   ( 2 6 5 )  ( 5 3 5 8 )  ( 5 8 9 7 9 )
                              ( 9 7 9 3 )  ( 3 2 3 8 4 )
                                           ( 6 2 6 4 3 )

( 3 ) ( 3 1 ) ( 3 1 4 ) ( 3 1 4 1 ) ( 3 1 4 1 5 )

( 4 1 ) ( 1 5 9 ) ( 5 9 2 6 ) ( 9 2 6 5 3 )

( 2 6 5 ) ( 5 3 5 8 ) ( 5 8 9 7 9 )

( 9 7 9 3 ) ( 3 2 3 8 4 )

( 6 2 6 4 3 )

y sus trazas (es decir, sumas de los elementos de la diagonal principal) son 3, 4, 13, 20 y 25, respectivamente.

Definir la función

   trazas :: Int -> IO [Int]

1	trazas :: Int -> IO [Int]

tal que (trazas n) es la lista de las trazas de las matrices de orden 1×1, 2×2, 3×3, …, nxn formadas por los primeros dígitos de pi. Por ejemplo,

   λ> trazas 20
   [3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]
   λ> ts <- trazas 1000
   λ> maximum ts
   4644
   λ> maximum <$> trazas 1000
   4644

λ> trazas 20

[3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]

λ> ts <- trazas 1000

λ> maximum ts

4644

λ> maximum <$> trazas 1000

4644

Soluciones

import Data.Char (digitToInt)
import Data.Matrix (fromList, trace)

trazas :: Int -> IO [Int]
trazas n = do
  (d:_:ds) <- readFile "Digitos_de_pi.txt"
  let xs = map digitToInt (d:ds)
  return [trace (fromList k k xs) | k <- [1..n]]

import Data.Char (digitToInt)

import Data.Matrix (fromList, trace)

trazas :: Int -> IO [Int]

trazas n = do

(d:_:ds) <- readFile "Digitos_de_pi.txt"

let xs = map digitToInt (d:ds)

return [trace (fromList k k xs) | k <- [1..n]]

Cálculo de pi usando la fórmula de Vieta

PorJosé A. Alonso 14-febrero-201725-abril-2021

La fórmula de Vieta para el cálculo de pi es la siguiente

Definir las funciones

   aproximacionPi :: Int -> Double
   errorPi :: Double -> Int

1 2	aproximacionPi :: Int -> Double errorPi :: Double -> Int

tales que

(aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo,

     aproximacionPi  5  ==  3.140331156954753
     aproximacionPi 10  ==  3.1415914215112
     aproximacionPi 15  ==  3.141592652386592
     aproximacionPi 20  ==  3.1415926535886207
     aproximacionPi 25  ==  3.141592653589795

aproximacionPi 5 == 3.140331156954753

aproximacionPi 10 == 3.1415914215112

aproximacionPi 15 == 3.141592652386592

aproximacionPi 20 == 3.1415926535886207

aproximacionPi 25 == 3.141592653589795

(errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo,

     errorPi 0.1        ==  2
     errorPi 0.01       ==  4
     errorPi 0.001      ==  6
     errorPi 0.0001     ==  7
     errorPi 1e-4       ==  7
     errorPi 1e-14      ==  24
     pi                 ==  3.141592653589793
     aproximacionPi 24  ==  3.1415926535897913

errorPi 0.1 == 2

errorPi 0.01 == 4

errorPi 0.001 == 6

errorPi 0.0001 == 7

errorPi 1e-4 == 7

errorPi 1e-14 == 24

pi == 3.141592653589793

aproximacionPi 24 == 3.1415926535897913

Soluciones

-- 1ª definición de aproximacionPi
aproximacionPi :: Int -> Double
aproximacionPi n = product [2 / aux x | x <- [0..n]]
  where
    aux 0 = 1
    aux 1 = sqrt 2
    aux n = sqrt (2 + aux (n-1))

-- 2ª definición de aproximacionPi
aproximacionPi2 :: Int -> Double
aproximacionPi2 n = product [2/x | x <- 1 : xs] 
  where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)

-- 3ª definición de aproximaxionPi
aproximacionPi3 :: Int -> Double
aproximacionPi3 n =  product (2 : take n (map (2/) xs))
  where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]

-- 1ª definición de errorPi
errorPi :: Double -> Int
errorPi x = head [n | n <- [1..]
                    , abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi
errorPi2 :: Double -> Int
errorPi2 x = until aceptable (+1) 1
  where aceptable n = abs (pi - aproximacionPi n) < x

-- 1ª definición de aproximacionPi

aproximacionPi :: Int -> Double

aproximacionPi n = product [2 / aux x | x <- [0..n]]

where

aux 0 = 1

aux 1 = sqrt 2

aux n = sqrt (2 + aux (n-1))

-- 2ª definición de aproximacionPi

aproximacionPi2 :: Int -> Double

aproximacionPi2 n = product [2/x | x <- 1 : xs]

where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)

-- 3ª definición de aproximaxionPi

aproximacionPi3 :: Int -> Double

aproximacionPi3 n = product (2 : take n (map (2/) xs))

where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]

-- 1ª definición de errorPi

errorPi :: Double -> Int

errorPi x = head [n | n <- [1..]

, abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi

errorPi2 :: Double -> Int

errorPi2 x = until aceptable (+1) 1

where aceptable n = abs (pi - aproximacionPi n) < x

Prefijo con suma acotada

PorJosé A. Alonso 7-febrero-201714-febrero-2017

Definir la función

   prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

1	prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

   prefijoAcotado 10 [3,2,5,7]  ==  [3,2]
   prefijoAcotado 10 [1..]      ==  [1,2,3]

1 2	prefijoAcotado 10 [3,2,5,7] == [3,2] prefijoAcotado 10 [1..] == [1,2,3]

Soluciones

-- 1ª definición (por recursión):
prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x [] = []
prefijoAcotado x (y:ys)
  | y < x     = y : prefijoAcotado (x-y) ys
  | otherwise = []

-- 2ª definición (con scanl1 y takeWhile):
prefijoAcotado2 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado2 x ys = map fst conSumasAcotadas
  where 
    sumas            = scanl1 (+) ys 
    conSumas         = zip ys sumas
    conSumasAcotadas = takeWhile (\(a,b) -> b < x) conSumas

-- 3ª definición (con (.)):
prefijoAcotado3 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado3 x ys = map fst conSumasAcotadas
  where 
    sumas            = scanl1 (+) ys 
    conSumas         = zip ys sumas
    conSumasAcotadas = takeWhile ((<x) . snd) conSumas

-- 4ª definición:
prefijoAcotado4 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado4 x ys = 
    map fst (takeWhile ((<x) . snd) (zip ys (scanl1 (+) ys)))

-- 1ª definición (por recursión):

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x [] = []

prefijoAcotado x (y:ys)

| y < x = y : prefijoAcotado (x-y) ys

| otherwise = []

-- 2ª definición (con scanl1 y takeWhile):

prefijoAcotado2 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado2 x ys = map fst conSumasAcotadas

where

sumas = scanl1 (+) ys

conSumas = zip ys sumas

conSumasAcotadas = takeWhile (\(a,b) -> b < x) conSumas

-- 3ª definición (con (.)):

prefijoAcotado3 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado3 x ys = map fst conSumasAcotadas

where

sumas = scanl1 (+) ys

conSumas = zip ys sumas

conSumasAcotadas = takeWhile ((<x) . snd) conSumas

-- 4ª definición:

prefijoAcotado4 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado4 x ys =

map fst (takeWhile ((<x) . snd) (zip ys (scanl1 (+) ys)))

Sucesión de Cantor de números innombrables

PorJosé A. Alonso 3-febrero-201725-abril-2021

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

   1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

1	1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior
como se indica a continuación:

  1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
  24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
  44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
  (2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
  (25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
  (30) 99 100

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23

24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41 (9) 43

44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62

(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)

(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)

(30) 99 100

Definir la sucesión

   sucCantor :: [Integer]

1	sucCantor :: [Integer]

cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,

   λ> take 100 sucCantor
   [1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
    22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
    40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
    13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
    20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
    6, 92,93,94,95,96, 29, 30 ,99,100]

   λ> sucCantor2 !! (5+10^6)
   544480

   λ> sucCantor2 !! (6+10^6)
   266086

λ> take 100 sucCantor

[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,

22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,

40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,

13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,

20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,

6, 92,93,94,95,96, 29, 30 ,99,100]

λ> sucCantor2 !! (5+10^6)

544480

λ> sucCantor2 !! (6+10^6)

266086

Soluciones

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

sucCantor1 :: [Integer]
sucCantor1 = map fst $ scanl f (1,0) [2..]
  where f (a,i) x
          | esInnombrable x = (sucCantor1 !! i, i+1)
          | otherwise       = (x,i)


esInnombrable :: Integer -> Bool
esInnombrable x =
  rem x 7 == 0 || '7' `elem` show x

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

sucCantor2 :: [Integer]
sucCantor2 = aux 0 1
  where aux i x
          | esInnombrable x = sucCantor2 !! i : aux (i+1) (x+1)
          | otherwise       = x : aux i (x+1)

-- 1ª solución

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

sucCantor1 :: [Integer]

sucCantor1 = map fst $ scanl f (1,0) [2..]

where f (a,i) x

| esInnombrable x = (sucCantor1 !! i, i+1)

| otherwise = (x,i)

esInnombrable :: Integer -> Bool

esInnombrable x =

rem x 7 == 0 || '7' `elem` show x

-- 2ª solución

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

sucCantor2 :: [Integer]

sucCantor2 = aux 0 1

where aux i x

| esInnombrable x = sucCantor2 !! i : aux (i+1) (x+1)

| otherwise = x : aux i (x+1)

Referencia

Basado en Cantor’s unspeakable numbers de
CodeGolf.

Subrayado de un carácter

PorJosé A. Alonso 1-febrero-20178-febrero-2017

Definir el procedimiento

   subraya :: String -> Char -> IO ()

1	subraya :: String -> Char -> IO ()

tal que (subraya cs c) escribe la cadena cs y debajo otra subrayando las ocurrencias de c. Por ejemplo,

   λ> subraya "Salamanca es castellana" 'a'
   Salamanca es castellana
    ^ ^ ^  ^     ^     ^ ^
   λ> subraya "Salamanca es castellana" 'n'
   Salamanca es castellana
         ^              ^ 
   λ> subraya "Salamanca es castellana" ' '
   Salamanca es castellana
            ^  ^

λ> subraya "Salamanca es castellana" 'a'

Salamanca es castellana

^ ^ ^ ^ ^ ^ ^

λ> subraya "Salamanca es castellana" 'n'

Salamanca es castellana

^ ^

λ> subraya "Salamanca es castellana" ' '

Salamanca es castellana

^ ^

Soluciones

-- 1ª definición
subraya :: String -> Char -> IO ()
subraya cs c = do
  putStrLn cs
  putStrLn (subrayado cs c)

subrayado :: String -> Char -> String
subrayado cs c = map procesa cs
  where procesa x | x == c    = '^'
                  | otherwise = ' '

-- 2ª definición
subraya2 :: String -> Char -> IO ()
subraya2 cs c = 
  mapM_ putStrLn [cs, subrayado cs c]

-- 1ª definición

subraya :: String -> Char -> IO ()

subraya cs c = do

putStrLn cs

putStrLn (subrayado cs c)

subrayado :: String -> Char -> String

subrayado cs c = map procesa cs

where procesa x | x == c = '^'

| otherwise = ' '

-- 2ª definición

subraya2 :: String -> Char -> IO ()

subraya2 cs c =

mapM_ putStrLn [cs, subrayado cs c]

Suma ordenada de listas infinitas ordenadas

PorJosé A. Alonso 13-enero-201720-enero-2017

Definir la función

   sumaOrdenada :: [Integer] -> [Integer] -> [Integer]

1	sumaOrdenada :: [Integer] -> [Integer] -> [Integer]

tal que (sumaOrdenada xs ys) es la suma ordenada de las listas infinitas crecientes xs e ys. Por ejemplo,

   λ> take 15 (sumaOrdenada [5,10..] [7,14..])
   [12,17,19,22,24,26,27,29,31,32,33,34,36,37,38]
   λ> take 15 (sumaOrdenada [2^n | n <- [0..]] [3^n | n <- [0..]])
   [2,3,4,5,7,9,10,11,13,17,19,25,28,29,31]

λ> take 15 (sumaOrdenada [5,10..] [7,14..])

[12,17,19,22,24,26,27,29,31,32,33,34,36,37,38]

λ> take 15 (sumaOrdenada [2^n | n <- [0..]] [3^n | n <- [0..]])

[2,3,4,5,7,9,10,11,13,17,19,25,28,29,31]

Soluciones

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

sumaOrdenada1 :: [Integer] -> [Integer] -> [Integer]
sumaOrdenada1 (x:xs) (y:ys) =
  x+y : map (+x) ys `mezcla` map (+y) xs `mezcla` sumaOrdenada1 ys xs

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys

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

sumaOrdenada2 :: [Integer] -> [Integer] -> [Integer]
sumaOrdenada2 xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- 1ª definición

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

sumaOrdenada1 :: [Integer] -> [Integer] -> [Integer]

sumaOrdenada1 (x:xs) (y:ys) =

x+y : map (+x) ys `mezcla` map (+y) xs `mezcla` sumaOrdenada1 ys xs

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x == y = x : mezcla xs ys

| x > y = y : mezcla (x:xs) ys

-- 2ª definición

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

sumaOrdenada2 :: [Integer] -> [Integer] -> [Integer]

sumaOrdenada2 xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]

mezclaTodas = foldr1 xmezcla

where xmezcla (x:xs) ys = x : mezcla xs ys

Mínima suma de las ramas de un árbol

PorJosé A. Alonso 28-diciembre-201625-marzo-2022

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
     deriving Show

1 2	data Arbol a = N a [Arbol a] deriving Show

Por ejemplo, los árboles

     1         1             1          
    / \       / \           / \   
   8   3     5   3         5   3  
       |        /|\       /|\  |   
       4       4 7 6     4 7 6 7

1 1 1

/ \ / \ / \

8 3 5 3 5 3

| /|\ /|\ |

4 4 7 6 4 7 6 7

se representan por

   ej1, ej2, ej3 :: Arbol Int
   ej1 = N 1 [N 8 [],N 3 [N 4 []]]
   ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]]
   ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]]

ej1, ej2, ej3 :: Arbol Int

ej1 = N 1 [N 8 [],N 3 [N 4 []]]

ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]]

ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]]

Definir la función

   minimaSuma :: Arbol Int -> Int

1	minimaSuma :: Arbol Int -> Int

tal que (minimaSuma a) es el mínimo de las sumas de las ramas del árbol a. Por ejemplo,

   minimaSuma ej1  ==  8
   minimaSuma ej2  ==  6
   minimaSuma ej3  ==  10

minimaSuma ej1 == 8

minimaSuma ej2 == 6

minimaSuma ej3 == 10

Soluciones

data Arbol a = N a [Arbol a]
  deriving Show

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 8 [],N 3 [N 4 []]]
ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]]
ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]] 


-- 1ª definición
-- =============
minimaSuma :: (Ord a, Num a) => Arbol a -> a
minimaSuma a = minimum [sum xs | xs <- ramas a]

-- (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
--    ghci> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
--    [[3,5,6],[3,4],[3,7,2],[3,7,1]]
ramas :: Arbol b -> [[b]]
ramas (N x []) = [[x]]
ramas (N x as) = [x : xs | a <- as, xs <- ramas a]

-- 2ª definición
-- =============
  
minimaSuma2 :: Arbol Int -> Int
minimaSuma2 (N x []) = x
minimaSuma2 (N x as) = x + minimum (map minimaSuma2 as)

data Arbol a = N a [Arbol a]

deriving Show

ej1, ej2, ej3 :: Arbol Int

ej1 = N 1 [N 8 [],N 3 [N 4 []]]

ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]]

ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]]

-- 1ª definición

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

minimaSuma :: (Ord a, Num a) => Arbol a -> a

minimaSuma a = minimum [sum xs | xs <- ramas a]

-- (ramas a) es la lista de las ramas del árbol a. Por ejemplo,

-- ghci> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])

-- [[3,5,6],[3,4],[3,7,2],[3,7,1]]

ramas :: Arbol b -> [[b]]

ramas (N x []) = [[x]]

ramas (N x as) = [x : xs | a <- as, xs <- ramas a]

-- 2ª definición

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

minimaSuma2 :: Arbol Int -> Int

minimaSuma2 (N x []) = x

minimaSuma2 (N x as) = x + minimum (map minimaSuma2 as)

Ordenación por una fila

PorJosé A. Alonso 22-diciembre-201629-diciembre-2016

Las matrices se pueden representar por listas de lista. Por ejemplo, la matriz

|1 2 5|

|3 0 7|

|9 1 6|

|6 4 2|

se puede representar por

   ej :: [[Int]]
   ej = [[1,2,5],
         [3,0,7],
         [9,1,6],
         [6,4,2]]

ej :: [[Int]]

ej = [[1,2,5],

[3,0,7],

[9,1,6],

[6,4,2]]

Definir la función

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

1	ordenaPorFila :: Ord a => [[a]] -> Int -> [[a]]

tal que (ordenaPorFila xss k) es la matriz obtenida ordenando xs por los elementos de la fila k. Por ejemplo,

   ordenaPorFila ej 1  ==  [[2,1,5],[0,3,7],[1,9,6],[4,6,2]]
   ordenaPorFila ej 2  ==  [[2,5,1],[0,7,3],[1,6,9],[4,2,6]]
   ordenaPorFila ej 3  ==  [[5,2,1],[7,0,3],[6,1,9],[2,4,6]]

ordenaPorFila ej 1 == [[2,1,5],[0,3,7],[1,9,6],[4,6,2]]

ordenaPorFila ej 2 == [[2,5,1],[0,7,3],[1,6,9],[4,2,6]]

ordenaPorFila ej 3 == [[5,2,1],[7,0,3],[6,1,9],[2,4,6]]

Soluciones

import Data.List (sort, transpose)

ej :: [[Int]]
ej = [[1,2,5],
      [3,0,7],
      [9,1,6],
      [6,4,2]]

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

ordenaPorFila :: Ord a => [[a]] -> Int -> [[a]]
ordenaPorFila xss k =
  transpose (ordenaPorColumna (transpose xss) k)

ordenaPorColumna :: Ord a => [[a]] -> Int -> [[a]]
ordenaPorColumna xss k =
  map snd (sort [(xs!!k,xs) | xs <- xss])

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

ordenaPorFila2 :: Ord a => [[a]] -> Int -> [[a]]
ordenaPorFila2 xss k =
  [[x | (_,x) <- sort $ zip (xss!!k) xs ] | xs <- xss]

import Data.List (sort, transpose)

ej :: [[Int]]

ej = [[1,2,5],

[3,0,7],

[9,1,6],

[6,4,2]]

-- 1ª solución

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

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

ordenaPorFila xss k =

transpose (ordenaPorColumna (transpose xss) k)

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

ordenaPorColumna xss k =

map snd (sort [(xs!!k,xs) | xs <- xss])

-- 2ª solución

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

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

ordenaPorFila2 xss k =

[[x | (_,x) <- sort $ zip (xss!!k) xs ] | xs <- xss]

Ordenación por una columna

PorJosé A. Alonso 20-diciembre-201627-diciembre-2016

Las matrices se pueden representar por listas de lista. Por ejemplo, la matriz

|1 2 5|

|3 0 7|

|9 1 6|

|6 4 2|

se puede representar por

   ej :: [[Int]]
   ej = [[1,2,5],
         [3,0,7],
         [9,1,6],
         [6,4,2]]

ej :: [[Int]]

ej = [[1,2,5],

[3,0,7],

[9,1,6],

[6,4,2]]

Definir la función

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

1	ordenaPor :: Ord a => [[a]] -> Int -> [[a]]

tal que (ordenaPor xss k) es la matriz obtenida ordenando xs por los elementos de la columna k. Por ejemplo,

   ordenaPor ej 0  ==  [[1,2,5],[3,0,7],[6,4,2],[9,1,6]]
   ordenaPor ej 1  ==  [[3,0,7],[9,1,6],[1,2,5],[6,4,2]]
   ordenaPor ej 2  ==  [[6,4,2],[1,2,5],[9,1,6],[3,0,7]]

ordenaPor ej 0 == [[1,2,5],[3,0,7],[6,4,2],[9,1,6]]

ordenaPor ej 1 == [[3,0,7],[9,1,6],[1,2,5],[6,4,2]]

ordenaPor ej 2 == [[6,4,2],[1,2,5],[9,1,6],[3,0,7]]

Soluciones

import Data.List (sort)

ej :: [[Int]]
ej = [[1,2,5],
      [3,0,7],
      [9,1,6],
      [6,4,2]]

-- 1ª definición
ordenaPor :: Ord a => [[a]] -> Int -> [[a]]
ordenaPor xss k =
  map snd (sort [(xs!!k,xs) | xs <- xss])

-- 2ª definición
ordenaPor2 :: Ord a => [[a]] -> Int -> [[a]]
ordenaPor2 xss k =
  map snd (sort (map (\xs -> (xs!!k, xs)) xss))

-- 3ª definición
ordenaPor3 :: Ord a => [[a]] -> Int -> [[a]]
ordenaPor3 xss k =
  map snd (sort [p | p <- zip (map (!!k) xss) xss])

import Data.List (sort)

ej :: [[Int]]

ej = [[1,2,5],

[3,0,7],

[9,1,6],

[6,4,2]]

-- 1ª definición

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

ordenaPor xss k =

map snd (sort [(xs!!k,xs) | xs <- xss])

-- 2ª definición

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

ordenaPor2 xss k =

map snd (sort (map (\xs -> (xs!!k, xs)) xss))

-- 3ª definición

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

ordenaPor3 xss k =

map snd (sort [p | p <- zip (map (!!k) xss) xss])

Selección por posición

PorJosé A. Alonso 19-diciembre-201627-diciembre-2016

Definir la función

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

1	seleccion :: Ord a => [a] -> [Int] -> [a]

tal que (seleccion xs ps) es la lista ordenada de los elementos que ocupan las posiciones indicadas en la lista ps. Por ejemplo,

   seleccion [6,2,4,7] [2,0]      ==  [4,6]
   seleccion ['a'..'z'] [0,2..10] ==  "acegik"

1 2	seleccion [6,2,4,7] [2,0] == [4,6] seleccion ['a'..'z'] [0,2..10] == "acegik"

Soluciones

import Data.List (sort)

-- 1ª definición
seleccion :: Ord a => [a] -> [Int] -> [a]
seleccion xs ps =
  sort [x | (x,n) <- zip xs [0..]
          , n `elem` ps]

-- 2ª definición
seleccion2 :: Ord a => [a] -> [Int] -> [a]
seleccion2 xs = sort . map (xs!!)

import Data.List (sort)

-- 1ª definición

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

seleccion xs ps =

sort [x | (x,n) <- zip xs [0..]

, n `elem` ps]

-- 2ª definición

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

seleccion2 xs = sort . map (xs!!)

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencia

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico