Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 8141379de2
Fetching contributors…

Cannot retrieve contributors at this time

85 lines (70 sloc) 2.137 kb
__author__ = 'Theo'
# ----------
# User Instructions:
#
# Define a function, search() that takes no input
# and returns a list
# in the form of [optimal path length, x, y]. For
# the grid shown below, your function should output
# [11, 4, 5].
#
# If there is no valid path from the start point
# to the goal, your function should return the string
# 'fail'
# ----------
# Grid format:
# 0 = Navigable space
# 1 = Occupied space
grid = [[0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 0]]
init = [0, 0]
goal = [len(grid) - 1, len(grid[0]) - 1] # Make sure that the goal definition stays in the function.
delta = [[-1, 0], # go up
[0, -1], # go left
[1, 0], # go down
[0, 1]] # go right
delta_name = ['^', '<', 'v', '>']
cost = 1
def search():
current = init
length = 0
open = []
visited = []
initVal = [length, init[0], init[1]]
open.append(initVal)
nextValue = initVal
while current != goal:
visited.append([current[0], current[1]])
# print 'visited ', visited
next = successors(current, visited)
open.remove(nextValue)
for node in next:
if (not isAlreadyOpen(open, node)):
open.append([nextValue[0] + cost, node[0], node[1]])
if not open:
return 'fail'
# print 'open', open
nextValue = min(open)
current = [nextValue[1], nextValue[2]]
# print 'current', current
return nextValue
def successors(current, visited):
result = []
for mov in delta:
newX = current[0] + mov[0]
newY = current[1] + mov[1]
if (isRightPoint(newX, newY, visited)):
result.append([newX, newY])
return result
def isRightPoint(x, y, visited):
return (x >= 0) and (x < len(grid)) and (y >= 0) and (y < len(grid[0])) and (grid[x][y] == 0)\
and ([x, y] not in visited)
def isAlreadyOpen(open, current):
for node in open:
if (node[1] == current[0]) and (node[2] == current[1]):
return True
return False
print search()
Jump to Line
Something went wrong with that request. Please try again.