#!/usr/bin/env python3

def main():
    # This is a sample main function that shows examples and expected
    # outputs of calling the heuristic and astar functions.
    #
    # It is called in the conditional at the bottom if this file
    # is the main file your interpreter is running on and it is
    # not called when this file is used as a module for our grading.
    # You do not have to delete this function before submitting
    # the file for grading.

    initState = (2, 8, 3, 1, 0, 5, 4, 7, 6)
    print('=== heuristic_misplaced')
    print(' + Expected value: {}'.format(7))
    print(' +     Your value: {}'.format(heuristic_misplaced(initState)))
    print('=== heuristic_manhattan')
    print(' + Expected value: {}'.format(8))
    print(' +     Your value: {}'.format(heuristic_manhattan(initState)))
    print('=== astar_misplaced')
    expectedPath = 'ulddrurd'
    expectedStates = [
        (2, 8, 3, 1, 0, 5, 4, 7, 6),
        (2, 8, 3, 1, 5, 0, 4, 7, 6),
        (2, 8, 3, 1, 5, 6, 4, 7, 0),
        (2, 0, 3, 1, 8, 5, 4, 7, 6),
        (0, 2, 3, 1, 8, 5, 4, 7, 6),
        (1, 2, 3, 0, 8, 5, 4, 7, 6),
        (1, 2, 3, 4, 8, 5, 0, 7, 6),
        (1, 2, 3, 4, 8, 5, 7, 0, 6),
        (1, 2, 3, 4, 0, 5, 7, 8, 6),
        (1, 2, 3, 4, 5, 0, 7, 8, 6),
        (1, 2, 3, 4, 5, 6, 7, 8, 0)
    ]
    path, states = astar(initState, heuristic_misplaced)
    print(' + Expected path: {}'.format(expectedPath))
    print(' +     Your path: {}'.format(path))
    print(' + Expected states:')
    for i in range(len(expectedStates)):
        print('   + {}'.format(expectedStates[i]))
    print(' + Your states:')
    for i in range(len(states)):
        print('   + {}'.format(states[i]))

    print('=== astar_manhattan')
    expectedPath = 'ulddrurd'
    expectedStates = [
        (2, 8, 3, 1, 0, 5, 4, 7, 6),
        (2, 0, 3, 1, 8, 5, 4, 7, 6),
        (0, 2, 3, 1, 8, 5, 4, 7, 6),
        (1, 2, 3, 0, 8, 5, 4, 7, 6),
        (1, 2, 3, 4, 8, 5, 0, 7, 6),
        (1, 2, 3, 4, 8, 5, 7, 0, 6),
        (1, 2, 3, 4, 0, 5, 7, 8, 6),
        (1, 2, 3, 4, 5, 0, 7, 8, 6),
        (1, 2, 3, 4, 5, 6, 7, 8, 0)
    ]
    path, states = astar(initState, heuristic_manhattan)
    print(' + Expected path: {}'.format(expectedPath))
    print(' +     Your path: {}'.format(path))
    print(' + Expected states:')
    for i in range(len(expectedStates)):
        print('   + {}'.format(expectedStates[i]))
    print(' + Your states:')
    for i in range(len(states)):
        print('   + {}'.format(states[i]))

def heuristic_misplaced(state):
    """
    The number of misplaced tiles.
    The blank space is not tile and should
    not be included in your misplaced tile count.

    :param state: A tuple of the flattened board.
    :return: The number of misplaced tiles.
    """

    # [TODO: Your implementation here]

    return -1 # TODO: Replace this with your value.

def heuristic_manhattan(state):
    """
    The sum of the Manhattan distances from the
    misplaced tiles to their correct positions.*

    :param state: A tuple of the flattened board.
    :return: The summed manhattan distances.
    """

    # [TODO: Your implementation here]

    return -1 # TODO: Replace this with your value.

def astar(init_state, heuristic):
    """
    A^* implementation.

    :param init_state: A tuple of the flattened board.
    :param heuristic: The heuristic function
    :return: A tuple where:
        The first element is a string representing the optimal path.
            Use the characters 'r', 'l', 'u', and 'd' for
            'right', 'left', 'up', and 'down' directions, respectively.
        The second element is a list that contains states in the
            in order they were visited by your algorithm.
    """

    states_visited = []

    # [TODO: Your implementation here]

    return 'ldlru', states_visited # TODO: Replace this with your values.

if __name__=='__main__':
    main()