{"id":8313,"date":"2023-10-24T06:00:19","date_gmt":"2023-10-24T04:00:19","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8313"},"modified":"2024-05-16T19:39:03","modified_gmt":"2024-05-16T17:39:03","slug":"24-oct-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/24-oct-23\/","title":{"rendered":"Camino de m\u00e1xima suma 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   caminoMaxSuma :: Matrix Int -> [Int]\n<\/pre>\n
tal que caminoMaxSuma m<\/code> es un camino de m\u00e1xima suma 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 la derecha. Por ejemplo,<\/p>\n
\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>\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 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
<\/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 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","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\/8313"}],"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=8313"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8313\/revisions"}],"predecessor-version":[{"id":8555,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8313\/revisions\/8555"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}