# 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)
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