def betterEvaluationFunction(currentGameState):
  """
    Your extreme ghost-hunting, pellet-nabbing, food-gobbling, unstoppable
    evaluation function (question 5).
  """

  pacPos = currentGameState.getPacmanPosition()
  numCapsules = len(currentGameState.getCapsules())

  # Determine distance to nearest Ghost, don't care if farther than 7
  gDistance = 7
  for pos in currentGameState.getGhostPositions():
    problem = searchAgents.PositionSearchProblem(currentGameState, goal=pos, start=pacPos)
    gDistance = min(gDistance, len(search.breadthFirstSearch(problem)))

  # Determine distance to nearest food
  fDistance = 0
  
  foodGrid = currentGameState.getFood()
  foodList = foodGrid.asList()
  numFood = len(foodList)
  if len(foodList) > 0:
    fProblem = searchAgents.PositionSearchProblem(currentGameState, goal=foodList[0], start=pacPos)
    fDistance = len(search.breadthFirstSearch(problem))

  # Make shorter ghost distance attractive when ghosts are scared
  newGhostStates = currentGameState.getGhostStates()
  newScaredTime = 0
  newScaredTime = reduce(lambda x, y: x.scaredTimer + y.scaredTimer, newGhostStates)
  if newScaredTime > 6:
    gDistance = -gDistance

  px, py = pacPos
  fDensity = 0

  def minus1(l):
    l[:] = [x - 1 for x in l]
    return l

  width = len(foodGrid[:][0])
  height = len(foodGrid[0])

  # Compute density of food surrounding Pacman
  for i in minus1(range(5)):
    intx = px + i
    if intx < 0 or intx > width-1:
      continue

    for j in minus1(range(5)):
      inty = py + j
      if inty < 0 or inty > height-1:
        continue
      if foodGrid[intx][inty]:
        fDensity += 1

  # Return linear combination of factors
  return 3 * gDistance - 13*numCapsules + 1.0/(fDistance+1) + 1*fDensity - 2*numFood

 def findPathToClosestDot(self, gameState):
     "Returns a path (a list of actions) to the closest dot, starting from gameState"
     # Here are some useful elements of the startState
     startPosition = gameState.getPacmanPosition()
     food = gameState.getFood()
     walls = gameState.getWalls()
     problem = AnyFoodSearchProblem(gameState)
     totDist = 99999
     closestPellet = 1
     foodList = food.asList()
     for foodPellet in foodList:
         
         dist = self.distance(startPosition, foodPellet)
         
         if dist < totDist:
             print dist
             print totDist
             closestPellet = foodPellet
             totDist = dist
     
     
     problem.goal = closestPellet
     
     actions  = search.breadthFirstSearch(problem)
     
     return actions
     
     "*** YOUR CODE HERE ***"
     util.raiseNotDefined()

 def getPathToApproachPoint(self, gameState, myState):
   """
   A path takes the form [(whereYouAre, whatYouDo), ...]
   """
   problem = OtherSideProblem(gameState, myState.getPosition(), self.west)
   states, actions, cost = search.breadthFirstSearch(problem)
   return zip(states, actions)  

 def getAction(self, state):
     """
     From game.py:
     The Agent will receive a GameState and must return an action from
     Directions.{North, South, East, West, Stop}
     """
     if not self.food or len(self.food) < 3:
         self.getNewFood(state)
     if not self.actions:
         problem = AnyFoodSearchProblem(state, self.food.pop(0))
         result = search.breadthFirstSearch(problem)
         if not result:
             self.getNewFood(state)
             problem = AnyFoodSearchProblem(state, self.food.pop(0))
         self.actions = search.breadthFirstSearch(problem)
     return self.actions.pop(0)

 def getPathToNearestDot(self, gameState, myState):
   """
   A path takes the form [(whereYouAre, whatYouDo), ...]
   """
   food = self.getFood(gameState)
   problem = AnyDotWithGameStates( gameState, food, self.index)
   states, actions, cost = search.breadthFirstSearch(problem)
   return zip(states, actions)

    def findPathToClosestDot(self, gameState):
        "Returns a path (a list of actions) to the closest dot, starting from gameState"
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        return search.breadthFirstSearch(problem)

def closestFoodDistance(gameState):
    """
    Returns the the distance to the closest food
    """
    from search import breadthFirstSearch
    startPosition = gameState.getPacmanPosition()
    food = gameState.getFood()
    walls = gameState.getWalls()
    problem = AnyFoodSearchProblem(gameState)
    path = breadthFirstSearch(problem)
    return len(path)

    def findPathToClosestDot(self, gameState):
        "Returns a path (a list of actions) to the closest dot, starting from gameState"
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        # use bfs. bfs will give you the shortest path, it spits out the solution, which is the path.
        # It is done. We return the path [a list of action]
        return search.breadthFirstSearch(problem)

 def findPathToClosestDot(self, gameState):
     "Returns a path (a list of actions) to the closest dot, starting from gameState"
     # Here are some useful elements of the startState
     from search import breadthFirstSearch
     startPosition = gameState.getPacmanPosition()
     food = gameState.getFood()
     walls = gameState.getWalls()
     problem = AnyFoodSearchProblem(gameState)
     path = breadthFirstSearch(problem)       
     return path
     "*** YOUR CODE HERE ***"
     util.raiseNotDefined()

    def findPathToClosestDot(self, gameState):
        "Returns a path (a list of actions) to the closest dot, starting from gameState"
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        #find the closest food to me and move towards it
        actions = search.breadthFirstSearch(problem)
        return actions
        util.raiseNotDefined()

  def findPathToClosestDot(self, gameState):
    "Returns a path (a list of actions) to the closest dot, starting from gameState"
    # Here are some useful elements of the startState
    startPosition = gameState.getPacmanPosition()
    #print 'startPosition: ' + str(startPosition) #DEBUG
    food = gameState.getFood()
    walls = gameState.getWalls()
    problem = AnyFoodSearchProblem(gameState)

    "*** YOUR CODE HERE ***"
    actions = search.breadthFirstSearch(problem)
    #print 'actions: ' + str(actions) #DEBUG
    return actions

 def findPathToClosestDot(self, gameState):
     """
     Returns a path (a list of actions) to the closest dot, starting from
     gameState.f
     """
     # Here are some useful elements of the startState
     startPosition = gameState.getPacmanPosition()
     food = gameState.getFood()
     walls = gameState.getWalls()
     problem = AnyFoodSearchProblem(gameState)
     "*** YOUR CODE HERE ***"
     #Camino que sera aprovechado para alcanzar todos los goals
     #dijkstra y brfs funcionan
     return search.breadthFirstSearch(problem)

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        foodGrid = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        #We don't have to do much here once AnyFoodSearch is implemented.  We just basically pass the problem on to
        #a search function.  I chose BFS because it's more efficient than DFS and does not require a heuristic.
        return search.breadthFirstSearch(problem)

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        "initialize some variables"
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "use breadthFirstSearch one AnyFoodSearchProblem to make it find the closest food dot"
        actionlist = search.breadthFirstSearch(problem)
        return actionlist

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        # using bfs to find the actions to be taken to solve the problem
        return search.breadthFirstSearch(problem)
        util.raiseNotDefined()

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        closest = None
        for pellet in food.asList():
            if closest == None:
                closest = pellet
                continue
            distance1 = abs(closest[0]-startPosition[0]) + abs(closest[1]-startPosition[1])
            distance2 = abs(pellet[0]-startPosition[0]) + abs(pellet[0]-startPosition[0])
            if distance1 < distance2:
                closest = pellet

        self.searchType = AnyFoodSearchProblem
        self.searchFunction = lambda prob: search.breadthFirstSearch(problem)
        return search.breadthFirstSearch(problem)

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        # do BFS with AnyFoodSearchProlem (which has as goal state 'any food')
        # since BFS searches breadth first, you will always get the closest food
        from search import breadthFirstSearch
        return breadthFirstSearch(problem)

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"

        """ Using BFS defined in search.py to find the goal""" 
        from search import breadthFirstSearch
        return breadthFirstSearch(problem)

 def evalFn(self, successor, action):
   if self.getFood(successor).count() == 0: return 1000
   myState = successor.getAgentState(self.index)
   pos = myState.getPosition() 
   if pos != nearestPoint(pos): return self.evalFn(successor.generateSuccessor(self.index, action), action)
   
   food = self.getFood(successor)
   problem = AnyDotOnSideWillDo(nearestPoint(pos), food, successor.getWalls())
   distanceToFood = search.breadthFirstSearch(problem)[2]
   
   distanceToOpponent = 100
   for enemyIndex in self.getOpponents(successor):
     opp = successor.getAgentState(enemyIndex)
     if not opp.isPacman:
       distanceToOpponent = min(distanceToOpponent, manhattanDistance(myState.getPosition(), opp.getPosition()))
     
   return -0.3 * distanceToFood + self.getScore(successor) + 2 * math.log(distanceToOpponent)

def primsMinSpanningTreeHeuristic(state, gameState, edges):
    vNew = []
    totalDist = 0
    
    currentFoodGrid = state[1]
    vertices = foodGridToFoodList(currentFoodGrid)
           
    if (len(vertices) == 0):
        return 0
    
    start = state[0] #Pacman's position
    
    delStart = False
    if (start not in edges.keys()): #This is only to keep the edge hash from becoming really big.
        delStart = True
        edges[start] = {}
        for pellet in vertices:
          problem = CustomPositionSearchProblem(gameState, lambda x: 1, pellet, start)
          actions = search.breadthFirstSearch(problem)
          distance = len(actions) #we can do this because the cost function is 1
          edges[start][pellet] = distance 
          #DO WE NEED TO ADD THE START AS A DESTINATION TO ALL THE OTHER PELLETS TOO? I DONT THINK SO...
    
    vNew.append(start)
    
    nearestV = None
    nearestD = 999999
    while len(vertices) > 0:
        nearestV = None
        nearestD = 999999 
        for sVertex in vNew:
            for eVertex in vertices:
                if (edges[sVertex][eVertex] < nearestD):
                    nearestD = edges[sVertex][eVertex]
                    nearestV = eVertex
        assert nearestV != None
        vNew.append(eVertex)
        vertices.remove(eVertex)
        totalDist += nearestD
        
    if (delStart):
        del edges[start]
    
    #print "h = ",totalDist,", ",foodCount," food, ", len(edges.keys()), "nodes in edge hash: ", edges.keys()
    #print "Prim distance=", totalDist, ", pellet count=", len(vertices), " and pacman position=", start    
    return totalDist