In [28]:
def pour_solution(X, Y, goal, start=(0, 0)):
"""X and Y are the capacity of glasses; (x, y) is current fill levels
and represents a state. The goal is a level that can be in either glass.
Start at start state and follow successors until we reach the goal.
Keep track of frontier and previously explored; fail when no frontier"""
if goal in start:
return [start]
explored = set() # set of states we have visited
frontier = [[start]] # ordered list of paths we have blazed
while frontier:
path = frontier.pop(0)
(x, y) = path[-1] # Last state in the first path of the frontier
for (state, action) in successors(x, y, X, Y).items():
if state not in explored:
explored.add(state)
path2 = path + [action, state]
if goal in state:
return path2
else:
frontier.append(path2)
return Fail
Fail = []
def successors(x, y, X, Y):
"""Return a dict of {state: action} pairs describing what can be reached from the (x, y) state, and how."""
assert x <= X and y <= Y ## (x, y) is glass levels; X and Y are glass sizes
return {((0, y+x) if x+y<=Y else (x-(Y-y), y+(Y-y))): "X->Y",
((x+y, 0) if x+y<=X else (x+(X-x), y-(X-x))): "X<-Y",
(X, y): "fill X", (x, Y): "fill Y",
(0, y): "empty X", (x, 0): "empty Y"}
print successors(0,0,4,9)
print pour_solution(4,9,6)
In [36]:
import doctest
from pprint import pprint as _
class Test: """
>>> _(successors(0, 0, 4, 9))
{(0, 0): 'empty Y', (0, 9): 'fill Y', (4, 0): 'fill X'}
>>> _(successors(3, 5, 4, 9))
{(0, 5): 'empty X',
(0, 8): 'X->Y',
(3, 0): 'empty Y',
(3, 9): 'fill Y',
(4, 4): 'X<-Y',
(4, 5): 'fill X'}
>>> _(successors(3, 7, 4, 9))
{(0, 7): 'empty X',
(1, 9): 'X->Y',
(3, 0): 'empty Y',
(3, 9): 'fill Y',
(4, 6): 'X<-Y',
(4, 7): 'fill X'}
>>> pour_solution(4, 9, 6)
[(0, 0), 'fill Y', (0, 9), 'X<-Y', (4, 5), 'empty X', (0, 5), 'X<-Y', (4, 1), 'empty X', (0, 1), \
'X<-Y', (1, 0), 'fill Y', (1, 9), 'X<-Y', (4, 6)]
"""
print doctest.testmod()
In [1]:
def bsuccessors(state):
"""Return a dict of {state:action} pairs. A state is a (here, there, t) tuple,
where here and there are frozensets of people (indicated by their times) and/or
the light, and t is a number indicating the elapsed time."""
here, there, t = state
if 'light' in here:
return dict(((here - frozenset([a,b, 'light']),
there | frozenset([a, b, 'light']),
t + max(a, b)),
(a, b, '->'))
for a in here if a is not 'light'
for b in here if b is not 'light')
else:
return dict(((here | frozenset([a,b, 'light']),
there - frozenset([a, b, 'light']),
t + max(a, b)),
(a, b, '<-'))
for a in there if a is not 'light'
for b in there if b is not 'light')
def elapsed_time(path):
return path[-1][2]
def bridge_problem(here):
"""Modify this to test for goal later: after pulling a state off frontier,
not when we are about to put it on the frontier."""
## modify code below
here = frozenset(here) | frozenset(['light'])
explored = set() # set of states we have visited
# State will be a (people-here, people-there, time-elapsed)
frontier = [ [(here, frozenset(), 0)] ] # ordered list of paths we have blazed
if not here:
return frontier[0]
while frontier:
path = frontier.pop(0)
here1, there1, t1 = state1 = path[-1]
if not here1 or here1 == set(['light']): # Check for solution when we pull the best path
return path
for (state, action) in bsuccessors(state1).items():
if state not in explored:
here, there, t = state
explored.add(state)
path2 = path + [action, state]
# Don't check for solution when we extend a path
frontier.append(path2)
frontier.sort(key=elapsed_time)
return []
def test():
assert bridge_problem(frozenset((1, 2),))[-1][-1] == 2 # the [-1][-1] grabs the total elapsed time
assert bridge_problem(frozenset((1, 2, 5, 10),))[-1][-1] == 17
return 'tests pass'
print test()
In [29]:
def bsuccessors2(state):
"""Return a dict of {state:action} pairs. A state is a
(here, there) tuple, where here and there are frozensets
of people (indicated by their travel times) and/or the light."""
here, there = state
if 'light' in here:
return dict(((here - frozenset([a,b, 'light']),
there | frozenset([a, b, 'light'])),
(a, b, '->'))
for a in here if a is not 'light'
for b in here if b is not 'light')
else:
return dict(((here | frozenset([a,b, 'light']),
there - frozenset([a, b, 'light'])),
(a, b, '<-'))
for a in there if a is not 'light'
for b in there if b is not 'light')
def path_cost(path):
"""The total cost of a path (which is stored in a tuple
with the final action."""
# path = (state, (action, total_cost), state, ... )
if len(path) < 3:
return 0
else:
action, total_cost = path[-2]
return total_cost
def bcost(action):
"""Returns the cost (a number) of an action in the
bridge problem."""
# An action is an (a, b, arrow) tuple; a and b are
# times; arrow is a string.
a, b, arrow = action
return max(a, b)
def elapsed_time(path):
return path[-1][2]
def final_state(path):
return path[-1]
def add_to_frontier(frontier, path):
"""Add path to frontier, replacing costlier path if there is one."""
old = None
for i, p in enumerate(frontier):
if final_state(p) == final_state(path):
old = i
break
if old is not None and path_cost(frontier[i]) < path_cost(path):
return # Old one is better
elif old is not None:
del frontier[old] # Old one is worse
frontier.append(path)
frontier.sort(key=path_cost)
def bridge_problem2(here):
"""Another approach to solve bridge problem. The main difference would be restructure a new way to
describe state"""
here = frozenset(here) | frozenset(['light'])
# State will be a (people-here, people-there)
frontier = [ [(here, frozenset())] ] # ordered list of paths we have blazed
if not here:
return frontier[0]
while frontier:
path = frontier.pop(0)
here1, _ = state1 = final_state(path)
if not here1 or here1 == set(['light']): # Check for solution when we pull the best path
return path
pcost = path_cost(path)
for (state, action) in bsuccessors2(state1).items():
total_cost = bcost(action) + pcost
path2 = path + [(action, total_cost), state]
add_to_frontier(frontier, path2)
return []
def test():
assert path_cost(bridge_problem2(frozenset((1, 2),))) == 2 # the [-1][-1] grabs the total elapsed time
assert path_cost(bridge_problem2(frozenset((1, 2, 5, 10),))) == 17
return 'tests pass'
print test()
In [35]:
# A state is a tuple with six entries: (M1, C1, B1, M2, C2, B2), where
# M1 means 'number of missionaries on the left side.'
#
# An action is one of the following ten strings:
#
# 'MM->', 'MC->', 'CC->', 'M->', 'C->', '<-MM', '<-MC', '<-M', '<-C', '<-CC'
# where 'MM->' means two missionaries travel to the right side.
#
# We should generate successor states that include more cannibals than
# missionaries, but such a state should generate no successors.
def csuccessors(state):
"""Find successors (including those that result in dining) to this
state. But a state where the cannibals can dine has no successors."""
M1, C1, B1, M2, C2, B2 = state
ans = {}
if C1 <= M1 and C2 <= M2:
if B1:
arrow, B1, B2 = '->', 0, 1
return dict(((M1-m, C1-c, B1, M2+m, C2+c, B2),
'M'*m + 'C'*c + arrow)
for m in range(3)
for c in range(3-m)
if m+c > 0 and M1-m >= 0 and C1-c >= 0 and (M1-m >= C1-c or M1-m == 0))
else:
arrow, B1, B2 = '<-', 1, 0
return dict(((M1+m, C1+c, B1, M2-m, C2-c, B2),
arrow + 'M'*m + 'C'*c)
for m in range(3)
for c in range(3-m)
if m+c > 0 and M2-m >= 0 and C2-c >= 0 and (M2-m >= C2-c or M2-m == 0))
else:
return {}
deltas = {(2, 0, 1, -2, 0, -1): 'MM',
(0, 2, 1, 0, -2, -1): 'CC',
(1, 1, 1, -1, -1, -1): 'MC',
(1, 0, 1, -1, 0, -1): 'M',
(0, 1, 1, 0, -1, -1): 'C'}
def sub(state, delta):
return tuple(x-y for x, y in zip(state, delta))
def add(state, delta):
return tuple(x+y for x, y in zip(state, delta))
def test():
assert csuccessors((2, 2, 1, 0, 0, 0)) == {(2, 1, 0, 0, 1, 1): 'C->',
(0, 2, 0, 2, 0, 1): 'MM->',
(2, 0, 0, 0, 2, 1): 'CC->',
(1, 1, 0, 1, 1, 1): 'MC->'}
assert csuccessors((1, 1, 0, 4, 3, 1)) == {(2, 1, 1, 3, 3, 0): '<-M',
(1, 2, 1, 4, 2, 0): '<-C',
(1, 3, 1, 4, 1, 0): '<-CC',
(2, 2, 1, 3, 2, 0): '<-MC'}
assert csuccessors((1, 4, 1, 2, 2, 0)) == {}
return 'tests pass'
print test()
In [36]:
def mc_problem(start=(1,0,1,0,0,0), goal=None):
"""Solve the missionaires and cannibals problem.
State is 6 ints: (M1, C1, B1, M2, C2, B2) on the start (1) and the other (2) sides.
Find a path that goes from initial state to the goal state(which, if not specified,
is the state with no people or boats on the start side.)"""
if goal is None:
goal = (0, 0, 0) + start[:3]
if start == goal:
return [start]
explored = set()
frontier = [[start]]
while frontier:
path = frontier.pop(0)
state = path[-1]
for s, a in csuccessors(state).items():
if s not in explored:
explored.add(s)
path2 = path + [a, s]
if s == goal:
return path2
else:
frontier.append(path2)
return []
print mc_problem()
In [ ]:
# A state is a (here, there, light) tuple. Here and there are
# frozensets of people (each person is represented by an integer
# which corresponds to their travel time), and light is 0 if
# it is on the `here` side and 1 if it is on the `there` side.
#
# An action is a tuple of (travelers, arrow), where the arrow is
# '->' or '<-'. See the test() function below for some examples
# of what your function's input and output should look like.
def bsuccessors3(state):
"""Return a dict of {state:action} pairs. State is (here, there, light)
where here and there are frozen sets of people, light is 0 if the light is
on the here side and 1 if it is on the there side.
Action is a tuple (travelers, arrow) where arrow is '->' or '<-'"""
here, there, light = state
if light == 0:
return dict(((here - frozenset([a,b]),
there | frozenset([a, b]),
1),
(set([a, b]), '->'))
for a in here
for b in here)
else:
return dict(((here | frozenset([a,b]),
there - frozenset([a, b]),
0),
(set([a, b]), '<-'))
for a in there
for b in there)
def test():
assert bsuccessors3((frozenset([1]), frozenset([]), 0)) == {
(frozenset([]), frozenset([1]), 1) : (set([1]), '->')}
assert bsuccessors3((frozenset([1, 2]), frozenset([]), 0)) == {
(frozenset([1]), frozenset([2]), 1) : (set([2]), '->'),
(frozenset([]), frozenset([1, 2]), 1) : (set([1, 2]), '->'),
(frozenset([2]), frozenset([1]), 1) : (set([1]), '->')}
assert bsuccessors3((frozenset([2, 4]), frozenset([3, 5]), 1)) == {
(frozenset([2, 4, 5]), frozenset([3]), 0) : (set([5]), '<-'),
(frozenset([2, 3, 4, 5]), frozenset([]), 0) : (set([3, 5]), '<-'),
(frozenset([2, 3, 4]), frozenset([5]), 0) : (set([3]), '<-')}
return 'tests pass'
print test()
In [ ]:
# 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.
import itertools as it
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."""
L = len(capacities)
if start is None:
start = (0,) * L
def is_goal(state):
return goal in state
def update(state, action, indices):
if action == 'fill':
i = indices[0]
return [state[:i] + (capacities[i],) + state[i+1:]]
elif action == 'empty':
i = indices[0]
return [state[:i] + (0,) + state[i+1:]]
else:
i, j = indices
si, sj = state[i], state[j]
ci, cj = capacities[i], capacities[j]
ans = []
if si + sj > cj:
ans.append(state[:i] + (si-(cj-sj),) + state[i+1:j] + (cj,) + state[j+1:])
else:
ans.append(state[:i] + (0,) + state[i+1:j] + (si+sj,) + state[j+1:])
if si + sj > ci:
ans.append(state[:i] + (ci,) + state[i+1:j] + (sj-(ci-si),) + state[j+1:])
else:
ans.append(state[:i] + (si+sj,) + state[i+1:j] + (0,) + state[j+1:])
return ans
def psuccessors(state):
pairs = [(newState, ('fill', i))
for i in xrange(L)
for newState in update(state, 'fill', [i])]
pairs += [(newState, ('empty', i))
for i in xrange(L)
for newState in update(state, 'empty', [i])]
pairs += [(newState, ('pour', j, i))
for i, j in it.combinations(xrange(L), 2)
for newState in update(state, 'pour', [i, j])]
return dict(pairs)
return shortest_path_search(start, psuccessors, is_goal)
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):
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()
In [34]:
# For example, when calling subway(boston), one of the entries in the
# resulting dictionary should be 'foresthills': {'backbay': 'orange'}.
# This means that foresthills only has one neighbor ('backbay') and
# that neighbor is on the orange line. Other stations have more neighbors:
# 'state', for example, has 4 neighbors.
#
# Once you've defined your subway function, you can define a ride and
# longest_ride function. ride(here, there, system) takes as input
# a starting station (here), a destination station (there), and a subway
# system and returns the shortest path.
#
# longest_ride(system) returns the longest possible ride in a given
# subway system.
def subway(**lines):
"""Define a subway map. Input is subway(linename='station1 station2...'...).
Convert that and return a dict of the form: {station:{neighbor:line,...},...}"""
system = {}
for linename, stations in lines.items():
stations = stations.split(' ')
L = len(stations)
for sa, sb in zip(stations[:-1], stations[1:]):
if sa not in system:
system[sa] = {}
system[sa][sb] = linename
if sb not in system:
system[sb] = {}
system[sb][sa] = linename
return system
boston = subway(
blue='bowdoin government state aquarium maverick airport suffolk revere wonderland',
orange='oakgrove sullivan haymarket state downtown chinatown tufts backbay foresthills',
green='lechmere science north haymarket government park copley kenmore newton riverside',
red='alewife davis porter harvard central mit charles park downtown south umass mattapan')
def ride(here, there, system=boston):
"Return a path on the subway system from here to there."
def is_goal(station):
return there == station
def successors(station):
return dict((nextStation, line)
for nextStation, line in system[station].items())
return shortest_path_search(here, successors, is_goal)
def longest_ride(system):
""""Return the longest possible 'shortest path'
ride between any two stops in the system."""
stations = [station for station in system]
rides = [ride(here, there, system=system)
for here in stations
for there in stations
if here != there]
return max(rides, key=len)
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() # set of states we have visited
frontier = [ [start] ] # ordered list of paths we have blazed
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):
return path2
else:
frontier.append(path2)
return []
def path_states(path):
"Return a list of states in this path."
return path[0::2]
def path_actions(path):
"Return a list of actions in this path."
return path[1::2]
def test_ride():
assert ride('mit', 'government') == [
'mit', 'red', 'charles', 'red', 'park', 'green', 'government']
assert ride('mattapan', 'foresthills') == [
'mattapan', 'red', 'umass', 'red', 'south', 'red', 'downtown',
'orange', 'chinatown', 'orange', 'tufts', 'orange', 'backbay', 'orange', 'foresthills']
assert ride('newton', 'alewife') == [
'newton', 'green', 'kenmore', 'green', 'copley', 'green', 'park', 'red', 'charles', 'red',
'mit', 'red', 'central', 'red', 'harvard', 'red', 'porter', 'red', 'davis', 'red', 'alewife']
assert (path_states(longest_ride(boston)) == [
'wonderland', 'revere', 'suffolk', 'airport', 'maverick', 'aquarium', 'state', 'downtown', 'park',
'charles', 'mit', 'central', 'harvard', 'porter', 'davis', 'alewife'] or
path_states(longest_ride(boston)) == [
'alewife', 'davis', 'porter', 'harvard', 'central', 'mit', 'charles',
'park', 'downtown', 'state', 'aquarium', 'maverick', 'airport', 'suffolk', 'revere', 'wonderland'])
assert len(path_states(longest_ride(boston))) == 16
return 'test_ride passes'
print test_ride()