{"id":7957,"date":"2023-07-09T09:16:22","date_gmt":"2023-07-09T07:16:22","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7957"},"modified":"2023-07-09T11:42:49","modified_gmt":"2023-07-09T09:42:49","slug":"08-jul-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/08-jul-23\/","title":{"rendered":"La semana en Exercitium (8 de julio de 2023)"},"content":{"rendered":"<p>Esta semana 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. El problema de las n reinas (mediante b\u00fasqueda por anchura en espacios de estados)<\/a><\/li>\n<li><a href=\"#ej2\">2. El problema de la mochila (mediante espacio de estados)<\/a><\/li>\n<li><a href=\"#ej3\">3. El tipo abstracto de datos de las colas de prioridad<\/a><\/li>\n<li><a href=\"#ej4\">4. B\u00fasqueda por primero el mejor<\/a><\/li>\n<li><a href=\"#ej5\">5. El problema del 8 puzzle<\/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. El problema de las n reinas (mediante b\u00fasqueda por anchura en espacios de estados)<\/h3>\n<p>El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren m\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal.<\/p>\n<p>Las posiciones de las reinas en el tablero se representan por su columna y su fila.<\/p>\n<pre lang=\"text\">\n   type Columna = Int\n   type Fila    = Int\n<\/pre>\n<p>Una soluci\u00f3n del problema de las n reinas es una lista de posiciones.<\/p>\n<pre lang=\"text\">\n   type SolNR = [(Columna,Fila)]\n<\/pre>\n<p>Usando el procedimiento de <a href=\"https:\/\/bit.ly\/3XBlqG7\">b\u00fasqueda en anchura<\/a>, definir las funciones<\/p>\n<pre lang=\"text\">\n   solucionesNR      :: Columna -> [SolNR]\n   primeraSolucionNR :: Columna -> SolNR\n   nSolucionesNR     :: Columna -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>solucionesNR n<\/code> es la lista de las soluciones del problema de las n reinas, por b\u00fasqueda de espacio de estados en anchura. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     take 3 (solucionesNR 8)\n     [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],\n      [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],\n      [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]\n<\/pre>\n<ul>\n<li><code>primeraSolucionNR n<\/code> es la primera soluci\u00f3n del problema de las n reinas, por b\u00fasqueda en espacio de estados por anchura. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> primeraSolucionNR 8\n     [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]\n<\/pre>\n<ul>\n<li><code>nSolucionesNR n<\/code> es el n\u00famero de soluciones del problema de las n reinas, por b\u00fasqueda en espacio de estados. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nSolucionesNR 8  ==  92\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_Reinas_Anchura where\n\nimport BusquedaEnAnchura (buscaAnchura)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Columna = Int\ntype Fila    = Int\ntype SolNR = [(Columna,Fila)]\n\n-- Los nodos del problema de las n reinas son ternas formadas por la\n-- columna de la \u00faltima reina colocada, el n\u00famero de columnas del\n-- tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente.\ntype NodoNR = (Columna,Columna,SolNR)\n\nsolucionesNR :: Columna -> [SolNR]\nsolucionesNR n =\n  map estado (buscaAnchura sucesoresNR esFinalNR (1,n,[]))\n  where\n    estado (_,_,e) = e\n\nprimeraSolucionNR :: Columna -> SolNR\nprimeraSolucionNR =\n  head . solucionesNR\n\nnSolucionesNR :: Columna -> Int\nnSolucionesNR =\n  length . solucionesNR\n\n-- (valida sp p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n-- soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n-- ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n-- columnas). Por ejemplo,\n--    valida [(1,1)] (2,2)  ==  False\n--    valida [(1,1)] (2,3)  ==  True\nvalida :: SolNR -> (Columna,Fila) -> Bool\nvalida solp (c,r) = and [test s | s <- solp]\n  where test (c',r') = c'+r'\/=c+r &#038;&#038; c'-r'\/=c-r &#038;&#038; r'\/=r\n\n-- (sucesoresNR e) es la lista de los sucesores del estado e en el\n-- problema de las n reinas. Por ejemplo,\n--    \u03bb> sucesoresNR (1,4,[])\n--    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\nsucesoresNR :: NodoNR -> [NodoNR]\nsucesoresNR (c,n,solp) =\n  [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]\n\n-- (esFinalNR e) se verifica si e es un estado final del problema de las\n-- n reinas.\nesFinalNR :: NodoNR -> Bool\nesFinalNR (c,n,_) = c > n\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    take 3 (solucionesNR 8) `shouldBe`\n    [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],\n     [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],\n     [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]\n  it \"e2\" $\n    nSolucionesNR 8 `shouldBe` 92\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.2116 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 src.BusquedaEnAnchura import buscaAnchura\n\nColumna = int\nFila = int\nSolNR = list[tuple[Columna, Fila]]\n\n# Los nodos del problema de las n reinas son ternas formadas por la\n# columna de la \u00faltima reina colocada, el n\u00famero de columnas del\n# tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente.\nNodoNR = tuple[Columna, Columna, SolNR]\n\n# valida(sp, p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n# soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n# ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n# columnas). Por ejemplo,\n#    valida([(1,1)], (2,2))  ==  False\n#    valida([(1,1)], (2,3))  ==  True\ndef valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:\n    c, r = p\n    def test(s: tuple[Columna, Fila]) -> bool:\n        c1, r1 = s\n        return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r\n\n    return all(test(s) for s in sp)\n\n# sucesoresNR(e) es la lista de los sucesores del estado e en el\n# problema de las n reinas. Por ejemplo,\n#    >>> sucesoresNR((1,4,[]))\n#    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\ndef sucesoresNR (nd: NodoNR) -> list[NodoNR]:\n    c,n,solp = nd\n    return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]\n\n# esFinalNR(e) se verifica si e es un estado final del problema de las\n# n reinas.\ndef esFinalNR(nd: NodoNR) -> bool:\n    c, n, _ = nd\n    return c > n\n\ndef solucionesNR(n: int) -> list[SolNR]:\n    nInicial: NodoNR = (1,n,[])\n    return [e for (_, _, e) in buscaAnchura(sucesoresNR,\n                                            esFinalNR,\n                                            nInicial)]\n\ndef primeraSolucionNR(n: int) -> SolNR:\n    return solucionesNR(n)[0]\n\ndef nSolucionesNR(n: int) -> int:\n    return len(solucionesNR(n))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_nReinas() -> None:\n    assert solucionesNR(5)[:3] == \\\n        [[(1,1),(2,3),(3,5),(4,2),(5,4)],\n         [(1,1),(2,4),(3,2),(4,5),(5,3)],\n         [(1,2),(2,4),(3,1),(4,3),(5,5)]]\n    assert nSolucionesNR(5) == 10\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_nReinas()\n#    Verificado\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. El problema de la mochila (mediante espacio de estados)<\/h3>\n<p>Se tiene una mochila de capacidad de peso p y una lista de n  para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el m\u00e1ximo valor posible.<\/p>\n<p>Para solucionar el problema se definen los siguientes tipos:<\/p>\n<ul>\n<li>Una soluci\u00f3n del problema de la mochila es una lista de objetos.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type SolMoch = [Objeto]\n<\/pre>\n<ul>\n<li>Los objetos son pares formado por un peso y un valor<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Objeto = (Peso,Valor)\n<\/pre>\n<ul>\n<li>Los pesos son n\u00famero enteros<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Peso = Int\n<\/pre>\n<ul>\n<li>Los valores son n\u00fameros reales.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Valor = Float\n<\/pre>\n<ul>\n<li>Los estados del problema de la mochila son 5-tupla de la  (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el l\u00edmite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente seg\u00fan sus pesos) y s es la soluci\u00f3n parcial.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)\n<\/pre>\n<p>Usando el procedimiento de <a href=\"http:\/\/bit.ly\/2sqPtGs\">b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   mochila :: [Objeto] -> Peso -> (SolMoch,Valor)\n<\/pre>\n<p>tal que <code>mochila os l<\/code> es la soluci\u00f3n del problema de la mochila para la lista de objetos <code>os<\/code> y el l\u00edmite de capacidad <code>l<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   > mochila [(2,3),(3,5),(4,6),(5,10)] 8\n   ([(5,10.0),(3,5.0)],15.0)\n   > mochila [(2,3),(3,5),(5,6)] 10\n   ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n   > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35\n   ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)\n   > mochila [(2,2.8),(3,4.4),(5,6.1)] 10\n   ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\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_Mochila where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.List (sort)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Peso     = Int\ntype Valor    = Float\ntype Objeto   = (Peso,Valor)\ntype SolMoch  = [Objeto]\ntype NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)\n\nmochila :: [Objeto] -> Peso -> (SolMoch,Valor)\nmochila os l = (sol,v)\n  where\n    (v,_,_,_,sol) =\n      maximum (buscaProfundidad sucesoresMoch\n                                esObjetivoMoch\n                                (inicial os l))\n\n-- (inicial os l) es el estado inicial del problema de la mochila\n-- para la lista de objetos os y el l\u00edmite de capacidad l\ninicial :: [Objeto] -> Peso -> NodoMoch\ninicial os l =\n  (0,0,l,sort os,[])\n\n-- (sucesoresMoch e) es la lista de los sucesores del estado e en el\n-- problema de la mochila para la lista de objetos os y el l\u00edmite de\n-- capacidad l.\nsucesoresMoch :: NodoMoch -> [NodoMoch]\nsucesoresMoch (v,p,l,os,solp) =\n  [( v+v',\n     p+p',\n     l,\n     [o | o@(p'',_) <- os, p''>=p'],\n     (p',v'):solp )\n  | (p',v') <- os,\n    p+p' <= l]\n\n-- (esObjetivoMoch e) se verifica si e es un estado final el problema de\n-- la mochila para la lista de objetos os y el l\u00edmite de capacidad l .\nesObjetivoMoch :: NodoMoch -> Bool\nesObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    mochila [(2,3),(3,5),(4,6),(5,10)] 8\n    `shouldBe` ([(5,10.0),(3,5.0)],15.0)\n  it \"e2\" $\n    mochila [(2,3),(3,5),(5,6)] 10\n    `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n  it \"e3\" $\n    mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35\n    `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)\n  it \"e4\" $\n    mochila [(2,2.8),(3,4.4),(5,6.1)] 10\n    `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0424 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.BusquedaEnProfundidad import buscaProfundidad\n\nPeso = int\nValor = float\nObjeto = tuple[Peso, Valor]\nSolMoch = list[Objeto]\nNodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch]\n\n# inicial(os, l) es el estado inicial del problema de la mochila\n# para la lista de objetos os y el l\u00edmite de capacidad l\ndef inicial(os: list[Objeto], l: Peso) -> NodoMoch:\n    return (0,0,l,sorted(os),[])\n\n# sucesoresMoch(e) es la lista de los sucesores del estado e en el\n# problema de la mochila para la lista de objetos os y el l\u00edmite de\n# capacidad l.\ndef sucesoresMoch(n: NodoMoch) -> list[NodoMoch]:\n    (v,p,l,os,solp) = n\n    return [( v+v1,\n              p+p1,\n              l,\n              [(p2,v2) for (p2,v2) in os if p2 >= p1],\n              [(p1,v1)] + solp )\n            for (p1,v1) in os if p + p1 <= l]\n\n# esObjetivoMoch(e) se verifica si e es un estado final el problema de\n# la mochila para la lista de objetos os y el l\u00edmite de capacidad l .\ndef esObjetivoMoch(e: NodoMoch) -> bool:\n    (_, p, l, os, _) = e\n    (p_, _) = os[0]\n    return p + p_ > l\n\ndef mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]:\n    (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch,\n                                         esObjetivoMoch,\n                                         inicial(os, l)))\n    return (sol, v)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_Mochila() -> None:\n    assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \\\n        ([(5,10.0),(3,5.0)],15.0)\n    assert mochila([(2,3),(3,5),(5,6)], 10) == \\\n        ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n    assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \\\n        ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_Mochila()\n#    Verificado\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. El tipo abstracto de datos de las colas de prioridad<\/h3>\n<h4>1. El tipo abstracto de datos de las colas de prioridad<\/h4>\n<p>Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operaci\u00f3n de extracci\u00f3n siempre elige el elemento de menor prioridad.<\/p>\n<p>Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:<\/p>\n<pre lang=\"text\">\n   vacia   :: Ord a => CPrioridad a\n   inserta :: Ord a => a -> CPrioridad a -> CPrioridad a\n   primero :: Ord a => CPrioridad a -> a\n   resto   :: Ord a => CPrioridad a -> CPrioridad a\n   esVacia :: Ord a => CPrioridad a -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>vacia es la cola de prioridad vac\u00eda.<\/li>\n<li>(inserta x c) a\u00f1ade el elemento x a la cola de prioridad c.<\/li>\n<li>(primero c) es el primer elemento de la cola de prioridad c.<\/li>\n<li>(resto c) es el resto de la cola de prioridad c.<\/li>\n<li>(esVacia c) se verifica si la cola de prioridad c es vac\u00eda.<\/li>\n<\/ul>\n<p>Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n<ul>\n<li>inserta x (inserta y c) == inserta y (inserta x c)<\/li>\n<li>primero (inserta x vacia) == x<\/li>\n<li>Si x &lt;= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)<\/li>\n<li>resto (inserta x vacia) == vacia<\/li>\n<li>Si x &lt;= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))<\/li>\n<li>esVacia vacia<\/li>\n<li>not (esVacia (inserta x c))<\/li>\n<\/ul>\n<h4>2. Las colas de prioridad en Haskell<\/h4>\n<h5>2.1. El tipo abstracto de datos de las colas de prioridad en Haskell<\/h5>\n<p>El TAD de las colas de prioridadd se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/43a4s2V\">ColaDePrioridad.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ColaDePrioridad\n  (CPrioridad,\n   vacia,   -- Ord a => CPrioridad a\n   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a\n   primero, -- Ord a => CPrioridad a -> a\n   resto,   -- Ord a => CPrioridad a -> CPrioridad a\n   esVacia, -- Ord a => CPrioridad a -> Bool\n  ) where\n\nimport TAD.ColaDePrioridadConListas\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio,<br \/>\nsolo considearemos una que usa las listas.<\/p>\n<h5>2.2. Implementaci\u00f3n de las colas de prioridad mediante listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3JMp22g\">ColaDePrioridadConListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.ColaDePrioridadConListas\n  (CPrioridad,\n   vacia,   -- Ord a => CPrioridad a\n   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a\n   primero, -- Ord a => CPrioridad a -> a\n   resto,   -- Ord a => CPrioridad a -> CPrioridad a\n   esVacia, -- Ord a => CPrioridad a -> Bool\n  ) where\n\nimport Test.QuickCheck\n\n-- Colas de prioridad mediante listas.\nnewtype CPrioridad a = CP [a]\n  deriving Eq\n\n-- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de\n-- prioridad c. Por ejemplo,\n--    \u03bb> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    \"2 | 3 | 5\"\nescribeColaDePrioridad :: Show a => CPrioridad a -> String\nescribeColaDePrioridad (CP [])     = \"-\"\nescribeColaDePrioridad (CP [x])    = show x\nescribeColaDePrioridad (CP (x:xs)) = show x ++ \" | \" ++ escribeColaDePrioridad (CP xs)\n\n-- Procedimiento de escritura de colas de prioridad.\ninstance Show a => Show (CPrioridad a) where\n  show = escribeColaDePrioridad\n\n-- Ejemplo de cola de prioridad\n--    \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n--    2 | 3 | 5\n\n-- vacia es la cola de prioridad vac\u00eda. Por ejemplo,\n--    \u03bb> vacia\n--    CP []\nvacia :: Ord a => CPrioridad a\nvacia = CP []\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo el elemento x a la cola\n-- de prioridad c. Por ejemplo,\n--    \u03bb> inserta 5 (foldr inserta vacia [3,1,7,2,9])\n--    1 | 2 | 3 | 5 | 7 | 9\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a\ninserta x (CP q) = CP (ins x q)\n  where ins y []                   = [y]\n        ins y r@(e:r') | y < e     = y:r\n                       | otherwise = e:ins y r'\n\n-- (primero c) es el primer elemento de la cola de prioridad c. Por\n-- ejemplo,\n--    primero (foldr inserta vacia [3,1,7,2,9])  ==  1\nprimero :: Ord a => CPrioridad a -> a\nprimero (CP(x:_)) = x\nprimero _         = error \"primero: cola de prioridad vacia\"\n\n-- (resto c) es la cola de prioridad obtenida eliminando el primer\n-- elemento de la cola de prioridad c. Por ejemplo,\n--    \u03bb> resto (foldr inserta vacia [3,1,7,2,9])\n--    2 | 3 | 7 | 9\nresto :: Ord a => CPrioridad a -> CPrioridad a\nresto (CP (_:xs)) = CP xs\nresto _           = error \"resto: cola de prioridad vacia\"\n\n-- (esVacia c) se verifica si la cola de prioridad c es vac\u00eda. Por\n-- ejemplo,\n--    esVacia (foldr inserta vacia [3,1,7,2,9]) ==  False\n--    esVacia vacia                             ==  True\nesVacia :: Ord a => CPrioridad a -> Bool\nesVacia (CP xs) = null xs\n\n-- Generador de colas de prioridad\n-- ===============================\n\n-- genCPrioridad es un generador de colas de enteros. Por ejemplo,\n--    \u03bb> sample genCPrioridad\n--    -\n--    0 | 0\n--    4\n--    -4 | -3 | 6 | 6\n--    -7 | -6 | -2 | 0\n--    -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10\n--    -\n--    -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14\n--    -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16\n--    -\n--    -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7\ngenCPrioridad :: (Arbitrary a, Num a, Ord a) =>  Gen (CPrioridad a)\ngenCPrioridad = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacia xs)\n\n-- El tipo cola de prioridad es una instancia del arbitrario.\ninstance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where\n  arbitrary = genCPrioridad\n\n-- Propiedades de las colas de prioridad\n-- =====================================\n\n-- Propiedad. Si se a\u00f1ade dos elementos a una cola de prioridad se\n-- obtiene la misma cola de prioridad idependientemente del orden en\n-- que se a\u00f1adan los elementos.\nprop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool\nprop_inserta_conmuta x y c =\n  inserta x (inserta y c) == inserta y (inserta x c)\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_inserta_conmuta\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. La cabeza de la cola de prioridad obtenida a\u00f1adiendo un\n-- elemento x a la cola de prioridad vac\u00eda es x.\nprop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool\nprop_primero_inserta_vacia x _ =\n  primero (inserta x vacia) == x\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_primero_inserta_vacia\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. El primer elemento de una cola de prioridad c no cambia\n-- cuando se le a\u00f1ade un elemento mayor o igual que alg\u00fan elemento de c.\nprop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property\nprop_primero_inserta x y c =\n  x <= y ==> primero (inserta y c') == primero c'\n  where c' = inserta x c\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_primero_inserta\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. El resto de a\u00f1adir un elemento a la cola de prioridad\n-- vac\u00eda es la cola vac\u00eda.\nprop_resto_inserta_vacia :: Int -> Bool\nprop_resto_inserta_vacia x =\n  resto (inserta x vacia) == vacia\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_resto_inserta_vacia\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. El resto de la cola de prioridad obtenida a\u00f1adiendo un\n-- elemento y a una cola c' (que tiene alg\u00fan elemento menor o igual que\n-- y) es la cola que se obtiene a\u00f1adiendo y al resto de c'.\nprop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property\nprop_resto_inserta x y c =\n  x <= y ==> resto (inserta y c') == inserta y (resto c')\n  where c' = inserta x c\n\n-- Comprobaci\u00f3n:\n--    \u03bb> quickCheck prop_resto_inserta\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. vacia es una cola vac\u00eda.\nprop_vacia_es_vacia :: Bool\nprop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int)\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_vacia_es_vacia\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. Si se a\u00f1ade un elemento a una cola de prioridad se obtiene\n-- una cola no vac\u00eda.\nprop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool\nprop_inserta_no_es_vacia x c =\n  not (esVacia (inserta x c))\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_inserta_no_es_vacia\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>3. Las colas de prioridad en Python<\/h4>\n<h5>3.1. El tipo abstracto de las colas de prioridad en Python<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3pFIxTy\">ColaDePrioridad.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n   'CPrioridad',\n   'vacia',\n   'inserta',\n   'primero',\n   'resto',\n   'esVacia',\n    ]\n\nfrom src.TAD.ColaDePrioridadConListas import (CPrioridad, esVacia, inserta,\n                                              primero, resto, vacia)\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos solo una que usa las listas.<\/p>\n<h5>3.2. Implementaci\u00f3n de las colas de prioridad mediante listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3PJXWg4\">ColaDePrioridadConListas.py<\/a> en el que se define la clase CPrioridad con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>inserta(x) a\u00f1ade x a la cola.<\/li>\n<li>primero() es el primero de la cola.<\/li>\n<li>resto() elimina el primero de la cola.<\/li>\n<li>esVacia() se verifica si la cola es vac\u00eda.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> c = CPrioridad()\n   >>> c\n   -\n   >>> c.inserta(5)\n   >>> c.inserta(2)\n   >>> c.inserta(3)\n   >>> c.inserta(4)\n   >>> c\n   2 | 3 | 4 | 5\n   >>> c.primero()\n   2\n   >>> c.resto()\n   >>> c\n   3 | 4 | 5\n   >>> c.esVacia()\n   False\n   >>> c = CPrioridad()\n   >>> c.esVacia()\n   True\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> vacia()\n   -\n   >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))\n   2 | 3 | 4 | 5\n   >>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   2\n   >>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   3 | 4 | 5\n   >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   False\n   >>> esVacia(vacia())\n   True\n<\/pre>\n<p>Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificaci\u00f3n.<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n   'CPrioridad',\n   'vacia',\n   'inserta',\n   'primero',\n   'resto',\n   'esVacia',\n]\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, Protocol, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# Clase de las colas de prioridad mediante listas\n# ===============================================\n\n@dataclass\nclass CPrioridad(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos de la cola separados por \" | \".\n        Si la cola est\u00e1 vac\u00eda, devuelve \"-\".\n        \"\"\"\n        if not self._elementos:\n            return '-'\n        return ' | '.join(str(x) for x in self._elementos)\n\n    def esVacia(self) -> bool:\n        \"\"\"\n        Comprueba si la cola est\u00e1 vac\u00eda.\n\n        Devuelve True si la cola est\u00e1 vac\u00eda, False en caso contrario.\n        \"\"\"\n        return not self._elementos\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        Inserta el elemento x en la cola de prioridad.\n        \"\"\"\n        self._elementos.append(x)\n        self._elementos.sort()\n\n    def primero(self) -> A:\n        \"\"\"\n        Devuelve el primer elemento de la cola.\n        \"\"\"\n        return self._elementos[0]\n\n    def resto(self) -> None:\n        \"\"\"\n        Elimina el primer elemento de la cola\n        \"\"\"\n        self._elementos.pop(0)\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> CPrioridad[A]:\n    \"\"\"\n    Crea y devuelve una cola vac\u00eda de tipo A.\n    \"\"\"\n    c: CPrioridad[A] = CPrioridad()\n    return c\n\ndef inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]:\n    \"\"\"\n    Inserta un elemento x en la cola c y devuelve una nueva cola con\n    el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef esVacia(c: CPrioridad[A]) -> bool:\n    \"\"\"\n    Devuelve True si la cola est\u00e1 vac\u00eda, False si no lo est\u00e1.\n    \"\"\"\n    return c.esVacia()\n\ndef primero(c: CPrioridad[A]) -> A:\n    \"\"\"\n    Devuelve el primer elemento de la cola c.\n    \"\"\"\n    return c.primero()\n\ndef resto(c: CPrioridad[A]) -> CPrioridad[A]:\n    \"\"\"\n    Elimina el primer elemento de la cola c y devuelve una copia de la\n    cola resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.resto()\n    return _aux\n\n# Generador de colas de prioridad\n# ===============================\n\ndef colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]:\n    \"\"\"\n    Genera una estrategia de b\u00fasqueda para generar colas de enteros de\n    forma aleatoria.\n\n    Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n    luego se convierte en una instancia de la clase cola.\n    \"\"\"\n    return st.lists(st.integers()).map(CPrioridad)\n\n# Comprobaci\u00f3n de las propiedades de las colas\n# ============================================\n\n# Las propiedades son\n@given(c=colaAleatoria(), x=st.integers(), y=st.integers())\ndef test_cola1(c: CPrioridad[int], x: int, y: int) -> None:\n    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))\n    assert primero(inserta(x, vacia())) == x\n    assert resto(inserta(x, vacia())) == vacia()\n    assert esVacia(vacia())\n    assert not esVacia(inserta(x, c))\n\n@given(c=colaAleatoria(), x=st.integers(), y=st.integers())\ndef test_cola2(c: CPrioridad[int], x: int, y: int) -> None:\n    assume(not y < x)\n    assert primero(inserta(y, (inserta(x, c)))) == \\\n        primero(inserta(x,c))\n    assert resto(inserta(y, (inserta(x, c)))) == \\\n        inserta(y, resto(inserta(x, c)))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q ColaDePrioridadConListas.py\n#    2 passed in 0.54s\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. B\u00fasqueda por primero el mejor<\/h3>\n<p>En la b\u00fasqueda por primero el mejor se supone que los estados est\u00e1n ordenados 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   buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]\n<\/pre>\n<p>tal que <code>buscaPM 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 por primero el mejor.<\/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 BusquedaPrimeroElMejor (buscaPM)  where\n\nimport TAD.ColaDePrioridad (esVacia, inserta, primero, resto, vacia)\n\nbuscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]\nbuscaPM sucesores esFinal x = busca' (inserta x vacia) where\n  busca' c\n    | esVacia c = []\n    | esFinal (primero c) = primero c : busca' (resto c)\n    | otherwise = busca' (foldr inserta (resto c) (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                                     resto, 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 buscaPM(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        if esFinal(primero(c)):\n            return primero(c)\n\n        es = sucesores(primero(c))\n        c = reduce(lambda x, y: inserta(y, x), es, resto(c))\n\n    return None\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. El problema del 8 puzzle<\/h3>\n<p>Para el 8-puzzle se usa un caj\u00f3n cuadrado en el que hay situados  bloques cuadrados. El cuadrado restante est\u00e1 sin rellenar. Cada bloque tiene un n\u00famero. Un bloque adyacente al hueco puede deslizarse hacia \u00e9l. El juego consiste en transformar la posici\u00f3n inicial en la posici\u00f3n final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:<\/p>\n<pre lang=\"text\">\n   +---+---+---+                   +---+---+---+\n   |   | 1 | 3 |                   | 1 | 2 | 3 |\n   +---+---+---+                   +---+---+---+\n   | 8 | 2 | 4 |                   | 8 |   | 4 |\n   +---+---+---+                   +---+---+---+\n   | 7 | 5 | 5 |                   | 7 | 6 | 5 |\n   +---+---+---+                   +---+---+---+\n   Estado inicial                  Estado final\n<\/pre>\n<p>Para solucionar el problema se definen los siguientes tipos:<\/p>\n<ul>\n<li><code>Tablero<\/code> es una matriz de n\u00famero enteros (que representan las piezas en<br \/>\ncada posici\u00f3n y el 0 representa el hueco):<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Tablero  = Matrix Int\n<\/pre>\n<ul>\n<li><code>Estado<\/code> es una listas de tableros [t_n,&#8230;,t_1] tal que t_i es un<br \/>\nsucesor de t_(i-1).<\/li>\n<\/ul>\n<pre lang=\"text\">\n     newtype Estado = Est [Tablero]\n       deriving Show\n<\/pre>\n<p>Usando el procedimiento de <a href=\"???\">b\u00fasqueda por primero el mejor<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   solucion_8puzzle :: Tablero -> [Tablero]\n<\/pre>\n<p>tal que <code>(solucion_8puzzle t)<\/code> es la soluci\u00f3n del problema del problema del 8 puzzle a partir del tablero <code>t<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]])\n   [\u250c       \u2510  \u250c       \u2510  \u250c       \u2510\n    \u2502 0 1 3 \u2502  \u2502 1 0 3 \u2502  \u2502 1 2 3 \u2502\n    \u2502 8 2 4 \u2502  \u2502 8 2 4 \u2502  \u2502 8 0 4 \u2502\n    \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n    \u2514       \u2518, \u2514       \u2518, \u2514       \u2518]\n   \u03bb> length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]]))\n   21\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 BPM_8Puzzle where\n\nimport BusquedaPrimeroElMejor (buscaPM)\nimport Data.Matrix (Matrix, (!), fromLists, setElem, toLists)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Tablero  = Matrix Int\n\nnewtype Estado = Est [Tablero]\n  deriving (Eq, Show)\n\nsolucion_8puzzle :: Tablero -> [Tablero]\nsolucion_8puzzle t = reverse ts\n  where (Est ts) = head (buscaPM sucesores\n                                 esFinal\n                                 (inicial t))\n\n-- Estado inicial\n-- ==============\n\n-- (inicial t) es el estado inicial del problema del 8 puzzle a partir del\n-- tablero t.\ninicial :: Tablero -> Estado\ninicial t = Est [t]\n\n-- Estado final\n-- ============\n\n-- (esFinal e) se verifica si e es un estado final.\nesFinal :: Estado -> Bool\nesFinal (Est (n:_)) = n == tableroFinal\n\n-- tableroFinal es el estado tablero final del 8 puzzle.\ntableroFinal :: Tablero\ntableroFinal = fromLists [[1,2,3],\n                          [8,0,4],\n                          [7,6,5]]\n\n-- Sucesores\n-- =========\n\n-- (sucesores e) es la lista de sucesores del estado e. Por ejemplo,\n--    \u03bb> sucesores (Est [fromLists [[2,1,3],[8,0,4],[7,6,5]]])\n--    [Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 0 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 8 1 4 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518],\n--     Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 8 6 4 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 0 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518],\n--     Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 0 8 4 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518],\n--     Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 8 4 0 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518]]\nsucesores :: Estado -> [Estado]\nsucesores (Est e@(t:_)) =\n  [Est (t':e) | t' <- tablerosSucesores t,\n                t' `notElem` e]\n\n-- (tablerosSucesores t) es la lista de los tableros sucesores del\n-- tablero t. Por ejemplo,\n--    \u03bb> tablerosSucesores (fromLists [[2,1,3],[8,0,4],[7,6,5]])\n--    [\u250c       \u2510  \u250c       \u2510  \u250c       \u2510  \u250c       \u2510\n--     \u2502 2 0 3 \u2502  \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--     \u2502 8 1 4 \u2502  \u2502 8 6 4 \u2502  \u2502 0 8 4 \u2502  \u2502 8 4 0 \u2502\n--     \u2502 7 6 5 \u2502  \u2502 7 0 5 \u2502  \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--     \u2514       \u2518, \u2514       \u2518, \u2514       \u2518, \u2514       \u2518]\ntablerosSucesores :: Tablero -> [Tablero]\ntablerosSucesores t =\n  [intercambia t p q | q <- posicionesVecinas p]\n  where p = posicionHueco t\n\n-- Una posici\u00f3n es un par de enteros.\ntype Posicion = (Int,Int)\n\n-- (posicionesVecinas p) son las posiciones de la matriz cuadrada de\n-- dimensi\u00f3n 3 que se encuentran encima, abajo, a la izquierda y a la\n-- derecha de los posici\u00f3n p. Por ejemplo,\n--    \u03bb> posicionesVecinas (2,2)\n--    [(1,2),(3,2),(2,1),(2,3)]\n--    \u03bb> posicionesVecinas (1,2)\n--    [(2,2),(1,1),(1,3)]\n--    \u03bb> posicionesVecinas (1,1)\n--    [(2,1),(1,2)]\nposicionesVecinas :: Posicion -> [Posicion]\nposicionesVecinas (i,j) =\n  [(i-1,j) | i > 1] ++\n  [(i+1,j) | i < 3] ++\n  [(i,j-1) | j > 1] ++\n  [(i,j+1) | j < 3]\n\n-- (posicionHueco t) es la posici\u00f3n del hueco en el tablero t. Por\n-- ejemplo,\n--    \u03bb> posicionHueco (fromLists [[2,1,3],[8,0,4],[7,6,5]])\n--    (2,2)\nposicionHueco :: Tablero -> Posicion\nposicionHueco t =\n  posicionElemento t 0\n\n-- (posicionElemento t a) es la posici\u00f3n de elemento a en el tablero\n-- t. Por ejemplo,\n--    \u03bb> posicionElemento (fromLists [[2,1,3],[8,0,4],[7,6,5]]) 4\n--    (2,3)\nposicionElemento :: Tablero -> Int -> Posicion\nposicionElemento t a =\n  head [(i,j) | i <- [1..3],\n                j <- [1..3],\n                t ! (i,j) == a]\n\n-- (intercambia t p1 p2) es el tablero obtenido intercambiando en t los\n-- elementos que se encuentran en las posiciones p1 y p2. Por ejemplo,\n--    \u03bb> intercambia (fromLists [[2,1,3],[8,0,4],[7,6,5]]) (1,2) (2,2)\n--    \u250c       \u2510\n--    \u2502 2 0 3 \u2502\n--    \u2502 8 1 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\nintercambia :: Tablero -> Posicion -> Posicion -> Tablero\nintercambia t p1 p2 =\n  setElem a2 p1 (setElem a1 p2 t)\n  where a1 = t ! p1\n        a2 = t ! p2\n\n-- Heur\u00edstica\n-- ==========\n\n-- (heuristica t) es la suma de la distancia Manhatan desde la posici\u00f3n de\n-- cada objeto del tablero a su posici\u00f3n en el tablero final. Por\n-- ejemplo,\n--    \u03bb> heuristica (fromLists [[0,1,3],[8,2,4],[7,6,5]])\n--    4\nheuristica :: Tablero  -> Int\nheuristica t =\n  sum [distancia (posicionElemento t i)\n                 (posicionElemento tableroFinal i)\n      | i <- [0..8]]\n\n-- (distancia p1 p2) es la distancia Manhatan entre las posiciones p1 y\n-- p2. Por ejemplo,\n--    distancia (2,7) (4,1)  ==  8\ndistancia :: Posicion -> Posicion -> Int\ndistancia (x1,y1) (x2,y2) = abs (x1-x2) + abs (y1-y2)\n\n-- Comparaci\u00f3n de estados\n-- ======================\n\n-- Un estado es menor o igual que otro si tiene la heur\u00edstica de su\n-- primer tablero es menor o que la del segundo o so iguales y el\n-- primero es m\u00e1s corto.\ninstance Ord Estado where\n  Est (t1:ts1) <= Est (t2:ts2) = (heuristica t1 < heuristica t2) ||\n                                 ((heuristica t1 == heuristica t2) &#038;&#038;\n                                  (length ts1 <= length ts2))\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    map toLists (solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]]))\n   `shouldBe` [[[0,1,3],\n                [8,2,4],\n                [7,6,5]],\n               [[1,0,3],\n                [8,2,4],\n                [7,6,5]],\n               [[1,2,3],\n                [8,0,4],\n                [7,6,5]]]\n  it \"e2\" $\n    length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]]))\n    `shouldBe` 21\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.1361 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 copy import deepcopy\nfrom typing import Optional\n\nfrom src.BusquedaPrimeroElMejor import buscaPM\n\nTablero = list[list[int]]\n\n# Tablero final\n# =============\n\n# tableroFinal es el tablero final del 8 puzzle.\ntableroFinal: Tablero = [[1,2,3],\n                         [8,0,4],\n                         [7,6,5]]\n\n# Posiciones\n# ==========\n\n# Una posici\u00f3n es un par de enteros.\nPosicion = tuple[int,int]\n\n# Heur\u00edstica\n# ==========\n\n# distancia(p1, p2) es la distancia Manhatan entre las posiciones p1 y\n# p2. Por ejemplo,\n#    >>> distancia((2,7), (4,1))\n#    8\ndef distancia(p1: Posicion, p2: Posicion) -> int:\n    (x1, y1) = p1\n    (x2, y2) = p2\n    return abs(x1-x2) + abs (y1-y2)\n\n# posicionElemento(t, a) es la posici\u00f3n de elemento a en el tablero\n# t. Por ejemplo,\n#    \u03bb> posicionElemento([[2,1,3],[8,0,4],[7,6,5]], 4)\n#    (1, 2)\ndef posicionElemento(t: Tablero, a: int) -> Posicion:\n    for i in range(0, 3):\n        for j in range(0, 3):\n            if t[i][j] == a:\n                return (i, j)\n    return (4, 4)\n\n# posicionHueco(t) es la posici\u00f3n del hueco en el tablero t. Por\n# ejemplo,\n#    >>> posicionHueco([[2,1,3],[8,0,4],[7,6,5]])\n#    (1, 1)\ndef posicionHueco(t: Tablero) -> Posicion:\n    return posicionElemento(t, 0)\n\n# heuristica(t) es la suma de la distancia Manhatan desde la posici\u00f3n de\n# cada objeto del tablero a su posici\u00f3n en el tablero final. Por\n# ejemplo,\n#    >>> heuristica([[0,1,3],[8,2,4],[7,6,5]])\n#    4\ndef heuristica(t: Tablero) -> int:\n    return sum((distancia(posicionElemento(t, i),\n                          posicionElemento(tableroFinal, i))\n                for i in range(0, 10)))\n\n# Estados\n# =======\n\n# Un estado es una tupla (h, n, ts), donde ts es una listas de tableros\n# [t_n,...,t_1] tal que t_i es un sucesor de t_(i-1) y h es la\n# heur\u00edstica de t_n.\nEstado = tuple[int, int, list[Tablero]]\n\n# Estado inicial\n# ==============\n\n# inicial(t) es el estado inicial del problema del 8 puzzle a partir del\n# tablero t.\ndef inicial(t: Tablero) -> Estado:\n    return (heuristica(t), 1, [t])\n\n# Estado final\n# ============\n\n# esFinal(e) se verifica si e es un estado final.\ndef esFinal(e: Estado) -> bool:\n    (_, _, ts) = e\n    return ts[0] == tableroFinal\n\n# Sucesores\n# =========\n\n# posicionesVecinas(p) son las posiciones de la matriz cuadrada de\n# dimensi\u00f3n 3 que se encuentran encima, abajo, a la izquierda y a la\n# derecha de los posici\u00f3n p. Por ejemplo,\n#    >>> posicionesVecinas((1,1))\n#    [(0, 1), (2, 1), (1, 0), (1, 2)]\n#    >>> posicionesVecinas((0,1))\n#    [(1, 1), (0, 0), (0, 2)]\n#    >>> posicionesVecinas((0,0))\n#    [(1, 0), (0, 1)]\ndef posicionesVecinas(p: Posicion) -> list[Posicion]:\n    (i, j) = p\n    vecinas = []\n    if i > 0:\n        vecinas.append((i - 1, j))\n    if i < 2:\n        vecinas.append((i + 1, j))\n    if j > 0:\n        vecinas.append((i, j - 1))\n    if j < 2:\n        vecinas.append((i, j + 1))\n    return vecinas\n\n# intercambia(t,p1, p2) es el tablero obtenido intercambiando en t los\n# elementos que se encuentran en las posiciones p1 y p2. Por ejemplo,\n#    >>> intercambia([[2,1,3],[8,0,4],[7,6,5]], (0,1), (1,1))\n#    [[2, 0, 3], [8, 1, 4], [7, 6, 5]]\ndef intercambia(t: Tablero, p1: Posicion, p2: Posicion) -> Tablero:\n    (i1, j1) = p1\n    (i2, j2) = p2\n    t1 = deepcopy(t)\n    a1 = t1[i1][j1]\n    a2 = t1[i2][j2]\n    t1[i1][j1] = a2\n    t1[i2][j2] = a1\n    return t1\n\n# tablerosSucesores(t) es la lista de los tablrtos sucesores del\n# tablero t. Por ejemplo,\n#    >>> tablerosSucesores([[2,1,3],[8,0,4],[7,6,5]])\n#    [[[2, 0, 3], [8, 1, 4], [7, 6, 5]],\n#     [[2, 1, 3], [8, 6, 4], [7, 0, 5]],\n#     [[2, 1, 3], [0, 8, 4], [7, 6, 5]],\n#     [[2, 1, 3], [8, 4, 0], [7, 6, 5]]]\ndef tablerosSucesores(t: Tablero) -> list[Tablero]:\n    p = posicionHueco(t)\n    return [intercambia(t, p, q) for q in posicionesVecinas(p)]\n\n# (sucesores e) es la lista de sucesores del estado e. Por ejemplo,\n#    >>> t1 = [[0,1,3],[8,2,4],[7,6,5]]\n#    >>> es = sucesores((heuristica(t1), 1, [t1]))\n#    >>> es\n#    [(4, 2, [[[8, 1, 3],\n#              [0, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]]),\n#     (2, 2, [[[1, 0, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]])]\n#    >>> sucesores(es[1])\n#    [(0, 3, [[[1, 2, 3],\n#              [8, 0, 4],\n#              [7, 6, 5]],\n#             [[1, 0, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]]),\n#     (4, 3, [[[1, 3, 0],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[1, 0, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]])]\ndef sucesores(e: Estado) -> list[Estado]:\n    (_, n, ts) = e\n    return [(heuristica(t1), n+1, [t1] + ts)\n            for t1 in tablerosSucesores(ts[0])\n            if t1 not in ts]\n\n# Soluci\u00f3n\n# ========\n\ndef solucion_8puzzle(t: Tablero) -> Optional[list[Tablero]]:\n    r = buscaPM(sucesores, esFinal, inicial(t))\n    if r is None:\n        return None\n    (_, _, ts) = r\n    ts.reverse()\n    return ts\n\n# Verificaci\u00f3n\n# ============\n\ndef test_8puzzle() -> None:\n    assert solucion_8puzzle([[8,1,3],[0,2,4],[7,6,5]]) == \\\n        [[[8, 1, 3], [0, 2, 4], [7, 6, 5]],\n         [[0, 1, 3], [8, 2, 4], [7, 6, 5]],\n         [[1, 0, 3], [8, 2, 4], [7, 6, 5]],\n         [[1, 2, 3], [8, 0, 4], [7, 6, 5]]]\n\n# La verificaci\u00f3n es\n#    src> poetry run pytest -q BPM_8Puzzle.py\n#    1 passed in 0.10s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. El problema de las n reinas (mediante b\u00fasqueda por anchura en espacios de estados) 2. El problema de la mochila (mediante espacio de estados) 3. El tipo abstracto de datos de las colas de prioridad 4. B\u00fasqueda por primero el mejor 5&#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\/7957"}],"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=7957"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7957\/revisions"}],"predecessor-version":[{"id":7958,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7957\/revisions\/7958"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7957"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7957"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7957"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}