Pouring water between two jugs to get a certain amount in one of the jugs (2)

Question

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)

Answer 1

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.