{"id":8299,"date":"2023-10-14T06:00:07","date_gmt":"2023-10-14T04:00:07","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8299"},"modified":"2024-05-16T19:40:06","modified_gmt":"2024-05-16T17:40:06","slug":"14-oct-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/14-oct-23\/","title":{"rendered":"Caminos en una matriz (con programaci\u00f3n din\u00e1mica)"},"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 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
Definir la funci\u00f3n<\/p>\n
\n   caminos :: Matrix Int -> [[Int]]\n<\/pre>\n
tal que caminos m<\/code> es la lista de los caminos en la matriz 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
\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>\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 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
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\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(,\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","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 abajo, son los siguientes: [1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,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\/8299"}],"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=8299"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8299\/revisions"}],"predecessor-version":[{"id":8557,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8299\/revisions\/8557"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8299"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8299"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8299"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}