{"id":8531,"date":"2024-04-04T18:27:44","date_gmt":"2024-04-04T16:27:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8531"},"modified":"2024-04-04T18:27:44","modified_gmt":"2024-04-04T16:27:44","slug":"04-abr-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-abr-24\/","title":{"rendered":"Caminos en un tri\u00e1ngulo"},"content":{"rendered":"

Los tri\u00e1ngulos se pueden representar mediante listas de listas. Por ejemplo, el tri\u00e1ngulo<\/p>\n

\n      3\n     7 4\n    2 4 6\n   8 5 9 3\n<\/pre>\n
se representa por<\/p>\n
\n   [[3],[7,4],[2,4,6],[8,5,9,3]]\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   caminos :: [[a]] -> [[a]]\n<\/pre>\n
tal que (caminos xss) es la lista de los caminos en el tri\u00e1ngulo  donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de  sus dos elementos adyacentes en la fila siguiente y terminan en la \u00faltima fila. Por ejemplo,<\/p>\n
\n   \u03bb> caminos [[3],[7,4]]\n   [[3,7],[3,4]]\n   \u03bb> caminos [[3],[7,4],[2,4,6]]\n   [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]\n   \u03bb> caminos [[3],[7,4],[2,4,6],[8,5,9,3]]\n   [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]\n<\/pre>\n
<\/p>\n
<\/a><\/p>\n
1. Soluciones en Haskell<\/h2>\n
\nmodule Caminos_en_un_triangulo where\n\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ncaminos :: [[a]] -> [[a]]\ncaminos []    = [[]]\ncaminos [[x]] = [[x]]\ncaminos ([x]:[y1,y2]:zs) =\n  [x:y1:us | (_:us) <- caminos ([y1] : map init zs)] ++\n  [x:y2:vs | (_:vs) <- caminos ([y2] : map tail zs)]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    caminos [[3],[7,4]] `shouldBe`\n    [[3,7],[3,4]]\n  it \"e2\" $\n    caminos [[3],[7,4],[2,4,6]] `shouldBe`\n    [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]\n  it \"e3\" $\n    caminos [[3],[7,4],[2,4,6],[8,5,9,3]] `shouldBe`\n    [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    3 examples, 0 failures\n<\/pre>\n
<\/a><\/p>\n
2. Soluciones en Python<\/h2>\n
\nfrom typing import TypeVar\n\nA = TypeVar('A')\n\ndef caminos(xss: list[list[A]]) -> list[list[A]]:\n    if not xss:\n        return [[]]\n    if len(xss) == 1:\n        return xss\n    x = xss[0][0]\n    y1 = xss[1][0]\n    y2 = xss[1][1]\n    zss = xss[2:]\n    return [[x, y1] + us for _, *us in caminos([[y1]] + [zs[:-1] for zs in zss])] + \\\n           [[x, y2] + us for _, *us in caminos([[y2]] + [zs[1:] for zs in zss])]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_caminos() -> None:\n    assert caminos([[3],[7,4]]) == \\\n        [[3,7],[3,4]]\n    assert caminos([[3],[7,4],[2,4,6]]) == \\\n        [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]\n    assert caminos([[3],[7,4],[2,4,6],[8,5,9,3]]) == \\\n        [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_caminos()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Los tri\u00e1ngulos se pueden representar mediante listas de listas. Por ejemplo, el tri\u00e1ngulo 3 7 4 2 4 6 8 5 9 3 se representa por [[3],[7,4],[2,4,6],[8,5,9,3]] Definir la funci\u00f3n caminos :: [[a]] -> [[a]] tal que (caminos xss) es la lista de los caminos en el tri\u00e1ngulo donde los caminos comienzan en el elemento…<\/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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8531"}],"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=8531"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8531\/revisions"}],"predecessor-version":[{"id":8532,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8531\/revisions\/8532"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}