Understanding the Python Code:

[zak100]

Hi,

I am trying to understand the following python code:

from collections import defaultdict


j1 = 5  
j2 = 3  
# aim = int(input("Enter the capacity of goal litters : "))

# the already visited node is to stored to save time and memory.
visited = defaultdict(lambda: False)


def waterJugSolver(amt1, amt2):
    if (amt1 == 1 and amt2 == 0):
        print(amt1, amt2)
        return True

    if visited[(amt1, amt2)] == False:
        print(amt1, amt2)

        visited[(amt1, amt2)] = True

        if (waterJugSolver(0, amt2)):
            exit(1)
        if (waterJugSolver(amt1, 0)):
            exit(1)
        if (waterJugSolver(j1, amt2)):
            exit(1)
        if (waterJugSolver(amt1, j2)):
            exit(1)
        if (waterJugSolver(amt1 + min(amt2, (j1 - amt1)), amt2 - min(amt2, (j1 - amt1)))):
            exit(1)
        if (waterJugSolver(amt1 - min(amt1, (j2 - amt2)), amt2 + min(amt1, (j2 - amt2)))):
            exit(1)

    else:
        return False


print("Steps: ")

waterJugSolver(4, 2)

I am getting the following output:

Quote

4 2
0 2
0 0
5 0
5 3
0 3
3 0
3 3
5 1
0 1
1 0

First iteration is 4,2 which is fine. But i can't understand the remaining iterations but I understand how we get the final result of 1,0. Somebody please guide me how the program displays the out 0 2, 0 0, 5 0, 5 3. If I get this understanding, I would be able to understand the code. (Note for Editing code, click Edit and then press on angle brackets.

Edited September 19, 2020 by zak100

[Ghideon]

3 hours ago, zak100 said:

But i can't understand the remaining iterations but I understand how we get the final result of 1,0. Somebody please guide me how the program displays the out 0 2, 0 0, 5 0, 5 3.

It may be easer to answer your questions if you explain some context what the program is supposed to do. Here is my guess what the program is supposed to do and what means:

Using a 5 liter and a 3 liter jug and starting with 4 liters in jug 1 and 2 liters in jug 2 perform the necessary steps to reach the goal of 1 liter in jug 1 and 0 liter in jug 2. Water may be poured out on ground and new water added from an infinite tap

Steps:
4 2 (Starting with 4 liters in jug 1 and 2 liters in jug 2)
Empty jug 1
0 2
Empty jug 2
0 0
Fill jug 1 from tap
5 0
Fill jug 2 from tap
5 3
Empty jug 1
0 3
Fill jug 1 from jug 2
3 0
Fill jug 2 from tap
3 3
Fill jug 1 from jug 2
5 1
Empty jug 1
0 1
Fill jug 1 from jug 2
1 0

Done

 

Edited September 19, 2020 by Ghideon

[zak100]

Hi,

Thanks for explaining me this whole process. I would come back to the program later on. Right on I am thinking of the fact that if initially we have (4, 2) why our program does not start from this situation:

i.e. Empty jug2

(4, 0)

Pour jug1 water into jug2

(1, 3)

Empty jug2

(1, 0)

 

Please guide me why we can't solve the problem in this manner?

Thanks for helping me to understand the output.

 

God blesses you.

 

Now I would like to discuss about the program:

1) What is the purpose of exit command?

I found that it is used to exit. So it is same as ending th eprogram

2)We have several calls to WaterJugSolver(...) so its a recursive program. For 1st call (4,2), 1st if is false. After that we would come to 2nd if, in which case is false so we would print (4,2). Then we come to the statement: visited[(4, 2)]= True, what is the purpose of this statement

3)Then we come to the statement:

if (waterJugSolver(0, amt2)):
            exit(1)

which is false because we have (4,2), then we would come to the statement:

if (waterJugSolver(amt1 + min(amt2, (j1 - amt1)), amt2 - min(amt2, (j1 - amt1)))):
            exit(1)

i.e.if(waterJugSolver(4+min(2, (5-4)), 2 - min(2,(5 - 4)))):

i.e. if(waterJugSolver(4+min(2, 1), 2-min(2, 1)))

i.e. if(waterJugSolver(5, 2-1))

i.e. if water JugSolver(5, 1)

Am I write? I don't think so, 2nd output is: 0,2

Please guide me.

Zulfi.

Zulfi.

[Ghideon]

Where did you get the program from? What does the author of the program state about the program's purpose? Is there more documentation?

6 hours ago, zak100 said:

Please guide me why we can't solve the problem in this manner?

The program does not seem to be constructed to look for that kind of solution. But I do not know if that is by design or a mistake by the author. I know what the program does and I can explain how the program works. But I do not know why it was created that way. 

6 hours ago, zak100 said:

2)We have several calls to WaterJugSolver(...) so its a recursive program.

Yes.

6 hours ago, zak100 said:

if (waterJugSolver(0, amt2)):

waterJugSolver is called, and have to run and return a result. Then the if statement evaluates wether that call to waterJugSolver returns true or false. The recursive call to waterJugSolver will result in printouts, further calls to waterJugSolver etc. You may want to check up on recursion first, that makes it easier to understand the specific steps this program runs through and in what order the statements are executed?

There are also plenty of debuggers that are useful. By using the "step"/"Step into" functions typically available will let you see each step and what data that the program has available. You can check your other threads for more info on debuggers, no need to repeat it again here.

 

[Ghideon]

On 9/20/2020 at 6:57 AM, zak100 said:

i.e. Empty jug2

(4, 0)

Pour jug1 water into jug2

(1, 3)

Empty jug2

(1, 0)

 

Please guide me why we can't solve the problem in this manner?

In case you are still working on this, here is an alternative (maybe better) explanation.

The program is constructed to exit as soon as a solution is found.
The first thing the program tries is to empty the first jug and recursively look for a solution from that step.
This means that if there is (at least) one solution that starts with emptying jug 1 that is a solution the program will find.

visited[(amt1, amt2)] = True 
if (waterJugSolver(0, amt2)): 
  exit(1) 
if (waterJugSolver(amt1, 0)): 
  exit(1)

It seems like you are asking why the program does not find a solution with few steps? The program is written to stop as soon as a solution is found. There is no guarantee that is the solution with few or least number of steps. You could rewrite the program to look for alternative solutions and presenting the solution that fits the requirements (if such a solution exists)