{"id":7844,"date":"2022-11-19T10:35:26","date_gmt":"2022-11-19T09:35:26","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7844"},"modified":"2022-11-19T10:37:03","modified_gmt":"2022-11-19T09:37:03","slug":"19-nov-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/19-nov-22\/","title":{"rendered":"PFH: La semana en Exercitium (18 de noviembre de 2022)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Reconocimiento de subcadenas<\/a><\/li>\n<li><a href=\"#ej2\">2. Segmentos cuyos elementos cumplen una propiedad<\/a><\/li>\n<li><a href=\"#ej3\">3. Elementos consecutivos relacionados<\/a><\/li>\n<li><a href=\"#ej4\">4. Agrupaci\u00f3n de elementos por posici\u00f3n<\/a><\/li>\n<li><a href=\"#ej5\">5. Concatenaci\u00f3n de una lista de listas<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Reconocimiento de subcadenas<\/h3>\n<p>Definir, por recursi\u00f3n, la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   esSubcadena :: String -> String -> Bool\n<\/pre>\n<p>tal que <code>esSubcadena xs ys<\/code> se verifica si <code>xs<\/code> es una subcadena de <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   esSubcadena \"casa\" \"escasamente\"   ==  True\n   esSubcadena \"cante\" \"escasamente\"  ==  False\n   esSubcadena \"\" \"\"                  ==  True\n<\/pre>\n<p><b>1.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena1 :: String -> String -> Bool\nesSubcadena1 [] _      = True\nesSubcadena1  _ []     = False\nesSubcadena1 xs (y:ys) = xs `isPrefixOf` (y:ys) || xs `esSubcadena1` ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena2 :: String -> String -> Bool\nesSubcadena2 xs ys =\n  or [xs `isPrefixOf` zs | zs <- sufijos ys]\n\n-- (sufijos xs) es la lista de sufijos de xs. Por ejemplo,\n--    sufijos \"abc\"  ==  [\"abc\",\"bc\",\"c\",\"<\/b>\nsufijos :: String -> [String]\nsufijos xs = [drop i xs | i <- [0..length xs]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena3 :: String -> String -> Bool\nesSubcadena3 xs ys =\n  or [xs `isPrefixOf` zs | zs <- tails ys]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena4 :: String -> String -> Bool\nesSubcadena4 xs ys =\n  any (xs `isPrefixOf`) (tails ys)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena5 :: String -> String -> Bool\nesSubcadena5 = (. tails) . any . isPrefixOf\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena6 :: String -> String -> Bool\nesSubcadena6 = isInfixOf\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_esSubcadena :: String -> String -> Bool\nprop_esSubcadena xs ys =\n  all (== esSubcadena1 xs ys)\n      [esSubcadena2 xs ys,\n       esSubcadena3 xs ys,\n       esSubcadena4 xs ys,\n       esSubcadena5 xs ys,\n       esSubcadena6 xs ys]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_esSubcadena\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> esSubcadena1 \"abc\" (replicate (5*10^4) 'd' ++ \"abc\")\n--    True\n--    (0.03 secs, 17,789,392 bytes)\n--    \u03bb> esSubcadena2 \"abc\" (replicate (5*10^4) 'd' ++ \"abc\")\n--    True\n--    (6.32 secs, 24,989,912 bytes)\n--\n--    \u03bb> esSubcadena1 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (3.24 secs, 1,720,589,432 bytes)\n--    \u03bb> esSubcadena3 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (1.81 secs, 1,720,589,656 bytes)\n--    \u03bb> esSubcadena4 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (0.71 secs, 1,120,589,480 bytes)\n--    \u03bb> esSubcadena5 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (0.41 secs, 1,120,589,584 bytes)\n--    \u03bb> esSubcadena6 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (0.11 secs, 560,589,200 bytes)\n<\/pre>\n<p><b>1.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef esSubcadena1(xs: str, ys: str) -> bool:\n    if not xs:\n        return True\n    if not ys:\n        return False\n    return ys.startswith(xs) or esSubcadena1(xs, ys[1:])\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# sufijos(xs) es la lista de sufijos de xs. Por ejemplo,\n#    sufijos(\"abc\")  ==  ['abc', 'bc', 'c', '']\ndef sufijos(xs: str) -> list[str]:\n    return [xs[i:] for i in range(len(xs) + 1)]\n\ndef esSubcadena2(xs: str, ys: str) -> bool:\n    return any(zs.startswith(xs) for zs in sufijos(ys))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef esSubcadena3(xs: str, ys: str) -> bool:\n    return xs in ys\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.text(), st.text())\ndef test_esSubcadena(xs: str, ys: str) -> None:\n    r = esSubcadena1(xs, ys)\n    assert esSubcadena2(xs, ys) == r\n    assert esSubcadena3(xs, ys) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q reconocimiento_de_subcadenas.py\n#    1 passed in 0.35s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('esSubcadena1(\"abc\", \"d\"*(10**4) + \"abc\")')\n#    0.02 segundos\n#    >>> tiempo('esSubcadena2(\"abc\", \"d\"*(10**4) + \"abc\")')\n#    0.01 segundos\n#    >>> tiempo('esSubcadena3(\"abc\", \"d\"*(10**4) + \"abc\")')\n#    0.00 segundos\n#\n#    >>> tiempo('esSubcadena2(\"abc\", \"d\"*(10**5) + \"abc\")')\n#    1.74 segundos\n#    >>> tiempo('esSubcadena3(\"abc\", \"d\"*(10**5) + \"abc\")')\n#    0.00 segundos\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Segmentos cuyos elementos cumplen una propiedad<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   segmentos :: (a -> Bool) -> [a] -> [[a]]\n<\/pre>\n<p>tal que <code>segmentos p xs<\/code> es la lista de los segmentos de <code>xs<\/code> cuyos elementos verifican la propiedad <code>p<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   segmentos even [1,2,0,4,9,6,4,5,7,2]  ==  [[2,0,4],[6,4],[2]]\n   segmentos odd  [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[9],[5,7]]\n<\/pre>\n<p><b>2.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Data.List.Split (splitWhen)\nimport Test.QuickCheck.HigherOrder (quickCheck')\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsegmentos1 :: (a -> Bool) -> [a] -> [[a]]\nsegmentos1 _ [] = []\nsegmentos1 p (x:xs)\n  | p x       = takeWhile p (x:xs) : segmentos1 p (dropWhile p xs)\n  | otherwise = segmentos1 p xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsegmentos2 :: (a -> Bool) -> [a] -> [[a]]\nsegmentos2 p xs = filter (not .null) (splitWhen (not . p) xs)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsegmentos3 :: (a -> Bool) -> [a] -> [[a]]\nsegmentos3 = (filter (not . null) .) . splitWhen . (not .)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_segmentos :: (Int -> Bool) -> [Int] -> Bool\nprop_segmentos p xs =\n  all (== segmentos1 p xs)\n      [segmentos2 p xs,\n       segmentos3 p xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck' prop_segmentos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (segmentos1 even [1..5*10^6])\n--    2500000\n--    (2.52 secs, 2,080,591,088 bytes)\n--    \u03bb> length (segmentos2 even [1..5*10^6])\n--    2500000\n--    (0.78 secs, 2,860,591,688 bytes)\n--    \u03bb> length (segmentos3 even [1..5*10^6])\n--    2500000\n--    (0.82 secs, 2,860,592,000 bytes)\n<\/pre>\n<p><b>2.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import dropwhile, takewhile\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Callable, TypeVar\n\nfrom more_itertools import split_at\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef segmentos1(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:\n    if not xs:\n        return []\n    if p(xs[0]):\n        return [list(takewhile(p, xs))] + \\\n            segmentos1(p, list(dropwhile(p, xs[1:])))\n    return segmentos1(p, xs[1:])\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef segmentos2(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:\n    return list(filter((lambda x: x), split_at(xs, lambda x: not p(x))))\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('segmentos1(lambda x: x % 2 == 0, range(10**4))')\n#    0.55 segundos\n#    >>> tiempo('segmentos2(lambda x: x % 2 == 0, range(10**4))')\n#    0.00 segundos\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Elementos consecutivos relacionados<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   relacionados :: (a -> a -> Bool) -> [a] -> Bool\n<\/pre>\n<p>tal que <code>relacionados r xs<\/code> se verifica si para todo par <code>(x,y)<\/code> de elementos consecutivos de <code>xs<\/code> se cumple la relaci\u00f3n <code>r<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   relacionados (<) [2,3,7,9] == True\n   relacionados (<) [2,3,1,9] == False\n<\/pre>\n<p><b>3.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nrelacionados1 :: (a -> a -> Bool) -> [a] -> Bool\nrelacionados1 r xs = and [r x y | (x,y) <- zip xs (tail xs)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nrelacionados2 :: (a -> a -> Bool) -> [a] -> Bool\nrelacionados2 r (x:y:zs) = r x y && relacionados2 r (y:zs)\nrelacionados2 _ _        = True\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nrelacionados3 :: (a -> a -> Bool) -> [a] -> Bool\nrelacionados3 r xs = and (zipWith r xs (tail xs))\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nrelacionados4 :: (a -> a -> Bool) -> [a] -> Bool\nrelacionados4 r xs = all (uncurry r) (zip xs (tail xs))\n<\/pre>\n<p><b>3.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Callable, TypeVar\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef relacionados1(r: Callable[[A, A], bool], xs: list[A]) -> bool:\n    return all((r(x, y) for (x, y) in zip(xs, xs[1:])))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef relacionados2(r: Callable[[A, A], bool], xs: list[A]) -> bool:\n    if len(xs) >= 2:\n        return r(xs[0], xs[1]) and relacionados1(r, xs[1:])\n    return True\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Agrupaci\u00f3n de elementos por posici\u00f3n<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   agrupa :: Eq a => [[a]] -> [[a]]\n<\/pre>\n<p>tal que <code>agrupa xss<\/code>es la lista de las listas obtenidas agrupando los primeros elementos, los segundos, ... Por ejemplo,<\/p>\n<pre lang=\"text\">\n   agrupa [[1..6],[7..9],[10..20]]  ==  [[1,7,10],[2,8,11],[3,9,12]]\n<\/pre>\n<p>Comprobar con QuickChek que la longitud de todos los elementos de <code>agrupa xs<\/code> es igual a la longitud de <code>xs<\/code>.<\/p>\n<p><b>4.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Data.List (transpose)\nimport qualified Data.Matrix as M (fromLists, toLists, transpose)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\n-- (primeros xss) es la lista de los primeros elementos de xss. Por\n-- ejemplo,\n--    primeros [[1..6],[7..9],[10..20]]  ==  [1,7,10]\nprimeros :: [[a]] -> [a]\nprimeros = map head\n\n-- (restos xss) es la lista de los restos de elementos de xss. Por\n-- ejemplo,\n--    restos [[1..3],[7,8],[4..7]]  ==  [[2,3],[8],[5,6,7]]\nrestos :: [[a]] -> [[a]]\nrestos = map tail\n\nagrupa1 :: Eq a => [[a]] -> [[a]]\nagrupa1 []  = []\nagrupa1 xss\n  | [] `elem` xss = []\n  | otherwise     = primeros xss : agrupa1 (restos xss)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- (conIgualLongitud xss) es la lista obtenida recortando los elementos\n-- de xss para que todos tengan la misma longitud. Por ejemplo,\n--    > conIgualLongitud [[1..6],[7..9],[10..20]]\n--    [[1,2,3],[7,8,9],[10,11,12]]\nconIgualLongitud :: [[a]] -> [[a]]\nconIgualLongitud xss = map (take n) xss\n  where n = minimum (map length xss)\n\nagrupa2 :: Eq a => [[a]] -> [[a]]\nagrupa2 = transpose . conIgualLongitud\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nagrupa3 :: Eq a => [[a]] -> [[a]]\nagrupa3 = M.toLists . M.transpose . M.fromLists . conIgualLongitud\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_agrupa :: NonEmptyList [Int] -> Bool\nprop_agrupa (NonEmpty xss) =\n  all (== agrupa1 xss)\n      [agrupa2 xss,\n       agrupa3 xss]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (agrupa1 [[1..10^4] | _ <- [1..10^4]])\n--    10000\n--    (3.96 secs, 16,012,109,904 bytes)\n--    \u03bb> length (agrupa2 [[1..10^4] | _ <- [1..10^4]])\n--    10000\n--    (25.80 secs, 19,906,197,528 bytes)\n--    \u03bb> length (agrupa3 [[1..10^4] | _ <- [1..10^4]])\n--    10000\n--    (9.56 secs, 7,213,797,984 bytes)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_agrupa\n--    +++ OK, passed 100 tests.\n\n-- La propiedad es\nprop_agrupa_length :: [[Int]] -> Bool\nprop_agrupa_length xss =\n  and [length xs == n | xs <- agrupa1 xss]\n  where n = length xss\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_agrupa_length\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><b>4.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom numpy import transpose, array\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# primeros(xss) es la lista de los primeros elementos de xss. Por\n# ejemplo,\n#    primeros([[1,6],[7,8,9],[3,4,5]])  ==  [1, 7, 3]\ndef primeros(xss: list[list[A]]) -> list[A]:\n    return [xs[0] for xs in xss]\n\n# restos(xss) es la lista de los restos de elementos de xss. Por\n# ejemplo,\n#    >>> restos([[1,6],[7,8,9],[3,4,5]])\n#    [[6], [8, 9], [4, 5]]\ndef restos(xss: list[list[A]]) -> list[list[A]]:\n    return [xs[1:] for xs in xss]\n\ndef agrupa1(xss: list[list[A]]) -> list[list[A]]:\n    if not xss:\n        return []\n    if [] in xss:\n        return []\n    return [primeros(xss)] + agrupa1(restos(xss))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# conIgualLongitud(xss) es la lista obtenida recortando los elementos\n# de xss para que todos tengan la misma longitud. Por ejemplo,\n#    >>> conIgualLongitud([[1,6],[7,8,9],[3,4,5]])\n#    [[1, 6], [7, 8], [3, 4]]\ndef conIgualLongitud(xss: list[list[A]]) -> list[list[A]]:\n    n = min(map(len, xss))\n    return [xs[:n] for xs in xss]\n\ndef agrupa2(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    return [[ys[i] for ys in yss] for i in range(len(yss[0]))]\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef agrupa3(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    return list(map(list, zip(*yss)))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef agrupa4(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    return (transpose(array(yss))).tolist()\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef agrupa5(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    r = []\n    for i in range(len(yss[0])):\n        f = []\n        for xs in xss:\n            f.append(xs[i])\n        r.append(f)\n    return r\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_agrupa(xss: list[list[int]]) -> None:\n    r = agrupa1(xss)\n    assert agrupa2(xss) == r\n    assert agrupa3(xss) == r\n    assert agrupa4(xss) == r\n    assert agrupa5(xss) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py\n#    1 passed in 0.74s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('agrupa1([list(range(10**3)) for _ in range(10**3)])')\n#    4.44 segundos\n#    >>> tiempo('agrupa2([list(range(10**3)) for _ in range(10**3)])')\n#    0.10 segundos\n#    >>> tiempo('agrupa3([list(range(10**3)) for _ in range(10**3)])')\n#    0.10 segundos\n#    >>> tiempo('agrupa4([list(range(10**3)) for _ in range(10**3)])')\n#    0.12 segundos\n#    >>> tiempo('agrupa5([list(range(10**3)) for _ in range(10**3)])')\n#    0.15 segundos\n#\n#    >>> tiempo('agrupa2([list(range(10**4)) for _ in range(10**4)])')\n#    21.25 segundos\n#    >>> tiempo('agrupa3([list(range(10**4)) for _ in range(10**4)])')\n#    20.82 segundos\n#    >>> tiempo('agrupa4([list(range(10**4)) for _ in range(10**4)])')\n#    13.46 segundos\n#    >>> tiempo('agrupa5([list(range(10**4)) for _ in range(10**4)])')\n#    21.70 segundos\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_agrupa_length(xss: list[list[int]]) -> None:\n    n = len(xss)\n    assert all((len(xs) == n for xs in agrupa2(xss)))\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py\n#    2 passed in 1.25s\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Concatenaci\u00f3n de una lista de listas<\/h3>\n<p>Definir, por recursi\u00f3n, la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   conc :: [[a]] -> [a]\n<\/pre>\n<p>tal que <code>conc xss<\/code> es la concenaci\u00f3n de las listas de <code>xss<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   conc [[1,3],[2,4,6],[1,9]]  ==  [1,3,2,4,6,1,9]\n<\/pre>\n<p>Comprobar con QuickCheck que la longitud de <code>conc xss<\/code> es la suma de las longitudes de los elementos de <code>xss<\/code>.<\/p>\n<p><b>5.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nconc1 :: [[a]] -> [a]\nconc1 xss = [x | xs <- xss, x <- xs]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nconc2 :: [[a]] -> [a]\nconc2 []       = []\nconc2 (xs:xss) = xs ++ conc2 xss\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nconc3 :: [[a]] -> [a]\nconc3 = foldr (++) []\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nconc4 :: [[a]] -> [a]\nconc4 = concat\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_conc :: [[Int]] -> Bool\nprop_conc xss =\n  all (== conc1 xss)\n      [conc2 xss,\n       conc3 xss,\n       conc4 xss]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_conc\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (conc1 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (2.72 secs, 1,802,391,200 bytes)\n--    \u03bb> length (conc2 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (0.27 secs, 1,602,351,160 bytes)\n--    \u03bb> length (conc3 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (0.28 secs, 1,602,071,192 bytes)\n--    \u03bb> length (conc4 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (0.26 secs, 1,602,071,184 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_long_conc :: [[Int]] -> Bool\nprop_long_conc xss =\n  length (conc1 xss) == sum (map length xss)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_long_conc\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><b>5.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom functools import reduce\nfrom operator import concat\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Any, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef conc1(xss: list[list[A]]) -> list[A]:\n    return [x for xs in xss for x in xs]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef conc2(xss: list[list[A]]) -> list[A]:\n    if not xss:\n        return []\n    return xss[0] + conc2(xss[1:])\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef conc3(xss: Any) -> Any:\n    return reduce(concat, xss)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef conc4(xss: list[list[A]]) -> list[A]:\n    r = []\n    for xs in xss:\n        for x in xs:\n            r.append(x)\n    return r\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_conc(xss: list[list[int]]) -> None:\n    r = conc1(xss)\n    assert conc2(xss) == r\n    assert conc3(xss) == r\n    assert conc4(xss) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q contenacion_de_una_lista_de_listas.py\n#    1 passed in 0.63s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('conc1([list(range(n)) for n in range(1500)])')\n#    0.04 segundos\n#    >>> tiempo('conc2([list(range(n)) for n in range(1500)])')\n#    6.28 segundos\n#    >>> tiempo('conc3([list(range(n)) for n in range(1500)])')\n#    2.55 segundos\n#    >>> tiempo('conc4([list(range(n)) for n in range(1500)])')\n#    0.09 segundos\n#\n#    >>> tiempo('conc1([list(range(n)) for n in range(10000)])')\n#    2.01 segundos\n#    >>> tiempo('conc4([list(range(n)) for n in range(10000)])')\n#    2.90 segundos\n#\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_long_conc(xss: list[list[int]]) -> None:\n    assert len(conc1(xss)) == sum(map(len, xss))\n\n# prop_long_conc :: [[Int]] -> Bool\n# prop_long_conc xss =\n#   length (conc1 xss) == sum (map length xss)\n#\n# La comprobaci\u00f3n es\n#    \u03bb> quickCheck prop_long_conc\n#    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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\u00f3n de elementos por posici\u00f3n 5. Concatenaci\u00f3n de una lista de listas A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7844"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7844"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7844\/revisions"}],"predecessor-version":[{"id":7845,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7844\/revisions\/7845"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}