# Jug pouring puzzle in Mathematica

Using two unmarked 5 and 3 gallon jugs, obtain exactly 1 gallons in one of these jugs by filling, pouring, and emptying operations. Assume there is an endless supply of water.

My approach:

I use the following variables.

jug1=5; jug2=3; jugObj=1; (*objective*)
nodes={};
paths={};


I have defined the following functions.
1. possibleStates - this includes filling, emptying, and transferring.

possibleStates[x_,y_]:={{jug1, y}, {x, jug2}, {x, 0}, {0, y}, {x+y, 0},
{0,x+y}, {jug1, x+y-jug1},{x+y-jug2, jug2}};


2. nextState - the states to be visited. If the input has the required quantity, then empty state is returned.

nextState[x_,y_,n_]:=
If[x== n||y== n,
Return[{{}}];,
(Cases[possibleStates[x,y],
m_/;(0<= m[[1]]<= jug1&&0<= m[[2]]<= jug2
&&{x,y}!={m[[1]],m[[2]]}&&!MemberQ[nodes,m])]//Union)//Return];


3. bfsJugPour - states which are encountered are added to paths and nodes. The paths variable contains directed elements. The nodes variable contains only nodes which have been visited.

bfsJugPour[x_,y_]:=
{nextState[x,y,jugObj],
If[nextState[x,y,jugObj]!={{}},
paths={paths,Map[{x,y}-> #&,nextState[x,y,jugObj]]}~Flatten~1//Union],
nodes={nodes,{{x,y}},nextState[x,y,jugObj]}~Flatten~1//Union};


Finally, I do a breadth first search (BFS) using NestWhile with the following arguments.

1. The main argument maps bfsJugPour to all of the possible next states,
2. Initial state {{{{0,0}}}},
3. Condition check: if the next state is an empty list, then stop the nesting.

 NestWhile[
Map[bfsJugPour @@ # &, (#[[;; , 1]] //. {{}} -> Sequence[])~Flatten~
1 // Union] &, {{{{0, 0}}}}, Flatten[#] != {} &];
TreePlot[paths, Automatic, {0, 0}, VertexLabeling -> True,
DirectedEdges -> True]


As can be seen from the above approach, the variables, paths and nodes are mutable, and it is kind of hard to understand. Is there any other way to approach this problem ?

• Commented Mar 20, 2017 at 11:48
• @J.M. Thanks for the link. Commented Mar 20, 2017 at 11:52

IntegerPartitions[1, 4, {-5, -3, 3, 5}]

{{3, 3, -5}}

• This is very interesting. Never thought IntegerPartitions can be used like this. Commented Mar 20, 2017 at 11:49