def genericSearch(problem, fn):
    # Inputs are a search problem - infrastructure provided by the class
    # It has all the information about the current state, goal state, etc.
    # They also made the util module available, which contains a Priority Queue
    # which is the basis for the search.  Priority Queue is a queue that arranges by
    # a given priority value.  Popping the lowest priority value can be done in O(1).
    fringe = util.PriorityQueue()
    closed = set()

    # My main piece of information I'm passing around is a tuple.
    # (state, actions) -- state is the current game state
    # containg relevant info like pacman's location, food locations, etc.
    # Actions is what we eventually return, a list of 'N', 'S', 'E', 'W' directions
    # to follow to win.
    fringe.push((problem.getStartState(), []), 0)
    while True:
        if fringe.isEmpty():
            # Fringe should never be empty.  That's why we throw an exception
            raise Exception("Fringe was empty!")
        current = fringe.pop()
        if current[0] in closed:
            # I implemented a graph search, which doesn't expand nodes more than once for
            # efficiency's sake.
            continue
        closed.add(current[0])
        if problem.isGoalState(current[0]):
            # return the list of actions if we end up declaring victory
            return current[1]

        # Otherwise, expand this current state, evaluate priorities based on the fn
        # and add them to the fringe.
        successors = problem.getSuccessors(current[0])
        for successor in successors:
            nextOne = (successor[0], current[1] + [successor[1]])
            fringe.update(nextOne, fn(nextOne))

def depthFirstSearch(problem):
    """Search the deepest nodes first"""
    def priorityFn(item):
        return -1 * len(item[1])    # Make sure the deepest nodes have the lowest priority
                                    # so that they are popped off the queue first
    return genericSearch(problem, priorityFn)

def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first."""
    def priorityFn(item):
        return len(item[1])     # Make sure the shallowest nodes have low priority
    return genericSearch(problem, priorityFn)

def uniformCostSearch(problem):
    """Search the node of least total cost first."""
    def priorityFn(item):
        return problem.getCostOfActions(item[1])
    return genericSearch(problem, priorityFn)

def aStarSearch(problem, heuristic=nullHeuristic):
    """Search the node that has the lowest combined cost and heuristic first."""
    def priorityFn(item):
        g = problem.getCostOfActions(item[1])
        h = heuristic(item[0], problem)
        return g + h
    return genericSearch(problem, priorityFn)

def manhattanHeuristic(position, problem, info={}):
    "The Manhattan distance heuristic for a PositionSearchProblem"
    # Provided by the class
    xy1 = position
    xy2 = problem.goal
    # Add up the city grid distance you would drive from point to point
    # abs x distance + abs y distance
    return abs(xy1[0] - xy2[0]) + abs(xy1[1] - xy2[1])

def shortestDistance(start, points, fn=util.manhattanDistance, initial=0, ):
    # Inspired by stackOverflow
    if len(points) == 0:
        return initial
    # Get the point that is closest to the start point.
    # Then leapfrog to the next closest point to that one, adding up the distance.
    # Return the full distance to get the the closest point and then loop through the rest of the points
    # Recursively

    # I could have probably done something more efficient by popping off of a list rather than recreate the list each time
    shortest = min(points, key=lambda x: fn(start, x))
    return shortestDistance(shortest, [p for p in points if p != shortest], fn=fn, initial=initial + fn(start, shortest))