{"id":8029,"date":"2023-09-30T12:00:23","date_gmt":"2023-09-30T10:00:23","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=8029"},"modified":"2023-10-01T16:21:19","modified_gmt":"2023-10-01T14:21:19","slug":"30-sep-23-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/30-sep-23-2\/","title":{"rendered":"El mes de septiembre en Exercitium (Ejercicios con Haskell y Python)"},"content":{"rendered":"<p>Durante el mes de septiembre 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. Problema de suma cero (mediante espacio de estados)<\/a><\/li>\n<li><a href=\"#ej2\">2. Problema de las jarras (mediante espacios de estados)<\/a><\/li>\n<li><a href=\"#ej3\">3. La funci\u00f3n de Fibonacci por programaci\u00f3n din\u00e1mica<\/a><\/li>\n<li><a href=\"#ej4\">4. Coeficientes binomiales (con programaci\u00f3n din\u00e1mica)<\/a><\/li>\n<li><a href=\"#ej5\">5. Longitud de la subsecuencia com\u00fan m\u00e1xima (con programaci\u00f3n din\u00e1mica)<\/a><\/li>\n<li><a href=\"#ej6\">6. Subsecuencia com\u00fan m\u00e1xima (con programaci\u00f3n din\u00e1mica)<\/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. Problema de suma cero (mediante espacio de estados)<\/h3>\n<p>El problema de suma cero consiste en, dado el conjunto de  enteros, encontrar sus subconjuntos no vac\u00edo cuyos elementos sumen cero.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3NPI4qV\">procedimiento de b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   suma0 :: [Int] -> [[Int]]\n<\/pre>\n<p>tal que <code>suma0 ns<\/code> es la lista de las soluciones del problema de suma cero para <code>ns<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> suma0 [-7,-3,-2,5,8]\n   [[-3,-2,5]]\n   \u03bb> suma0 [-7,-3,-2,5,8,-1]\n   [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n   \u03bb> suma0 [-7,-3,1,5,8]\n   []\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Problema_de_suma_cero where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.List (delete, nub, sort)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Los estados son ternas formadas por los n\u00fameros seleccionados, su\n-- suma y los restantes n\u00fameros.\ntype Estado = ([Int], Int, [Int])\n\ninicial :: [Int] -> Estado\ninicial ns = ([],0,ns)\n\nesFinal :: Estado -> Bool\nesFinal (xs,s,_) =\n  not (null xs) && s == 0\n\nsucesores :: Estado -> [Estado]\nsucesores (xs,s,ns) =\n  [(n:xs, n+s, delete n ns) | n <- ns]\n\nsoluciones :: [Int] -> [Estado]\nsoluciones ns =\n  buscaProfundidad sucesores esFinal (inicial ns)\n\nsuma0 :: [Int] -> [[Int]]\nsuma0 ns =\n  nub [sort xs | (xs,_,_) <- soluciones ns]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    suma0 [-7,-3,-2,5,8] `shouldBe`\n    [[-3,-2,5]]\n  it \"e2\" $\n    suma0 [-7,-3,-2,5,8,-1] `shouldBe`\n    [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n  it \"e3\" $\n    suma0 [-7,-3,1,5,8] `shouldBe`\n    []\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0098 seconds\n--    3 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\n# Los estados son ternas formadas por los n\u00fameros seleccionados, su\n# suma y los restantes n\u00fameros.\nEstado = tuple[list[int], int, list[int]]\n\ndef inicial(ns: list[int]) -> Estado:\n    return ([], 0, ns)\n\ndef esFinal(e: Estado) -> bool:\n    (xs,s,_) = e\n    return xs != [] and s == 0\n\ndef sucesores(e: Estado) -> list[Estado]:\n    (xs, s, ns) = e\n    return [([n] + xs, n + s, [m for m in ns if m !=n])\n            for n in ns]\n\ndef soluciones(ns: list[int]) -> list[Estado]:\n    return buscaProfundidad(sucesores, esFinal, inicial(ns))\n\ndef suma0(ns: list[int]) -> list[list[int]]:\n    xss = [list(sorted(s[0])) for s in soluciones(ns)]\n    r = []\n    for xs in xss:\n        if xs not in r:\n            r.append(xs)\n    return r\n\n# Verificaci\u00f3n\n# ============\n\ndef test_suma0() -> None:\n    assert suma0([-7,-3,-2,5,8]) == \\\n        [[-3,-2,5]]\n    assert suma0([-7,-3,-2,5,8,-1]) == \\\n        [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n    assert not suma0([-7,-3,1,5,8])\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_suma0()\n#    Verificado\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Problema de las jarras (mediante espacios de estados)<\/h3>\n<p>En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medici\u00f3n, una de A litros de capacidad y otra de B. Tambi\u00e9n se dispone de una bomba que permite llenar las jarras de agua.<\/p>\n<p>El problema de las jarras (A,B,C) consiste en determinar c\u00f3mo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3XBlqG7\">procedimiento de b\u00fasqueda en anchura<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   jarras :: (Int,Int,Int) -> [[(Int,Int)]]\n<\/pre>\n<p>tal <code>jarras (a,b,c)<\/code> es la lista de las soluciones del problema de las jarras <code>(a,b,c)<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 3 (jarras (4,3,2))\n   [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],\n    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],\n    [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]\n<\/pre>\n<p>La interpretaci\u00f3n [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:<\/p>\n<ul>\n<li>(0,0) se inicia con las dos jarras vac\u00edas,<\/li>\n<li>(4,0) se llena la jarra de 4 con el grifo,<\/li>\n<li>(1,3) se llena la de 3 con la de 4,<\/li>\n<li>(1,0) se vac\u00eda la de 3,<\/li>\n<li>(0,1) se pasa el contenido de la primera a la segunda,<\/li>\n<li>(4,1) se llena la primera con el grifo,<\/li>\n<li>(2,3) se llena la segunda con la primera.<\/li>\n<\/ul>\n<p>Otros ejemplos<\/p>\n<pre lang=\"text\">\n   \u03bb> length (jarras (15,10,5))\n   8\n   \u03bb> map length (jarras (15,10,5))\n   [3,5,5,7,7,7,8,9]\n   \u03bb> jarras (15,10,4)\n   []\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Problema_de_las_jarras where\n\nimport BusquedaEnAnchura (buscaAnchura)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Un problema es una lista de 3 n\u00fameros enteros (a,b,c) tales que a es\n-- la capacidad de la primera jarra, b es la capacidad de la segunda\n-- jarra y c es el n\u00famero de litros que se desea obtener en la primera\n-- jarra.\ntype Problema = (Int,Int,Int)\n\n-- Una configuracion es una lista de dos n\u00fameros. El primero es el\n-- contenido de la primera jarra y el segundo el de la segunda.\ntype Configuracion = (Int,Int)\n\n-- Inicialmente, las dos jarras est\u00e1n vac\u00edas.\nconfiguracionInicial :: Configuracion\nconfiguracionInicial = (0,0)\n\n-- (esConfiguracionFinal p e) se verifica si e es un configuracion final\n-- del problema p.\nesConfiguracionFinal :: Problema -> Configuracion -> Bool\nesConfiguracionFinal (_,_,c) (x,_) = x == c\n\n-- (sucesorasConfiguracion p c) son las sucesoras de la configuraci\u00f3n c\n-- del problema p. Por ejemplo,\n--    sucesorasConfiguracion (4,3,2) (0,0)  ==  [(4,0),(0,3)]\n--    sucesorasConfiguracion (4,3,2) (4,0)  ==  [(4,3),(0,0),(1,3)]\n--    sucesorasConfiguracion (4,3,2) (4,3)  ==  [(0,3),(4,0)]\nsucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion]\nsucesorasConfiguracion (a,b,_) (x,y) =\n    [(a,y) | x < a] ++\n    [(x,b) | y < b] ++\n    [(0,y) | x > 0] ++\n    [(x,0) | y > 0] ++\n    [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++\n    [(x-(b-y),b) | x > 0, y < b, x + y > b] ++\n    [(x+y,0) | y > 0, x + y <= a] ++\n    [(0,x+y) | x > 0, x + y <= b]\n\n-- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que\n-- c_1 es la configuraci\u00f3n inicial y, para 2 <= i <= n, c_i es una\n-- sucesora de c_(i-1).\ntype Estado = [Configuracion]\n\n-- inicial es el estado cuyo \u00fanico elemento es la configuraci\u00f3n\n-- inicial.\ninicial :: Estado\ninicial = [configuracionInicial]\n\n-- (esFinal p e) se verifica si e es un estado final; es decir, su\n-- primer elemento es una configuraci\u00f3n final.\nesFinal :: Problema -> Estado -> Bool\nesFinal p (e:_) = esConfiguracionFinal p e\n\n-- (sucesores p e) es la lista de los sucesores del estado e en el\n-- problema p. Por ejemplo,\n--    \u03bb> sucesores (4,3,2) [(0,0)]\n--    [[(4,0),(0,0)],[(0,3),(0,0)]]\n--    \u03bb> sucesores (4,3,2) [(4,0),(0,0)]\n--    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]\n--    \u03bb> sucesores (4,3,2) [(4,3),(4,0),(0,0)]\n--    [[(0,3),(4,3),(4,0),(0,0)]]\nsucesores :: Problema -> Estado -> [Estado]\nsucesores p e@(c:_) =\n    [c':e | c' <- sucesorasConfiguracion p c,\n            c' `notElem` e]\n\njarras :: Problema -> [Estado]\njarras p = map reverse soluciones\n  where\n     soluciones = buscaAnchura (sucesores p) (esFinal p) inicial\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    take 3 (jarras (4,3,2)) `shouldBe`\n    [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],\n     [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],\n     [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]\n  it \"e2\" $\n    length (jarras (15,10,5)) `shouldBe` 8\n  it \"e3\" $\n    map length (jarras (15,10,5)) `shouldBe`\n    [3,5,5,7,7,7,8,9]\n  it \"e4\" $\n    jarras (15,10,4) `shouldBe` []\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0080 seconds\n--    4 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.BusquedaEnAnchura import buscaAnchura\n\n# Un problema es una lista de 3 n\u00fameros enteros (a,b,c) tales que a es\n# la capacidad de la primera jarra, b es la capacidad de la segunda\n# jarra y c es el n\u00famero de litros que se desea obtener en la primera\n# jarra.\nProblema = tuple[int, int, int]\n\n# Una configuracion es una lista de dos n\u00fameros. El primero es el\n# contenido de la primera jarra y el segundo el de la segunda.\nConfiguracion = tuple[int, int]\n\n# Inicialmente, las dos jarras est\u00e1n vac\u00edas.\nconfiguracionInicial: Configuracion = (0,0)\n\n# esConfiguracionFinal(p, e) se verifica si e es un configuracion final\n# del problema p.\ndef esConfiguracionFinal(p: Problema, c: Configuracion) -> bool:\n    return p[2] == c[0]\n\n# sucesorasConfiguracion(p, c) son las sucesoras de la configuraci\u00f3n c\n# del problema p. Por ejemplo,\n#    sucesorasConfiguracion((4,3,2), (0,0))  ==  [(4,0),(0,3)]\n#    sucesorasConfiguracion((4,3,2), (4,0))  ==  [(4,3),(0,0),(1,3)]\n#    sucesorasConfiguracion((4,3,2), (4,3))  ==  [(0,3),(4,0)]\ndef sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]:\n    (a, b, _) = p\n    (x, y) = c\n    r = []\n    if x < a:\n        r.append((a, y))\n    if y < b:\n        r.append((x, b))\n    if x > 0:\n        r.append((0, y))\n    if y > 0:\n        r.append((x, 0))\n    if x < a and y > 0 and x + y > a:\n        r.append((a, y - (a - x)))\n    if x > 0 and y < b and x + y > b:\n        r.append((x - (b - y), b))\n    if y > 0 and x + y <= a:\n        r.append((x + y, 0))\n    if x > 0 and x + y <= b:\n        r.append((0, x + y))\n    return r\n\n# Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que\n# c_1 es la configuraci\u00f3n inicial y, para 2 <= i <= n, c_i es una\n# sucesora de c_(i-1).\nEstado = list[Configuracion]\n\n# inicial es el estado cuyo \u00fanico elemento es la configuraci\u00f3n\n# inicial.\ninicial: Estado = [configuracionInicial]\n\n# esFinal(p, e) se verifica si e es un estado final; es decir, su\n# primer elemento es una configuraci\u00f3n final.\ndef esFinal(p: Problema, e: Estado) -> bool:\n    return esConfiguracionFinal(p, e[0])\n\n# sucesores(p, e) es la lista de los sucesores del estado e en el\n# problema p. Por ejemplo,\n#    \u03bb> sucesores((4,3,2), [(0,0)])\n#    [[(4,0),(0,0)],[(0,3),(0,0)]]\n#    \u03bb> sucesores((4,3,2), [(4,0),(0,0)])\n#    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]\n#    \u03bb> sucesores((4,3,2), [(4,3),(4,0),(0,0)])\n#    [[(0,3),(4,3),(4,0),(0,0)]]\ndef sucesores(p: Problema, e: Estado) -> list[Estado]:\n    return [[c] + e\n            for c in sucesorasConfiguracion(p, e[0])\n            if c not in e]\n\ndef jarras(p: Problema) -> list[Estado]:\n    soluciones = buscaAnchura(lambda e: sucesores(p, e),\n                              lambda e: esFinal(p, e),\n                              inicial)\n    return [list(reversed(e)) for e in soluciones]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_jarras() -> None:\n    assert jarras((4,3,2))[:3] == \\\n        [[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)],\n         [(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)],\n         [(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]]\n    assert len(jarras((15,10,5))) == 8\n    assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9]\n    assert jarras((15,10,4)) == []\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_jarras()\n#    Verificado\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. La funci\u00f3n de Fibonacci por programaci\u00f3n din\u00e1mica<\/h3>\n<p>Los primeros t\u00e9rminos de la sucesi\u00f3n de Fibonacci son<\/p>\n<pre lang=\"text\">\n   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...\n<\/pre>\n<p>Escribir dos definiciones (una recursiva y otra con programaci\u00f3n din\u00e1mica) de la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   fib :: Integer -> Integer\n<\/pre>\n<p>tal que <code>fib n<\/code> es el <code>n<\/code>-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   fib 6 == 8\n<\/pre>\n<p>Comparar la eficiencia de las dos definiciones.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule La_funcion_de_Fibonacci_por_programacion_dinamica where\n\nimport Data.Array\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nfib1 :: Integer -> Integer\nfib1 0 = 0\nfib1 1 = 1\nfib1 n = fib1 (n-1) + fib1 (n-2)\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nfib2 :: Integer -> Integer\nfib2 n = vectorFib2 n ! n\n\n-- (vectorFib2 n) es el vector con \u00edndices de 0 a n tal que el valor\n-- de la posici\u00f3n i es el i-\u00e9simo n\u00famero de Finonacci. Por ejemplo,\n--    \u03bb> vectorFib2 7\n--    array (0,7) [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13)]\nvectorFib2 :: Integer -> Array Integer Integer\nvectorFib2 n = v where\n  v = array (0,n) [(i,f i) | i <- [0..n]]\n  f 0 = 0\n  f 1 = 1\n  f m = v!(m-1) + v!(m-2)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> fib1 34\n--    5702887\n--    (11.82 secs, 3,504,944,704 bytes)\n--    \u03bb> fib2 34\n--    5702887\n--    (0.01 secs, 587,808 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    fib1 6 `shouldBe` 8\n  it \"e2\" $\n    fib2 6 `shouldBe` 8\n  it \"e3\" $\n    map fib1 [0..9] `shouldBe` map fib2 [0..9]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0007 seconds\n--    3 examples, 0 failures\n--    (0.01 secs, 788,952 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nimport numpy as np\nimport numpy.typing as npt\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\ndef fib1(n: int) -> int:\n    if n == 0:\n        return 0\n    if n == 1:\n        return 1\n    return fib1(n - 1) + fib1(n - 2)\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef fib2(n: int) -> int:\n    return vectorFib2(n)[n]\n\n# (vectorFib2 n) es el vector con \u00edndices de 0 a n tal que el valor\n# de la posici\u00f3n i es el i-\u00e9simo n\u00famero de Finonacci. Por ejemplo,\n#    >>> vectorFib2(7)\n#    [0, 1, 1, 2, 3, 5, 8, 13]\ndef vectorFib2(n: int) -> list[int]:\n    v = [0] * (n + 1)\n    v[0] = 0\n    v[1] = 1\n    for i in range(2, n + 1):\n        v[i] = v[i - 1] + v[i - 2]\n    return v\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica y array)\n# =================================================\n\ndef fib3(n: int) -> int:\n    return vectorFib3(n)[n]\n\n# (vectorFib3 n) es el vector con \u00edndices de 0 a n tal que el valor\n# de la posici\u00f3n i es el i-\u00e9simo n\u00famero de Finonacci. Por ejemplo,\n#    >>> vectorFib3(7)\n#    array([ 0,  1,  1,  2,  3,  5,  8, 13])\ndef vectorFib3(n: int) -> npt.NDArray[np.complex64]:\n    v = np.zeros(n + 1, dtype=int)\n    v[0] = 0\n    v[1] = 1\n    for i in range(2, n + 1):\n        v[i] = v[i - 1] + v[i - 2]\n    return v\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('fib1(34)')\n#    2.10 segundos\n#    >>> tiempo('fib2(34)')\n#    0.00 segundos\n#    >>> tiempo('fib3(34)')\n#    0.00 segundos\n#\n#    >>> tiempo('fib2(100000)')\n#    0.37 segundos\n#    >>> tiempo('fib3(100000)')\n#    0.08 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_fib() -> None:\n    assert fib1(6) == 8\n    assert fib2(6) == 8\n    assert fib3(6) == 8\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_fib()\n#    Verificado\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Coeficientes binomiales (con programaci\u00f3n din\u00e1mica)<\/h3>\n<p>El coeficiente binomial <code>n<\/code> sobre <code>k<\/code> es el n\u00famero de subconjuntos de <code>k<\/code> elementos escogidos de un conjunto con <code>n<\/code> elementos.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   binomial :: Integer -> Integer -> Integer\n<\/pre>\n<p>tal que <code>binomial n k<\/code> es el coeficiente binomial <code>n<\/code> sobre <code>k<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   binomial 6 3 == 20\n   binomial 5 2 == 10\n   binomial 5 3 == 10\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Coeficientes_binomiales where\n\nimport Data.Array (Array, (!), array)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nbinomial1 :: Integer -> Integer -> Integer\nbinomial1 _ 0 = 1\nbinomial1 n k\n  | n == k    = 1\n  | otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nbinomial2 :: Integer -> Integer -> Integer\nbinomial2 n k = matrizBinomial2 n k ! (n,k)\n\n-- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el\n-- valor en la posici\u00f3n (i,j) (con j <= i) es el coeficiente binomial i\n-- sobre j. Por ejemplo,\n--    \u03bb> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]]\n--    [[1],[1,1],[1,2,1],[1,3,3,1]]\nmatrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer\nmatrizBinomial2 n k = q where\n  q = array ((0,0),(n,k)) [((i,j),f i j) | i <- [0..n], j <- [0..k]]\n  f _ 0 = 1\n  f i j\n    | i == j    = 1\n    | otherwise = q!(i-1,j-1) + q!(i-1,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> binomial1 25 12\n--    5200300\n--    (6.45 secs, 2,654,797,776 bytes)\n--    \u03bb> binomial2 25 12\n--    5200300\n--    (0.00 secs, 826,272 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    binomial1 6 3 `shouldBe` 20\n  it \"e2\" $\n    binomial1 5 2 `shouldBe` 10\n  it \"e3\" $\n    binomial1 5 3 `shouldBe` 10\n  it \"e4\" $\n    binomial2 6 3 `shouldBe` 20\n  it \"e5\" $\n    binomial2 5 2 `shouldBe` 10\n  it \"e6\" $\n    binomial2 5 3 `shouldBe` 10\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--\n--    Finished in 0.0006 seconds\n--    6 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nimport numpy as np\nimport numpy.typing as npt\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\ndef binomial1(n: int, k: int) -> int:\n    if k == 0:\n        return 1\n    if n == k:\n        return 1\n    return binomial1(n-1, k-1) + binomial1(n-1, k)\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef binomial2(n: int, k: int) -> int:\n    return matrizBinomial2(n, k)[n][k]\n\n# (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el\n# valor en la posici\u00f3n (i,j) (con j <= i) es el coeficiente binomial i\n# sobre j. Por ejemplo,\n#    >>> matrizBinomial2(3, 3)\n#    [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1]]\ndef matrizBinomial2(n: int, k: int) -> list[list[int]]:\n    q = [[0 for i in range(k + 1)] for j in range(n + 1)]\n\n    for i in range(n + 1):\n        for j in range(min(i, k) + 1):\n            if j == 0:\n                q[i][j] = 1\n            elif i == j:\n                q[i][j] = 1\n            else:\n                q[i][j] = q[i - 1][j - 1] + q[i - 1][j]\n\n    return q\n\n# 3\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica y numpy)\n# ================================================\n\ndef binomial3(n: int, k: int) -> int:\n    return matrizBinomial3(n, k)[n][k]\n\n# (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el\n# valor en la posici\u00f3n (i,j) (con j <= i) es el coeficiente binomial i\n# sobre j. Por ejemplo,\n#    >>> matrizBinomial3(3, 3)\n#    array([[1, 0, 0, 0],\n#           [1, 1, 0, 0],\n#           [1, 2, 1, 0],\n#           [1, 3, 3, 1]])\ndef matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]:\n    q = np.zeros((n + 1, k + 1), dtype=object)\n\n    for i in range(n + 1):\n        for j in range(min(i, k) + 1):\n            if j == 0:\n                q[i, j] = 1\n            elif i == j:\n                q[i, j] = 1\n            else:\n                q[i, j] = q[i - 1, j - 1] + q[i - 1, j]\n\n    return q\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('binomial1(27, 12)')\n#    4.26 segundos\n#    >>> tiempo('binomial2(27, 12)')\n#    0.00 segundos\n#    >>> tiempo('binomial3(27, 12)')\n#    0.00 segundos\n#\n# >>> tiempo('binomial2(50000, 12)')\n# 0.18 segundos\n# >>> tiempo('binomial3(50000, 12)')\n# 0.26 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_binomial() -> None:\n    assert binomial1(6, 3) == 20\n    assert binomial1(5, 2) == 10\n    assert binomial1(5, 3) == 10\n    assert binomial2(6, 3) == 20\n    assert binomial2(5, 2) == 10\n    assert binomial2(5, 3) == 10\n    assert binomial3(6, 3) == 20\n    assert binomial3(5, 2) == 10\n    assert binomial3(5, 3) == 10\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_binomial()\n#    Verificado\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Longitud de la subsecuencia com\u00fan m\u00e1xima (con programaci\u00f3n din\u00e1mica)<\/h3>\n<p>Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparec\u00edan originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, &#8220;aaoa&#8221; es una subsecuencia de la secuencia &#8220;amapola&#8221;.<\/p>\n<p>El t\u00e9rmino tambi\u00e9n se aplica cuando quitamos todos los elementos (es decir, la secuencia vac\u00eda es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de s\u00ed misma).<\/p>\n<p>Dadas dos secuencias X e Y, decimos que Z es una subsecuencia com\u00fan de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = &#8220;amapola&#8221; e Y = &#8220;matamoscas&#8221;, la secuencia &#8220;aaoa&#8221; es una de las subsecuencias comunes de X e Y m\u00e1s larga, con longitud 4, ya que no hay ninguna subsecuencia com\u00fan a X e Y de longitud mayor que 4. Tambi\u00e9n son subsecuencias comunes de longitud 4 &#8220;maoa&#8221; o &#8220;amoa&#8221;.<\/p>\n<p>Se desea encontrar la longitud de las subsecuencias comunes m\u00e1s largas de dos secuencias de caracteres dadas.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   longitudSCM :: Eq a => [a] -> [a] -> Int\n<\/pre>\n<p>tal que <code>longitudSCM xs ys<\/code> es la longitud de la subsecuencia m\u00e1xima de <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   longitudSCM \"amapola\" \"matamoscas\" == 4\n   longitudSCM \"atamos\" \"matamoscas\"  == 6\n   longitudSCM \"aaa\" \"bbbb\"           == 0\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Longitud_SCM where\n\nimport Data.Array (Array,(!), array, listArray)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nlongitudSCM1 :: Eq a => [a] -> [a] -> Int\nlongitudSCM1 [] _ = 0\nlongitudSCM1 _ [] = 0\nlongitudSCM1 (x:xs) (y:ys)\n  | x == y    = 1 + longitudSCM1 xs ys\n  | otherwise = max (longitudSCM1 (x:xs) ys) (longitudSCM1 xs (y:ys))\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nlongitudSCM2 :: Eq a => [a] -> [a] -> Int\nlongitudSCM2 xs ys = matrizLongitudSCM2 xs ys ! (n,m)\n  where n = length xs\n        m = length ys\n\n-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n\n-- y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n-- el valor en la posici\u00f3n (i,j) es la longitud de la SCM de los i\n-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,\n--    \u03bb> elems (matrizLongitudSCM2 \"amapola\" \"matamoscas\")\n--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,\n--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,\n--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]\n-- Gr\u00e1ficamente,\n--       m a t a m o s c a s\n--    [0,0,0,0,0,0,0,0,0,0,0,\n-- a   0,0,1,1,1,1,1,1,1,1,1,\n-- m   0,1,1,1,1,2,2,2,2,2,2,\n-- a   0,1,2,2,2,2,2,2,2,3,3,\n-- p   0,1,2,2,2,2,2,2,2,3,3,\n-- o   0,1,2,2,2,2,3,3,3,3,3,\n-- l   0,1,2,2,2,2,3,3,3,3,3,\n-- a   0,1,2,2,3,3,3,3,3,4,4]\nmatrizLongitudSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) Int\nmatrizLongitudSCM2 xs ys = q\n  where\n    n = length xs\n    m = length ys\n    v = listArray (1,n) xs\n    w = listArray (1,m) ys\n    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\n      where f 0 _ = 0\n            f _ 0 = 0\n            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)\n                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> longitudSCM1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))\n--    9\n--    (13.90 secs, 8,883,660,048 bytes)\n--    \u03bb> longitudSCM2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))\n--    9\n--    (0.01 secs, 953,880 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    longitudSCM1 \"amapola\" \"matamoscas\" `shouldBe` 4\n  it \"e2\" $\n    longitudSCM1 \"atamos\" \"matamoscas\"  `shouldBe` 6\n  it \"e3\" $\n    longitudSCM1 \"aaa\" \"bbbb\"           `shouldBe` 0\n  it \"e4\" $\n    longitudSCM2 \"amapola\" \"matamoscas\" `shouldBe` 4\n  it \"e5\" $\n    longitudSCM2 \"atamos\" \"matamoscas\"  `shouldBe` 6\n  it \"e6\" $\n    longitudSCM2 \"aaa\" \"bbbb\"           `shouldBe` 0\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--\n--    Finished in 0.0025 seconds\n--    6 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom timeit import Timer, default_timer\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\ndef longitudSCM1(xs: str, ys: str) -> int:\n    if not xs:\n        return 0\n    if not ys:\n        return 0\n    if xs[0] == ys[0]:\n        return 1 + longitudSCM1(xs[1:], ys[1:])\n    return max(longitudSCM1(xs, ys[1:]), longitudSCM1(xs[1:], ys))\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef longitudSCM2(xs: str, ys: str) -> int:\n    n = len(xs)\n    m = len(ys)\n    return matrizLongitudSCM2(xs, ys)[n][m]\n\n# matrizLongitudSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n\n# y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n# el valor en la posici\u00f3n (i,j) es la longitud de la SCM de los i\n# primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,\n#    >>> matrizLongitudSCM2(\"amapola\", \"matamoscas\")\n#    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n#     [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n#     [0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2],\n#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],\n#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],\n#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],\n#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],\n#     [0, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4]]\n#    # Gr\u00e1ficamente,\n#       m a t a m o s c a s\n#    [0,0,0,0,0,0,0,0,0,0,0,\n# a   0,0,1,1,1,1,1,1,1,1,1,\n# m   0,1,1,1,1,2,2,2,2,2,2,\n# a   0,1,2,2,2,2,2,2,2,3,3,\n# p   0,1,2,2,2,2,2,2,2,3,3,\n# o   0,1,2,2,2,2,3,3,3,3,3,\n# l   0,1,2,2,2,2,3,3,3,3,3,\n# a   0,1,2,2,3,3,3,3,3,4,4]\ndef matrizLongitudSCM2(xs: str, ys: str) -> list[list[int]]:\n    n = len(xs)\n    m = len(ys)\n    q = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n    for i in range(1, n + 1):\n        for j in range(1, m + 1):\n            if xs[i - 1] == ys[j - 1]:\n                q[i][j] = 1 + q[i - 1][j - 1]\n            else:\n                q[i][j] = max(q[i - 1][j], q[i][j - 1])\n    return q\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('longitudSCM1([1,3]*9, [2,3]*9)')\n#    8.04 segundos\n#    >>> tiempo('longitudSCM2([1,3]*9, [2,3]*9)')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_longitudSCM() -> None:\n    assert longitudSCM1(\"amapola\", \"matamoscas\") == 4\n    assert longitudSCM1(\"atamos\", \"matamoscas\")  == 6\n    assert longitudSCM1(\"aaa\", \"bbbb\")           == 0\n    assert longitudSCM2(\"amapola\", \"matamoscas\") == 4\n    assert longitudSCM2(\"atamos\", \"matamoscas\")  == 6\n    assert longitudSCM2(\"aaa\", \"bbbb\")           == 0\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_longitudSCM()\n#    Verificado\n<\/pre>\n<p><a name=\"ej6\"><\/a><\/p>\n<h3>6. Subsecuencia com\u00fan m\u00e1xima (con programaci\u00f3n din\u00e1mica)<\/h3>\n<p>Si a una secuencia X de elementos (pongamos por ejemplo,  le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparec\u00edan originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, &#8220;aaoa&#8221; es una subsecuencia de la secuencia &#8220;amapola&#8221;.<\/p>\n<p>El t\u00e9rmino tambi\u00e9n se aplica cuando quitamos todos los elementos (es decir, la secuencia vac\u00eda es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de s\u00ed misma).<\/p>\n<p>Dadas dos secuencias X e Y, decimos que Z es una subsecuencia  de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = &#8220;amapola&#8221; e Y = &#8220;matamoscas&#8221;, la secuencia &#8220;aaoa&#8221; es una de las subsecuencias comunes de X e Y m\u00e1s larga, con longitud 4, ya que no hay ninguna subsecuencia com\u00fan a X e Y de longitud mayor que 4. Tambi\u00e9n son subsecuencias comunes de longitud 4 &#8220;maoa&#8221; o &#8220;amoa&#8221;.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   scm :: Eq a => [a] -> [a] -> [a]\n<\/pre>\n<p>tal que <code>scm xs ys<\/code> es una de las subsecuencias comunes de longitud m\u00e1xima de <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   scm \"amapola\" \"matamoscas\" == \"amoa\"\n   scm \"atamos\" \"matamoscas\"  == \"atamos\"\n   scm \"aaa\" \"bbbb\"           == \"\"\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Subsecuencia_comun_maxima where\n\nimport Data.Array (Array, (!), array, listArray)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nscm1 :: Eq a => [a] -> [a] -> [a]\nscm1 [] _ = []\nscm1 _ [] = []\nscm1 (x:xs) (y:ys)\n  | x == y    = x : scm1 xs ys\n  | otherwise = mayor (scm1 (x:xs) ys) (scm1 xs (y:ys))\n\n-- (mayor xs ys) es la cadena m\u00e1s larga de xs e ys.\n--    mayor \"hola\" \"buenas\"  ==  \"buenas\"\n--    mayor \"hola\" \"pera\"    ==  \"hola\"\nmayor :: [a] -> [a] -> [a]\nmayor xs ys\n  | length xs >= length ys = xs\n  | otherwise              = ys\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nscm2 :: Eq a => [a] -> [a] -> [a]\nscm2 xs ys = reverse (matrizSCM2 xs ys ! (n,m))\n  where n = length xs\n        m = length ys\n\n-- (matrizSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n\n-- y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n-- el valor en la posici\u00f3n (i,j) es una SCM de los i primeros\n-- elementos de xs y los j primeros elementos de ys. Por ejemplo,\n--    \u03bb> elems (matrizSCM2 \"amapola\" \"matamoscas\")\n--    [\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\n--     \"a\",\"a\",\"a\",\"\",\"m\",\"a\",\"a\",\"a\",\"ma\",\"ma\",\"ma\",\"ma\",\"ma\",\"ma\",\"\",\n--     \"m\",\"am\",\"am\",\"aa\",\"ma\",\"ma\",\"ma\",\"ma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\n--     \"am\",\"aa\",\"ma\",\"ma\",\"ma\",\"ma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\"am\",\"aa\",\n--     \"ma\",\"oma\",\"oma\",\"oma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\"am\",\"aa\",\"ma\",\n--     \"oma\",\"oma\",\"oma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\"am\",\"aam\",\"aam\",\"oma\",\n--     \"oma\",\"oma\",\"aoma\",\"aoma\"]\n-- Gr\u00e1ficamente,\n--        m   a    t    a     m     o     s     c     a      s\n--    [\"\",\"\" ,\"\"  ,\"\"  ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"    ,\"\",\n-- a   \"\",\"\" ,\"a\" ,\"a\" ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"   ,\"a\",\n-- m   \"\",\"m\",\"a\" ,\"a\" ,\"a\"  ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\"  ,\"ma\",\n-- a   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n-- p   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n-- o   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n-- l   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n-- a   \"\",\"m\",\"am\",\"am\",\"aam\",\"aam\",\"oma\",\"oma\",\"oma\",\"aoma\",\"aoma\"]\nmatrizSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) [a]\nmatrizSCM2 xs ys = q where\n  q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\n  n = length xs\n  m = length ys\n  v = listArray (1,n) xs\n  w = listArray (1,m) ys\n  f 0 _ = []\n  f _ 0 = []\n  f i j | v ! i == w ! j = (v!i) : (q ! (i-1,j-1))\n        | otherwise      = mayor (q ! (i-1,j)) (q ! (i,j-1))\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (scm1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))\n--    9\n--    (20.17 secs, 11,436,759,992 bytes)\n--    \u03bb> length (scm2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))\n--    9\n--    (0.00 secs, 1,013,624 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    scm1 \"amapola\" \"matamoscas\" `shouldBe` \"amoa\"\n  it \"e2\" $\n    scm1 \"atamos\" \"matamoscas\"  `shouldBe` \"atamos\"\n  it \"e3\" $\n    scm1 \"aaa\" \"bbbb\"           `shouldBe` \"\"\n  it \"e4\" $\n    scm2 \"amapola\" \"matamoscas\" `shouldBe` \"amoa\"\n  it \"e5\" $\n    scm2 \"atamos\" \"matamoscas\"  `shouldBe` \"atamos\"\n  it \"e6\" $\n    scm2 \"aaa\" \"bbbb\"           `shouldBe` \"\"\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--\n--    Finished in 0.0026 seconds\n--    6 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\n# (mayor xs ys) es la cadena m\u00e1s larga de xs e ys.\n#    mayor \"hola\" \"buenas\"  ==  \"buenas\"\n#    mayor \"hola\" \"pera\"    ==  \"hola\"\ndef mayor(xs: str, ys: str) -> str:\n    if len(xs) >= len(ys):\n        return xs\n    return ys\n\ndef scm1(xs: str, ys: str) -> str:\n    if not xs:\n        return \"\"\n    if not ys:\n        return \"\"\n    if xs[0] == ys[0]:\n        return xs[0] + scm1(xs[1:], ys[1:])\n    return mayor(scm1(xs, ys[1:]), scm1(xs[1:], ys))\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef scm2(xs: str, ys: str) -> str:\n    n = len(xs)\n    m = len(ys)\n    return (matrizSCM2(xs, ys)[n][m])[::-1]\n\n# matrizSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n\n# y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n# el valor en la posici\u00f3n (i,j) es una SCM de los i primeros\n# elementos de xs y los j primeros elementos de ys. Por ejemplo,\n#    >>> matrizSCM2(\"amapola\", \"matamoscas\")\n#    [['', '', '', '', '', '', '', '', '', '', ''],\n#     ['', '', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],\n#     ['', 'm', 'a', 'a', 'a', 'ma', 'ma', 'ma', 'ma', 'ma', 'ma'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aam', 'aam', 'oma', 'oma', 'oma', 'aoma', 'aoma']]\n# Gr\u00e1ficamente,\n#        m   a    t    a     m     o     s     c     a      s\n#    [\"\",\"\" ,\"\"  ,\"\"  ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"    ,\"\",\n# a   \"\",\"\" ,\"a\" ,\"a\" ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"   ,\"a\",\n# m   \"\",\"m\",\"a\" ,\"a\" ,\"a\"  ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\"  ,\"ma\",\n# a   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n# p   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n# o   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n# l   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n# a   \"\",\"m\",\"am\",\"am\",\"aam\",\"aam\",\"oma\",\"oma\",\"oma\",\"aoma\",\"aoma\"]\ndef matrizSCM2(xs: str, ys: str) -> list[list[str]]:\n    n = len(xs)\n    m = len(ys)\n    q = [[\"\" for _ in range(m + 1)] for _ in range(n + 1)]\n    for i in range(1, n + 1):\n        for j in range(1, m + 1):\n            if xs[i - 1] == ys[j - 1]:\n                q[i][j] = xs[i - 1] + q[i - 1][j - 1]\n            else:\n                q[i][j] = mayor(q[i - 1][j], q[i][j - 1])\n    return q\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('scm1([\"1\",\"3\"]*9, [\"2\",\"3\"]*9)')\n#    8.44 segundos\n#    >>> tiempo('scm2([\"1\",\"3\"]*9, [\"2\",\"3\"]*9)')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_scm() -> None:\n    assert scm1(\"amapola\", \"matamoscas\") == \"amoa\"\n    assert scm1(\"atamos\", \"matamoscas\")  == \"atamos\"\n    assert scm1(\"aaa\", \"bbbb\")           == \"\"\n    assert scm2(\"amapola\", \"matamoscas\") == \"amoa\"\n    assert scm2(\"atamos\", \"matamoscas\")  == \"atamos\"\n    assert scm2(\"aaa\", \"bbbb\")           == \"\"\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_scm()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Durante el mes de septiembre he publicado en Exercitium las soluciones de los siguientes problemas: 1. Problema de suma cero (mediante espacio de estados) 2. Problema de las jarras (mediante espacios de estados) 3. La funci\u00f3n de Fibonacci por programaci\u00f3n din\u00e1mica 4. Coeficientes binomiales (con programaci\u00f3n din\u00e1mica) 5. Longitud de la subsecuencia com\u00fan m\u00e1xima (con&#8230;<\/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\/8029"}],"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=8029"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8029\/revisions"}],"predecessor-version":[{"id":8030,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8029\/revisions\/8030"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=8029"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=8029"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=8029"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}