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

Reiteración de suma de consecutivos

1. Soluciones en Haskell

2. Soluciones en Python

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

1. Soluciones en Haskell

2. Soluciones en Python

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico