Problema de las jarras
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) []