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
|
#advent of code 2018
#day 22
#part 1 and part 2
#at this point Im used to pathfinding problems, so I expected an easy 2-star
#I started with a recursive djikstra-algo function, but unfortunately
#for the actual input, I was reaching the maximum number of recurrences
#my plan B was a queue, which in general was correct, but I was missing one detail
#the problem isnt 2D pathfinding, but 4D (width, depth, time AND equipment)
#to discover this I needed to look up a solution on reddit
#said solution reminded me of heapq module which I already intended to learn
#the results were great - my initial no-heapq code needed almost 10 minutes to finish
#while with heapq whole program ran for less than half a second
#while I tried to compensate for the equipment variable with some
#"guess which equipment is probably the best choice when traversing"
#it didnt really help as much as heapq
#anyway, I still wasnt getting the correct answer
#This time the issue was in the design:
#in order to account for regions that are outside the initial scope
#(within target coordinates range) I simply scaled up the whole map by constant factor
#for factor = 2 the map still wasnt big enough to create the shortest path
#I needed to scale it up by factoer = 6 to get the correct result
#while this scale-up strategy isnt *that* bad for square-ish maps
#this map is extremely deep, but not very wide
#I really liked the idea to calculate the region type on the spot for part2
#which I noticed only after struggling for 3 hours to fix my code
#might redo the part2 to fix this
#if the code doesnt provide correct results for part 2, try changing the SCALE variable
#to a bigger number
#
import time;
import heapq;
f = open("input.txt",'r');
Testing = False;
#Testing = True;
if Testing:
f.close();
f = open("testinput.txt",'r');
depth = eval(f.readline().replace("depth: ",""));
target = tuple(eval(f.readline().replace("target: ","")));
f.close();
#determine the type of region and other parameters
class region:
def __init__(self, pos, erosion1, erosion2):
self.Distance = 99999; #for when I tried to use djikstra
self.Equipped = None;
self.pos = pos;
if pos == (0,0) or pos == target: self.geo = 0;
elif pos[0] == 0: self.geo = pos[1]*48271;
elif pos[1] == 0: self.geo = pos[0]*16807;
else: self.geo = erosion1*erosion2;
self.erosion = (self.geo + depth)%20183;
self.risk = self.erosion%3;
if (self.risk == 0):
self.type = "R";
self.Gear = ["T","C"];
elif (self.risk == 1):
self.type = "W";
self.Gear = ["C","N"];
elif (self.risk == 2):
self.type = "N";
self.Gear = ["T","N"];
def GetAdjacent(self, grid): #hard to read, should remake this func, but not feeling like it
nextcords = [];
nx, ny = self.pos[0]-1, self.pos[1];
if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny));
nx, ny = self.pos[0]+1, self.pos[1];
if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny));
nx, ny = self.pos[0], self.pos[1]-1;
if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny));
nx, ny = self.pos[0], self.pos[1]+1;
if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny));
return nextcords;
area = {};
mouth = (0,0);
part1 = 0;
#for part 2:
#scale up the area with SCALE - wrong idea, see comment at the start
#SCALE is a variable in case it needs to be adjusted later
SCALE = 6;
#initiate area and calculate part 1
for y in range(SCALE*target[1] +1):
for x in range(SCALE*target[0] +1):
ero1 = 0;
ero2 = 0;
r1 = area.get((x-1,y),None);
r2 = area.get((x,y-1),None);
if r1 != None: ero1 = r1.erosion;
if r2 != None: ero2 = r2.erosion;
area.update({(x,y):region((x,y),ero1,ero2)}); #brackets puke
if ( x in range(target[0] +1) and y in range(target[1] +1)):
part1 += area[(x,y)].risk;
print("part 1 = ", part1);
equip = "T";
area[mouth].Distance = 0;
area[mouth].Equipped = equip;
gears = ["T","C","N"];
queue = [(0, mouth, "T")];
distances = {}; #obviously I meant time, but technically the same thing
t1 = time.time();
while queue:
d, p, e = heapq.heappop(queue);
if (p[0],p[1],e) in distances and distances[(p[0],p[1],e)] <= d: continue;
distances[(p[0],p[1],e)] = d; #update distances with the shorter path
#if the current region is the target and we're holding a torch - finish loop
if p == target and e == "T":
area[p].Equipped = e;
area[p].Distance = d;
break;
#push to queue the same region but with changed gear
for g in gears:
if g != e and g in area[p].Gear:
heapq.heappush(queue, (d+7,p,g));
#push to queue the adjacent regions
neighbours = area[p].GetAdjacent(area);
for neighbour in neighbours:
if not e in area[neighbour].Gear: continue;
heapq.heappush(queue,(d+1,neighbour,e));
t2= time.time();
part2 = area[target].Distance;
print("part2 = ", part2);
print("\tpart 2 runtime ", t2-t1, "s");
|
