{"id":8294,"date":"2023-10-09T05:09:51","date_gmt":"2023-10-09T03:09:51","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8294"},"modified":"2024-05-16T19:40:35","modified_gmt":"2024-05-16T17:40:35","slug":"09-oct-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/09-oct-23\/","title":{"rendered":"Caminos en una ret\u00edcula (con programaci\u00f3n din\u00e1mica)"},"content":{"rendered":"

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×4 se numera como sigue:<\/p>\n

\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
Definir la funci\u00f3n<\/p>\n
\n   caminos :: (Int,Int) -> [[(Int,Int)]]\n<\/pre>\n
tal que 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
\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>\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 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
<\/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 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(,\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","protected":false},"excerpt":{"rendered":"
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×4 se numera como sigue: |——-+——-+——-+——-| | (1,1) | (1,2) | (1,3) | (1,4) | | (2,1) | (2,2) | (2,3) | (2,4) | | (3,1) | (3,2) | (3,3)…<\/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\/8294"}],"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=8294"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8294\/revisions"}],"predecessor-version":[{"id":8558,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8294\/revisions\/8558"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}