diff options
Diffstat (limited to '2018/aoc2018-d22.py')
| -rw-r--r-- | 2018/aoc2018-d22.py | 136 |
1 files changed, 136 insertions, 0 deletions
diff --git a/2018/aoc2018-d22.py b/2018/aoc2018-d22.py new file mode 100644 index 0000000..7dd7a86 --- /dev/null +++ b/2018/aoc2018-d22.py @@ -0,0 +1,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"); + + |