-
Notifications
You must be signed in to change notification settings - Fork 0
/
day_17.py
160 lines (118 loc) · 4.11 KB
/
day_17.py
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
TEST = False
in_file = "./resources/day_17_test.txt" if TEST else "./resources/day_17_input.txt"
import numpy as np
from queue import PriorityQueue
directions = {"R": (0, 1), "L": (0, -1), "D": (1, 0), "U": (-1, 0)}
with open(in_file) as file:
graph = []
for line in file:
"""Custom iteration logic goes here"""
line = line.strip()
graph.append([int(i) for i in line])
graph = np.array(graph)
def question_1():
"""Answer to the first question of the day"""
answer = None
frontier = PriorityQueue()
start = (0, 0)
goal = (len(graph)-1, len(graph[0])-1)
frontier.put((start, "", 1), 0)
came_from = dict()
cost_so_far = dict()
came_from[(start, "", 1)] = None
cost_so_far[(start, "", 1)] = 0
while not frontier.empty():
current = frontier.get()
pos, direc, steps = current
for d in ["R", "L", "D", "U"]:
if direc and directions[direc] == tuple(-i for i in directions[d]):
continue
if steps == 3 and direc == d:
continue
next = tuple(map(sum, zip(pos, directions[d])))
x,y = next
if x < 0 or y < 0 or x >= len(graph) or y >= len(graph[0]):
continue
new_cost = cost_so_far[current] + graph[*next]
if direc == d:
next_steps = steps + 1
else:
next_steps = 1
next = (next, d, next_steps)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.put(next, priority)
came_from[next] = current
best = 10000000
for i in cost_so_far:
if i[0] == goal and cost_so_far[i] < best:
print(i, cost_so_far[i])
best = cost_so_far[i]
best_route = i
# output(best_route, came_from)
return best
def output(current, came_form):
path = [current]
while current:
# print(current)
current = came_form[current]
if current:
path.append(current[0])
# print(path)
for i, row in enumerate(graph):
for j, col in enumerate(row):
if (i, j) in path:
print("#", end="")
else:
print(col, end="")
print()
def question_2():
"""Answer to the second question of the day"""
answer = None
frontier = PriorityQueue()
start = (0, 0)
goal = (len(graph)-1, len(graph[0])-1)
frontier.put((start, "", 1), 0)
came_from = dict()
cost_so_far = dict()
came_from[(start, "", 1)] = None
cost_so_far[(start, "", 1)] = 0
while not frontier.empty():
current = frontier.get()
pos, direc, steps = current
for d in ["R", "L", "D", "U"]:
if direc and directions[direc] == tuple(-i for i in directions[d]):
continue
if steps == 10 and direc == d:
continue
if direc and steps < 4 and direc != d:
continue
next = tuple(map(sum, zip(pos, directions[d])))
x,y = next
if x < 0 or y < 0 or x >= len(graph) or y >= len(graph[0]):
continue
new_cost = cost_so_far[current] + graph[*next]
if direc == d:
next_steps = steps + 1
else:
next_steps = 1
next = (next, d, next_steps)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.put(next, priority)
came_from[next] = current
best = 10000000
for i in cost_so_far:
if i[0] == goal and cost_so_far[i] < best:
print(i, cost_so_far[i])
best = cost_so_far[i]
best_route = i
# output(best_route, came_from)
return best
if __name__ == '__main__':
# answer_1 = question_1()
# print(f"Question 1 answer is: {answer_1}")
answer_2 = question_2()
print(f"Question 2 answer is: {answer_2}")