Menu Close

Mes: noviembre 2022

Elementos consecutivos relacionados

José A. Alonso, ,

Definir la función

   relacionados :: (a -> a -> Bool) -> [a] -> Bool

tal que relacionados r xs se verifica si para todo par (x,y) de elementos consecutivos de xs se cumple la relación r. Por ejemplo,

   relacionados (<) [2,3,7,9] == True
   relacionados (<) [2,3,1,9] == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

-- 1ª solución
-- ===========
 
relacionados1 :: (a -> a -> Bool) -> [a] -> Bool
relacionados1 r xs = and [r x y | (x,y) <- zip xs (tail xs)]
 
-- 2ª solución
-- ===========
 
relacionados2 :: (a -> a -> Bool) -> [a] -> Bool
relacionados2 r (x:y:zs) = r x y && relacionados2 r (y:zs)
relacionados2 _ _        = True
 
-- 3ª solución
-- ===========
 
relacionados3 :: (a -> a -> Bool) -> [a] -> Bool
relacionados3 r xs = and (zipWith r xs (tail xs))
 
-- 4ª solución
-- ===========
 
relacionados4 :: (a -> a -> Bool) -> [a] -> Bool
relacionados4 r xs = all (uncurry r) (zip xs (tail xs))


Soluciones en Python

from typing import Callable, TypeVar
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def relacionados1(r: Callable[[A, A], bool], xs: list[A]) -> bool:
    return all((r(x, y) for (x, y) in zip(xs, xs[1:])))
 
# 2ª solución
# ===========
 
def relacionados2(r: Callable[[A, A], bool], xs: list[A]) -> bool:
    if len(xs) >= 2:
        return r(xs[0], xs[1]) and relacionados1(r, xs[1:])
    return True
Leer más →

Segmentos cuyos elementos cumplen una propiedad

José A. Alonso, ,

Definir la función

   segmentos :: (a -> Bool) -> [a] -> [[a]]

tal que segmentos p xs es la lista de los segmentos de xs cuyos elementos verifican la propiedad p. Por ejemplo,

   segmentos even [1,2,0,4,9,6,4,5,7,2]  ==  [[2,0,4],[6,4],[2]]
   segmentos odd  [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[9],[5,7]]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Data.List.Split (splitWhen)
import Test.QuickCheck.HigherOrder (quickCheck')
 
-- 1ª solución
-- ===========
 
segmentos1 :: (a -> Bool) -> [a] -> [[a]]
segmentos1 _ [] = []
segmentos1 p (x:xs)
  | p x       = takeWhile p (x:xs) : segmentos1 p (dropWhile p xs)
  | otherwise = segmentos1 p xs
 
-- 2ª solución
-- ===========
 
segmentos2 :: (a -> Bool) -> [a] -> [[a]]
segmentos2 p xs = filter (not .null) (splitWhen (not . p) xs)
 
-- 3ª solución
-- ===========
 
segmentos3 :: (a -> Bool) -> [a] -> [[a]]
segmentos3 = (filter (not . null) .) . splitWhen . (not .)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_segmentos :: (Int -> Bool) -> [Int] -> Bool
prop_segmentos p xs =
  all (== segmentos1 p xs)
      [segmentos2 p xs,
       segmentos3 p xs]
 
-- La comprobación es
--    λ> quickCheck' prop_segmentos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (segmentos1 even [1..5*10^6])
--    2500000
--    (2.52 secs, 2,080,591,088 bytes)
--    λ> length (segmentos2 even [1..5*10^6])
--    2500000
--    (0.78 secs, 2,860,591,688 bytes)
--    λ> length (segmentos3 even [1..5*10^6])
--    2500000
--    (0.82 secs, 2,860,592,000 bytes)


Soluciones en Python

from itertools import dropwhile, takewhile
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Callable, TypeVar
 
from more_itertools import split_at
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def segmentos1(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:
    if not xs:
        return []
    if p(xs[0]):
        return [list(takewhile(p, xs))] + \
            segmentos1(p, list(dropwhile(p, xs[1:])))
    return segmentos1(p, xs[1:])
 
# 2ª solución
# ===========
 
def segmentos2(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:
    return list(filter((lambda x: x), split_at(xs, lambda x: not p(x))))
 
# 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('segmentos1(lambda x: x % 2 == 0, range(10**4))')
#    0.55 segundos
#    >>> tiempo('segmentos2(lambda x: x % 2 == 0, range(10**4))')
#    0.00 segundos
Leer más →

Reconocimiento de subcadenas

José A. Alonso, ,

Definir, por recursión, la función

   esSubcadena :: String -> String -> Bool

tal que esSubcadena xs ys se verifica si xs es una subcadena de ys. Por ejemplo,

   esSubcadena "casa" "escasamente"   ==  True
   esSubcadena "cante" "escasamente"  ==  False
   esSubcadena "" ""                  ==  True

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

-- 1ª solución
-- ===========
 
esSubcadena1 :: String -> String -> Bool
esSubcadena1 [] _      = True
esSubcadena1  _ []     = False
esSubcadena1 xs (y:ys) = xs `isPrefixOf` (y:ys) || xs `esSubcadena1` ys
 
-- 2ª solución
-- ===========
 
esSubcadena2 :: String -> String -> Bool
esSubcadena2 xs ys =
  or [xs `isPrefixOf` zs | zs <- sufijos ys]
 
-- (sufijos xs) es la lista de sufijos de xs. Por ejemplo,
--    sufijos "abc"  ==  ["abc","bc","c",""]
sufijos :: String -> [String]
sufijos xs = [drop i xs | i <- [0..length xs]]
 
-- 3ª solución
-- ===========
 
esSubcadena3 :: String -> String -> Bool
esSubcadena3 xs ys =
  or [xs `isPrefixOf` zs | zs <- tails ys]
 
-- 4ª solución
-- ===========
 
esSubcadena4 :: String -> String -> Bool
esSubcadena4 xs ys =
  any (xs `isPrefixOf`) (tails ys)
 
-- 5ª solución
-- ===========
 
esSubcadena5 :: String -> String -> Bool
esSubcadena5 = (. tails) . any . isPrefixOf
 
-- 6ª solución
-- ===========
 
esSubcadena6 :: String -> String -> Bool
esSubcadena6 = isInfixOf
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_esSubcadena :: String -> String -> Bool
prop_esSubcadena xs ys =
  all (== esSubcadena1 xs ys)
      [esSubcadena2 xs ys,
       esSubcadena3 xs ys,
       esSubcadena4 xs ys,
       esSubcadena5 xs ys,
       esSubcadena6 xs ys]
 
-- La comprobación es
--    λ> quickCheck prop_esSubcadena
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> esSubcadena1 "abc" (replicate (5*10^4) 'd' ++ "abc")
--    True
--    (0.03 secs, 17,789,392 bytes)
--    λ> esSubcadena2 "abc" (replicate (5*10^4) 'd' ++ "abc")
--    True
--    (6.32 secs, 24,989,912 bytes)
--
--    λ> esSubcadena1 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (3.24 secs, 1,720,589,432 bytes)
--    λ> esSubcadena3 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (1.81 secs, 1,720,589,656 bytes)
--    λ> esSubcadena4 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (0.71 secs, 1,120,589,480 bytes)
--    λ> esSubcadena5 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (0.41 secs, 1,120,589,584 bytes)
--    λ> esSubcadena6 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (0.11 secs, 560,589,200 bytes)


Soluciones en Python

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 esSubcadena1(xs: str, ys: str) -> bool:
    if not xs:
        return True
    if not ys:
        return False
    return ys.startswith(xs) or esSubcadena1(xs, ys[1:])
 
# 2ª solución
# ===========
 
# sufijos(xs) es la lista de sufijos de xs. Por ejemplo,
#    sufijos("abc")  ==  ['abc', 'bc', 'c', '']
def sufijos(xs: str) -> list[str]:
    return [xs[i:] for i in range(len(xs) + 1)]
 
def esSubcadena2(xs: str, ys: str) -> bool:
    return any(zs.startswith(xs) for zs in sufijos(ys))
 
# 3ª solución
# ===========
 
def esSubcadena3(xs: str, ys: str) -> bool:
    return xs in ys
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.text(), st.text())
def test_esSubcadena(xs: str, ys: str) -> None:
    r = esSubcadena1(xs, ys)
    assert esSubcadena2(xs, ys) == r
    assert esSubcadena3(xs, ys) == r
 
# La comprobación es
#    src> poetry run pytest -q reconocimiento_de_subcadenas.py
#    1 passed in 0.35s
 
# 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('esSubcadena1("abc", "d"*(10**4) + "abc")')
#    0.02 segundos
#    >>> tiempo('esSubcadena2("abc", "d"*(10**4) + "abc")')
#    0.01 segundos
#    >>> tiempo('esSubcadena3("abc", "d"*(10**4) + "abc")')
#    0.00 segundos
#
#    >>> tiempo('esSubcadena2("abc", "d"*(10**5) + "abc")')
#    1.74 segundos
#    >>> tiempo('esSubcadena3("abc", "d"*(10**5) + "abc")')
#    0.00 segundos
Leer más →

Posiciones de un carácter en una cadena

José A. Alonso, ,

Definir la función

   posiciones :: Char -> String -> [Int]

tal que posiciones x ys es la lista de la posiciones del carácter x en la cadena ys. Por ejemplo,

   posiciones 'a' "Salamamca"   ==  [1,3,5,8]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Data.List (elemIndices)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
posiciones1 :: Char -> String -> [Int]
posiciones1 x ys = [n | (y,n) <- zip ys [0..], y == x]
 
-- 2ª solución
-- ===========
 
posiciones2 :: Char -> String -> [Int]
posiciones2 x ys = aux x ys 0
  where
    aux _ [] _ = []
    aux b (a:as) n | a == b    = n : aux b as (n+1)
                   | otherwise = aux b as (n+1)
 
-- 3ª solución
-- ===========
 
posiciones3 :: Char -> String -> [Int]
posiciones3 = elemIndices
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_posiciones :: Char -> String -> Bool
prop_posiciones x ys =
  all (== posiciones1 x ys)
      [posiciones2 x ys,
       posiciones3 x ys]
 
-- La comprobación es
--    λ> quickCheck prop_posiciones
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (posiciones1 'a' (take (6*10^6) (cycle "abc")))
--    2000000
--    (2.48 secs, 1,680,591,672 bytes)
--    λ> length (posiciones2 'a' (take (6*10^6) (cycle "abc")))
--    2000000
--    (2.98 secs, 1,584,591,720 bytes)
--    λ> length (posiciones3 'a' (take (6*10^6) (cycle "abc")))
--    2000000
--    (0.11 secs, 496,591,600 bytes)


Soluciones en Python

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 posiciones1(x: str, ys: str) -> list[int]:
    return [n for (n, y) in enumerate(ys) if y == x]
 
# -- 2ª solución
# -- ===========
 
def posiciones2(x: str, ys: str) -> list[int]:
    def aux(a: str, bs: str, n: int) -> list[int]:
        if bs:
            if a == bs[0]:
                return [n] + aux(a, bs[1:], n + 1)
            return aux(a, bs[1:], n + 1)
        return []
    return aux(x, ys, 0)
 
# -- 3ª solución
# -- ===========
 
def posiciones3(x: str, ys: str) -> list[int]:
    r = []
    for n, y in enumerate(ys):
        if x == y:
            r.append(n)
    return r
 
# La propiedad es
@given(st.text(), st.text())
def test_posiciones(x: str, ys: str) -> None:
    r = posiciones1(x, ys)
    assert posiciones2(x, ys) == r
    assert posiciones3(x, ys) == r
 
# La comprobación es
#    src> poetry run pytest -q posiciones_de_un_caracter_en_una_cadena.py
#    1 passed in 0.29s
 
# 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('posiciones1("a", "abc"*6000)')
#    0.00 segundos
#    >>> tiempo('posiciones2("a", "abc"*6000)')
#    0.06 segundos
#    >>> tiempo('posiciones3("a", "abc"*6000)')
#    0.00 segundos
#
#    >>> tiempo('posiciones1("a", "abc"*(2*10**7))')
#    3.02 segundos
#    >>> tiempo('posiciones3("a", "abc"*(2*10**7))')
#    3.47 segundos
Leer más →

Mayúsculas iniciales

José A. Alonso, ,

Se consideran las siguientes reglas de mayúsculas iniciales para los títulos:

  • la primera palabra comienza en mayúscula y
  • todas las palabras que tienen 4 letras como mínimo empiezan con mayúsculas

Definir la función

   titulo :: [String] -> [String]

tal que titulo ps es la lista de las palabras de ps con las reglas de mayúsculas iniciales de los títulos. Por ejemplo,

   λ> titulo ["eL","arTE","DE","La","proGraMacion"]
   ["El","Arte","de","la","Programacion"]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Data.Char (toUpper, toLower)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
titulo1 :: [String] -> [String]
titulo1 []     = []
titulo1 (p:ps) = mayusculaInicial p : [transforma q | q <- ps]
 
-- (mayusculaInicial xs) es la palabra xs con la letra inicial
-- en mayúscula y las restantes en minúsculas. Por ejemplo,
--    mayusculaInicial "sEviLLa"  ==  "Sevilla"
mayusculaInicial :: String -> String
mayusculaInicial []     = []
mayusculaInicial (x:xs) = toUpper x : [toLower y | y <- xs]
 
-- (transforma p) es la palabra p con mayúscula inicial si su longitud
-- es mayor o igual que 4 y es p en minúscula en caso contrario
transforma :: String -> String
transforma p | length p >= 4 = mayusculaInicial p
             | otherwise     = minuscula p
 
-- (minuscula xs) es la palabra xs en minúscula.
minuscula :: String -> String
minuscula xs = [toLower x | x <- xs]
 
-- 2ª solución
-- ===========
 
titulo2 :: [String] -> [String]
titulo2 []     = []
titulo2 (p:ps) = mayusculaInicial p : aux ps
  where aux []     = []
        aux (q:qs) = transforma q : aux qs
 
-- 3ª solución
-- ===========
 
titulo3 :: [String] -> [String]
titulo3 []     = []
titulo3 (p:ps) = mayusculaInicial p : map transforma ps
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_titulo :: [String] -> Bool
prop_titulo xs =
  all (== titulo1 xs)
      [titulo2 xs,
       titulo3 xs]
 
-- La comprobación es
--    λ> quickCheck prop_titulo
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (titulo1 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))
--    10000000
--    (2.17 secs, 1,680,592,512 bytes)
--    λ> length (titulo2 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))
--    10000000
--    (2.45 secs, 2,240,592,464 bytes)
--    λ> length (titulo3 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))
--    10000000
--    (0.16 secs, 1,440,592,464 bytes)


Soluciones en Python

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
# ===========
 
# (mayusculaInicial xs) es la palabra xs con la letra inicial
# en mayúscula y las restantes en minúsculas. Por ejemplo,
#    mayusculaInicial("sEviLLa")  ==  "Sevilla"
def mayusculaInicial(xs: str) -> str:
    return xs.capitalize()
 
# (minuscula xs) es la palabra xs en minúscula.
def minuscula(xs: str) -> str:
    return xs.lower()
 
# (transforma p) es la palabra p con mayúscula inicial si su longitud
# es mayor o igual que 4 y es p en minúscula en caso contrario
def transforma(p: str) -> str:
    if len(p) >= 4:
        return mayusculaInicial(p)
    return minuscula(p)
 
def titulo1(ps: list[str]) -> list[str]:
    if ps:
        return [mayusculaInicial(ps[0])] + [transforma(q) for q in ps[1:]]
    return []
 
# 2ª solución
# ===========
 
def titulo2(ps: list[str]) -> list[str]:
    def aux(qs: list[str]) -> list[str]:
        if qs:
            return [transforma(qs[0])] + aux(qs[1:])
        return []
    if ps:
        return [mayusculaInicial(ps[0])] + aux(ps[1:])
    return []
 
# 3ª solución
# ===========
 
def titulo3(ps: list[str]) -> list[str]:
    if ps:
        return [mayusculaInicial(ps[0])] + list(map(transforma, ps[1:]))
    return []
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.text()))
def test_titulo(ps: list[str]) -> None:
    r = titulo1(ps)
    assert titulo2(ps) == r
    assert titulo3(ps) == r
 
# La comprobación es
#    src> poetry run pytest -q mayusculas_iniciales.py
#    1 passed in 0.55s
 
# 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(mayusculaInicial1("aB"*(10**7)))')
#    >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion "]*1900)')
#    0.00 segundos
#    >>> tiempo('titulo2(["eL","arTE","DE","La","proGraMacion "]*1900)')
#    0.30 segundos
#    >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion "]*1900)')
#    0.00 segundos
#
#    >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion "]*(2*10**6))')
#    2.93 segundos
#    >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion "]*(2*10**6))')
#    2.35 segundos
Leer más →