Problema de las 3 jarras
En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).
Definir las funciones
1 2 |
solucionesTresJarras :: Problema -> [[Estado]] tresJarras :: Problema -> Maybe [Estado] |
tales que
- (solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
λ> mapM_ print (solucionesTresJarras (4,2,1)) [(4,0,0),(2,2,0)] [(4,0,0),(3,0,1),(1,2,1),(2,2,0)] [(4,0,0),(3,0,1),(3,1,0),(2,2,0)] [(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)] [(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)] λ> mapM_ print (solucionesTresJarras (8,6,2)) [(8,0,0),(2,6,0),(2,4,2),(4,4,0)] [(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)] [(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)] [(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)] [(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)] [(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)] [(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)] [(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)] λ> length (solucionesTresJarras (8,5,3)) 16 λ> head (solucionesTresJarras (8,5,3)) [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)] λ> length (solucionesTresJarras (8,6,5)) 0 |
- (tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> tresJarras (4,2,1) Just [(4,0,0),(2,2,0)] λ> tresJarras (8,6,2) Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)] λ> tresJarras (8,5,3) Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)] λ> tresJarras (8,6,5) Nothing |
Soluciones
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 |
import Data.Maybe (listToMaybe) -- Para simplificar la notación se definen los tipos Problema y Estado -- como sigue. -- Un problema es una terna de números. El primero es la capacidad de la -- primera jarra, el segundo el de la segunda y el tercero el de la -- tercera. type Problema = (Int,Int,Int) -- Un estado es una terna de números. El primero es el contenido de la -- jarra de A litros, el segundo el de la de B litros y el tercero el de -- la de C litros. type Estado = (Int,Int,Int) solucionesTresJarras :: Problema -> [[Estado]] solucionesTresJarras p = busca [[inicial p]] where busca [] = [] busca ((e:es):ns) | esFinal p e = reverse (e:es) : busca ns | otherwise = busca (ns ++ [e1:e:es | e1 <- sucesores p e , e1 `notElem` es]) -- (inicial p) es el estado inicial del problema p. Por ejemplo, -- inicial (8,5,3) == (8,0,0) inicial :: Problema -> Estado inicial (a,_,_) = (a,0,0) -- (esFinal p e) es verifica si e es un estado final del problema de las -- tres jarras p. Por ejemplo, -- esFinal (8,5,3) (4,4,0) == True -- esFinal (8,5,3) (4,0,4) == False esFinal :: Problema -> Estado -> Bool esFinal (a,_,_) (x,y,z) = x == y && x + y == a -- (sucesores p e) es la lista de los sucesores del estado e en el -- problema de las tres jarras p. Por ejemplo, -- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)] -- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)] sucesores :: Problema -> Estado -> [Estado] sucesores (a,b,c) (x,y,z) = [(x-ab,y+ab,z) | let ab = min x (b-y), ab > 0] ++ [(x-ac,y ,z+ac) | let ac = min x (c-z), ac > 0] ++ [(x+ba,y-ba,z) | let ba = min y (a-x), ba > 0] ++ [(x ,y-bc,z+bc) | let bc = min y (c-z), bc > 0] ++ [(x+ca,y ,z-ca) | let ca = min z (a-x), ca > 0] ++ [(x ,y+cb,z-cb) | let cb = min z (b-y), cb > 0] tresJarras :: Problema -> Maybe [Estado] tresJarras p = listToMaybe (solucionesTresJarras p) |
Un comentario