Espacio de estados – Exercitium

Problema de las jarras (con espacios de estados)

José A. Alonso, 9-septiembre-2023, Haskell y Python

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.

Usando el procedimiento de búsqueda en anchura, definir la función

   jarras :: (Int,Int,Int) -> [[(Int,Int)]]

tal jarras (a,b,c) es la lista de las soluciones del problema de las jarras (a,b,c). Por ejemplo,

   λ> take 3 (jarras (4,3,2))
   [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],
    [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:

(0,0) se inicia con las dos jarras vacías,
(4,0) se llena la jarra de 4 con el grifo,
(1,3) se llena la de 3 con la de 4,
(1,0) se vacía la de 3,
(0,1) se pasa el contenido de la primera a la segunda,
(4,1) se llena la primera con el grifo,
(2,3) se llena la segunda con la primera.

Otros ejemplos

   λ> length (jarras (15,10,5))
   8
   λ> map length (jarras (15,10,5))
   [3,5,5,7,7,7,8,9]
   λ> jarras (15,10,4)
   []

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Problema_de_las_jarras where
 
import BusquedaEnAnchura (buscaAnchura)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- Un problema es una lista de 3 números enteros (a,b,c) tales que a es
-- la capacidad de la primera jarra, b es la capacidad de la segunda
-- jarra y c es el número de litros que se desea obtener en la primera
-- jarra.
type Problema = (Int,Int,Int)
 
-- Una configuracion es una lista de dos números. El primero es el
-- contenido de la primera jarra y el segundo el de la segunda.
type Configuracion = (Int,Int)
 
-- Inicialmente, las dos jarras están vacías.
configuracionInicial :: Configuracion
configuracionInicial = (0,0)
 
-- (esConfiguracionFinal p e) se verifica si e es un configuracion final
-- del problema p.
esConfiguracionFinal :: Problema -> Configuracion -> Bool
esConfiguracionFinal (_,_,c) (x,_) = x == c
 
-- (sucesorasConfiguracion p c) son las sucesoras de la configuración c
-- del problema p. Por ejemplo,
--    sucesorasConfiguracion (4,3,2) (0,0)  ==  [(4,0),(0,3)]
--    sucesorasConfiguracion (4,3,2) (4,0)  ==  [(4,3),(0,0),(1,3)]
--    sucesorasConfiguracion (4,3,2) (4,3)  ==  [(0,3),(4,0)]
sucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion]
sucesorasConfiguracion (a,b,_) (x,y) =
    [(a,y) | x < a] ++
    [(x,b) | y < b] ++
    [(0,y) | x > 0] ++
    [(x,0) | y > 0] ++
    [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++
    [(x-(b-y),b) | x > 0, y < b, x + y > b] ++
    [(x+y,0) | y > 0, x + y <= a] ++
    [(0,x+y) | x > 0, x + y <= b]
 
-- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que
-- c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una
-- sucesora de c_(i-1).
type Estado = [Configuracion]
 
-- inicial es el estado cuyo único elemento es la configuración
-- inicial.
inicial :: Estado
inicial = [configuracionInicial]
 
-- (esFinal p e) se verifica si e es un estado final; es decir, su
-- primer elemento es una configuración final.
esFinal :: Problema -> Estado -> Bool
esFinal p (e:_) = esConfiguracionFinal p e
 
-- (sucesores p e) es la lista de los sucesores del estado e en el
-- problema p. Por ejemplo,
--    λ> sucesores (4,3,2) [(0,0)]
--    [[(4,0),(0,0)],[(0,3),(0,0)]]
--    λ> sucesores (4,3,2) [(4,0),(0,0)]
--    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]
--    λ> sucesores (4,3,2) [(4,3),(4,0),(0,0)]
--    [[(0,3),(4,3),(4,0),(0,0)]]
sucesores :: Problema -> Estado -> [Estado]
sucesores p e@(c:_) =
    [c':e | c' <- sucesorasConfiguracion p c,
            c' `notElem` e]
 
jarras :: Problema -> [Estado]
jarras p = map reverse soluciones
  where
     soluciones = buscaAnchura (sucesores p) (esFinal p) inicial
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    take 3 (jarras (4,3,2)) `shouldBe`
    [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
     [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],
     [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]
  it "e2" $
    length (jarras (15,10,5)) `shouldBe` 8
  it "e3" $
    map length (jarras (15,10,5)) `shouldBe`
    [3,5,5,7,7,7,8,9]
  it "e4" $
    jarras (15,10,4) `shouldBe` []
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0080 seconds
--    4 examples, 0 failures

module Problema_de_las_jarras where import BusquedaEnAnchura (buscaAnchura) import Test.Hspec (Spec, hspec, it, shouldBe) -- Un problema es una lista de 3 números enteros (a,b,c) tales que a es -- la capacidad de la primera jarra, b es la capacidad de la segunda -- jarra y c es el número de litros que se desea obtener en la primera -- jarra. type Problema = (Int,Int,Int) -- Una configuracion es una lista de dos números. El primero es el -- contenido de la primera jarra y el segundo el de la segunda. type Configuracion = (Int,Int) -- Inicialmente, las dos jarras están vacías. configuracionInicial :: Configuracion configuracionInicial = (0,0) -- (esConfiguracionFinal p e) se verifica si e es un configuracion final -- del problema p. esConfiguracionFinal :: Problema -> Configuracion -> Bool esConfiguracionFinal (_,_,c) (x,_) = x == c -- (sucesorasConfiguracion p c) son las sucesoras de la configuración c -- del problema p. Por ejemplo, -- sucesorasConfiguracion (4,3,2) (0,0) == [(4,0),(0,3)] -- sucesorasConfiguracion (4,3,2) (4,0) == [(4,3),(0,0),(1,3)] -- sucesorasConfiguracion (4,3,2) (4,3) == [(0,3),(4,0)] sucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion] sucesorasConfiguracion (a,b,_) (x,y) = [(a,y) | x < a] ++ [(x,b) | y < b] ++ [(0,y) | x > 0] ++ [(x,0) | y > 0] ++ [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++ [(x-(b-y),b) | x > 0, y < b, x + y > b] ++ [(x+y,0) | y > 0, x + y <= a] ++ [(0,x+y) | x > 0, x + y <= b] -- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que -- c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una -- sucesora de c_(i-1). type Estado = [Configuracion] -- inicial es el estado cuyo único elemento es la configuración -- inicial. inicial :: Estado inicial = [configuracionInicial] -- (esFinal p e) se verifica si e es un estado final; es decir, su -- primer elemento es una configuración final. esFinal :: Problema -> Estado -> Bool esFinal p (e:_) = esConfiguracionFinal p e -- (sucesores p e) es la lista de los sucesores del estado e en el -- problema p. Por ejemplo, -- λ> sucesores (4,3,2) [(0,0)] -- [[(4,0),(0,0)],[(0,3),(0,0)]] -- λ> sucesores (4,3,2) [(4,0),(0,0)] -- [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]] -- λ> sucesores (4,3,2) [(4,3),(4,0),(0,0)] -- [[(0,3),(4,3),(4,0),(0,0)]] sucesores :: Problema -> Estado -> [Estado] sucesores p e@(c:_) = [c':e | c' <- sucesorasConfiguracion p c, c' `notElem` e] jarras :: Problema -> [Estado] jarras p = map reverse soluciones where soluciones = buscaAnchura (sucesores p) (esFinal p) inicial -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ take 3 (jarras (4,3,2)) `shouldBe` [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)], [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)], [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]] it "e2" $ length (jarras (15,10,5)) `shouldBe` 8 it "e3" $ map length (jarras (15,10,5)) `shouldBe` [3,5,5,7,7,7,8,9] it "e4" $ jarras (15,10,4) `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0080 seconds -- 4 examples, 0 failures

Soluciones en Python

from src.BusquedaEnAnchura import buscaAnchura
 
# Un problema es una lista de 3 números enteros (a,b,c) tales que a es
# la capacidad de la primera jarra, b es la capacidad de la segunda
# jarra y c es el número de litros que se desea obtener en la primera
# jarra.
Problema = tuple[int, int, int]
 
# Una configuracion es una lista de dos números. El primero es el
# contenido de la primera jarra y el segundo el de la segunda.
Configuracion = tuple[int, int]
 
# Inicialmente, las dos jarras están vacías.
configuracionInicial: Configuracion = (0,0)
 
# esConfiguracionFinal(p, e) se verifica si e es un configuracion final
# del problema p.
def esConfiguracionFinal(p: Problema, c: Configuracion) -> bool:
    return p[2] == c[0]
 
# sucesorasConfiguracion(p, c) son las sucesoras de la configuración c
# del problema p. Por ejemplo,
#    sucesorasConfiguracion((4,3,2), (0,0))  ==  [(4,0),(0,3)]
#    sucesorasConfiguracion((4,3,2), (4,0))  ==  [(4,3),(0,0),(1,3)]
#    sucesorasConfiguracion((4,3,2), (4,3))  ==  [(0,3),(4,0)]
def sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]:
    (a, b, _) = p
    (x, y) = c
    r = []
    if x < a:
        r.append((a, y))
    if y < b:
        r.append((x, b))
    if x > 0:
        r.append((0, y))
    if y > 0:
        r.append((x, 0))
    if x < a and y > 0 and x + y > a:
        r.append((a, y - (a - x)))
    if x > 0 and y < b and x + y > b:
        r.append((x - (b - y), b))
    if y > 0 and x + y <= a:
        r.append((x + y, 0))
    if x > 0 and x + y <= b:
        r.append((0, x + y))
    return r
 
# Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que
# c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una
# sucesora de c_(i-1).
Estado = list[Configuracion]
 
# inicial es el estado cuyo único elemento es la configuración
# inicial.
inicial: Estado = [configuracionInicial]
 
# esFinal(p, e) se verifica si e es un estado final; es decir, su
# primer elemento es una configuración final.
def esFinal(p: Problema, e: Estado) -> bool:
    return esConfiguracionFinal(p, e[0])
 
# sucesores(p, e) es la lista de los sucesores del estado e en el
# problema p. Por ejemplo,
#    λ> sucesores((4,3,2), [(0,0)])
#    [[(4,0),(0,0)],[(0,3),(0,0)]]
#    λ> sucesores((4,3,2), [(4,0),(0,0)])
#    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]
#    λ> sucesores((4,3,2), [(4,3),(4,0),(0,0)])
#    [[(0,3),(4,3),(4,0),(0,0)]]
def sucesores(p: Problema, e: Estado) -> list[Estado]:
    return [[c] + e
            for c in sucesorasConfiguracion(p, e[0])
            if c not in e]
 
def jarras(p: Problema) -> list[Estado]:
    soluciones = buscaAnchura(lambda e: sucesores(p, e),
                              lambda e: esFinal(p, e),
                              inicial)
    return [list(reversed(e)) for e in soluciones]
 
# Verificación
# ============
 
def test_jarras() -> None:
    assert jarras((4,3,2))[:3] == \
        [[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)],
         [(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)],
         [(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]]
    assert len(jarras((15,10,5))) == 8
    assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9]
    assert jarras((15,10,4)) == []
    print("Verificado")
 
# La verificación es
#    >>> test_jarras()
#    Verificado

from src.BusquedaEnAnchura import buscaAnchura # Un problema es una lista de 3 números enteros (a,b,c) tales que a es # la capacidad de la primera jarra, b es la capacidad de la segunda # jarra y c es el número de litros que se desea obtener en la primera # jarra. Problema = tuple[int, int, int] # Una configuracion es una lista de dos números. El primero es el # contenido de la primera jarra y el segundo el de la segunda. Configuracion = tuple[int, int] # Inicialmente, las dos jarras están vacías. configuracionInicial: Configuracion = (0,0) # esConfiguracionFinal(p, e) se verifica si e es un configuracion final # del problema p. def esConfiguracionFinal(p: Problema, c: Configuracion) -> bool: return p[2] == c[0] # sucesorasConfiguracion(p, c) son las sucesoras de la configuración c # del problema p. Por ejemplo, # sucesorasConfiguracion((4,3,2), (0,0)) == [(4,0),(0,3)] # sucesorasConfiguracion((4,3,2), (4,0)) == [(4,3),(0,0),(1,3)] # sucesorasConfiguracion((4,3,2), (4,3)) == [(0,3),(4,0)] def sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]: (a, b, _) = p (x, y) = c r = [] if x < a: r.append((a, y)) if y < b: r.append((x, b)) if x > 0: r.append((0, y)) if y > 0: r.append((x, 0)) if x < a and y > 0 and x + y > a: r.append((a, y - (a - x))) if x > 0 and y < b and x + y > b: r.append((x - (b - y), b)) if y > 0 and x + y <= a: r.append((x + y, 0)) if x > 0 and x + y <= b: r.append((0, x + y)) return r # Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que # c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una # sucesora de c_(i-1). Estado = list[Configuracion] # inicial es el estado cuyo único elemento es la configuración # inicial. inicial: Estado = [configuracionInicial] # esFinal(p, e) se verifica si e es un estado final; es decir, su # primer elemento es una configuración final. def esFinal(p: Problema, e: Estado) -> bool: return esConfiguracionFinal(p, e[0]) # sucesores(p, e) es la lista de los sucesores del estado e en el # problema p. Por ejemplo, # λ> sucesores((4,3,2), [(0,0)]) # [[(4,0),(0,0)],[(0,3),(0,0)]] # λ> sucesores((4,3,2), [(4,0),(0,0)]) # [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]] # λ> sucesores((4,3,2), [(4,3),(4,0),(0,0)]) # [[(0,3),(4,3),(4,0),(0,0)]] def sucesores(p: Problema, e: Estado) -> list[Estado]: return [[c] + e for c in sucesorasConfiguracion(p, e[0]) if c not in e] def jarras(p: Problema) -> list[Estado]: soluciones = buscaAnchura(lambda e: sucesores(p, e), lambda e: esFinal(p, e), inicial) return [list(reversed(e)) for e in soluciones] # Verificación # ============ def test_jarras() -> None: assert jarras((4,3,2))[:3] == \ [[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)], [(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)], [(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]] assert len(jarras((15,10,5))) == 8 assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9] assert jarras((15,10,4)) == [] print("Verificado") # La verificación es # >>> test_jarras() # Verificado

Leer más →

Problema de suma cero (con espacios de estados)

José A. Alonso, 4-septiembre-2023, Haskell y Python

El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vacío cuyos elementos sumen cero.

Usando el procedimiento de búsqueda en profundidad, definir la función

   suma0 :: [Int] -> [[Int]]

tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,

   λ> suma0 [-7,-3,-2,5,8]
   [[-3,-2,5]]
   λ> suma0 [-7,-3,-2,5,8,-1]
   [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]
   λ> suma0 [-7,-3,1,5,8]
   []

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Problema_de_suma_cero where
 
import BusquedaEnProfundidad (buscaProfundidad)
import Data.List (delete, nub, sort)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- Los estados son ternas formadas por los números seleccionados, su
-- suma y los restantes números.
type Estado = ([Int], Int, [Int])
 
inicial :: [Int] -> Estado
inicial ns = ([],0,ns)
 
esFinal :: Estado -> Bool
esFinal (xs,s,_) =
  not (null xs) && s == 0
 
sucesores :: Estado -> [Estado]
sucesores (xs,s,ns) =
  [(n:xs, n+s, delete n ns) | n <- ns]
 
soluciones :: [Int] -> [Estado]
soluciones ns =
  buscaProfundidad sucesores esFinal (inicial ns)
 
suma0 :: [Int] -> [[Int]]
suma0 ns =
  nub [sort xs | (xs,_,_) <- soluciones ns]
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    suma0 [-7,-3,-2,5,8] `shouldBe`
    [[-3,-2,5]]
  it "e2" $
    suma0 [-7,-3,-2,5,8,-1] `shouldBe`
    [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]
  it "e3" $
    suma0 [-7,-3,1,5,8] `shouldBe`
    []
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0098 seconds
--    3 examples, 0 failures

Soluciones en Python

from src.BusquedaEnProfundidad import buscaProfundidad
 
# Los estados son ternas formadas por los números seleccionados, su
# suma y los restantes números.
Estado = tuple[list[int], int, list[int]]
 
def inicial(ns: list[int]) -> Estado:
    return ([], 0, ns)
 
def esFinal(e: Estado) -> bool:
    (xs,s,_) = e
    return xs != [] and s == 0
 
def sucesores(e: Estado) -> list[Estado]:
    (xs, s, ns) = e
    return [([n] + xs, n + s, [m for m in ns if m !=n])
            for n in ns]
 
def soluciones(ns: list[int]) -> list[Estado]:
    return buscaProfundidad(sucesores, esFinal, inicial(ns))
 
def suma0(ns: list[int]) -> list[list[int]]:
    xss = [list(sorted(s[0])) for s in soluciones(ns)]
    r = []
    for xs in xss:
        if xs not in r:
            r.append(xs)
    return r
 
# Verificación
# ============
 
def test_suma0() -> None:
    assert suma0([-7,-3,-2,5,8]) == \
        [[-3,-2,5]]
    assert suma0([-7,-3,-2,5,8,-1]) == \
        [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]
    assert not suma0([-7,-3,1,5,8])
    print("Verificado")
 
# La verificación es
#    >>> test_suma0()
#    Verificado

Leer más →

El problema del dominó (con espacios de estados)

José A. Alonso, 29-agosto-2023, Haskell y Python

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

   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,

   λ> 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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

Leer más →

El problema del calendario mediante búsqueda en espacio de estado

José A. Alonso, 24-agosto-2023, Haskell y Python

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
   --+--------------
   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

   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,

   λ> 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.

Soluciones en Haskell

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

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

Soluciones en Python

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")

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")

Leer más →

El problema de las fichas mediante búsqueda en espacio de estado

José A. Alonso, 19-agosto-2023, Haskell y Python

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

      +---+---+---+---+---+---+---+
      | B | B | B |   | V | V | V |
      +---+---+---+---+---+---+---+

y el final es

      +---+---+---+---+---+---+---+
      | 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 constructores B, V y H que representan las fichas blanca, verde y hueco, respectivamente.

     data Ficha = B | V | H
       deriving (Eq, Show)

Tablero que es una lista de fichas que representa las fichas colocadas en el tablero.

     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).

     newtype Estado = E [Tablero]
       deriving (Eq, Show)

Busqueda es un procedimiento de búsqueda

     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

      +---+---+---+---+---+---+---+
      | 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

   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,

   λ> 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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

Leer más →

Etiqueta: Espacio de estados

Problema de las jarras (con espacios de estados)

Problema de suma cero (con espacios de estados)

El problema del dominó (con espacios de estados)

El problema del calendario mediante búsqueda en espacio de estado

El problema de las fichas mediante búsqueda en espacio de estado

Subscribe to Blog via Email

Entradas recientes

Etiquetas