Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Reconocimiento de subcadenas
- 2. Segmentos cuyos elementos cumplen una propiedad
- 3. Elementos consecutivos relacionados
- 4. Agrupación de elementos por posición
- 5. Concatenación de una lista de listas
A continuación se muestran las soluciones.
1. Reconocimiento de subcadenas
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 |
1.1. 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","</b> 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) |
1.2. 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 |
2. Segmentos cuyos elementos cumplen una propiedad
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]] |
2.1. 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) |
2.2. 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 |
3. Elementos consecutivos relacionados
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 |
3.1. 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)) |
3.2. 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 |
4. Agrupación de elementos por posición
Definir la función
agrupa :: Eq a => [[a]] -> [[a]] |
tal que agrupa xsses la lista de las listas obtenidas agrupando los primeros elementos, los segundos, … Por ejemplo,
agrupa [[1..6],[7..9],[10..20]] == [[1,7,10],[2,8,11],[3,9,12]] |
Comprobar con QuickChek que la longitud de todos los elementos de agrupa xs es igual a la longitud de xs.
4.1. Soluciones en Haskell
import Data.List (transpose) import qualified Data.Matrix as M (fromLists, toLists, transpose) import Test.QuickCheck -- 1ª solución -- =========== -- (primeros xss) es la lista de los primeros elementos de xss. Por -- ejemplo, -- primeros [[1..6],[7..9],[10..20]] == [1,7,10] primeros :: [[a]] -> [a] primeros = map head -- (restos xss) es la lista de los restos de elementos de xss. Por -- ejemplo, -- restos [[1..3],[7,8],[4..7]] == [[2,3],[8],[5,6,7]] restos :: [[a]] -> [[a]] restos = map tail agrupa1 :: Eq a => [[a]] -> [[a]] agrupa1 [] = [] agrupa1 xss | [] `elem` xss = [] | otherwise = primeros xss : agrupa1 (restos xss) -- 2ª solución -- =========== -- (conIgualLongitud xss) es la lista obtenida recortando los elementos -- de xss para que todos tengan la misma longitud. Por ejemplo, -- > conIgualLongitud [[1..6],[7..9],[10..20]] -- [[1,2,3],[7,8,9],[10,11,12]] conIgualLongitud :: [[a]] -> [[a]] conIgualLongitud xss = map (take n) xss where n = minimum (map length xss) agrupa2 :: Eq a => [[a]] -> [[a]] agrupa2 = transpose . conIgualLongitud -- 3ª solución -- =========== agrupa3 :: Eq a => [[a]] -> [[a]] agrupa3 = M.toLists . M.transpose . M.fromLists . conIgualLongitud -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_agrupa :: NonEmptyList [Int] -> Bool prop_agrupa (NonEmpty xss) = all (== agrupa1 xss) [agrupa2 xss, agrupa3 xss] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (agrupa1 [[1..10^4] | _ <- [1..10^4]]) -- 10000 -- (3.96 secs, 16,012,109,904 bytes) -- λ> length (agrupa2 [[1..10^4] | _ <- [1..10^4]]) -- 10000 -- (25.80 secs, 19,906,197,528 bytes) -- λ> length (agrupa3 [[1..10^4] | _ <- [1..10^4]]) -- 10000 -- (9.56 secs, 7,213,797,984 bytes) -- La comprobación es -- λ> quickCheck prop_agrupa -- +++ OK, passed 100 tests. -- La propiedad es prop_agrupa_length :: [[Int]] -> Bool prop_agrupa_length xss = and [length xs == n | xs <- agrupa1 xss] where n = length xss -- La comprobación es -- λ> quickCheck prop_agrupa_length -- +++ OK, passed 100 tests. |
4.2. Soluciones en Python
from sys import setrecursionlimit from timeit import Timer, default_timer from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from numpy import transpose, array setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== # primeros(xss) es la lista de los primeros elementos de xss. Por # ejemplo, # primeros([[1,6],[7,8,9],[3,4,5]]) == [1, 7, 3] def primeros(xss: list[list[A]]) -> list[A]: return [xs[0] for xs in xss] # restos(xss) es la lista de los restos de elementos de xss. Por # ejemplo, # >>> restos([[1,6],[7,8,9],[3,4,5]]) # [[6], [8, 9], [4, 5]] def restos(xss: list[list[A]]) -> list[list[A]]: return [xs[1:] for xs in xss] def agrupa1(xss: list[list[A]]) -> list[list[A]]: if not xss: return [] if [] in xss: return [] return [primeros(xss)] + agrupa1(restos(xss)) # 2ª solución # =========== # conIgualLongitud(xss) es la lista obtenida recortando los elementos # de xss para que todos tengan la misma longitud. Por ejemplo, # >>> conIgualLongitud([[1,6],[7,8,9],[3,4,5]]) # [[1, 6], [7, 8], [3, 4]] def conIgualLongitud(xss: list[list[A]]) -> list[list[A]]: n = min(map(len, xss)) return [xs[:n] for xs in xss] def agrupa2(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) return [[ys[i] for ys in yss] for i in range(len(yss[0]))] # 3ª solución # =========== def agrupa3(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) return list(map(list, zip(*yss))) # 4ª solución # =========== def agrupa4(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) return (transpose(array(yss))).tolist() # 5ª solución # =========== def agrupa5(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) r = [] for i in range(len(yss[0])): f = [] for xs in xss: f.append(xs[i]) r.append(f) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_agrupa(xss: list[list[int]]) -> None: r = agrupa1(xss) assert agrupa2(xss) == r assert agrupa3(xss) == r assert agrupa4(xss) == r assert agrupa5(xss) == r # La comprobación es # src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py # 1 passed in 0.74s # 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('agrupa1([list(range(10**3)) for _ in range(10**3)])') # 4.44 segundos # >>> tiempo('agrupa2([list(range(10**3)) for _ in range(10**3)])') # 0.10 segundos # >>> tiempo('agrupa3([list(range(10**3)) for _ in range(10**3)])') # 0.10 segundos # >>> tiempo('agrupa4([list(range(10**3)) for _ in range(10**3)])') # 0.12 segundos # >>> tiempo('agrupa5([list(range(10**3)) for _ in range(10**3)])') # 0.15 segundos # # >>> tiempo('agrupa2([list(range(10**4)) for _ in range(10**4)])') # 21.25 segundos # >>> tiempo('agrupa3([list(range(10**4)) for _ in range(10**4)])') # 20.82 segundos # >>> tiempo('agrupa4([list(range(10**4)) for _ in range(10**4)])') # 13.46 segundos # >>> tiempo('agrupa5([list(range(10**4)) for _ in range(10**4)])') # 21.70 segundos # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_agrupa_length(xss: list[list[int]]) -> None: n = len(xss) assert all((len(xs) == n for xs in agrupa2(xss))) # La comprobación es # src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py # 2 passed in 1.25s |
5. Concatenación de una lista de listas
Definir, por recursión, la función
conc :: [[a]] -> [a] |
tal que conc xss es la concenación de las listas de xss. Por ejemplo,
conc [[1,3],[2,4,6],[1,9]] == [1,3,2,4,6,1,9] |
Comprobar con QuickCheck que la longitud de conc xss es la suma de las longitudes de los elementos de xss.
5.1. Soluciones en Haskell
-- 1ª solución -- =========== conc1 :: [[a]] -> [a] conc1 xss = [x | xs <- xss, x <- xs] -- 2ª solución -- =========== conc2 :: [[a]] -> [a] conc2 [] = [] conc2 (xs:xss) = xs ++ conc2 xss -- 3ª solución -- =========== conc3 :: [[a]] -> [a] conc3 = foldr (++) [] -- 4ª solución -- =========== conc4 :: [[a]] -> [a] conc4 = concat -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_conc :: [[Int]] -> Bool prop_conc xss = all (== conc1 xss) [conc2 xss, conc3 xss, conc4 xss] -- La comprobación es -- λ> quickCheck prop_conc -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (conc1 [[1..n] | n <- [1..5000]]) -- 12502500 -- (2.72 secs, 1,802,391,200 bytes) -- λ> length (conc2 [[1..n] | n <- [1..5000]]) -- 12502500 -- (0.27 secs, 1,602,351,160 bytes) -- λ> length (conc3 [[1..n] | n <- [1..5000]]) -- 12502500 -- (0.28 secs, 1,602,071,192 bytes) -- λ> length (conc4 [[1..n] | n <- [1..5000]]) -- 12502500 -- (0.26 secs, 1,602,071,184 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_long_conc :: [[Int]] -> Bool prop_long_conc xss = length (conc1 xss) == sum (map length xss) -- La comprobación es -- λ> quickCheck prop_long_conc -- +++ OK, passed 100 tests. |
5.2. Soluciones en Python
from functools import reduce from operator import concat from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Any, TypeVar from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def conc1(xss: list[list[A]]) -> list[A]: return [x for xs in xss for x in xs] # 2ª solución # =========== def conc2(xss: list[list[A]]) -> list[A]: if not xss: return [] return xss[0] + conc2(xss[1:]) # 3ª solución # =========== def conc3(xss: Any) -> Any: return reduce(concat, xss) # 4ª solución # =========== def conc4(xss: list[list[A]]) -> list[A]: r = [] for xs in xss: for x in xs: r.append(x) return r # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_conc(xss: list[list[int]]) -> None: r = conc1(xss) assert conc2(xss) == r assert conc3(xss) == r assert conc4(xss) == r # La comprobación es # src> poetry run pytest -q contenacion_de_una_lista_de_listas.py # 1 passed in 0.63s # 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('conc1([list(range(n)) for n in range(1500)])') # 0.04 segundos # >>> tiempo('conc2([list(range(n)) for n in range(1500)])') # 6.28 segundos # >>> tiempo('conc3([list(range(n)) for n in range(1500)])') # 2.55 segundos # >>> tiempo('conc4([list(range(n)) for n in range(1500)])') # 0.09 segundos # # >>> tiempo('conc1([list(range(n)) for n in range(10000)])') # 2.01 segundos # >>> tiempo('conc4([list(range(n)) for n in range(10000)])') # 2.90 segundos # # Comprobación de la propiedad # ============================ # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_long_conc(xss: list[list[int]]) -> None: assert len(conc1(xss)) == sum(map(len, xss)) # prop_long_conc :: [[Int]] -> Bool # prop_long_conc xss = # length (conc1 xss) == sum (map length xss) # # La comprobación es # λ> quickCheck prop_long_conc # +++ OK, passed 100 tests. |