Skip to content

Instantly share code, notes, and snippets.

@serser
Created December 5, 2017 08:10
Show Gist options
  • Save serser/e219b071fd1c704bcefb6f792b8afe19 to your computer and use it in GitHub Desktop.
Save serser/e219b071fd1c704bcefb6f792b8afe19 to your computer and use it in GitHub Desktop.
# https://classroom.udacity.com/courses/cs373/lessons/48646841/concepts/487263470923
# ----------
# User Instructions:
#
# Define a function, search() that returns a list
# in the form of [optimal path length, row, col]. 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]
cost = 1
delta = [[-1, 0], # go up
[ 0,-1], # go left
[ 1, 0], # go down
[ 0, 1]] # go right
delta_name = ['^', '<', 'v', '>']
def get_candidates(current, grid, visited, cost):
candidates = []
for d in delta:
x, y= d
g, cx, cy = current
cx += x
cy += y
if 0 <= cx < len(grid) and 0 <= cy < len(grid[0]) and ([cx,cy] not in visited) & (grid[cx][cy]!=1):
candidates.append([g+cost,cx,cy])
return candidates
def search(grid,init,goal,cost):
# ----------------------------------------
# insert code here
# ----------------------------------------
visited = []
visited.append(init)
init_g = [0, init[0],init[1]]
candidates = get_candidates(init_g, grid, visited, cost)
while True:
cand_sorted = sorted(candidates, key=lambda x:x[0], reverse=False)
# always pick the lowest cose
cand_pick = cand_sorted[0]
g, cx,cy = cand_pick
visited.append([cx,cy])
#print 'visited', visited
candidates.remove(cand_pick)
candidates += get_candidates(cand_pick, grid, visited, cost)
if len(candidates) == 0:
return 'fail'
for c in candidates:
g, cx, cy = c
if goal == [cx, cy]:
path = [g, cx, cy]
return path
print search(grid, init, goal, cost)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment