{"id":8012,"date":"2023-09-03T06:05:17","date_gmt":"2023-09-03T04:05:17","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=8012"},"modified":"2023-09-02T19:47:24","modified_gmt":"2023-09-02T17:47:24","slug":"03-sep-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/03-sep-23\/","title":{"rendered":"El mes en Exercitium (Ejercicios con Haskell y Python, septiembre de 2023)"},"content":{"rendered":"<p>Este mes he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. B\u00fasqueda en escalada<\/a><\/li>\n<li><a href=\"#ej2\">2. Problema de las monedas por b\u00fasqueda en escalada<\/a><\/li>\n<li><a href=\"#ej3\">3. El algoritmo de Prim del \u00e1rbol de expansi\u00f3n m\u00ednimo por escalada<\/a><\/li>\n<li><a href=\"#ej4\">4. El problema del granjero mediante b\u00fasqueda en espacio de estado<\/a><\/li>\n<li><a href=\"#ej5\">5. El problema de las fichas mediante b\u00fasqueda en espacio de estado<\/a><\/li>\n<li><a href=\"#ej6\">6. El problema del calendario mediante b\u00fasqueda en espacio de estado<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. B\u00fasqueda en escalada<\/h3>\n<p>En la b\u00fasqueda en escalada se supone que los estados est\u00e1n  mediante una funci\u00f3n, la heur\u00edstica, que es una estimaci\u00f3n de su coste para llegar a un estado final.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]\n<\/pre>\n<p>tal que <code>(buscaEscalada s o e)<\/code> es la lista de soluciones del problema de espacio de estado definido por la funci\u00f3n sucesores <code>s<\/code>, el objetivo <code>o<\/code> y estado inicial <code>e<\/code>, obtenidas buscando en escalada.<\/p>\n<p><strong>Nota:<\/strong> La b\u00fasqueda en escalada se aplica en el <a href=\"https:\/\/bit.ly\/3OfjM8Z\">problema de las monedas<\/a>.<\/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 BusquedaEnEscalada (buscaEscalada)  where\n\nimport TAD.ColaDePrioridad (esVacia, inserta, primero, vacia)\n\nbuscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]\nbuscaEscalada sucesores esFinal x = busca' (inserta x vacia) where\n  busca' c\n    | esVacia c           = []\n    | esFinal (primero c) = [primero c]\n    | otherwise           = busca' (foldr inserta vacia (sucesores (primero c)))\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\nfrom abc import abstractmethod\nfrom functools import reduce\nfrom typing import Callable, Optional, Protocol, TypeVar\n\nfrom src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero,\n                                     vacia)\n\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\ndef buscaEscalada(sucesores: Callable[[A], list[A]],\n                  esFinal: Callable[[A], bool],\n                  inicial: A) -> Optional[A]:\n    c: CPrioridad[A] = inserta(inicial, vacia())\n\n    while not esVacia(c):\n        x = primero(c)\n        if esFinal(x):\n            return x\n\n        c = reduce(lambda x, y: inserta(y, x), sucesores(x), vacia())\n\n    return None\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Problema de las monedas por b\u00fasqueda en escalada<\/h3>\n<p>El problema del cambio de monedas consiste en determinar  conseguir una cantidad usando el menor n\u00famero de monedas disponibles. Se supone que se posee un n\u00famero ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como m\u00ednimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).<\/p>\n<p>En la representaci\u00f3n se usar\u00e1n los siguientes tipos:<\/p>\n<ul>\n<li><code>Moneda<\/code>, que es un n\u00famero entero representado el valor de la moneda<\/li>\n<li><code>Solucion<\/code>, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista m\u00e1s corta con la misma suma.<\/li>\n<\/ul>\n<p>Usando la <a href=\"https:\/\/bit.ly\/3Kk4A99\">b\u00fasqueda en escalada<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   cambio :: Int -> Solucion\n<\/pre>\n<p>tal que <code>(cambio n)<\/code> es la soluci\u00f3n del problema de las monedas, para obtener la cantidad <code>n<\/code>, por b\u00fasqueda en escalada. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   cambio 199  ==  [2,2,5,20,20,50,100]\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 Escalada_Monedas where\n\nimport BusquedaEnEscalada\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Las monedas son n\u00fameros enteros.\ntype Moneda = Int\n\n-- monedas es la lista del tipo de monedas disponibles. Se supone que\n-- hay un n\u00famero infinito de monedas de cada tipo.\nmonedas :: [Moneda]\nmonedas = [1,2,5,10,20,50,100]\n\n-- Las soluciones son listas de monedas.\ntype Solucion = [Moneda]\n\n-- Los estados son pares formados por la cantidad que falta y la lista\n-- de monedas usadas.\ntype Estado = (Int, [Moneda])\n\n-- (inicial n) es el estado inicial del problema de las monedas, para\n-- obtener la cantidad n.\ninicial :: Int -> Estado\ninicial n = (n, [])\n\n-- (esFinal e) se verifica si e es un estado final del problema\n-- de las monedas.\nesFinal :: Estado -> Bool\nesFinal (v,_) = v == 0\n\n-- (sucesores e) es la lista de los sucesores del estado e en el\n-- problema de las monedas. Por ejemplo,\n--   \u03bb> sucesores (199,[])\n--   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),\n--    (179,[20]),(149,[50]),(99,[100])]\nsucesores :: Estado -> [Estado]\nsucesores (r,p) =\n  [(r-c,c:p) | c <- monedas, r-c >= 0]\n\ncambio :: Int -> Solucion\ncambio n =\n  snd (head (buscaEscalada sucesores\n                           esFinal\n                           (inicial n)))\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    cambio 199  `shouldBe`  [2,2,5,20,20,50,100]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--\n--    Finished in 0.0003 seconds\n--    1 example, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Optional\n\nfrom src.BusquedaEnEscalada import buscaEscalada\n\n# Las monedas son n\u00fameros enteros.\nMoneda = int\n\n# monedas es la lista del tipo de monedas disponibles. Se supone que\n# hay un n\u00famero infinito de monedas de cada tipo.\nmonedas: list[Moneda] = [1,2,5,10,20,50,100]\n\n# Las soluciones son listas de monedas.\nSolucion = list[Moneda]\n\n# Los estados son pares formados por la cantidad que falta y la lista\n# de monedas usadas.\nEstado = tuple[int, list[Moneda]]\n\n# inicial(n) es el estado inicial del problema de las monedas, para\n# obtener la cantidad n.\ndef inicial(n: int) -> Estado:\n    return (n, [])\n\n# esFinal(e) se verifica si e es un estado final del problema\n# de las monedas.\ndef esFinal(e: Estado) -> bool:\n    return e[0] == 0\n\n# sucesores(e) es la lista de los sucesores del estado e en el\n# problema de las monedas. Por ejemplo,\n#   \u03bb> sucesores((199,[]))\n#   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),\n#    (179,[20]),(149,[50]),(99,[100])]\ndef sucesores(e: Estado) -> list[Estado]:\n    (r,p) = e\n    return [(r - c, [c] + p) for c in monedas if r - c >= 0]\n\ndef cambio(n: int) -> Optional[Solucion]:\n    r = buscaEscalada(sucesores, esFinal, inicial(n))\n    if r is None:\n        return None\n    return r[1]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_monedas() -> None:\n    assert cambio(199) == [2,2,5,20,20,50,100]\n\n# La verificaci\u00f3n es\n#    src> poetry run pytest -q Escalada_Monedas.py\n#    1 passed in 0.12s\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. El algoritmo de Prim del \u00e1rbol de expansi\u00f3n m\u00ednimo por escalada<\/h3>\n<p>El <a href=\"https:\/\/bit.ly\/466fwRe\">algoritmo de Prim<\/a> calcula un  recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo.<\/p>\n<p>El algoritmo de Prim funciona de la siguiente manera:<\/p>\n<ul>\n<li>Inicializar un \u00e1rbol con un \u00fanico v\u00e9rtice, elegido arbitrariamente, del grafo.<\/li>\n<li>Aumentar el \u00e1rbol por un lado. Llamamos lado a la uni\u00f3n entre dos v\u00e9rtices: de las posibles uniones que pueden conectar el \u00e1rbol a los v\u00e9rtices que no est\u00e1n a\u00fan en el \u00e1rbol, encontrar el lado de menor distancia y unirlo al \u00e1rbol.<\/li>\n<li>Repetir el paso 2 (hasta que todos los v\u00e9rtices pertenezcan al \u00e1rbol)<\/li>\n<\/ul>\n<p>Usando la <a href=\"https:\/\/bit.ly\/3Kk4A99\">b\u00fasqueda en escalada<\/a> el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\n<\/pre>\n<p>tal que <code>prim g<\/code> es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo <code>g<\/code> calculado mediante el algoritmo de Prim con b\u00f1usqueda en escalada. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por<\/p>\n<pre lang=\"text\">\n   g1, g2, g3, g4 :: Grafo Int Int\n   g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                            (2,4,55),(2,5,32),\n                            (3,4,61),(3,5,44),\n                            (4,5,93)]\n   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                            (2,4,12),(2,5,32),\n                            (3,4,14),(3,5,44),\n                            (4,5,93)]\n   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,7),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,1),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n<\/pre>\n<p>entonces<\/p>\n<pre lang=\"text\">\n   prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)]\n   prim g2 == [(2,5,32),(2,4,12),(1,2,13),(1,3,11)]\n   prim g3 == [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)]\n   prim g4 == [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)]\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 Escalada_Prim where\n\nimport BusquedaEnEscalada (buscaEscalada)\nimport TAD.Grafo (Grafo, Orientacion (ND), aristaEn, creaGrafo, nodos, peso)\nimport Data.Ix (Ix)\nimport Data.List (delete)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ng1, g2, g3, g4 :: Grafo Int Int\ng1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                         (2,4,55),(2,5,32),\n                         (3,4,61),(3,5,44),\n                         (4,5,93)]\ng2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                         (2,4,12),(2,5,32),\n                         (3,4,14),(3,5,44),\n                         (4,5,93)]\ng3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,7),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\ng4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,1),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\n\n-- Una arista esta formada por dos v\u00e9rtices junto con su peso.\ntype Arista a b = (a,a,b)\n\n-- Un estado (Estado (p,t,r,aem)) est\u00e1 formado por el peso p de la\n-- \u00faltima arista a\u00f1adida el \u00e1rbol de expansi\u00f3n m\u00ednimo (aem), la lista t\n-- de nodos del grafo que est\u00e1n en el aem, la lista r de nodos del\n-- grafo que no est\u00e1n en el aem y el aem.\ntype Estado a b = (b,[a],[a],[Arista a b])\n\n-- (inicial g) es el estado inicial correspondiente al grafo g.\ninicial :: (Ix a, Num b, Ord b) => Grafo a b -> Estado a b\ninicial g = (0,[n],ns,[])\n  where (n:ns) = nodos g\n\n-- (esFinal e) se verifica si e es un estado final; es decir, si no\n-- queda ning\u00fan elemento en la lista de nodos sin colocar en el \u00e1rbol de\n-- expansi\u00f3n m\u00ednimo.\nesFinal :: Estado a b -> Bool\nesFinal (_,_,[],_) = True\nesFinal _          = False\n\n-- (sucesores g e) es la lista de los sucesores del estado e en el\n-- grafo g. Por ejemplo,\n--    \u03bb> sucesores g1 (0,[1],[2..5],[])\n--    [(12,[2,1],[3,4,5],[(1,2,12)]),\n--     (34,[3,1],[2,4,5],[(1,3,34)]),\n--     (78,[5,1],[2,3,4],[(1,5,78)])]\nsucesores\n  :: (Ix a, Num b, Eq b) => Grafo a b -> Estado a b -> [Estado a b]\nsucesores g (_,t,r,aem) =\n  [(peso x y g, y:t, delete y r, (x,y,peso x y g):aem)\n   | x <- t , y <- r, aristaEn g (x,y)]\n\nprim :: (Ix a, Num b, Ord b) => Grafo a b -> [Arista a b]\nprim g = sol\n  where [(_,_,_,sol)] = buscaEscalada (sucesores g)\n                                      esFinal\n                                      (inicial g)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    prim g1 `shouldBe` [(2,4,55),(1,3,34),(2,5,32),(1,2,12)]\n  it \"e2\" $\n    prim g2 `shouldBe` [(2,5,32),(2,4,12),(1,2,13),(1,3,11)]\n  it \"e3\" $\n    prim g3 `shouldBe` [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)]\n  it \"e4\" $\n    prim g4 `shouldBe` [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0043 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 typing import Optional\n\nfrom src.BusquedaEnEscalada import buscaEscalada\nfrom src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristaEn,\n                           creaGrafo, nodos, peso)\n\ng1 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((1,2),12),((1,3),34),((1,5),78),\n                 ((2,4),55),((2,5),32),\n                 ((3,4),61),((3,5),44),\n                 ((4,5),93)])\ng2 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((1,2),13),((1,3),11),((1,5),78),\n                 ((2,4),12),((2,5),32),\n                 ((3,4),14),((3,5),44),\n                 ((4,5),93)])\ng3 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),7),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\ng4 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),1),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\n\nArista = tuple[tuple[Vertice, Vertice], Peso]\n\n# Un nodo (Estado (p,t,r,aem)) est\u00e1 formado por el peso p de la \u00faltima\n# arista a\u00f1adida el \u00e1rbol de expansi\u00f3n m\u00ednimo (aem), la lista t\n# de nodos del grafo que est\u00e1n en el aem, la lista r de nodos del\n# grafo que no est\u00e1n en el aem y el aem.\nEstado = tuple[Peso, list[Vertice], list[Vertice], list[Arista]]\n\n# inicial(g) es el estado inicial correspondiente al grafo g.\ndef inicial(g: Grafo) -> Estado:\n    n, *ns = nodos(g)\n    return (0, [n], ns, [])\n\n# esFinal(e) se verifica si e es un estado final; es decir, si no\n# queda ning\u00fan elemento en la lista de nodos sin colocar en el \u00e1rbol de\n# expansi\u00f3n m\u00ednimo.\ndef esFinal(e: Estado) -> bool:\n    return e[2] == []\n\n# sucesores(g, e) es la lista de los sucesores del estado e en el\n# grafo g. Por ejemplo,\n#    \u03bb> sucesores(g1, (0,[1],[2,3,4,5],[]))\n#    [(12,[2,1],[3,4,5],[(1,2,12)]),\n#     (34,[3,1],[2,4,5],[(1,3,34)]),\n#     (78,[5,1],[2,3,4],[(1,5,78)])]\ndef sucesores(g: Grafo, e: Estado) -> list[Estado]:\n    (_,t,r,aem) = e\n    return [(peso(x, y, g),\n             [y] + t,\n             [x for x in r if x != y],\n             [((x,y),peso(x, y, g))] + aem)\n            for x in t for y in r if aristaEn(g, (x, y))]\n\ndef prim(g: Grafo) -> Optional[list[Arista]]:\n    r = buscaEscalada(lambda e: sucesores(g, e), esFinal, inicial(g))\n    if r is None:\n        return None\n    return r[3]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_prim() -> None:\n    assert prim(g1) == [((2,4),55),((1,3),34),((2,5),32),((1,2),12)]\n    assert prim(g2) == [((2,5),32),((2,4),12),((1,2),13),((1,3),11)]\n    assert prim(g3) == [((5,7),9),((2,3),7),((5,4),5),((6,5),3),((1,6),6),((1,2),5)]\n    assert prim(g4) == [((5,7),9),((5,4),5),((5,3),1),((6,5),3),((1,6),6),((1,2),5)]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_prim()\n#    Verificado\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. El problema del granjero mediante b\u00fasqueda en espacio de estado<\/h3>\n<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<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. El problema de las fichas mediante b\u00fasqueda en espacio de estado<\/h3>\n<p>Para el problema de las fichas de orden (m,n) se considera un tablero con m+n+1 cuadrados consecutivos.<\/p>\n<p>Inicialmente, en cada uno de los m primeros cuadrados hay una  blanca, a continuaci\u00f3n un hueco y  en cada uno de los n \u00faltimos cuadrados hay una ficha verde. El objetivo consiste en tener las fichas verdes al principio y las blancas al final.<\/p>\n<p>Por ejemplo, en el problema de las fichas de orden (3,3) el tablero inicial es<\/p>\n<pre lang=\"text\">\n      +---+---+---+---+---+---+---+\n      | B | B | B |   | V | V | V |\n      +---+---+---+---+---+---+---+\n<\/pre>\n<p>y el final es<\/p>\n<pre lang=\"text\">\n      +---+---+---+---+---+---+---+\n      | V | V | V |   | B | B | B |\n      +---+---+---+---+---+---+---+\n<\/pre>\n<p>Los movimientos permitidos consisten en desplazar una ficha al hueco saltando, como m\u00e1ximo, sobre otras dos.<\/p>\n<p>Para representar el problema se definen los siguientes tipos de datos:<\/p>\n<ul>\n<li><code>Ficha<\/code> con tres constructores <code>B<\/code>, <code>V<\/code> y <code>H<\/code> que representan las fichas blanca, verde y hueco, respectivamente.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     data Ficha = B | V | H\n       deriving (Eq, Show)\n<\/pre>\n<ul>\n<li><code>Tablero<\/code> que es una lista de fichas que representa las fichas colocadas en el tablero.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Tablero = [Ficha]\n<\/pre>\n<ul>\n<li><code>Estado<\/code> representa los estados del espacio de b\u00fasqueda, donde un estado es una lista de tableros [t(n), &#8230;, t(2), t(1)] tal que t(1) es el tablero inicial y para cada i (2 &lt;= i &lt;= n), t(i) es un sucesor de t(i-1).<\/li>\n<\/ul>\n<pre lang=\"text\">\n     newtype Estado = E [Tablero]\n       deriving (Eq, Show)\n<\/pre>\n<ul>\n<li><code>Busqueda<\/code> es un procedimiento de b\u00fasqueda<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Busqueda = (Estado -> [Estado]) ->\n                     (Estado -> Bool) ->\n                     Estado ->\n                     [Estado]\n<\/pre>\n<p>Adem\u00e1s, se considera la heur\u00edstica que para cada tablero vale la suma de piezas blancas situadas a la izquierda de cada una de las piezas verdes. Por  ejemplo, para el estado<\/p>\n<pre lang=\"text\">\n      +---+---+---+---+---+---+---+\n      | B | V | B |   | V | V | B |\n      +---+---+---+---+---+---+---+\n<\/pre>\n<p>su valor es 1+2+2 = 5. La heur\u00edstica de un estado es la del primero de sus tableros.<\/p>\n<p>Usando los m\u00e9todos de b\u00fasqueda estudiado en los ejercicios anteriores, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   fichas :: Busqueda -> Int -> Int -> [[Tablero]]\n<\/pre>\n<p>tal que <code>fichas b m n<\/code> es la lista de las soluciones del problema de las fichas de orden (m,n) obtenidas mediante el procedimiento de b\u00fasqueda b. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> head (fichas buscaProfundidad 2 2)\n   [[B,B,H,V,V],[B,H,B,V,V],[H,B,B,V,V],[V,B,B,H,V],[V,B,H,B,V],[V,H,B,B,V],\n    [H,V,B,B,V],[B,V,H,B,V],[B,H,V,B,V],[H,B,V,B,V],[B,B,V,H,V],[B,B,V,V,H],\n    [B,H,V,V,B],[H,B,V,V,B],[V,B,H,V,B],[V,H,B,V,B],[H,V,B,V,B],[B,V,H,V,B],\n    [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]]\n   \u03bb> head (fichas buscaAnchura 2 2)\n   [[B,B,H,V,V],[B,B,V,V,H],[B,H,V,V,B],[B,V,V,H,B],[H,V,V,B,B],\n    [V,V,H,B,B]]\n   \u03bb> head (fichas buscaPM 2 2)\n   [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],\n    [V,V,B,B,H],[V,V,B,H,B],[V,V,H,B,B]]\n   \u03bb> head (fichas buscaEscalada 2 2)\n   [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],\n    [V,V,B,B,H],[V,V,B,H,B],[V,V,H,B,B]]\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_de_las_fichas where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport BusquedaEnAnchura (buscaAnchura)\nimport BusquedaPrimeroElMejor (buscaPM)\nimport BusquedaEnEscalada (buscaEscalada)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Representaci\u00f3n del problema\n-- ===========================\n\ndata Ficha = B | V | H\n  deriving (Eq, Show)\n\ntype Tablero = [Ficha]\n\n-- (tableroInicial m n) representa el tablero inicial del problema de las fichas\n-- de orden (m,n). Por ejemplo,\n--    tableroInicial 2 3  ==  [B,B,H,V,V,V]\n--    tableroInicial 3 2  ==  [B,B,B,H,V,V]\ntableroInicial ::  Int -> Int -> Tablero\ntableroInicial m n = replicate m B ++ [H] ++ replicate n V\n\n-- (tableroFinal m n) representa el tablero final del problema de las fichas de\n-- orden (m,n). Por ejemplo,\n--    tableroFinal 2 3  ==  [V,V,V,H,B,B]\n--    tableroFinal 3 2  ==  [V,V,H,B,B,B]\ntableroFinal ::  Int -> Int -> Tablero\ntableroFinal m n = replicate n V ++ [H] ++ replicate m B\n\n-- (tablerosSucesores t) es la lista de los sucesores del tablero t. Por\n-- ejemplo,\n--    \u03bb> tablerosSucesores [V,B,H,V,V,B]\n--    [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B],\n--     [V,B,B,V,V,H]]\n--    \u03bb> tablerosSucesores [B,B,B,H,V,V,V]\n--    [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V],\n--     [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]]\ntablerosSucesores :: Tablero -> [Tablero]\ntablerosSucesores t =\n  [intercambia i j t | i <- [j-1,j-2,j-3,j+1,j+2,j+3]\n                     , 0 <= i, i < n]\n  where j = posicionHueco t\n        n = length t\n\n-- (posicionHueco t) es la posici\u00f3n del hueco en el tablero t. Por\n-- ejemplo,\n--    posicionHueco (tableroInicial 3 2)  ==  3\nposicionHueco :: Tablero -> Int\nposicionHueco t = length (takeWhile (\/=H) t)\n\n-- (intercambia xs i j) es la lista obtenida intercambiando los\n-- elementos de xs en las posiciones i y j. Por ejemplo,\n--    intercambia 2 6 [0..9]  ==  [0,1,6,3,4,5,2,7,8,9]\n--    intercambia 6 2 [0..9]  ==  [0,1,6,3,4,5,2,7,8,9]\nintercambia :: Int -> Int -> [a] -> [a]\nintercambia i j xs = concat [xs1,[x2],xs2,[x1],xs3]\n  where (xs1,x1,xs2,x2,xs3) = divide (min i j) (max i j) xs\n\n-- (divide xs i j) es la tupla (xs1,x1,xs2,x2,xs3) tal que xs1 son los\n-- elementos de xs cuya posici\u00f3n es menor que i, x1 es el elemento de xs\n-- en la posici\u00f3n i, xs2 son los elementos de xs cuya posici\u00f3n es mayor\n-- que i y menor que j, x2 es el elemento de xs en la posici\u00f3n j y xs3\n-- son los elementos de xs cuya posici\u00f3n es mayor que j (suponiendo que\n-- i < j). Por ejemplo,\n--    divide 2 6 [0..9]  ==  ([0,1],2,[3,4,5],6,[7,8,9])\ndivide :: Int -> Int -> [a] -> ([a],a,[a],a,[a])\ndivide i j xs = (xs1,x1,xs2,x2,xs3)\n  where (xs1,x1:ys)  = splitAt i xs\n        (xs2,x2:xs3) = splitAt (j - i - 1) ys\n\nnewtype Estado = E [Tablero]\n  deriving (Eq, Show)\n\n-- (inicial m n) representa el estado inicial del problema de las fichas\n-- de orden (m,n). Por ejemplo,\n--    inicial 2 3  ==  E [[B,B,H,V,V,V]]\n--    inicial 3 2  ==  E [[B,B,B,H,V,V]]\ninicial :: Int -> Int -> Estado\ninicial m n = E [tableroInicial m n]\n\n-- (esFinal m n e) se verifica si e es un estado final del problema de las\n-- fichas de orden (m,n). Por ejemplo,\n--    \u03bb> esFinal 2 1 (E [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]])\n--    True\n--    \u03bb> esFinal 2 1 (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]])\n--    False\nesFinal :: Int -> Int -> Estado -> Bool\nesFinal m n (E (e:_)) = e == tableroFinal m n\n\n-- (sucesores n) es la lista de los sucesores del estado n. Por ejemplo,\n--    \u03bb> sucesores (E [[H,B,B,V],[B,B,H,V]])\n--    [E [[B,H,B,V],[H,B,B,V],[B,B,H,V]],\n--     E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]]\n--    \u03bb> sucesores (E [[B,H,B,V],[H,B,B,V],[B,B,H,V]])\n--    [E [[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]]\nsucesores :: Estado -> [Estado]\nsucesores (E e@(t:ts)) =\n  [E (t':e) | t' <- tablerosSucesores t,\n              t' `notElem` ts]\n\n-- Heur\u00edstica\n-- ==========\n\n-- (heuristicaT t) es la heur\u00edstica del tablero t. Por ejemplo,\n--    heuristicaT [B,V,B,H,V,V,B] == 5\nheuristicaT :: Tablero -> Int\nheuristicaT []     = 0\nheuristicaT (V:xs) = heuristicaT xs\nheuristicaT (H:xs) = heuristicaT xs\nheuristicaT (B:xs) = heuristicaT xs + length (filter (==V) xs)\n\n-- (heuristica e) es la heur\u00edstica del primer tablero del estado e. Por\n-- ejemplo,\n--    heuristica (E [[H,B,B,V],[B,B,H,V]])            ==  2\n--    heuristica (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]])  ==  0\nheuristica :: Estado -> Int\nheuristica (E (t:_)) = heuristicaT t\n\n-- Estado es un subtipo de Ord de forma que un estado es menor o igual\n-- que otro si su heur\u00edstica lo es.\ninstance Ord Estado where\n  e1 <= e2 = heuristica e1 <= heuristica e2\n\n-- Soluci\u00f3n por b\u00fasqueda\n-- =====================\n\ntype Busqueda = (Estado -> [Estado]) ->\n                (Estado -> Bool) ->\n                Estado ->\n                [Estado]\n\nfichas :: Busqueda -> Int -> Int -> [[Tablero]]\nfichas b m n =\n  [reverse es | E es <- b sucesores (esFinal m n) (inicial m n)]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    head (fichas buscaProfundidad 2 2) `shouldBe`\n    [[B,B,H,V,V],[B,H,B,V,V],[H,B,B,V,V],[V,B,B,H,V],[V,B,H,B,V],[V,H,B,B,V],\n     [H,V,B,B,V],[B,V,H,B,V],[B,H,V,B,V],[H,B,V,B,V],[B,B,V,H,V],[B,B,V,V,H],\n     [B,H,V,V,B],[H,B,V,V,B],[V,B,H,V,B],[V,H,B,V,B],[H,V,B,V,B],[B,V,H,V,B],\n     [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]]\n  it \"e2\" $\n    head (fichas buscaAnchura 2 2) `shouldBe`\n    [[B,B,H,V,V],[B,B,V,V,H],[B,H,V,V,B],[B,V,V,H,B],[H,V,V,B,B],[V,V,H,B,B]]\n  it \"e3\" $\n    head (fichas buscaPM 2 2) `shouldBe`\n    [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],[V,V,B,B,H],\n     [V,V,B,H,B],[V,V,H,B,B]]\n  it \"e4\" $\n    head (fichas buscaEscalada 2 2) `shouldBe`\n    [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],[V,V,B,B,H],\n     [V,V,B,H,B],[V,V,H,B,B]]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0055 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 enum import Enum\nfrom functools import partial\nfrom typing import Callable, Optional\n\nfrom src.BusquedaEnAnchura import buscaAnchura1\nfrom src.BusquedaEnEscalada import buscaEscalada\nfrom src.BusquedaEnProfundidad import buscaProfundidad1\nfrom src.BusquedaPrimeroElMejor import buscaPM\n\n# Representaci\u00f3n del problema\n# ===========================\n\nclass Ficha(Enum):\n    B = 0\n    V = 1\n    H = 2\n\n    def __repr__(self) -> str:\n        return self.name\n\nB = Ficha.B\nV = Ficha.V\nH = Ficha.H\n\nTablero = list[Ficha]\n\n# tableroInicial(m, n) representa el tablero inicial del problema de las fichas\n# de orden (m,n). Por ejemplo,\n#    tableroInicial(2, 3)  ==  [B,B,H,V,V,V]\n#    tableroInicial(3, 2)  ==  [B,B,B,H,V,V]\ndef tableroInicial(m: int, n: int) -> Tablero:\n    return [B]*m + [H] + [V]*n\n\n# tableroFinal(m, n) representa el tablero final del problema de las fichas de\n# orden (m,n). Por ejemplo,\n#    tableroFinal(2, 3)  ==  [V,V,V,H,B,B]\n#    tableroFinal(3, 2)  ==  [V,V,H,B,B,B]\ndef tableroFinal(m: int, n: int) -> Tablero:\n    return [V]*n + [H] + [B]*m\n\n# posicionHueco(t) es la posici\u00f3n del hueco en el tablero t. Por\n# ejemplo,\n#    posicionHueco(tableroInicial(3, 2))  ==  3\ndef posicionHueco(t: Tablero) -> int:\n    return t.index(H)\n\n# intercambia(xs, i, j) es la lista obtenida intercambiando los\n# elementos de xs en las posiciones i y j. Por ejemplo,\n#    intercambia(1, 3, tableroInicial(3, 2))  ==  [B, H, B, B, V, V]\ndef intercambia(i: int, j: int, t: Tablero) -> Tablero:\n    t1 = t.copy()\n    t1[i], t1[j] = t1[j], t1[i]\n    return t1\n\n# tablerosSucesores(t) es la lista de los sucesores del tablero t. Por\n# ejemplo,\n#    >>> tablerosSucesores([V,B,H,V,V,B])\n#    [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B],\n#     [V,B,B,V,V,H]]\n#    >>> tablerosSucesores([B,B,B,H,V,V,V])\n#    [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V],\n#     [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]]\ndef tablerosSucesores(t: Tablero) -> list[Tablero]:\n    j = posicionHueco(t)\n    n = len(t)\n    return [intercambia(i, j, t)\n            for i in [j-1,j-2,j-3,j+1,j+2,j+3]\n            if 0 <= i < n]\n\n# Heur\u00edstica\n# ==========\n\n# heuristicaT(t) es la heur\u00edstica del tablero t. Por ejemplo,\n#    heuristicaT([B,V,B,H,V,V,B]) == 5\ndef heuristicaT(t: Tablero) -> int:\n    if not t:\n        return 0\n    f, *fs = t\n    if f in {V, H}:\n        return heuristicaT(fs)\n    return heuristicaT(fs) + len([x for x in fs if x == V])\n\nclass Estado(list[Tablero]):\n    def __lt__(self, e: list[Tablero]) -> bool:\n        return heuristicaT(self[0]) < heuristicaT(e[0])\n\n# inicial(m, n) representa el estado inicial del problema de las fichas\n# de orden (m,n). Por ejemplo,\n#    inicial(2, 3)  ==  [[B,B,H,V,V,V]]\n#    inicial(3, 2)  ==  [[B,B,B,H,V,V]]\ndef inicial(m: int, n: int) -> Estado:\n    return Estado([tableroInicial(m, n)])\n\n# esFinal(m, n, e) se verifica si e es un estado final del problema de las\n# fichas de orden (m,n). Por ejemplo,\n#    >>> esFinal(2, 1, [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]])\n#    True\n#    >>> esFinal(2, 1, [[V,B,B,H],[H,B,B,V],[B,B,H,V]])\n#    False\ndef esFinal(m: int, n: int, e: Estado) -> bool:\n    return e[0] == tableroFinal(m, n)\n\n# (sucesores n) es la lista de los sucesores del estado n. Por ejemplo,\n#    >>> sucesores([[H,B,B,V],[B,B,H,V]])\n#    [[[B,H,B,V],[H,B,B,V],[B,B,H,V]],\n#     [[V,B,B,H],[H,B,B,V],[B,B,H,V]]]\n#    >>> sucesores([[B,H,B,V],[H,B,B,V],[B,B,H,V]])\n#    [[[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]]\ndef sucesores(e: Estado) -> list[Estado]:\n    t, *ts = e\n    return [Estado([t1] + e) for t1 in tablerosSucesores(t) if t1 not in ts]\n\n# Soluci\u00f3n por b\u00fasqueda\n# =====================\n\nBusqueda = Callable[[Callable[[Estado], list[Estado]],\n                     Callable[[Estado], bool],\n                     Estado],\n                    Optional[Estado]]\n\ndef fichas(b: Busqueda, m: int, n: int) -> Optional[list[Tablero]]:\n    r = partial(b, sucesores, lambda e: esFinal(m, n, e), inicial(m, n))()\n    if r is None:\n        return None\n    return [list(reversed(es)) for es in r]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_fichas() -> None:\n    assert fichas(buscaProfundidad1, 1, 2) == \\\n        [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]]\n    assert fichas(buscaAnchura1, 1, 2) == \\\n        [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]]\n    assert fichas(buscaPM, 1, 2) == \\\n        [[B, H, V, V], [B, V, H, V], [H, V, B, V], [V, V, B, H],\n         [V, V, H, B]]\n    assert fichas(buscaEscalada, 1, 2) == \\\n        [[B, H, V, V], [H, B, V, V], [V, B, H, V], [V, H, B, V],\n         [V, V, B, H], [V, V, H, B]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_fichas()\n#    Verificado\n<\/pre>\n<p><a name=\"ej6\"><\/a><\/p>\n<h3>6. El problema del calendario mediante b\u00fasqueda en espacio de estado<\/h3>\n<p>El problema del calendario, para una competici\u00f3n deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que:<\/p>\n<ul>\n<li>el campeonato dure n-1 d\u00edas,<\/li>\n<li>cada participante juegue exactamente un partido diario y<\/li>\n<li>cada participante juegue exactamente una vez con cada adversario.<\/li>\n<\/ul>\n<p>Por ejemplo, con 8 participantes una posible soluci\u00f3n es<\/p>\n<pre lang=\"text\">\n     | 1 2 3 4 5 6 7\n   --+--------------\n   1 | 2 3 4 5 6 7 8\n   2 | 1 4 3 6 5 8 7\n   3 | 4 1 2 7 8 5 6\n   4 | 3 2 1 8 7 6 5\n   5 | 6 7 8 1 2 3 4\n   6 | 5 8 7 2 1 4 3\n   7 | 8 5 6 3 4 1 2\n   8 | 7 6 5 4 3 2 1\n<\/pre>\n<p>donde las filas indican los jugadores y las columnas los d\u00edas; es decir, el elemento (i,j) indica el adversario del jugador i el d\u00eda j; por ejemplo, el adversario del jugador 2 el 4\u00aa d\u00eda es el jugador 6.<\/p>\n<p>Para representar el problema se define el tipo Calendario como matrices de enteros,<\/p>\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   calendario :: Int -> [Calendario]\n<\/pre>\n<p>tal que <code>calendario n<\/code> son las soluciones del problema del calendario, con n participantes, mediante el patr\u00f3n de b\u00fasqueda em profundidad. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> head (calendario 6)\n   \u250c           \u2510\n   \u2502 2 3 4 5 6 \u2502\n   \u2502 1 4 5 6 3 \u2502\n   \u2502 5 1 6 4 2 \u2502\n   \u2502 6 2 1 3 5 \u2502\n   \u2502 3 6 2 1 4 \u2502\n   \u2502 4 5 3 2 1 \u2502\n   \u2514           \u2518\n\n   \u03bb> length (calendario 6)\n   720\n   \u03bb> length (calendario 5)\n   0\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 El_problema_del_calendario_mediante_busqueda_en_espacio_de_estado where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.Matrix (Matrix, (!), nrows, zero, setElem, toLists)\nimport Data.List ((\\\\))\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Calendario = Matrix Int\n\n-- (inicial n) es el estado inicial para el problema del calendario con\n-- n participantes; es decir, una matriz de n fila y n-1 columnas con\n-- todos sus elementos iguales a 0. Por ejemplo,\n--    \u03bb> inicial 4\n--    \u250c       \u2510\n--    \u2502 0 0 0 \u2502\n--    \u2502 0 0 0 \u2502\n--    \u2502 0 0 0 \u2502\n--    \u2502 0 0 0 \u2502\n--    \u2514       \u2518\ninicial :: Int -> Calendario\ninicial n = zero n (n-1)\n\n-- (huecos c) es la lista de las posiciones de c cuyo valor es 0.\nhuecos :: Calendario -> [(Int, Int)]\nhuecos c = [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0]\n  where n = nrows c\n\n-- (sucesores c) es la lista de calendarios obtenidos poniendo en el\n-- lugar del primer elemento nulo de c uno de los posibles jugadores de\n-- forma que se cumplan las condiciones del problema. Por ejemplo,\n--    \u03bb> sucesores (inicial 4)\n--    [\u250c       \u2510  \u250c       \u2510  \u250c       \u2510\n--     \u2502 2 0 0 \u2502  \u2502 3 0 0 \u2502  \u2502 4 0 0 \u2502\n--     \u2502 1 0 0 \u2502  \u2502 0 0 0 \u2502  \u2502 0 0 0 \u2502\n--     \u2502 0 0 0 \u2502  \u2502 1 0 0 \u2502  \u2502 0 0 0 \u2502\n--     \u2502 0 0 0 \u2502  \u2502 0 0 0 \u2502  \u2502 1 0 0 \u2502\n--     \u2514       \u2518, \u2514       \u2518, \u2514       \u2518]\n--    \u03bb> sucesores (fromLists [[2,3,0],[1,0,0],[0,1,0],[0,0,0]])\n--    [\u250c       \u2510\n--     \u2502 2 3 4 \u2502\n--     \u2502 1 0 0 \u2502\n--     \u2502 0 1 0 \u2502\n--     \u2502 0 0 1 \u2502\n--     \u2514       \u2518]\n--    \u03bb> sucesores (fromLists [[2,3,4],[1,0,0],[0,1,0],[0,0,1]])\n--    [\u250c       \u2510\n--     \u2502 2 3 4 \u2502\n--     \u2502 1 4 0 \u2502\n--     \u2502 0 1 0 \u2502\n--     \u2502 0 2 1 \u2502\n--     \u2514       \u2518]\nsucesores :: Calendario -> [Calendario]\nsucesores c =\n  [setElem i (k,j) (setElem k (i,j) c) |\n   k <- [1..n] \\\\ (i : [c!(k,j) | k <- [1..i-1]] ++\n                       [c!(i,k) | k <- [1..j-1]]),\n   c!(k,j) == 0]\n  where\n    n = nrows c\n    (i,j) = head (huecos c)\n\n-- (esFinal c) se verifica si c un estado final para el problema\n-- del calendario con n participantes; es decir, no queda en c ning\u00fan\n-- elemento igual a 0. Por ejemplo,\n--    \u03bb> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]])\n--    True\n--    \u03bb> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]])\n--    False\nesFinal :: Calendario -> Bool\nesFinal c = null (huecos c)\n\ncalendario :: Int -> [Calendario]\ncalendario n = buscaProfundidad sucesores esFinal (inicial n)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    toLists (head (calendario 6)) `shouldBe`\n    [[2,3,4,5,6],[1,4,5,6,3],[5,1,6,4,2],[6,2,1,3,5],[3,6,2,1,4],[4,5,3,2,1]]\n  it \"e2\" $\n    length (calendario 6) `shouldBe` 720\n  it \"e3\" $\n    length (calendario 5) `shouldBe` 0\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.2580 seconds\n--    3 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import Optional\n\nimport numpy as np\nimport numpy.typing as npt\n\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\nCalendario = npt.NDArray[np.complex64]\n\n# inicial(n) es el estado inicial para el problema del calendario con\n# n participantes; es decir, una matriz de n fila y n-1 columnas con\n# todos sus elementos iguales a 0. Por ejemplo,\n#    >>> inicial(4)\n#    array([[0, 0, 0],\n#           [0, 0, 0],\n#           [0, 0, 0],\n#           [0, 0, 0]])\ndef inicial(n: int) -> Calendario:\n    return np.zeros((n, n - 1), dtype=int)\n\n# primerHueco(c) es la posici\u00f3n del primer elemento cuyo valor es 0. Si\n# todos los valores son distintos de 0, devuelve (-1,-1). Por ejemplo,\n#    primerHueco(np.array([[1,2,3],[4,5,0],[7,0,0]])) == (1, 2)\n#    primerHueco(np.array([[1,2,3],[4,5,6],[7,8,0]])) == (2, 2)\n#    primerHueco(np.array([[1,2,3],[4,5,6],[7,8,9]])) == (-1, -1)\ndef primerHueco(c: Calendario) -> tuple[int, int]:\n    (n, m) = c.shape\n    for i in range(0, n):\n        for j in range(0, m):\n            if c[i,j] == 0:\n                return (i, j)\n    return (-1, -1)\n\n# libres(c, i, j) es la lista de valores que que pueden poner en la\n# posici\u00f3n (i,j) del calendario c. Por ejemplo,\n#    libres(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]),0,0) == [2, 3, 4]\n#    libres(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]),0,1) == [3, 4]\n#    libres(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]),0,2) == [4]\n#    libres(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]),1,1) == [4]\n#    libres(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]),1,2) == [3]\ndef libres(c: Calendario, i: int, j: int) -> list[int]:\n    n = c.shape[0]\n    return list(set(range(1, n + 1))\n                - {i + 1}\n                - set(c[i])\n                - set(c[:,j]))\n\n# setElem(k, i, j, c) es el calendario obtenido colocando en c el valor\n# k en la posici\u00f3n (i,j).\n#    >>> setElem(7,1,2,np.array([[1,2,3],[4,5,0],[0,0,0]]))\n#    array([[1, 2, 3],\n#           [4, 5, 7],\n#           [0, 0, 0]])\ndef setElem(k: int, i: int, j: int, c: Calendario) -> Calendario:\n    _c = deepcopy(c)\n    _c[i, j] = k\n    return _c\n\n# sucesores(c) es la lista de calendarios obtenidos poniendo en el\n# lugar del primer elemento nulo de c uno de los posibles jugadores de\n# forma que se cumplan las condiciones del problema. Por ejemplo,\n#    >>> sucesores(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]))\n#    [array([[2,0,0], [1,0,0], [0,0,0], [0,0,0]]),\n#     array([[3,0,0], [0,0,0], [1,0,0], [0,0,0]]),\n#     array([[4,0,0], [0,0,0], [0,0,0], [1,0,0]])]\n#    >>> sucesores(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]))\n#    [array([[2,3,0], [1,0,0], [0,1,0], [0,0,0]]),\n#     array([[2,4,0], [1,0,0], [0,0,0], [0,1,0]])]\n#    >>> sucesores(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]))\n#    [array([[2,3,4], [1,0,0], [0,1,0], [0,0,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]))\n#    [array([[2,3,4], [1,4,0], [0,1,0], [0,2,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]))\n#    [array([[2,3,4], [1,4,3], [0,1,2], [0,2,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,4,3],[0,1,2],[0,2,1]]))\n#    [array([[2,3,4], [1,4,3], [4,1,2], [3,2,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]]))\n#    []\ndef sucesores(c: Calendario) -> list[Calendario]:\n    n = c.shape[0]\n    (i, j) = primerHueco(c)\n    return [setElem(i+1, k-1, j, setElem(k, i, j, c))\n            for k in libres(c, i, j)]\n\n# esFinal(c) se verifica si c un estado final para el problema\n# del calendario con n participantes; es decir, no queda en c ning\u00fan\n# elemento igual a 0. Por ejemplo,\n#    >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]]))\n#    True\n#    >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,0]]))\n#    False\ndef esFinal(c: Calendario) -> bool:\n    return primerHueco(c) == (-1, -1)\n\ndef calendario(n: int) -> list[Calendario]:\n    return buscaProfundidad(sucesores, esFinal, inicial(n))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_calendario() -> None:\n    def filas(p: Calendario) -> list[list[int]]:\n        return p.tolist()\n\n    assert filas(calendario(6)[0]) == \\\n        [[6, 5, 4, 3, 2],\n         [5, 4, 3, 6, 1],\n         [4, 6, 2, 1, 5],\n         [3, 2, 1, 5, 6],\n         [2, 1, 6, 4, 3],\n         [1, 3, 5, 2, 4]]\n    assert len(calendario(6)) == 720\n    assert len(calendario(5)) == 0\n    print(\"Verificado\")\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Este mes he publicado en Exercitium las soluciones de los siguientes problemas: 1. B\u00fasqueda en escalada 2. Problema de las monedas por b\u00fasqueda en escalada 3. El algoritmo de Prim del \u00e1rbol de expansi\u00f3n m\u00ednimo por escalada 4. El problema del granjero mediante b\u00fasqueda en espacio de estado 5. El problema de las fichas mediante&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8012"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=8012"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8012\/revisions"}],"predecessor-version":[{"id":8013,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8012\/revisions\/8013"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=8012"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=8012"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=8012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}