LeetCode - Water and Jug Problem

June 25, 2016 Author: Lina Chu

leetcode Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

Operations allowed:

Fill any of the jugs completely.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:

1 2	Input: x = 2, y = 6, z = 4 Output: True

Example 2:

1 2	Input: x = 2, y = 6, z = 5 Output: False

Source：leetcode Water and Jug Problem

The first thought to solve this problem is using deep first search. By Defining the following function:

fill(x, x_water, y, y_water, z)

We have the following options:

If a simple calculation of the current value of water can get the target z, we are done.

Fill the water from x to y based on x_water, y and y_water.

#put water in x to y:
    if x_water > 0:
        y_remain = y - y_water
        if x_water > y_remain:
            if fill(x, x_water - y_remain, y, y, z):
                return True
        else:
            if fill(x, 0, y, x_water + y_water, z):
                return True

#put water in x to y:

if x_water > 0:

y_remain = y - y_water

if x_water > y_remain:

if fill(x, x_water - y_remain, y, y, z):

return True

else:

if fill(x, 0, y, x_water + y_water, z):

return True

Fill the water from y to x based on y_water, x and x_water.

    #put  water in y to x
    if y_water > 0:
        x_remain = x - x_water
        if y_water > x_remain:
            if fill(x, x, y, y_water - x_remain, z):
                return True
        elif fill(x, x_water + y_water, y, 0, z):
            return True

#put water in y to x

if y_water > 0:

x_remain = x - x_water

if y_water > x_remain:

if fill(x, x, y, y_water - x_remain, z):

return True

elif fill(x, x_water + y_water, y, 0, z):

return True

We can use the idea of memorization to return immediately if one state has been reached and the result is False.

def is_visited(x_water, y_water, visited):
 return (x_water, y_water) in visited
def fill(x, x_water, y, y_water, z):
    if is_visited(x_water, y_water, visited):
        return False
    if not res.get((x_water, y_water), True):
        return False
    visited.add((x_water, y_water))
    print x, x_water, y, y_water, z
    if x_water == z or y_water == z:
        return True
    if x_water + y_water == z:
        return True
    #empty x:
    if x_water > 0:
        if fill(x, 0, y, y_water, z):
            return True
    #put water in x to y:
    if x_water > 0:
        y_remain = y - y_water
        if x_water > y_remain:
            if fill(x, x_water - y_remain, y, y, z):
                return True
        else:
            if fill(x, 0, y, x_water + y_water, z):
                return True
    #empty y:
    if y_water > 0 and fill(x, x_water, y, 0, z):
        return True
    #put  water in y to x
    if y_water > 0:
        x_remain = x - x_water
        if y_water > x_remain:
            if fill(x, x, y, y_water - x_remain, z):
                return True
        elif fill(x, x_water + y_water, y, 0, z):
            return True
    #fill x up
    if x_water != x  and fill(x, x, y, y_water, z):
        return True
    #fill y up
    if y_water != y  and fill(x, x_water, y, y, z):
        return True
    res[(x_water, y_water)] = False
    return False

def is_visited(x_water, y_water, visited):

return (x_water, y_water) in visited

def fill(x, x_water, y, y_water, z):

if is_visited(x_water, y_water, visited):

return False

if not res.get((x_water, y_water), True):

return False

visited.add((x_water, y_water))

print x, x_water, y, y_water, z

if x_water == z or y_water == z:

return True

if x_water + y_water == z:

return True

#empty x:

if x_water > 0:

if fill(x, 0, y, y_water, z):

return True

#put water in x to y:

if x_water > 0:

y_remain = y - y_water

if x_water > y_remain:

if fill(x, x_water - y_remain, y, y, z):

return True

else:

if fill(x, 0, y, x_water + y_water, z):

return True

#empty y:

if y_water > 0 and fill(x, x_water, y, 0, z):

return True

#put water in y to x

if y_water > 0:

x_remain = x - x_water

if y_water > x_remain:

if fill(x, x, y, y_water - x_remain, z):

return True

elif fill(x, x_water + y_water, y, 0, z):

return True

#fill x up

if x_water != x and fill(x, x, y, y_water, z):

return True

#fill y up

if y_water != y and fill(x, x_water, y, y, z):

return True

res[(x_water, y_water)] = False

return False

The above method can not pass when x, y are too large. It turned out that this problem is equal to the following problem:

m * x + n * y = z, with the constraint that m and n are integers.

It turns out that, only when z % GCD(x,y) == 0, the above equation has valid solutions.

class Solution(object):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        return x + y == z or ((x + y > z) and z % gcd(x, y) == 0)