How do I make this Python solution fast enough for OJ?


  • 0
    D
    	def canMeasureWater(self, x, y, z):
    		if not z or z in (x,y,x+y): return True
    		checked = {(0,0)}
    		queue = [(x,0),(0,y)]
    		def check(a,b):
    			if (a,b) not in checked:
    				checked.add((a,b))
    				queue.append((a,b))
    			return a + b == z
    		while queue:
    			a,b = queue.pop(0)
    			possibilities = [
    				(0, b), # pour out jug 1
    				(x, b), # fill jug 1
    				(a, 0), # pour out jug 2
    				(a, y), # fill jug 2
    				(max(0, a-(y-b)), min(y, b+a)), # pour jug 1 into jug 2
    				(min(x, a+b), max(0, b-(x-a))) # pour jug 2 into jug 1   
    			]
    			if any([check(pa,pb) for pa, pb in possibilities]): return True
    		return False
    

    The idea is to do a DFS on each combination of the amount of water in the jugs. It passes test cases for small numbers but gets TLE on larger ones.


  • 0
    Z

    maybe you could exclude some duplicate issue.
    if current state is (0,b), the next step can't be:
    empty jug 1
    empty jug 2
    fill jug2
    pour jug 1 in to jug 2


Log in to reply
 

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