Problema de las jarras (con espacios de estados)
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
|
1 |
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,
|
1 2 3 4 |
λ> 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
|
1 2 3 4 5 6 |
λ> 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.
|
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 |
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 |
|
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 |
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 |