octubre 2022 – Exercitium

Número a partir de sus dígitos

PorJosé A. Alonso 31-octubre-202214-diciembre-2022

Definir la función

   listaNumero :: [Integer] -> Integer

1	listaNumero :: [Integer] -> Integer

tal que listaNumero xs es el número formado por los dígitos xs. Por ejemplo,

   listaNumero [5]        == 5
   listaNumero [1,3,4,7]  == 1347
   listaNumero [0,0,1]    == 1

listaNumero [5] == 5

listaNumero [1,3,4,7] == 1347

listaNumero [0,0,1] == 1

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Data.Digits (unDigits)
import Test.QuickCheck

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

listaNumero1 :: [Integer] -> Integer
listaNumero1 = aux . reverse
  where
    aux :: [Integer] -> Integer
    aux []     = 0
    aux (x:xs) = x + 10 * aux xs

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

listaNumero2 :: [Integer] -> Integer
listaNumero2 = aux 0
  where
    aux :: Integer -> [Integer] -> Integer
    aux r []     = r
    aux r (x:xs) = aux (x+10*r) xs

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

listaNumero3 :: [Integer] -> Integer
listaNumero3 = aux 0
  where
    aux :: Integer -> [Integer] -> Integer
    aux = foldl (\ r x -> x + 10 * r)

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

listaNumero4 :: [Integer] -> Integer
listaNumero4 = foldl' (\ r x -> x + 10 * r) 0

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

listaNumero5 :: [Integer] -> Integer
listaNumero5 xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]

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

listaNumero6 :: [Integer] -> Integer
listaNumero6 xs = sum (zipWith (\ y n -> y*10^n) (reverse xs) [0..])

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

listaNumero7 :: [Integer] -> Integer
listaNumero7 = unDigits 10

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

listaNumero8 :: [Integer] -> Integer
listaNumero8 = read . concatMap show

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

-- La propiedad es
prop_listaNumero :: NonEmptyList Integer -> Bool
prop_listaNumero (NonEmpty xs) =
  all (== listaNumero1 ys)
      [listaNumero2 ys,
       listaNumero3 ys,
       listaNumero4 ys,
       listaNumero5 ys,
       listaNumero6 ys,
       listaNumero7 ys,
       listaNumero8 ys]
  where ys = map (`mod` 10) xs

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

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

-- La comparación es
--    λ> length (show (listaNumero1 (replicate (10^5) 9)))
--    100000
--    (4.01 secs, 4,309,740,064 bytes)
--    λ> length (show (listaNumero2 (replicate (10^5) 9)))
--    100000
--    (4.04 secs, 4,307,268,856 bytes)
--    λ> length (show (listaNumero3 (replicate (10^5) 9)))
--    100000
--    (4.08 secs, 4,300,868,816 bytes)
--    λ> length (show (listaNumero4 (replicate (10^5) 9)))
--    100000
--    (0.42 secs, 4,288,480,208 bytes)
--    λ> length (show (listaNumero4 (replicate (10^5) 9)))
--    100000
--    (0.41 secs, 4,288,480,208 bytes)
--    λ> length (show (listaNumero5 (replicate (10^5) 9)))
--    100000
--    (43.35 secs, 10,702,827,328 bytes)
--    λ> length (show (listaNumero6 (replicate (10^5) 9)))
--    100000
--    (46.89 secs, 10,693,227,280 bytes)
--    λ> length (show (listaNumero7 (replicate (10^5) 9)))
--    100000
--    (4.33 secs, 4,297,499,344 bytes)
--    λ> length (show (listaNumero8 (replicate (10^5) 9)))
--    100000
--    (0.03 secs, 60,760,360 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

import Data.List (foldl')

import Data.Digits (unDigits)

import Test.QuickCheck

-- 1ª solución

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

listaNumero1 :: [Integer] -> Integer

listaNumero1 = aux . reverse

where

aux :: [Integer] -> Integer

aux [] = 0

aux (x:xs) = x + 10 * aux xs

-- 2ª solución

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

listaNumero2 :: [Integer] -> Integer

listaNumero2 = aux 0

where

aux :: Integer -> [Integer] -> Integer

aux r [] = r

aux r (x:xs) = aux (x+10*r) xs

-- 3ª solución

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

listaNumero3 :: [Integer] -> Integer

listaNumero3 = aux 0

where

aux :: Integer -> [Integer] -> Integer

aux = foldl (\ r x -> x + 10 * r)

-- 4ª solución

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

listaNumero4 :: [Integer] -> Integer

listaNumero4 = foldl' (\ r x -> x + 10 * r) 0

-- 5ª solución

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

listaNumero5 :: [Integer] -> Integer

listaNumero5 xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]

-- 6ª solución

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

listaNumero6 :: [Integer] -> Integer

listaNumero6 xs = sum (zipWith (\ y n -> y*10^n) (reverse xs) [0..])

-- 7ª solución

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

listaNumero7 :: [Integer] -> Integer

listaNumero7 = unDigits 10

-- 7ª solución

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

listaNumero8 :: [Integer] -> Integer

listaNumero8 = read . concatMap show

-- Comprobación de equivalencia

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

-- La propiedad es

prop_listaNumero :: NonEmptyList Integer -> Bool

prop_listaNumero (NonEmpty xs) =

all (== listaNumero1 ys)

[listaNumero2 ys,

listaNumero3 ys,

listaNumero4 ys,

listaNumero5 ys,

listaNumero6 ys,

listaNumero7 ys,

listaNumero8 ys]

where ys = map (`mod` 10) xs

-- La comprobación es

-- λ> quickCheck prop_listaNumero

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (show (listaNumero1 (replicate (10^5) 9)))

-- 100000

-- (4.01 secs, 4,309,740,064 bytes)

-- λ> length (show (listaNumero2 (replicate (10^5) 9)))

-- 100000

-- (4.04 secs, 4,307,268,856 bytes)

-- λ> length (show (listaNumero3 (replicate (10^5) 9)))

-- 100000

-- (4.08 secs, 4,300,868,816 bytes)

-- λ> length (show (listaNumero4 (replicate (10^5) 9)))

-- 100000

-- (0.42 secs, 4,288,480,208 bytes)

-- λ> length (show (listaNumero4 (replicate (10^5) 9)))

-- 100000

-- (0.41 secs, 4,288,480,208 bytes)

-- λ> length (show (listaNumero5 (replicate (10^5) 9)))

-- 100000

-- (43.35 secs, 10,702,827,328 bytes)

-- λ> length (show (listaNumero6 (replicate (10^5) 9)))

-- 100000

-- (46.89 secs, 10,693,227,280 bytes)

-- λ> length (show (listaNumero7 (replicate (10^5) 9)))

-- 100000

-- (4.33 secs, 4,297,499,344 bytes)

-- λ> length (show (listaNumero8 (replicate (10^5) 9)))

-- 100000

-- (0.03 secs, 60,760,360 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
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 listaNumero1(xs: list[int]) -> int:
    def aux(ys: list[int]) -> int:
        if ys:
            return ys[0] + 10 * aux(ys[1:])
        return 0
    return aux(list(reversed(xs)))

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

def listaNumero2(xs: list[int]) -> int:
    def aux(r: int, ys: list[int]) -> int:
        if ys:
            return aux(ys[0] + 10 * r, ys[1:])
        return r
    return aux(0, xs)

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

def listaNumero3(xs: list[int]) -> int:
    return reduce((lambda r, x: x + 10 * r), xs)

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

def listaNumero4(xs: list[int]) -> int:
    r = 0
    for x in xs:
        r = x + 10 * r
    return r

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

def listaNumero5(xs: list[int]) -> int:
    return sum((y * 10**n
                for (y, n) in zip(list(reversed(xs)), range(0, len(xs)))))

# 6ª solución
# ===========

def listaNumero6(xs: list[int]) -> int:
    return int("".join(list(map(str, xs))))

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

# La propiedad es
@given(st.lists(st.integers(min_value=0, max_value=9), min_size=1))
def test_listaNumero(xs: list[int]) -> None:
    r = listaNumero1(xs)
    assert listaNumero2(xs) == r
    assert listaNumero3(xs) == r
    assert listaNumero4(xs) == r
    assert listaNumero5(xs) == r
    assert listaNumero6(xs) == r

# La comprobación es
#    src> poetry run pytest -q numero_a_partir_de_sus_digitos.py
#    1 passed in 0.27s

# 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('listaNumero1([9]*(10**4))')
#    0.28 segundos
#    >>> tiempo('listaNumero2([9]*(10**4))')
#    0.16 segundos
#    >>> tiempo('listaNumero3([9]*(10**4))')
#    0.01 segundos
#    >>> tiempo('listaNumero4([9]*(10**4))')
#    0.01 segundos
#    >>> tiempo('listaNumero5([9]*(10**4))')
#    0.41 segundos
#    >>> tiempo('listaNumero6([9]*(10**4))')
#    0.00 segundos
#
#    >>> tiempo('listaNumero3([9]*(2*10**5))')
#    3.45 segundos
#    >>> tiempo('listaNumero4([9]*(2*10**5))')
#    3.29 segundos
#    >>> tiempo('listaNumero6([9]*(2*10**5))')
#    0.19 segundos

100

101

102

from functools import reduce

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 listaNumero1(xs: list[int]) -> int:

def aux(ys: list[int]) -> int:

if ys:

return ys[0] + 10 * aux(ys[1:])

return 0

return aux(list(reversed(xs)))

# 2ª solución

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

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

def aux(r: int, ys: list[int]) -> int:

if ys:

return aux(ys[0] + 10 * r, ys[1:])

return r

return aux(0, xs)

# 3ª solución

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

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

return reduce((lambda r, x: x + 10 * r), xs)

# 4ª solución

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

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

r = 0

for x in xs:

r = x + 10 * r

return r

# 5ª solución

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

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

return sum((y * 10**n

for (y, n) in zip(list(reversed(xs)), range(0, len(xs)))))

# 6ª solución

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

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

return int("".join(list(map(str, xs))))

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers(min_value=0, max_value=9), min_size=1))

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

r = listaNumero1(xs)

assert listaNumero2(xs) == r

assert listaNumero3(xs) == r

assert listaNumero4(xs) == r

assert listaNumero5(xs) == r

assert listaNumero6(xs) == r

# La comprobación es

# src> poetry run pytest -q numero_a_partir_de_sus_digitos.py

# 1 passed in 0.27s

# 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('listaNumero1([9]*(10**4))')

# 0.28 segundos

# >>> tiempo('listaNumero2([9]*(10**4))')

# 0.16 segundos

# >>> tiempo('listaNumero3([9]*(10**4))')

# 0.01 segundos

# >>> tiempo('listaNumero4([9]*(10**4))')

# 0.01 segundos

# >>> tiempo('listaNumero5([9]*(10**4))')

# 0.41 segundos

# >>> tiempo('listaNumero6([9]*(10**4))')

# 0.00 segundos

# >>> tiempo('listaNumero3([9]*(2*10**5))')

# 3.45 segundos

# >>> tiempo('listaNumero4([9]*(2*10**5))')

# 3.29 segundos

# >>> tiempo('listaNumero6([9]*(2*10**5))')

# 0.19 segundos

El código se encuentra en GitHub.

Suma de los dígitos de un número

PorJosé A. Alonso 28-octubre-202214-diciembre-2022

Definir la función

   sumaDigitos :: Integer -> Integer

1	sumaDigitos :: Integer -> Integer

tal que sumaDigitos n es la suma de los dígitos de n. Por ejemplo,

   sumaDigitos 3     ==  3
   sumaDigitos 2454  == 15
   sumaDigitos 20045 == 11

sumaDigitos 3 == 3

sumaDigitos 2454 == 15

sumaDigitos 20045 == 11

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Test.QuickCheck

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

sumaDigitos1 :: Integer -> Integer
sumaDigitos1 n = sum (digitos n)

-- (digitos n) es la lista de los dígitos del número n. Por ejemplo,
--    digitos 320274  ==  [3,2,0,2,7,4]
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]

-- Nota. En lugar de la definición anterior de digitos se puede usar
-- cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

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

sumaDigitos2 :: Integer -> Integer
sumaDigitos2 n = foldl' (+) 0 (digitos n)

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

sumaDigitos3 :: Integer -> Integer
sumaDigitos3 n
  | n < 10    = n
  | otherwise = n `rem` 10 + sumaDigitos3 (n `div` 10)

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

sumaDigitos4 :: Integer -> Integer
sumaDigitos4 = aux 0
  where aux r n
          | n < 10    = r + n
          | otherwise = aux (r + n `rem` 10) (n `div` 10)

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

-- La propiedad es
prop_sumaDigitos :: NonNegative Integer -> Bool
prop_sumaDigitos (NonNegative n) =
  all (== sumaDigitos1 n)
      [sumaDigitos2 n,
       sumaDigitos3 n,
       sumaDigitos4 n]

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

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

-- La comparación es
--    λ> sumaDigitos1 (product [1..2*10^4])
--    325494
--    (0.64 secs, 665,965,832 bytes)
--    λ> sumaDigitos2 (product [1..2*10^4])
--    325494
--    (0.41 secs, 660,579,064 bytes)
--    λ> sumaDigitos3 (product [1..2*10^4])
--    325494
--    (1.58 secs, 1,647,082,224 bytes)
--    λ> sumaDigitos4 (product [1..2*10^4])
--    325494
--    (1.72 secs, 1,662,177,792 bytes)
--
--    λ> sumaDigitos1 (product [1..5*10^4])
--    903555
--    (2.51 secs, 3,411,722,136 bytes)
--    λ> sumaDigitos2 (product [1..5*10^4])
--    903555
--    (2.30 secs, 3,396,802,856 bytes)

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

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

sumaDigitos1 :: Integer -> Integer

sumaDigitos1 n = sum (digitos n)

-- (digitos n) es la lista de los dígitos del número n. Por ejemplo,

-- digitos 320274 == [3,2,0,2,7,4]

digitos :: Integer -> [Integer]

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

-- Nota. En lugar de la definición anterior de digitos se puede usar

-- cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

-- 2ª solución

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

sumaDigitos2 :: Integer -> Integer

sumaDigitos2 n = foldl' (+) 0 (digitos n)

-- 3ª solución

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

sumaDigitos3 :: Integer -> Integer

sumaDigitos3 n

| n < 10 = n

| otherwise = n `rem` 10 + sumaDigitos3 (n `div` 10)

-- 4ª solución

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

sumaDigitos4 :: Integer -> Integer

sumaDigitos4 = aux 0

where aux r n

| n < 10 = r + n

| otherwise = aux (r + n `rem` 10) (n `div` 10)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_sumaDigitos :: NonNegative Integer -> Bool

prop_sumaDigitos (NonNegative n) =

all (== sumaDigitos1 n)

[sumaDigitos2 n,

sumaDigitos3 n,

sumaDigitos4 n]

-- La comprobación es

-- λ> quickCheck prop_sumaDigitos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

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

-- 325494

-- (0.64 secs, 665,965,832 bytes)

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

-- 325494

-- (0.41 secs, 660,579,064 bytes)

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

-- 325494

-- (1.58 secs, 1,647,082,224 bytes)

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

-- 325494

-- (1.72 secs, 1,662,177,792 bytes)

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

-- 903555

-- (2.51 secs, 3,411,722,136 bytes)

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

-- 903555

-- (2.30 secs, 3,396,802,856 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
from math import factorial
from operator import add
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
# ===========

# digitos(n) es la lista de los dígitos del número n. Por ejemplo,
#    digitos(320274)  ==  [3, 2, 0, 2, 7, 4]
def digitos(n: int) -> list[int]:
    return list(map(int, list(str(n))))

def sumaDigitos1(n: int) -> int:
    return sum(digitos(n))

# Nota. En lugar de la definición anterior de digitos se puede usar
# cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

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

def sumaDigitos2(n: int) -> int:
    return reduce(add, digitos(n))

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

def sumaDigitos3(n: int) -> int:
    if n < 10:
        return n
    return n % 10 + sumaDigitos3(n // 10)

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

def sumaDigitos4(n: int) -> int:
    def aux(r: int, m: int) -> int:
        if m < 10:
            return r + m
        return aux(r + m % 10, m // 10)
    return aux(0, n)

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

def sumaDigitos5(n: int) -> int:
    r = 0
    for x in digitos(n):
        r = r + x
    return r

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

# La propiedad es
@given(st.integers(min_value=0, max_value=1000))
def test_sumaDigitos(n: int) -> None:
    r = sumaDigitos1(n)
    assert sumaDigitos2(n) == r
    assert sumaDigitos3(n) == r
    assert sumaDigitos4(n) == r
    assert sumaDigitos5(n) == r

# La comprobación es
#    src> poetry run pytest -q suma_de_los_digitos_de_un_numero.py
#    1 passed in 0.35s

# 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('sumaDigitos1(factorial(6*10**3))')
#    0.01 segundos
#    >>> tiempo('sumaDigitos2(factorial(6*10**3))')
#    0.01 segundos
#    >>> tiempo('sumaDigitos3(factorial(6*10**3))')
#    0.13 segundos
#    >>> tiempo('sumaDigitos4(factorial(6*10**3))')
#    0.13 segundos
#    >>> tiempo('sumaDigitos5(factorial(6*10**3))')
#    0.01 segundos
#
#    >>> tiempo('sumaDigitos1(factorial(10**5))')
#    2.20 segundos
#    >>> tiempo('sumaDigitos2(factorial(10**5))')
#    2.22 segundos
#    >>> tiempo('sumaDigitos5(factorial(10**5))')
#    2.19 segundos

100

from functools import reduce

from math import factorial

from operator import add

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

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

# digitos(n) es la lista de los dígitos del número n. Por ejemplo,

# digitos(320274) == [3, 2, 0, 2, 7, 4]

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

return list(map(int, list(str(n))))

def sumaDigitos1(n: int) -> int:

return sum(digitos(n))

# Nota. En lugar de la definición anterior de digitos se puede usar

# cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

# 2ª solución

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

def sumaDigitos2(n: int) -> int:

return reduce(add, digitos(n))

# 3ª solución

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

def sumaDigitos3(n: int) -> int:

if n < 10:

return n

return n % 10 + sumaDigitos3(n // 10)

# 4ª solución

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

def sumaDigitos4(n: int) -> int:

def aux(r: int, m: int) -> int:

if m < 10:

return r + m

return aux(r + m % 10, m // 10)

return aux(0, n)

# 5ª solución

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

def sumaDigitos5(n: int) -> int:

r = 0

for x in digitos(n):

r = r + x

return r

# Comprobación de equivalencia

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

# La propiedad es

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

def test_sumaDigitos(n: int) -> None:

r = sumaDigitos1(n)

assert sumaDigitos2(n) == r

assert sumaDigitos3(n) == r

assert sumaDigitos4(n) == r

assert sumaDigitos5(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_los_digitos_de_un_numero.py

# 1 passed in 0.35s

# 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('sumaDigitos1(factorial(6*10**3))')

# 0.01 segundos

# >>> tiempo('sumaDigitos2(factorial(6*10**3))')

# 0.01 segundos

# >>> tiempo('sumaDigitos3(factorial(6*10**3))')

# 0.13 segundos

# >>> tiempo('sumaDigitos4(factorial(6*10**3))')

# 0.13 segundos

# >>> tiempo('sumaDigitos5(factorial(6*10**3))')

# 0.01 segundos

# >>> tiempo('sumaDigitos1(factorial(10**5))')

# 2.20 segundos

# >>> tiempo('sumaDigitos2(factorial(10**5))')

# 2.22 segundos

# >>> tiempo('sumaDigitos5(factorial(10**5))')

# 2.19 segundos

El código se encuentra en GitHub

Dígitos de un número

PorJosé A. Alonso 27-octubre-202214-diciembre-2022

Definir la función

   digitos :: Integer -> [Int]

1	digitos :: Integer -> [Int]

tal que digitos n es la lista de los dígitos del número n. Por ejemplo,

   digitos 320274  ==  [3,2,0,2,7,4]

1	digitos 320274 == [3,2,0,2,7,4]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.Char (digitToInt)
import qualified Data.Digits as D (digits)
import qualified Data.FastDigits as FD (digits)
import Test.QuickCheck

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

digitos1 :: Integer -> [Int]
digitos1 n = map fromInteger (aux n)
  where aux :: Integer -> [Integer]
        aux m
          | m < 10    = [m]
          | otherwise = aux (m `div` 10) ++ [m `rem` 10]

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

digitos2 :: Integer -> [Int]
digitos2 n = map fromInteger (reverse (aux n))
  where aux :: Integer -> [Integer]
        aux m
          | m < 10    = [m]
          | otherwise = (m `rem` 10) : aux (m `div` 10)

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

digitos3 :: Integer -> [Int]
digitos3 n = map fromInteger (aux [] n)
  where aux :: [Integer] -> Integer -> [Integer]
        aux ds m
          | m < 10    = m : ds
          | otherwise = aux (m `rem` 10 : ds) (m `div` 10)

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

digitos4 :: Integer -> [Int]
digitos4 n = [read [x] | x <- show n]

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

digitos5 :: Integer -> [Int]
digitos5 n = map (\ x -> read [x]) (show n)

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

digitos6 :: Integer -> [Int]
digitos6 = map (read . return) . show

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

digitos7 :: Integer -> [Int]
digitos7 n = map digitToInt (show n)

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

digitos8 :: Integer -> [Int]
digitos8 = map digitToInt . show

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

digitos9 :: Integer -> [Int]
digitos9 0 = [0]
digitos9 n = map fromInteger (D.digits 10 n)

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

digitos10 :: Integer -> [Int]
digitos10 0 = [0]
digitos10 n = reverse (FD.digits 10 n)

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

-- La propiedad es
prop_digitos :: NonNegative Integer -> Bool
prop_digitos (NonNegative n) =
  all (== digitos1 n)
      [digitos2 n,
       digitos3 n,
       digitos4 n,
       digitos5 n,
       digitos6 n,
       digitos7 n,
       digitos8 n,
       digitos9 n,
       digitos10 n]

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

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

-- La comparación es
--    λ> n = product [1..5000]
--    λ> length (digitos1 n)
--    16326
--    (3.00 secs, 11,701,450,912 bytes)
--    λ> length (digitos2 n)
--    16326
--    (0.13 secs, 83,393,816 bytes)
--    λ> length (digitos3 n)
--    16326
--    (0.11 secs, 83,132,552 bytes)
--    λ> length (digitos4 n)
--    16326
--    (0.01 secs, 23,054,920 bytes)
--    λ> length (digitos5 n)
--    16326
--    (0.01 secs, 22,663,088 bytes)
--    λ> length (digitos6 n)
--    16326
--    (0.06 secs, 22,663,224 bytes)
--    λ> length (digitos7 n)
--    16326
--    (0.01 secs, 22,663,064 bytes)
--    λ> length (digitos8 n)
--    16326
--    (0.03 secs, 22,663,192 bytes)
--    λ> length (digitos9 n)
--    16326
--    (0.05 secs, 82,609,944 bytes)
--    λ> length (digitos10 n)
--    16326
--    (0.01 secs, 26,295,416 bytes)
--
--    λ> n = product [1..5*10^4]
--    λ> length (digitos2 n)
--    213237
--    (10.17 secs, 12,143,633,056 bytes)
--    λ> length (digitos3 n)
--    213237
--    (10.54 secs, 12,140,221,216 bytes)
--    λ> length (digitos4 n)
--    213237
--    (1.29 secs, 2,638,199,328 bytes)
--    λ> length (digitos5 n)
--    213237
--    (2.48 secs, 2,633,081,632 bytes)
--    λ> length (digitos6 n)
--    213237
--    (2.59 secs, 2,633,081,600 bytes)
--    λ> length (digitos7 n)
--    213237
--    (2.55 secs, 2,633,081,608 bytes)
--    λ> length (digitos8 n)
--    213237
--    (2.49 secs, 2,633,081,600 bytes)
--    λ> length (digitos9 n)
--    213237
--    (7.07 secs, 12,133,397,456 bytes)
--    λ> length (digitos10 n)
--    213237
--    (2.47 secs, 2,725,182,064 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

import Data.Char (digitToInt)

import qualified Data.Digits as D (digits)

import qualified Data.FastDigits as FD (digits)

import Test.QuickCheck

-- 1ª solución

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

digitos1 :: Integer -> [Int]

digitos1 n = map fromInteger (aux n)

where aux :: Integer -> [Integer]

aux m

| m < 10 = [m]

| otherwise = aux (m `div` 10) ++ [m `rem` 10]

-- 2ª solución

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

digitos2 :: Integer -> [Int]

digitos2 n = map fromInteger (reverse (aux n))

where aux :: Integer -> [Integer]

aux m

| m < 10 = [m]

| otherwise = (m `rem` 10) : aux (m `div` 10)

-- 3ª solución

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

digitos3 :: Integer -> [Int]

digitos3 n = map fromInteger (aux [] n)

where aux :: [Integer] -> Integer -> [Integer]

aux ds m

| m < 10 = m : ds

| otherwise = aux (m `rem` 10 : ds) (m `div` 10)

-- 4ª solución

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

digitos4 :: Integer -> [Int]

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

-- 5ª solución

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

digitos5 :: Integer -> [Int]

digitos5 n = map (\ x -> read [x]) (show n)

-- 6ª solución

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

digitos6 :: Integer -> [Int]

digitos6 = map (read . return) . show

-- 7ª solución

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

digitos7 :: Integer -> [Int]

digitos7 n = map digitToInt (show n)

-- 8ª solución

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

digitos8 :: Integer -> [Int]

digitos8 = map digitToInt . show

-- 9ª solución

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

digitos9 :: Integer -> [Int]

digitos9 0 = [0]

digitos9 n = map fromInteger (D.digits 10 n)

-- 10ª solución

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

digitos10 :: Integer -> [Int]

digitos10 0 = [0]

digitos10 n = reverse (FD.digits 10 n)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_digitos :: NonNegative Integer -> Bool

prop_digitos (NonNegative n) =

all (== digitos1 n)

[digitos2 n,

digitos3 n,

digitos4 n,

digitos5 n,

digitos6 n,

digitos7 n,

digitos8 n,

digitos9 n,

digitos10 n]

-- La comprobación es

-- λ> quickCheck prop_digitos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> n = product [1..5000]

-- λ> length (digitos1 n)

-- 16326

-- (3.00 secs, 11,701,450,912 bytes)

-- λ> length (digitos2 n)

-- 16326

-- (0.13 secs, 83,393,816 bytes)

-- λ> length (digitos3 n)

-- 16326

-- (0.11 secs, 83,132,552 bytes)

-- λ> length (digitos4 n)

-- 16326

-- (0.01 secs, 23,054,920 bytes)

-- λ> length (digitos5 n)

-- 16326

-- (0.01 secs, 22,663,088 bytes)

-- λ> length (digitos6 n)

-- 16326

-- (0.06 secs, 22,663,224 bytes)

-- λ> length (digitos7 n)

-- 16326

-- (0.01 secs, 22,663,064 bytes)

-- λ> length (digitos8 n)

-- 16326

-- (0.03 secs, 22,663,192 bytes)

-- λ> length (digitos9 n)

-- 16326

-- (0.05 secs, 82,609,944 bytes)

-- λ> length (digitos10 n)

-- 16326

-- (0.01 secs, 26,295,416 bytes)

-- λ> n = product [1..5*10^4]

-- λ> length (digitos2 n)

-- 213237

-- (10.17 secs, 12,143,633,056 bytes)

-- λ> length (digitos3 n)

-- 213237

-- (10.54 secs, 12,140,221,216 bytes)

-- λ> length (digitos4 n)

-- 213237

-- (1.29 secs, 2,638,199,328 bytes)

-- λ> length (digitos5 n)

-- 213237

-- (2.48 secs, 2,633,081,632 bytes)

-- λ> length (digitos6 n)

-- 213237

-- (2.59 secs, 2,633,081,600 bytes)

-- λ> length (digitos7 n)

-- 213237

-- (2.55 secs, 2,633,081,608 bytes)

-- λ> length (digitos8 n)

-- 213237

-- (2.49 secs, 2,633,081,600 bytes)

-- λ> length (digitos9 n)

-- 213237

-- (7.07 secs, 12,133,397,456 bytes)

-- λ> length (digitos10 n)

-- 213237

-- (2.47 secs, 2,725,182,064 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import factorial
from sys import setrecursionlimit
from timeit import Timer, default_timer

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

setrecursionlimit(10**6)

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

def digitos1(n: int) -> list[int]:
    if n < 10:
        return [n]
    return digitos1(n // 10) + [n % 10]

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

def digitos2(n: int) -> list[int]:
    return [int(x) for x in str(n)]

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

def digitos3(n: int) -> list[int]:
    r: list[int] = []
    for x in str(n):
        r.append(int(x))
    return r

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

def digitos4(n: int) -> list[int]:
    return list(map(int, list(str(n))))

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

def digitos5(n: int) -> list[int]:
    r: list[int] = []
    while n > 0:
        r = [n % 10] + r
        n = n // 10
    return r

# 6ª solución
# ===========

def digitos6(n: int) -> list[int]:
    r: list[int] = []
    while n > 0:
        r.append(n % 10)
        n = n // 10
    return list(reversed(r))

# 7ª solución
# ===========

def digitos7(n: int) -> list[int]:
    return digits(n)[1:]

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

# La propiedad es
@given(st.integers(min_value=1))
def test_digitos(n: int) -> None:
    r = digitos1(n)
    assert digitos2(n) == r
    assert digitos3(n) == r
    assert digitos4(n) == r
    assert digitos5(n) == r
    assert digitos6(n) == r
    assert digitos7(n) == r

# La comprobación es
#    src> poetry run pytest -q digitos_de_un_numero.py
#    1 passed in 0.49s

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

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

# La comparación es
#    >>> tiempo('digitos1(factorial(6000))')
#    0.58 segundos
#    >>> tiempo('digitos2(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos3(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos4(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos5(factorial(6000))')
#    0.60 segundos
#    >>> tiempo('digitos6(factorial(6000))')
#    0.17 segundos
#    >>> tiempo('digitos7(factorial(6000))')
#    0.10 segundos
#
#    >>> tiempo('digitos2(factorial(2*10**4))')
#    0.10 segundos
#    >>> tiempo('digitos3(factorial(2*10**4))')
#    0.10 segundos
#    >>> tiempo('digitos4(factorial(2*10**4))')
#    0.09 segundos
#    >>> tiempo('digitos6(factorial(2*10**4))')
#    2.33 segundos
#    >>> tiempo('digitos7(factorial(2*10**4))')
#    1.18 segundos
#
#    >>> tiempo('digitos2(factorial(10**5))')
#    3.53 segundos
#    >>> tiempo('digitos3(factorial(10**5))')
#    3.22 segundos
#    >>> tiempo('digitos4(factorial(10**5))')
#    3.02 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

from math import factorial

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy.ntheory.digits import digits

setrecursionlimit(10**6)

# 1ª solución

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

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

if n < 10:

return [n]

return digitos1(n // 10) + [n % 10]

# 2ª solución

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

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

return [int(x) for x in str(n)]

# 3ª solución

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

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

r: list[int] = []

for x in str(n):

r.append(int(x))

return r

# 4ª solución

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

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

return list(map(int, list(str(n))))

# 5ª solución

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

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

r: list[int] = []

while n > 0:

r = [n % 10] + r

n = n // 10

return r

# 6ª solución

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

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

r: list[int] = []

while n > 0:

r.append(n % 10)

n = n // 10

return list(reversed(r))

# 7ª solución

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

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

return digits(n)[1:]

# Comprobación de equivalencia

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

# La propiedad es

@given(st.integers(min_value=1))

def test_digitos(n: int) -> None:

r = digitos1(n)

assert digitos2(n) == r

assert digitos3(n) == r

assert digitos4(n) == r

assert digitos5(n) == r

assert digitos6(n) == r

assert digitos7(n) == r

# La comprobación es

# src> poetry run pytest -q digitos_de_un_numero.py

# 1 passed in 0.49s

# Comparación de eficiencia

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

def tiempo(ex: str) -> None:

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

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

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

# La comparación es

# >>> tiempo('digitos1(factorial(6000))')

# 0.58 segundos

# >>> tiempo('digitos2(factorial(6000))')

# 0.01 segundos

# >>> tiempo('digitos3(factorial(6000))')

# 0.01 segundos

# >>> tiempo('digitos4(factorial(6000))')

# 0.01 segundos

# >>> tiempo('digitos5(factorial(6000))')

# 0.60 segundos

# >>> tiempo('digitos6(factorial(6000))')

# 0.17 segundos

# >>> tiempo('digitos7(factorial(6000))')

# 0.10 segundos

# >>> tiempo('digitos2(factorial(2*10**4))')

# 0.10 segundos

# >>> tiempo('digitos3(factorial(2*10**4))')

# 0.10 segundos

# >>> tiempo('digitos4(factorial(2*10**4))')

# 0.09 segundos

# >>> tiempo('digitos6(factorial(2*10**4))')

# 2.33 segundos

# >>> tiempo('digitos7(factorial(2*10**4))')

# 1.18 segundos

# >>> tiempo('digitos2(factorial(10**5))')

# 3.53 segundos

# >>> tiempo('digitos3(factorial(10**5))')

# 3.22 segundos

# >>> tiempo('digitos4(factorial(10**5))')

# 3.02 segundos

El código se encuentra en GitHub.

Algoritmo de Euclides del mcd

PorJosé A. Alonso 26-octubre-202214-diciembre-2022

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = mcd (b, a módulo b), si b > 0

1 2	mcd(a,b) = a, si b = 0 = mcd (b, a módulo b), si b > 0

Definir la función

   mcd :: Integer -> Integer -> Integer

1	mcd :: Integer -> Integer -> Integer

tal que mcd a b es el máximo común divisor de a y b calculado mediante el algoritmo de Euclides. Por ejemplo,

   mcd 30 45  ==  15
   mcd 45 30  ==  15

1 2	mcd 30 45 == 15 mcd 45 30 == 15

Comprobar con QuickCheck que el máximo común divisor de dos números a y b (ambos mayores que 0) es siempre mayor o igual que 1 y además es menor o igual que el menor de los números a y b.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (a `mod` b)

-- La propiedad es
prop_mcd :: Positive Integer -> Positive Integer -> Bool
prop_mcd (Positive a) (Positive b) =
  m >= 1 && m <= min a b
  where m = mcd a b

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

import Test.QuickCheck

mcd :: Integer -> Integer -> Integer

mcd a 0 = a

mcd a b = mcd b (a `mod` b)

-- La propiedad es

prop_mcd :: Positive Integer -> Positive Integer -> Bool

prop_mcd (Positive a) (Positive b) =

m >= 1 && m <= min a b

where m = mcd a b

-- La comprobación es

-- λ> quickCheck prop_mcd

-- OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from hypothesis import given
from hypothesis import strategies as st

def mcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return mcd(b, a % b)

# -- La propiedad es
@given(st.integers(min_value=1, max_value=1000),
       st.integers(min_value=1, max_value=1000))
def test_mcd(a: int, b: int) -> None:
    assert 1 <= mcd(a, b) <= min(a, b)

# La comprobación es
#    src> poetry run pytest -q algoritmo_de_Euclides_del_mcd.py
#    1 passed in 0.22s

from hypothesis import given

from hypothesis import strategies as st

def mcd(a: int, b: int) -> int:

if b == 0:

return a

return mcd(b, a % b)

# -- La propiedad es

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

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

def test_mcd(a: int, b: int) -> None:

assert 1 <= mcd(a, b) <= min(a, b)

# La comprobación es

# src> poetry run pytest -q algoritmo_de_Euclides_del_mcd.py

# 1 passed in 0.22s

El código se encuentra en GitHub.

Potencia entera

PorJosé A. Alonso 25-octubre-202214-diciembre-2022

Definir la función

   potencia :: Integer -> Integer -> Integer

1	potencia :: Integer -> Integer -> Integer

tal que potencia x n es x elevado al número natural n. Por ejemplo,

   potencia 2 3  ==  8

1	potencia 2 3 == 8

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Control.Arrow ((***))
import Test.QuickCheck

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

potencia1 :: Integer -> Integer -> Integer
potencia1 _ 0 = 1
potencia1 m n = m * potencia1 m (n-1)

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

potencia2 :: Integer -> Integer -> Integer
potencia2 m = aux
  where aux 0 = 1
        aux n = m * aux (n-1)

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

potencia3 :: Integer -> Integer -> Integer
potencia3 m = aux 1
  where aux r 0 = r
        aux r n = aux (r*m) (n-1)

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

potencia4 :: Integer -> Integer -> Integer
potencia4 m = aux 1
  where aux r 0 = r
        aux r n = (aux $! (r*m)) $! (n-1)

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

potencia5 :: Integer -> Integer -> Integer
potencia5 m n = product [m | _ <- [1..n]]

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

potencia6 :: Integer -> Integer -> Integer
potencia6 m n = foldl' (*) 1 [m | _ <- [1..n]]

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

potencia7 :: Integer -> Integer -> Integer
potencia7 m n =
  fst (until (\ (_,k) -> k == n)
             (\ (r,k) -> (r*m, k+1))
             (1,0))

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

potencia8 :: Integer -> Integer -> Integer
potencia8 m n =
  fst (until ((== n) . snd)
             ((m *) *** (1 +))
             (1,0))

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

potencia9 :: Integer -> Integer -> Integer
potencia9 m n = m^n

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

-- La propiedad es
prop_potencia :: Integer -> NonNegative Integer -> Bool
prop_potencia m (NonNegative n) =
  all (== potencia1 m n)
      [potencia2 m n,
       potencia3 m n,
       potencia4 m n,
       potencia5 m n,
       potencia6 m n,
       potencia7 m n,
       potencia8 m n,
       potencia9 m n]

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

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

-- La comparación es
--    λ> length (show (potencia1 2 (2*10^5)))
--    60206
--    (2.97 secs, 2,602,252,408 bytes)
--    λ> length (show (potencia2 2 (2*10^5)))
--    60206
--    (2.63 secs, 2,624,652,624 bytes)
--    λ> length (show (potencia3 2 (2*10^5)))
--    60206
--    (3.41 secs, 2,619,606,368 bytes)
--    λ> length (show (potencia4 2 (2*10^5)))
--    60206
--    (0.64 secs, 2,636,888,928 bytes)
--    λ> length (show (potencia5 2 (2*10^5)))
--    60206
--    (2.47 secs, 2,597,108,000 bytes)
--    λ> length (show (potencia6 2 (2*10^5)))
--    60206
--    (0.35 secs, 2,582,488,824 bytes)
--    λ> length (show (potencia7 2 (2*10^5)))
--    60206
--    (2.48 secs, 2,616,406,272 bytes)
--    λ> length (show (potencia8 2 (2*10^5)))
--    60206
--    (2.40 secs, 2,608,652,736 bytes)
--    λ> length (show (potencia9 2 (2*10^5)))
--    60206
--    (0.01 secs, 4,212,968 bytes)
--
--    λ> length (show (potencia4 2 (10^6)))
--    301030
--    (10.39 secs, 63,963,999,656 bytes)
--    λ> length (show (potencia6 2 (10^6)))
--    301030
--    (8.90 secs, 63,691,999,552 bytes)
--    λ> length (show (potencia9 2 (10^6)))
--    301030
--    (0.04 secs, 19,362,032 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

import Data.List (foldl')

import Control.Arrow ((***))

import Test.QuickCheck

-- 1ª solución

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

potencia1 :: Integer -> Integer -> Integer

potencia1 _ 0 = 1

potencia1 m n = m * potencia1 m (n-1)

-- 2ª solución

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

potencia2 :: Integer -> Integer -> Integer

potencia2 m = aux

where aux 0 = 1

aux n = m * aux (n-1)

-- 3ª solución

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

potencia3 :: Integer -> Integer -> Integer

potencia3 m = aux 1

where aux r 0 = r

aux r n = aux (r*m) (n-1)

-- 4ª solución

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

potencia4 :: Integer -> Integer -> Integer

potencia4 m = aux 1

where aux r 0 = r

aux r n = (aux $! (r*m)) $! (n-1)

-- 5ª solución

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

potencia5 :: Integer -> Integer -> Integer

potencia5 m n = product [m | _ <- [1..n]]

-- 6ª solución

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

potencia6 :: Integer -> Integer -> Integer

potencia6 m n = foldl' (*) 1 [m | _ <- [1..n]]

-- 7ª solución

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

potencia7 :: Integer -> Integer -> Integer

potencia7 m n =

fst (until (\ (_,k) -> k == n)

(\ (r,k) -> (r*m, k+1))

(1,0))

-- 8ª solución

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

potencia8 :: Integer -> Integer -> Integer

potencia8 m n =

fst (until ((== n) . snd)

((m *) *** (1 +))

(1,0))

-- 9ª solución

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

potencia9 :: Integer -> Integer -> Integer

potencia9 m n = m^n

-- Comprobación de equivalencia

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

-- La propiedad es

prop_potencia :: Integer -> NonNegative Integer -> Bool

prop_potencia m (NonNegative n) =

all (== potencia1 m n)

[potencia2 m n,

potencia3 m n,

potencia4 m n,

potencia5 m n,

potencia6 m n,

potencia7 m n,

potencia8 m n,

potencia9 m n]

-- La comprobación es

-- λ> quickCheck prop_potencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (show (potencia1 2 (2*10^5)))

-- 60206

-- (2.97 secs, 2,602,252,408 bytes)

-- λ> length (show (potencia2 2 (2*10^5)))

-- 60206

-- (2.63 secs, 2,624,652,624 bytes)

-- λ> length (show (potencia3 2 (2*10^5)))

-- 60206

-- (3.41 secs, 2,619,606,368 bytes)

-- λ> length (show (potencia4 2 (2*10^5)))

-- 60206

-- (0.64 secs, 2,636,888,928 bytes)

-- λ> length (show (potencia5 2 (2*10^5)))

-- 60206

-- (2.47 secs, 2,597,108,000 bytes)

-- λ> length (show (potencia6 2 (2*10^5)))

-- 60206

-- (0.35 secs, 2,582,488,824 bytes)

-- λ> length (show (potencia7 2 (2*10^5)))

-- 60206

-- (2.48 secs, 2,616,406,272 bytes)

-- λ> length (show (potencia8 2 (2*10^5)))

-- 60206

-- (2.40 secs, 2,608,652,736 bytes)

-- λ> length (show (potencia9 2 (2*10^5)))

-- 60206

-- (0.01 secs, 4,212,968 bytes)

-- λ> length (show (potencia4 2 (10^6)))

-- 301030

-- (10.39 secs, 63,963,999,656 bytes)

-- λ> length (show (potencia6 2 (10^6)))

-- 301030

-- (8.90 secs, 63,691,999,552 bytes)

-- λ> length (show (potencia9 2 (10^6)))

-- 301030

-- (0.04 secs, 19,362,032 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
from operator import mul
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 potencia1(m: int, n: int) -> int:
    if n == 0:
        return 1
    return m * potencia1(m, n-1)

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

def potencia2(m: int, n: int) -> int:
    def aux(k: int) -> int:
        if k == 0:
            return 1
        return m * aux(k-1)
    return aux(n)

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

def potencia3(m: int, n: int) -> int:
    def aux(r: int, k: int) -> int:
        if k == 0:
            return r
        return aux(r*m, k-1)
    return aux(1, n)

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

# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([2, 3, 5])  ==  30
def producto(xs: list[int]) -> int:
    return reduce(mul, xs, 1)

def potencia4(m: int, n: int) -> int:
    return producto([m]*n)

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

def potencia5(m: int, n: int) -> int:
    r = 1
    for _ in range(0, n):
        r = r * m
    return r

# 6ª solución
# ===========

def potencia6(m: int, n: int) -> int:
    return m**n

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

# La propiedad es
@given(st.integers(),
       st.integers(min_value=0, max_value=100))
def test_potencia(m: int, n: int) -> None:
    r = potencia1(m, n)
    assert potencia2(m, n) == r
    assert potencia3(m, n) == r
    assert potencia4(m, n) == r
    assert potencia5(m, n) == r
    assert potencia6(m, n) == r

# La comprobación es
#    src> poetry run pytest -q potencia_entera.py
#    1 passed in 0.17s

# 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('potencia1(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia2(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia3(2, 2*10**4)')
#    0.02 segundos
#    >>> tiempo('potencia4(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia5(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia6(2, 2*10**4)')
#    0.00 segundos
#
#    >>> tiempo('potencia4(2, 5*10**5)')
#    2.87 segundos
#    >>> tiempo('potencia5(2, 5*10**5)')
#    3.17 segundos
#    >>> tiempo('potencia6(2, 5*10**5)')
#    0.00 segundos

100

101

102

103

104

105

106

107

108

109

110

from functools import reduce

from operator import mul

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 potencia1(m: int, n: int) -> int:

if n == 0:

return 1

return m * potencia1(m, n-1)

# 2ª solución

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

def potencia2(m: int, n: int) -> int:

def aux(k: int) -> int:

if k == 0:

return 1

return m * aux(k-1)

return aux(n)

# 3ª solución

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

def potencia3(m: int, n: int) -> int:

def aux(r: int, k: int) -> int:

if k == 0:

return r

return aux(r*m, k-1)

return aux(1, n)

# 4ª solución

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

# producto(xs) es el producto de los elementos de xs. Por ejemplo,

# producto([2, 3, 5]) == 30

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

return reduce(mul, xs, 1)

def potencia4(m: int, n: int) -> int:

return producto([m]*n)

# 5ª solución

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

def potencia5(m: int, n: int) -> int:

r = 1

for _ in range(0, n):

r = r * m

return r

# 6ª solución

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

def potencia6(m: int, n: int) -> int:

return m**n

# Comprobación de equivalencia

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

# La propiedad es

@given(st.integers(),

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

def test_potencia(m: int, n: int) -> None:

r = potencia1(m, n)

assert potencia2(m, n) == r

assert potencia3(m, n) == r

assert potencia4(m, n) == r

assert potencia5(m, n) == r

assert potencia6(m, n) == r

# La comprobación es

# src> poetry run pytest -q potencia_entera.py

# 1 passed in 0.17s

# 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('potencia1(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia2(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia3(2, 2*10**4)')

# 0.02 segundos

# >>> tiempo('potencia4(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia5(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia6(2, 2*10**4)')

# 0.00 segundos

# >>> tiempo('potencia4(2, 5*10**5)')

# 2.87 segundos

# >>> tiempo('potencia5(2, 5*10**5)')

# 3.17 segundos

# >>> tiempo('potencia6(2, 5*10**5)')

# 0.00 segundos

El código se encuentra en GitHub.

Meses: octubre 2022

Número a partir de sus dígitos

Suma de los dígitos de un número

Dígitos de un número

Algoritmo de Euclides del mcd

Potencia entera

Entradas recientes

Buscar

Correo electrónico