cs212 ยป

Unit 4 Code

Contents

bridge.py

A description of the bridge and torch problem can be found here.

import doctest

def bridge_problem2(here):
    "Find the fastest (least path cost) path to the goal in the bridge problem."
    here = frozenset(here) | frozenset(['light'])
    explored = set() # set of states we have visited
    # State will be a (people_here, people_there)
    # E.g. ({1, 2, 5, 10, 'light'}, {})
    frontier = [ [(here, frozenset())] ] # ordered list of paths we have blazed
    while frontier:
        path = frontier.pop(0)
        here1, there1 = state1 = final_state(path)
        if not here1 or (len(here1) == 1 and 'light' in here1):
            return path
        explored.add(state1)
        pcost = path_cost(path)
        for (state, action) in bsuccessors2(state1).items():
            if state not in explored:
                total_cost = pcost + bcost(action)
                path2 = path + [(action, total_cost), state]
                add_to_frontier(frontier, path2)
    return []

bridge_problem = bridge_problem2

def final_state(path):
    return path[-1]

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) < 2:
        return 0
    else:
        return path[-2][-1]

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 add_to_frontier(frontier, path):
    "Add path to frontier, replacing costlier path if there is one."
    # (This could be done more efficiently)
    # Find if there is an old path to the final state of this path.
    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[old]) < path_cost(path):
        return # Old path was better; do nothing
    elif old is not None:
        del frontier[old] # Old path was worse; delete it
    ## Now add the new path and re-sort
    frontier.append(path)
    frontier.sort(key = path_cost)

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 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_states(path):
    "Return a list of states in this path."
    return path[::2]

def path_actions(path):
    "Return a list of actions in this path."
    return path[1::2]

def test():
    here1 = frozenset([1, 'light'])
    there1 = frozenset([])

    here2 = frozenset([1, 2, 'light'])
    there2 = frozenset([3])

    assert bsuccessors2((here1, there1)) == {
            (frozenset([]), frozenset([1, 'light'])): (1, 1, '->')}
    assert bsuccessors2((here2, there2)) == {
            (frozenset([1]), frozenset(['light', 2, 3])): (2, 2, '->'),
            (frozenset([2]), frozenset([1, 3, 'light'])): (1, 1, '->'),
            (frozenset([]), frozenset([1, 2, 3, 'light'])): (2, 1, '->')}

    assert bsuccessors2((frozenset([1, 'light']), frozenset([]))) == {
        (frozenset([]), frozenset([1, 'light'])): (1, 1, '->')}

    assert bsuccessors2((frozenset([]), frozenset([2, 'light']))) == {
                (frozenset([2, 'light']), frozenset([])): (2, 2, '<-')}
    assert bsuccessors2((frozenset([1, 2, 5, 10, 'light']), frozenset([]))) == {
                (frozenset([1, 10]), frozenset(['light', 2, 5])): (5, 2, '->'),
                (frozenset([10, 5]), frozenset([1, 2, 'light'])): (2, 1, '->'),
                (frozenset([1, 2, 10]), frozenset(['light', 5])): (5, 5, '->'),
                (frozenset([1, 2]), frozenset(['light', 10, 5])): (5, 10, '->'),
                (frozenset([1, 10, 5]), frozenset(['light', 2])): (2, 2, '->'),
                (frozenset([2, 5]), frozenset([1, 10, 'light'])): (10, 1, '->'),
                (frozenset([1, 2, 5]), frozenset(['light', 10])): (10, 10, '->'),
                (frozenset([1, 5]), frozenset(['light', 2, 10])): (10, 2, '->'),
                (frozenset([2, 10]), frozenset([1, 5, 'light'])): (5, 1, '->'),
                (frozenset([2, 10, 5]), frozenset([1, 'light'])): (1, 1, '->')}

    assert path_cost(('fake_state1', ((2, 5, '->'), 5), 'fake_state2')) == 5
    assert path_cost(('fs1', ((2, 1, '->'), 2), 'fs2', ((3, 4, '<-'), 6), 'fs3')) == 6
    assert bcost((4, 2, '->'), ) == 4
    assert bcost((3, 10, '<-'), ) == 10

    assert path_cost(bridge_problem(frozenset((1, 2), ))) == 2
    assert path_cost(bridge_problem(frozenset((1, 2, 5, 10), ))) == 17

    testpath = [(frozenset([1, 10]), frozenset(['light', 2, 5]), 5), # state 1
                (5, 2, '->'),                                        # action 1
                (frozenset([10, 5]), frozenset([1, 2, 'light']), 2), # state 2
                (2, 1, '->'),                                        # action 2
                (frozenset([1, 2, 10]), frozenset(['light', 5]), 5),
                (5, 5, '->'),
                (frozenset([1, 2]), frozenset(['light', 10, 5]), 10),
                (5, 10, '->'),
                (frozenset([1, 10, 5]), frozenset(['light', 2]), 2),
                (2, 2, '->'),
                (frozenset([2, 5]), frozenset([1, 10, 'light']), 10),
                (10, 1, '->'),
                (frozenset([1, 2, 5]), frozenset(['light', 10]), 10),
                (10, 10, '->'),
                (frozenset([1, 5]), frozenset(['light', 2, 10]), 10),
                (10, 2, '->'),
                (frozenset([2, 10]), frozenset([1, 5, 'light']), 5),
                (5, 1, '->'),
                (frozenset([2, 10, 5]), frozenset([1, 'light']), 1),
                (1, 1, '->')]
    assert path_states(testpath) == [(frozenset([1, 10]), frozenset(['light', 2, 5]), 5), # state 1
                (frozenset([10, 5]), frozenset([1, 2, 'light']), 2), # state 2
                (frozenset([1, 2, 10]), frozenset(['light', 5]), 5),
                (frozenset([1, 2]), frozenset(['light', 10, 5]), 10),
                (frozenset([1, 10, 5]), frozenset(['light', 2]), 2),
                (frozenset([2, 5]), frozenset([1, 10, 'light']), 10),
                (frozenset([1, 2, 5]), frozenset(['light', 10]), 10),
                (frozenset([1, 5]), frozenset(['light', 2, 10]), 10),
                (frozenset([2, 10]), frozenset([1, 5, 'light']), 5),
                (frozenset([2, 10, 5]), frozenset([1, 'light']), 1)]
    assert path_actions(testpath) == [(5, 2, '->'), # action 1
                                      (2, 1, '->'), # action 2
                                      (5, 5, '->'),
                                      (5, 10, '->'),
                                      (2, 2, '->'),
                                      (10, 1, '->'),
                                      (10, 10, '->'),
                                      (10, 2, '->'),
                                      (5, 1, '->'),
                                      (1, 1, '->')]

    return 'tests pass'

class TestBridge: """
>>> path_cost(bridge_problem([1,2,5,10]))
17

## There are two equally good solutions
>>> S1 = [((2, 1, '->'), 2), ((1, 1, '<-'), 3), ((5, 10, '->'), 13), ((2, 2, '<-'), 15), ((2, 1, '->'), 17)]

>>> S2 = [((2, 1, '->'), 2), ((2, 2, '<-'), 4), ((5, 10, '->'), 14), ((1, 1, '<-'), 15), ((2, 1, '->'), 17)]
>>> path_actions(bridge_problem([1,2,5,10])) in (S1, S2)
True

## Try some other problems
>>> path_actions(bridge_problem([1,2,5,10,15,20]))
[((2, 1, '->'), 2), ((1, 1, '<-'), 3), ((5, 10, '->'), 13), ((2, 2, '<-'), 15), ((2, 1, '->'), 17), ((1, 1, '<-'), 18), ((15, 20, '->'), 38), ((2, 2, '<-'), 40), ((2, 1, '->'), 42)]

>>> path_actions(bridge_problem([1,2,4,8,16,32]))
[((2, 1, '->'), 2), ((1, 1, '<-'), 3), ((8, 4, '->'), 11), ((2, 2, '<-'), 13), ((1, 2, '->'), 15), ((1, 1, '<-'), 16), ((16, 32, '->'), 48), ((2, 2, '<-'), 50), ((2, 1, '->'), 52)]

>>> [path_cost(bridge_problem([1,2,4,8,16][:N])) for N in range(6)]
[0, 1, 2, 7, 15, 28]

>>> [path_cost(bridge_problem([1,1,2,3,5,8,13,21][:N])) for N in range(8)]
[0, 1, 1, 2, 6, 12, 19, 30]

# http://en.wikipedia.org/wiki/Bridge_and_torch_problem
>>> path_actions(bridge_problem([1,2,5,8]))
[((2, 1, '->'), 2), ((1, 1, '<-'), 3), ((5, 8, '->'), 11), ((2, 2, '<-'), 13), ((2, 1, '->'), 15)]

>>> path_cost(bridge_problem([1,2,5,8]))
15

>>> path_cost(bridge_problem([5,10,20,25]))
60
"""

print(test())
print(doctest.testmod())

pour.py

import doctest

def pour_problem(X, Y, goal, start = (0, 0)):
    """X and Y are the capacity of glasses; (x,y) is current fill levels and
    represent 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 the 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 y+x <= 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'
            }

class Test:
    """
    >>> successors(0, 0, 4, 9)
    {(0, 9): 'fill Y', (0, 0): 'empty Y', (4, 0): 'fill X'}

    >>> successors(3, 5, 4, 9)
    {(4, 5): 'fill X', (4, 4): 'X<-Y', (3, 0): 'empty Y', (3, 9): 'fill Y', (0, 5): 'empty X', (0, 8): 'X->Y'}

    >>> successors(3, 7, 4, 9)
    {(4, 7): 'fill X', (4, 6): 'X<-Y', (3, 0): 'empty Y', (0, 7): 'empty X', (3, 9): 'fill Y', (1, 9): 'X->Y'}

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

    ## What problem, with X, Y, and goal < 10 has the longest solution?
    ## Answer: pour_problem(7, 9, 8) with 14 steps.

    >>> def num_actions(triplet): X, Y, goal = triplet; return len(pour_problem(X, Y, goal)) / 2

    >>> def hardness(triplet): X, Y, goal = triplet; return num_actions((X, Y, goal)) - max(X, Y)
    >>> max([(X, Y, goal) for X in range(1, 10) for Y in range(1, 10)
    ...                   for goal in range(1, max(X, Y))], key = num_actions)
    (7, 9, 8)

    >>> max([(X, Y, goal) for X in range(1, 10) for Y in range(1, 10)
    ...                   for goal in range(1, max(X, Y))], key = hardness)
    (7, 9, 8)

    >>> pour_problem(7, 9, 8)
    [(0, 0), 'fill Y', (0, 9), 'X<-Y', (7, 2), 'empty X', (0, 2), 'X<-Y', (2, 0), 'fill Y', (2, 9), 'X<-Y', (7, 4), 'empty X', (0, 4), 'X<-Y', (4, 0), 'fill Y', (4, 9), 'X<-Y', (7, 6), 'empty X', (0, 6), 'X<-Y', (6, 0), 'fill Y', (6, 9), 'X<-Y', (7, 8)]
    """

print(doctest.testmod())
# TestResults(failed=0, attempted=9)

Note that doctests compare the computed result and answer as strings, not Python objects. So the order of the items in the dict matter in a doctest whereas the order does not matter in an assert statement

cannibals.py

A description of the Missionaries and Cannibals problem can be found here.

import doctest

def mc_problem(start = (3, 3, 1, 0, 0, 0), goal = None):
    """Solve the missionaries and cannibals problem.  State is 6 ints: (M1, C1,
    B1, M2, C2, B2) on the start (1) and other (2) sides.  Find a path that goes
    from the 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() # 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 csuccessors(s).items():
            if state not in explored:
                explored.add(state)
                path2 = path + [action, state]
                if state == goal:
                    return path2
                else:
                    frontier.append(path2)

def csuccessors(state):
    # Norvig's solution, with a check to make sure no state has negative numbers.
    """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
    ## Check for state with no successors
    if C1 > M1 > 0 or C2 > M2 > 0:
        return {}
    items = []
    if B1 > 0:
        for delta, a in deltas.items():
            x = sub(state, delta)
            if all(val >= 0 for val in x):
                items.append((sub(state, delta), a + '->'))
    if B2 > 0:
        for delta, a in deltas.items():
            x = add(state, delta)
            if all(val >= 0 for val in x):
                items.append((add(state, delta), '<-' + a))
    return dict(items)

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 add(X, Y):
    "add two vectors, X and Y."
    return tuple(x+y for x, y in zip(X, Y))

def sub(X, Y):
    "subtract two vectors, X and Y."
    return tuple(x-y for x, y in zip(X, Y))

def test():
    """
    >>> mc_problem((1, 2, 1, 0, 0, 0))

    """
    assert csuccessors((2, 2, 1, 0, 0, 0)) == {(2, 1, 0, 0, 1, 1): 'C->',
                                               (1, 2, 0, 1, 0, 1): 'M->',
                                               (0, 2, 0, 2, 0, 1): 'MM->',
                                               (1, 1, 0, 1, 1, 1): 'MC->',
                                               (2, 0, 0, 0, 2, 1): 'CC->'}
    assert csuccessors((1, 1, 0, 4, 3, 1)) == {(1, 2, 1, 4, 2, 0): '<-C',
                                               (2, 1, 1, 3, 3, 0): '<-M',
                                               (3, 1, 1, 2, 3, 0): '<-MM',
                                               (1, 3, 1, 4, 1, 0): '<-CC',
                                               (2, 2, 1, 3, 2, 0): '<-MC'}
    assert csuccessors((1, 0, 0, 4, 1, 1)) == {(1, 1, 1, 4, 0, 0): '<-C',
                                               (2, 0, 1, 3, 1, 0): '<-M',
                                               (2, 1, 1, 3, 0, 0): '<-MC',
                                               (3, 0, 1, 2, 1, 0): '<-MM'}
    assert csuccessors((1, 4, 1, 2, 2, 0)) == {}
    assert mc_problem((1, 0, 1, 0, 0, 0)) == [(1, 0, 1, 0, 0, 0), 'M->', (0, 0, 0, 1, 0, 1)]
    assert mc_problem((1, 1, 1, 0, 0, 0)) == [(1, 1, 1, 0, 0, 0), 'MC->', (0, 0, 0, 1, 1, 1)]
    assert mc_problem((2, 1, 1, 0, 0, 0)) == [(2, 1, 1, 0, 0, 0), 'MC->', (1, 0, 0, 1, 1, 1), '<-C', (1, 1, 1, 1, 0, 0), 'MC->', (0, 0, 0, 2, 1, 1)]
    assert mc_problem((1, 2, 1, 0, 0, 0)) == None
    return 'tests pass'

print(doctest.testmod())
print test()

search.py

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 Fail

Fail = []

################################################################################

def lowest_cost_search(start, successors, is_goal, action_cost):
    """Return the lowest cost path, starting from start state,
    and considering successors(state) => {state:action,...},
    that ends in a state for which is_goal(state) is true,
    where the cost of a path is the sum of action costs,
    which are given by action_cost(action)."""
    explored = set() # set of states we have visited
    frontier = [ [start] ] # ordered list of paths we have blazed
    while frontier:
        path = frontier.pop(0)
        state1 = final_state(path)
        if is_goal(state1):
            return path
        explored.add(state1)
        pcost = path_cost(path)
        for (state, action) in successors(state1).items():
            if state not in explored:
                total_cost = pcost + action_cost(action)
                path2 = path + [(action, total_cost), state]
                add_to_frontier(frontier, path2)
    return Fail

def final_state(path): return path[-1]

def path_cost(path):
    "The total cost of a path (which is stored in a tuple with the final action)."
    if len(path) < 3:
        return 0
    else:
        action, total_cost = path[-2]
        return total_cost

def add_to_frontier(frontier, path):
    "Add path to frontier, replacing costlier path if there is one."
    # (This could be done more efficiently.)
    # Find if there is an old path to the final state of this path.
    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[old]) < path_cost(path):
        return # Old path was better; do nothing
    elif old is not None:
        del frontier[old] # Old path was worse; delete it
    ## Now add the new path and re-sort
    frontier.append(path)
    frontier.sort(key = path_cost)

################################################################################
## Example: Solving the bridge problem using lowest_cost_search

def bridge_problem3(here):
    """Find the fastest (least elapsed time) path to
    the goal in the bridge problem."""
    here = frozenset(here) | frozenset(['light'])
    state = (here, frozenset())
    return lowest_cost_search(state, bsuccessors2, is_goal, bcost)    

def is_goal(state):
    here, there = state
    return not here or (len(here) == 1 and 'light' in here)

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

################################################################################
## Example: Solving the cannibal problem using shortest_path_search

def mc_problem2(start = (3, 3, 1, 0, 0, 0), goal = None):
    if goal is None:
        goal = (0, 0, 0) + start[:3]
    def is_goal(state):
        return state == goal
    return shortest_path_search(start, csuccessors, is_goal)

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
    ## Check for state with no successors
    if C1 > M1 > 0 or C2 > M2 > 0:
        return {}
    items = []
    if B1 > 0:
        items += [(sub(state, delta), a + '->')
                  for delta, a in deltas.items()]
    if B2 > 0:
        items += [(add(state, delta), '<-' + a)
                  for delta, a in deltas.items()]
    return dict(items)

def add(X, Y):
    "add two vectors, X and Y."
    return tuple(x+y for x, y in zip(X, Y))

def sub(X, Y):
    "subtract vector Y from X."
    return tuple(x-y for x, y in zip(X, Y))

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'}

################################################################################
## Example: A simple problem solved with shortest_path_search
#
# Let's say the states in an optimization problem are given by integers.
# From a state, i, the only possible successors are i+1 and i-1. Given
# a starting integer, find the shortest path to the integer 8.
#
# This is an overly simple example of when we can use the
# shortest_path_search function. We just need to define the appropriate
# is_goal and successors functions.

def is_goal(state):
    if state == 8:
        return True
    else:
        return False

def successors(state):
    successors = {state + 1: '->',
                  state - 1: '<-'}
    return successors

# shortest_path_search(5, successors, is_goal)

################################################################################
## Tests

def test():
    here = [1, 2, 5, 10]
    assert bridge_problem3(here) == [
            (frozenset([1, 2, 'light', 10, 5]), frozenset([])),
            ((2, 1, '->'), 2),
            (frozenset([10, 5]), frozenset([1, 2, 'light'])),
            ((2, 2, '<-'), 4),
            (frozenset(['light', 10, 2, 5]), frozenset([1])),
            ((5, 10, '->'), 14),
            (frozenset([2]), frozenset([1, 10, 5, 'light'])),
            ((1, 1, '<-'), 15),
            (frozenset([1, 2, 'light']), frozenset([10, 5])),
            ((2, 1, '->'), 17),
            (frozenset([]), frozenset([1, 10, 2, 5, 'light']))]

    assert mc_problem2(start = (1, 1, 1, 0, 0, 0)) == [
                             (1, 1, 1, 0, 0, 0), 'MC->',
                             (0, 0, 0, 1, 1, 1)]
    assert mc_problem2() == [(3, 3, 1, 0, 0, 0), 'CC->',
                             (3, 1, 0, 0, 2, 1), '<-C',
                             (3, 2, 1, 0, 1, 0), 'CC->',
                             (3, 0, 0, 0, 3, 1), '<-C',
                             (3, 1, 1, 0, 2, 0), 'MM->',
                             (1, 1, 0, 2, 2, 1), '<-MC',
                             (2, 2, 1, 1, 1, 0), 'MM->',
                             (0, 2, 0, 3, 1, 1), '<-C',
                             (0, 3, 1, 3, 0, 0), 'CC->',
                             (0, 1, 0, 3, 2, 1), '<-C',
                             (0, 2, 1, 3, 1, 0), 'CC->',
                             (0, 0, 0, 3, 3, 1)]
    assert shortest_path_search(5, successors, is_goal) == [5, '->', 6, '->', 7, '->', 8]

    return 'tests pass'

print test()