Producto de los elementos de la diagonal principal
Publicado el 9 de marzo de 2024 por José A. Alonso

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

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

module Producto_de_los_elementos_de_la_diagonal_principal where

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

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

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

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

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

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

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

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

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

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

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

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

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

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

verifica :: IO ()
verifica = hspec spec

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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