AdventOfCode2021/day15_task1.py at master · HenrikSZ/AdventOfCode2021 · 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
###############################################################################
# Day x, Task y                                                               #
###############################################################################

import aoc_util, sys


day = 15
data_str = """1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""


class Dijkstra():
    def __init__(self, matrix):
        self.matrix = matrix
        self.vertices = []
        self.dists = {(0, 0): 0}
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                vertex = (row, col)
                self.vertices.append(vertex)
                self.dists[vertex] = sys.maxsize

        self.dists[(0, 0)] = 0

    def find_min_distance_vertex(self):
        min_dist_vertex = (0, 0)
        distance = sys.maxsize
        for k in self.vertices:
            if self.dists[k] < distance:
                distance = self.dists[k]
                min_dist_vertex = k

        return distance, min_dist_vertex


    def get_neighbours(self, vertex):
        neighbours = []
        if (vertex[0] - 1, vertex[1]) in self.vertices:
            neighbours.append((vertex[0] - 1, vertex[1]))
        if (vertex[0], vertex[1] - 1) in self.vertices:
            neighbours.append((vertex[0], vertex[1] - 1))
        if (vertex[0], vertex[1] + 1) in self.vertices:
            neighbours.append((vertex[0], vertex[1] + 1))
        if (vertex[0] + 1, vertex[1]) in self.vertices:
            neighbours.append((vertex[0] + 1, vertex[1]))

        return neighbours


    def solve(self):
        while len(self.vertices) > 0:
            distance, min_distance_vertex = self.find_min_distance_vertex()
            self.vertices.remove(min_distance_vertex)

            neighbours = self.get_neighbours(min_distance_vertex)
            for n in neighbours:
                alt = distance + self.matrix[n[0]][n[1]]

                if alt < self.dists[n]:
                    self.dists[n] = alt

        return self.dists[(len(self.matrix) - 1, len(self.matrix[0]) - 1)]


def task(data_set: list[str]) -> int:
    risk_map = []
    for i in data_set:
        row = [int(x) for x in i]
        risk_map.append(row)

    dijkstra = Dijkstra(risk_map)

    return dijkstra.solve()


aoc_util.run_with_data_str(task, data_str)
aoc_util.run_with_data_set(task, day)