PFH: La semana en Exercitium (4 de noviembre de 2022)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

1. Número a partir de sus dígitos
2. Exponente de la mayor potencia de x que divide a y
3. Producto cartesiano de dos conjuntos
4. Subconjuntos de un conjunto
5. El algoritmo de Luhn

A continuación se muestran las soluciones.

1. Número a partir de sus dígitos

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

1.1. 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)

1.2. 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

2. Exponente de la mayor potencia de x que divide a y

Definir la función

   mayorExponente :: Integer -> Integer -> Integer

1	mayorExponente :: Integer -> Integer -> Integer

tal que mayorExponente a b es el exponente de la mayor potencia de a que divide a b. Por ejemplo,

   mayorExponente 2 8    ==  3
   mayorExponente 2 9    ==  0
   mayorExponente 5 100  ==  2
   mayorExponente 2 60   ==  2

mayorExponente 2 8 == 3

mayorExponente 2 9 == 0

mayorExponente 5 100 == 2

mayorExponente 2 60 == 2

Nota: Se supone que a > 1 y b > 0.

2.1. Soluciones en Haskell

import Test.QuickCheck

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

mayorExponente1 :: Integer -> Integer -> Integer
mayorExponente1 a b
  | rem b a /= 0 = 0
  | otherwise    = 1 + mayorExponente1 a (b `div` a)

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

mayorExponente2 :: Integer -> Integer -> Integer
mayorExponente2 a b = aux b 0
  where
    aux c r | rem c a /= 0 = r
            | otherwise    = aux (c `div` a) (r + 1)

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

mayorExponente3 :: Integer -> Integer -> Integer
mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]

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

mayorExponente4 :: Integer -> Integer -> Integer
mayorExponente4 a b =
  fst (until (\ (_,c) -> rem c a /= 0)
             (\ (r,c) -> (r+1, c `div` a))
             (0,b))

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

-- La propiedad es
prop_mayorExponente :: Integer -> Integer -> Property
prop_mayorExponente a b =
  a > 1 && b > 0 ==>
  all (== mayorExponente1 a b)
      [mayorExponente2 a b,
       mayorExponente3 a b,
       mayorExponente4 a b]

-- La comprobación es
--    λ> quickCheck prop_mayorExponente
--    +++ OK, passed 100 tests; 457 discarded.

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

-- La comparación es
--    λ> mayorExponente1 2 (2^(5*10^4))
--    50000
--    (0.12 secs, 179,578,424 bytes)
--    λ> mayorExponente2 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,533,376 bytes)
--    λ> mayorExponente3 2 (2^(5*10^4))
--    50000
--    (3.88 secs, 818,319,096 bytes)
--    λ> mayorExponente4 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,133,344 bytes)
--
--    λ> mayorExponente1 2 (2^(3*10^5))
--    300000
--    (2.94 secs, 5,762,199,064 bytes)
--    λ> mayorExponente2 2 (2^(3*10^5))
--    300000
--    (2.91 secs, 5,773,829,624 bytes)
--    λ> mayorExponente4 2 (2^(3*10^5))
--    300000
--    (3.70 secs, 5,771,396,824 bytes)

import Test.QuickCheck

-- 1ª solución

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

mayorExponente1 :: Integer -> Integer -> Integer

mayorExponente1 a b

| rem b a /= 0 = 0

| otherwise = 1 + mayorExponente1 a (b `div` a)

-- 2ª solución

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

mayorExponente2 :: Integer -> Integer -> Integer

mayorExponente2 a b = aux b 0

where

aux c r | rem c a /= 0 = r

| otherwise = aux (c `div` a) (r + 1)

-- 3ª solución

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

mayorExponente3 :: Integer -> Integer -> Integer

mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]

-- 4ª solución

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

mayorExponente4 :: Integer -> Integer -> Integer

mayorExponente4 a b =

fst (until (\ (_,c) -> rem c a /= 0)

(\ (r,c) -> (r+1, c `div` a))

(0,b))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_mayorExponente :: Integer -> Integer -> Property

prop_mayorExponente a b =

a > 1 && b > 0 ==>

all (== mayorExponente1 a b)

[mayorExponente2 a b,

mayorExponente3 a b,

mayorExponente4 a b]

-- La comprobación es

-- λ> quickCheck prop_mayorExponente

-- +++ OK, passed 100 tests; 457 discarded.

-- Comparación de eficiencia

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

-- La comparación es

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

-- 50000

-- (0.12 secs, 179,578,424 bytes)

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

-- 50000

-- (0.13 secs, 181,533,376 bytes)

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

-- 50000

-- (3.88 secs, 818,319,096 bytes)

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

-- 50000

-- (0.13 secs, 181,133,344 bytes)

-- λ> mayorExponente1 2 (2^(3*10^5))

-- 300000

-- (2.94 secs, 5,762,199,064 bytes)

-- λ> mayorExponente2 2 (2^(3*10^5))

-- 300000

-- (2.91 secs, 5,773,829,624 bytes)

-- λ> mayorExponente4 2 (2^(3*10^5))

-- 300000

-- (3.70 secs, 5,771,396,824 bytes)

2.2. Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

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

def mayorExponente1(a: int, b: int) -> int:
    if b % a != 0:
        return 0
    return 1 + mayorExponente1(a, b // a)

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

def mayorExponente2(a: int, b: int) -> int:
    def aux(c: int, r: int) -> int:
        if c % a != 0:
            return r
        return aux(c // a, r + 1)
    return aux(b, 0)

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

# naturales es el generador de los números naturales, Por ejemplo,
#    >>> list(islice(naturales(), 5))
#    [0, 1, 2, 3, 4]
def naturales() -> Iterator[int]:
    i = 0
    while True:
        yield i
        i += 1

def mayorExponente3(a: int, b: int) -> int:
    return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]

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

def mayorExponente4(a: int, b: int) -> int:
    r = 0
    while b % a == 0:
        b = b // a
        r = r + 1
    return r

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

def prueba1() -> None:
    for x in range(2, 11):
        for y in range(1, 11):
            print(x, y, mayorExponente4(x, y))


# La propiedad es
@given(st.integers(min_value=2, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_mayorExponente(a: int, b: int) -> None:
    r = mayorExponente1(a, b)
    assert mayorExponente2(a, b) == r
    assert mayorExponente3(a, b) == r
    assert mayorExponente4(a, b) == r

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

# 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('mayorExponente1(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente2(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente3(2, 2**(2*10**4))')
#    1.81 segundos
#    >>> tiempo('mayorExponente4(2, 2**(2*10**4))')
#    0.12 segundos
#
#    >>> tiempo('mayorExponente4(2, 2**(2*10**5))')
#    12.19 segundos

from itertools import islice

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import Iterator

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

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

if b % a != 0:

return 0

return 1 + mayorExponente1(a, b // a)

# 2ª solución

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

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

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

if c % a != 0:

return r

return aux(c // a, r + 1)

return aux(b, 0)

# 3ª solución

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

# naturales es el generador de los números naturales, Por ejemplo,

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

# [0, 1, 2, 3, 4]

def naturales() -> Iterator[int]:

i = 0

while True:

yield i

i += 1

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

return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]

# 4ª solución

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

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

r = 0

while b % a == 0:

b = b // a

r = r + 1

return r

# Comprobación de equivalencia

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

def prueba1() -> None:

for x in range(2, 11):

for y in range(1, 11):

print(x, y, mayorExponente4(x, y))

# La propiedad es

@given(st.integers(min_value=2, max_value=10),

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

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

r = mayorExponente1(a, b)

assert mayorExponente2(a, b) == r

assert mayorExponente3(a, b) == r

assert mayorExponente4(a, b) == r

# La comprobación es

# src> poetry run pytest -q exponente_mayor.py

# 1 passed in 0.16s

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

# 0.13 segundos

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

# 0.13 segundos

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

# 1.81 segundos

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

# 0.12 segundos

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

# 12.19 segundos

3. Producto cartesiano de dos conjuntos

Definir la función

   producto :: [a] -> [b] -> [(a,b)]

1	producto :: [a] -> [b] -> [(a,b)]

tal que producto xs ys es el producto cartesiano de xs e ys. Por ejemplo,

   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

1	producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

Comprobar con QuickCheck que el número de elementos de producto xs y es el producto del número de elementos de xs y de ys.

3.1. Soluciones en Haskell

import Test.QuickCheck

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

producto1 :: [a] -> [a] -> [(a,a)]
producto1 xs ys = [(x,y) | x <- xs, y <- ys]

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

producto2 :: [a] -> [a] -> [(a,a)]
producto2 []     _  = []
producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys

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

-- La propiedad es
prop_producto :: [Int] -> [Int] -> Bool
prop_producto xs ys =
  producto1 xs ys `iguales` producto2 xs ys

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,
--    iguales [3,2,3] [2,3]    ==  True
--    iguales [3,2,3] [2,3,2]  ==  True
--    iguales [3,2,3] [2,3,4]  ==  False
--    iguales [2,3] [4,5]      ==  False
iguales :: Ord a => [a] -> [a] -> Bool
iguales xs ys =
  subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por
-- ejemplo,
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto xs ys =
  [x | x <- xs, x `elem` ys] == xs

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

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

-- La comparación es
--    λ> length (producto1 [1..4000] [1..4000])
--    16000000
--    (2.33 secs, 1,537,551,208 bytes)
--    λ> length (producto2 [1..4000] [1..4000])
--    16000000
--    (2.87 secs, 2,434,095,160 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_elementos_producto :: [Int] -> [Int] -> Bool
prop_elementos_producto xs ys =
  length (producto1 xs ys) == length xs * length ys

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

import Test.QuickCheck

-- 1ª solución

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

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

producto1 xs ys = [(x,y) | x <- xs, y <- ys]

-- 2ª solución

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

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

producto2 [] _ = []

producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_producto :: [Int] -> [Int] -> Bool

prop_producto xs ys =

producto1 xs ys `iguales` producto2 xs ys

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,

-- iguales [3,2,3] [2,3] == True

-- iguales [3,2,3] [2,3,2] == True

-- iguales [3,2,3] [2,3,4] == False

-- iguales [2,3] [4,5] == False

iguales :: Ord a => [a] -> [a] -> Bool

iguales xs ys =

subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por

-- ejemplo,

-- subconjunto [3,2,3] [2,5,3,5] == True

-- subconjunto [3,2,3] [2,5,6,5] == False

subconjunto :: Ord a => [a] -> [a] -> Bool

subconjunto xs ys =

[x | x <- xs, x `elem` ys] == xs

-- La comprobación es

-- λ> quickCheck prop_producto

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (producto1 [1..4000] [1..4000])

-- 16000000

-- (2.33 secs, 1,537,551,208 bytes)

-- λ> length (producto2 [1..4000] [1..4000])

-- 16000000

-- (2.87 secs, 2,434,095,160 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_elementos_producto :: [Int] -> [Int] -> Bool

prop_elementos_producto xs ys =

length (producto1 xs ys) == length xs * length ys

-- La comprobación es

-- λ> quickCheck prop_elementos_producto

-- +++ OK, passed 100 tests.

3.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

setrecursionlimit(10**6)

A = TypeVar('A')
B = TypeVar('B')

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

def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    return [(x, y) for x in xs for y in ys]

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

def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    if xs:
        return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)
    return []

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

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_producto(xs: list[int], ys: list[int]) -> None:
    assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))

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

# 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('len(producto1(range(0, 1000), range(0, 500)))')
#    0.03 segundos
#    >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')
#    2.58 segundos

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_elementos_producto(xs: list[int], ys: list[int]) -> None:
    assert len(producto1(xs, ys)) == len(xs) * len(ys)

# La comprobación es
#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py
#    2 passed in 0.48s

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

B = TypeVar('B')

# 1ª solución

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

def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:

return [(x, y) for x in xs for y in ys]

# 2ª solución

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

def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:

if xs:

return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)

return []

# Comprobación de equivalencia

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

# La propiedad es

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

st.lists(st.integers()))

def test_producto(xs: list[int], ys: list[int]) -> None:

assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))

# La comprobación es

# src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py

# 1 passed in 0.31s

# 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('len(producto1(range(0, 1000), range(0, 500)))')

# 0.03 segundos

# >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')

# 2.58 segundos

# Comprobación de la propiedad

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

# La propiedad es

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

st.lists(st.integers()))

def test_elementos_producto(xs: list[int], ys: list[int]) -> None:

assert len(producto1(xs, ys)) == len(xs) * len(ys)

# La comprobación es

# src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py

# 2 passed in 0.48s

4. Subconjuntos de un conjunto

Definir la función

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

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

tal que subconjuntos xs es la lista de las subconjuntos de la lista xs. Por ejemplo,

   λ> subconjuntos [2,3,4]
   [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
   λ> subconjuntos [1,2,3,4]
   [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],
      [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]

λ> subconjuntos [2,3,4]

[[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]

λ> subconjuntos [1,2,3,4]

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

[2,3,4], [2,3], [2,4], [2], [3,4], [3], [4], []]

Comprobar con QuickChek que el número de elementos de subconjuntos xs es 2 elevado al número de elementos de xs.

4.1. Soluciones en Haskell

import Data.List (sort, subsequences)
import Test.QuickCheck

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

subconjuntos1 :: [a] -> [[a]]
subconjuntos1 []     = [[]]
subconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub
  where sub = subconjuntos1 xs

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

subconjuntos2 :: [a] -> [[a]]
subconjuntos2 []     = [[]]
subconjuntos2 (x:xs) = map (x:) sub ++ sub
  where sub = subconjuntos2 xs

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

subconjuntos3 :: [a] -> [[a]]
subconjuntos3 = subsequences

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

-- La propiedad es
prop_subconjuntos :: [Int] -> Bool
prop_subconjuntos xs =
  all (== sort (subconjuntos1 xs))
      [sort (subconjuntos2 xs),
       sort (subconjuntos3 xs)]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> length (subconjuntos1 [1..23])
--    8388608
--    (2.05 secs, 1,476,991,840 bytes)
--    λ> length (subconjuntos2 [1..23])
--    8388608
--    (0.87 secs, 1,208,555,312 bytes)
--    λ> length (subconjuntos3 [1..23])
--    8388608
--    (0.09 secs, 873,006,608 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_length_subconjuntos :: [Int] -> Bool
prop_length_subconjuntos xs =
  length (subconjuntos1 xs) == 2 ^ length xs

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos
--    +++ OK, passed 100 tests.

import Data.List (sort, subsequences)

import Test.QuickCheck

-- 1ª solución

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

subconjuntos1 :: [a] -> [[a]]

subconjuntos1 [] = [[]]

subconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub

where sub = subconjuntos1 xs

-- 2ª solución

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

subconjuntos2 :: [a] -> [[a]]

subconjuntos2 [] = [[]]

subconjuntos2 (x:xs) = map (x:) sub ++ sub

where sub = subconjuntos2 xs

-- 3ª solución

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

subconjuntos3 :: [a] -> [[a]]

subconjuntos3 = subsequences

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subconjuntos :: [Int] -> Bool

prop_subconjuntos xs =

all (== sort (subconjuntos1 xs))

[sort (subconjuntos2 xs),

sort (subconjuntos3 xs)]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (subconjuntos1 [1..23])

-- 8388608

-- (2.05 secs, 1,476,991,840 bytes)

-- λ> length (subconjuntos2 [1..23])

-- 8388608

-- (0.87 secs, 1,208,555,312 bytes)

-- λ> length (subconjuntos3 [1..23])

-- 8388608

-- (0.09 secs, 873,006,608 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_length_subconjuntos :: [Int] -> Bool

prop_length_subconjuntos xs =

length (subconjuntos1 xs) == 2 ^ length xs

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos

-- +++ OK, passed 100 tests.

4.2. Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st
from sympy import FiniteSet

setrecursionlimit(10**6)

A = TypeVar('A')

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

def subconjuntos1(xs: list[A]) -> list[list[A]]:
    if xs:
        sub = subconjuntos1(xs[1:])
        return [[xs[0]] + ys for ys in sub] + sub
    return [[]]

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

def subconjuntos2(xs: list[A]) -> list[list[A]]:
    if xs:
        sub = subconjuntos1(xs[1:])
        return list(map((lambda ys: [xs[0]] + ys), sub)) + sub
    return [[]]

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

def subconjuntos3(xs: list[A]) -> list[list[A]]:
    c = FiniteSet(*xs)
    return list(map(list, c.powerset()))

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

def subconjuntos4(xs: list[A]) -> list[list[A]]:
    return [list(ys)
            for r in range(len(xs)+1)
            for ys in combinations(xs, r)]

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

# La propiedad es
@given(st.lists(st.integers(), max_size=5))
def test_subconjuntos(xs: list[int]) -> None:
    ys = list(set(xs))
    r = sorted([sorted(zs) for zs in subconjuntos1(ys)])
    assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r
    assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r
    assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r

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

# 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('subconjuntos1(range(14))')
#    0.00 segundos
#    >>> tiempo('subconjuntos2(range(14))')
#    0.00 segundos
#    >>> tiempo('subconjuntos3(range(14))')
#    6.01 segundos
#    >>> tiempo('subconjuntos4(range(14))')
#    0.00 segundos
#
#    >>> tiempo('subconjuntos1(range(23))')
#    1.95 segundos
#    >>> tiempo('subconjuntos2(range(23))')
#    2.27 segundos
#    >>> tiempo('subconjuntos4(range(23))')
#    1.62 segundos

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.lists(st.integers(), max_size=7))
def test_length_subconjuntos(xs: list[int]) -> None:
    assert len(subconjuntos1(xs)) == 2 ** len(xs)

# La comprobación es
#    src> poetry run pytest -q subconjuntos_de_un_conjunto.py
#    2 passed in 0.95s

from itertools import combinations

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from sympy import FiniteSet

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

def subconjuntos1(xs: list[A]) -> list[list[A]]:

if xs:

sub = subconjuntos1(xs[1:])

return [[xs[0]] + ys for ys in sub] + sub

return [[]]

# 2ª solución

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

def subconjuntos2(xs: list[A]) -> list[list[A]]:

if xs:

sub = subconjuntos1(xs[1:])

return list(map((lambda ys: [xs[0]] + ys), sub)) + sub

return [[]]

# 3ª solución

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

def subconjuntos3(xs: list[A]) -> list[list[A]]:

c = FiniteSet(*xs)

return list(map(list, c.powerset()))

# 4ª solución

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

def subconjuntos4(xs: list[A]) -> list[list[A]]:

return [list(ys)

for r in range(len(xs)+1)

for ys in combinations(xs, r)]

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers(), max_size=5))

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

ys = list(set(xs))

r = sorted([sorted(zs) for zs in subconjuntos1(ys)])

assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r

assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r

assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r

# La comprobación es

# src> poetry run pytest -q subconjuntos_de_un_conjunto.py

# 1 passed in 0.89s

# 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('subconjuntos1(range(14))')

# 0.00 segundos

# >>> tiempo('subconjuntos2(range(14))')

# 0.00 segundos

# >>> tiempo('subconjuntos3(range(14))')

# 6.01 segundos

# >>> tiempo('subconjuntos4(range(14))')

# 0.00 segundos

# >>> tiempo('subconjuntos1(range(23))')

# 1.95 segundos

# >>> tiempo('subconjuntos2(range(23))')

# 2.27 segundos

# >>> tiempo('subconjuntos4(range(23))')

# 1.62 segundos

# Comprobación de la propiedad

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

# La propiedad es

@given(st.lists(st.integers(), max_size=7))

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

assert len(subconjuntos1(xs)) == 2 ** len(xs)

# La comprobación es

# src> poetry run pytest -q subconjuntos_de_un_conjunto.py

# 2 passed in 0.95s

5. El algoritmo de Luhn

El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores numéricos como los números de algunas tarjetas de crédito; por ejemplo, las de tipo Visa o Master Card.

El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente en aplicar los siguientes pasos a los dígitos del número de la tarjeta.

Se invierten los dígitos del número; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].
Se duplican los dígitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].
Se suman los dígitos de cada número; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.
Si el último dígito de la suma es 0, el número es válido; y no lo es, en caso contrario.

A los números válidos, se les llama números de Luhn.

Definir las siguientes funciones:

   digitosInv    :: Integer -> [Integer]
   doblePosImpar :: [Integer] -> [Integer]
   sumaDigitos   :: [Integer] -> Integer
   ultimoDigito  :: Integer -> Integer
   luhn          :: Integer -> Bool

digitosInv :: Integer -> [Integer]

doblePosImpar :: [Integer] -> [Integer]

sumaDigitos :: [Integer] -> Integer

ultimoDigito :: Integer -> Integer

luhn :: Integer -> Bool

tales que

digitosInv n es la lista de los dígitos del número n, en orden inverso. Por ejemplo,

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

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

doblePosImpar ns es la lista obtenida doblando los elementos de ns en las posiciones impares (empezando a contar en cero y dejando igual a los que están en posiciones pares. Por ejemplo,

     doblePosImpar [4,9,5,5]    ==  [4,18,5,10]
     doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]

1 2	doblePosImpar [4,9,5,5] == [4,18,5,10] doblePosImpar [4,9,5,5,7] == [4,18,5,10,7]

sumaDigitos ns es la suma de los dígitos de ns. Por ejemplo,

     sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =
                             = 19

1 2	sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 = = 19

ultimoDigito n es el último dígito de n. Por ejemplo,

     ultimoDigito 123 == 3
     ultimoDigito   0 == 0

1 2	ultimoDigito 123 == 3 ultimoDigito 0 == 0

luhn n se verifica si n es un número de Luhn. Por ejemplo,

     luhn 5594589764218858  ==  True
     luhn 1234567898765432  ==  False

1 2	luhn 5594589764218858 == True luhn 1234567898765432 == False

5.1. Soluciones en Haskell

-- Definición de digitosInv
-- ========================

digitosInv :: Integer -> [Integer]
digitosInv n = [read [x] | x <- reverse (show n)]

-- Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
-- se presentan otras definiciones.

-- Definiciones de doblePosImpar
-- =============================

-- 1ª definición
doblePosImpar :: [Integer] -> [Integer]
doblePosImpar []       = []
doblePosImpar [x]      = [x]
doblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs

-- 2ª definición
doblePosImpar2 :: [Integer] -> [Integer]
doblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs
doblePosImpar2 xs       = xs

-- 3ª definición
doblePosImpar3 :: [Integer] -> [Integer]
doblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]
  where f n x | odd n     = 2*x
              | otherwise = x

-- Definiciones de sumaDigitos
-- ===========================

sumaDigitos :: [Integer] -> Integer
sumaDigitos ns = sum [sum (digitosInv n) | n <- ns]

-- Nota: En el ejercicio "Suma de los dígitos de un número"
-- https://bit.ly/3U4u7WR se presentan otras definiciones.

-- Definición de ultimoDigito
-- ==========================

ultimoDigito :: Integer -> Integer
ultimoDigito n = n `rem` 10

-- Definiciones de luhn
-- ====================

-- 1ª definición
luhn1 :: Integer -> Bool
luhn1 n =
  ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0

-- 2ª definición
luhn2 :: Integer -> Bool
luhn2 =
  (==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv

-- Definición de digitosInv

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

digitosInv :: Integer -> [Integer]

digitosInv n = [read [x] | x <- reverse (show n)]

-- Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

-- se presentan otras definiciones.

-- Definiciones de doblePosImpar

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

-- 1ª definición

doblePosImpar :: [Integer] -> [Integer]

doblePosImpar [] = []

doblePosImpar [x] = [x]

doblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs

-- 2ª definición

doblePosImpar2 :: [Integer] -> [Integer]

doblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs

doblePosImpar2 xs = xs

-- 3ª definición

doblePosImpar3 :: [Integer] -> [Integer]

doblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]

where f n x | odd n = 2*x

| otherwise = x

-- Definiciones de sumaDigitos

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

sumaDigitos :: [Integer] -> Integer

sumaDigitos ns = sum [sum (digitosInv n) | n <- ns]

-- Nota: En el ejercicio "Suma de los dígitos de un número"

-- https://bit.ly/3U4u7WR se presentan otras definiciones.

-- Definición de ultimoDigito

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

ultimoDigito :: Integer -> Integer

ultimoDigito n = n `rem` 10

-- Definiciones de luhn

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

-- 1ª definición

luhn1 :: Integer -> Bool

luhn1 n =

ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0

-- 2ª definición

luhn2 :: Integer -> Bool

luhn2 =

(==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv

5.2. Soluciones en Python

# Definición de digitosInv
# ========================

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

# Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
# se presentan otras definiciones.

# Definiciones de doblePosImpar
# =============================

# 1ª definición
def doblePosImpar(xs: list[int]) -> list[int]:
    if len(xs) <= 1:
        return xs
    return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:])

# 2ª definición
def doblePosImpar2(xs: list[int]) -> list[int]:
    def f(n: int, x: int) -> int:
        if n % 2 == 1:
            return 2 * x
        return x
    return [f(n, x) for (n, x) in enumerate(xs)]

# Definiciones de sumaDigitos
# ===========================

def sumaDigitos(ns: list[int]) -> int:
    return sum((sum(digitosInv(n)) for n in ns))

# Nota: En el ejercicio "Suma de los dígitos de un número"
# https://bit.ly/3U4u7WR se presentan otras definiciones.

# Definición de ultimoDigito
# ==========================

def ultimoDigito(n: int) -> int:
    return n % 10

# Definiciones de luhn
# ====================

def luhn(n: int) -> bool:
    return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0

# Definición de digitosInv

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

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

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

# Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

# se presentan otras definiciones.

# Definiciones de doblePosImpar

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

# 1ª definición

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

if len(xs) <= 1:

return xs

return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:])

# 2ª definición

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

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

if n % 2 == 1:

return 2 * x

return x

return [f(n, x) for (n, x) in enumerate(xs)]

# Definiciones de sumaDigitos

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

def sumaDigitos(ns: list[int]) -> int:

return sum((sum(digitosInv(n)) for n in ns))

# Nota: En el ejercicio "Suma de los dígitos de un número"

# https://bit.ly/3U4u7WR se presentan otras definiciones.

# Definición de ultimoDigito

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

def ultimoDigito(n: int) -> int:

return n % 10

# Definiciones de luhn

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

def luhn(n: int) -> bool:

return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0

1. Número a partir de sus dígitos

2. Exponente de la mayor potencia de x que divide a y

3. Producto cartesiano de dos conjuntos

4. Subconjuntos de un conjunto

5. El algoritmo de Luhn

Se puede imprimir o compartir con