from reference import build_cave, shortest_path
data = {'size': 4,'entrance': (0, 0),'exit': (2, 1),'dragon': (0, 2),'sword': (3, 3),'treasure': [(1, 3)],'walls': [(1, 1), (1, 2), (2, 2), (2, 3)]}
data2 = {'size': 5,'entrance': (0, 2),'exit': (0, 4),'sword': (0, 0),'dragon': (2, 1),'treasure': [(0, 3), (4, 1)]}
'''
node = start state
unexplored = a priority queue containing node as the only element

repeat:
    if unexplored is empty:
        return failure (there is no valid path)
    node = node in unexplored with the lowest cost
    if node == end state:
        return solution
    for each valid move from node:
        child = result of executing move
        if child is not in unexplored:
            add child to unexplored, together with its cost
        else if child is in unexplored and the new cost is less than
                    current cost:
            replace the current cost with new cost
'''

def generate_moves(data, node, has_sword, explored,
                   collected_treasure):
    possible_moves = []

    if has_sword is False:
        if 'sword' in data:
            sword = (shortest_path(data, node[1], data['sword'], False), data['sword'], node[1])
            possible_moves.append(sword)

    if 'treasure' in data:
        treasure = data['treasure']
        treasure_one = (shortest_path(data, node[1], data['treasure'][0], has_sword), data['treasure'][0], node[1])
        if treasure_one[1] != node[1]:
            possible_moves.append(treasure_one)
        required_treasure = 1
        if len(treasure) == 2:
            treasure_two = (shortest_path(data, node[1], data['treasure'][1], has_sword), data['treasure'][1], node[1])
            if treasure_two[1] != node[1]:
                possible_moves.append(treasure_two)
            required_treasure = 2
        if len(treasure) == 3:
            treasure_three = (shortest_path(data, node[1], data['treasure'][2], has_sword), data['treasure'][2], node[1])
            if treasure_three[1] != node[1]:
                possible_moves.append(treasure_three)
            required_treasure = 3

    if collected_treasure == required_treasure:
        end = data['exit']
        find_exit = (shortest_path(data, node[1], end, has_sword), end, node[1])
        possible_moves = []
        possible_moves.append(find_exit)


    for move in possible_moves:
        if move[0] == None:
            possible_moves.remove(move)


    return sorted(possible_moves)

def count(start, end, path, path_count):

    count = 0
    total_path = [end]
    while total_path[-1] != start:
        total_path.append(path[total_path[-1]])

    for node in total_path:
        count += path_count[node]

    return count


def optimal_path(data):
    '''
    '''
    start = data['entrance']
    node = (0, start, start)
    explored = set()
    unexplored = [node]
    end = data['exit']
    path = {}

    path_count = {}
    collected_treasure = 0
    has_sword = False
    if 'sword' in data:
        sword = data['sword']

    while sorted(unexplored):
        node = unexplored.pop(0)
        explored.add(node[1])

        if node[1] == end:
            path_count[node[1]] = node[0]

            return (count(start, end, path, path_count))
        if node[1] == sword:
            has_sword = True
        if 'treasure' in data:
            if node[1] in data['treasure']:
                collected_treasure += 1

        possible_moves = generate_moves(data, node, has_sword, explored,
                                        collected_treasure)
        for move in sorted(possible_moves):
            unexplored.append(move)
            path[move[1]] = move[2]
            path_count[node[1]] = node[0]