{"id":8042,"date":"2023-10-30T16:27:17","date_gmt":"2023-10-30T15:27:17","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=8042"},"modified":"2023-10-30T16:27:17","modified_gmt":"2023-10-30T15:27:17","slug":"30-oct-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/30-oct-23\/","title":{"rendered":"El mes de octubre en Exercitium (Ejercicios con Haskell y Python)"},"content":{"rendered":"<p>Durante el mes de octubre 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. La distancia Levenshtein (con programaci\u00f3n din\u00e1mica)<\/a><\/li>\n<li><a href=\"#ej2\">2. Caminos en una ret\u00edcula (con programaci\u00f3n din\u00e1mica)<\/a><\/li>\n<li><a href=\"#ej3\">3. Caminos en una matriz (con programaci\u00f3n din\u00e1mica)<\/a><\/li>\n<li><a href=\"#ej4\">4. M\u00e1xima suma de los caminos en una matriz<\/a><\/li>\n<li><a href=\"#ej5\">5. Camino de m\u00e1xima suma en una matriz<\/a><\/li>\n<li><a href=\"#ej6\">6. M\u00e9todo de Her\u00f3n para calcular la ra\u00edz cuadrada<\/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. La distancia Levenshtein (con programaci\u00f3n din\u00e1mica)<\/h3>\n<p>La distancia de Levenshtein (o distancia de edici\u00f3n) es el  m\u00ednimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edici\u00f3n que se pueden hacer son:<\/p>\n<ul>\n<li>insertar un car\u00e1cter (por ejemplo, de &#8220;abc&#8221; a &#8220;abca&#8221;)<\/li>\n<li>eliminar un car\u00e1cter (por ejemplo, de &#8220;abc&#8221; a &#8220;ac&#8221;)<\/li>\n<li>sustituir un car\u00e1cter (por ejemplo, de &#8220;abc&#8221; a &#8220;adc&#8221;)<\/li>\n<\/ul>\n<p>Por ejemplo, la distancia de Levenshtein entre &#8220;casa&#8221; y &#8220;calle&#8221; es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:<\/p>\n<pre lang=\"text\">\n   \"casa\"  --> \"cala\"  (sustituci\u00f3n de 's' por 'l')\n   \"cala\"  --> \"calla\" (inserci\u00f3n de 'l' entre 'l' y 'a')\n   \"calla\" --> \"calle\" (sustituci\u00f3n de 'a' por 'e')\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   levenshtein :: String -> String -> Int\n<\/pre>\n<p>tal que <code>levenshtein xs ys<\/code> es la distancia de Levenshtein entre <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   levenshtein \"casa\"  \"calle\"    ==  3\n   levenshtein \"calle\" \"casa\"     ==  3\n   levenshtein \"casa\"  \"casa\"     ==  0\n   levenshtein \"ana\" \"maria\"      ==  3\n   levenshtein \"agua\" \"manantial\" ==  7\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 Levenshtein 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\nlevenshtein1 :: String -> String -> Int\nlevenshtein1 \"\" ys = length ys\nlevenshtein1 xs \"\" = length xs\nlevenshtein1 c1@(x:xs) c2@(y:ys)\n  | x == y    = levenshtein1 xs ys\n  | otherwise = 1 + minimum [ levenshtein1 xs c2\n                            , levenshtein1 c1 ys\n                            , levenshtein1 xs ys]\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nlevenshtein2 :: String -> String -> Int\nlevenshtein2 xs ys = matrizLevenshtein xs ys ! (m,n)\n  where  m = length xs\n         n = length ys\n\n-- (matrizLevenshtein xs ys) es la matriz cuyo n\u00famero de filas es la\n-- longitud de xs, cuyo n\u00famero de columnas es la longitud de ys y en\n-- valor en la posici\u00f3n (i,j) es la distancia de Levenshtein entre los\n-- primeros i caracteres de xs y los j primeros caracteres de ys. Por\n-- ejemplo,\n--    \u03bb> elems (matrizLevenshtein \"casa\" \"calle\")\n--    [0,1,2,3,4,5,1,0,1,2,3,4,2,1,0,1,2,3,3,2,1,1,2,3,4,3,2,2,2,3]\n-- Gr\u00e1ficamente,\n--       c a l l e\n--     0,1,2,3,4,5,\n--  c  1,0,1,2,3,4,\n--  a  2,1,0,1,2,3,\n--  s  3,2,1,1,2,3,\n--  a  4,3,2,2,2,3\nmatrizLevenshtein :: String -> String -> Array (Int,Int) Int\nmatrizLevenshtein xs ys = q where\n  q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]]\n  m = length xs\n  n = length ys\n  f 0 j = j\n  f i 0 = i\n  f i j | xs !! (i-1) == ys !! (j-1) = q ! (i-1,j-1)\n        | otherwise                  = 1 + minimum [ q ! (i-1,j)\n                                                   , q ! (i,j-1)\n                                                   , q ! (i-1,j-1)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> levenshtein1 (show (2^33)) (show (3^33))\n--    12\n--    (16.19 secs, 11,766,254,536 bytes)\n--    \u03bb> levenshtein2 (show (2^33)) (show (3^33))\n--    12\n--    (0.02 secs, 0 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"ej1\" $\n    levenshtein1 \"casa\"  \"calle\"    `shouldBe`  3\n  it \"ej2\" $\n    levenshtein1 \"calle\" \"casa\"     `shouldBe`  3\n  it \"ej3\" $\n    levenshtein1 \"casa\"  \"casa\"     `shouldBe`  0\n  it \"ej4\" $\n    levenshtein1 \"ana\" \"maria\"      `shouldBe`  3\n  it \"ej5\" $\n    levenshtein1 \"agua\" \"manantial\" `shouldBe`  7\n  it \"ej6\" $\n    levenshtein2 \"casa\"  \"calle\"    `shouldBe`  3\n  it \"ej7\" $\n    levenshtein2 \"calle\" \"casa\"     `shouldBe`  3\n  it \"ej8\" $\n    levenshtein2 \"casa\"  \"casa\"     `shouldBe`  0\n  it \"ej9\" $\n    levenshtein2 \"ana\" \"maria\"      `shouldBe`  3\n  it \"ej10\" $\n    levenshtein2 \"agua\" \"manantial\" `shouldBe`  7\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    ej1\n--    ej2\n--    ej3\n--    ej4\n--    ej5\n--    ej6\n--    ej7\n--    ej8\n--    ej9\n--    ej10\n--\n--    Finished in 0.0024 seconds\n--    10 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\ndef levenshtein1(xs: str, ys: str) -> int:\n    if not xs:\n        return len(ys)\n    if not ys:\n        return len(xs)\n    if xs[0] == ys[0]:\n        return levenshtein1(xs[1:], ys[1:])\n    return 1 + min([levenshtein1(xs[1:], ys),\n                    levenshtein1(xs, ys[1:]),\n                    levenshtein1(xs[1:], ys[1:])])\n\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\n# matrizLevenshtein(xs, ys) es la matriz cuyo n\u00famero de filas es la\n# longitud de xs, cuyo n\u00famero de columnas es la longitud de ys y en\n# valor en la posici\u00f3n (i,j) es la distancia de Levenshtein entre los\n# primeros i caracteres de xs y los j primeros caracteres de ys. Por\n# ejemplo,\n#    >>> matrizLevenshtein(\"casa\", \"calle\")\n#    [[0, 1, 2, 3, 4, 5],\n#     [1, 0, 1, 2, 3, 4],\n#     [2, 1, 0, 1, 2, 3],\n#     [3, 2, 1, 1, 2, 3],\n#     [4, 3, 2, 2, 2, 3]]\n# Gr\u00e1ficamente,\n#       c a l l e\n#     0,1,2,3,4,5,\n#  c  1,0,1,2,3,4,\n#  a  2,1,0,1,2,3,\n#  s  3,2,1,1,2,3,\n#  a  4,3,2,2,2,3\ndef matrizLevenshtein(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(n + 1):\n        q[i][0] = i\n    for j in range(m + 1):\n        q[0][j] = j\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] = q[i - 1][j - 1]\n            else:\n                q[i][j] = 1 + min([q[i-1][j],  q[i][j-1], q[i-1][j-1]])\n    return q\n\ndef levenshtein2(xs: str, ys: str) -> int:\n    m = len(xs)\n    n = len(ys)\n    return matrizLevenshtein(xs, ys)[m][n]\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('levenshtein1(str(2**33), str(3**33))')\n#    13.78 segundos\n#    >>> tiempo('levenshtein2(str(2**33), str(3**33))')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_levenshtein() -> None:\n    assert levenshtein1(\"casa\",  \"calle\")     ==  3\n    assert levenshtein1(\"calle\", \"casa\")      ==  3\n    assert levenshtein1(\"casa\",  \"casa\")      ==  0\n    assert levenshtein1(\"ana\",   \"maria\")     ==  3\n    assert levenshtein1(\"agua\",  \"manantial\") ==  7\n    assert levenshtein2(\"casa\",  \"calle\")     ==  3\n    assert levenshtein2(\"calle\", \"casa\")      ==  3\n    assert levenshtein2(\"casa\",  \"casa\")      ==  0\n    assert levenshtein2(\"ana\",   \"maria\")     ==  3\n    assert levenshtein2(\"agua\",  \"manantial\") ==  7\n    print(\"Verificado\")\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Caminos en una ret\u00edcula (con programaci\u00f3n din\u00e1mica)<\/h3>\n<p>Se considera una ret\u00edcula con sus posiciones numeradas, desde el v\u00e9rtice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la ret\u00edcula de dimensi\u00f3n 3&#215;4 se numera como sigue:<\/p>\n<pre lang=\"text\">\n   |-------+-------+-------+-------|\n   | (1,1) | (1,2) | (1,3) | (1,4) |\n   | (2,1) | (2,2) | (2,3) | (2,4) |\n   | (3,1) | (3,2) | (3,3) | (3,4) |\n   |-------+-------+-------+-------|\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   caminos :: (Int,Int) -> [[(Int,Int)]]\n<\/pre>\n<p>tal que <code>caminos (m,n)<\/code> es la lista de los caminos en la ret\u00edcula de dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> caminos (2,3)\n   [[(1,1),(1,2),(1,3),(2,3)],\n    [(1,1),(1,2),(2,2),(2,3)],\n    [(1,1),(2,1),(2,2),(2,3)]]\n   \u03bb> mapM_ print (caminos (3,4))\n   [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]\n   [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]\n   [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]\n   [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]\n   [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]\n   [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]\n   [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]\n   [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]\n   [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]\n   [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]\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 Programacion_dinamica_Caminos_en_una_reticula where\n\nimport Data.Array (Array, (!), array)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n (por recursi\u00f3n)\n-- ===========================\n\ncaminos1 :: (Int,Int) -> [[(Int,Int)]]\ncaminos1 p = map reverse (caminos1Aux p)\n  where\n    caminos1Aux (1,y) = [[(1,z) | z <- [y,y-1..1]]]\n    caminos1Aux (x,1) = [[(z,1) | z <- [x,x-1..1]]]\n    caminos1Aux (x,y) = [(x,y) : cs | cs <- caminos1Aux (x-1,y) ++\n                                            caminos1Aux (x,y-1)]\n\n-- 2\u00aa soluci\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =======================================\n\ncaminos2 :: (Int,Int) -> [[(Int,Int)]]\ncaminos2 p = map reverse (matrizCaminos p ! p)\n\nmatrizCaminos :: (Int,Int) -> Array (Int,Int) [[(Int,Int)]]\nmatrizCaminos (m,n) = q\n  where\n    q = array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]\n    f 1 y = [[(1,z) | z <- [y,y-1..1]]]\n    f x 1 = [[(z,1) | z <- [x,x-1..1]]]\n    f x y = [(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximum (head (caminos1 (2000,2000)))\n--    (2000,2000)\n--    (0.01 secs, 3,459,576 bytes)\n--    \u03bb> maximum (head (caminos2 (2000,2000)))\n--    (2000,2000)\n--    (2.79 secs, 1,507,636,688 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    caminos1 (2,3) `shouldBe`\n    [[(1,1),(1,2),(1,3),(2,3)],\n     [(1,1),(1,2),(2,2),(2,3)],\n     [(1,1),(2,1),(2,2),(2,3)]]\n  it \"e2\" $\n    caminos2 (2,3) `shouldBe`\n    [[(1,1),(1,2),(1,3),(2,3)],\n     [(1,1),(1,2),(2,2),(2,3)],\n     [(1,1),(2,1),(2,2),(2,3)]]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0010 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom collections import defaultdict\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n (por recursi\u00f3n)\n# ===========================\n\ndef caminos1(p: tuple[int, int]) -> list[list[tuple[int, int]]]:\n    def aux(p: tuple[int, int]) -> list[list[tuple[int, int]]]:\n        (x, y) = p\n        if x == 1:\n            return [[(1,z) for z in range(y, 0, -1)]]\n        if y == 1:\n            return [[(z,1) for z in range(x, 0, -1)]]\n        return [[(x,y)] + cs for cs in aux((x-1,y)) + aux((x,y-1))]\n\n    return [list(reversed(ps)) for ps in aux(p)]\n\n# 2\u00aa soluci\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =======================================\n\ndef caminos2(p: tuple[int, int]) -> list[list[tuple[int, int]]]:\n    return [list(reversed(ps)) for ps in diccionarioCaminos(p)[p]]\n\n\n# diccionarioCaminos((m,n)) es el diccionario cuyas claves son los\n# puntos de la ret\u00edcula mxn y sus valores son los caminos a dichos\n# puntos. Por ejemplo,\n#    >>> diccionarioCaminos((2,3))\n#    defaultdict(<class 'list'>,\n#                {(1,1): [[(1,1)]],\n#                 (1,2): [[(1,2),(1,1)]],\n#                 (1,3): [[(1,3),(1,2),(1,1)]],\n#                 (2,1): [[(2,1),(1,1)]],\n#                 (2,2): [[(2,2),(1,2),(1,1)],\n#                         [(2,2),(2,1),(1,1)]],\n#                 (2,3): [[(2,3),(1,3),(1,2),(1,1)],\n#                         [(2,3),(2,2),(1,2),(1,1)],\n#                         [(2,3),(2,2),(2,1),(1,1)]]})\ndef diccionarioCaminos(p: tuple[int, int]) -> dict[tuple[int, int], list[list[tuple[int, int]]]]:\n    m, n = p\n    q = defaultdict(list)\n    for i in range(1, m + 1):\n        for j in range(1, n + 1):\n            if i == 1:\n                q[(i, j)] = [[(1, z) for z in range(j, 0, -1)]]\n            elif j == 1:\n                q[(i, j)] = [[(z, 1) for z in range(i, 0, -1)]]\n            else:\n                q[(i, j)] = [[(i, j)] + cs for cs in 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('max(caminos1((13,13))[0])')\n#    26.75 segundos\n#    >>> tiempo('max(caminos2((13,13))[0])')\n#    7.40 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_caminos() -> None:\n    assert caminos1((2,3)) == \\\n        [[(1,1),(1,2),(1,3),(2,3)],\n         [(1,1),(1,2),(2,2),(2,3)],\n         [(1,1),(2,1),(2,2),(2,3)]]\n    assert caminos2((2,3)) == \\\n        [[(1,1),(1,2),(1,3),(2,3)],\n         [(1,1),(1,2),(2,2),(2,3)],\n         [(1,1),(2,1),(2,2),(2,3)]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_caminos()\n#    Verificado\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Caminos en una matriz (con programaci\u00f3n din\u00e1mica)<\/h3>\n<p>Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz<\/p>\n<pre lang=\"text\">\n   (  1  6 11  2 )\n   (  7 12  3  8 )\n   (  3  8  4  9 )\n<\/pre>\n<p>movi\u00e9ndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:<\/p>\n<pre lang=\"text\">\n   [1,6,11,2,8,9]\n   [1,6,11,3,8,9]\n   [1,6,12,3,8,9]\n   [1,7,12,3,8,9]\n   [1,6,11,3,4,9]\n   [1,6,12,3,4,9]\n   [1,7,12,3,4,9]\n   [1,6,12,8,4,9]\n   [1,7,12,8,4,9]\n   [1,7, 3,8,4,9]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   caminos :: Matrix Int -> [[Int]]\n<\/pre>\n<p>tal que <code>caminos m<\/code> es la lista de los caminos en la matriz <code>m<\/code> desde  extremo superior izquierdo hasta el extremo inferior derecho, movi\u00e9ndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n   [[1,6,11,2,8,9],\n    [1,6,11,3,8,9],\n    [1,6,12,3,8,9],\n    [1,7,12,3,8,9],\n    [1,6,11,3,4,9],\n    [1,6,12,3,4,9],\n    [1,7,12,3,4,9],\n    [1,6,12,8,4,9],\n    [1,7,12,8,4,9],\n    [1,7, 3,8,4,9]]\n   \u03bb> length (caminos (fromList 12 12 [1..]))\n   705432\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 Caminos_en_una_matriz where\n\nimport Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\ncaminos1 :: Matrix Int -> [[Int]]\ncaminos1 m =\n  reverse (map reverse (caminos1Aux m (nf,nc)))\n  where nf = nrows m\n        nc = ncols m\n\n-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m\n-- desde la posici\u00f3n (1,1) hasta la posici\u00f3n p. Por ejemplo,\ncaminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]\ncaminos1Aux m (1,1) = [[m!(1,1)]]\ncaminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]\ncaminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]\ncaminos1Aux m (i,j) = [m!(i,j) : xs\n                      | xs <- caminos1Aux m (i,j-1) ++\n                              caminos1Aux m (i-1,j)]\n\n-- 2\u00aa soluci\u00f3n (mediante programaci\u00f3n din\u00e1mica)\n-- ============================================\n\ncaminos2 :: Matrix Int -> [[Int]]\ncaminos2 m =\n  map reverse (matrizCaminos m ! (nrows m, ncols m))\n\nmatrizCaminos :: Matrix Int -> Matrix [[Int]]\nmatrizCaminos m = q\n  where\n    q = matrix (nrows m) (ncols m) f\n    f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]\n    f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]\n    f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (caminos1 (fromList 11 11 [1..]))\n--    184756\n--    (3.64 secs, 667,727,568 bytes)\n--    \u03bb> length (caminos2 (fromList 11 11 [1..]))\n--    184756\n--    (0.82 secs, 129,181,072 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    caminos1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r\n  it \"e2\" $\n    caminos2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r\n  where r = [[1,6,11,2,8,9],\n             [1,6,11,3,8,9],\n             [1,6,12,3,8,9],\n             [1,7,12,3,8,9],\n             [1,6,11,3,4,9],\n             [1,6,12,3,4,9],\n             [1,7,12,3,4,9],\n             [1,6,12,8,4,9],\n             [1,7,12,8,4,9],\n             [1,7, 3,8,4,9]]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0010 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom collections import defaultdict\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\ndef caminos1(m: list[list[int]]) -> list[list[int]]:\n    nf = len(m)\n    nc = len(m[0])\n    return list(reversed([list(reversed(xs)) for xs in caminos1Aux(m, (nf,nc))]))\n\n# caminos1Aux(m, p) es la lista de los caminos invertidos en la matriz m\n# desde la posici\u00f3n (1,1) hasta la posici\u00f3n p. Por ejemplo,\ndef caminos1Aux(m: list[list[int]], p: tuple[int, int]) -> list[list[int]]:\n    (i, j) = p\n    if p == (1,1):\n        return [[m[0][0]]]\n    if i == 1:\n        return [[m[0][k-1] for k in range(j, 0, -1)]]\n    if j == 1:\n        return [[m[k-1][0] for k in range(i, 0, -1)]]\n    return [[m[i-1][j-1]] + xs\n            for xs in caminos1Aux(m, (i,j-1)) + caminos1Aux(m, (i-1,j))]\n\n# 2\u00aa soluci\u00f3n (mediante programaci\u00f3n din\u00e1mica)\n# ============================================\n\ndef caminos2(p: list[list[int]]) -> list[list[int]]:\n    m = len(p)\n    n = len(p[0])\n    return [list(reversed(xs)) for xs in diccionarioCaminos(p)[(m, n)]]\n\n# diccionarioCaminos(p) es el diccionario cuyas claves son los\n# puntos de la matriz p y sus valores son los caminos a dichos\n# puntos. Por ejemplo,\n#    >>> diccionarioCaminos([[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n#    defaultdict(<class 'list'>,\n#                {(1, 1): [[1]],\n#                 (1, 2): [[6, 1]],\n#                 (1, 3): [[11, 6, 1]],\n#                 (1, 4): [[2, 11, 6, 1]],\n#                 (2, 1): [[7, 1]],\n#                 (2, 2): [[12, 6, 1], [12, 7, 1]],\n#                 (2, 3): [[3, 11, 6, 1], [3, 12, 6, 1], [3, 12, 7, 1]],\n#                 (2, 4): [[8, 2, 11, 6, 1], [8, 3, 11, 6, 1],\n#                          [8, 3, 12, 6, 1], [8, 3, 12, 7, 1]],\n#                 (3, 1): [[3, 7, 1]],\n#                 (3, 2): [[8, 12, 6, 1], [8, 12, 7, 1], [8, 3, 7, 1]],\n#                 (3, 3): [[4, 3, 11, 6, 1], [4, 3, 12, 6, 1],\n#                          [4, 3, 12, 7, 1], [4, 8, 12, 6, 1],\n#                          [4, 8, 12, 7, 1], [4, 8, 3, 7, 1]],\n#                 (3, 4): [[9, 8, 2, 11, 6, 1], [9, 8, 3, 11, 6, 1],\n#                          [9, 8, 3, 12, 6, 1], [9, 8, 3, 12, 7, 1],\n#                          [9, 4, 3, 11, 6, 1], [9, 4, 3, 12, 6, 1],\n#                          [9, 4, 3, 12, 7, 1], [9, 4, 8, 12, 6, 1],\n#                          [9, 4, 8, 12, 7, 1], [9, 4, 8, 3, 7, 1]]})\ndef diccionarioCaminos(p: list[list[int]]) -> dict[tuple[int, int], list[list[int]]]:\n    m = len(p)\n    n = len(p[0])\n    q = defaultdict(list)\n    for i in range(1, m + 1):\n        for j in range(1, n + 1):\n            if i == 1:\n                q[(i, j)] = [[p[0][z-1] for z in range(j, 0, -1)]]\n            elif j == 1:\n                q[(i, j)] = [[p[z-1][0] for z in range(i, 0, -1)]]\n            else:\n                q[(i, j)] = [[p[i-1][j-1]] + cs for cs in 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('caminos1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')\n#    2.20 segundos\n#    >>> tiempo('caminos2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')\n#    0.64 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_caminos() -> None:\n    r = [[1, 6, 11, 2, 8, 9],\n         [1, 6, 11, 3, 8, 9],\n         [1, 6, 12, 3, 8, 9],\n         [1, 7, 12, 3, 8, 9],\n         [1, 6, 11, 3, 4, 9],\n         [1, 6, 12, 3, 4, 9],\n         [1, 7, 12, 3, 4, 9],\n         [1, 6, 12, 8, 4, 9],\n         [1, 7, 12, 8, 4, 9],\n         [1, 7,  3, 8, 4, 9]]\n    assert caminos1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r\n    assert caminos2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_caminos()\n#    Verificado\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. M\u00e1xima suma de los caminos en una matriz<\/h3>\n<p>Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz<\/p>\n<pre lang=\"text\">\n   (  1  6 11  2 )\n   (  7 12  3  8 )\n   (  3  8  4  9 )\n<\/pre>\n<p>movi\u00e9ndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:<\/p>\n<pre lang=\"text\">\n   [1,6,11,2,8,9]\n   [1,6,11,3,8,9]\n   [1,6,12,3,8,9]\n   [1,7,12,3,8,9]\n   [1,6,11,3,4,9]\n   [1,6,12,3,4,9]\n   [1,7,12,3,4,9]\n   [1,6,12,8,4,9]\n   [1,7,12,8,4,9]\n   [1,7, 3,8,4,9]\n<\/pre>\n<p>La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de m\u00e1xima suma es el pen\u00faltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maximaSuma :: Matrix Int -> Int\n<\/pre>\n<p>tal que <code>maximaSuma m<\/code> es el m\u00e1ximo de las sumas de los caminos en la matriz <code>m<\/code> desde el extremo superior izquierdo hasta el extremo inferior derecho, movi\u00e9ndose en cada paso una casilla hacia abajo o hacia a derecha. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n   41\n   \u03bb> maximaSuma (fromList 800 800 [1..])\n   766721999\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 Maxima_suma_de_los_caminos_en_una_matriz where\n\nimport Data.Matrix (Matrix, (!), fromList, fromLists, matrix, nrows, ncols)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\nimport Caminos_en_una_matriz (caminos1, caminos2)\n\n-- 1\u00aa definicion de maximaSuma (con caminos1)\n-- ==========================================\n\nmaximaSuma1 :: Matrix Int -> Int\nmaximaSuma1 =\n  maximum . map sum . caminos1\n\n-- Se usa la funci\u00f3n caminos1 del ejercicio\n-- \"Caminos en una matriz\" que se encuentra en\n-- https:\/\/bit.ly\/45bYoYE\n\n\n-- 2\u00aa definici\u00f3n de maximaSuma (con caminos2)\n-- ==========================================\n\nmaximaSuma2 :: Matrix Int -> Int\nmaximaSuma2 =\n  maximum . map sum . caminos2\n\n-- Se usa la funci\u00f3n caminos2 del ejercicio\n-- \"Caminos en una matriz\" que se encuentra en\n-- https:\/\/bit.ly\/45bYoYE\n\n-- 3\u00aa definicion de maximaSuma (por recursi\u00f3n)\n-- ===========================================\n\nmaximaSuma3 :: Matrix Int -> Int\nmaximaSuma3 m = maximaSuma3Aux m (nf,nc)\n  where nf = nrows m\n        nc = ncols m\n\n-- (maximaSuma3Aux m p) calcula la suma m\u00e1xima de un camino hasta la\n-- posici\u00f3n p. Por ejemplo,\n--    \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)\n--    41\n--    \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)\n--    32\n--    \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)\n--    31\nmaximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int\nmaximaSuma3Aux m (1,1) = m ! (1,1)\nmaximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)\nmaximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)\nmaximaSuma3Aux m (i,j) =\n  max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)\n\n-- 4\u00aa soluci\u00f3n (mediante programaci\u00f3n din\u00e1mica)\n-- ============================================\n\nmaximaSuma4 :: Matrix Int -> Int\nmaximaSuma4 m = q ! (nf,nc)\n  where nf = nrows m\n        nc = ncols m\n        q  = matrizMaximaSuma m\n\n-- (matrizMaximaSuma m) es la matriz donde en cada posici\u00f3n p se\n-- encuentra el m\u00e1xima de las sumas de los caminos desde (1,1) a p en la\n-- matriz m. Por ejemplo,\n--    \u03bb> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n--    (  1  7 18 20 )\n--    (  8 20 23 31 )\n--    ( 11 28 32 41 )\nmatrizMaximaSuma :: Matrix Int -> Matrix Int\nmatrizMaximaSuma m = q\n  where nf = nrows m\n        nc = ncols m\n        q  = matrix nf nc f\n          where  f (1,1) = m ! (1,1)\n                 f (1,j) = q ! (1,j-1) + m ! (1,j)\n                 f (i,1) = q ! (i-1,1) + m ! (i,1)\n                 f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximaSuma1 (fromList 11 11 [1..])\n--    1781\n--    (3.88 secs, 1,525,812,680 bytes)\n--    \u03bb> maximaSuma2 (fromList 11 11 [1..])\n--    1781\n--    (1.08 secs, 546,144,264 bytes)\n--    \u03bb> maximaSuma3 (fromList 11 11 [1..])\n--    1781\n--    (0.55 secs, 217,712,280 bytes)\n--    \u03bb> maximaSuma4 (fromList 11 11 [1..])\n--    1781\n--    (0.01 secs, 643,832 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    maximaSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41\n  it \"e2\" $\n    maximaSuma1 (fromList 4 4 [1..]) `shouldBe` 73\n  it \"e3\" $\n    maximaSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41\n  it \"e4\" $\n    maximaSuma2 (fromList 4 4 [1..]) `shouldBe` 73\n  it \"e5\" $\n    maximaSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41\n  it \"e6\" $\n    maximaSuma3 (fromList 4 4 [1..]) `shouldBe` 73\n  it \"e7\" $\n    maximaSuma4 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41\n  it \"e8\" $\n    maximaSuma4 (fromList 4 4 [1..]) `shouldBe` 73\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--    e7\n--    e8\n--\n--    Finished in 0.0034 seconds\n--    8 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom collections import defaultdict\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom src.Caminos_en_una_matriz import caminos1, caminos2\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definicion de maximaSuma (con caminos1)\n# ==========================================\n\ndef maximaSuma1(m: list[list[int]]) -> int:\n    return max((sum(xs) for xs in caminos1(m)))\n\n# Se usa la funci\u00f3n caminos1 del ejercicio\n# \"Caminos en una matriz\" que se encuentra en\n# https:\/\/bit.ly\/45bYoYE\n\n# 2\u00aa definici\u00f3n de maximaSuma (con caminos2)\n# ==========================================\n\ndef maximaSuma2(m: list[list[int]]) -> int:\n    return max((sum(xs) for xs in caminos2(m)))\n\n# Se usa la funci\u00f3n caminos2 del ejercicio\n# \"Caminos en una matriz\" que se encuentra en\n# https:\/\/bit.ly\/45bYoYE\n\n# 3\u00aa definicion de maximaSuma (por recursi\u00f3n)\n# ===========================================\n\ndef maximaSuma3(m: list[list[int]]) -> int:\n    nf = len(m)\n    nc = len(m[0])\n    return maximaSuma3Aux(m, (nf,nc))\n\n# (maximaSuma3Aux m p) calcula la suma m\u00e1xima de un camino hasta la\n# posici\u00f3n p. Por ejemplo,\n#    \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)\n#    41\n#    \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)\n#    32\n#    \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)\n#    31\ndef maximaSuma3Aux(m: list[list[int]], p: tuple[int, int]) -> int:\n    (i, j) = p\n    if (i, j) == (1, 1):\n        return m[0][0]\n    if i == 1:\n        return maximaSuma3Aux(m, (1,j-1)) + m[0][j-1]\n    if j == 1:\n        return maximaSuma3Aux(m, (i-1,1)) + m[i-1][0]\n    return max(maximaSuma3Aux(m, (i,j-1)), maximaSuma3Aux(m, (i-1,j))) + m[i-1][j-1]\n\n# 4\u00aa soluci\u00f3n (mediante programaci\u00f3n din\u00e1mica)\n# ============================================\n\ndef maximaSuma4(p: list[list[int]]) -> int:\n    m = len(p)\n    n = len(p[0])\n    return diccionarioMaxSuma(p)[(m,n)]\n\n# diccionarioMaxSuma(p) es el diccionario cuyas claves son los\n# puntos de la matriz p y sus valores son las m\u00e1ximas sumas de los\n# caminos a dichos puntos. Por ejemplo,\n#    diccionarioMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n#    defaultdict(<class 'int'>,\n#                {(1, 0): 0,\n#                 (1, 1): 1,  (1, 2): 7,  (1, 3): 18, (1, 4): 20,\n#                 (2, 1): 8,  (2, 2): 20, (2, 3): 23, (2, 4): 31,\n#                 (3, 1): 11, (3, 2): 28, (3, 3): 32, (3, 4): 41})\ndef diccionarioMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], int]:\n    m = len(p)\n    n = len(p[0])\n    q: dict[tuple[int, int], int] = defaultdict(int)\n    for i in range(1, m + 1):\n        for j in range(1, n + 1):\n            if i == 1:\n                q[(i, j)] = q[(1,j-1)] + p[0][j-1]\n            elif j == 1:\n                q[(i, j)] = q[(i-1,1)] + p[i-1][0]\n            else:\n                q[(i, j)] = max(q[(i,j-1)], q[(i-1,j)]) + p[i-1][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('maximaSuma1([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')\n#    4.95 segundos\n#    >>> tiempo('maximaSuma2([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')\n#    1.49 segundos\n#    >>> tiempo('maximaSuma3([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')\n#    0.85 segundos\n#    >>> tiempo('maximaSuma4([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_maximaSuma() -> None:\n    assert maximaSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41\n    assert maximaSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41\n    assert maximaSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41\n    assert maximaSuma4([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_maximaSuma()\n#    Verificado\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Camino de m\u00e1xima suma en una matriz<\/h3>\n<p>Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz<\/p>\n<pre lang=\"text\">\n   (  1  6 11  2 )\n   (  7 12  3  8 )\n   (  3  8  4  9 )\n<\/pre>\n<p>movi\u00e9ndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:<\/p>\n<pre lang=\"text\">\n   [1,6,11,2,8,9]\n   [1,6,11,3,8,9]\n   [1,6,12,3,8,9]\n   [1,7,12,3,8,9]\n   [1,6,11,3,4,9]\n   [1,6,12,3,4,9]\n   [1,7,12,3,4,9]\n   [1,6,12,8,4,9]\n   [1,7,12,8,4,9]\n   [1,7, 3,8,4,9]\n<\/pre>\n<p>La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de m\u00e1xima suma es el pen\u00faltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   caminoMaxSuma :: Matrix Int -> [Int]\n<\/pre>\n<p>tal que <code>caminoMaxSuma m<\/code> es un camino de m\u00e1xima suma en la matriz <code>m<\/code> desde el extremo superior izquierdo hasta el extremo inferior derecho, movi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n   [1,7,12,8,4,9]\n   \u03bb> sum (caminoMaxSuma (fromList 500 500 [1..]))\n   187001249\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 Camino_de_maxima_suma_en_una_matriz where\n\nimport Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n de caminoMaxSuma (con caminos1)\n-- =============================================\n\ncaminoMaxSuma1 :: Matrix Int -> [Int]\ncaminoMaxSuma1 m =\n  head [c | c <- cs, sum c == k]\n  where cs = caminos1 m\n        k  = maximum (map sum cs)\n\ncaminos1 :: Matrix Int -> [[Int]]\ncaminos1 m =\n  reverse (map reverse (caminos1Aux m (nf,nc)))\n  where nf = nrows m\n        nc = ncols m\n\n-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m\n-- desde la posici\u00f3n (1,1) hasta la posici\u00f3n p. Por ejemplo,\ncaminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]\ncaminos1Aux m (1,1) = [[m!(1,1)]]\ncaminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]\ncaminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]\ncaminos1Aux m (i,j) = [m!(i,j) : xs\n                      | xs <- caminos1Aux m (i,j-1) ++\n                              caminos1Aux m (i-1,j)]\n\n-- 2\u00aa definici\u00f3n de caminoMaxSuma (con caminos2)\n-- =============================================\n\ncaminoMaxSuma2 :: Matrix Int -> [Int]\ncaminoMaxSuma2 m =\n  head [c | c <- cs, sum c == k]\n  where cs = caminos2 m\n        k  = maximum (map sum cs)\n\ncaminos2 :: Matrix Int -> [[Int]]\ncaminos2 m =\n  map reverse (matrizCaminos m ! (nrows m, ncols m))\n\nmatrizCaminos :: Matrix Int -> Matrix [[Int]]\nmatrizCaminos m = q\n  where\n    q = matrix (nrows m) (ncols m) f\n    f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]\n    f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]\n    f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]\n\n-- 3\u00aa definici\u00f3n de caminoMaxSuma (con programaci\u00f3n din\u00e1mica)\n-- ==========================================================\n\ncaminoMaxSuma3 :: Matrix Int -> [Int]\ncaminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))\n  where nf = nrows m\n        nc = ncols m\n        q  = caminoMaxSumaAux m\n\ncaminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])\ncaminoMaxSumaAux m = q\n  where\n    nf = nrows m\n    nc = ncols m\n    q  = matrix nf nc f\n      where\n        f (1,1) = (m!(1,1),[m!(1,1)])\n        f (1,j) = (k + m!(1,j), m!(1,j):xs)\n          where (k,xs) = q!(1,j-1)\n        f (i,1) = (k + m!(i,1), m!(i,1):xs)\n          where (k,xs) = q!(i-1,1)\n        f (i,j) | k1 > k2   = (k1 + m!(i,j), m!(i,j):xs)\n                | otherwise = (k2 + m!(i,j), m!(i,j):ys)\n          where (k1,xs) = q!(i,j-1)\n                (k2,ys) = q!(i-1,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (caminoMaxSuma1 (fromList 11 11 [1..]))\n--    21\n--    (3.92 secs, 1,778,557,904 bytes)\n--    \u03bb> length (caminoMaxSuma2 (fromList 11 11 [1..]))\n--    21\n--    (1.16 secs, 798,889,488 bytes)\n--    \u03bb> length (caminoMaxSuma3 (fromList 11 11 [1..]))\n--    21\n--    (0.00 secs, 680,256 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n    `shouldBe` [1,7,12,8,4,9]\n  it \"e2\" $\n    caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n    `shouldBe` [1,7,12,8,4,9]\n  it \"e3\" $\n    caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n    `shouldBe` [1,7,12,8,4,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<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom collections import defaultdict\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom src.Caminos_en_una_matriz import caminos1, caminos2\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n de caminoMaxSuma (con caminos1)\n# =============================================\n\ndef caminoMaxSuma1(m: list[list[int]]) -> list[int]:\n    cs = caminos1(m)\n    k = max((sum(c) for c in cs))\n    return [c for c in cs if sum(c) == k][0]\n\n# Se usa la funci\u00f3n caminos1 del ejercicio\n# \"Caminos en una matriz\" que se encuentra en\n# https:\/\/bit.ly\/45bYoYE\n\n# 2\u00aa definici\u00f3n de caminoMaxSuma (con caminos2)\n# =============================================\n\ndef caminoMaxSuma2(m: list[list[int]]) -> list[int]:\n    cs = caminos2(m)\n    k = max((sum(c) for c in cs))\n    return [c for c in cs if sum(c) == k][0]\n\n# Se usa la funci\u00f3n caminos2 del ejercicio\n# \"Caminos en una matriz\" que se encuentra en\n# https:\/\/bit.ly\/45bYoYE\n\n# 3\u00aa definici\u00f3n de caminoMaxSuma (con programaci\u00f3n din\u00e1mica)\n# ==========================================================\n\ndef caminoMaxSuma3(m: list[list[int]]) -> list[int]:\n    nf = len(m)\n    nc = len(m[0])\n    return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1]))\n\n# diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los\n# puntos de la matriz p y sus valores son los pares formados por la\n# m\u00e1xima suma de los caminos hasta dicho punto y uno de los caminos con\n# esa suma. Por ejemplo,\n#    >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n#    {(1, 1): (1, [1]),\n#     (1, 2): (7, [6, 1]),\n#     (1, 3): (18, [11, 6, 1]),\n#     (1, 4): (20, [2, 11, 6, 1]),\n#     (2, 1): (8, [7, 1]),\n#     (3, 1): (11, [3, 7, 1]),\n#     (2, 2): (20, [12, 7, 1]),\n#     (2, 3): (23, [3, 12, 7, 1]),\n#     (2, 4): (31, [8, 3, 12, 7, 1]),\n#     (3, 2): (28, [8, 12, 7, 1]),\n#     (3, 3): (32, [4, 8, 12, 7, 1]),\n#     (3, 4): (41, [9, 4, 8, 12, 7, 1])}\ndef diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]:\n    m = len(p)\n    n = len(p[0])\n    q: dict[tuple[int, int], tuple[int, list[int]]] = {}\n    q[(1, 1)] = (p[0][0], [p[0][0]])\n    for j in range(2, n + 1):\n        (k, xs) = q[(1, j-1)]\n        q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs)\n    for i in range(2, m + 1):\n        (k,xs) = q[(i-1,1)]\n        q[(i, 1)] =  (k + p[i-1][0], [p[i-1][0]] + xs)\n    for i in range(2, m + 1):\n        for j in range(2, n + 1):\n            (k1,xs) = q[(i,j-1)]\n            (k2,ys) = q[(i-1,j)]\n            if k1 > k2:\n                q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs)\n            else:\n                q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys)\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('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')\n#    1.92 segundos\n#    >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')\n#    0.65 segundos\n#    >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')\n#    0.00 segundos\n\n# # Verificaci\u00f3n\n# # ============\n\ndef test_caminoMaxSuma() -> None:\n    assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \\\n        [1, 7, 12, 8, 4, 9]\n    assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \\\n        [1, 7, 12, 8, 4, 9]\n    assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \\\n        [1, 7, 12, 8, 4, 9]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_caminoMaxSuma()\n#    Verificado\n<\/pre>\n<p><a name=\"ej6\"><\/a><\/p>\n<h3>6. M\u00e9todo de Her\u00f3n para calcular la ra\u00edz cuadrada<\/h3>\n\n<p>El m\u00e9todo de Her\u00f3n para calcular la ra\u00edz cuadrada de un n\u00famero se basa en las siguientes propiedades:<\/p>\n<ul>\n<li>Si &#92;(y&#92;) es una aproximaci\u00f3n de la ra\u00edz cuadrada de &#92;(x&#92;), entonces<br \/>\n&#92;[&#92;frac{y+&#92;frac{x}{y}}{2}&#92;] es una aproximaci\u00f3n mejor.<\/li>\n<li>El l\u00edmite de la sucesi\u00f3n definida por<br \/>\n&#92;begin{align}<br \/>\n  x_{0}   &amp;= 1 &#92;&#92;<br \/>\n  x_{n+1} &amp;= &#92;frac{x_n+&#92;frac{x}{x_n}}{2}<br \/>\n&#92;end{align}<br \/>\nes la ra\u00edz cuadrada de x.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   raiz :: Double -> Double\n<\/pre>\n<p>tal que <code>raiz x<\/code> es la ra\u00edz cuadrada de <code>x<\/code> calculada usando la propiedad anterior con una aproximaci\u00f3n de 0.00001 y tomando como valor inicial 1. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   raiz 9  ==  3.000000001396984\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 Metodo_de_Heron_para_calcular_la_raiz_cuadrada where\n\nimport Test.QuickCheck\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nraiz :: Double -> Double\nraiz x = raizAux 1\n  where raizAux y | aceptable y = y\n                  | otherwise   = raizAux (mejora y)\n        aceptable y = abs(y*y-x) < 0.00001\n        mejora y    = 0.5*(y+x\/y)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nraiz2 :: Double -> Double\nraiz2 x = until aceptable mejora 1\n  where aceptable y = abs(y*y-x) < 0.00001\n        mejora y    = 0.5*(y+x\/y)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_raiz :: Positive Double -> Bool\nprop_raiz (Positive x) =\n  raiz x ~= sqrt x &&\n  raiz2 x ~= sqrt x\n  where\n    a ~= b = abs (a-b) < 0.001\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_raiz\n--    +++ OK, passed 100 tests.\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    raiz 9 `shouldBe`  3.000000001396984\n  it \"e2\" $\n    raiz2 9 `shouldBe`  3.000000001396984\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0008 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef raiz(x : float) -> float:\n    def aceptable(y: float) -> bool:\n        return abs(y*y-x) < 0.00001\n    def mejora(y: float) -> float:\n        return 0.5*(y+x\/y)\n    def raizAux(y: float) -> float:\n        if aceptable(y):\n            return y\n        return raizAux(mejora(y))\n    return raizAux(1)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef raiz2(x: float) -> float:\n    def aceptable(y: float) -> bool:\n        return abs(y*y-x) < 0.00001\n    def mejora(y: float) -> float:\n        return 0.5*(y+x\/y)\n    y = 1.0\n    while not aceptable(y):\n        y = mejora(y)\n    return y\n\n# Verificaci\u00f3n\n# ============\n\ndef test_raiz() -> None:\n    assert raiz(9)  ==  3.000000001396984\n    assert raiz2(9)  ==  3.000000001396984\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_raiz()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Durante el mes de octubre he publicado en Exercitium las soluciones de los siguientes problemas: 1. La distancia Levenshtein (con programaci\u00f3n din\u00e1mica) 2. Caminos en una ret\u00edcula (con programaci\u00f3n din\u00e1mica) 3. Caminos en una matriz (con programaci\u00f3n din\u00e1mica) 4. M\u00e1xima suma de los caminos en una matriz 5. Camino de m\u00e1xima suma en una matriz&#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\/8042"}],"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=8042"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8042\/revisions"}],"predecessor-version":[{"id":8043,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8042\/revisions\/8043"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=8042"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=8042"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=8042"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}