Iam_Sandeep

Water Jug problem bfs

Jun 24th, 2022 (edited)
550
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #method 1:
  3. from math import gcd
  4. class Solution:
  5.     def canMeasureWater(self, a: int, b: int, d: int) -> bool:
  6.         if d>a+b:return False
  7.         return d%gcd(a,b)==0
  8.        
  9. #to find no of steps
  10. from math import gcd
  11. def minSteps( m, n, d):
  12.     return mins(m,n,d)
  13. def find(m,n,d):
  14.     x,y,c1=m,0,1
  15.     while not(x==d or y==d ):
  16.         val=min(x,n-y)
  17.         x,y=x-val,y+val
  18.         c1+=1
  19.         if x==d or y==d:break
  20.         if x==0:
  21.             x=m
  22.             c1+=1
  23.         if y==n:
  24.             y=0
  25.             c1+=1
  26.     return c1
  27.        
  28. def mins(m,n,d):
  29.     if m<d and d>n:return -1
  30.     if d%gcd(m,n)!=0:return -1
  31.     c1,c2=0,0
  32.     x,y=m,0
  33.     a=find(m,n,d)
  34.     b=find(n,m,d)
  35.     return  min(a,b)
  36. return minSteps(m,n,d)
  37.  
  38. #method 2:
  39. from collections import deque
  40. class Solution:
  41.     def canMeasureWater(self, a: int, b: int, tar: int) -> bool:
  42.         q=deque()
  43.         q.append((0,0))
  44.         vis=set()
  45.         vis.add(0)
  46.         while  q:
  47.             for _ in range(len(q)):
  48.                 #print(q)
  49.                 t,c=q.popleft()
  50.                 for i in (a,b,-a,-b):
  51.                     nt=t+i
  52.                     if nt==tar:return True
  53.                     if nt in vis:continue
  54.                     vis.add(nt)    
  55.                     if 0<=nt<=a+b:q.append((nt,c+1))
  56.         return False
  57.  #method 3                
  58. from collections import deque
  59. class Solution:
  60.     def canMeasureWater(self, a: int, b: int, tar: int) -> bool:
  61.         q=deque()
  62.         q.append((0,0,0))
  63.         vis=set()
  64.         while q:
  65.             for _ in range(len(q)):
  66.                 #print(q)
  67.                 i,j,c=q.popleft()
  68.                 if (i,j) in vis:continue
  69.                 vis.add((i,j))
  70.                 if not(0<=i<=a and 0<=j<=b):continue
  71.                
  72.                 if i==tar or j==tar or i+j==tar:return True
  73.                
  74.                    
  75.                 #pour water from jug2 to jug1
  76.                
  77.                 q.append((min(i+j,a),max(j-(a-i),0),c+1))
  78.                
  79.                
  80.                 #pour water from jug1 to jug2
  81.                 q.append((max(i-(b-j),0),min(i+j,b),c+1))
  82.                
  83.                 #empty jug1
  84.                 q.append((0,j,c+1))
  85.                
  86.                 #empty jug2
  87.                 q.append((i,0,c+1))
  88.                
  89.                 q.append((i,b,c+1))
  90.                
  91.                 q.append((a,j,c+1))
  92.         return False
  93.   #method3:
  94.                
  95.                    
  96.                
  97.                    
  98.                
  99.                
  100.                
  101.                    
  102.                    
  103.                
  104.            
  105.                    
  106.            
  107.        
RAW Paste Data Copied