{"id":2490,"date":"2016-05-26T09:16:30","date_gmt":"2016-05-26T07:16:30","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2490"},"modified":"2016-06-02T06:32:46","modified_gmt":"2016-06-02T04:32:46","slug":"caminos-en-una-reticula","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/caminos-en-una-reticula\/","title":{"rendered":"Caminos en una ret\u00edcula"},"content":{"rendered":"<p>El <strong>problema de los caminos en una ret\u00edcula<\/strong> consiste en, dada una ret\u00edcula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el v\u00e9rtice inferior izquierdo hasta el v\u00e9rtice superior derecho donde los movimientos permitidos son mover hacia el siguiente v\u00e9rtice a la derecha o arriba.<\/p>\n<p>Por ejemplo, en la siguiente ret\u00edcula un posible camino es el indicado en rojo.<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/05\/C.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/05\/C.png?resize=160%2C112\" alt=\"C\" width=\"160\" height=\"112\" class=\"aligncenter size-full wp-image-2493\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/05\/C.png?w=160&amp;ssl=1 160w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/05\/C.png?resize=100%2C70&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/05\/C.png?resize=150%2C105&amp;ssl=1 150w\" sizes=\"(max-width: 160px) 100vw, 160px\" data-recalc-dims=\"1\" \/><\/a><\/p>\n<p>Para representar los caminos se definen los siguientes tipos de datos:<\/p>\n<pre lang=\"text\">\n    data Direccion = D | A deriving (Show, Eq)\n    type Camino = [Direccion]\n<\/pre>\n<p>Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   caminos  :: Int -> Int -> [Camino]\n   nCaminos :: Int -> Int -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(caminos m n) es la lista de los caminos en una ret\u00edcula rectangular con m filas y n columnas. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> caminos 2 2\n     [[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]\n     \u03bb> caminos 1 3\n     [[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]\n     \u03bb> caminos 2 3\n     [[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],\n      [D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]\n<\/pre>\n<ul>\n<li>(nCaminos m n) es el n\u00famero de los caminos en una ret\u00edcula rectangular con m filas y n columnas. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nCaminos 2 2  ==  6\n     nCaminos 1 3  ==  4\n     nCaminos 2 3  ==  10\n     length (show (nCaminos 20000 30000))  ==  14612\n     length (show (nCaminos 30000 20000))  ==  14612\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\n\ndata Direccion = D | A deriving (Show, Eq)\n\ntype Camino = [Direccion]\n\n-- Definici\u00f3n de caminos\n-- =====================\n\ncaminos :: Int -> Int -> [Camino]\ncaminos 0 n = [replicate n A]\ncaminos m 0 = [replicate m D]\ncaminos m n = [A:xs | xs <- caminos m (n-1)] ++\n              [D:xs | xs <- caminos (m-1) n]\n\n-- 1\u00aa definici\u00f3n de nCaminos\n-- =========================\n\nnCaminos1 :: Int -> Int -> Integer\nnCaminos1 m n = genericLength (caminos m n)\n\n-- 2\u00aa definici\u00f3n de nCaminos\n-- =========================\n\nnCaminos2 :: Int -> Int -> Integer\nnCaminos2 0 n = 1\nnCaminos2 m 0 = 1\nnCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n\n\n-- 3\u00aa definici\u00f3n de nCaminos\n-- =========================\n\n-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetici\u00f3n\n-- de m veces la D y n veces la A. Por tanto, su n\u00famero es\n--    (m+n)! \/ m!*n!\n\nnCaminos3 :: Int -> Int -> Integer\nnCaminos3 m n = \n    fact (m+n) `div` (fact m * fact n)\n\nfact :: Int -> Integer\nfact n = product [1..fromIntegral n]\n\n-- 4\u00aa soluci\u00f3n de nCaminos\n-- =======================\n\nnCaminos4 :: Int -> Int -> Integer\nnCaminos4 m n = \n    product [a+1..a+b] `div` product [2..b]\n    where m' = fromIntegral m\n          n' = fromIntegral n\n          a  = max m' n'\n          b  = min m' n'\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> nCaminos1 10 10\n--    184756\n--    (3.50 secs, 656,909,648 bytes)\n--    \u03bb> nCaminos2 10 10\n--    184756\n--    (0.50 secs, 47,330,272 bytes)\n--    \u03bb> nCaminos3 10 10\n--    184756\n--    (0.01 secs, 0 bytes)\n--    \u03bb> nCaminos4 10 10\n--    184756\n--    (0.01 secs, 0 bytes)\n-- \n--    \u03bb> nCaminos2 10 15\n--    3268760\n--    (8.83 secs, 1,142,623,080 bytes)\n--    \u03bb> nCaminos3 10 15\n--    3268760\n--    (0.01 secs, 0 bytes)\n--    \u03bb> nCaminos4 10 15\n--    3268760\n--    (0.00 secs, 0 bytes)\n--\n--    \u03bb> let n = 2*10^4 \n--    (0.01 secs, 0 bytes)\n--    \u03bb> length (show (nCaminos3 n n))\n--    12039\n--    (8.41 secs, 2,369,767,480 bytes)\n--    \u03bb> length (show (nCaminos4 n n))\n--    12039\n--    (2.98 secs, 833,386,648 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El problema de los caminos en una ret\u00edcula consiste en, dada una ret\u00edcula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el v\u00e9rtice inferior izquierdo hasta el v\u00e9rtice superior derecho donde los movimientos permitidos son mover hacia el siguiente v\u00e9rtice a la derecha o arriba. Por ejemplo, en la&#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":[4],"tags":[8,30,183,258,157,6,19],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2490"}],"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=2490"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2490\/revisions"}],"predecessor-version":[{"id":2519,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2490\/revisions\/2519"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2490"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2490"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2490"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}