menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a

   menorProductoEscalar [3,2,5]  [1,4,6]    == 29
   menorProductoEscalar [3,2,5]  [1,4,-6]   == -19
   menorProductoEscalar [1..10^2] [1..10^2] == 171700
   menorProductoEscalar [1..10^3] [1..10^3] == 167167000
   menorProductoEscalar [1..10^4] [1..10^4] == 166716670000
   menorProductoEscalar [1..10^5] [1..10^5] == 166671666700000
   menorProductoEscalar [1..10^6] [1..10^6] == 166667166667000000

import Data.List (permutations, sort, sortOn)
import Test.QuickCheck (quickCheck)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

menorProductoEscalar1 :: (Ord a, Num a) => [a] -> [a] -> a
menorProductoEscalar1 xs ys =
  minimum [sum (zipWith (*) pxs pys) | pxs <- permutations xs,
                                       pys <- permutations ys]

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

menorProductoEscalar2 :: (Ord a, Num a) => [a] -> [a] -> a
menorProductoEscalar2 xs ys =
  minimum [sum (zipWith (*) pxs ys) | pxs <- permutations xs]

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

menorProductoEscalar3 :: (Ord a, Num a) => [a] -> [a] -> a
menorProductoEscalar3 xs ys =
  sum (zipWith (*) (sort xs) (reverse (sort ys)))

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

verifica :: IO ()
verifica = hspec spec

specG :: ([Integer] -> [Integer] -> Integer) -> Spec
specG menorProductoEscalar = do
  it "e1" $
    menorProductoEscalar [3,2,5]  [1,4,6]  `shouldBe` 29
  it "e2" $
    menorProductoEscalar [3,2,5]  [1,4,-6] `shouldBe` -19

spec :: Spec
spec = do
  describe "def. 1" $ specG menorProductoEscalar1
  describe "def. 2" $ specG menorProductoEscalar2
  describe "def. 3" $ specG menorProductoEscalar3

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

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

-- La propiedad es
prop_menorProductoEscalar :: [Integer] -> [Integer] -> Bool
prop_menorProductoEscalar xs ys =
  all (== menorProductoEscalar1 xs' ys')
      [menorProductoEscalar2 xs' ys',
       menorProductoEscalar3 xs' ys']
  where n   = min (length xs) (length ys)
        xs' = take n xs
        ys' = take n ys

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

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

-- La comparación es
--    λ> menorProductoEscalar1 [0..5] [0..5]
--    20
--    (3.24 secs, 977385528 bytes)
--    λ> menorProductoEscalar2 [0..5] [0..5]
--    20
--    (0.01 secs, 4185776 bytes)
--
--    λ> menorProductoEscalar2 [0..9] [0..9]
--    120
--    (23.86 secs, 9342872784 bytes)
--    λ> menorProductoEscalar3 [0..9] [0..9]
--    120
--    (0.01 secs, 2580824 bytes)
--
--    λ> menorProductoEscalar3 [0..10^6] [0..10^6]
--    166666666666500000
--    (2.46 secs, 473,338,912 bytes)

from itertools import permutations
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

def menorProductoEscalar1(xs: list[int], ys: list[int]) -> int:
    return min(sum(x * y for x, y in zip(pxs, pys))
               for pxs in permutations(xs)
               for pys in permutations(ys))

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

def menorProductoEscalar2(xs: list[int], ys: list[int]) -> int:
    return min(sum(x * y for x, y in zip(pxs, ys))
               for pxs in permutations(xs))

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

def menorProductoEscalar3(xs: list[int], ys: list[int]) -> int:
    return sum(x * y for x, y in zip(sorted(xs),
                                     sorted(ys, reverse=True)))

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

def test_menorProductoEscalar() -> None:
    for menorProductoEscalar in [menorProductoEscalar1,
                                 menorProductoEscalar2,
                                 menorProductoEscalar3]:
        assert menorProductoEscalar([3,2,5], [1,4,6])  == 29
        assert menorProductoEscalar([3,2,5], [1,4,-6]) == -19
    print("Verificado")

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

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

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=1000), max_size = 6),
       st.lists(st.integers(min_value=1, max_value=1000)))
def test_menorProductoEscalar_equiv(xs: list[int], ys: list[int]) -> None:
    n = min(len(xs), len(ys))
    xs_ = xs[:n]
    ys_ = ys[:n]
    r = menorProductoEscalar1(xs_, ys_)
    assert menorProductoEscalar2(xs_, ys_) == r
    assert menorProductoEscalar3(xs_, ys_) == r

# La comprobación es
#    >>> test_menorProductoEscalar_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('menorProductoEscalar1(range(7), range(7))')
#    23.11 segundos
#    >>> tiempo('menorProductoEscalar2(range(7), range(7))')
#    0.01 segundos
#    >>> tiempo('menorProductoEscalar3(range(7), range(7))')
#    0.00 segundos
#
#    >>> tiempo('menorProductoEscalar2(range(10), range(10))')
#    3.93 segundos
#    >>> tiempo('menorProductoEscalar3(range(10), range(10))')
#    0.00 segundos