El mes en Exercitium (Ejercicios con Haskell y Python, septiembre de 2023)
Este mes he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Búsqueda en escalada
- 2. Problema de las monedas por búsqueda en escalada
- 3. El algoritmo de Prim del árbol de expansión mínimo por escalada
- 4. El problema del granjero mediante búsqueda en espacio de estado
- 5. El problema de las fichas mediante búsqueda en espacio de estado
- 6. El problema del calendario mediante búsqueda en espacio de estado
A continuación se muestran las soluciones.
1. Búsqueda en escalada
En la búsqueda en escalada se supone que los estados están mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.
Definir la función
1 |
buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] |
tal que (buscaEscalada s o e)
es la lista de soluciones del problema de espacio de estado definido por la función sucesores s
, el objetivo o
y estado inicial e
, obtenidas buscando en escalada.
Nota: La búsqueda en escalada se aplica en el problema de las monedas.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 |
module BusquedaEnEscalada (buscaEscalada) where import TAD.ColaDePrioridad (esVacia, inserta, primero, vacia) buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] buscaEscalada sucesores esFinal x = busca' (inserta x vacia) where busca' c | esVacia c = [] | esFinal (primero c) = [primero c] | otherwise = busca' (foldr inserta vacia (sucesores (primero c))) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
from __future__ import annotations from abc import abstractmethod from functools import reduce from typing import Callable, Optional, Protocol, TypeVar from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero, vacia) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) def buscaEscalada(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> Optional[A]: c: CPrioridad[A] = inserta(inicial, vacia()) while not esVacia(c): x = primero(c) if esFinal(x): return x c = reduce(lambda x, y: inserta(y, x), sucesores(x), vacia()) return None |
2. Problema de las monedas por búsqueda en escalada
El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor número de monedas disponibles. Se supone que se posee un número ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como mínimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).
En la representación se usarán los siguientes tipos:
Moneda
, que es un número entero representado el valor de la monedaSolucion
, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista más corta con la misma suma.
Usando la búsqueda en escalada, definir la función
1 |
cambio :: Int -> Solucion |
tal que (cambio n)
es la solución del problema de las monedas, para obtener la cantidad n
, por búsqueda en escalada. Por ejemplo,
1 |
cambio 199 == [2,2,5,20,20,50,100] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
module Escalada_Monedas where import BusquedaEnEscalada import Test.Hspec (Spec, hspec, it, shouldBe) -- Las monedas son números enteros. type Moneda = Int -- monedas es la lista del tipo de monedas disponibles. Se supone que -- hay un número infinito de monedas de cada tipo. monedas :: [Moneda] monedas = [1,2,5,10,20,50,100] -- Las soluciones son listas de monedas. type Solucion = [Moneda] -- Los estados son pares formados por la cantidad que falta y la lista -- de monedas usadas. type Estado = (Int, [Moneda]) -- (inicial n) es el estado inicial del problema de las monedas, para -- obtener la cantidad n. inicial :: Int -> Estado inicial n = (n, []) -- (esFinal e) se verifica si e es un estado final del problema -- de las monedas. esFinal :: Estado -> Bool esFinal (v,_) = v == 0 -- (sucesores e) es la lista de los sucesores del estado e en el -- problema de las monedas. Por ejemplo, -- λ> sucesores (199,[]) -- [(198,[1]),(197,[2]),(194,[5]),(189,[10]), -- (179,[20]),(149,[50]),(99,[100])] sucesores :: Estado -> [Estado] sucesores (r,p) = [(r-c,c:p) | c <- monedas, r-c >= 0] cambio :: Int -> Solucion cambio n = snd (head (buscaEscalada sucesores esFinal (inicial n))) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ cambio 199 `shouldBe` [2,2,5,20,20,50,100] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0003 seconds -- 1 example, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada # Las monedas son números enteros. Moneda = int # monedas es la lista del tipo de monedas disponibles. Se supone que # hay un número infinito de monedas de cada tipo. monedas: list[Moneda] = [1,2,5,10,20,50,100] # Las soluciones son listas de monedas. Solucion = list[Moneda] # Los estados son pares formados por la cantidad que falta y la lista # de monedas usadas. Estado = tuple[int, list[Moneda]] # inicial(n) es el estado inicial del problema de las monedas, para # obtener la cantidad n. def inicial(n: int) -> Estado: return (n, []) # esFinal(e) se verifica si e es un estado final del problema # de las monedas. def esFinal(e: Estado) -> bool: return e[0] == 0 # sucesores(e) es la lista de los sucesores del estado e en el # problema de las monedas. Por ejemplo, # λ> sucesores((199,[])) # [(198,[1]),(197,[2]),(194,[5]),(189,[10]), # (179,[20]),(149,[50]),(99,[100])] def sucesores(e: Estado) -> list[Estado]: (r,p) = e return [(r - c, [c] + p) for c in monedas if r - c >= 0] def cambio(n: int) -> Optional[Solucion]: r = buscaEscalada(sucesores, esFinal, inicial(n)) if r is None: return None return r[1] # Verificación # ============ def test_monedas() -> None: assert cambio(199) == [2,2,5,20,20,50,100] # La verificación es # src> poetry run pytest -q Escalada_Monedas.py # 1 passed in 0.12s |
3. El algoritmo de Prim del árbol de expansión mínimo por escalada
El algoritmo de Prim calcula un recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Prim funciona de la siguiente manera:
- Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
- Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
- Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)
Usando la búsqueda en escalada el tipo abstracto de datos de los grafos, definir la función
1 |
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] |
tal que prim g
es el árbol de expansión mínimo del grafo g
calculado mediante el algoritmo de Prim con bñusqueda en escalada. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] |
entonces
1 2 3 4 |
prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] prim g2 == [(2,5,32),(2,4,12),(1,2,13),(1,3,11)] prim g3 == [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)] prim g4 == [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
module Escalada_Prim where import BusquedaEnEscalada (buscaEscalada) import TAD.Grafo (Grafo, Orientacion (ND), aristaEn, creaGrafo, nodos, peso) import Data.Ix (Ix) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] -- Una arista esta formada por dos vértices junto con su peso. type Arista a b = (a,a,b) -- Un estado (Estado (p,t,r,aem)) está formado por el peso p de la -- última arista añadida el árbol de expansión mínimo (aem), la lista t -- de nodos del grafo que están en el aem, la lista r de nodos del -- grafo que no están en el aem y el aem. type Estado a b = (b,[a],[a],[Arista a b]) -- (inicial g) es el estado inicial correspondiente al grafo g. inicial :: (Ix a, Num b, Ord b) => Grafo a b -> Estado a b inicial g = (0,[n],ns,[]) where (n:ns) = nodos g -- (esFinal e) se verifica si e es un estado final; es decir, si no -- queda ningún elemento en la lista de nodos sin colocar en el árbol de -- expansión mínimo. esFinal :: Estado a b -> Bool esFinal (_,_,[],_) = True esFinal _ = False -- (sucesores g e) es la lista de los sucesores del estado e en el -- grafo g. Por ejemplo, -- λ> sucesores g1 (0,[1],[2..5],[]) -- [(12,[2,1],[3,4,5],[(1,2,12)]), -- (34,[3,1],[2,4,5],[(1,3,34)]), -- (78,[5,1],[2,3,4],[(1,5,78)])] sucesores :: (Ix a, Num b, Eq b) => Grafo a b -> Estado a b -> [Estado a b] sucesores g (_,t,r,aem) = [(peso x y g, y:t, delete y r, (x,y,peso x y g):aem) | x <- t , y <- r, aristaEn g (x,y)] prim :: (Ix a, Num b, Ord b) => Grafo a b -> [Arista a b] prim g = sol where [(_,_,_,sol)] = buscaEscalada (sucesores g) esFinal (inicial g) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ prim g1 `shouldBe` [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] it "e2" $ prim g2 `shouldBe` [(2,5,32),(2,4,12),(1,2,13),(1,3,11)] it "e3" $ prim g3 `shouldBe` [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)] it "e4" $ prim g4 `shouldBe` [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0043 seconds -- 4 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristaEn, creaGrafo, nodos, peso) g1 = creaGrafo (Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) g2 = creaGrafo (Orientacion.ND, (1,5), [((1,2),13),((1,3),11),((1,5),78), ((2,4),12),((2,5),32), ((3,4),14),((3,5),44), ((4,5),93)]) g3 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),7), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) g4 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),1), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) Arista = tuple[tuple[Vertice, Vertice], Peso] # Un nodo (Estado (p,t,r,aem)) está formado por el peso p de la última # arista añadida el árbol de expansión mínimo (aem), la lista t # de nodos del grafo que están en el aem, la lista r de nodos del # grafo que no están en el aem y el aem. Estado = tuple[Peso, list[Vertice], list[Vertice], list[Arista]] # inicial(g) es el estado inicial correspondiente al grafo g. def inicial(g: Grafo) -> Estado: n, *ns = nodos(g) return (0, [n], ns, []) # esFinal(e) se verifica si e es un estado final; es decir, si no # queda ningún elemento en la lista de nodos sin colocar en el árbol de # expansión mínimo. def esFinal(e: Estado) -> bool: return e[2] == [] # sucesores(g, e) es la lista de los sucesores del estado e en el # grafo g. Por ejemplo, # λ> sucesores(g1, (0,[1],[2,3,4,5],[])) # [(12,[2,1],[3,4,5],[(1,2,12)]), # (34,[3,1],[2,4,5],[(1,3,34)]), # (78,[5,1],[2,3,4],[(1,5,78)])] def sucesores(g: Grafo, e: Estado) -> list[Estado]: (_,t,r,aem) = e return [(peso(x, y, g), [y] + t, [x for x in r if x != y], [((x,y),peso(x, y, g))] + aem) for x in t for y in r if aristaEn(g, (x, y))] def prim(g: Grafo) -> Optional[list[Arista]]: r = buscaEscalada(lambda e: sucesores(g, e), esFinal, inicial(g)) if r is None: return None return r[3] # Verificación # ============ def test_prim() -> None: assert prim(g1) == [((2,4),55),((1,3),34),((2,5),32),((1,2),12)] assert prim(g2) == [((2,5),32),((2,4),12),((1,2),13),((1,3),11)] assert prim(g3) == [((5,7),9),((2,3),7),((5,4),5),((6,5),3),((1,6),6),((1,2),5)] assert prim(g4) == [((5,7),9),((5,4),5),((5,3),1),((6,5),3),((1,6),6),((1,2),5)] print("Verificado") # La verificación es # >>> test_prim() # Verificado |
4. El problema del granjero mediante búsqueda en espacio de estado
Un granjero está parado en un lado del río y con él tiene un una cabra y una repollo. En el río hay un barco pequeño. El desea cruzar el río con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un artículo. Si deja la cabra con la repollo sola en un lado del río la cabra comerá la repollo. Si deja el lobo y la cabra en un lado, el lobo se comerá a la cabra. ¿Cómo puede cruzar el granjero el río con los tres artículos, sin que ninguno se coma al otro?
Para representar el problema se definen los siguientes tipos de dato:
Orilla
con dos constructores (I
yD
) que representan las orillas izquierda y derecha, respectivamente.Estado
que es una tupla que representa en qué orilla se encuentra cada uno de los elementos (granjero, lobo, cabra, repollo). Por ejemplo,(I,D,D,I)
representa que el granjero está en la izquierda, que el lobo está en la derecha, que la cabra está en la derecha y el repollo está en la izquierda.
Usando el procedimiento de búsqueda en profundidad, definir la función
1 |
granjero :: [[Estado]] |
tal que granjero
son las soluciones del problema del granjero mediante el patrón de búsqueda en espacio de estados. Por ejemplo,
1 2 3 4 5 |
λ> head granjero [(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)] λ> length granjero 2 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
module BEE_El_problema_del_granjero where import BusquedaEnProfundidad (buscaProfundidad) import Test.Hspec (Spec, hspec, it, shouldBe) data Orilla = I | D deriving (Eq, Show) type Estado = (Orilla,Orilla,Orilla,Orilla) -- (seguro e) se verifica si el estado e es seguro; es decir, que no -- puede estar en una orilla el lobo con la cabra sin el granjero ni la -- cabra con el repollo sin el granjero. Por ejemplo, -- seguro (I,D,D,I) == False -- seguro (D,D,D,I) == True -- seguro (D,D,I,I) == False -- seguro (I,D,I,I) == True seguro :: Estado -> Bool seguro (g,l,c,r) = not (g /= c && (c == l || c == r)) -- (opuesta x) es la opuesta de la orilla x. Por ejemplo -- opuesta I = D opuesta :: Orilla -> Orilla opuesta I = D opuesta D = I -- (sucesoresE e) es la lista de los sucesores seguros del estado e. Por -- ejemplo, -- sucesoresE (I,I,I,I) == [(D,I,D,I)] -- sucesoresE (D,I,D,I) == [(I,I,D,I),(I,I,I,I)] sucesoresE :: Estado -> [Estado] sucesoresE e = [mov e | mov <- [m1,m2,m3,m4], seguro (mov e)] where m1 (g,l,c,r) = (opuesta g, l, c, r) m2 (g,l,c,r) = (opuesta g, opuesta l, c, r) m3 (g,l,c,r) = (opuesta g, l, opuesta c, r) m4 (g,l,c,r) = (opuesta g, l, c, opuesta r) -- Nodo es el tipo de los nodos del espacio de búsqueda, donde un nodo -- es una lista de estados -- [e_n, ..., e_2, e_1] -- tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un -- sucesor de e_(i-1). newtype Nodo = Nodo [Estado] deriving (Eq, Show) -- inicial es el nodo inicial en el que todos están en la orilla -- izquierda. inicial :: Nodo inicial = Nodo [(I,I,I,I)] -- (esFinal n) se verifica si n es un nodo final; es decir, su primer -- elemento es el estado final. Por ejemplo, -- esFinal (Nodo [(D,D,D,D),(I,I,I,I)]) == True -- esFinal (Nodo [(I,I,D,I),(I,I,I,I)]) == False esFinal :: Nodo -> Bool esFinal (Nodo (n:_)) = n == (D,D,D,D) -- (sucesores n) es la lista de los sucesores del nodo n. Por ejemplo, -- λ> sucesores (Nodo [(I,I,D,I),(D,I,D,I),(I,I,I,I)]) -- [Nodo [(D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)], -- Nodo [(D,I,D,D),(I,I,D,I),(D,I,D,I),(I,I,I,I)]] sucesores :: Nodo -> [Nodo] sucesores (Nodo n@(e:es)) = [Nodo (e':n) | e' <- sucesoresE e, e' `notElem` es] granjero :: [[Estado]] granjero = [reverse es | (Nodo es) <- buscaProfundidad sucesores esFinal inicial] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ head granjero `shouldBe` [(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)] it "e2" $ length granjero `shouldBe` 2 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0008 seconds -- 2 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
from enum import Enum from src.BusquedaEnProfundidad import buscaProfundidad class Orilla(Enum): I = 0 D = 1 def __repr__(self) -> str: return self.name I = Orilla.I D = Orilla.D Estado = tuple[Orilla, Orilla, Orilla, Orilla] # seguro(e) se verifica si el estado e es seguro; es decir, que no # puede estar en una orilla el lobo con la cabra sin el granjero ni la # cabra con el repollo sin el granjero. Por ejemplo, # seguro((I,D,D,I)) == False # seguro((D,D,D,I)) == True # seguro((D,D,I,I)) == False # seguro((I,D,I,I)) == True def seguro(e: Estado) -> bool: (g,l,c,r) = e return not (g != c and c in {l, r}) # (opuesta x) es la opuesta de la orilla x. Por ejemplo # opuesta(I) == D def opuesta(o: Orilla) -> Orilla: if o == I: return D return I # sucesoresE(e) es la lista de los sucesores seguros del estado e. Por # ejemplo, # sucesoresE((I,I,I,I)) == [(D,I,D,I)] # sucesoresE((D,I,D,I)) == [(I,I,D,I),(I,I,I,I)] def sucesoresE(e: Estado) -> list[Estado]: def mov(n: int, e: Estado) -> Estado: (g,l,c,r) = e if n == 1: return (opuesta(g), l, c, r) if n == 2: return (opuesta(g), opuesta(l), c, r) if n == 3: return (opuesta(g), l, opuesta(c), r) return (opuesta(g), l, c, opuesta(r)) return [mov(n, e) for n in range(1, 5) if seguro(mov(n, e))] # Nodo es el tipo de los nodos del espacio de búsqueda, donde un nodo # es una lista de estados # [e_n, ..., e_2, e_1] # tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un # sucesor de e_(i-1). Nodo = list[Estado] # inicial es el nodo inicial en el que todos están en la orilla # izquierda. inicial: Nodo = [(I,I,I,I)] # esFinal(n) se verifica si n es un nodo final; es decir, su primer # elemento es el estado final. Por ejemplo, # esFinal([(D,D,D,D),(I,I,I,I)]) == True # esFinal([(I,I,D,I),(I,I,I,I)]) == False def esFinal(n: Nodo) -> bool: return n[0] == (D,D,D,D) # sucesores(n) es la lista de los sucesores del nodo n. Por ejemplo, # >>> sucesores([(I,I,D,I),(D,I,D,I),(I,I,I,I)]) # [[(D, D, D, I), (I, I, D, I), (D, I, D, I), (I, I, I, I)], # [(D, I, D, D), (I, I, D, I), (D, I, D, I), (I, I, I, I)]] def sucesores(n: Nodo) -> list[Nodo]: e, *es = n return [[e1] + n for e1 in sucesoresE(e) if e1 not in es] def granjero() -> list[list[Estado]]: return [list(reversed(es)) for es in buscaProfundidad(sucesores, esFinal, inicial)] # # Verificación # # ============ def test_granjero() -> None: assert granjero() == \ [[(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)], [(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)]] print("Verificado") # La verificación es # >>> test_granjero() # Verificado |
5. El problema de las fichas mediante búsqueda en espacio de estado
Para el problema de las fichas de orden (m,n) se considera un tablero con m+n+1 cuadrados consecutivos.
Inicialmente, en cada uno de los m primeros cuadrados hay una blanca, a continuación un hueco y en cada uno de los n últimos cuadrados hay una ficha verde. El objetivo consiste en tener las fichas verdes al principio y las blancas al final.
Por ejemplo, en el problema de las fichas de orden (3,3) el tablero inicial es
1 2 3 |
+---+---+---+---+---+---+---+ | B | B | B | | V | V | V | +---+---+---+---+---+---+---+ |
y el final es
1 2 3 |
+---+---+---+---+---+---+---+ | V | V | V | | B | B | B | +---+---+---+---+---+---+---+ |
Los movimientos permitidos consisten en desplazar una ficha al hueco saltando, como máximo, sobre otras dos.
Para representar el problema se definen los siguientes tipos de datos:
Ficha
con tres constructoresB
,V
yH
que representan las fichas blanca, verde y hueco, respectivamente.
1 2 |
data Ficha = B | V | H deriving (Eq, Show) |
Tablero
que es una lista de fichas que representa las fichas colocadas en el tablero.
1 |
type Tablero = [Ficha] |
Estado
representa los estados del espacio de búsqueda, donde un estado es una lista de tableros [t(n), …, t(2), t(1)] tal que t(1) es el tablero inicial y para cada i (2 <= i <= n), t(i) es un sucesor de t(i-1).
1 2 |
newtype Estado = E [Tablero] deriving (Eq, Show) |
Busqueda
es un procedimiento de búsqueda
1 2 3 4 |
type Busqueda = (Estado -> [Estado]) -> (Estado -> Bool) -> Estado -> [Estado] |
Además, se considera la heurística 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
1 2 3 |
+---+---+---+---+---+---+---+ | B | V | B | | V | V | B | +---+---+---+---+---+---+---+ |
su valor es 1+2+2 = 5. La heurística de un estado es la del primero de sus tableros.
Usando los métodos de búsqueda estudiado en los ejercicios anteriores, definir la función
1 |
fichas :: Busqueda -> Int -> Int -> [[Tablero]] |
tal que fichas b m n
es la lista de las soluciones del problema de las fichas de orden (m,n) obtenidas mediante el procedimiento de búsqueda b. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> head (fichas buscaProfundidad 2 2) [[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], [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], [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], [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]] λ> head (fichas buscaAnchura 2 2) [[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]] λ> head (fichas buscaPM 2 2) [[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],[V,V,B,H,B],[V,V,H,B,B]] λ> head (fichas buscaEscalada 2 2) [[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],[V,V,B,H,B],[V,V,H,B,B]] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
module BEE_El_problema_de_las_fichas where import BusquedaEnProfundidad (buscaProfundidad) import BusquedaEnAnchura (buscaAnchura) import BusquedaPrimeroElMejor (buscaPM) import BusquedaEnEscalada (buscaEscalada) import Test.Hspec (Spec, hspec, it, shouldBe) -- Representación del problema -- =========================== data Ficha = B | V | H deriving (Eq, Show) type Tablero = [Ficha] -- (tableroInicial m n) representa el tablero inicial del problema de las fichas -- de orden (m,n). Por ejemplo, -- tableroInicial 2 3 == [B,B,H,V,V,V] -- tableroInicial 3 2 == [B,B,B,H,V,V] tableroInicial :: Int -> Int -> Tablero tableroInicial m n = replicate m B ++ [H] ++ replicate n V -- (tableroFinal m n) representa el tablero final del problema de las fichas de -- orden (m,n). Por ejemplo, -- tableroFinal 2 3 == [V,V,V,H,B,B] -- tableroFinal 3 2 == [V,V,H,B,B,B] tableroFinal :: Int -> Int -> Tablero tableroFinal m n = replicate n V ++ [H] ++ replicate m B -- (tablerosSucesores t) es la lista de los sucesores del tablero t. Por -- ejemplo, -- λ> tablerosSucesores [V,B,H,V,V,B] -- [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B], -- [V,B,B,V,V,H]] -- λ> tablerosSucesores [B,B,B,H,V,V,V] -- [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V], -- [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]] tablerosSucesores :: Tablero -> [Tablero] tablerosSucesores t = [intercambia i j t | i <- [j-1,j-2,j-3,j+1,j+2,j+3] , 0 <= i, i < n] where j = posicionHueco t n = length t -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- posicionHueco (tableroInicial 3 2) == 3 posicionHueco :: Tablero -> Int posicionHueco t = length (takeWhile (/=H) t) -- (intercambia xs i j) es la lista obtenida intercambiando los -- elementos de xs en las posiciones i y j. Por ejemplo, -- intercambia 2 6 [0..9] == [0,1,6,3,4,5,2,7,8,9] -- intercambia 6 2 [0..9] == [0,1,6,3,4,5,2,7,8,9] intercambia :: Int -> Int -> [a] -> [a] intercambia i j xs = concat [xs1,[x2],xs2,[x1],xs3] where (xs1,x1,xs2,x2,xs3) = divide (min i j) (max i j) xs -- (divide xs i j) es la tupla (xs1,x1,xs2,x2,xs3) tal que xs1 son los -- elementos de xs cuya posición es menor que i, x1 es el elemento de xs -- en la posición i, xs2 son los elementos de xs cuya posición es mayor -- que i y menor que j, x2 es el elemento de xs en la posición j y xs3 -- son los elementos de xs cuya posición es mayor que j (suponiendo que -- i < j). Por ejemplo, -- divide 2 6 [0..9] == ([0,1],2,[3,4,5],6,[7,8,9]) divide :: Int -> Int -> [a] -> ([a],a,[a],a,[a]) divide i j xs = (xs1,x1,xs2,x2,xs3) where (xs1,x1:ys) = splitAt i xs (xs2,x2:xs3) = splitAt (j - i - 1) ys newtype Estado = E [Tablero] deriving (Eq, Show) -- (inicial m n) representa el estado inicial del problema de las fichas -- de orden (m,n). Por ejemplo, -- inicial 2 3 == E [[B,B,H,V,V,V]] -- inicial 3 2 == E [[B,B,B,H,V,V]] inicial :: Int -> Int -> Estado inicial m n = E [tableroInicial m n] -- (esFinal m n e) se verifica si e es un estado final del problema de las -- fichas de orden (m,n). Por ejemplo, -- λ> esFinal 2 1 (E [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]]) -- True -- λ> esFinal 2 1 (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) -- False esFinal :: Int -> Int -> Estado -> Bool esFinal m n (E (e:_)) = e == tableroFinal m n -- (sucesores n) es la lista de los sucesores del estado n. Por ejemplo, -- λ> sucesores (E [[H,B,B,V],[B,B,H,V]]) -- [E [[B,H,B,V],[H,B,B,V],[B,B,H,V]], -- E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]] -- λ> sucesores (E [[B,H,B,V],[H,B,B,V],[B,B,H,V]]) -- [E [[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]] sucesores :: Estado -> [Estado] sucesores (E e@(t:ts)) = [E (t':e) | t' <- tablerosSucesores t, t' `notElem` ts] -- Heurística -- ========== -- (heuristicaT t) es la heurística del tablero t. Por ejemplo, -- heuristicaT [B,V,B,H,V,V,B] == 5 heuristicaT :: Tablero -> Int heuristicaT [] = 0 heuristicaT (V:xs) = heuristicaT xs heuristicaT (H:xs) = heuristicaT xs heuristicaT (B:xs) = heuristicaT xs + length (filter (==V) xs) -- (heuristica e) es la heurística del primer tablero del estado e. Por -- ejemplo, -- heuristica (E [[H,B,B,V],[B,B,H,V]]) == 2 -- heuristica (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) == 0 heuristica :: Estado -> Int heuristica (E (t:_)) = heuristicaT t -- Estado es un subtipo de Ord de forma que un estado es menor o igual -- que otro si su heurística lo es. instance Ord Estado where e1 <= e2 = heuristica e1 <= heuristica e2 -- Solución por búsqueda -- ===================== type Busqueda = (Estado -> [Estado]) -> (Estado -> Bool) -> Estado -> [Estado] fichas :: Busqueda -> Int -> Int -> [[Tablero]] fichas b m n = [reverse es | E es <- b sucesores (esFinal m n) (inicial m n)] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ head (fichas buscaProfundidad 2 2) `shouldBe` [[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], [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], [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], [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]] it "e2" $ head (fichas buscaAnchura 2 2) `shouldBe` [[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]] it "e3" $ head (fichas buscaPM 2 2) `shouldBe` [[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], [V,V,B,H,B],[V,V,H,B,B]] it "e4" $ head (fichas buscaEscalada 2 2) `shouldBe` [[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], [V,V,B,H,B],[V,V,H,B,B]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0055 seconds -- 4 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
from enum import Enum from functools import partial from typing import Callable, Optional from src.BusquedaEnAnchura import buscaAnchura1 from src.BusquedaEnEscalada import buscaEscalada from src.BusquedaEnProfundidad import buscaProfundidad1 from src.BusquedaPrimeroElMejor import buscaPM # Representación del problema # =========================== class Ficha(Enum): B = 0 V = 1 H = 2 def __repr__(self) -> str: return self.name B = Ficha.B V = Ficha.V H = Ficha.H Tablero = list[Ficha] # tableroInicial(m, n) representa el tablero inicial del problema de las fichas # de orden (m,n). Por ejemplo, # tableroInicial(2, 3) == [B,B,H,V,V,V] # tableroInicial(3, 2) == [B,B,B,H,V,V] def tableroInicial(m: int, n: int) -> Tablero: return [B]*m + [H] + [V]*n # tableroFinal(m, n) representa el tablero final del problema de las fichas de # orden (m,n). Por ejemplo, # tableroFinal(2, 3) == [V,V,V,H,B,B] # tableroFinal(3, 2) == [V,V,H,B,B,B] def tableroFinal(m: int, n: int) -> Tablero: return [V]*n + [H] + [B]*m # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # posicionHueco(tableroInicial(3, 2)) == 3 def posicionHueco(t: Tablero) -> int: return t.index(H) # intercambia(xs, i, j) es la lista obtenida intercambiando los # elementos de xs en las posiciones i y j. Por ejemplo, # intercambia(1, 3, tableroInicial(3, 2)) == [B, H, B, B, V, V] def intercambia(i: int, j: int, t: Tablero) -> Tablero: t1 = t.copy() t1[i], t1[j] = t1[j], t1[i] return t1 # tablerosSucesores(t) es la lista de los sucesores del tablero t. Por # ejemplo, # >>> tablerosSucesores([V,B,H,V,V,B]) # [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B], # [V,B,B,V,V,H]] # >>> tablerosSucesores([B,B,B,H,V,V,V]) # [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V], # [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]] def tablerosSucesores(t: Tablero) -> list[Tablero]: j = posicionHueco(t) n = len(t) return [intercambia(i, j, t) for i in [j-1,j-2,j-3,j+1,j+2,j+3] if 0 <= i < n] # Heurística # ========== # heuristicaT(t) es la heurística del tablero t. Por ejemplo, # heuristicaT([B,V,B,H,V,V,B]) == 5 def heuristicaT(t: Tablero) -> int: if not t: return 0 f, *fs = t if f in {V, H}: return heuristicaT(fs) return heuristicaT(fs) + len([x for x in fs if x == V]) class Estado(list[Tablero]): def __lt__(self, e: list[Tablero]) -> bool: return heuristicaT(self[0]) < heuristicaT(e[0]) # inicial(m, n) representa el estado inicial del problema de las fichas # de orden (m,n). Por ejemplo, # inicial(2, 3) == [[B,B,H,V,V,V]] # inicial(3, 2) == [[B,B,B,H,V,V]] def inicial(m: int, n: int) -> Estado: return Estado([tableroInicial(m, n)]) # esFinal(m, n, e) se verifica si e es un estado final del problema de las # fichas de orden (m,n). Por ejemplo, # >>> esFinal(2, 1, [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]]) # True # >>> esFinal(2, 1, [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) # False def esFinal(m: int, n: int, e: Estado) -> bool: return e[0] == tableroFinal(m, n) # (sucesores n) es la lista de los sucesores del estado n. Por ejemplo, # >>> sucesores([[H,B,B,V],[B,B,H,V]]) # [[[B,H,B,V],[H,B,B,V],[B,B,H,V]], # [[V,B,B,H],[H,B,B,V],[B,B,H,V]]] # >>> sucesores([[B,H,B,V],[H,B,B,V],[B,B,H,V]]) # [[[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]] def sucesores(e: Estado) -> list[Estado]: t, *ts = e return [Estado([t1] + e) for t1 in tablerosSucesores(t) if t1 not in ts] # Solución por búsqueda # ===================== Busqueda = Callable[[Callable[[Estado], list[Estado]], Callable[[Estado], bool], Estado], Optional[Estado]] def fichas(b: Busqueda, m: int, n: int) -> Optional[list[Tablero]]: r = partial(b, sucesores, lambda e: esFinal(m, n, e), inicial(m, n))() if r is None: return None return [list(reversed(es)) for es in r] # Verificación # ============ def test_fichas() -> None: assert fichas(buscaProfundidad1, 1, 2) == \ [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]] assert fichas(buscaAnchura1, 1, 2) == \ [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]] assert fichas(buscaPM, 1, 2) == \ [[B, H, V, V], [B, V, H, V], [H, V, B, V], [V, V, B, H], [V, V, H, B]] assert fichas(buscaEscalada, 1, 2) == \ [[B, H, V, V], [H, B, V, V], [V, B, H, V], [V, H, B, V], [V, V, B, H], [V, V, H, B]] print("Verificado") # La verificación es # >>> test_fichas() # Verificado |
6. El problema del calendario mediante búsqueda en espacio de estado
El problema del calendario, para una competición deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que:
- el campeonato dure n-1 días,
- cada participante juegue exactamente un partido diario y
- cada participante juegue exactamente una vez con cada adversario.
Por ejemplo, con 8 participantes una posible solución es
1 2 3 4 5 6 7 8 9 10 |
| 1 2 3 4 5 6 7 --+-------------- 1 | 2 3 4 5 6 7 8 2 | 1 4 3 6 5 8 7 3 | 4 1 2 7 8 5 6 4 | 3 2 1 8 7 6 5 5 | 6 7 8 1 2 3 4 6 | 5 8 7 2 1 4 3 7 | 8 5 6 3 4 1 2 8 | 7 6 5 4 3 2 1 |
donde las filas indican los jugadores y las columnas los días; es decir, el elemento (i,j) indica el adversario del jugador i el día j; por ejemplo, el adversario del jugador 2 el 4ª día es el jugador 6.
Para representar el problema se define el tipo Calendario como matrices de enteros,
Usando el procedimiento de búsqueda en profundidad, definir la función
1 |
calendario :: Int -> [Calendario] |
tal que calendario n
son las soluciones del problema del calendario, con n participantes, mediante el patrón de búsqueda em profundidad. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> head (calendario 6) ┌ ┐ │ 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 │ └ ┘ λ> length (calendario 6) 720 λ> length (calendario 5) 0 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
module El_problema_del_calendario_mediante_busqueda_en_espacio_de_estado where import BusquedaEnProfundidad (buscaProfundidad) import Data.Matrix (Matrix, (!), nrows, zero, setElem, toLists) import Data.List ((\\)) import Test.Hspec (Spec, hspec, it, shouldBe) type Calendario = Matrix Int -- (inicial n) es el estado inicial para el problema del calendario con -- n participantes; es decir, una matriz de n fila y n-1 columnas con -- todos sus elementos iguales a 0. Por ejemplo, -- λ> inicial 4 -- ┌ ┐ -- │ 0 0 0 │ -- │ 0 0 0 │ -- │ 0 0 0 │ -- │ 0 0 0 │ -- └ ┘ inicial :: Int -> Calendario inicial n = zero n (n-1) -- (huecos c) es la lista de las posiciones de c cuyo valor es 0. huecos :: Calendario -> [(Int, Int)] huecos c = [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0] where n = nrows c -- (sucesores c) es la lista de calendarios obtenidos poniendo en el -- lugar del primer elemento nulo de c uno de los posibles jugadores de -- forma que se cumplan las condiciones del problema. Por ejemplo, -- λ> sucesores (inicial 4) -- [┌ ┐ ┌ ┐ ┌ ┐ -- │ 2 0 0 │ │ 3 0 0 │ │ 4 0 0 │ -- │ 1 0 0 │ │ 0 0 0 │ │ 0 0 0 │ -- │ 0 0 0 │ │ 1 0 0 │ │ 0 0 0 │ -- │ 0 0 0 │ │ 0 0 0 │ │ 1 0 0 │ -- └ ┘, └ ┘, └ ┘] -- λ> sucesores (fromLists [[2,3,0],[1,0,0],[0,1,0],[0,0,0]]) -- [┌ ┐ -- │ 2 3 4 │ -- │ 1 0 0 │ -- │ 0 1 0 │ -- │ 0 0 1 │ -- └ ┘] -- λ> sucesores (fromLists [[2,3,4],[1,0,0],[0,1,0],[0,0,1]]) -- [┌ ┐ -- │ 2 3 4 │ -- │ 1 4 0 │ -- │ 0 1 0 │ -- │ 0 2 1 │ -- └ ┘] sucesores :: Calendario -> [Calendario] sucesores c = [setElem i (k,j) (setElem k (i,j) c) | k <- [1..n] \\ (i : [c!(k,j) | k <- [1..i-1]] ++ [c!(i,k) | k <- [1..j-1]]), c!(k,j) == 0] where n = nrows c (i,j) = head (huecos c) -- (esFinal c) se verifica si c un estado final para el problema -- del calendario con n participantes; es decir, no queda en c ningún -- elemento igual a 0. Por ejemplo, -- λ> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]]) -- True -- λ> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]]) -- False esFinal :: Calendario -> Bool esFinal c = null (huecos c) calendario :: Int -> [Calendario] calendario n = buscaProfundidad sucesores esFinal (inicial n) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ toLists (head (calendario 6)) `shouldBe` [[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]] it "e2" $ length (calendario 6) `shouldBe` 720 it "e3" $ length (calendario 5) `shouldBe` 0 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.2580 seconds -- 3 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
from copy import deepcopy from typing import Optional import numpy as np import numpy.typing as npt from src.BusquedaEnProfundidad import buscaProfundidad Calendario = npt.NDArray[np.complex64] # inicial(n) es el estado inicial para el problema del calendario con # n participantes; es decir, una matriz de n fila y n-1 columnas con # todos sus elementos iguales a 0. Por ejemplo, # >>> inicial(4) # array([[0, 0, 0], # [0, 0, 0], # [0, 0, 0], # [0, 0, 0]]) def inicial(n: int) -> Calendario: return np.zeros((n, n - 1), dtype=int) # primerHueco(c) es la posición del primer elemento cuyo valor es 0. Si # todos los valores son distintos de 0, devuelve (-1,-1). Por ejemplo, # primerHueco(np.array([[1,2,3],[4,5,0],[7,0,0]])) == (1, 2) # primerHueco(np.array([[1,2,3],[4,5,6],[7,8,0]])) == (2, 2) # primerHueco(np.array([[1,2,3],[4,5,6],[7,8,9]])) == (-1, -1) def primerHueco(c: Calendario) -> tuple[int, int]: (n, m) = c.shape for i in range(0, n): for j in range(0, m): if c[i,j] == 0: return (i, j) return (-1, -1) # libres(c, i, j) es la lista de valores que que pueden poner en la # posición (i,j) del calendario c. Por ejemplo, # libres(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]),0,0) == [2, 3, 4] # libres(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]),0,1) == [3, 4] # libres(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]),0,2) == [4] # libres(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]),1,1) == [4] # libres(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]),1,2) == [3] def libres(c: Calendario, i: int, j: int) -> list[int]: n = c.shape[0] return list(set(range(1, n + 1)) - {i + 1} - set(c[i]) - set(c[:,j])) # setElem(k, i, j, c) es el calendario obtenido colocando en c el valor # k en la posición (i,j). # >>> setElem(7,1,2,np.array([[1,2,3],[4,5,0],[0,0,0]])) # array([[1, 2, 3], # [4, 5, 7], # [0, 0, 0]]) def setElem(k: int, i: int, j: int, c: Calendario) -> Calendario: _c = deepcopy(c) _c[i, j] = k return _c # sucesores(c) es la lista de calendarios obtenidos poniendo en el # lugar del primer elemento nulo de c uno de los posibles jugadores de # forma que se cumplan las condiciones del problema. Por ejemplo, # >>> sucesores(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]])) # [array([[2,0,0], [1,0,0], [0,0,0], [0,0,0]]), # array([[3,0,0], [0,0,0], [1,0,0], [0,0,0]]), # array([[4,0,0], [0,0,0], [0,0,0], [1,0,0]])] # >>> sucesores(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]])) # [array([[2,3,0], [1,0,0], [0,1,0], [0,0,0]]), # array([[2,4,0], [1,0,0], [0,0,0], [0,1,0]])] # >>> sucesores(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]])) # [array([[2,3,4], [1,0,0], [0,1,0], [0,0,1]])] # >>> sucesores(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]])) # [array([[2,3,4], [1,4,0], [0,1,0], [0,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]])) # [array([[2,3,4], [1,4,3], [0,1,2], [0,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,3],[0,1,2],[0,2,1]])) # [array([[2,3,4], [1,4,3], [4,1,2], [3,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]])) # [] def sucesores(c: Calendario) -> list[Calendario]: n = c.shape[0] (i, j) = primerHueco(c) return [setElem(i+1, k-1, j, setElem(k, i, j, c)) for k in libres(c, i, j)] # esFinal(c) se verifica si c un estado final para el problema # del calendario con n participantes; es decir, no queda en c ningún # elemento igual a 0. Por ejemplo, # >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]])) # True # >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,0]])) # False def esFinal(c: Calendario) -> bool: return primerHueco(c) == (-1, -1) def calendario(n: int) -> list[Calendario]: return buscaProfundidad(sucesores, esFinal, inicial(n)) # Verificación # ============ def test_calendario() -> None: def filas(p: Calendario) -> list[list[int]]: return p.tolist() assert filas(calendario(6)[0]) == \ [[6, 5, 4, 3, 2], [5, 4, 3, 6, 1], [4, 6, 2, 1, 5], [3, 2, 1, 5, 6], [2, 1, 6, 4, 3], [1, 3, 5, 2, 4]] assert len(calendario(6)) == 720 assert len(calendario(5)) == 0 print("Verificado") |