En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medici\u00f3n, una de A litros de capacidad y otra de B. Tambi\u00e9n se dispone de una bomba que permite llenar las jarras de agua.<\/p>\n
El problema de las jarras<\/strong> (A,B,C) consiste en determinar c\u00f3mo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.<\/p>\n Definir la funci\u00f3n<\/p>\n tal (jarras (a,b,c)) es una soluci\u00f3n del problema de las jarras (a,b,c) con el m\u00ednimo n\u00famero de movimientos, si el problema tiene soluci\u00f3n y Nothing, en caso contrario. Por ejemplo,<\/p>\n La interpretaci\u00f3n de la soluci\u00f3n anterior es<\/p>\n Otros ejemplos:<\/p>\n En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medici\u00f3n, una de A litros de capacidad y otra de B. Tambi\u00e9n se dispone de una bomba que permite llenar las jarras de agua. El problema de las jarras (A,B,C) consiste en determinar c\u00f3mo se puede lograr tener exactamente C litros…<\/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":[353,8,10,27,11,32],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4052"}],"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=4052"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4052\/revisions"}],"predecessor-version":[{"id":4085,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4052\/revisions\/4085"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4052"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4052"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4052"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n jarras :: (Int,Int,Int) -> Maybe [(Int,Int)]\n<\/pre>\n
\n \u03bb> jarras (5,3,4)\n Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]\n<\/pre>\n
\n (0,0) se inicia con las dos jarras vac\u00edas,\n (5,0) se llena la jarra de 5 con el grifo,\n (2,3) se llena la de 3 con la de 5,\n (2,0) se vac\u00eda la de 3,\n (0,2) se pasa el contenido de la primera a la segunda,\n (5,2) se llena la primera con el grifo,\n (4,3) se llena la segunda con la primera.\n<\/pre>\n
\n \u03bb> jarras (3,5,4)\n Just [(0,0),(0,5),(3,2),(0,2),(2,0),(2,5),(3,4)]\n \u03bb> jarras (15,10,5)\n Just [(0,0),(15,0),(5,10)]\n \u03bb> jarras (15,10,4)\n Nothing\n \u03bb> length <$> jarras (181,179,100)\n Just 199\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.Maybe (listToMaybe, isJust)\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 es el n\u00famero\n-- de litros que hay que obtener.\ntype Problema = (Int,Int,Int)\n\n-- Un estado es un par de n\u00fameros. El primero es el contenido de la\n-- jarra de A litros y el segundo el de la de B litros. \ntype Estado = (Int,Int)\n\njarras :: Problema -> Maybe [Estado]\njarras p | null ns = Nothing\n | otherwise = Just (head ns)\n where ns = soluciones p\n\n-- (soluciones p) es la lista de soluciones del problema p. Por ejemplo, \n-- \u03bb> take 2 (soluciones (15,10,5))\n-- [[(0,0),(15,0),(5,10)],[(0,0),(0,10),(15,10),(15,0),(5,10)]]\n-- \u03bb> length (soluciones (15,10,5))\n-- 6\n-- \u03bb> soluciones (15,10,4)\n-- []\nsoluciones :: Problema -> [[Estado]]\nsoluciones p = busca [[inicial]]\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 es el estado inicial\ninicial :: Estado\ninicial = (0,0)\n\n-- (esFinal p e) es verifica si e es un estado final del problema de las\n-- jarras p. Por ejemplo,\n-- esFinal (5,4,3) (3,2) == True\n-- esFinal (5,4,3) (2,3) == True\n-- esFinal (5,4,1) (2,3) == False\nesFinal :: Problema -> Estado -> Bool\nesFinal (_,_,c) (x,y) = x == c || y == c\n\n-- (sucesores p e) es la lista de los sucesores del estado e. Por\n-- ejemplo, \n-- \u03bb> sucesores (7,4,3) (1,2)\n-- [(7,2),(1,4),(0,2),(1,0),(3,0),(0,3)]\n-- \u03bb> sucesores (7,4,3) (6,3)\n-- [(7,3),(6,4),(0,3),(6,0),(7,2),(5,4)]\nsucesores :: Problema -> Estado -> [Estado]\nsucesores (a,b,_) (x,y) =\n [(a,y) | x < a] ++\n [(x,b) | y < b] ++\n [(0,y) | x > 0] ++\n [(x,0) | y > 0] ++\n [(a,y-(a-x)) | x < a, y > a - x] ++\n [(x-(b-y),b) | y < b, x > b - y] ++\n [(x+y,0) | y > 0, x + y <= a] ++ \n [(0,x+y) | x > 0, x + y <= b]\n\n-- La definici\u00f3n de jarras se puede simplificar usando listToMaybe\njarras2 :: Problema -> Maybe [Estado]\njarras2 p = listToMaybe (soluciones p)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"