code-challenges-v2/python/src/code_wars/sg1.py at main · W-Ely/code-challenges-v2 · 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import math
from queue import PriorityQueue


class DialHomeDevice:
    def __init__(self, galactic_map):
        self.start, self.goal = None, None
        self._galactic_gates = [
            [self._create_gate(x, y, gate) for x, gate in enumerate(gates)]
            for y, gates in enumerate(galactic_map.split("\n"))
        ]
        self._set_connections()

    def _create_gate(self, x, y, gate_key):
        if gate_key == "X":
            return None
        gate = Gate(x, y)
        if gate_key == "S":
            self.start = gate
        elif gate_key == "G":
            self.goal = gate
        return gate

    def _set_connections(self):
        for gates in self._galactic_gates:
            for gate in gates:
                if gate:
                    gate.connect(self._galactic_gates, self.goal)

    def dial_home(self):
        queue = PriorityQueue()
        queue.put((0, self.start, []))
        visited = {}
        visited[self.start] = 0
        shortest_route = None
        shortest_distance = math.inf
        while queue.qsize() > 0:
            previous_distance, current, route = queue.get_nowait()
            for gate in current.connections:
                distance = previous_distance + math.dist(
                    gate.location, current.location
                )
                if gate == self.goal:
                    if distance < shortest_distance:
                        shortest_route = route
                        shortest_distance = distance
                else:
                    visited_distance = visited.get(gate, math.inf)
                    if visited_distance > distance:
                        queue.put((distance, gate, route + [gate]))
                        visited[gate] = distance
        if shortest_distance < math.inf:
            return self._route(shortest_route)
        return "Oh for crying out loud..."

    def _route(self, route):
        map_key = {None: "X", self.start: "S", self.goal: "G"}
        return "\n".join(
            [
                "".join(
                    [
                        "P" if gate and gate in route else map_key.get(gate, ".")
                        for gate in gates
                    ]
                )
                for gates in self._galactic_gates
            ]
        )


class Gate:
    def __init__(self, x, y):
        self.location = x, y
        self.connections = set()
        self.distance_from_goal = None

    def __repr__(self):
        x, y = self.location
        return f"Gate({x}, {y})"

    def __hash__(self):
        return hash(self.location)

    def __eq__(self, other_gate):
        return self.location == other_gate.location

    def __lt__(self, other_gate):
        return self.distance_from_goal < other_gate.distance_from_goal

    def connect(self, galactic_gates, goal):
        self.distance_from_goal = math.dist(self.location, goal.location)
        up, down = (0, 1), (0, -1)  # pylint: disable=invalid-name
        left, right = (-1, 0), (1, 0)
        up_left, up_right = (-1, 1), (1, 1)
        down_left, down_right = (-1, -1), (1, -1)
        directions = (up, left, right, down, up_left, up_right, down_left, down_right)
        max_x, max_y = len(galactic_gates[0]) - 1, len(galactic_gates) - 1
        for i, j in directions:
            x, y = self.location
            x, y = x + i, y + j
            if x < 0 or x > max_x or y < 0 or y > max_y:
                continue
            neighbor = galactic_gates[y][x]
            if neighbor:
                neighbor.connections.add(self)
                self.connections.add(neighbor)


def wire_DHD_SG1(existing_wires):  # pylint: disable=invalid-name
    """Code Wars entry point"""
    dhd = DialHomeDevice(existing_wires)
    return dhd.dial_home()