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 ?

• – J. M. is away Mar 20 '17 at 11:48
• @J.M. Thanks for the link. – Anjan Kumar Mar 20 '17 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. – Anjan Kumar Mar 20 '17 at 11:49