{"id":3517,"date":"2017-12-13T06:00:27","date_gmt":"2017-12-13T04:00:27","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3517"},"modified":"2017-12-20T07:04:32","modified_gmt":"2017-12-20T05:04:32","slug":"arbol-de-recorridos-del-autobus","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arbol-de-recorridos-del-autobus\/","title":{"rendered":"Bosque de recorridos del autob\u00fas"},"content":{"rendered":"<p>En la librer\u00eda <a href=\"http:\/\/bit.ly\/2mLEVg4\">Data.Tree<\/a> se definen los \u00e1rboles y los bosques como sigue<\/p>\n<pre lang=\"text\">\n   data Tree a   = Node a (Forest a)\n   type Forest a = [Tree a]\n<\/pre>\n<p>Se pueden definir \u00e1rboles. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []]\n   ejArbol2 = Node 8 [Node 4 []]\n<\/pre>\n<p>Tambi\u00e9n se pueden definir bosques. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ejBosque = [ejArbol1, ejArbol2]\n<\/pre>\n<p>Se pueden dibujar los bosques con la funci\u00f3n drawForest. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> putStrLn (drawForest (map (fmap show) ejBosque))\n   3\n   |\n   +- 5\n   |  |\n   |  `- 9\n   |\n   `- 7\n   \n   8\n   |\n   `- 4\n<\/pre>\n<p>Usando la notaci\u00f3n de los ejercicios anteriores para las subidas y bajadas en el autob\u00fas, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   bosqueRecorridos :: Int -> Int -> Forest (Int,Int)\n<\/pre>\n<p>tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autob\u00fas de capacidad n y usando m paradas. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))\n   (0,0)\n   |\n   +- (0,0)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  `- (2,0)\n   |\n   +- (1,0)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  `- (2,1)\n   |\n   `- (2,0)\n      |\n      +- (0,0)\n      |\n      +- (0,1)\n      |\n      +- (1,1)\n      |\n      +- (0,2)\n      |\n      +- (1,2)\n      |\n      `- (2,2)\n   \n   (1,0)\n   |\n   +- (0,0)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  `- (2,1)\n   |\n   +- (1,0)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  +- (0,2)\n   |  |\n   |  +- (1,2)\n   |  |\n   |  `- (2,2)\n   |\n   +- (0,1)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  `- (2,0)\n   |\n   +- (1,1)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  `- (2,1)\n   |\n   `- (2,1)\n      |\n      +- (0,0)\n      |\n      +- (0,1)\n      |\n      +- (1,1)\n      |\n      +- (0,2)\n      |\n      +- (1,2)\n      |\n      `- (2,2)\n   \n   (2,0)\n   |\n   +- (0,0)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  +- (0,2)\n   |  |\n   |  +- (1,2)\n   |  |\n   |  `- (2,2)\n   |\n   +- (0,1)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  `- (2,1)\n   |\n   +- (1,1)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  +- (0,2)\n   |  |\n   |  +- (1,2)\n   |  |\n   |  `- (2,2)\n   |\n   +- (0,2)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  `- (2,0)\n   |\n   +- (1,2)\n   |  |\n   |  +- (0,0)\n   |  |\n   |  +- (1,0)\n   |  |\n   |  +- (0,1)\n   |  |\n   |  +- (1,1)\n   |  |\n   |  `- (2,1)\n   |\n   `- (2,2)\n      |\n      +- (0,0)\n      |\n      +- (0,1)\n      |\n      +- (1,1)\n      |\n      +- (0,2)\n      |\n      +- (1,2)\n      |\n      `- (2,2)\n<\/pre>\n<p>en donde la \u00faltima rama representa el recorrido [(2,0),(2,2),(2,2)].<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Tree\n\nbosqueRecorridos :: Int -> Int -> Forest (Int, Int)\nbosqueRecorridos c p = aux p 0\n  where aux 0 _ = []\n        aux p' a = [Node (s,b) (aux (p'-1) (a+s-b))\n                   | b <- [0..a]\n                   , s <- [0..c-a+b]]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la librer\u00eda Data.Tree se definen los \u00e1rboles y los bosques como sigue data Tree a = Node a (Forest a) type Forest a = [Tree a] Se pueden definir \u00e1rboles. Por ejemplo, ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []] ejArbol2 = Node 8 [Node 4 []] Tambi\u00e9n se pueden&#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":[7],"tags":[269,8,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3517"}],"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=3517"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3517\/revisions"}],"predecessor-version":[{"id":3549,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3517\/revisions\/3549"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}