Everyone knows the classic water jug problem. You are by a stream with a 5-Litre and a 7-Litre bucket. How do you measure out 6-Litres in the fewest possible pourings? You first fill up the 7 and so on.
You might not have seen this particular problem but you have definitely heard of a problem like this. But what many people do not know about this problem is you can actually solve it using the points of a Parallelogram or what some people call a pool table. If you translate your starting amount of water as 5 litres in the 5-litre jug, then you can translate it to (0,5). You can keep it bouncing off the points until you desired amount in the x or y. The parallelogram does the exact same thing as what we just did in the table above.
I found that it was easier to find the patterns if I made the parallelogram a rectangle. There are 4 different variables you need to use this. The current x and y, the method you are using and the side & top length. Once you have those 4 variables you can make any table. I strongly recommend following each line with your finger as I tell you the rules:
Phesudocode
The Total Method:
The Total Method is when you add up the x and y and then flip it to the other side of the rectangle. If you look at the start point of the line and the endpoint of the line then the x+y will equal the same. There are 2 rules in the total method
- if the red line is going horizontally down, then return the number that is minimum of (top length or x+y) and they as the maximum number that is either ((x+y- top length) or 0).
How does rule 1 work?
Count until you reach x+y from the bottom left to the bottom right and go up the right line if you reach it.
- If the red line is going horizontally up then return x as the maximum of either ((x+y)- side length or 0) and the y as the minimum of either (side length or (x+y).
How does rule 2 work?
Count until you reach x+y from the bottom left to the top of the left line and go up the right line until you reach it.
The Swap Method:
The swap method swaps the x or y depending on which line it is on. The swap method is made up of 4 smaller rules that each change specific variables in the coordinates depending on which side of the rectangle you are using the swap method on.
- if x = 0 then return the top length and y
This is done as we need to flip 0,2 to
- if y = 0 then return x with side length
- if y = the side length then return x and 0
- if x = the top length then return 0 and y
We can also find out that to start the bouncing of the parallelogram, it will always start with the total method and then switch to the swap method and then back to the total method and so on.
Python code
The Swap Method
jugs = []
numberOfJugs = 2
def swapMethod(x,y, tLength, sLength):
if x == 0:
print("added")
return tLength, y
elif y == 0:
print("else ", x, sLength)
return x,sLength
elif y == sLength:
print("x: ",x, "y: ", y,)
return x,0
elif x == tLength:
print(0,y)
return 0,y
...
The Total Method
...
def totalMethod(x,y, maxi, minu):
if x == 0 or y == minu:
return min(maxi, (x+y)), max((x+y-maxi), 0)
else:
return max((x+y-minu), 0), min(minu, (x+y))
...
The calling
...
targetCapacity = 6
tLength, sLength = 7,5
x,y = 0,5
history = f'''
_____{tLength}___{sLength}_|
01 | {x} | {y} |
'''
x,y = totalMethod(x,y, tLength, sLength)
past = 0
history += f'02 | {x} | {y} |\n'
for i in range(0,10):
if x == targetCapacity or y == targetCapacity:
break
if past == 0:
x,y = swapMethod(x,y,tLength,sLength)
past = 1
else:
x,y = totalMethod(x,y, tLength, sLength)
past = 0
history += f'{i+3:02} | {x} | {y} |\n'
print(history)
Full code here
Closing notes
If you want to see a more complete version with inputs look on my GitHub here.
Thanks to my math teacher for showing me this problem. It was a fun challenge.
