def heuristic(state):
    """
    Take in a state (a triple of current place, all places before the current
    place, and the total cost associated with the current place) and apply a
    heuristic to it for A* search.
    state (triple): (current place, all places before the current
    place, the total cost associated with the current place)

    return: integer that approximates distance from the goal
    """
    # Encode the progress to the goal as the length of the list of previous states
    progress = len(state[0])
    # Goal distance is the number of places left to be added multiplied by
    # the average of the sadness value to the current point
    if progress != 0:
        goal_distance = (7 - progress) * state[2] / (progress)
    else:
        goal_distance = 7
    return goal_distance