-
Notifications
You must be signed in to change notification settings - Fork 0
/
more-pour.py
105 lines (88 loc) · 3.6 KB
/
more-pour.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# -----------------
# User Instructions
#
# In this problem, you will solve the pouring problem for an arbitrary
# number of glasses. Write a function, more_pour_problem, that takes
# as input capacities, goal, and (optionally) start. This function should
# return a path of states and actions.
#
# Capacities is a tuple of numbers, where each number represents the
# volume of a glass.
#
# Goal is the desired volume and start is a tuple of the starting levels
# in each glass. Start defaults to None (all glasses empty).
#
# The returned path should look like [state, action, state, action, ... ]
# where state is a tuple of volumes and action is one of ('fill', i),
# ('empty', i), ('pour', i, j) where i and j are indices indicating the
# glass number.
def more_pour_problem(capacities, goal, start=None):
"""The first argument is a tuple of capacities (numbers) of glasses; the
goal is a number which we must achieve in some glass. start is a tuple
of starting levels for each glass; if None, that means 0 for all.
Start at start state and follow successors until we reach the goal.
Keep track of frontier and previously explored; fail when no frontier.
On success return a path: a [state, action, state2, ...] list, where an
action is one of ('fill', i), ('empty', i), ('pour', i, j), where
i and j are indices indicating the glass number."""
# your code here
def g (state):
print state, capacities, [x == goal for x in state]
return any([x == goal for x in state])
def succ (state):
#print '/', state, capacities
dic = {}
for i,c in [ (i,c)
for i,c in enumerate(state)
if state[i] < capacities[i] ]:
l = list(state)
l[i] = capacities[i]
dic [tuple(l)] = ('fill', i)
for x,y in [ (x,y)
for x in range(len(state))
for y in range(len(state))
if x!=y
if state[x] > 0 ]:
l = list(state)
# l[y] += l[x]
# l[x] = 0
k = min(capacities[y] - state[y], state[x])
l[y] = state[y] + k
l[x] = state[x] - k
dic[tuple(l)] = ('pour', x, y)
return dic
s = tuple([start] if start else [0]*len (capacities))
print '### ', capacities, s
return shortest_path_search(s, succ, g)
def shortest_path_search(start, successors, is_goal):
"""Find the shortest path from start state to a state
such that is_goal(state) is true."""
if is_goal(start):
return [start]
explored = set()
frontier = [ [start] ]
while frontier:
path = frontier.pop(0)
s = path[-1]
for (state, action) in successors(s).items():
if state not in explored:
explored.add(state)
path2 = path + [action, state]
if is_goal(state):
#print '$', path2
return path2
else:
frontier.append(path2)
return Fail
Fail = []
def test_more_pour():
assert more_pour_problem((1, 2, 4, 8), 4) == [
(0, 0, 0, 0), ('fill', 2), (0, 0, 4, 0)]
assert more_pour_problem((1, 2, 4), 3) == [
(0, 0, 0), ('fill', 2), (0, 0, 4), ('pour', 2, 0), (1, 0, 3)]
starbucks = (8, 12, 16, 20, 24)
assert not any(more_pour_problem(starbucks, odd) for odd in (3, 5, 7, 9))
assert all(more_pour_problem((1, 3, 9, 27), n) for n in range(28))
assert more_pour_problem((1, 3, 9, 27), 28) == []
return 'test_more_pour passes'
print test_more_pour()