{"id":6614,"date":"2022-02-15T08:41:37","date_gmt":"2022-02-15T06:41:37","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6614"},"modified":"2022-02-23T19:09:17","modified_gmt":"2022-02-23T17:09:17","slug":"maxima-suma-de-caminos-en-un-triangulo","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maxima-suma-de-caminos-en-un-triangulo\/","title":{"rendered":"M\u00e1xima suma de caminos en un tri\u00e1ngulo"},"content":{"rendered":"<p>Los tri\u00e1ngulos se pueden representar mediante listas de listas. Por ejemplo, el tri\u00e1ngulo<\/p>\n<pre lang=\"text\">\n      3\n     7 4\n    2 4 6\n   8 5 9 3\n<\/pre>\n<p>se reperesenta por<\/p>\n<pre lang=\"text\">\n   [[3],[7,4],[2,4,6],[8,5,9,3]]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maximaSuma :: [[Integer]] -> Integer\n<\/pre>\n<p>tal que (maximaSuma xss) es el m\u00e1ximo de las sumas de los elementos de los caminos en el tri\u00e1ngulo xss 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<pre lang=\"text\">\n   maximaSuma [[3],[7,4]]                    ==  10\n   maximaSuma [[3],[7,4],[2,4,6]]            ==  14\n   maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]]  ==  23\n   maximaSuma [[n..n+n] | n <- [0..100]]     ==  10100\n   maximaSuma [[n..n+n] | n <- [0..1000]]    ==  1001000\n   maximaSuma [[n..n+n] | n <- [0..2000]]    ==  4002000\n   maximaSuma [[n..n+n] | n <- [0..3000]]    ==  9003000\n   maximaSuma [[n..n+n] | n <- [0..4000]]    ==  16004000\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (tails)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma1 :: [[Integer]] -> Integer\nmaximaSuma1 xss =\n  maximum [sum ys | ys <- caminos xss]\n\ncaminos :: [[Integer]] -> [[Integer]]\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-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma2 :: [[Integer]] -> Integer\nmaximaSuma2 xss = maximum (map sum (caminos xss))\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma3 :: [[Integer]] -> Integer\nmaximaSuma3 = maximum . map sum . caminos\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma4 :: [[Integer]] -> Integer\nmaximaSuma4 []    = 0\nmaximaSuma4 [[x]] = x\nmaximaSuma4 ([x]:[y1,y2]:zs) =\n  x + max (maximaSuma4 ([y1] : map init zs))\n          (maximaSuma4 ([y2] : map tail zs))\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma5 :: [[Integer]] -> Integer\nmaximaSuma5 xss = head (foldr1 g xss)\n  where\n    f x y z = x + max y z\n    g xs ys = zipWith3 f xs ys (tail ys)\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma6 :: [[Integer]] -> Integer\nmaximaSuma6 xss = head (foldr1 aux xss)\n  where aux a b = zipWith (+) a (zipWith max b (tail b))\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma7 :: [[Integer]] -> Integer\nmaximaSuma7 xss = head (foldr (flip f) (last xss) (init xss))\n  where f = zipWith ((+) . maximum . take 2) . tails\n\n-- 8\u00aa soluci\u00f3n\n-- ===========\n\nmaximaSuma8 :: [[Integer]] -> Integer\nmaximaSuma8 = head . foldr1 aux\n  where\n    aux [] _              = []\n    aux (x:xs) (y0:y1:ys) = x + max y0 y1 : aux xs (y1:ys)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- Para la comparaciones se usar\u00e1 la siguiente funci\u00f3n que construye un\n-- tri\u00e1ngulo de la altura dada. Por ejemplo,\n--    triangulo 2  ==  [[0],[1,2]]\n--    triangulo 3  ==  [[0],[1,2],[2,3,4]]\n--    triangulo 4  ==  [[0],[1,2],[2,3,4],[3,4,5,6]]\ntriangulo :: Integer -> [[Integer]]\ntriangulo n = [[k..k+k] | k <- [0..n-1]]\n\n-- La comparaci\u00f3n es\n--    (1.97 secs, 876,483,056 bytes)\n--    \u03bb> maximaSuma1 (triangulo 19)\n--    342\n--    (2.37 secs, 1,833,637,824 bytes)\n--    \u03bb> maximaSuma2 (triangulo 19)\n--    342\n--    (2.55 secs, 1,804,276,472 bytes)\n--    \u03bb> maximaSuma3 (triangulo 19)\n--    342\n--    (2.57 secs, 1,804,275,320 bytes)\n--    \u03bb> maximaSuma4 (triangulo 19)\n--    342\n--    (0.28 secs, 245,469,384 bytes)\n--    \u03bb> maximaSuma5 (triangulo 19)\n--    342\n--    (0.01 secs, 153,272 bytes)\n--    \u03bb> maximaSuma6 (triangulo 19)\n--    342\n--    (0.01 secs, 161,360 bytes)\n--    \u03bb> maximaSuma7 (triangulo 19)\n--    342\n--    (0.01 secs, 187,456 bytes)\n--    \u03bb> maximaSuma8 (triangulo 19)\n--    342\n--    (0.01 secs, 191,160 bytes)\n--\n--    \u03bb> maximaSuma4 (triangulo 22)\n--    462\n--    (2.30 secs, 1,963,037,888 bytes)\n--    \u03bb> maximaSuma5 (triangulo 22)\n--    462\n--    (0.00 secs, 173,512 bytes)\n--    \u03bb> maximaSuma6 (triangulo 22)\n--    462\n--    (0.01 secs, 182,904 bytes)\n--    \u03bb> maximaSuma7 (triangulo 22)\n--    462\n--    (0.01 secs, 216,560 bytes)\n--    \u03bb> maximaSuma8 (triangulo 22)\n--    462\n--    (0.01 secs, 224,160 bytes)\n--\n--    \u03bb> maximaSuma5 (triangulo 3000)\n--    8997000\n--    (2.25 secs, 2,059,784,792 bytes)\n--    \u03bb> maximaSuma6 (triangulo 3000)\n--    8997000\n--    (2.15 secs, 2,404,239,896 bytes)\n--    \u03bb> maximaSuma7 (triangulo 3000)\n--    8997000\n--    (1.53 secs, 2,612,659,504 bytes)\n--    \u03bb> maximaSuma8 (triangulo 3000)\n--    8997000\n--    (3.47 secs, 3,520,910,256 bytes)\n--\n--    \u03bb> maximaSuma7 (triangulo 4000)\n--    15996000\n--    (3.12 secs, 4,634,841,200 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Maxima_suma_de_caminos_en_un_triangulo.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 reperesenta por [[3],[7,4],[2,4,6],[8,5,9,3]] Definir la funci\u00f3n maximaSuma :: [[Integer]] -> Integer tal que (maximaSuma xss) es el m\u00e1ximo de las sumas de los elementos de los caminos en el tri\u00e1ngulo xss&#8230;<\/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":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_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":[2],"tags":[8,498,11,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6614"}],"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=6614"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6614\/revisions"}],"predecessor-version":[{"id":6702,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6614\/revisions\/6702"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6614"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6614"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6614"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}