{"id":8265,"date":"2023-08-14T06:00:24","date_gmt":"2023-08-14T04:00:24","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8265"},"modified":"2023-08-03T17:21:27","modified_gmt":"2023-08-03T15:21:27","slug":"14-ago-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/14-ago-23\/","title":{"rendered":"El problema del granjero mediante b\u00fasqueda en espacio de estado"},"content":{"rendered":"<p>Un granjero est\u00e1 parado en un lado del r\u00edo y con \u00e9l tiene un  una cabra y una repollo. En el r\u00edo hay un barco peque\u00f1o. El  desea cruzar el r\u00edo con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un art\u00edculo. Si deja la cabra con la repollo sola en un lado del r\u00edo la cabra comer\u00e1 la repollo. Si deja el lobo y la cabra en un lado, el lobo se comer\u00e1 a la cabra. \u00bfC\u00f3mo puede cruzar el granjero el r\u00edo con los tres art\u00edculos, sin que ninguno se coma al otro?<\/p>\n<p>Para representar el problema se definen los siguientes tipos de dato:<\/p>\n<ul>\n<li><code>Orilla<\/code> con dos constructores (<code>I<\/code> y <code>D<\/code>) que representan las orillas izquierda y derecha, respectivamente.<\/li>\n<li><code>Estado<\/code> que es una tupla que representa en qu\u00e9 orilla se encuentra cada uno de los elementos (granjero, lobo, cabra, repollo). Por ejemplo, <code>(I,D,D,I)<\/code> representa que el granjero est\u00e1 en la izquierda, que el lobo est\u00e1 en la derecha, que la cabra est\u00e1 en la derecha y el repollo est\u00e1 en la izquierda.<\/li>\n<\/ul>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3NPI4qV\">procedimiento de b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   granjero :: [[Estado]]\n<\/pre>\n<p>tal que <code>granjero<\/code> son las soluciones del problema del granjero mediante el patr\u00f3n de b\u00fasqueda en espacio de estados. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> head granjero\n   [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I),\n    (I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)]\n   \u03bb> length granjero\n   2\n<\/pre>\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 BEE_El_problema_del_granjero where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ndata Orilla = I | D\n  deriving (Eq, Show)\n\ntype Estado = (Orilla,Orilla,Orilla,Orilla)\n\n-- (seguro e) se verifica si el estado e es seguro; es decir, que no\n-- puede estar en una orilla el lobo con la cabra sin el granjero ni la\n-- cabra con el repollo sin el granjero. Por ejemplo,\n--    seguro (I,D,D,I)  ==  False\n--    seguro (D,D,D,I)  ==  True\n--    seguro (D,D,I,I)  ==  False\n--    seguro (I,D,I,I)  ==  True\nseguro :: Estado -> Bool\nseguro (g,l,c,r) = not (g \/= c && (c == l || c == r))\n\n-- (opuesta x) es la opuesta de la orilla x. Por ejemplo\n--    opuesta I = D\nopuesta :: Orilla -> Orilla\nopuesta I = D\nopuesta D = I\n\n-- (sucesoresE e) es la lista de los sucesores seguros del estado e. Por\n-- ejemplo,\n--    sucesoresE (I,I,I,I)  ==  [(D,I,D,I)]\n--    sucesoresE (D,I,D,I)  ==  [(I,I,D,I),(I,I,I,I)]\nsucesoresE :: Estado -> [Estado]\nsucesoresE e = [mov e | mov <- [m1,m2,m3,m4], seguro (mov e)]\n  where m1 (g,l,c,r) = (opuesta g, l, c, r)\n        m2 (g,l,c,r) = (opuesta g, opuesta l, c, r)\n        m3 (g,l,c,r) = (opuesta g, l, opuesta c, r)\n        m4 (g,l,c,r) = (opuesta g, l, c, opuesta r)\n\n-- Nodo es el tipo de los nodos del espacio de b\u00fasqueda, donde un nodo\n-- es una lista de estados\n--    [e_n, ..., e_2, e_1]\n-- tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un\n-- sucesor de e_(i-1).\nnewtype Nodo = Nodo [Estado]\n  deriving (Eq, Show)\n\n-- inicial es el nodo inicial en el que todos est\u00e1n en la orilla\n-- izquierda.\ninicial :: Nodo\ninicial = Nodo [(I,I,I,I)]\n\n-- (esFinal n) se verifica si n es un nodo final; es decir, su primer\n-- elemento es el estado final. Por ejemplo,\n--    esFinal (Nodo [(D,D,D,D),(I,I,I,I)])  ==  True\n--    esFinal (Nodo [(I,I,D,I),(I,I,I,I)])  ==  False\nesFinal :: Nodo -> Bool\nesFinal (Nodo (n:_)) = n == (D,D,D,D)\n\n-- (sucesores n) es la lista de los sucesores del nodo n. Por ejemplo,\n--    \u03bb> sucesores (Nodo [(I,I,D,I),(D,I,D,I),(I,I,I,I)])\n--    [Nodo [(D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)],\n--     Nodo [(D,I,D,D),(I,I,D,I),(D,I,D,I),(I,I,I,I)]]\nsucesores :: Nodo -> [Nodo]\nsucesores (Nodo n@(e:es)) =\n  [Nodo (e':n) | e' <- sucesoresE e, e' `notElem` es]\n\ngranjero :: [[Estado]]\ngranjero =\n  [reverse es | (Nodo es) <- buscaProfundidad sucesores esFinal inicial]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    head granjero `shouldBe`\n    [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I),\n     (I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)]\n  it \"e2\" $\n    length granjero `shouldBe` 2\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0008 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom enum import Enum\n\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\n\nclass Orilla(Enum):\n    I = 0\n    D = 1\n\n    def __repr__(self) -> str:\n        return self.name\n\nI = Orilla.I\nD = Orilla.D\n\nEstado = tuple[Orilla, Orilla, Orilla, Orilla]\n\n# seguro(e) se verifica si el estado e es seguro; es decir, que no\n# puede estar en una orilla el lobo con la cabra sin el granjero ni la\n# cabra con el repollo sin el granjero. Por ejemplo,\n#    seguro((I,D,D,I))  ==  False\n#    seguro((D,D,D,I))  ==  True\n#    seguro((D,D,I,I))  ==  False\n#    seguro((I,D,I,I))  ==  True\ndef seguro(e: Estado) -> bool:\n    (g,l,c,r) = e\n    return not (g != c and c in {l, r})\n\n# (opuesta x) es la opuesta de la orilla x. Por ejemplo\n#    opuesta(I) == D\ndef opuesta(o: Orilla) -> Orilla:\n    if o == I:\n        return D\n    return I\n\n# sucesoresE(e) es la lista de los sucesores seguros del estado e. Por\n# ejemplo,\n#    sucesoresE((I,I,I,I))  ==  [(D,I,D,I)]\n#    sucesoresE((D,I,D,I))  ==  [(I,I,D,I),(I,I,I,I)]\ndef sucesoresE(e: Estado) -> list[Estado]:\n    def mov(n: int, e: Estado) -> Estado:\n        (g,l,c,r) = e\n        if n == 1:\n            return (opuesta(g), l, c, r)\n        if n == 2:\n            return (opuesta(g), opuesta(l), c, r)\n        if n == 3:\n            return (opuesta(g), l, opuesta(c), r)\n        return (opuesta(g), l, c, opuesta(r))\n    return [mov(n, e) for n in range(1, 5) if seguro(mov(n, e))]\n\n# Nodo es el tipo de los nodos del espacio de b\u00fasqueda, donde un nodo\n# es una lista de estados\n#    [e_n, ..., e_2, e_1]\n# tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un\n# sucesor de e_(i-1).\nNodo = list[Estado]\n\n# inicial es el nodo inicial en el que todos est\u00e1n en la orilla\n# izquierda.\ninicial: Nodo = [(I,I,I,I)]\n\n# esFinal(n) se verifica si n es un nodo final; es decir, su primer\n# elemento es el estado final. Por ejemplo,\n#    esFinal([(D,D,D,D),(I,I,I,I)])  ==  True\n#    esFinal([(I,I,D,I),(I,I,I,I)])  ==  False\ndef esFinal(n: Nodo) -> bool:\n    return n[0] == (D,D,D,D)\n\n# sucesores(n) es la lista de los sucesores del nodo n. Por ejemplo,\n#    >>> sucesores([(I,I,D,I),(D,I,D,I),(I,I,I,I)])\n#    [[(D, D, D, I), (I, I, D, I), (D, I, D, I), (I, I, I, I)],\n#     [(D, I, D, D), (I, I, D, I), (D, I, D, I), (I, I, I, I)]]\ndef sucesores(n: Nodo) -> list[Nodo]:\n    e, *es = n\n    return [[e1] + n for e1 in sucesoresE(e) if e1 not in es]\n\ndef granjero() -> list[list[Estado]]:\n    return [list(reversed(es)) for es in buscaProfundidad(sucesores, esFinal, inicial)]\n\n# # Verificaci\u00f3n\n# # ============\n\ndef test_granjero() -> None:\n    assert granjero() == \\\n        [[(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,I,D,D),(I,I,I,D),(D,D,I,D),(I,D,I,D),(D,D,D,D)],\n         [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I),(I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_granjero()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Un granjero est\u00e1 parado en un lado del r\u00edo y con \u00e9l tiene un una cabra y una repollo. En el r\u00edo hay un barco peque\u00f1o. El desea cruzar el r\u00edo con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un art\u00edculo. Si deja la cabra&#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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8265"}],"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=8265"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8265\/revisions"}],"predecessor-version":[{"id":8266,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8265\/revisions\/8266"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8265"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8265"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8265"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}