Guest User

Jug puzzle

a guest
Mar 29th, 2018
147
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import collections
  2.  
  3. def jugPuzzle(jugs, goal, start=None):
  4.     '''Given n jugs of specified capacities, use BFS to try to find a sequence
  5.    of fillings, emptyings and transferings of water that will produce the goal
  6.    amount from the start state. Otherwise return empty list.'''
  7.     if not start:
  8.         start = (0,) * len(jugs)
  9.    
  10.     if not (0 <= goal <= max(jugs)):
  11.         return []
  12.    
  13.     if goal in start:
  14.         return [('start', start)]
  15.        
  16.     paths = collections.deque([[('start', start)]])
  17.     seen = set([start])
  18.    
  19.     while paths:
  20.         path = paths.popleft()
  21.         lastAction, lastState = path[-1]
  22.          
  23.         for action, state in successors(jugs, lastState):
  24.             if state not in seen:
  25.                 currPath = path + [(action, state)]
  26.                
  27.                 # goal reached
  28.                 if goal in state:
  29.                     return currPath
  30.                    
  31.                 paths.append(currPath)
  32.                 seen.add(state)
  33.                      
  34.     # no path found    
  35.     return []
  36.                      
  37. def successors(jugs, levels):
  38.     '''Compute all non-trivial successor states. Return as a list of (action, state) tuples.'''
  39.     result = []
  40.     L = len(jugs)
  41.    
  42.     for i in range(L):
  43.         if levels[i] < jugs[i]:
  44.             action = 'fill %d' % i
  45.             state = tuple(jugs[j] if j == i else levels[j] for j in range(L))
  46.             result.append((action, state))
  47.    
  48.         if levels[i] > 0:
  49.             action = 'empty %d' % i
  50.             state = tuple(0 if j == i else levels[j] for j in range(L))
  51.             result.append((action, state))
  52.            
  53.             for j in range(L):
  54.                 if j != i and levels[j] < jugs[j]:
  55.                     action = '%d -> %d' % (i, j)
  56.                     total = levels[i] + levels[j]
  57.                     iLevel = max(0, total - jugs[j])
  58.                     jLevel = min(jugs[j], total)
  59.                     state = tuple(iLevel if k == i else jLevel if k == j
  60.                                                    else levels[k] for k in range(L))
  61.                     result.append((action, state))
  62.                    
  63.     return result
  64.    
  65. # demo  
  66. print(*jugPuzzle([100, 13, 43], 98), sep='\n')
RAW Paste Data