{"id":4097,"date":"2018-05-23T06:00:13","date_gmt":"2018-05-23T04:00:13","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4097"},"modified":"2018-05-30T06:11:12","modified_gmt":"2018-05-30T04:11:12","slug":"problema-de-las-3-jarras","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/problema-de-las-3-jarras\/","title":{"rendered":"Problema de las 3 jarras"},"content":{"rendered":"<p>En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor est\u00e1 llena y las otras dos vac\u00edas. Queremos, trasvasando adecuadamente el l\u00edquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   solucionesTresJarras :: Problema -> [[Estado]]\n   tresJarras :: Problema -> Maybe [Estado]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,  <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> mapM_ print (solucionesTresJarras (4,2,1))\n     [(4,0,0),(2,2,0)]\n     [(4,0,0),(3,0,1),(1,2,1),(2,2,0)]\n     [(4,0,0),(3,0,1),(3,1,0),(2,2,0)]\n     [(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]\n     [(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]\n     \u03bb> mapM_ print (solucionesTresJarras (8,6,2))\n     [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]\n     [(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]\n     [(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]\n     [(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]\n     [(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]\n     [(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]\n     [(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]\n     [(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]\n     \u03bb> length (solucionesTresJarras (8,5,3))\n     16\n     \u03bb> head (solucionesTresJarras (8,5,3))\n     [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]\n     \u03bb> length (solucionesTresJarras (8,6,5))\n     0\n<\/pre>\n<ul>\n<li>(tresJarras p) es una soluci\u00f3n del problema de las tres jarras p con el m\u00ednimo m\u00ednimo n\u00famero de trasvase, si p tiene soluci\u00f3n y Nothing, en caso contrario. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> tresJarras (4,2,1)\n     Just [(4,0,0),(2,2,0)]\n     \u03bb> tresJarras (8,6,2)\n     Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]\n     \u03bb> tresJarras (8,5,3)\n     Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]\n     \u03bb> tresJarras (8,6,5)\n     Nothing\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Maybe (listToMaybe)\n\n-- Para simplificar la notaci\u00f3n se definen los tipos Problema y Estado\n-- como sigue.\n\n-- Un problema es una terna de n\u00fameros. El primero es la capacidad de la\n-- primera jarra, el segundo el de la segunda y el tercero el de la\n-- tercera.\ntype Problema = (Int,Int,Int)\n\n-- Un estado es una terna de n\u00fameros. El primero es el contenido de la\n-- jarra de A litros, el segundo el de la de B litros y el tercero el de\n-- la de C litros.\ntype Estado = (Int,Int,Int)\n\nsolucionesTresJarras :: Problema -> [[Estado]]\nsolucionesTresJarras p = busca [[inicial p]]\n  where\n    busca []        = []\n    busca ((e:es):ns)  \n      | esFinal p e = reverse (e:es) : busca ns\n      | otherwise   = busca (ns ++ [e1:e:es | e1 <- sucesores p e\n                                            , e1 `notElem` es])\n\n-- (inicial p) es el estado inicial del problema p. Por ejemplo, \n--    inicial (8,5,3)  ==  (8,0,0)\ninicial :: Problema -> Estado\ninicial (a,_,_) = (a,0,0)\n\n-- (esFinal p e) es verifica si e es un estado final del problema de las\n-- tres jarras p. Por ejemplo,\n--    esFinal (8,5,3) (4,4,0)  ==  True\n--    esFinal (8,5,3) (4,0,4)  ==  False\nesFinal :: Problema -> Estado -> Bool\nesFinal (a,_,_) (x,y,z) =\n  x == y && x + y == a\n\n-- (sucesores p e) es la lista de los sucesores del estado e en el\n-- problema de las tres jarras p. Por ejemplo, \n--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]\n--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]\nsucesores :: Problema -> Estado -> [Estado]\nsucesores (a,b,c) (x,y,z) =\n     [(x-ab,y+ab,z)    | let ab = min x (b-y), ab > 0]\n  ++ [(x-ac,y   ,z+ac) | let ac = min x (c-z), ac > 0]\n  ++ [(x+ba,y-ba,z)    | let ba = min y (a-x), ba > 0]\n  ++ [(x   ,y-bc,z+bc) | let bc = min y (c-z), bc > 0]\n  ++ [(x+ca,y   ,z-ca) | let ca = min z (a-x), ca > 0]\n  ++ [(x   ,y+cb,z-cb) | let cb = min z (b-y), cb > 0]\n  \ntresJarras :: Problema -> Maybe [Estado]\ntresJarras p = listToMaybe (solucionesTresJarras p)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor est\u00e1 llena y las otras dos vac\u00edas. Queremos, trasvasando adecuadamente el l\u00edquido entre las jarras, repartir por igual el contenido inicial entre&#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":[8,27,6,32],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4097"}],"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=4097"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4097\/revisions"}],"predecessor-version":[{"id":4129,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4097\/revisions\/4129"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4097"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4097"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4097"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}