El mes de marzo en Exercitium (Ejercicios con Haskell y Python)

Durante el mes de marzo he publicado en Exercitium las soluciones de los siguientes problemas:

1. Reiteración de suma de consecutivos
2. Producto de los elementos de la diagonal principal
3. Reconocimiento de potencias de 4
4. Exponente en la factorización
5. Mayor órbita de la sucesión de Collatz
6. Máximos locales

A continuación se muestran las soluciones.

1. Reiteración de suma de consecutivos

La reiteración de la suma de los elementos consecutivos de la lista [1,5,3] es 14 como se explica en el siguiente diagrama

1 + 5 = 6

==> 14

5 + 3 = 8

y la de la lista [1,5,3,4] es 29 como se explica en el siguiente diagrama

   1 + 5 = 6
             \
              ==> 14
             /       \
   5 + 3 = 8          ==> 29
             \       /
              ==> 15
             /
   3 + 4 = 7

1 + 5 = 6

==> 14

/ \

5 + 3 = 8 ==> 29

\ /

==> 15

3 + 4 = 7

Definir la función

   sumaReiterada :: Num a => [a] -> a

1	sumaReiterada :: Num a => [a] -> a

tal que (sumaReiterada xs) es la suma reiterada de los elementos consecutivos de la lista no vacía xs. Por ejemplo,

   sumaReiterada [1,5,3]    ==  14
   sumaReiterada [1,5,3,4]  ==  29

1 2	sumaReiterada [1,5,3] == 14 sumaReiterada [1,5,3,4] == 29

1. Soluciones en Haskell

module Reiteracion_de_suma_de_consecutivos where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

sumaReiterada1 :: Num a => [a] -> a
sumaReiterada1 [x] = x
sumaReiterada1 xs  = sumaReiterada1 [x+y | (x,y) <- consecutivos xs]

-- (consecutivos xs) es la lista de pares de elementos consecutivos de
-- xs. Por ejemplo,
--    consecutivos [1,5,3,4]  ==  [(1,5),(5,3),(3,4)]
consecutivos :: [a] -> [(a,a)]
consecutivos xs = zip xs (tail xs)

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

sumaReiterada2 :: Num a => [a] -> a
sumaReiterada2 [x] = x
sumaReiterada2 xs  = sumaReiterada2 (sumaConsecutivos xs)

-- (sumaConsecutivos xs) es la suma de los de pares de elementos
-- consecutivos de xs. Por ejemplo,
--    sumaConsecutivos [1,5,3,4]   ==  [6,8,7]
sumaConsecutivos :: Num a => [a] -> [a]
sumaConsecutivos xs = zipWith (+) xs (tail xs)

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

sumaReiterada3 :: Num a => [a] -> a
sumaReiterada3 [x] = x
sumaReiterada3 xs  = sumaReiterada3 (zipWith (+) xs (tail xs))

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

sumaReiterada4 :: Num a => [a] -> a
sumaReiterada4 [x]    = x
sumaReiterada4 (x:xs) = sumaReiterada4 (zipWith (+) (x:xs) xs)

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

sumaReiterada5 :: Num a => [a] -> a
sumaReiterada5 [x]       = x
sumaReiterada5 xs@(_:ys) = sumaReiterada5 (zipWith (+) xs ys)

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

sumaReiterada6 :: Num a => [a] -> a
sumaReiterada6 xs =
  head (head (dropWhile noEsUnitaria (iterate sumaConsecutivos xs)))

-- (noEsUnitaria xs) se verifica si la lista xs no tiene sólo un
-- elemento. Por ejemplo,
--    noEsUnitaria []     ==  True
--    noEsUnitaria [7,5]  ==  True
--    noEsUnitaria [7]    ==  False
noEsUnitaria :: [a] -> Bool
noEsUnitaria [_] = False
noEsUnitaria _   = True

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

sumaReiterada7 :: Num a => [a] -> a
sumaReiterada7 =
  head . head . dropWhile (not . null . tail) . iterate sumaConsecutivos

-- 8ª solución
-- ===========

sumaReiterada8 :: Num a => [a] -> a
sumaReiterada8 =
  head . head . dropWhile (not . null . tail) . iterate (zipWith (+) =<< tail)

-- 9ª solución
-- ===========

sumaReiterada9 :: Num a => [a] -> a
sumaReiterada9 = head . until ((==1) . length) (zipWith (+) <*> tail)

-- 10ª solución
-- ===========

sumaReiterada10 :: Num a => [a] -> a
sumaReiterada10 xs =
  sum (zipWith (*) xs (map fromIntegral (pascal !! (length xs - 1))))

-- pascal es la lista de las filas del triángulo de Pascal. Por ejemplo,
--    λ> take 7 pascal
--    [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]]
pascal :: [[Integer]]
pascal = [1] : map f pascal
  where f xs = zipWith (+) (0:xs) (xs++[0])

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Integer] -> Integer) -> Spec
specG sumaReiterada = do
  it "e1" $
    sumaReiterada [1,5,3] `shouldBe` 14
  it "e2" $
    sumaReiterada [1,5,3,4] `shouldBe` 29

spec :: Spec
spec = do
  describe "def. 1" $ specG sumaReiterada1
  describe "def. 2" $ specG sumaReiterada2
  describe "def. 3" $ specG sumaReiterada3
  describe "def. 4" $ specG sumaReiterada4
  describe "def. 5" $ specG sumaReiterada5
  describe "def. 6" $ specG sumaReiterada6
  describe "def. 7" $ specG sumaReiterada7
  describe "def. 8" $ specG sumaReiterada8
  describe "def. 9" $ specG sumaReiterada9
  describe "def. 10" $ specG sumaReiterada10

-- La verificación es
--    λ> verifica
--
--    20 examples, 0 failures

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

-- La propiedad es
prop_sumaReiterada :: [Integer] -> Property
prop_sumaReiterada xs =
  not (null xs) ==>
  all (== (sumaReiterada1 xs))
      [f xs | f <- [sumaReiterada2,
                    sumaReiterada3,
                    sumaReiterada4,
                    sumaReiterada5,
                    sumaReiterada6,
                    sumaReiterada7,
                    sumaReiterada8,
                    sumaReiterada9,
                    sumaReiterada10 ]]

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

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

-- La comparación es
--    λ> length (show (sumaReiterada1 [1..4000]))
--    1208
--    (4.84 secs, 4,444,754,000 bytes)
--    λ> length (show (sumaReiterada2 [1..4000]))
--    1208
--    (3.07 secs, 3,332,858,616 bytes)
--    λ> length (show (sumaReiterada3 [1..4000]))
--    1208
--    (3.04 secs, 3,270,112,112 bytes)
--    λ> length (show (sumaReiterada4 [1..4000]))
--    1208
--    (3.05 secs, 3,332,857,768 bytes)
--    λ> length (show (sumaReiterada5 [1..4000]))
--    1208
--    (3.08 secs, 3,332,570,672 bytes)
--    λ> length (show (sumaReiterada6 [1..4000]))
--    1208
--    (3.03 secs, 3,270,469,704 bytes)
--    λ> length (show (sumaReiterada7 [1..4000]))
--    1208
--    (3.03 secs, 3,270,598,416 bytes)
--    λ> length (show (sumaReiterada8 [1..4000]))
--    1208
--    (3.14 secs, 3,202,183,352 bytes)
--    λ> length (show (sumaReiterada9 [1..4000]))
--    1208
--    (3.71 secs, 2,869,137,232 bytes)
--    λ> length (show (sumaReiterada10 [1..4000]))
--    1208
--    (6.48 secs, 4,621,303,752 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

module Reiteracion_de_suma_de_consecutivos where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

import Test.QuickCheck

-- 1ª solución

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

sumaReiterada1 :: Num a => [a] -> a

sumaReiterada1 [x] = x

sumaReiterada1 xs = sumaReiterada1 [x+y | (x,y) <- consecutivos xs]

-- (consecutivos xs) es la lista de pares de elementos consecutivos de

-- xs. Por ejemplo,

-- consecutivos [1,5,3,4] == [(1,5),(5,3),(3,4)]

consecutivos :: [a] -> [(a,a)]

consecutivos xs = zip xs (tail xs)

-- 2ª solución

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

sumaReiterada2 :: Num a => [a] -> a

sumaReiterada2 [x] = x

sumaReiterada2 xs = sumaReiterada2 (sumaConsecutivos xs)

-- (sumaConsecutivos xs) es la suma de los de pares de elementos

-- consecutivos de xs. Por ejemplo,

-- sumaConsecutivos [1,5,3,4] == [6,8,7]

sumaConsecutivos :: Num a => [a] -> [a]

sumaConsecutivos xs = zipWith (+) xs (tail xs)

-- 3ª solución

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

sumaReiterada3 :: Num a => [a] -> a

sumaReiterada3 [x] = x

sumaReiterada3 xs = sumaReiterada3 (zipWith (+) xs (tail xs))

-- 4ª solución

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

sumaReiterada4 :: Num a => [a] -> a

sumaReiterada4 [x] = x

sumaReiterada4 (x:xs) = sumaReiterada4 (zipWith (+) (x:xs) xs)

-- 5ª solución

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

sumaReiterada5 :: Num a => [a] -> a

sumaReiterada5 [x] = x

sumaReiterada5 xs@(_:ys) = sumaReiterada5 (zipWith (+) xs ys)

-- 6ª solución

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

sumaReiterada6 :: Num a => [a] -> a

sumaReiterada6 xs =

head (head (dropWhile noEsUnitaria (iterate sumaConsecutivos xs)))

-- (noEsUnitaria xs) se verifica si la lista xs no tiene sólo un

-- elemento. Por ejemplo,

-- noEsUnitaria [] == True

-- noEsUnitaria [7,5] == True

-- noEsUnitaria [7] == False

noEsUnitaria :: [a] -> Bool

noEsUnitaria [_] = False

noEsUnitaria _ = True

-- 7ª solución

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

sumaReiterada7 :: Num a => [a] -> a

sumaReiterada7 =

head . head . dropWhile (not . null . tail) . iterate sumaConsecutivos

-- 8ª solución

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

sumaReiterada8 :: Num a => [a] -> a

sumaReiterada8 =

head . head . dropWhile (not . null . tail) . iterate (zipWith (+) =<< tail)

-- 9ª solución

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

sumaReiterada9 :: Num a => [a] -> a

sumaReiterada9 = head . until ((==1) . length) (zipWith (+) <*> tail)

-- 10ª solución

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

sumaReiterada10 :: Num a => [a] -> a

sumaReiterada10 xs =

sum (zipWith (*) xs (map fromIntegral (pascal !! (length xs - 1))))

-- pascal es la lista de las filas del triángulo de Pascal. Por ejemplo,

-- λ> take 7 pascal

-- [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]]

pascal :: [[Integer]]

pascal = [1] : map f pascal

where f xs = zipWith (+) (0:xs) (xs++[0])

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: ([Integer] -> Integer) -> Spec

specG sumaReiterada = do

it "e1" $

sumaReiterada [1,5,3] `shouldBe` 14

it "e2" $

sumaReiterada [1,5,3,4] `shouldBe` 29

spec :: Spec

spec = do

describe "def. 1" $ specG sumaReiterada1

describe "def. 2" $ specG sumaReiterada2

describe "def. 3" $ specG sumaReiterada3

describe "def. 4" $ specG sumaReiterada4

describe "def. 5" $ specG sumaReiterada5

describe "def. 6" $ specG sumaReiterada6

describe "def. 7" $ specG sumaReiterada7

describe "def. 8" $ specG sumaReiterada8

describe "def. 9" $ specG sumaReiterada9

describe "def. 10" $ specG sumaReiterada10

-- La verificación es

-- λ> verifica

-- 20 examples, 0 failures

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_sumaReiterada :: [Integer] -> Property

prop_sumaReiterada xs =

not (null xs) ==>

all (== (sumaReiterada1 xs))

[f xs | f <- [sumaReiterada2,

sumaReiterada3,

sumaReiterada4,

sumaReiterada5,

sumaReiterada6,

sumaReiterada7,

sumaReiterada8,

sumaReiterada9,

sumaReiterada10 ]]

-- La comprobación es

-- λ> quickCheck prop_sumaReiterada

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (show (sumaReiterada1 [1..4000]))

-- 1208

-- (4.84 secs, 4,444,754,000 bytes)

-- λ> length (show (sumaReiterada2 [1..4000]))

-- 1208

-- (3.07 secs, 3,332,858,616 bytes)

-- λ> length (show (sumaReiterada3 [1..4000]))

-- 1208

-- (3.04 secs, 3,270,112,112 bytes)

-- λ> length (show (sumaReiterada4 [1..4000]))

-- 1208

-- (3.05 secs, 3,332,857,768 bytes)

-- λ> length (show (sumaReiterada5 [1..4000]))

-- 1208

-- (3.08 secs, 3,332,570,672 bytes)

-- λ> length (show (sumaReiterada6 [1..4000]))

-- 1208

-- (3.03 secs, 3,270,469,704 bytes)

-- λ> length (show (sumaReiterada7 [1..4000]))

-- 1208

-- (3.03 secs, 3,270,598,416 bytes)

-- λ> length (show (sumaReiterada8 [1..4000]))

-- 1208

-- (3.14 secs, 3,202,183,352 bytes)

-- λ> length (show (sumaReiterada9 [1..4000]))

-- 1208

-- (3.71 secs, 2,869,137,232 bytes)

-- λ> length (show (sumaReiterada10 [1..4000]))

-- 1208

-- (6.48 secs, 4,621,303,752 bytes)

2. Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')
setrecursionlimit(10**6)

# 1ª solución
# ===========

# consecutivos(xs) es la lista de pares de elementos consecutivos de
# xs. Por ejemplo,
#    consecutivos([1,5,3,4])  ==  [(1,5),(5,3),(3,4)]
def consecutivos(xs: list[A]) -> list[tuple[A, A]]:
    return list(zip(xs, xs[1:]))

def sumaReiterada1(xs: list[int]) -> int:
    if len(xs) == 1:
        return xs[0]
    return sumaReiterada1([x + y for (x, y) in consecutivos(xs)])

# 2ª solución
# ===========

# sumaConsecutivos(xs) es la suma de los de pares de elementos
# consecutivos de xs. Por ejemplo,
#    sumaConsecutivos([1,5,3,4])   ==  [6,8,7]
def sumaConsecutivos(xs : list[int]) -> list[int]:
    return [x + y for (x, y) in list(zip(xs, xs[1:]))]

def sumaReiterada2(xs: list[int]) -> int:
    if len(xs) == 1:
        return xs[0]
    return sumaReiterada2(sumaConsecutivos(xs))

# 3ª solución
# ===========

def sumaReiterada3(xs: list[int]) -> int:
    if len(xs) == 1:
        return xs[0]
    return sumaReiterada3([x + y for (x, y) in list(zip(xs, xs[1:]))])

# Verificación
# ============

def test_sumaReiterada() -> None:
    for sumaReiterada in [sumaReiterada1, sumaReiterada2,
                          sumaReiterada3]:
        assert sumaReiterada([1,5,3]) == 14
        assert sumaReiterada([1,5,3,4]) == 29
    print("Verificado")

# La verificación es
#    >>> test_sumaReiterada()
#    Verificado

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.lists(st.integers(), min_size=1))
def test_sumaReiterada_equiv(xs: list[int]) -> None:
    r = sumaReiterada1(xs)
    assert sumaReiterada2(xs) == r
    assert sumaReiterada3(xs) == r

# La comprobación es
#    >>> test_sumaReiterada_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('sumaReiterada1(range(4000))')
#    2.18 segundos
#    >>> tiempo('sumaReiterada2(range(4000))')
#    1.90 segundos
#    >>> tiempo('sumaReiterada3(range(4000))')
#    1.97 segundos

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

setrecursionlimit(10**6)

# 1ª solución

# ===========

# consecutivos(xs) es la lista de pares de elementos consecutivos de

# xs. Por ejemplo,

# consecutivos([1,5,3,4]) == [(1,5),(5,3),(3,4)]

def consecutivos(xs: list[A]) -> list[tuple[A, A]]:

return list(zip(xs, xs[1:]))

def sumaReiterada1(xs: list[int]) -> int:

if len(xs) == 1:

return xs[0]

return sumaReiterada1([x + y for (x, y) in consecutivos(xs)])

# 2ª solución

# ===========

# sumaConsecutivos(xs) es la suma de los de pares de elementos

# consecutivos de xs. Por ejemplo,

# sumaConsecutivos([1,5,3,4]) == [6,8,7]

def sumaConsecutivos(xs : list[int]) -> list[int]:

return [x + y for (x, y) in list(zip(xs, xs[1:]))]

def sumaReiterada2(xs: list[int]) -> int:

if len(xs) == 1:

return xs[0]

return sumaReiterada2(sumaConsecutivos(xs))

# 3ª solución

# ===========

def sumaReiterada3(xs: list[int]) -> int:

if len(xs) == 1:

return xs[0]

return sumaReiterada3([x + y for (x, y) in list(zip(xs, xs[1:]))])

# Verificación

# ============

def test_sumaReiterada() -> None:

for sumaReiterada in [sumaReiterada1, sumaReiterada2,

sumaReiterada3]:

assert sumaReiterada([1,5,3]) == 14

assert sumaReiterada([1,5,3,4]) == 29

print("Verificado")

# La verificación es

# >>> test_sumaReiterada()

# Verificado

# Equivalencia de las definiciones

# ================================

# La propiedad es

@given(st.lists(st.integers(), min_size=1))

def test_sumaReiterada_equiv(xs: list[int]) -> None:

r = sumaReiterada1(xs)

assert sumaReiterada2(xs) == r

assert sumaReiterada3(xs) == r

# La comprobación es

# >>> test_sumaReiterada_equiv()

# >>>

# Comparación de eficiencia

# =========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('sumaReiterada1(range(4000))')

# 2.18 segundos

# >>> tiempo('sumaReiterada2(range(4000))')

# 1.90 segundos

# >>> tiempo('sumaReiterada3(range(4000))')

# 1.97 segundos

2. Producto de los elementos de la diagonal principal

Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.

Definir la función

   productoDiagonalPrincipal :: Num a => [[a]] -> a

1	productoDiagonalPrincipal :: Num a => [[a]] -> a

tal que (productoDiagonalPrincipal xss) es el producto de los elementos de la diagonal principal de la matriz cuadrada xss. Por ejemplo,

   productoDiagonal [[3,5,2],[4,7,1],[6,9,8]]  ==  168
   productoDiagonal (replicate 5 [1..5])       ==  120
   length (show (productoDiagonal (replicate 30000 [1..30000])))  ==  121288

productoDiagonal [[3,5,2],[4,7,1],[6,9,8]] == 168

productoDiagonal (replicate 5 [1..5]) == 120

length (show (productoDiagonal (replicate 30000 [1..30000]))) == 121288

1. Soluciones en Haskell

module Producto_de_los_elementos_de_la_diagonal_principal where

import Data.List (genericReplicate)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

productoDiagonal1 :: Num a => [[a]] -> a
productoDiagonal1 xss = product (diagonal1 xss)

-- (diagonal1 xss) es la diagonal de la matriz xss. Por ejemplo,
--    diagonal1 [[3,5,2],[4,7,1],[6,9,0]]  ==  [3,7,0]
--    diagonal1 [[3,5],[4,7],[6,9]]        ==  [3,7]
--    diagonal1 [[3,5,2],[4,7,1]]          ==  [3,7]
diagonal1 :: [[a]] -> [a]
diagonal1 ((x:_):xss) = x : diagonal1 (map tail xss)
diagonal1 _           = []

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

productoDiagonal2 :: Num a => [[a]] -> a
productoDiagonal2 = product . diagonal1

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

productoDiagonal3 :: Num a => [[a]] -> a
productoDiagonal3 = product . diagonal3

diagonal3 :: [[a]] -> [a]
diagonal3 xss = [xs !! k | (xs,k) <- zip xss [0..n]]
  where n = length (head xss) - 1

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

productoDiagonal4 :: Num a => [[a]] -> a
productoDiagonal4 []          = 1
productoDiagonal4 [[]]        = 1
productoDiagonal4 ((x:_):xss) = x * productoDiagonal4 (map tail xss)

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

productoDiagonal5 :: Num a => [[a]] -> a
productoDiagonal5 xss = product (zipWith (!!) xss [0..k])
  where m = length xss
        n = length (head xss)
        k = min m n - 1

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([[Integer]] -> Integer) -> Spec
specG productoDiagonal = do
  it "e1" $
    productoDiagonal [[3,5,2],[4,7,1],[6,9,8]]  `shouldBe`  168
  it "e2" $
    productoDiagonal (replicate 5 [1..5])       `shouldBe`  120

spec :: Spec
spec = do
  describe "def. 1" $ specG productoDiagonal1
  describe "def. 2" $ specG productoDiagonal2
  describe "def. 3" $ specG productoDiagonal3
  describe "def. 4" $ specG productoDiagonal4
  describe "def. 5" $ specG productoDiagonal5

-- La verificación es
--    λ> verifica
--
--    10 examples, 0 failures

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

ejemplo :: Integer -> [[Integer]]
ejemplo n = genericReplicate n [1..n]

-- La comparación es
--    λ> length (show (productoDiagonal1 (ejemplo 7000)))
--    23878
--    (1.23 secs, 3,396,129,424 bytes)
--    λ> length (show (productoDiagonal2 (ejemplo 7000)))
--    23878
--    (0.94 secs, 3,396,127,680 bytes)
--    λ> length (show (productoDiagonal3 (ejemplo 7000)))
--    23878
--    (0.09 secs, 44,841,864 bytes)
--    λ> length (show (productoDiagonal4 (ejemplo 7000)))
--    23878
--    (0.96 secs, 3,614,137,840 bytes)
--    λ> length (show (productoDiagonal5 (ejemplo 7000)))
--    23878
--    (0.07 secs, 44,168,984 bytes)
--
--    λ> length (show (productoDiagonal3 (ejemplo 70000)))
--    308760
--    (8.26 secs, 5,359,752,408 bytes)
--    λ> length (show (productoDiagonal5 (ejemplo 70000)))
--    308760
--    (9.34 secs, 5,353,035,656 bytes)

100

101

102

103

104

105

106

107

module Producto_de_los_elementos_de_la_diagonal_principal where

import Data.List (genericReplicate)

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución

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

productoDiagonal1 :: Num a => [[a]] -> a

productoDiagonal1 xss = product (diagonal1 xss)

-- (diagonal1 xss) es la diagonal de la matriz xss. Por ejemplo,

-- diagonal1 [[3,5,2],[4,7,1],[6,9,0]] == [3,7,0]

-- diagonal1 [[3,5],[4,7],[6,9]] == [3,7]

-- diagonal1 [[3,5,2],[4,7,1]] == [3,7]

diagonal1 :: [[a]] -> [a]

diagonal1 ((x:_):xss) = x : diagonal1 (map tail xss)

diagonal1 _ = []

-- 2ª solución

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

productoDiagonal2 :: Num a => [[a]] -> a

productoDiagonal2 = product . diagonal1

-- 3ª solución

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

productoDiagonal3 :: Num a => [[a]] -> a

productoDiagonal3 = product . diagonal3

diagonal3 :: [[a]] -> [a]

diagonal3 xss = [xs !! k | (xs,k) <- zip xss [0..n]]

where n = length (head xss) - 1

-- 4ª solución

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

productoDiagonal4 :: Num a => [[a]] -> a

productoDiagonal4 [] = 1

productoDiagonal4 [[]] = 1

productoDiagonal4 ((x:_):xss) = x * productoDiagonal4 (map tail xss)

-- 5ª solución

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

productoDiagonal5 :: Num a => [[a]] -> a

productoDiagonal5 xss = product (zipWith (!!) xss [0..k])

where m = length xss

n = length (head xss)

k = min m n - 1

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: ([[Integer]] -> Integer) -> Spec

specG productoDiagonal = do

it "e1" $

productoDiagonal [[3,5,2],[4,7,1],[6,9,8]] `shouldBe` 168

it "e2" $

productoDiagonal (replicate 5 [1..5]) `shouldBe` 120

spec :: Spec

spec = do

describe "def. 1" $ specG productoDiagonal1

describe "def. 2" $ specG productoDiagonal2

describe "def. 3" $ specG productoDiagonal3

describe "def. 4" $ specG productoDiagonal4

describe "def. 5" $ specG productoDiagonal5

-- La verificación es

-- λ> verifica

-- 10 examples, 0 failures

-- Comparación de eficiencia

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

ejemplo :: Integer -> [[Integer]]

ejemplo n = genericReplicate n [1..n]

-- La comparación es

-- λ> length (show (productoDiagonal1 (ejemplo 7000)))

-- 23878

-- (1.23 secs, 3,396,129,424 bytes)

-- λ> length (show (productoDiagonal2 (ejemplo 7000)))

-- 23878

-- (0.94 secs, 3,396,127,680 bytes)

-- λ> length (show (productoDiagonal3 (ejemplo 7000)))

-- 23878

-- (0.09 secs, 44,841,864 bytes)

-- λ> length (show (productoDiagonal4 (ejemplo 7000)))

-- 23878

-- (0.96 secs, 3,614,137,840 bytes)

-- λ> length (show (productoDiagonal5 (ejemplo 7000)))

-- 23878

-- (0.07 secs, 44,168,984 bytes)

-- λ> length (show (productoDiagonal3 (ejemplo 70000)))

-- 308760

-- (8.26 secs, 5,359,752,408 bytes)

-- λ> length (show (productoDiagonal5 (ejemplo 70000)))

-- 308760

-- (9.34 secs, 5,353,035,656 bytes)

2. Soluciones en Python

from functools import reduce
from operator import mul
from sys import set_int_max_str_digits, setrecursionlimit
from timeit import Timer, default_timer

set_int_max_str_digits(10**6)
setrecursionlimit(10**6)

# 1ª solución
# ===========

# diagonal1(xss) es la diagonal de la matriz xss. Por ejemplo,
#    diagonal1([[3,5,2],[4,7,1],[6,9,0]])  ==  [3,7,0]
#    diagonal1([[3,5],[4,7],[6,9]])        ==  [3,7]
#    diagonal1([[3,5,2],[4,7,1]])          ==  [3,7]
def diagonal1(xss: list[list[int]]) -> list[int]:
    if not xss:
        return []
    if not xss[0]:
        return []
    return [xss[0][0]] + diagonal1(list(map((lambda ys : ys[1:]), xss[1:])))

def producto(xs: list[int]) -> int:
    return reduce(mul, xs)

def productoDiagonal1(xss: list[list[int]]) -> int:
    return producto(diagonal1(xss))

# 2ª solución
# ===========

def diagonal2(xss: list[list[int]]) -> list[int]:
    n = min(len(xss), len(xss[0]))
    return [xss[k][k] for k in range(n)]

def productoDiagonal2(xss: list[list[int]]) -> int:
    return producto(diagonal2(xss))

# 3ª solución
# ===========

def productoDiagonal3(xss: list[list[int]]) -> int:
    if not xss:
        return 1
    if not xss[0]:
        return 1
    return xss[0][0] * productoDiagonal3(list(map((lambda ys : ys[1:]), xss[1:])))

# Verificación
# ============

def test_productoDiagonal() -> None:
    for productoDiagonal in [productoDiagonal1, productoDiagonal2,
                             productoDiagonal3]:
        assert productoDiagonal([[3,5,2],[4,7,1],[6,9,8]]) == 168
        assert productoDiagonal([[1, 2, 3, 4, 5]]*5) == 120
    print("Verificado")

# La verificación es
#    >>> test_productoDiagonal()
#    Verificado

# Comparación de eficiencia
# =========================

# ejemplo(n) es la matriz con n filas formadas por los números de 1 a
# n. Por ejemplo,
#    >>> ejemplo(3)
#    [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
def ejemplo(n: int) -> list[list[int]]:
    return [list(range(1, n+1))]*n

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('productoDiagonal1(ejemplo(1200))')
#    1.97 segundos
#    >>> tiempo('productoDiagonal2(ejemplo(1200))')
#    0.00 segundos
#    >>> tiempo('productoDiagonal3(ejemplo(1200))')
#    1.56 segundos

from functools import reduce

from operator import mul

from sys import set_int_max_str_digits, setrecursionlimit

from timeit import Timer, default_timer

set_int_max_str_digits(10**6)

setrecursionlimit(10**6)

# 1ª solución

# ===========

# diagonal1(xss) es la diagonal de la matriz xss. Por ejemplo,

# diagonal1([[3,5,2],[4,7,1],[6,9,0]]) == [3,7,0]

# diagonal1([[3,5],[4,7],[6,9]]) == [3,7]

# diagonal1([[3,5,2],[4,7,1]]) == [3,7]

def diagonal1(xss: list[list[int]]) -> list[int]:

if not xss:

return []

if not xss[0]:

return []

return [xss[0][0]] + diagonal1(list(map((lambda ys : ys[1:]), xss[1:])))

def producto(xs: list[int]) -> int:

return reduce(mul, xs)

def productoDiagonal1(xss: list[list[int]]) -> int:

return producto(diagonal1(xss))

# 2ª solución

# ===========

def diagonal2(xss: list[list[int]]) -> list[int]:

n = min(len(xss), len(xss[0]))

return [xss[k][k] for k in range(n)]

def productoDiagonal2(xss: list[list[int]]) -> int:

return producto(diagonal2(xss))

# 3ª solución

# ===========

def productoDiagonal3(xss: list[list[int]]) -> int:

if not xss:

return 1

if not xss[0]:

return 1

return xss[0][0] * productoDiagonal3(list(map((lambda ys : ys[1:]), xss[1:])))

# Verificación

# ============

def test_productoDiagonal() -> None:

for productoDiagonal in [productoDiagonal1, productoDiagonal2,

productoDiagonal3]:

assert productoDiagonal([[3,5,2],[4,7,1],[6,9,8]]) == 168

assert productoDiagonal([[1, 2, 3, 4, 5]]*5) == 120

print("Verificado")

# La verificación es

# >>> test_productoDiagonal()

# Verificado

# Comparación de eficiencia

# =========================

# ejemplo(n) es la matriz con n filas formadas por los números de 1 a

# n. Por ejemplo,

# >>> ejemplo(3)

# [[1, 2, 3], [1, 2, 3], [1, 2, 3]]

def ejemplo(n: int) -> list[list[int]]:

return [list(range(1, n+1))]*n

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('productoDiagonal1(ejemplo(1200))')

# 1.97 segundos

# >>> tiempo('productoDiagonal2(ejemplo(1200))')

# 0.00 segundos

# >>> tiempo('productoDiagonal3(ejemplo(1200))')

# 1.56 segundos

3. Reconocimiento de potencias de 4

Definir la función

   esPotenciaDe4 :: Integral a => a -> Bool

1	esPotenciaDe4 :: Integral a => a -> Bool

tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,

   esPotenciaDe4 16                ==  True
   esPotenciaDe4 17                ==  False
   esPotenciaDe4 (4^(4*10^5))      ==  True
   esPotenciaDe4 (1 + 4^(4*10^5))  ==  False

esPotenciaDe4 16 == True

esPotenciaDe4 17 == False

esPotenciaDe4 (4^(4*10^5)) == True

esPotenciaDe4 (1 + 4^(4*10^5)) == False

1. Soluciones en Haskell

module Reconocimiento_de_potencias_de_4 where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

esPotenciaDe4_1 :: Integral a => a -> Bool
esPotenciaDe4_1 0 = False
esPotenciaDe4_1 1 = True
esPotenciaDe4_1 n = n `mod` 4 == 0 && esPotenciaDe4_1 (n `div` 4)

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

esPotenciaDe4_2 :: Integral a => a -> Bool
esPotenciaDe4_2 n = n `pertenece` potenciasDe4

-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,
--    take 5 potenciasDe4  ==  [1,4,16,64,256]
potenciasDe4 :: Integral a => [a]
potenciasDe4 = [4^x | x <- [0..]]

-- (pertenece x ys) se verifica si x pertenece a la lista ordenada
-- (posiblemente infinita xs). Por ejemplo,
--    pertenece 8 [2,4..]  ==  True
--    pertenece 9 [2,4..]  ==  False
pertenece :: Integral a => a -> [a] -> Bool
pertenece x ys = x == head (dropWhile (<x) ys)

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

esPotenciaDe4_3 :: Integral a => a -> Bool
esPotenciaDe4_3 n = n `pertenece` potenciasDe4_2

-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,
--    take 5 potenciasDe4  ==  [1,4,16,64,256]
potenciasDe4_2 :: Integral a => [a]
potenciasDe4_2 = iterate (*4) 1

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

esPotenciaDe4_4 :: Integral n => n -> Bool
esPotenciaDe4_4 n =
  n == head (dropWhile (<n) (iterate (*4) 1))

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

esPotenciaDe4_5 :: Integral n => n -> Bool
esPotenciaDe4_5 n =
  n == until (>=n) (*4) 1

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Bool) -> Spec
specG esPotenciaDe4 = do
  it "e1" $
    esPotenciaDe4 16 `shouldBe` True
  it "e2" $
    esPotenciaDe4 17 `shouldBe` False

spec :: Spec
spec = do
  describe "def. 1" $ specG esPotenciaDe4_1
  describe "def. 2" $ specG esPotenciaDe4_2
  describe "def. 3" $ specG esPotenciaDe4_3
  describe "def. 4" $ specG esPotenciaDe4_4
  describe "def. 5" $ specG esPotenciaDe4_5

-- La verificación es
--    λ> verifica
--
--    10 examples, 0 failures

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

-- La comparación es
--    λ> esPotenciaDe4_1 (4^(4*10^4))
--    True
--    (0.18 secs, 233,903,248 bytes)
--    λ> esPotenciaDe4_2 (4^(4*10^4))
--    True
--    (2.01 secs, 756,125,712 bytes)
--    λ> esPotenciaDe4_3 (4^(4*10^4))
--    True
--    (0.05 secs, 212,019,464 bytes)
--    λ> esPotenciaDe4_4 (4^(4*10^4))
--    True
--    (0.05 secs, 212,019,368 bytes)
--    λ> esPotenciaDe4_5 (4^(4*10^4))
--    True
--    (0.07 secs, 209,779,888 bytes)
--
--    λ> esPotenciaDe4_3 (4^(2*10^5))
--    True
--    (0.64 secs, 5,184,667,280 bytes)
--    λ> esPotenciaDe4_4 (4^(2*10^5))
--    True
--    (0.64 secs, 5,184,667,200 bytes)
--    λ> esPotenciaDe4_5 (4^(2*10^5))
--    True
--    (0.63 secs, 5,173,467,656 bytes)
--
--    λ> esPotenciaDe4_3 (4^(4*10^5))
--    True
--    (2.27 secs, 20,681,727,464 bytes)
--    λ> esPotenciaDe4_4 (4^(4*10^5))
--    True
--    (2.30 secs, 20,681,727,320 bytes)
--    λ> esPotenciaDe4_5 (4^(4*10^5))
--    True
--    (2.28 secs, 20,659,327,352 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

module Reconocimiento_de_potencias_de_4 where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución

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

esPotenciaDe4_1 :: Integral a => a -> Bool

esPotenciaDe4_1 0 = False

esPotenciaDe4_1 1 = True

esPotenciaDe4_1 n = n `mod` 4 == 0 && esPotenciaDe4_1 (n `div` 4)

-- 2ª solución

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

esPotenciaDe4_2 :: Integral a => a -> Bool

esPotenciaDe4_2 n = n `pertenece` potenciasDe4

-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,

-- take 5 potenciasDe4 == [1,4,16,64,256]

potenciasDe4 :: Integral a => [a]

potenciasDe4 = [4^x | x <- [0..]]

-- (pertenece x ys) se verifica si x pertenece a la lista ordenada

-- (posiblemente infinita xs). Por ejemplo,

-- pertenece 8 [2,4..] == True

-- pertenece 9 [2,4..] == False

pertenece :: Integral a => a -> [a] -> Bool

pertenece x ys = x == head (dropWhile (<x) ys)

-- 3ª solución

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

esPotenciaDe4_3 :: Integral a => a -> Bool

esPotenciaDe4_3 n = n `pertenece` potenciasDe4_2

-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,

-- take 5 potenciasDe4 == [1,4,16,64,256]

potenciasDe4_2 :: Integral a => [a]

potenciasDe4_2 = iterate (*4) 1

-- 4ª solución

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

esPotenciaDe4_4 :: Integral n => n -> Bool

esPotenciaDe4_4 n =

n == head (dropWhile (<n) (iterate (*4) 1))

-- 5ª solución

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

esPotenciaDe4_5 :: Integral n => n -> Bool

esPotenciaDe4_5 n =

n == until (>=n) (*4) 1

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: (Integer -> Bool) -> Spec

specG esPotenciaDe4 = do

it "e1" $

esPotenciaDe4 16 `shouldBe` True

it "e2" $

esPotenciaDe4 17 `shouldBe` False

spec :: Spec

spec = do

describe "def. 1" $ specG esPotenciaDe4_1

describe "def. 2" $ specG esPotenciaDe4_2

describe "def. 3" $ specG esPotenciaDe4_3

describe "def. 4" $ specG esPotenciaDe4_4

describe "def. 5" $ specG esPotenciaDe4_5

-- La verificación es

-- λ> verifica

-- 10 examples, 0 failures

-- Comparación de eficiencia

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

-- La comparación es

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

-- True

-- (0.18 secs, 233,903,248 bytes)

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

-- True

-- (2.01 secs, 756,125,712 bytes)

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

-- True

-- (0.05 secs, 212,019,464 bytes)

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

-- True

-- (0.05 secs, 212,019,368 bytes)

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

-- True

-- (0.07 secs, 209,779,888 bytes)

-- λ> esPotenciaDe4_3 (4^(2*10^5))

-- True

-- (0.64 secs, 5,184,667,280 bytes)

-- λ> esPotenciaDe4_4 (4^(2*10^5))

-- True

-- (0.64 secs, 5,184,667,200 bytes)

-- λ> esPotenciaDe4_5 (4^(2*10^5))

-- True

-- (0.63 secs, 5,173,467,656 bytes)

-- λ> esPotenciaDe4_3 (4^(4*10^5))

-- True

-- (2.27 secs, 20,681,727,464 bytes)

-- λ> esPotenciaDe4_4 (4^(4*10^5))

-- True

-- (2.30 secs, 20,681,727,320 bytes)

-- λ> esPotenciaDe4_5 (4^(4*10^5))

-- True

-- (2.28 secs, 20,659,327,352 bytes)

2. Soluciones en Python

from itertools import count, dropwhile, islice
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Callable, Iterator

setrecursionlimit(10**6)

# 1ª solución
# ===========

def esPotenciaDe4_1(n: int) -> bool:
    if n == 0:
        return False
    if n == 1:
        return True
    return n % 4 == 0 and esPotenciaDe4_1(n // 4)

# 2ª solución
# ===========

# potenciassDe4() es la lista de las potencias de 4. Por ejemplo,
#    >>> list(islice(potenciasDe4(), 5))
#    [1, 4, 16, 64, 256]
def potenciasDe4() -> Iterator[int]:
    return (4 ** n for n in count())

# pertenece(x, ys) se verifica si x pertenece a la lista ordenada
# (posiblemente infinita xs). Por ejemplo,
#    >>> pertenece(8, count(2, 2))
#    True
#    >>> pertenece(9, count(2, 2))
#    False
def pertenece(x: int, ys: Iterator[int]) -> bool:
    return next(dropwhile(lambda y: y < x, ys), None) == x

def esPotenciaDe4_2(n: int) -> bool:
    return pertenece(n, potenciasDe4())

# 3ª solución
# ===========

# iterate(f, x) es el iterador obtenido aplicando f a x y continuando
# aplicando f al resultado anterior. Por ejemplo,
#    >>> list(islice(iterate(lambda x : 4 * x, 1), 5))
#    [1, 4, 16, 64, 256]
def iterate(f: Callable[[int], int], x: int) -> Iterator[int]:
    r = x
    while True:
        yield r
        r = f(r)

def potenciasDe4_2() -> Iterator[int]:
    return iterate(lambda x : 4 * x, 1)

def esPotenciaDe4_3(n: int) -> bool:
    return pertenece(n, potenciasDe4_2())

# 4ª solución
# ===========

def esPotenciaDe4_4(n: int) -> bool:
    return next(dropwhile(lambda y: y < n,
                          iterate(lambda x : 4 * x, 1)),
                          None) == n

# 5ª solución
# ===========

def esPotenciaDe4_5(n: int) -> bool:
    r = 1
    while r < n:
        r = 4 * r
    return r == n

# Verificación
# ============

def test_esPotenciaDe4() -> None:
    for esPotenciaDe4 in [esPotenciaDe4_1, esPotenciaDe4_2,
                          esPotenciaDe4_3, esPotenciaDe4_4,
                          esPotenciaDe4_5]:
        assert esPotenciaDe4(16)
        assert not esPotenciaDe4(17)
    assert list(islice(potenciasDe4(), 5)) == [1, 4, 16, 64, 256]
    print("Verificado")

# La verificación es
#    >>> test_esPotenciaDe4()
#    Verificado

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('esPotenciaDe4_1(4**(2*10**4))')
#    0.33 segundos
#    >>> tiempo('esPotenciaDe4_2(4**(2*10**4))')
#    0.63 segundos
#    >>> tiempo('esPotenciaDe4_3(4**(2*10**4))')
#    0.04 segundos
#    >>> tiempo('esPotenciaDe4_4(4**(2*10**4))')
#    0.05 segundos
#    >>> tiempo('esPotenciaDe4_5(4**(2*10**4))')
#    0.04 segundos
#
#    >>> tiempo('esPotenciaDe4_3(4**(3*10**5))')
#    2.29 segundos
#    >>> tiempo('esPotenciaDe4_4(4**(3*10**5))')
#    2.28 segundos
#    >>> tiempo('esPotenciaDe4_5(4**(3*10**5))')
#    2.31 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

from itertools import count, dropwhile, islice

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import Callable, Iterator

setrecursionlimit(10**6)

# 1ª solución

# ===========

def esPotenciaDe4_1(n: int) -> bool:

if n == 0:

return False

if n == 1:

return True

return n % 4 == 0 and esPotenciaDe4_1(n // 4)

# 2ª solución

# ===========

# potenciassDe4() es la lista de las potencias de 4. Por ejemplo,

# >>> list(islice(potenciasDe4(), 5))

# [1, 4, 16, 64, 256]

def potenciasDe4() -> Iterator[int]:

return (4 ** n for n in count())

# pertenece(x, ys) se verifica si x pertenece a la lista ordenada

# (posiblemente infinita xs). Por ejemplo,

# >>> pertenece(8, count(2, 2))

# True

# >>> pertenece(9, count(2, 2))

# False

def pertenece(x: int, ys: Iterator[int]) -> bool:

return next(dropwhile(lambda y: y < x, ys), None) == x

def esPotenciaDe4_2(n: int) -> bool:

return pertenece(n, potenciasDe4())

# 3ª solución

# ===========

# iterate(f, x) es el iterador obtenido aplicando f a x y continuando

# aplicando f al resultado anterior. Por ejemplo,

# >>> list(islice(iterate(lambda x : 4 * x, 1), 5))

# [1, 4, 16, 64, 256]

def iterate(f: Callable[[int], int], x: int) -> Iterator[int]:

r = x

while True:

yield r

r = f(r)

def potenciasDe4_2() -> Iterator[int]:

return iterate(lambda x : 4 * x, 1)

def esPotenciaDe4_3(n: int) -> bool:

return pertenece(n, potenciasDe4_2())

# 4ª solución

# ===========

def esPotenciaDe4_4(n: int) -> bool:

return next(dropwhile(lambda y: y < n,

iterate(lambda x : 4 * x, 1)),

None) == n

# 5ª solución

# ===========

def esPotenciaDe4_5(n: int) -> bool:

r = 1

while r < n:

r = 4 * r

return r == n

# Verificación

# ============

def test_esPotenciaDe4() -> None:

for esPotenciaDe4 in [esPotenciaDe4_1, esPotenciaDe4_2,

esPotenciaDe4_3, esPotenciaDe4_4,

esPotenciaDe4_5]:

assert esPotenciaDe4(16)

assert not esPotenciaDe4(17)

assert list(islice(potenciasDe4(), 5)) == [1, 4, 16, 64, 256]

print("Verificado")

# La verificación es

# >>> test_esPotenciaDe4()

# Verificado

# Comparación de eficiencia

# =========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('esPotenciaDe4_1(4**(2*10**4))')

# 0.33 segundos

# >>> tiempo('esPotenciaDe4_2(4**(2*10**4))')

# 0.63 segundos

# >>> tiempo('esPotenciaDe4_3(4**(2*10**4))')

# 0.04 segundos

# >>> tiempo('esPotenciaDe4_4(4**(2*10**4))')

# 0.05 segundos

# >>> tiempo('esPotenciaDe4_5(4**(2*10**4))')

# 0.04 segundos

# >>> tiempo('esPotenciaDe4_3(4**(3*10**5))')

# 2.29 segundos

# >>> tiempo('esPotenciaDe4_4(4**(3*10**5))')

# 2.28 segundos

# >>> tiempo('esPotenciaDe4_5(4**(3*10**5))')

# 2.31 segundos

4. Exponente en la factorización

Definir la función

   exponente :: Integer -> Integer -> Int

1	exponente :: Integer -> Integer -> Int

tal que (exponente x n) es el exponente de x en la factorización prima de n (se supone que x > 1 y n > 0). Por ejemplo,

   exponente 2 24  ==  3
   exponente 3 24  ==  1
   exponente 6 24  ==  0
   exponente 7 24  ==  0

exponente 2 24 == 3

exponente 3 24 == 1

exponente 6 24 == 0

exponente 7 24 == 0

1. Soluciones en Haskell

module Exponente_en_la_factorizacion where

import Data.Numbers.Primes (primeFactors)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

exponente1 :: Integer -> Integer -> Int
exponente1 x n
  | esPrimo x = aux n
  | otherwise = 0
  where aux m | m `mod` x == 0 = 1 + aux (m `div` x)
              | otherwise      = 0

-- (esPrimo x) se verifica si x es un número primo. Por ejemplo,
--    esPrimo 7  ==  True
--    esPrimo 8  ==  False
esPrimo :: Integer -> Bool
esPrimo x =
  [y | y <- [1..x], x `mod` y == 0] == [1,x]

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

exponente2 :: Integer -> Integer -> Int
exponente2 x n
  | esPrimo x = length (takeWhile (`divisible` x) (iterate (`div` x) n))
  | otherwise = 0

-- (divisible n x) se verifica si n es divisible por x. Por ejemplo,
--    divisible 6 2  ==  True
--    divisible 7 2  ==  False
divisible :: Integer -> Integer -> Bool
divisible n x = n `mod` x == 0

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

exponente3 :: Integer -> Integer -> Int
exponente3 x n =
  length (filter (==x) (primeFactors n))

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Integer -> Int) -> Spec
specG exponente = do
  it "e1" $
    exponente 2 24  `shouldBe`  3
  it "e2" $
    exponente 3 24  `shouldBe`  1
  it "e3" $
    exponente 6 24  `shouldBe`  0
  it "e4" $
    exponente 7 24  `shouldBe`  0

spec :: Spec
spec = do
  describe "def. 1" $ specG exponente1
  describe "def. 2" $ specG exponente2
  describe "def. 3" $ specG exponente3

-- La verificación es
--    λ> verifica
--
--    12 examples, 0 failures

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

-- La propiedad es
prop_exponente :: Integer -> Integer -> Property
prop_exponente x n =
  x > 1 && n > 0 ==>
  exponente1 x n == exponente2 x n &&
  exponente1 x n == exponente3 x n

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

module Exponente_en_la_factorizacion where

import Data.Numbers.Primes (primeFactors)

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

import Test.QuickCheck

-- 1ª solución

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

exponente1 :: Integer -> Integer -> Int

exponente1 x n

| esPrimo x = aux n

| otherwise = 0

where aux m | m `mod` x == 0 = 1 + aux (m `div` x)

| otherwise = 0

-- (esPrimo x) se verifica si x es un número primo. Por ejemplo,

-- esPrimo 7 == True

-- esPrimo 8 == False

esPrimo :: Integer -> Bool

esPrimo x =

[y | y <- [1..x], x `mod` y == 0] == [1,x]

-- 2ª solución

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

exponente2 :: Integer -> Integer -> Int

exponente2 x n

| esPrimo x = length (takeWhile (`divisible` x) (iterate (`div` x) n))

| otherwise = 0

-- (divisible n x) se verifica si n es divisible por x. Por ejemplo,

-- divisible 6 2 == True

-- divisible 7 2 == False

divisible :: Integer -> Integer -> Bool

divisible n x = n `mod` x == 0

-- 3ª solución

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

exponente3 :: Integer -> Integer -> Int

exponente3 x n =

length (filter (==x) (primeFactors n))

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: (Integer -> Integer -> Int) -> Spec

specG exponente = do

it "e1" $

exponente 2 24 `shouldBe` 3

it "e2" $

exponente 3 24 `shouldBe` 1

it "e3" $

exponente 6 24 `shouldBe` 0

it "e4" $

exponente 7 24 `shouldBe` 0

spec :: Spec

spec = do

describe "def. 1" $ specG exponente1

describe "def. 2" $ specG exponente2

describe "def. 3" $ specG exponente3

-- La verificación es

-- λ> verifica

-- 12 examples, 0 failures

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_exponente :: Integer -> Integer -> Property

prop_exponente x n =

x > 1 && n > 0 ==>

exponente1 x n == exponente2 x n &&

exponente1 x n == exponente3 x n

-- La comprobación es

-- λ> quickCheck prop_exponente

-- +++ OK, passed 100 tests.

2. Soluciones en Python

from itertools import takewhile
from typing import Callable, Iterator

from hypothesis import given
from hypothesis import strategies as st
from sympy.ntheory import factorint

# 1ª solución
# ===========

# esPrimo(x) se verifica si x es un número primo. Por ejemplo,
#    esPrimo(7)  ==  True
#    esPrimo(8)  ==  False
def esPrimo(x: int) -> bool:
    return [y for y in range(1, x+1) if x % y == 0] == [1,x]

def exponente1(x: int, n: int) -> int:
    def aux (m: int) -> int:
        if m % x == 0:
            return 1 + aux(m // x)
        return 0
    if esPrimo(x):
        return aux(n)
    return 0

# 2ª solución
# ===========

# iterate(f, x) es el iterador obtenido aplicando f a x y continuando
# aplicando f al resultado anterior. Por ejemplo,
#    >>> list(islice(iterate(lambda x : 4 * x, 1), 5))
#    [1, 4, 16, 64, 256]
def iterate(f: Callable[[int], int], x: int) -> Iterator[int]:
    r = x
    while True:
        yield r
        r = f(r)

# divisible(n, x) se verifica si n es divisible por x. Por ejemplo,
#    divisible(6, 2)  ==  True
#    divisible(7, 2)  ==  False
def divisible(n: int, x: int) -> bool:
    return n % x == 0

def exponente2(x: int, n: int) -> int:
    if esPrimo(x):
        return len(list(takewhile(lambda m : divisible(m, x),
                                  iterate(lambda m : m // x, n))))
    return 0

# 3ª solución
# ===========

def exponente3(x: int, n: int) -> int:
    return factorint(n, multiple = True).count(x)

# Verificación
# ============

def test_exponente() -> None:
    for exponente in [exponente1, exponente2, exponente3]:
        assert exponente(2, 24) == 3
        assert exponente(3, 24) == 1
        assert exponente(6, 24) == 0
        assert exponente(7, 24) == 0
    print("Verificado")

# La verificación es
#    >>> test_exponente()
#    Verificado

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000),
       st.integers(min_value=0, max_value=1000))
def test_exponente_equiv(x: int, n: int) -> None:
    r = exponente1(x, n)
    assert r == exponente2(x, n)
    assert r == exponente3(x, n)

# La comprobación es
#    >>> test_exponente_equiv()
#    >>>

from itertools import takewhile

from typing import Callable, Iterator

from hypothesis import given

from hypothesis import strategies as st

from sympy.ntheory import factorint

# 1ª solución

# ===========

# esPrimo(x) se verifica si x es un número primo. Por ejemplo,

# esPrimo(7) == True

# esPrimo(8) == False

def esPrimo(x: int) -> bool:

return [y for y in range(1, x+1) if x % y == 0] == [1,x]

def exponente1(x: int, n: int) -> int:

def aux (m: int) -> int:

if m % x == 0:

return 1 + aux(m // x)

return 0

if esPrimo(x):

return aux(n)

return 0

# 2ª solución

# ===========

# iterate(f, x) es el iterador obtenido aplicando f a x y continuando

# aplicando f al resultado anterior. Por ejemplo,

# >>> list(islice(iterate(lambda x : 4 * x, 1), 5))

# [1, 4, 16, 64, 256]

def iterate(f: Callable[[int], int], x: int) -> Iterator[int]:

r = x

while True:

yield r

r = f(r)

# divisible(n, x) se verifica si n es divisible por x. Por ejemplo,

# divisible(6, 2) == True

# divisible(7, 2) == False

def divisible(n: int, x: int) -> bool:

return n % x == 0

def exponente2(x: int, n: int) -> int:

if esPrimo(x):

return len(list(takewhile(lambda m : divisible(m, x),

iterate(lambda m : m // x, n))))

return 0

# 3ª solución

# ===========

def exponente3(x: int, n: int) -> int:

return factorint(n, multiple = True).count(x)

# Verificación

# ============

def test_exponente() -> None:

for exponente in [exponente1, exponente2, exponente3]:

assert exponente(2, 24) == 3

assert exponente(3, 24) == 1

assert exponente(6, 24) == 0

assert exponente(7, 24) == 0

print("Verificado")

# La verificación es

# >>> test_exponente()

# Verificado

# Equivalencia de las definiciones

# ================================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000),

st.integers(min_value=0, max_value=1000))

def test_exponente_equiv(x: int, n: int) -> None:

r = exponente1(x, n)

assert r == exponente2(x, n)

assert r == exponente3(x, n)

# La comprobación es

# >>> test_exponente_equiv()

# >>>

5. Mayor órbita de la sucesión de Collatz

Se considera la siguiente operación, aplicable a cualquier número entero positivo:

Si el número es par, se divide entre 2.
Si el número es impar, se multiplica por 3 y se suma 1.

Dado un número cualquiera, podemos calcular su órbita; es decir, las imágenes sucesivas al iterar la función. Por ejemplo, la órbita de 13 es

   13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

1	13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

Si observamos este ejemplo, la órbita de 13 es periódica, es decir,
se repite indefinidamente a partir de un momento dado). La conjetura
de Collatz dice que siempre alcanzaremos el 1 para cualquier número
con el que comencemos. Ejemplos:

Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.
Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Empezando en n = 27, la sucesión tiene 112 pasos, llegando hasta
9232 antes de descender a 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Definir la función

   mayoresGeneradores :: Integer -> [Integer]

1	mayoresGeneradores :: Integer -> [Integer]

tal que (mayoresGeneradores n) es la lista de los números menores o iguales que n cuyas órbitas de Collatz son las de mayor longitud. Por ejemplo,

   mayoresGeneradores 20      ==  [18,19]
   mayoresGeneradores (10^6)  ==  [837799]

1 2	mayoresGeneradores 20 == [18,19] mayoresGeneradores (10^6) == [837799]

1. Soluciones en Haskell

module Mayor_orbita_de_la_sucesion_de_Collatz where

import qualified Data.MemoCombinators as Memo (integral)
import Data.List (genericLength, genericTake)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

mayoresGeneradores1 :: Integer -> [Integer]
mayoresGeneradores1 n =
  [x | (x,y) <- ps, y == m]
  where ps = genericTake n longitudesOrbitas
        m  = maximum (map snd ps)

-- longitudesOrbita es la lista de los números junto a las longitudes de
-- las órbitas de Collatz que generan. Por ejemplo,
--    λ> take 10 longitudesOrbitas
--    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]
longitudesOrbitas :: [(Integer, Integer)]
longitudesOrbitas =
  [(n, genericLength (collatz n)) | n <- [1..]]

-- (siguiente n) es el siguiente de n en la sucesión de Collatz. Por
-- ejemplo,
--    siguiente 13  ==  40
--    siguiente 40  ==  20
siguiente :: Integer -> Integer
siguiente n | even n    = n `div` 2
            | otherwise = 3*n+1

-- (collatz1 n) es la órbita de Collatz de n hasta alcanzar el
-- 1. Por ejemplo,
--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]

-- 1ª definición de collatz
collatz1 :: Integer -> [Integer]
collatz1 1 = [1]
collatz1 n = n : collatz1 (siguiente n)

-- 2ª definición de collatz
collatz2 :: Integer -> [Integer]
collatz2 n = takeWhile (/=1) (iterate siguiente n) ++ [1]

-- Usaremos la 2ª definición de collatz
collatz :: Integer -> [Integer]
collatz = collatz2

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

mayoresGeneradores2 :: Integer -> [Integer]
mayoresGeneradores2 n =
  [x | (x,y) <- ps, y == m]
  where ps = [(x, longitudOrbita x) | x <- [1..n]]
        m  = maximum (map snd ps)

-- (longitudOrbita x) es la longitud de la órbita de x. Por ejemplo,
--    longitudOrbita 13  ==  10
longitudOrbita :: Integer -> Integer
longitudOrbita 1 = 1
longitudOrbita x = 1 + longitudOrbita (siguiente x)

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

mayoresGeneradores3 :: Integer -> [Integer]
mayoresGeneradores3 n =
  [x | (x,y) <- ps, y == m]
  where ps = [(x, longitudOrbita2 x) | x <- [1..n]]
        m  = maximum (map snd ps)

longitudOrbita2 :: Integer -> Integer
longitudOrbita2 = Memo.integral longitudOrbita2'
  where
    longitudOrbita2' 1 = 1
    longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> [Integer]) -> Spec
specG mayoresGeneradores = do
  it "e1" $
    mayoresGeneradores 20 `shouldBe` [18,19]

spec :: Spec
spec = do
  describe "def. 1" $ specG mayoresGeneradores1
  describe "def. 2" $ specG mayoresGeneradores2
  describe "def. 3" $ specG mayoresGeneradores3

-- La verificación es
--    λ> verifica
--
--    3 examples, 0 failures

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

-- La propiedad es
prop_mayoresGeneradores :: Positive Integer -> Bool
prop_mayoresGeneradores (Positive n) =
  all (== mayoresGeneradores1 n)
      [mayoresGeneradores2 n,
       mayoresGeneradores3 n]

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

-- Comprobación de eficiencia
-- ==========================

-- La comprobación es
--    λ> mayoresGeneradores (10^5)
--    [77031]
--    (5.43 secs, 6,232,320,064 bytes)
--    λ> mayoresGeneradores2 (10^5)
--    [77031]
--    (7.68 secs, 5,238,991,616 bytes)
--    λ> mayoresGeneradores3 (10^5)
--    [77031]
--    (0.88 secs, 571,788,736 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

module Mayor_orbita_de_la_sucesion_de_Collatz where

import qualified Data.MemoCombinators as Memo (integral)

import Data.List (genericLength, genericTake)

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

import Test.QuickCheck

-- 1ª solución

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

mayoresGeneradores1 :: Integer -> [Integer]

mayoresGeneradores1 n =

[x | (x,y) <- ps, y == m]

where ps = genericTake n longitudesOrbitas

m = maximum (map snd ps)

-- longitudesOrbita es la lista de los números junto a las longitudes de

-- las órbitas de Collatz que generan. Por ejemplo,

-- λ> take 10 longitudesOrbitas

-- [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]

longitudesOrbitas :: [(Integer, Integer)]

longitudesOrbitas =

[(n, genericLength (collatz n)) | n <- [1..]]

-- (siguiente n) es el siguiente de n en la sucesión de Collatz. Por

-- ejemplo,

-- siguiente 13 == 40

-- siguiente 40 == 20

siguiente :: Integer -> Integer

siguiente n | even n = n `div` 2

| otherwise = 3*n+1

-- (collatz1 n) es la órbita de Collatz de n hasta alcanzar el

-- 1. Por ejemplo,

-- collatz 13 == [13,40,20,10,5,16,8,4,2,1]

-- 1ª definición de collatz

collatz1 :: Integer -> [Integer]

collatz1 1 = [1]

collatz1 n = n : collatz1 (siguiente n)

-- 2ª definición de collatz

collatz2 :: Integer -> [Integer]

collatz2 n = takeWhile (/=1) (iterate siguiente n) ++ [1]

-- Usaremos la 2ª definición de collatz

collatz :: Integer -> [Integer]

collatz = collatz2

-- 2ª solución

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

mayoresGeneradores2 :: Integer -> [Integer]

mayoresGeneradores2 n =

[x | (x,y) <- ps, y == m]

where ps = [(x, longitudOrbita x) | x <- [1..n]]

m = maximum (map snd ps)

-- (longitudOrbita x) es la longitud de la órbita de x. Por ejemplo,

-- longitudOrbita 13 == 10

longitudOrbita :: Integer -> Integer

longitudOrbita 1 = 1

longitudOrbita x = 1 + longitudOrbita (siguiente x)

-- 3ª solución

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

mayoresGeneradores3 :: Integer -> [Integer]

mayoresGeneradores3 n =

[x | (x,y) <- ps, y == m]

where ps = [(x, longitudOrbita2 x) | x <- [1..n]]

m = maximum (map snd ps)

longitudOrbita2 :: Integer -> Integer

longitudOrbita2 = Memo.integral longitudOrbita2'

where

longitudOrbita2' 1 = 1

longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: (Integer -> [Integer]) -> Spec

specG mayoresGeneradores = do

it "e1" $

mayoresGeneradores 20 `shouldBe` [18,19]

spec :: Spec

spec = do

describe "def. 1" $ specG mayoresGeneradores1

describe "def. 2" $ specG mayoresGeneradores2

describe "def. 3" $ specG mayoresGeneradores3

-- La verificación es

-- λ> verifica

-- 3 examples, 0 failures

-- Equivalencia de definiciones

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

-- La propiedad es

prop_mayoresGeneradores :: Positive Integer -> Bool

prop_mayoresGeneradores (Positive n) =

all (== mayoresGeneradores1 n)

[mayoresGeneradores2 n,

mayoresGeneradores3 n]

-- La comprobación es

-- λ> quickCheck prop_mayoresGeneradores

-- +++ OK, passed 100 tests.

-- Comprobación de eficiencia

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

-- La comprobación es

-- λ> mayoresGeneradores (10^5)

-- [77031]

-- (5.43 secs, 6,232,320,064 bytes)

-- λ> mayoresGeneradores2 (10^5)

-- [77031]

-- (7.68 secs, 5,238,991,616 bytes)

-- λ> mayoresGeneradores3 (10^5)

-- [77031]

-- (0.88 secs, 571,788,736 bytes)

2. Soluciones en Python

from functools import lru_cache
from itertools import count, islice
from timeit import Timer, default_timer
from typing import Iterator

from hypothesis import given
from hypothesis import strategies as st

# 1ª solución
# ===========

# siguiente(n) es el siguiente de n en la sucesión de Collatz. Por
# ejemplo,
#    siguiente(13)  ==  40
#    siguiente(40)  ==  20
def siguiente (n: int) -> int:
    if n % 2 == 0:
        return n // 2
    return 3*n+1

# collatz1(n) es la órbita de Collatz de n hasta alcanzar el
# 1. Por ejemplo,
#    collatz1(13)  ==  [13,40,20,10,5,16,8,4,2,1]
def collatz1(n: int) -> list[int]:
    if n == 1:
        return [1]
    return [n]+ collatz1(siguiente(n))

# longitudesOrbita() es la lista de los números junto a las longitudes de
# las órbitas de Collatz que generan. Por ejemplo,
#    >>> list(islice(longitudesOrbitas(), 10))
#    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]
def longitudesOrbitas() -> Iterator[tuple[int, int]]:
    return ((n, len(collatz1(n))) for n in count(1))

def mayoresGeneradores1(n: int) -> list[int]:
    ps = list(islice(longitudesOrbitas(), n))
    m = max((y for (_, y) in ps))
    return [x for (x,y) in ps if y == m]

# 2ª solución
# ===========

def collatz2(n: int) -> list[int]:
    r = [n]
    while n != 1:
        n = siguiente(n)
        r.append(n)
    return r

def longitudesOrbitas2() -> Iterator[tuple[int, int]]:
    return ((n, len(collatz2(n))) for n in count(1))

def mayoresGeneradores2(n: int) -> list[int]:
    ps = list(islice(longitudesOrbitas2(), n))
    m = max((y for (_, y) in ps))
    return [x for (x,y) in ps if y == m]

# 3ª solución
# ===========

# longitudOrbita(x) es la longitud de la órbita de x. Por ejemplo,
#    longitudOrbita(13)  ==  10
def longitudOrbita(x: int) -> int:
    if x == 1:
        return 1
    return 1 + longitudOrbita(siguiente(x))

def mayoresGeneradores3(n: int) -> list[int]:
    ps = [(x, longitudOrbita(x)) for x in range(1, n+1)]
    m = max((y for (_, y) in ps))
    return [x for (x,y) in ps if y == m]

# 4ª solución
# ===========

# longitudOrbita2(x) es la longitud de la órbita de x. Por ejemplo,
#    longitudOrbita2(13)  ==  10
def longitudOrbita2(x: int) -> int:
    r = 0
    while x != 1:
        x = siguiente(x)
        r += 1
    return r + 1

def mayoresGeneradores4(n: int) -> list[int]:
    ps = [(x, longitudOrbita2(x)) for x in range(1, n+1)]
    m = max((y for (_, y) in ps))
    return [x for (x,y) in ps if y == m]

# 5ª solución
# ===========

@lru_cache(maxsize=None)
def longitudOrbita3(x: int) -> int:
    if x == 1:
        return 1
    return 1 + longitudOrbita3(siguiente(x))

def mayoresGeneradores5(n: int) -> list[int]:
    ps = [(x, longitudOrbita3(x)) for x in range(1, n+1)]
    m = max((y for (_, y) in ps))
    return [x for (x,y) in ps if y == m]

# Verificación
# ============

def test_mayoresGeneradores() -> None:
    for mayoresGeneradores in [mayoresGeneradores1,
                               mayoresGeneradores2,
                               mayoresGeneradores3,
                               mayoresGeneradores4,
                               mayoresGeneradores5]:
        assert mayoresGeneradores(20) == [18,19]
    print("Verificado")

# La verificación es
#    >>> test_mayoresGeneradores()
#    Verificado

# Equivalencia de definiciones
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_mayoresGeneradores_equiv(n: int) -> None:
    r = mayoresGeneradores1(n)
    assert mayoresGeneradores2(n) == r
    assert mayoresGeneradores3(n) == r

# La comprobación es
#    >>> test_mayoresGeneradores_equiv()
#    >>>

# Comprobación de eficiencia
# ==========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comprobación es
#    >>> tiempo('mayoresGeneradores1(10**5)')
#    4.08 segundos
#    >>> tiempo('mayoresGeneradores2(10**5)')
#    1.95 segundos
#    >>> tiempo('mayoresGeneradores3(10**5)')
#    2.16 segundos
#    >>> tiempo('mayoresGeneradores4(10**5)')
#    1.71 segundos
#    >>> tiempo('mayoresGeneradores5(10**5)')
#    0.14 segundos

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

from functools import lru_cache

from itertools import count, islice

from timeit import Timer, default_timer

from typing import Iterator

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución

# ===========

# siguiente(n) es el siguiente de n en la sucesión de Collatz. Por

# ejemplo,

# siguiente(13) == 40

# siguiente(40) == 20

def siguiente (n: int) -> int:

if n % 2 == 0:

return n // 2

return 3*n+1

# collatz1(n) es la órbita de Collatz de n hasta alcanzar el

# 1. Por ejemplo,

# collatz1(13) == [13,40,20,10,5,16,8,4,2,1]

def collatz1(n: int) -> list[int]:

if n == 1:

return [1]

return [n]+ collatz1(siguiente(n))

# longitudesOrbita() es la lista de los números junto a las longitudes de

# las órbitas de Collatz que generan. Por ejemplo,

# >>> list(islice(longitudesOrbitas(), 10))

# [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]

def longitudesOrbitas() -> Iterator[tuple[int, int]]:

return ((n, len(collatz1(n))) for n in count(1))

def mayoresGeneradores1(n: int) -> list[int]:

ps = list(islice(longitudesOrbitas(), n))

m = max((y for (_, y) in ps))

return [x for (x,y) in ps if y == m]

# 2ª solución

# ===========

def collatz2(n: int) -> list[int]:

r = [n]

while n != 1:

n = siguiente(n)

r.append(n)

return r

def longitudesOrbitas2() -> Iterator[tuple[int, int]]:

return ((n, len(collatz2(n))) for n in count(1))

def mayoresGeneradores2(n: int) -> list[int]:

ps = list(islice(longitudesOrbitas2(), n))

m = max((y for (_, y) in ps))

return [x for (x,y) in ps if y == m]

# 3ª solución

# ===========

# longitudOrbita(x) es la longitud de la órbita de x. Por ejemplo,

# longitudOrbita(13) == 10

def longitudOrbita(x: int) -> int:

if x == 1:

return 1

return 1 + longitudOrbita(siguiente(x))

def mayoresGeneradores3(n: int) -> list[int]:

ps = [(x, longitudOrbita(x)) for x in range(1, n+1)]

m = max((y for (_, y) in ps))

return [x for (x,y) in ps if y == m]

# 4ª solución

# ===========

# longitudOrbita2(x) es la longitud de la órbita de x. Por ejemplo,

# longitudOrbita2(13) == 10

def longitudOrbita2(x: int) -> int:

r = 0

while x != 1:

x = siguiente(x)

r += 1

return r + 1

def mayoresGeneradores4(n: int) -> list[int]:

ps = [(x, longitudOrbita2(x)) for x in range(1, n+1)]

m = max((y for (_, y) in ps))

return [x for (x,y) in ps if y == m]

# 5ª solución

# ===========

@lru_cache(maxsize=None)

def longitudOrbita3(x: int) -> int:

if x == 1:

return 1

return 1 + longitudOrbita3(siguiente(x))

def mayoresGeneradores5(n: int) -> list[int]:

ps = [(x, longitudOrbita3(x)) for x in range(1, n+1)]

m = max((y for (_, y) in ps))

return [x for (x,y) in ps if y == m]

# Verificación

# ============

def test_mayoresGeneradores() -> None:

for mayoresGeneradores in [mayoresGeneradores1,

mayoresGeneradores2,

mayoresGeneradores3,

mayoresGeneradores4,

mayoresGeneradores5]:

assert mayoresGeneradores(20) == [18,19]

print("Verificado")

# La verificación es

# >>> test_mayoresGeneradores()

# Verificado

# Equivalencia de definiciones

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_mayoresGeneradores_equiv(n: int) -> None:

r = mayoresGeneradores1(n)

assert mayoresGeneradores2(n) == r

assert mayoresGeneradores3(n) == r

# La comprobación es

# >>> test_mayoresGeneradores_equiv()

# >>>

# Comprobación de eficiencia

# ==========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comprobación es

# >>> tiempo('mayoresGeneradores1(10**5)')

# 4.08 segundos

# >>> tiempo('mayoresGeneradores2(10**5)')

# 1.95 segundos

# >>> tiempo('mayoresGeneradores3(10**5)')

# 2.16 segundos

# >>> tiempo('mayoresGeneradores4(10**5)')

# 1.71 segundos

# >>> tiempo('mayoresGeneradores5(10**5)')

# 0.14 segundos

6. Máximos locales

Un máximo local de una lista es un elemento de la lista que es mayor que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

   maximosLocales :: Ord a => [a] -> [a]

1	maximosLocales :: Ord a => [a] -> [a]

tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,

   maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
   maximosLocales [1..100]             ==  []
   maximosLocales "adbpmqexyz"         ==  "dpq"

maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6]

maximosLocales [1..100] == []

maximosLocales "adbpmqexyz" == "dpq"

1. Soluciones en Haskell

module Maximos_locales where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

maximosLocales1 :: Ord a => [a] -> [a]
maximosLocales1 (x:y:z:xs)
  | y > x && y > z = y : maximosLocales1 (z:xs)
  | otherwise      = maximosLocales1 (y:z:xs)
maximosLocales1 _ = []

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

maximosLocales2 :: Ord a => [a] -> [a]
maximosLocales2 xs =
  [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y > x, y > z]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> [Int]) -> Spec
specG maximosLocales = do
  it "e1" $
    maximosLocales [3,2,5,3,7,7,1,6,2]  `shouldBe`  [5,6]
  it "e2" $
    maximosLocales [1..100]             `shouldBe`  []

spec :: Spec
spec = do
  describe "def. 1" $ specG maximosLocales1
  describe "def. 2" $ specG maximosLocales2

-- La verificación es
--    λ> verifica
--
--    4 examples, 0 failures


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

-- La propiedad es
prop_maximosLocales :: [Int] -> Property
prop_maximosLocales xs =
  maximosLocales1 xs === maximosLocales2 xs

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

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

-- La comparación es
--    λ> last (maximosLocales1 (take (6*10^6) (cycle "abc")))
--    'c'
--    (3.26 secs, 1,904,464,984 bytes)
--    λ> last (maximosLocales2 (take (6*10^6) (cycle "abc")))
--    'c'
--    (2.79 secs, 1,616,465,088 bytes)

module Maximos_locales where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

import Test.QuickCheck

-- 1ª solución

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

maximosLocales1 :: Ord a => [a] -> [a]

maximosLocales1 (x:y:z:xs)

| y > x && y > z = y : maximosLocales1 (z:xs)

| otherwise = maximosLocales1 (y:z:xs)

maximosLocales1 _ = []

-- 2ª solución

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

maximosLocales2 :: Ord a => [a] -> [a]

maximosLocales2 xs =

[y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y > x, y > z]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

specG :: ([Int] -> [Int]) -> Spec

specG maximosLocales = do

it "e1" $

maximosLocales [3,2,5,3,7,7,1,6,2] `shouldBe` [5,6]

it "e2" $

maximosLocales [1..100] `shouldBe` []

spec :: Spec

spec = do

describe "def. 1" $ specG maximosLocales1

describe "def. 2" $ specG maximosLocales2

-- La verificación es

-- λ> verifica

-- 4 examples, 0 failures

-- Comprobación de equivalencia

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

-- La propiedad es

prop_maximosLocales :: [Int] -> Property

prop_maximosLocales xs =

maximosLocales1 xs === maximosLocales2 xs

-- La comprobación es

-- λ> quickCheck prop_maximosLocales

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> last (maximosLocales1 (take (6*10^6) (cycle "abc")))

-- 'c'

-- (3.26 secs, 1,904,464,984 bytes)

-- λ> last (maximosLocales2 (take (6*10^6) (cycle "abc")))

-- 'c'

-- (2.79 secs, 1,616,465,088 bytes)

2. Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

def maximosLocales1(xs: list[int]) -> list[int]:
    if len(xs) < 3:
        return []
    x, y, z, *ys = xs
    if y > x and y > z:
        return [y] + maximosLocales1([z] + ys)
    return maximosLocales1([y, z] + ys)

# 2ª solución
# ===========

def maximosLocales2(xs: list[int]) -> list[int]:
    ys: list[int] = []
    if len(xs) < 3:
        return ys
    for i in range(1, len(xs) - 1):
        if xs[i] > xs[i - 1] and xs[i] > xs[i + 1]:
            ys.append(xs[i])
    return ys

# 3ª solución
# ===========

def maximosLocales3(xs: list[int]) -> list[int]:
    return [y for x, y, z in zip(xs, xs[1:], xs[2:]) if y > x and y > z]

# Verificación
# ============

def test_maximosLocales() -> None:
    for maximosLocales in [maximosLocales1,
                           maximosLocales2,
                           maximosLocales3]:
        assert maximosLocales([3,2,5,3,7,7,1,6,2]) == [5,6]
        assert maximosLocales(list(range(0, 100))) == []
    print("Verificado")

# La verificación es
#    >>> test_maximosLocales()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()))
def test_maximosLocales_equiv(xs: list[int]) -> None:
    r = maximosLocales1(xs)
    assert maximosLocales2(xs) == r
    assert maximosLocales3(xs) == r

# La comprobación es
#    >>> test_maximosLocales_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('maximosLocales1([1,2,3]*(10**4))')
#    3.19 segundos
#    >>> tiempo('maximosLocales2([1,2,3]*(10**4))')
#    0.01 segundos
#    >>> tiempo('maximosLocales3([1,2,3]*(10**4))')
#    0.01 segundos
#
#    >>> tiempo('maximosLocales2([1,2,3]*(10**7))')
#    3.95 segundos
#    >>> tiempo('maximosLocales3([1,2,3]*(10**7))')
#    1.85 segundos

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

def maximosLocales1(xs: list[int]) -> list[int]:

if len(xs) < 3:

return []

x, y, z, *ys = xs

if y > x and y > z:

return [y] + maximosLocales1([z] + ys)

return maximosLocales1([y, z] + ys)

# 2ª solución

# ===========

def maximosLocales2(xs: list[int]) -> list[int]:

ys: list[int] = []

if len(xs) < 3:

return ys

for i in range(1, len(xs) - 1):

if xs[i] > xs[i - 1] and xs[i] > xs[i + 1]:

ys.append(xs[i])

return ys

# 3ª solución

# ===========

def maximosLocales3(xs: list[int]) -> list[int]:

return [y for x, y, z in zip(xs, xs[1:], xs[2:]) if y > x and y > z]

# Verificación

# ============

def test_maximosLocales() -> None:

for maximosLocales in [maximosLocales1,

maximosLocales2,

maximosLocales3]:

assert maximosLocales([3,2,5,3,7,7,1,6,2]) == [5,6]

assert maximosLocales(list(range(0, 100))) == []

print("Verificado")

# La verificación es

# >>> test_maximosLocales()

# Verificado

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()))

def test_maximosLocales_equiv(xs: list[int]) -> None:

r = maximosLocales1(xs)

assert maximosLocales2(xs) == r

assert maximosLocales3(xs) == r

# La comprobación es

# >>> test_maximosLocales_equiv()

# >>>

# Comparación de eficiencia

# =========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('maximosLocales1([1,2,3]*(10**4))')

# 3.19 segundos

# >>> tiempo('maximosLocales2([1,2,3]*(10**4))')

# 0.01 segundos

# >>> tiempo('maximosLocales3([1,2,3]*(10**4))')

# 0.01 segundos

# >>> tiempo('maximosLocales2([1,2,3]*(10**7))')

# 3.95 segundos

# >>> tiempo('maximosLocales3([1,2,3]*(10**7))')

# 1.85 segundos

1. Reiteración de suma de consecutivos

1. Soluciones en Haskell

2. Soluciones en Python

2. Producto de los elementos de la diagonal principal

1. Soluciones en Haskell

2. Soluciones en Python

3. Reconocimiento de potencias de 4

1. Soluciones en Haskell

2. Soluciones en Python

4. Exponente en la factorización

1. Soluciones en Haskell

2. Soluciones en Python

5. Mayor órbita de la sucesión de Collatz

1. Soluciones en Haskell

2. Soluciones en Python

6. Máximos locales

1. Soluciones en Haskell

2. Soluciones en Python

Se puede imprimir o compartir con