python A* implementation

A* implementation

from Queue import PriorityQueue
"""
matrix=[['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], 
        ['@', '.', '#', '.', '.', '.', '.', '.', '.', '#'], 
        ['#', '.', '.', '.', '#', '#', '.', '.', '.', '#'], 
        ['#', '.', '.', '.', '#', '#', '.', '#', '.', '#'], 
        ['#', '#', '.', '.', '#', '#', '.', '.', '.', '#'], 
        ['#', '#', '#', '.', '#', '#', '.', '#', '#', '#'], 
        ['#', '.', '.', '.', '.', '.', '.', '.', '.', '#'], 
        ['#', '.', '.', '.', '.', '#', '#', '#', '.', '#'], 
        ['#', '.', '.', '.', '.', '.', '.', '.', '.', 'C'], 
        ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]
"""
def get_route(matrix):
  """
  Return list of moves to get to the customer. The moves can be either
  l - for left
  d - for down
  r - for right
  u - for up

  The matrix is two dimension list of chars that represents the city.
  It can have following items:
  @ - courier starting location
  # - blocked
  . - empty
  C - customer location
  """
  start = decart_location('@', matrix)
  goal = decart_location('C', matrix)
  queue = PriorityQueue()
  # any point coordinate structure:
  # ((x,y), action, cost, plan) -- see A* implementation
  # NOTE : lowest cost gives highest priority
  curr = (start, None, 0, [])
  queue.put(curr, 0)
  expanded = []
  found = None
  while not queue.empty():
    curr = queue.get()
    print "processing curr : ", curr
    (point, action, cost, plan) = curr
    if point == goal:
      print "reached goal"
      found = curr
      break
  
    if point in expanded:
      continue
      
    expanded.append(point)
    
    for node in getSucessors(goal, point, matrix):
      (p, a, c) = node
      if not p in expanded:
        cloned_plan = plan[:]
        cloned_plan.append(a)
        queue.put((p, a, c, cloned_plan),c)
  
  (p, a, c, plan) = found
  print "Found path %s" % (plan)
  transl_opt = {
    'left': 'l',
    'right': 'r',
    'up': 'u',
    'down':'d'
  }
  return [transl_opt[x] for x in plan]

def decart_location(sym, matrix):
  for y, row in enumerate(matrix):
    if sym in row:
      return (row.index(sym), y)

def getSucessors(goal, point, matrix):
  raw_list = [
    actionToPoint(point, 'left', matrix, goal),
    actionToPoint(point, 'down', matrix, goal),
    actionToPoint(point, 'right', matrix, goal),
    actionToPoint(point, 'up', matrix, goal)
  ]
  return [x for x in raw_list if x]

def actionToPoint(curposition, action, matrix, goal):
  (x, y) = curposition
  if (action == 'up'):
    y -= 1
  elif (action == 'down'):
    y += 1
  elif (action == 'right'):
    x += 1
  elif (action == 'left'):
    x -= 1
  if isObstacle((x,y), matrix):
    return None
  return ((x, y), action, getPathCost(goal, (x,y)))

def getPathCost((goal_x, goal_y), (p_x, p_y)):
  # Manhattan distance
  return abs(p_x - goal_x) + abs(p_y - goal_y)

def isObstacle(point, matrix):
  (x, y) = point
  try:
    if matrix[y][x] in ['C', '.']:
      return False
  except:
      pass
  return True

submitted for a job application on 19 Jan 2017 . Nothing special but self-made 👍