El problema del dominó (con espacios de estados)
Las fichas del dominó se pueden representar por pares de enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
domino :: [(Int,Int)] -> [[(Int,Int)]] |
tal que domino fs es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> domino [(1,2),(2,3),(1,4)] [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] λ> domino [(1,2),(1,1),(1,4)] [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] λ> domino [(1,2),(3,4),(2,3)] [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]] λ> domino [(1,2),(2,3),(5,4)] [] |
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 El_problema_del_domino where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) -- Las fichas son pares de números enteros. type Ficha = (Int,Int) -- Un problema está definido por la lista de fichas que hay que colocar type Problema = [Ficha] -- Los estados son los pares formados por la listas sin colocar y las -- colocadas. type Estado = ([Ficha],[Ficha]) -- (inicial p) es el estado inicial del problema p. Por ejemplo, -- λ> inicial [(1,2),(2,3),(1,4)] -- ([(1,2),(2,3),(1,4)],[]) inicial :: Problema -> Estado inicial p = (p,[]) -- (esFinal e) se verifica si e es un estado final. Por ejemplo, -- λ> esFinal ([], [(4,1),(1,2),(2,3)]) -- True -- λ> esFinal ([(2,3)], [(4,1),(1,2)]) -- False esFinal :: Estado -> Bool esFinal = null . fst -- (sucesores e) es la lista de los sucesores del estado e. Por ejemplo, -- λ> sucesores ([(1,2),(2,3),(1,4)],[]) -- [([(2,3),(1,4)],[(1,2)]), -- ([(1,2),(1,4)],[(2,3)]), -- ([(1,2),(2,3)],[(1,4)]), -- ([(2,3),(1,4)],[(2,1)]), -- ([(1,2),(1,4)],[(3,2)]), -- ([(1,2),(2,3)],[(4,1)])] -- λ> sucesores ([(2,3),(1,4)],[(1,2)]) -- [([(2,3)],[(4,1),(1,2)])] -- λ> sucesores ([(2,3),(1,4)],[(2,1)]) -- [([(1,4)],[(3,2),(2,1)])] sucesores :: Estado -> [Estado] sucesores (fs,[]) = [(delete (a,b) fs, [(a,b)]) | (a,b) <- fs, a /= b] ++ [(delete (a,b) fs, [(b,a)]) | (a,b) <- fs] sucesores (fs,e@((x,_):_)) = [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u /= v, v == x] ++ [(delete (u,v) fs,(v,u):e) | (u,v) <- fs, u /= v, u == x] ++ [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u == v, u == x] -- (soluciones p) es la lista de las soluciones del problema p. Por -- ejemplo, -- λ> soluciones [(1,2),(2,3),(1,4)] -- [([],[(4,1),(1,2),(2,3)]),([],[(3,2),(2,1),(1,4)])] soluciones :: Problema -> [Estado] soluciones p = buscaProfundidad sucesores esFinal (inicial p) domino :: Problema -> [[Ficha]] domino p = map snd (soluciones p) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ domino [(1,2),(2,3),(1,4)] `shouldBe` [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] it "e2" $ domino [(1,2),(1,1),(1,4)] `shouldBe` [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] it "e3" $ domino [(1,2),(3,4),(2,3)] `shouldBe` [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]] it "e4" $ domino [(1,2),(2,3),(5,4)] `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0013 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 |
from src.BusquedaEnProfundidad import buscaProfundidad # Las fichas son pares de números enteros. Ficha = tuple[int, int] # Un problema está definido por la lista de fichas que hay que colocar Problema = list[Ficha] # Los estados son los pares formados por la listas sin colocar y las # colocadas. Estado = tuple[list[Ficha], list[Ficha]] # inicial(p) es el estado inicial del problema p. Por ejemplo, # >>> inicial([(1,2),(2,3),(1,4)]) # ([(1, 2), (2, 3), (1, 4)], []) def inicial(p: Problema) -> Estado: return (p, []) # esFinal(e) se verifica si e es un estado final. Por ejemplo, # >>> esFinal(([], [(4,1),(1,2),(2,3)])) # True # >>> esFinal(([(2,3)], [(4,1),(1,2)])) # False def esFinal(e: Estado) -> bool: return not e[0] # elimina(f, fs) es la lista obtenida eliminando la ficha f de la lista # fs. Por ejemplo, # >>> elimina((1,2),[(4,1),(1,2),(2,3)]) # [(4, 1), (2, 3)] def elimina(f: Ficha, fs: list[Ficha]) -> list[Ficha]: return [g for g in fs if g != f] # sucesores(e) es la lista de los sucesores del estado e. Por ejemplo, # >>> sucesores(([(1,2),(2,3),(1,4)],[])) # [([(2,3),(1,4)],[(1,2)]), # ([(1,2),(1,4)],[(2,3)]), # ([(1,2),(2,3)],[(1,4)]), # ([(2,3),(1,4)],[(2,1)]), # ([(1,2),(1,4)],[(3,2)]), # ([(1,2),(2,3)],[(4,1)])] # >>> sucesores(([(2,3),(1,4)],[(1,2)])) # [([(2,3)],[(4,1),(1,2)])] # >>> sucesores(([(2,3),(1,4)],[(2,1)])) # [([(1,4)],[(3,2),(2,1)])] def sucesores(e: Estado) -> list[Estado]: if not e[1]: return [(elimina((a,b), e[0]), [(a,b)]) for (a,b) in e[0] if a != b] + \ [(elimina((a,b), e[0]), [(b,a)]) for (a,b) in e[0]] return [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u != v and v == e[1][0][0]] +\ [(elimina((u,v),e[0]),[(v,u)]+e[1]) for (u,v) in e[0] if u != v and u == e[1][0][0]] +\ [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u == v and u == e[1][0][0]] # soluciones(p) es la lista de las soluciones del problema p. Por # ejemplo, # >>> soluciones([(1,2),(2,3),(1,4)]) # [([], [(3, 2), (2, 1), (1, 4)]), ([], [(4, 1), (1, 2), (2, 3)])] def soluciones(p: Problema) -> list[Estado]: return buscaProfundidad(sucesores, esFinal, inicial(p)) def domino(p: Problema) -> list[list[Ficha]]: return [s[1] for s in soluciones(p)] # # Verificación # # ============ def test_domino() -> None: assert domino([(1,2),(2,3),(1,4)]) == \ [[(3, 2), (2, 1), (1, 4)], [(4, 1), (1, 2), (2, 3)]] assert domino([(1,2),(1,1),(1,4)]) == \ [[(2, 1), (1, 1), (1, 4)], [(4, 1), (1, 1), (1, 2)]] assert domino([(1,2),(3,4),(2,3)]) == \ [[(4, 3), (3, 2), (2, 1)], [(1, 2), (2, 3), (3, 4)]] assert domino([(1,2),(2,3),(5,4)]) == \ [] print("Verificado") # La verificación es # >>> test_domino() # Verificado |