def terminalTest(self, state):
        """
          state: Search state

        Returns True if and only if the state is a valid goal state.
        """
        util.raiseNotDefined()

def aStarSearch(problem, heuristic=nullHeuristic):
    """Search the node that has the lowest combined cost and heuristic first."""
    "*** YOUR CODE HERE ***"

    heap = util.PriorityQueue()
    start = problem.getStartState()
    heap.push(start, 0)

    came_from = {}
    actions_cost = {}
    came_from[start] = None
    actions_cost[start] = 0
        
    while not heap.isEmpty():
        state = heap.pop()

        if problem.isGoalState(state):
            return recontruct_actions(came_from, start, state)

        for nextState, action, cost in problem.getSuccessors(state):
            newcost = actions_cost[state] + cost
            if nextState not in actions_cost or actions_cost[nextState] > newcost:
                actions_cost[nextState] = newcost
                priority = newcost + heuristic(nextState, problem)
                heap.push(nextState, priority)
                came_from[nextState] = (state, action)

    return []
    util.raiseNotDefined()

 def computeQValueFromValues(self, state, action):
     """
       Compute the Q-value of action in state from the
       value function stored in self.values.
     """
     "*** YOUR CODE HERE ***"
     util.raiseNotDefined()

 def getBeliefDistribution(self):
   """
   Return the agent's current belief state, a distribution over
   ghost locations conditioned on all evidence and time passage.
   """
   "*** YOUR CODE HERE ***"
   util.raiseNotDefined()

 def getFeatures(self, state, action):    
   """
     Returns a dict from features to counts
     Usually, the count will just be 1.0 for
     indicator functions.  
   """
   util.raiseNotDefined()

def aStarSearch(problem, heuristic=nullHeuristic):

    from util import PriorityQueue
    from game import Directions
    
    actions = []
    
    frontier = PriorityQueue()
    frontier.push((problem.getStartState(), [], 0), 0)
    visited = []

    while (frontier.isEmpty() == False):
        (currentS, currentP, currentC) = frontier.pop()
        if (problem.isGoalState(currentS) == True):
            actions = currentP
            break
        if (visited.count(currentS) == 0):
            visited.append(currentS)
            successors = problem.getSuccessors(currentS)
            for i in range(0,len(successors)):
                (neighbor, direction, cost) = successors[i]
                if (visited.count(neighbor) == 0):
                    frontier.push((neighbor, (currentP +[direction]), (currentC + cost)), (currentC + cost + heuristic(neighbor, problem)))
                
    return actions


    
    util.raiseNotDefined()

def breadthFirstSearch(problem):
  """
  Search the shallowest nodes in the search tree first.
  [2nd Edition: p 73, 3rd Edition: p 82]
  """
  "*** YOUR CODE HERE ***"
  util.raiseNotDefined()

def aStarSearch(problem, heuristic=nullHeuristic):
    "Search the node that has the lowest combined cost and heuristic first."
    "*** YOUR CODE HERE ***"
    visited = set()
    frontier = util.PriorityQueueWithFunction(lambda x: x[pathCosts] +
        heuristic(x[coordinates], problem))
    currentState = ((problem.getStartState(), [], 0))
    frontier.push(currentState)

    while frontier.isEmpty() == False:
        currentState = frontier.pop()
            
        if problem.isGoalState(currentState[coordinates]):
           return currentState[actions]
        elif currentState[coordinates] in visited:
           continue

        # Here we have the same as before but this time, we have to 
        # add to the successor's path cost to our current value for the 
        # path's up to this point
        for successor in problem.getSuccessors(currentState[coordinates]):
           frontier.push((successor[coordinates], 
            currentState[actions] + [successor[actions]], 
                currentState[pathCosts] + successor[pathCosts]))

        visited.add(currentState[coordinates])
    util.raiseNotDefined()

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    path = []
    cost = 0
    stack = util.Stack()
    visited = set()
    now = problem.getStartState()
    stack.push((now, path, cost))
    while not stack.isEmpty():
        now, path, cost = stack.pop()
        if now in visited:
            continue
        visited.add(now)
        if problem.isGoalState(now):
            return path
        for state, direction, c in problem.getSuccessors(now):
            stack.push((state, path+[direction], cost+c))
    util.raiseNotDefined()

    def train(self, X, Y):
        '''
        just figure out what the most frequent class is for each value of X[:,0] and store it
        '''

        ### TODO: YOUR CODE HERE
        util.raiseNotDefined()

    def predict(self, X):
        """
        check the first feature and make a classification decision based on it
        """

        ### TODO: YOUR CODE HERE
        util.raiseNotDefined()

    def computeActionFromQValues(self, state):
        """
          Compute the best action to take in a state.  Note that if there
          are no legal actions, which is the case at the terminal state,
          you should return None.
        """
        "*** YOUR CODE HERE ***"

        #get all the legal actions
        legalActions = self.getLegalActions(state)
        valueActionPair= []
       # Return None0 if no legal action 
        if len(legalActions)==0:
            return None

        else: 

            #Find the action that returns has maximum qvalue
            for action in legalActions: 
                # record all the value and action pairs
                valueActionPair.append((self.getQValue(state, action), action))
                #get all the best actions if two or more have the best actions
                bestActions = []
                
                for valueAndAction in valueActionPair:
                    if valueAndAction == max(valueActionPair):
                        bestActions.append(valueAndAction)

                #choose one randomly from the bestAction
                bestActionList = random.choice(bestActions)

        return bestActionList[1]
        util.raiseNotDefined()

    def getAction(self, state):
        """
          Compute the action to take in the current state.  With
          probability self.epsilon, we should take a random action and
          take the best policy action otherwise.  Note that if there are
          no legal actions, which is the case at the terminal state, you
          should choose None as the action.

          HINT: You might want to use util.flipCoin(prob)
          HINT: To pick randomly from a list, use random.choice(list)
        """
        # Pick Action
        legalActions = self.getLegalActions(state)
        action = None
        "*** YOUR CODE HERE ***"

        #if terminal state return None
        if len(legalActions)==0:
            return None
        #check random true or false
        
        randomOrNot= util.flipCoin(self.epsilon)
        if  randomOrNot: 
            #Chose east, west, north, south? how do I get the list? 
            return   random.choice(legalActions)
          
        else: 
            #best policy action get policy or compute action from q values? 
            return self.computeActionFromQValues(state)
        
        util.raiseNotDefined()

 def result(self, state, action):
     """
     Given a state and an action, returns resulting state and step cost, which is
     the incremental cost of moving to that successor.
     Returns (next_state, cost)
     """
     util.raiseNotDefined()

    def observe(self, observation, gameState):
        """
        Update beliefs based on the given distance observation. Make
        sure to handle the special case where all particles have weight
        0 after reweighting based on observation. If this happens,
        resample particles uniformly at random from the set of legal
        positions (self.legalPositions).

        A correct implementation will handle two special cases:
          1) When a ghost is captured by Pacman, **all** particles should be updated so
             that the ghost appears in its prison cell, self.getJailPosition()

             You can check if a ghost has been captured by Pacman by
             checking if it has a noisyDistance of None (a noisy distance
             of None will be returned if, and only if, the ghost is
             captured).

          2) When all particles receive 0 weight, they should be recreated from the
             prior distribution by calling initializeUniformly. The total weight
             for a belief distribution can be found by calling totalCount on
             a Counter object

        util.sample(Counter object) is a helper method to generate a sample from
        a belief distribution

        You may also want to use util.manhattanDistance to calculate the distance
        between a particle and pacman's position.
        """

        noisyDistance = observation
        emissionModel = busters.getObservationDistribution(noisyDistance)
        pacmanPosition = gameState.getPacmanPosition()
        "*** YOUR CODE HERE ***"
        util.raiseNotDefined()

    def getLegalActions(self, state):
        """
          state: Search state

        For a given state should return list of legal action
        """
        util.raiseNotDefined()

def breadthFirstSearch(problem):
    """
    Search the shallowest nodes in the search tree first.
    """

    from util import Queue
    from game import Directions
    
    actions = []
    
    frontier = Queue()
    frontier.push((problem.getStartState(), [], 0))
    visited = []

    while (frontier.isEmpty() == False):
        (currentS, currentP, currentC) = frontier.pop()
        if (problem.isGoalState(currentS) == True):
            actions = currentP
            break
        if (visited.count(currentS) == 0):
            visited.append(currentS)
            successors = problem.getSuccessors(currentS)
            for i in range(0,len(successors)):
                (neighbor, direction, cost) = successors[i]
                if (visited.count(neighbor) == 0):
                    frontier.push((neighbor, (currentP +[direction]), (currentC + cost)))
    print actions
    return actions

    util.raiseNotDefined()

    def chooseAction(self, gameState):
        #print self.ghostBeliefs.__str__()
        #return Directions.STOP
        pacmanPosition = gameState.getPacmanPosition()
        legal = [a for a in gameState.getLegalPacmanActions()]
        livingGhosts = gameState.getLivingGhosts()
        l = [beliefs for i,beliefs
             in enumerate(self.ghostBeliefs)
             if livingGhosts[i+1]]
        "*** YOUR CODE HERE ***"
        n = 99999
        array = util.Counter()
        for q in l:
            x = max(q.values())
            m = n
            w = "ahem THIS ahemING oh"
            for e in q:
                if q[e] == x:
                    w = e
            n = min(n, self.distancer.getDistance(w, pacmanPosition))
            if n != m:
                array[n] = w

        for action in legal:
            successorPosition = Actions.getSuccessor(pacmanPosition, action)
            if self.distancer.getDistance(successorPosition, array[min(array.keys())]) < self.distancer.getDistance(pacmanPosition, array[min(array.keys())]):
                return action

        util.raiseNotDefined()

def uniformCostSearch(problem):
    "Search the node of least total cost first. "
    "*** YOUR CODE HERE ***"
    node = [problem.getStartState(),'',1,[]]
    frontier = util.PriorityQueue()
    frontier.push(node,0)
    explored = set()
    explored.add(node[0])
    found = False
    while not found:
        if frontier.isEmpty():
            return []
        node = frontier.pop()
        if problem.isGoalState(node[0]):
            found = True
            solution = node[3]
        explored.add(node[0])
        children = problem.getSuccessors(node[0])
        for child in children:
            if child[0] not in explored:#(explored or frontier[:][0]):
                current_path = list(node[3])
                current_path.append(child[1])
                child = list(child)
                child.append(current_path)
                #explored.add(child[0])
                frontier.push(child, problem.getCostOfActions(current_path))
            #elif len([True for item in frontier.heap if child[0] in item[1]])>0:
            #    print 'child: '+str(child)
            #    print 'frontier items:'+ frontier
    return solution

    util.raiseNotDefined()

 def isGoalState(self, state):
     """
     Returns whether this search state is a goal state of the problem.
     """
     "*** YOUR CODE HERE ***"
     return False not in state[1:]
     util.raiseNotDefined()