1
$\begingroup$

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]
    

enter image description here


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 ?

$\endgroup$
5
$\begingroup$

I get the feeling you want something more "advanced" than this but the first thing I would do is:

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

That gives me a way to add up the volumes to one. Some logic is required to apply it, but it's pretty straightforward: fill the 5 gallon jug twice using the 3 gallon jug, stop when full, observe remainder of 1 gallon.

$\endgroup$
  • $\begingroup$ This is very interesting. Never thought IntegerPartitions can be used like this. $\endgroup$ – Anjan Kumar Mar 20 '17 at 11:49
  • $\begingroup$ Fantastic. +1 not for code but excellent abstract thinking. $\endgroup$ – LLlAMnYP Mar 20 '17 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.