P2/Q4.py at master · wingsuit/P2 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from reference import build_cave, shortest_path


def optimal_path(data):
    """optimal_path returns the length of the shortest path that enables Falca
    to collect all of the treasures and exit from the dungeon.

    data: a dictionary of features in the cave"""

    # An object holding info on the path
    class Node:
        def __init__(self, weight, visited, treasures, sword):
            self.cost = weight
            self.visited = visited
            self.treasures = treasures
            self.sword = sword

    # Location of the sword
    sword_location = data['sword'] if 'sword' in data else (-1, -1)

    # Treasure locations
    treasure_locations = data['treasure'] if 'treasure' in data else []

    # All locations
    locations = [data['exit']] + treasure_locations
    locations += [data['sword']] if 'sword' in data else []

    # Entrance node
    node = Node(0, [data['entrance']], 0, False)

    # Add the first node onto the que
    unexplored = [(0, id(node), node)]

    while unexplored:

        # Our current position
        unexplored.sort()
        node = unexplored.pop(0)[2]

        # Check for the sword
        if node.visited[-1] == sword_location:
            node.sword = True

        # We made it to the end, return the distance
        if node.visited[-1] == data['exit']:
            return node.cost

        # Find every location we can go from here
        for spot in locations:
            if spot not in node.visited:

                # Dont exit without all the treasure
                if spot == data['exit'] and \
                        node.treasures < len(treasure_locations):
                    continue

                # If the location is reachable, add it to the que
                cost = shortest_path(data, node.visited[-1], spot, node.sword)
                if cost:
                    treasure = 1 if spot in treasure_locations else 0
                    new_node = Node(node.cost + cost, node.visited + [spot],
                                    node.treasures + treasure, node.sword)
                    unexplored.append((new_node.cost, id(new_node), new_node))

    return None