Ir al contenido principal

El mes de mayo en Exercitium (Ejercicios con Haskell y Python)

Durante el mes de mayo he publicado en Exercitium las soluciones de los siguientes problemas:

A continuación se muestran las soluciones.

1. Posiciones de las diagonales principales

Las posiciones de una matriz con 3 filas y 4 columnas son

   (1,1) (1,2) (1,3) (1,4)
   (2,1) (2,2) (2,3) (2,4)
   (3,1) (3,2) (3,3) (3,4)

La posiciones de sus 6 diagonales principales son

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

Definir la función

   posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]

tal que posicionesdiagonalesprincipales m n es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,

  λ> mapM_ print (posicionesDiagonalesPrincipales 3 4)
  [(3,1)]
  [(2,1),(3,2)]
  [(1,1),(2,2),(3,3)]
  [(1,2),(2,3),(3,4)]
  [(1,3),(2,4)]
  [(1,4)]
  λ> mapM_ print (posicionesDiagonalesPrincipales 4 4)
  [(4,1)]
  [(3,1),(4,2)]
  [(2,1),(3,2),(4,3)]
  [(1,1),(2,2),(3,3),(4,4)]
  [(1,2),(2,3),(3,4)]
  [(1,3),(2,4)]
  [(1,4)]
  λ> mapM_ print (posicionesDiagonalesPrincipales 4 3)
  [(4,1)]
  [(3,1),(4,2)]
  [(2,1),(3,2),(4,3)]
  [(1,1),(2,2),(3,3)]
  [(1,2),(2,3)]
  [(1,3)]

1.1. Soluciones en Haskell

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

posicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales1 m n =
  [extension ij | ij <- iniciales]
  where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]]
        extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]]

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

posicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales2 m n =
  [zip [i..m] [1..n] | i <- [m,m-1..1]] ++
  [zip [1..m] [j..n] | j <- [2..n]]

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

verifica :: IO ()
verifica = hspec spec

specG :: (Int -> Int -> [[(Int, Int)]]) -> Spec
specG posicionesDiagonalesPrincipales = do
  it "e1" $
    posicionesDiagonalesPrincipales 3 4 `shouldBe`
      [[(3,1)],
       [(2,1),(3,2)],
       [(1,1),(2,2),(3,3)],
       [(1,2),(2,3),(3,4)],
       [(1,3),(2,4)],
       [(1,4)]]
  it "e2" $
    posicionesDiagonalesPrincipales 4 4 `shouldBe`
      [[(4,1)],
       [(3,1),(4,2)],
       [(2,1),(3,2),(4,3)],
       [(1,1),(2,2),(3,3),(4,4)],
       [(1,2),(2,3),(3,4)],
       [(1,3),(2,4)],
       [(1,4)]]
  it "e3" $
    posicionesDiagonalesPrincipales 4 3 `shouldBe`
      [[(4,1)],
       [(3,1),(4,2)],
       [(2,1),(3,2),(4,3)],
       [(1,1),(2,2),(3,3)],
       [(1,2),(2,3)],
       [(1,3)]]

spec :: Spec
spec = do
  describe "def. 1" $ specG posicionesDiagonalesPrincipales1
  describe "def. 2" $ specG posicionesDiagonalesPrincipales2

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

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_posicionesDiagonalesPrincipales2 :: Positive Int -> Positive Int -> Bool
prop_posicionesDiagonalesPrincipales2 (Positive m) (Positive n) =
  posicionesDiagonalesPrincipales1 m n ==
  posicionesDiagonalesPrincipales2 m n

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

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

-- La comparación es
--   λ> length (posicionesDiagonalesPrincipales1 (10^7) (10^6))
--   10999999
--   (6.14 secs, 3,984,469,440 bytes)
--   λ> length (posicionesDiagonalesPrincipales2 (10^7) (10^6))
--   10999999
--   (3.07 secs, 2,840,469,440 bytes)

1.2. Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

matriz = list[list[tuple[int, int]]]

def posicionesDiagonalesPrincipales1(m: int, n: int) -> matriz:
    def iniciales() -> list[tuple[int, int]]:
        return [(i,1) for i in range(m,1,-1)] + [(1,j) for j in range(1, n+1)]
    def extension(p: tuple[int, int]) -> list[tuple[int, int]]:
        (i,j) = p
        return [(i+k,j+k) for k in range(0, 1+min(m-i, n-j))]
    return [extension(ij) for ij in iniciales()]

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

def posicionesDiagonalesPrincipales2(m: int, n: int) -> matriz:
    return [list(zip(range(i,m+1), range(1,n+1))) for i in range(m,0,-1)] + \
           [list(zip(range(1,m+1), range(j,n+1))) for j in range(2,n+1)]

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

def test_posicionesDiagonalesPrincipales() -> None:
    for posicionesDiagonalesPrincipales in [posicionesDiagonalesPrincipales1,
                                            posicionesDiagonalesPrincipales2]:
        assert posicionesDiagonalesPrincipales(3, 4) == \
            [[(3,1)],
             [(2,1),(3,2)],
             [(1,1),(2,2),(3,3)],
             [(1,2),(2,3),(3,4)],
             [(1,3),(2,4)],
             [(1,4)]]
        assert posicionesDiagonalesPrincipales(4, 4) == \
            [[(4,1)],
             [(3,1),(4,2)],
             [(2,1),(3,2),(4,3)],
             [(1,1),(2,2),(3,3),(4,4)],
             [(1,2),(2,3),(3,4)],
             [(1,3),(2,4)],
             [(1,4)]]
        assert posicionesDiagonalesPrincipales(4, 3) == \
            [[(4,1)],
             [(3,1),(4,2)],
             [(2,1),(3,2),(4,3)],
             [(1,1),(2,2),(3,3)],
             [(1,2),(2,3)],
             [(1,3)]]
    print("Verificado")

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

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.integers(min_value=1, max_value=100),
       st.integers(min_value=1, max_value=100))
def test_posicionesDiagonalesPrincipales_equiv(m: int, n: int) -> None:
    assert posicionesDiagonalesPrincipales1(m, n) == \
           posicionesDiagonalesPrincipales2(m, n)

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

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

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

# La comparación es
#    >>> tiempo('posicionesDiagonalesPrincipales1(10**4, 2*10**3)')
#    3.32 segundos
#    >>> tiempo('posicionesDiagonalesPrincipales2(10**4, 2*10**3)')
#    2.16 segundos

2. Diagonales principales de una matriz

La lista de las diagonales principales de la matriz

   1  2  3  4
   5  6  7  8
   9 10 11 12

es

   [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

Definir la función

   diagonalesPrincipales :: Array (Int,Int) a -> [[a]]

tal que diagonalesPrincipales p es la lista de las diagonales principales de p. Por ejemplo,

   λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])
   [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

2.1. Soluciones en Haskell

import Data.Array (Array, (!), bounds, listArray)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

diagonalesPrincipales1 :: Array (Int,Int) a -> [[a]]
diagonalesPrincipales1 p =
  [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales1 m n]
  where (_,(m,n)) = bounds p

posicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales1 m n =
  [extension ij | ij <- iniciales]
  where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]]
        extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]]

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

diagonalesPrincipales2 :: Array (Int,Int) a -> [[a]]
diagonalesPrincipales2 p =
  [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales2 m n]
  where (_,(m,n)) = bounds p

posicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales2 m n =
  [zip [i..m] [1..n] | i <- [m,m-1..1]] ++
  [zip [1..m] [j..n] | j <- [2..n]]

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

verifica :: IO ()
verifica = hspec spec

specG :: (Array (Int,Int) Int -> [[Int]]) -> Spec
specG diagonalesPrincipales = do
  it "e1" $
    diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) `shouldBe`
      [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

spec :: Spec
spec = do
  describe "def. 1" $ specG diagonalesPrincipales1
  describe "def. 2" $ specG diagonalesPrincipales2

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

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_diagonalesPrincipales2 :: Positive Int -> Positive Int -> Bool
prop_diagonalesPrincipales2 (Positive m) (Positive n) =
  diagonalesPrincipales1 p == diagonalesPrincipales2 p
  where p = listArray ((1,1),(m,n)) [1..]

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

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

-- La comparación es
--    λ> length (diagonalesPrincipales1 (listArray ((1,1),(10^4,10^4)) [1..]))
--    19999
--    (6.90 secs, 8,010,369,224 bytes)
--    λ> length (diagonalesPrincipales2 (listArray ((1,1),(10^4,10^4)) [1..]))
--    19999
--    (6.78 secs, 8,008,289,224 bytes)

2.2. Soluciones en Python

from typing import TypeVar

from src.Posiciones_diagonales_principales import (
    posicionesDiagonalesPrincipales1, posicionesDiagonalesPrincipales2)

A = TypeVar('A')

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

matriz = list[list[A]]

def diagonalesPrincipales1(p: matriz[A]) -> list[list[A]]:
    m = len(p)
    n = len(p[0])
    return [[p[i-1][j-1] for (i,j) in ijs]
            for ijs in posicionesDiagonalesPrincipales1(m, n)]

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

def diagonalesPrincipales2(p: matriz[A]) -> list[list[A]]:
    m = len(p)
    n = len(p[0])
    return [[p[i-1][j-1] for (i,j) in ijs]
            for ijs in posicionesDiagonalesPrincipales2(m, n)]

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

def test_diagonalesPrincipales() -> None:
    for diagonalesPrincipales in [diagonalesPrincipales1,
                                  diagonalesPrincipales2]:
        assert diagonalesPrincipales([[ 1, 2, 3, 4],
                                      [ 5, 6, 7, 8],
                                      [ 9,10,11,12]]) == \
                    [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
    print("Verificado")

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

3. Matrices de Toepliz

Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

   |2 5 1 6|       |2 5 1 6|
   |4 2 5 1|       |4 2 6 1|
   |7 4 2 5|       |7 4 2 5|
   |9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

   ej1, ej2 :: Array (Int,Int) Int
   ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
   ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

   esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que esToeplitz p se verifica si la matriz p es de Toeplitz. Por ejemplo,

   esToeplitz ej1  ==  True
   esToeplitz ej2  ==  False

3.1. Soluciones en Haskell

import Data.Array (Array, (!), bounds, listArray)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

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

esToeplitz1 :: Eq a => Array (Int,Int) a -> Bool
esToeplitz1 p =
  esCuadrada p &&
  all todosIguales (diagonalesPrincipales p)

-- (esCuadrada p) se verifica si la matriz p es cuadrada. Por ejemplo,
--    esCuadrada (listArray ((1,1),(4,4)) [1..])  ==  True
--    esCuadrada (listArray ((1,1),(3,4)) [1..])  ==  False
esCuadrada :: Eq a => Array (Int,Int) a -> Bool
esCuadrada p = m == n
  where (_,(m,n)) = bounds p

-- (diagonalesPrincipales p) es la lista de las diagonales principales
-- de p. Por ejemplo,
--    λ> diagonalesPrincipales ej1
--    [[2,2,2,2],[5,5,5],[1,1],[6],[2,2,2,2],[4,4,4],[7,7],[9]]
--    λ> diagonalesPrincipales ej2
--    [[2,2,2,2],[5,6,5],[1,1],[6],[2,2,2,2],[4,4,4],[7,7],[9]]
diagonalesPrincipales :: Array (Int,Int) a -> [[a]]
diagonalesPrincipales p =
  [[p ! i |i <- is] | is <- posicionesDiagonalesPrincipales m n]
  where (_,(m,n)) = bounds p

-- (posicionesDiagonalesPrincipales m n) es la lista de las
-- posiciones de las diagonales principales de una matriz con m filas y
-- n columnas. Por ejemplo,
--   λ> mapM_ print (posicionesDiagonalesPrincipales 3 4)
--   [(3,1)]
--   [(2,1),(3,2)]
--   [(1,1),(2,2),(3,3)]
--   [(1,2),(2,3),(3,4)]
--   [(1,3),(2,4)]
--   [(1,4)]
--   λ> mapM_ print (posicionesDiagonalesPrincipales 4 4)
--   [(4,1)]
--   [(3,1),(4,2)]
--   [(2,1),(3,2),(4,3)]
--   [(1,1),(2,2),(3,3),(4,4)]
--   [(1,2),(2,3),(3,4)]
--   [(1,3),(2,4)]
--   [(1,4)]
--   λ> mapM_ print (posicionesDiagonalesPrincipales 4 3)
--   [(4,1)]
--   [(3,1),(4,2)]
--   [(2,1),(3,2),(4,3)]
--   [(1,1),(2,2),(3,3)]
--   [(1,2),(2,3)]
--   [(1,3)]
posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales m n =
  [zip [i..m] [1..n] | i <- [m,m-1..1]] ++
  [zip [1..m] [j..n] | j <- [2..n]]

-- (todosIguales xs) se verifica si todos los elementos de xs son
-- iguales. Por ejemplo,
--    todosIguales [5,5,5]  ==  True
--    todosIguales [5,4,5]  ==  False
todosIguales :: Eq a => [a] -> Bool
todosIguales []     = True
todosIguales (x:xs) = all (== x) xs

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

esToeplitz2 :: Eq a => Array (Int,Int) a -> Bool
esToeplitz2 p = m == n &&
                and [p!(i,j) == p!(i+1,j+1) |
                     i <- [1..n-1], j <- [1..n-1]]
  where (_,(m,n)) = bounds p

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

verifica :: IO ()
verifica = hspec spec

specG :: (Array (Int,Int) Int -> Bool) -> Spec
specG esToeplitz = do
  it "e1" $
    esToeplitz ej1 `shouldBe` True
  it "e2" $
    esToeplitz ej2 `shouldBe` False

spec :: Spec
spec = do
  describe "def. 1" $ specG esToeplitz1
  describe "def. 2" $ specG esToeplitz2

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

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

-- La comparación es
--    λ> esToeplitz1 (listArray ((1,1),(2*10^3,2*10^3)) (repeat 1))
--    True
--    (2.26 secs, 2,211,553,888 bytes)
--    λ> esToeplitz2 (listArray ((1,1),(2*10^3,2*10^3)) (repeat 1))
--    True
--    (4.26 secs, 3,421,651,032 bytes)

3.2. Soluciones en Python

from timeit import Timer, default_timer
from typing import TypeVar

from src.Diagonales_principales import diagonalesPrincipales1

A = TypeVar('A')

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

ej1: list[list[int]] = [[2,5,1,6],[4,2,5,1],[7,4,2,5],[9,7,4,2]]
ej2: list[list[int]] = [[2,5,1,6],[4,2,6,1],[7,4,2,5],[9,7,4,2]]

#  esCuadrada(p) se verifica si la matriz p es cuadrada. Por ejemplo,
#    >>> esCuadrada([[1,2],[3,4]])       == True
#    >>> esCuadrada([[1,2],[3,4],[5,6]]) == False
#    >>> esCuadrada([[1,2,3],[4,5,6]])   == False
def esCuadrada(p : list[list[A]]) -> bool:
    return all(len(elemento) == len(p) for elemento in p)

# todosIguales(xs) se verifica si todos los elementos de xs son
# iguales. Por ejemplo,
#    todosIguales([5,5,5])  ==  True
#    todosIguales([5,4,5])  ==  False
def todosIguales(xs: list[A]) -> bool:
    return all(x == xs[0] for x in xs)

def esToeplitz1(p: list[list[A]]) -> bool:
    return esCuadrada(p) and all(todosIguales(xs) for xs in diagonalesPrincipales1(p))

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

def esToeplitz2(p: list[list[A]]) -> bool:
    n = len(p)
    return all(len(xs) == n for xs in p) and \
           all(p[i][j] == p[i+1][j+1] for i in range(0,n-1)
                                      for j in range(0,n-1))

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

def test_esToeplitz() -> None:
    for esToeplitz in [esToeplitz1, esToeplitz2]:
        assert esToeplitz(ej1)
        assert not esToeplitz(ej2)
    print("Verificado")

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

# 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('esToeplitz1([[1]*2*10**3]*2*10**3)')
#    1.52 segundos
#    >>> tiempo('esToeplitz2([[1]*2*10**3]*2*10**3)')
#    0.51 segundos

4. Diferencia simétrica

La diferencia simétrica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica de {2,5,3} y {4,2,3,7} es {5,4,7}.

Definir la función

   diferenciaSimetrica :: Ord a => [a] -> [a] -> [a]

tal que diferenciaSimetrica xs ys es la diferencia simétrica de xs e ys. Por ejemplo,

   diferenciaSimetrica [2,5,3] [4,2,3,7]    ==  [4,5,7]
   diferenciaSimetrica [2,5,3] [5,2,3]      ==  []
   diferenciaSimetrica [2,5,2] [4,2,3,7]    ==  [3,4,5,7]
   diferenciaSimetrica [2,5,2] [4,2,4,7]    ==  [4,5,7]
   diferenciaSimetrica [2,5,2,4] [4,2,4,7]  ==  [5,7]

4.1. Soluciones en Haskell

module Diferencia_simetrica where

import Data.List ((\\), intersect, nub, sort, union)
import qualified Data.Set as S
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

diferenciaSimetrica1 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica1 xs ys =
  sort (nub ([x | x <- xs, x `notElem` ys] ++
             [y | y <- ys, y `notElem` xs]))

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

diferenciaSimetrica2 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica2 xs ys =
  sort (nub (filter (`notElem` ys) xs ++
             filter (`notElem` xs) ys))

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

diferenciaSimetrica3 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica3 xs ys =
  sort (nub (union xs ys \\ intersect xs ys))

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

diferenciaSimetrica4 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica4 xs ys =
  [x | x <- sort (nub (xs ++ ys))
     , x `notElem` xs || x `notElem` ys]

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

diferenciaSimetrica5 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica5 xs ys =
  S.elems ((xs' `S.union` ys') `S.difference` (xs' `S.intersection` ys'))
  where xs' = S.fromList xs
        ys' = S.fromList ys

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

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> [Int] -> [Int]) -> Spec
specG diferenciaSimetrica = do
  it "e1" $
    diferenciaSimetrica [2,5,3] [4,2,3,7]    `shouldBe`  [4,5,7]
  it "e2" $
    diferenciaSimetrica [2,5,3] [5,2,3]      `shouldBe`  []
  it "e3" $
    diferenciaSimetrica [2,5,2] [4,2,3,7]    `shouldBe`  [3,4,5,7]
  it "e4" $
    diferenciaSimetrica [2,5,2] [4,2,4,7]    `shouldBe`  [4,5,7]
  it "e5" $
    diferenciaSimetrica [2,5,2,4] [4,2,4,7]  `shouldBe`  [5,7]

spec :: Spec
spec = do
  describe "def. 1" $ specG diferenciaSimetrica1
  describe "def. 2" $ specG diferenciaSimetrica2
  describe "def. 3" $ specG diferenciaSimetrica3
  describe "def. 4" $ specG diferenciaSimetrica4
  describe "def. 5" $ specG diferenciaSimetrica5

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

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

-- La propiedad es
prop_diferenciaSimetrica :: [Int] -> [Int] -> Bool
prop_diferenciaSimetrica xs ys =
  all (== diferenciaSimetrica1 xs ys)
      [diferenciaSimetrica2 xs ys,
       diferenciaSimetrica3 xs ys,
       diferenciaSimetrica4 xs ys,
       diferenciaSimetrica5 xs ys]

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

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

-- La comparación es
--    λ> length (diferenciaSimetrica1 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (2.34 secs, 10,014,360 bytes)
--    λ> length (diferenciaSimetrica2 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (2.41 secs, 8,174,264 bytes)
--    λ> length (diferenciaSimetrica3 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (5.84 secs, 10,232,006,288 bytes)
--    λ> length (diferenciaSimetrica4 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (5.83 secs, 14,814,184 bytes)
--    λ> length (diferenciaSimetrica5 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (0.02 secs, 7,253,496 bytes)

4.2. Soluciones en Python

from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

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

def diferenciaSimetrica1(xs: list[A], ys: list[A]) -> list[A]:
    return list(set([x for x in xs if x not in ys] + \
                    [y for y in ys if y not in xs]))

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

def diferenciaSimetrica2(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(list(filter(lambda x: x not in ys, xs)) + \
                    list(filter(lambda y: y not in xs, ys))))

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

def diferenciaSimetrica3(xs: list[A], ys: list[A]) -> list[A]:
    s1 = set(xs)
    s2 = set(ys)
    return list((s1 | s2) - (s1 & s2))

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

def diferenciaSimetrica4(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in list(set(xs + ys)) if x not in xs or x not in ys]

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

def diferenciaSimetrica5(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) ^ set(ys))

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

def test_diferenciaSimetrica() -> None:
    for diferenciaSimetrica in [diferenciaSimetrica1,
                                diferenciaSimetrica2,
                                diferenciaSimetrica3,
                                diferenciaSimetrica4,
                                diferenciaSimetrica5]:
        assert diferenciaSimetrica([2,5,3], [4,2,3,7])    ==  [4,5,7]
        assert diferenciaSimetrica([2,5,3], [5,2,3])      ==  []
        assert diferenciaSimetrica([2,5,2], [4,2,3,7])    ==  [3,4,5,7]
        assert diferenciaSimetrica([2,5,2], [4,2,4,7])    ==  [4,5,7]
        assert diferenciaSimetrica([2,5,2,4], [4,2,4,7])  ==  [5,7]
    print("Verificado")

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

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

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_diferenciaSimetrica_equiv(xs: list[int], ys: list[int]) -> None:
    assert set(diferenciaSimetrica1(xs, ys)) ==\
           set(diferenciaSimetrica2(xs, ys)) ==\
           set(diferenciaSimetrica3(xs, ys)) ==\
           set(diferenciaSimetrica4(xs, ys)) ==\
           set(diferenciaSimetrica5(xs, ys))

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

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


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

# La comparación es
#    >>> tiempo('diferenciaSimetrica1(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    1.62 segundos
#    >>> tiempo('diferenciaSimetrica2(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    1.60 segundos
#    >>> tiempo('diferenciaSimetrica3(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    0.02 segundos
#    >>> tiempo('diferenciaSimetrica4(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    2.25 segundos
#    >>> tiempo('diferenciaSimetrica5(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    0.01 segundos

5. Conjunto de primos relativos

Dos números enteros positivos son primos relativos si no tienen ningún factor primo en común; es decir, si 1 es su único divisor común. Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3.

Definir la función

   primosRelativos :: [Int] -> Bool

tal que primosRelativos xs se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,

   primosRelativos [6,35]         ==  True
   primosRelativos [6,27]         ==  False
   primosRelativos [2,3,4]        ==  False
   primosRelativos [6,35,11]      ==  True
   primosRelativos [6,35,11,221]  ==  True
   primosRelativos [6,35,11,231]  ==  False

5.1. Soluciones en Haskell

import Data.Numbers.Primes (primes)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

primosRelativos1 :: [Int] -> Bool
primosRelativos1 []     = True
primosRelativos1 (x:xs) =
  and [sonPrimosRelativos x y | y <- xs] && primosRelativos1 xs

-- (sonPrimosRelativos x y) se verifica si x e y son primos
-- relativos. Por ejemplo,
--    sonPrimosRelativos 6 35  ==  True
--    sonPrimosRelativos 6 27  ==  False
sonPrimosRelativos :: Int -> Int -> Bool
sonPrimosRelativos x y =
  gcd x y == 1

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

primosRelativos2 :: [Int] -> Bool
primosRelativos2 []     = True
primosRelativos2 (x:xs) =
  all (sonPrimosRelativos x) xs && primosRelativos2 xs

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

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> Bool) -> Spec
specG primosRelativos = do
  it "e1" $
    primosRelativos [6,35]         `shouldBe`  True
  it "e2" $
    primosRelativos [6,27]         `shouldBe`  False
  it "e3" $
    primosRelativos [2,3,4]        `shouldBe`  False
  it "e4" $
    primosRelativos [6,35,11]      `shouldBe`  True
  it "e5" $
    primosRelativos [6,35,11,221]  `shouldBe`  True
  it "e6" $
    primosRelativos [6,35,11,231]  `shouldBe`  False

spec :: Spec
spec = do
  describe "def. 1" $ specG primosRelativos1
  describe "def. 2" $ specG primosRelativos2

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

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

-- La propiedad es
prop_primosRelativos :: [Positive Int] -> Bool
prop_primosRelativos xs =
  primosRelativos1 ys == primosRelativos2 ys
  where ys = getPositive <$> xs

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

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

-- La comparación es
--    λ> primosRelativos1 (take 2000 primes)
--    True
--    (1.43 secs, 1,730,437,768 bytes)
--    λ> primosRelativos2 (take 2000 primes)
--    True
--    (0.99 secs, 1,490,445,736 bytes)

5.2. Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st
from sympy.ntheory.generate import primerange

setrecursionlimit(10**6)

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

# sonPrimosRelativos(x, y) se verifica si x e y son primos
# relativos. Por ejemplo,
#    sonPrimosRelativos(6, 35)  ==  True
#    sonPrimosRelativos(6, 27)  ==  False
def sonPrimosRelativos(x: int, y: int) -> bool:
    return gcd(x, y) == 1

def primosRelativos1(ys: list[int]) -> bool:
    if not ys:
        return True
    x, *xs = ys
    return all(sonPrimosRelativos(x, z) for z in xs) and primosRelativos1(xs)

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

def primosRelativos2(ys: list[int]) -> bool:
    if not ys:
        return True
    for y in ys[1:]:
        if gcd(ys[0], y) != 1:
            return False
    return primosRelativos2(ys[1:])

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

def test_primosRelativos() -> None:
    for primosRelativos in [primosRelativos1,
                            primosRelativos2]:
        assert primosRelativos([6,35])
        assert not primosRelativos([6,27])
        assert not primosRelativos([2,3,4])
        assert primosRelativos([6,35,11])
        assert primosRelativos([6,35,11,221])
        assert not primosRelativos([6,35,11,231])
    print("Verificado")

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

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

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=1000)))
def test_primosRelativos_equiv(xs: list[int]) -> None:
    assert primosRelativos1(xs) == primosRelativos2(xs)

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

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

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

# La comparación es
#    >>> tiempo('primosRelativos1(list(primerange(40000)))')
#    2.20 segundos
#    >>> tiempo('primosRelativos2(list(primerange(40000)))')
#    1.82 segundos

6. Descomposiciones triangulares

Los números triangulares se forman como sigue

   *     *      *
        * *    * *
              * * *
   1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

    1 = 1
    3 = 1 + 2
    6 = 1 + 2 + 3
   10 = 1 + 2 + 3 + 4
   15 = 1 + 2 + 3 + 4 + 5

Definir la función

   descomposicionesTriangulares :: Int -> [(Int, Int, Int)]

tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,

   λ> descomposicionesTriangulares3 4
   []
   λ> descomposicionesTriangulares3 5
   [(1,1,3)]
   λ> descomposicionesTriangulares3 12
   [(1,1,10),(3,3,6)]
   λ> descomposicionesTriangulares3 30
   [(1,1,28),(3,6,21),(10,10,10)]
   λ> descomposicionesTriangulares3 61
   [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
   λ> descomposicionesTriangulares3 52
   [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
   λ> descomposicionesTriangulares3 82
   [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
   λ> length (descomposicionesTriangulares3 (5*10^5))
   124

6.1. Soluciones en Haskell

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

descomposicionesTriangulares1 :: Int -> [(Int, Int, Int)]
descomposicionesTriangulares1 n =
  [(x,y,z) | x <- xs,
             y <- xs,
             z <- xs,
             x <= y && y <= z,
             x + y + z == n]
  where xs = takeWhile (<=n) triangulares

-- triangulares es la lista de los números triangulares. Por ejemplo,
--    take 9 triangulares  ==  [1,3,6,10,15,21,28,36,45]
triangulares :: [Int]
triangulares = scanl (+) 1 [2..]

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

descomposicionesTriangulares2 :: Int -> [(Int, Int, Int)]
descomposicionesTriangulares2 n =
  [(x,y,z) | x <- xs,
             y <- xs,
             x <= y,
             z <- xs,
             y <= z,
             x + y + z == n]
  where xs = takeWhile (<=n) triangulares

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

descomposicionesTriangulares3 :: Int -> [(Int, Int, Int)]
descomposicionesTriangulares3 n =
  [(x,y,z) | x <- xs,
             y <- xs,
             x <= y,
             let z = n - x - y,
             y <= z,
             z `elem` xs]
  where xs = takeWhile (<=n) triangulares

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

descomposicionesTriangulares4 :: Int -> [(Int, Int, Int)]
descomposicionesTriangulares4 n =
  [(x,y,n-x-y) | x <- xs,
                 y <- dropWhile (<x) xs,
                 let z = n - x - y,
                 y <= z,
                 z `elem` xs]
  where xs = takeWhile (<=n) triangulares

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

verifica :: IO ()
verifica = hspec spec

specG :: (Int -> [(Int, Int, Int)]) -> Spec
specG descomposicionesTriangulares = do
  it "e1" $
    descomposicionesTriangulares  4 `shouldBe`
      []
  it "e2" $
    descomposicionesTriangulares  5 `shouldBe`
      [(1,1,3)]
  it "e3" $
    descomposicionesTriangulares 12 `shouldBe`
      [(1,1,10),(3,3,6)]
  it "e4" $
    descomposicionesTriangulares 30 `shouldBe`
      [(1,1,28),(3,6,21),(10,10,10)]
  it "e5" $
    descomposicionesTriangulares 61 `shouldBe`
      [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
  it "e6" $
    descomposicionesTriangulares 52 `shouldBe`
      [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
  it "e7" $
    descomposicionesTriangulares 82 `shouldBe`
      [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]

spec :: Spec
spec = do
  describe "def. 1" $ specG descomposicionesTriangulares1
  describe "def. 2" $ specG descomposicionesTriangulares2
  describe "def. 3" $ specG descomposicionesTriangulares3
  describe "def. 4" $ specG descomposicionesTriangulares4

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

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

-- La propiedad es
prop_descomposicionesTriangulares_equiv ::  Positive Int -> Bool
prop_descomposicionesTriangulares_equiv (Positive n) =
  all (== descomposicionesTriangulares1 n)
      [descomposicionesTriangulares2 n,
       descomposicionesTriangulares3 n,
       descomposicionesTriangulares4 n]

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

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

-- La comparación es
--   λ> last (descomposicionesTriangulares1 (2*10^4))
--   (5671,6328,8001)
--   (3.34 secs, 1,469,517,168 bytes)
--   λ> last (descomposicionesTriangulares2 (2*10^4))
--   (5671,6328,8001)
--   (1.29 secs, 461,433,928 bytes)
--   λ> last (descomposicionesTriangulares3 (2*10^4))
--   (5671,6328,8001)
--   (0.08 secs, 6,574,056 bytes)
--
--   λ> last (descomposicionesTriangulares3 (5*10^5))
--   (140185,148240,211575)
--   (2.12 secs, 151,137,280 bytes)
--   λ> last (descomposicionesTriangulares4 (5*10^5))
--   (140185,148240,211575)
--   (2.30 secs, 103,280,216 bytes)

6.2. Soluciones en Python

from itertools import count, dropwhile, takewhile
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
# ===========

# triangular(n) es el n-ésimo número triangular. Por ejemplo,
#    triangular(9) == 45
def triangular(n: int) -> int:
    if n == 1:
        return 1
    return triangular(n-1) + n

# triangulares1() es la lista de los números triangulares. Por ejemplo,
#    >>> from itertools import islice
#    >>> list(islice(triangulares1(), 10))
#    [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
def triangulares1() -> Iterator[int]:
    return (triangular(n) for n in count(1))

def descomposicionesTriangulares1(n: int) -> list[tuple[int, int, int]]:
    xs = list(takewhile(lambda x : x <= n, triangulares1()))
    return [(x,y,z) for x in xs for y in xs for z in xs if
            x <= y <= z and x + y + z == n]

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

def triangulares2() -> Iterator[int]:
    return ((n*(n+1)) // 2 for n in count(1))

def descomposicionesTriangulares2(n: int) -> list[tuple[int, int, int]]:
    xs = list(takewhile(lambda x : x <= n, triangulares2()))
    return [(x,y,z) for x in xs for y in xs for z in xs if
            x <= y <= z and x + y + z == n]

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

def descomposicionesTriangulares3(n: int) -> list[tuple[int, int, int]]:
    xs = list(takewhile(lambda x : x <= n, triangulares2()))
    return [(x,y,z)
            for x in xs
            for y in xs
            if x <= y
            for z in xs
            if y <= z
            if x + y + z == n]

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

def descomposicionesTriangulares4(n: int) -> list[tuple[int, int, int]]:
    xs = list(takewhile(lambda x : x <= n, triangulares2()))
    ts = []
    for x in xs:
        for y in xs:
            if x <= y:
                z = n - x - y
                if y <= z and z in xs:
                    ts.append((x, y, z))
    return ts

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

def descomposicionesTriangulares5(n: int) -> list[tuple[int, int, int]]:
    xs = list(takewhile(lambda a : a <= n, triangulares2()))
    ts = []
    for x in xs:
        ys = list(dropwhile(lambda y: y < x, xs))
        for y in ys:
            z = n - x - y
            if y <= z and z in xs:
                ts.append((x, y, z))
    return ts

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

def test_descomposicionesTriangulares() -> None:
    for descomposicionesTriangulares in [descomposicionesTriangulares1,
                                         descomposicionesTriangulares2,
                                         descomposicionesTriangulares3,
                                         descomposicionesTriangulares4,
                                         descomposicionesTriangulares5]:
        assert descomposicionesTriangulares(4) ==\
            []
        assert descomposicionesTriangulares(5) ==\
            [(1,1,3)]
        assert descomposicionesTriangulares(12) ==\
            [(1,1,10),(3,3,6)]
        assert descomposicionesTriangulares(30) ==\
            [(1,1,28),(3,6,21),(10,10,10)]
        assert descomposicionesTriangulares(61) ==\
            [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
        assert descomposicionesTriangulares(52) ==\
            [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
        assert descomposicionesTriangulares(82) ==\
            [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
    print("Verificado")

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

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_descomposicionesTriangulares_equiv(n: int) -> None:
    r = descomposicionesTriangulares1(n)
    assert descomposicionesTriangulares2(n) == r
    assert descomposicionesTriangulares3(n) == r
    assert descomposicionesTriangulares4(n) == r

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

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

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

# La comparación es
#    >>> tiempo('descomposicionesTriangulares1(6*10**4)[-1]')
#    2.16 segundos
#    >>> tiempo('descomposicionesTriangulares2(6*10**4)[-1]')
#    2.05 segundos
#    >>> tiempo('descomposicionesTriangulares3(6*10**4)[-1]')
#    1.04 segundos
#    >>> tiempo('descomposicionesTriangulares4(6*10**4)[-1]')
#    0.10 segundos