Water Pouring


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)


{(0, 9): 'fill Y', (0, 0): 'empty Y', (4, 0): 'fill X'}
[(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)]

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


TestResults(failed=0, attempted=4)

Bridge Problem


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


tests pass

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


tests pass

Generalization


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


tests pass

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


[(1, 0, 1, 0, 0, 0), 'M->', (0, 0, 0, 1, 0, 1)]

Problem 1


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

Problem 2


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

Problem 3


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


test_ride passes