divisores :: Integer -> [Integer]

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

import Data.List (group, inits, nub, sort, subsequences)
import Data.Numbers.Primes (primeFactors)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

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

divisores2 :: Integer -> [Integer]
divisores2 n = filter ((== 0) . mod n) [1..n]

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

divisores3 :: Integer -> [Integer]
divisores3 =
  nub . sort . map product . subsequences . primeFactors

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

divisores4 :: Integer -> [Integer]
divisores4 =
  sort
  . map (product . concat)
  . productoCartesiano
  . map inits
  . group
  . primeFactors

-- (productoCartesiano xss) es el producto cartesiano de los conjuntos
-- xss. Por ejemplo,
--    λ> productoCartesiano [[1,3],[2,5],[6,4]]
--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
productoCartesiano :: [[a]] -> [[a]]
productoCartesiano []       = [[]]
productoCartesiano (xs:xss) =
  [x:ys | x <- xs, ys <- productoCartesiano xss]

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

divisores5 :: Integer -> [Integer]
divisores5 = sort
           . map (product . concat)
           . sequence
           . map inits
           . group
           . primeFactors

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

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> [Integer]) -> Spec
specG divisores = do
  it "e1" $
    divisores 30  `shouldBe`  [1,2,3,5,6,10,15,30]

spec :: Spec
spec = do
  describe "def. 1" $ specG divisores1
  describe "def. 2" $ specG divisores2
  describe "def. 3" $ specG divisores3
  describe "def. 4" $ specG divisores4
  describe "def. 5" $ specG divisores5

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

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

-- La propiedad es
prop_divisores :: Positive Integer -> Bool
prop_divisores (Positive n) =
  all (== divisores1 n)
      [ divisores2 n
      , divisores3 n
      , divisores4 n
      , divisores5 n
      ]

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

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

--    λ> length (divisores (product [1..11]))
--    540
--    (12.51 secs, 7,983,499,736 bytes)
--    λ> length (divisores2 (product [1..11]))
--    540
--    (4.81 secs, 4,790,146,656 bytes)
--    λ> length (divisores3 (product [1..11]))
--    540
--    (0.10 secs, 107,339,848 bytes)
--    λ> length (divisores4 (product [1..11]))
--    540
--    (0.02 secs, 1,702,616 bytes)
--    λ> length (divisores5 (product [1..11]))
--    540
--    (0.02 secs, 1,205,824 bytes)
--
--    λ> length (divisores3 (product [1..14]))
--    2592
--    (7.89 secs, 9,378,454,912 bytes)
--    λ> length (divisores4 (product [1..14]))
--    2592
--    (0.03 secs, 9,426,528 bytes)
--    λ> length (divisores5 (product [1..14]))
--    2592
--    (0.02 secs, 6,636,608 bytes)
--
--    λ> length (divisores4 (product [1..25]))
--    340032
--    (1.65 secs, 2,055,558,208 bytes)
--    λ> length (divisores5 (product [1..25]))
--    340032
--    (0.88 secs, 1,532,515,304 bytes)

from functools import reduce
from itertools import combinations, groupby
from itertools import product as cartesian_product
from operator import mul
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisors, factorint

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

def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n+1) if n % x == 0]

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

def divisores2(n: int) -> list[int]:
    return list(filter(lambda i: n % i == 0, range(1, n + 1)))

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

# primeFactors(n) es la lista de los factores primos de n. Por ejemplo,
#    >>> primeFactors(12)
#    [2, 2, 3]
def primeFactors(n: int) -> list[int]:
    return [a for a, b in factorint(n).items() for _ in range(b)]

# subsequences(xs) es la lista de las subsecuencias de xs; es decir, de
# las listas obtenidas eliminando algunos elementos de xs sin cambiar el
# orden de los elementos restantes. Por ejemplo,
#    >>> subsequences([1,2,3])
#    [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
def subsequences(xs: list[int]) -> list[list[int]]:
    return [list(ys)
            for i in range(len(xs) + 1)
            for ys in combinations(xs, i)]

# 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 divisores3(n: int) -> list[int]:
    return sorted(set(map(producto,
                          subsequences(primeFactors(n)))))

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

# inits(xs) es la lista de los segmentos iniciales de xs. Por ejemplo,
#    >>> inits([3,2,5,2])
#    [[], [3], [3, 2], [3, 2, 5], [3, 2, 5, 2]]
def inits(xs: list[int]) -> list[list[int]]:
    return [xs[:i] for i in range(len(xs) + 1)]

# productoCartesiano(xss) es el producto cartesiano de los conjuntos
# xss. Por ejemplo,
#    >>> productoCartesiano([[[2, 2]], [[], [3]], [[], [5]]])
#    [[[2,2],[],[]],[[2,2],[],[5]],[[2,2],[3],[]],[[2,2],[3],[5]]]
def productoCartesiano(xss: list[list[list[int]]]) -> list[list[list[int]]]:
    return [list(t) for t in cartesian_product(*xss)]

# concat(xss) es la lista obtenida concatenando los elementos de
# xss. Por ejemplo,
#    >>> concat([[2], [1,3], [5,2]])
#    [2, 1, 3, 5, 2]
def concat(xss: list[list[int]]) -> list[int]:
    return sum(xss, [])

def divisores4(n: int) -> list[int]:
    factores = primeFactors(n)
    factoresAgrupados = [list(g) for k, g in groupby(factores)]
    return sorted({producto(concat(xss))
                   for xss in productoCartesiano(list(map(inits,
                                                          factoresAgrupados)))})

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

def divisores5(n: int) -> list[int]:
    return divisors(n)

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

def test_divisores() -> None:
    for divisores in [divisores1,
                      divisores2,
                      divisores3,
                      divisores4,
                      divisores5]:
        assert divisores(30) == [1,2,3,5,6,10,15,30]
    print("Verificado")

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

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_divisores_equiv(n: int) -> None:
    r = divisores1(n)
    assert divisores2(n) == r
    assert divisores3(n) == r
    assert divisores4(n) == r
    assert divisores5(n) == r

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

# Comparación de la 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(divisores1(producto(range(1, 12))))')
#    1.95 segundos
#    >>> tiempo('len(divisores2(producto(range(1, 12))))')
#    3.20 segundos
#    >>> tiempo('len(divisores3(producto(range(1, 12))))')
#    0.04 segundos
#    >>> tiempo('len(divisores4(producto(range(1, 12))))')
#    0.00 segundos
#    >>> tiempo('len(divisores5(producto(range(1, 12))))')
#    0.00 segundos
#
#    >>> tiempo('len(divisores3(producto(range(1, 15))))')
#    2.50 segundos
#    >>> tiempo('len(divisores4(producto(range(1, 15))))')
#    0.00 segundos
#    >>> tiempo('len(divisores5(producto(range(1, 15))))')
#    0.00 segundos
#
#    >>> tiempo('len(divisores4(producto(range(1, 30))))')
#    5.10 segundos
#    >>> tiempo('len(divisores5(producto(range(1, 30))))')
#    0.91 segundos