#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");