3
\$\begingroup\$

I have been practicing recursion lately and I came up with this code to solve the water jug problem, given two jugs of volume jug1 and jug2, where jug1 < jug2, obtain a volume t, where t < jug2.

The algorithm below basically always pours from the smaller jug into the bigger jug, how would you improve the solution ?

I think I get the minimum number of steps this way... am I correct ?

jug1 = 5
jug2 = 7
t = 4

def jugSolver(amt1, amt2):

    print(amt1, amt2)

    if (amt1 == t and amt2 == 0) or (amt1 == 0 and amt2 == t):
        return

    elif amt2 == jug2:
        jugSolver(amt1, 0)

    elif amt1 != 0:
        if amt1 <= jug2-amt2:
            jugSolver(0, amt1+amt2)
        elif amt1 > jug2-amt2:
            jugSolver(amt1-(jug2-amt2),amt2+(jug2-amt2))

    else:
        jugSolver(jug1, amt2)

jugSolver(0,0)
\$\endgroup\$
  • \$\begingroup\$ I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – AJNeufeld Nov 13 '18 at 20:08
3
\$\begingroup\$

Your code is not a “good” practice at recursion. Every “recursive” call to jugSolver is the last statement that is executed in the current call, thus the whole function can easily be replaced by a simple loop:

print(amt1, amt2)
while amt1 != t  and  amt2 != t:
    if amt2 = jug2:
        amt2 = 0
    elif amt1 != 0:
        if amt1 <= jug2 - amt2:
            amt1, amt2 = 0, amt1+amt2
        else:
            amt1, amt2 = amt1 - (jug2-amt2), jug2
    else:
        amt1 = jug1
    print(amt1, amt2)

Your assumption that pouring from the smaller jug into the bigger jug always results in the minimum number of steps is flawed. Consider t=2. Your way:

  • 5, 0
  • 0, 5
  • 5, 5
  • 3, 7
  • 3, 0
  • 0, 3
  • 5, 3
  • 1, 7
  • 1, 0
  • 0, 1
  • 5, 1
  • 0, 6
  • 5, 6
  • 4, 7
  • 4, 0
  • 0, 4
  • 5, 4
  • 2, 7

Compare with:

  • 0, 7
  • 5, 2

So you’ll need to relook at solving the problem with different possible moves.

\$\endgroup\$
  • \$\begingroup\$ I guess you're correct, thanks for the insights ! I'll be working on my skills more. \$\endgroup\$ – d_darric Nov 12 '18 at 8:30
  • \$\begingroup\$ Hello, I posted and edit if you have time to look at it ... thanks \$\endgroup\$ – d_darric Nov 13 '18 at 17:33
  • \$\begingroup\$ For the record, I did look at your second solution. “The problem is I’m struggling to ...” The Code Review Stack Exchange is for reviewing working code. Your second solution doesn’t work yet, since you want it to return the steps of the solution, which it does not do. Once your solution works, including returning the required steps, only then will it be appropriate to post here for reviewing and improving. \$\endgroup\$ – AJNeufeld Nov 14 '18 at 1:29
  • \$\begingroup\$ Makes sense, I will post it when I get it to work. \$\endgroup\$ – d_darric Nov 14 '18 at 9:34

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.