{"id":8301,"date":"2023-10-19T06:00:48","date_gmt":"2023-10-19T04:00:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8301"},"modified":"2024-05-16T19:39:34","modified_gmt":"2024-05-16T17:39:34","slug":"19-oct-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-oct-23\/","title":{"rendered":"M\u00e1xima suma de los caminos en una matriz"},"content":{"rendered":"

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

\n   (  1  6 11  2 )\n   (  7 12  3  8 )\n   (  3  8  4  9 )\n<\/pre>\n
movi\u00e9ndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:<\/p>\n
\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
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
Definir la funci\u00f3n<\/p>\n
\n   maximaSuma :: Matrix Int -> Int\n<\/pre>\n
tal que maximaSuma m<\/code> es el m\u00e1ximo de las sumas de los caminos en la matriz 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
\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>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\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
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\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(,\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","protected":false},"excerpt":{"rendered":"
Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz ( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) movi\u00e9ndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes: [1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9]…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[581],"tags":[591],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8301"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8301"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8301\/revisions"}],"predecessor-version":[{"id":8556,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8301\/revisions\/8556"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8301"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}