{"id":8277,"date":"2023-09-09T06:00:57","date_gmt":"2023-09-09T04:00:57","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8277"},"modified":"2024-05-17T18:48:53","modified_gmt":"2024-05-17T16:48:53","slug":"09-sep-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/09-sep-23\/","title":{"rendered":"Problema de las jarras (con espacios de estados)"},"content":{"rendered":"<p>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<p>El problema de las jarras (A,B,C) consiste en determinar c\u00f3mo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3XBlqG7\">procedimiento de b\u00fasqueda en anchura<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   jarras :: (Int,Int,Int) -> [[(Int,Int)]]\n<\/pre>\n<p>tal <code>jarras (a,b,c)<\/code> es la lista de las soluciones del problema de las jarras <code>(a,b,c)<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 3 (jarras (4,3,2))\n   [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],\n    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],\n    [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]\n<\/pre>\n<p>La interpretaci\u00f3n [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:<\/p>\n<ul>\n<li>(0,0) se inicia con las dos jarras vac\u00edas,<\/li>\n<li>(4,0) se llena la jarra de 4 con el grifo,<\/li>\n<li>(1,3) se llena la de 3 con la de 4,<\/li>\n<li>(1,0) se vac\u00eda la de 3,<\/li>\n<li>(0,1) se pasa el contenido de la primera a la segunda,<\/li>\n<li>(4,1) se llena la primera con el grifo,<\/li>\n<li>(2,3) se llena la segunda con la primera.<\/li>\n<\/ul>\n<p>Otros ejemplos<\/p>\n<pre lang=\"text\">\n   \u03bb> length (jarras (15,10,5))\n   8\n   \u03bb> map length (jarras (15,10,5))\n   [3,5,5,7,7,7,8,9]\n   \u03bb> jarras (15,10,4)\n   []\n<\/pre>\n<p><!--more--><\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Problema_de_las_jarras where\n\nimport BusquedaEnAnchura (buscaAnchura)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Un problema es una lista de 3 n\u00fameros enteros (a,b,c) tales que a es\n-- la capacidad de la primera jarra, b es la capacidad de la segunda\n-- jarra y c es el n\u00famero de litros que se desea obtener en la primera\n-- jarra.\ntype Problema = (Int,Int,Int)\n\n-- Una configuracion es una lista de dos n\u00fameros. El primero es el\n-- contenido de la primera jarra y el segundo el de la segunda.\ntype Configuracion = (Int,Int)\n\n-- Inicialmente, las dos jarras est\u00e1n vac\u00edas.\nconfiguracionInicial :: Configuracion\nconfiguracionInicial = (0,0)\n\n-- (esConfiguracionFinal p e) se verifica si e es un configuracion final\n-- del problema p.\nesConfiguracionFinal :: Problema -> Configuracion -> Bool\nesConfiguracionFinal (_,_,c) (x,_) = x == c\n\n-- (sucesorasConfiguracion p c) son las sucesoras de la configuraci\u00f3n c\n-- del problema p. Por ejemplo,\n--    sucesorasConfiguracion (4,3,2) (0,0)  ==  [(4,0),(0,3)]\n--    sucesorasConfiguracion (4,3,2) (4,0)  ==  [(4,3),(0,0),(1,3)]\n--    sucesorasConfiguracion (4,3,2) (4,3)  ==  [(0,3),(4,0)]\nsucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion]\nsucesorasConfiguracion (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 > 0, x + y > a] ++\n    [(x-(b-y),b) | x > 0, y < b, x + y > b] ++\n    [(x+y,0) | y > 0, x + y <= a] ++\n    [(0,x+y) | x > 0, x + y <= b]\n\n-- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que\n-- c_1 es la configuraci\u00f3n inicial y, para 2 <= i <= n, c_i es una\n-- sucesora de c_(i-1).\ntype Estado = [Configuracion]\n\n-- inicial es el estado cuyo \u00fanico elemento es la configuraci\u00f3n\n-- inicial.\ninicial :: Estado\ninicial = [configuracionInicial]\n\n-- (esFinal p e) se verifica si e es un estado final; es decir, su\n-- primer elemento es una configuraci\u00f3n final.\nesFinal :: Problema -> Estado -> Bool\nesFinal p (e:_) = esConfiguracionFinal p e\n\n-- (sucesores p e) es la lista de los sucesores del estado e en el\n-- problema p. Por ejemplo,\n--    \u03bb> sucesores (4,3,2) [(0,0)]\n--    [[(4,0),(0,0)],[(0,3),(0,0)]]\n--    \u03bb> sucesores (4,3,2) [(4,0),(0,0)]\n--    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]\n--    \u03bb> sucesores (4,3,2) [(4,3),(4,0),(0,0)]\n--    [[(0,3),(4,3),(4,0),(0,0)]]\nsucesores :: Problema -> Estado -> [Estado]\nsucesores p e@(c:_) =\n    [c':e | c' <- sucesorasConfiguracion p c,\n            c' `notElem` e]\n\njarras :: Problema -> [Estado]\njarras p = map reverse soluciones\n  where\n     soluciones = buscaAnchura (sucesores p) (esFinal p) inicial\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    take 3 (jarras (4,3,2)) `shouldBe`\n    [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],\n     [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],\n     [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]\n  it \"e2\" $\n    length (jarras (15,10,5)) `shouldBe` 8\n  it \"e3\" $\n    map length (jarras (15,10,5)) `shouldBe`\n    [3,5,5,7,7,7,8,9]\n  it \"e4\" $\n    jarras (15,10,4) `shouldBe` []\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0080 seconds\n--    4 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.BusquedaEnAnchura import buscaAnchura\n\n# Un problema es una lista de 3 n\u00fameros enteros (a,b,c) tales que a es\n# la capacidad de la primera jarra, b es la capacidad de la segunda\n# jarra y c es el n\u00famero de litros que se desea obtener en la primera\n# jarra.\nProblema = tuple[int, int, int]\n\n# Una configuracion es una lista de dos n\u00fameros. El primero es el\n# contenido de la primera jarra y el segundo el de la segunda.\nConfiguracion = tuple[int, int]\n\n# Inicialmente, las dos jarras est\u00e1n vac\u00edas.\nconfiguracionInicial: Configuracion = (0,0)\n\n# esConfiguracionFinal(p, e) se verifica si e es un configuracion final\n# del problema p.\ndef esConfiguracionFinal(p: Problema, c: Configuracion) -> bool:\n    return p[2] == c[0]\n\n# sucesorasConfiguracion(p, c) son las sucesoras de la configuraci\u00f3n c\n# del problema p. Por ejemplo,\n#    sucesorasConfiguracion((4,3,2), (0,0))  ==  [(4,0),(0,3)]\n#    sucesorasConfiguracion((4,3,2), (4,0))  ==  [(4,3),(0,0),(1,3)]\n#    sucesorasConfiguracion((4,3,2), (4,3))  ==  [(0,3),(4,0)]\ndef sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]:\n    (a, b, _) = p\n    (x, y) = c\n    r = []\n    if x < a:\n        r.append((a, y))\n    if y < b:\n        r.append((x, b))\n    if x > 0:\n        r.append((0, y))\n    if y > 0:\n        r.append((x, 0))\n    if x < a and y > 0 and x + y > a:\n        r.append((a, y - (a - x)))\n    if x > 0 and y < b and x + y > b:\n        r.append((x - (b - y), b))\n    if y > 0 and x + y <= a:\n        r.append((x + y, 0))\n    if x > 0 and x + y <= b:\n        r.append((0, x + y))\n    return r\n\n# Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que\n# c_1 es la configuraci\u00f3n inicial y, para 2 <= i <= n, c_i es una\n# sucesora de c_(i-1).\nEstado = list[Configuracion]\n\n# inicial es el estado cuyo \u00fanico elemento es la configuraci\u00f3n\n# inicial.\ninicial: Estado = [configuracionInicial]\n\n# esFinal(p, e) se verifica si e es un estado final; es decir, su\n# primer elemento es una configuraci\u00f3n final.\ndef esFinal(p: Problema, e: Estado) -> bool:\n    return esConfiguracionFinal(p, e[0])\n\n# sucesores(p, e) es la lista de los sucesores del estado e en el\n# problema p. Por ejemplo,\n#    \u03bb> sucesores((4,3,2), [(0,0)])\n#    [[(4,0),(0,0)],[(0,3),(0,0)]]\n#    \u03bb> sucesores((4,3,2), [(4,0),(0,0)])\n#    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]\n#    \u03bb> sucesores((4,3,2), [(4,3),(4,0),(0,0)])\n#    [[(0,3),(4,3),(4,0),(0,0)]]\ndef sucesores(p: Problema, e: Estado) -> list[Estado]:\n    return [[c] + e\n            for c in sucesorasConfiguracion(p, e[0])\n            if c not in e]\n\ndef jarras(p: Problema) -> list[Estado]:\n    soluciones = buscaAnchura(lambda e: sucesores(p, e),\n                              lambda e: esFinal(p, e),\n                              inicial)\n    return [list(reversed(e)) for e in soluciones]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_jarras() -> None:\n    assert jarras((4,3,2))[:3] == \\\n        [[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)],\n         [(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)],\n         [(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]]\n    assert len(jarras((15,10,5))) == 8\n    assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9]\n    assert jarras((15,10,4)) == []\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_jarras()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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&#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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[581],"tags":[456],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8277"}],"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=8277"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8277\/revisions"}],"predecessor-version":[{"id":8580,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8277\/revisions\/8580"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8277"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8277"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8277"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}