Breadth-First Search with explanation.


  • 16
    L

    It took me a while to understand the GCD method. My first attempt to this problem was using BFS, which is very intuitive and easy to understand.
    The complexity is definitely much longer than GCD-based method.

    class Solution(object):
        def canMeasureWater(self, x, y, z):
            """
            :type x: int
            :type y: int
            :type z: int
            :rtype: bool
            """
            if x > y:
                temp = x;
                x = y;
                y = temp;
                
            if z > x + y:
                return False;
            
            # set the initial state will empty jars;
            queue = [(0, 0)];
            visited = set((0, 0));
            while len(queue) > 0:
                a, b = queue.pop(0);
                if a + b == z:
                    return True;
                
                states = set()
                
                states.add((x, b)) # fill jar x;
                states.add((a, y)) # fill jar y;
                states.add((0, b)) # empty jar x;
                states.add((a, 0)) # empty jar y;
                states.add((min(x, b + a), 0 if b < x - a else b - (x - a))) # pour jar y to x;
                states.add((0 if a + b < y else a - (y - b), min(b + a, y))) # pour jar x to y;
    
                for state in states:
                    if state in visited:
                        continue;
                    queue.append(state)
                    visited.add(state);
                    
            return False;
    

  • 0

    Just tried your code, gets TLE for

    104639
    104651
    234
    

  • 4

    Great Solution even though it results in TLE on OJ. I translate your solution into Java, here is the code:

    public class Solution {
        public boolean waterJugProblem(int x, int y, int z) {
            if(x + y < z) return false;
            if(z == x || x == y || x == x + y) return true;
            
            if(x > y) {
                int tmp = x;
                x = y;
                y = tmp;
            }
    
            Queue<State> states = new ArrayDeque<>();
            Set<State> visited = new HashSet<>();
    
            // initial state
            State init = new State(0, 0);
            states.offer(init);
            visited.add(init);
    
            while(!states.isEmpty()) {
                State curr = states.poll();
                if(curr.a + curr.b == z) return true;
    
                // fill jug1
                Queue<State> queue = new ArrayDeque<>();
                queue.offer(new State(x, curr.b));      // fill jug 1
                queue.offer(new State(0, curr.b));      // empty jug1
                queue.offer(new State(curr.a, y));      // fill jug 2
                queue.offer(new State(curr.a, 0));      // empty jug2
                queue.offer(new State(Math.min(curr.a + curr.b, x),
                        curr.a + curr.b < x ? 0 : curr.b - (x - curr.a)));      // pour all water from jug2 to jug1
                queue.offer(new State(curr.a + curr.b < y ? 0 : curr.a - (y - curr.b),
                        Math.min(curr.a + curr.b, y)));                         // pour all water from jug1 to jug2
    
                for(State tmp: queue) {
                    if(visited.contains(tmp)) continue;
                    states.offer(tmp);
                    visited.add(tmp);
                }
            }
            return false;
        }
    
    
        class State {
            public int a, b;
    
            public State(int a, int b) {
                this.a = a;
                this.b = b;
            }
    
            public int hashCode() {
                return 31 * a + b;
            }
    
            public boolean equals(Object o) {
                State other = (State)o;
                return this.a == other.a && this.b == other.b;
            }
        }
    }
    

  • 0
    A

    Good try. That was my initial approach to the problem, trying to brute force recursively with 3 states (Empty, Fill, Partial fill) and 2 jugs, but being wayyy too cumbersome I didn't work out the details. Nice to see you put up a solution here. The GCD solution is impossible to figure out without knowing the Bezout's thereom.


  • 0
    X

    I used bfs with C++ but it is very slow

    class Solution {
    public:
        bool canMeasureWater(int x, int y, int z) {
    		if (z > x + y || z < 0) {
    			return false;
    		} else if (z == x || z == y || z == x + y) {
    			return true;
    		}
    		
    		int smaller = min(x, y); 
    		int larger = max(x, y);
    		return bfs(smaller, larger, z, 0);
        }
    private:
    	bool bfs(int smaller, int larger, int z, int water) {
    		unordered_set<int> visited;
    		queue<int> myqueue;
    		
    		myqueue.push(water);
    		visited.insert(water);
    		while (!myqueue.empty()) {
    			int curr = myqueue.front();
    			//visited.insert(curr);
    			if (curr == z) {
    				return true;
    			}
    			myqueue.pop();
    			
    			// 3 cases
    			vector<int> next;
    			if (curr < smaller) {
    				next.push_back(larger - (smaller - curr));
    			} else if (curr < larger) {
    				next.push_back(curr - smaller);
    			} else if (curr < larger + smaller) {
    				next.push_back(curr - smaller);
    				next.push_back(curr - larger);
    			}
    		
    			while(curr < larger && smaller > 0) {
    				curr += smaller;
    				next.push_back(curr);
    			}
    			
    			for (int i : next) {
    				if (visited.find(i) == visited.end()) {
    					visited.insert(i);
    					myqueue.push(i);
    				}
    			}
    		}
    		return false;
    	}
    };
    

  • 0
    X

    @xiliuzju You may need to change the inner while to pass this case [1, 2, 3]

    while (cur <= b && a > 0){
                    cur += a; 
                    next.push_back(cur); 
                }
    

  • 0
    S

    I upvoted this solution because this is a coding question, we need focus more on solving the problem by coding, not by math. BFS is not slow for this question actually, though there is a faster math solution. Time complexity of BFS is O(x + y) which can be treated as linear (Because there are only 2x + 2y possible states.). I guess it is acceptable in interview..


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.