Se dispone de dos jarros, uno con una capacidad de 3 litros y otro con una capacidad de 4 litros. Ninguno de los dos tiene marcas que permitan medir cantidades que no sean las de sus propias capacidades.
Existe una pila de agua que permite llenar los jarros con agua y un sumidero donde se puede vaciar los mismos. El problema consiste en encontrar cuál es la secuencia de movimientos de llenado, vaciado y trasvase que permite obtener exactamente dos litros de agua en el jarro de 4 litros.
Primeramente pensemos en una forma de representar la solución del problema. En la implementación realizada se utilizó una lista de string, en la cual cada string representa una acción a realizar con las jarras. Por ejemplo la lista Solution de abajo contiene una solución válida del problema.
Solution = ['fill pitcher1', 'pitcher1 to pitcher2', 'fill pitcher1', 'pitcher1 to pitcher2', 'empty pitcher2', 'pitcher1 to pitcher2']
Para la solución del problema se considera que existen 6 tipos de acciones entre las jarras a tener en cuenta para la idea del algoritmo; estas son:
-
"fill pitcher1": Llenar la primera jarra de la pila de agua.
-
"fill pitcher2": Llenar la segunda jarra de la pila de agua.
-
"empty pitcher1": Vaciar la primera jarra en el sumidero.
-
"empty pitcher2": Vaciar la segunda jarra en el sumidero.
-
"pitcher1 to pitcher2": Echar el agua (que se pueda) de la primera jarra en la segunda.
-
"pitcher2 to pitcher1": Echar el agua (que se pueda) de la segunda jarra en la primera.
Una forma de atacar el problema y fácil de implementar, entender y explicar es, a consideración de los autores, modelando el problema a un problema de la teoría de grafos.
Sea G = <V, E> un grafo dirigido, donde al conjunto de vértices V pertenecen todos los estados posibles en los que pueden estar las dos jarras: el estado de una jarra es la cantidad de litros de agua que hay en ella. Por ejemplo, si en la primera jarra hay 1L de agua y en la segunda hay 3L, entonces el vértice de G que representa a dicho estado será state(1, 3). Las aristas de nuestro grafo serán precisamente el conjunto de pares de vértices <x, y> tal que el estado y se obtiene al realizar una de las 6 acciones anteriores al estado x. Por ejemplo, una arista de G es <state(1, 3), state(0, 4)>, ya que el estado state(0, 4) es el resultado de aplicar la quinta acción (echar el agua (que se pueda) de la primera jarra en la segunda) al estado state(1, 3).
Como lo que deseamos es encontrar una lista de acciones válidas que permitan, dado las jarras vacías, obtener en la segunda jarra exactamente dos litros, el problema se reduce a encontrar un camino en G desde el vértice state(0, 0) al state(_, 2). Es evidente que las aristas de un camino en G desde un vértice u a otro v representan una lista de acciones posibles a realizar para llevar las jarras del estado u al v.
Para encontrar dicho camino en G podemos realizar tanto un BFS como un DFS. Aprovechando las características de PROLOG, la solución presentada realiza un recorrido DFS.
solve(InitialState, FinalState, Actions) :- plan(InitialState, FinalState, Actions, [InitialState]).
plan(State, State, [], _) :- !.
plan(State1, State, [Action|R], States) :- go(State1, State2, Action),
not(member(State2, States)),
plan(State2, State, R, [State2|States]).
go( state(0, L2) , state(3, L2) , 'fill pitcher1' ).
go( state(L1, 0) , state(L1, 4) , 'fill pitcher2' ).
go( state(L1, L2), state(0, L2) , 'empty pitcher1') :- L1 > 0.
go( state(L1, L2), state(L1, 0) , 'empty pitcher2') :- L2 > 0.
go( state(L1, L2), state(L3, 4), 'pitcher1 to pitcher2') :- L1 > 0 , L2 < 4 , L2+L1 >= 4 , L3 is L1-(4-L2).
go( state(L1, L2), state(0, L4), 'pitcher1 to pitcher2') :- L1 > 0 , L2 < 4 , L2+L1 < 4 , L4 is L2+L1.
go( state(L1, L2), state(3, L4), 'pitcher2 to pitcher1') :- L2 > 0 , L1 < 3 , L1+L2 >= 3 , L4 is L2-(3-L1).
go( state(L1, L2), state(L3, 0), 'pitcher2 to pitcher1') :- L2 > 0 , L1 < 3 , L1+L2 < 3 , L3 is L1+L2.El predicado principal del código es solve, que recibe como parámetros un estado inicial, un estado final y una variable a unificar con una lista de string que será la solución del problema; dicho esto, la query formulada al intérprete para obtener la solución será:
?- solve(state(0, 0), state(_, 2), Solution).En la implementación podemos ver que el predicado plan contiene un parámetro más que el predicado solve. Este último es una lista que contiene a todos los vértices que he visitado hasta el momento con el objetivo de no pasar nuevamente por ellos a través de otro camino de G (técnica comúnmente utilizada en los recorridos de grafos); ese es precisamente el objetivo del cuerpo:
not(member(State2, States))El predicado go representa las transiciones entre vértices (aristas). Recibe el estado de inicio, estado de fin y un string que indica la acción que fue necesario llevar a cabo para pasar del estado de inicio al estado de fin.
-
Regla asociada a la primera acción
go( state(0, L2) , state(3, L2) , 'fill pitcher1' ).
-
Regla asociada a la segunda acción
go( state(L1, 0) , state(L1, 4) , 'fill pitcher2' ).
-
Regla asociada a la tercera acción
Es necesario comprobar que la primera jarra tenga agua.
go( state(L1, L2), state(0, L2) , 'empty pitcher1') :- L1 > 0.
-
Regla asociadas a la cuarta acción.
Es necesario comprobar que la segunda jarra tenga agua.
go( state(L1, L2), state(L1, 0) , 'empty pitcher2') :- L2 > 0.
-
Reglas asociadas a la quinta acción
La primera regla abarca el caso en el que la cantidad de litros de la primera jarra es mayor o igual que lo que le falta a la segunda para llenarse. La segunda regla es el caso complementario.
go( state(L1, L2), state(L3, 4), 'pitcher1 to pitcher2') :- L1 > 0 , L2 < 4 , L2+L1 >= 4 , L3 is L1-(4-L2). go( state(L1, L2), state(0, L4), 'pitcher1 to pitcher2') :- L1 > 0 , L2 < 4 , L2+L1 < 4 , L4 is L2+L1.
-
Reglas asociadas a la sexta acción
La primera regla abarca el caso en el que la cantidad de litros de la segunda jarra es mayor o igual que lo que le falta a la primera para llenarse. La segunda regla es el caso complementario.
go( state(L1, L2), state(3, L4), 'pitcher2 to pitcher1') :- L2 > 0 , L1 < 3 , L1+L2 >= 3 , L4 is L2-(3-L1). go( state(L1, L2), state(L3, 0), 'pitcher2 to pitcher1') :- L2 > 0 , L1 < 3 , L1+L2 < 3 , L3 is L1+L2.
Aprovechando las potencialidades del lenguaje de programación PROLOG, se ha implementado un lenguaje de dominio específico (DSL por sus siglas en inglés), con el objetivo de resolver este problema con una sintaxis más cercana al lenguaje natural.
-
go_to: Transición desde un estado (operador izquierdo) a otro (operador derecho).
-
not_in: Triunfa si un elemento (operador izquierdo) no pertenece a la lista (operador derecho).
-
to
-
with
-
fill
-
empty
:-op(800,xfx,go_to).
:-op(800,xfx,not_in).
:-op(900,xfx,to).
:-op(850,yfx,with).
:-op(900,fx,fill).
:-op(900,fx,empty).
X not_in L :- not(member(X, L)).
solve(InitialState, FinalState, Actions) :- plan(FinalState, Actions, [InitialState]).
plan(FinalState, [], [FinalState|_]) :- !.
plan(FinalState, [Action|R], [IniState|States]) :- IniState go_to NextState with Action,
NextState not_in States,
plan(FinalState, R, [NextState, IniState|States]).
state(0, L2) go_to state(3, L2) with (fill pitcher1).
state(L1, 0) go_to state(L1, 4) with (fill pitcher2).
state(L1, L2) go_to state(0, L2) with (empty pitcher1) :- L1 > 0.
state(L1, L2) go_to state(L1, 0) with (empty pitcher2) :- L2 > 0.
state(L1, L2) go_to state(L3, L4) with (pitcher1 to pitcher2) :- L1 > 0, L2 < 4, pour(L1, L2, L3, L4, 4).
state(L1, L2) go_to state(L3, L4) with (pitcher2 to pitcher1) :- L2 > 0, L1 < 3, pour(L2, L1, L4, L3, 3).
pour(L1, L2, L3, Limit, Limit) :- L2 + L1 >= Limit, !, L3 is L1 - (Limit - L2).
pour(L1, L2, 0, L4, _) :- L4 is L2 + L1.Cree un issue o envíe un pull request
Iván Galbán Smith ivan.galban.smith@gmail.com
Raydel E. Alonso Baryolo raydelalonsobaryolo@gmail.com
4th year Computer Science students, University of Havana