#advent of code 2018
#day 15
#part 1 and 2
#oop too hard for scriptkid

import heapq

class creature:
	def __init__(self, pos, team, unitID,health,attack):
		self.team = team;
		self.pos = pos;
		self.isAlive = True;
		self.health = health;
		self.attack = attack;
		self.unitID = unitID;
		
	def __str__(self):
		return f'{self.team} #{self.unitID}: {self.health}/200';
		
	def GetAttacked(self,dmg):
		self.health -= dmg;
		if self.health <= 0:
			self.isAlive = False;
			self.health = 0;
			
	def LookAround(self,enemyset):
		targets = [];
		p0,p1 = self.pos;
		for direction in ReadOrder:
			neighbor = (p0+direction[0],p1+direction[1]);
			if neighbor in enemyset:
				targets.append(neighbor);
		return targets;
	
	def pathfinding(self, enemyset, occupiedset):
		paths = [];
		pathlimit = len(grid);
		queue = [];
		heapq.heappush( queue,(0,[self.pos]) );
		visited = set();
		while queue:
			d, path = heapq.heappop(queue);
			if d > pathlimit:
				return paths;
			if path[-1] in enemyset:
				if pathlimit >= len(path):
					paths.append(path);
					pathlimit = len(path);
					continue;
			if path[-1] in visited: continue;
			visited.add(path[-1]);
			p0,p1 = path[-1];
			for direction in ReadOrder:
				neighbor = (p0+direction[0],p1+direction[1]);
				if grid.get(neighbor,"#") != ".":continue;
				if neighbor in occupiedset: continue;
				heapq.heappush(queue,(d+1,path+[neighbor]));
		return paths;
	
	def MakeMove(self, enemyset,occupiedset):
		PossiblePaths = self.pathfinding(enemyset,occupiedset);
		if len(PossiblePaths) != 0:
			for nextpath in sorted( PossiblePaths, key = lambda node: node[1]):
				self.pos = nextpath[1];
				return True;
				break;
		return False;


def run(ulist,att,part2):
	units = dict();
	u_hp = 200;
	for unit in ulist:
		u_pos, u_team, u_id = unit;
		u_att = 3;
		if u_team == "E": u_att = att;
		units[u_id] =  creature(u_pos,u_team,u_id,u_hp,u_att) ;
	
	TotalHP = dict();
	TotalHP["E"] = 1;
	TotalHP["G"] = 1;
	Round = 0;
	while TotalHP["E"] > 0 and TotalHP["G"] > 0:
		if part2 and len([1 for uid in units if units[uid].isAlive==False and units[uid].team=="E"]) != 0:
			return 0;
		
		for unit_id in sorted(units, key=lambda p: units[p].pos):
			if not units[unit_id].isAlive : continue;
			enemyLocation = dict();
			for Unit in units:
				if units[Unit].team != units[unit_id].team and units[Unit].isAlive:
					enemyLocation[units[Unit].pos] = Unit;
			
			occupied = set([units[Unit].pos for Unit in units if units[Unit].isAlive and units[Unit].team == units[unit_id].team]);
			InRangeTargets = units[unit_id].LookAround(enemyLocation);
			
			if len(InRangeTargets) != 0:
				TargetsOrdered = sorted([enemyLocation[tar] for tar in InRangeTargets], key = lambda en: (units[en].health,units[en].pos));
				targetEnemy = TargetsOrdered[0];
				units[targetEnemy].GetAttacked( units[unit_id].attack );
				continue;
			
			MadeMove = units[unit_id].MakeMove(enemyLocation,occupied);
			if not MadeMove: continue;
			InRangeTargets = units[unit_id].LookAround(enemyLocation);
			if len(InRangeTargets) != 0:
				TargetsOrdered = sorted([enemyLocation[tar] for tar in InRangeTargets], key = lambda en: (units[en].health,units[en].pos));
				targetEnemy = TargetsOrdered[0];
				units[targetEnemy].GetAttacked( units[unit_id].attack );
	
		TotalHP["E"] = sum([units[uid].health for uid in units if units[uid].team=="E"]);
		TotalHP["G"] = sum([units[uid].health for uid in units if units[uid].team=="G"]);
		Round += 1;
		###################
		#optional turn by turn battleground output
		'''
		print();
		locations = dict();
		for unitprint in units:
			if not units[unitprint].isAlive:
				locations[ units[unitprint].pos ] = units[unitprint].team.casefold() ;
			else:
				locations[ units[unitprint].pos ] = units[unitprint].team ; 
			print(units[unitprint]);
			
			
		print("Round",Round);
		for y in range(bgsizeY+1):
			for x in range(bgsizeX+1):
				c = locations.get((y,x),grid[(y,x)]);
				print(c,end="");
			print();
		#input();
		'''
		###################
	#part 2 requires all elves to be alive so it's a different check than in part 1
	if part2 and len([1 for u in units if units[u].isAlive==False and units[u].team=="E"]) != 0:
		return 0;
	else: 
		#"number of full rounds that were completed (not counting the round in which combat ends)"
		elfscore = (Round-1)*sum([units[uid].health for uid in units if units[uid].team=="E"]);
		gobscore = (Round-1)*sum([units[uid].health for uid in units if units[uid].team=="G"]);
		return(max(elfscore,gobscore));


bgsizeY = 0;
bgsizeX = 0;
grid = dict();
unitlist = [];
ReadOrder = [(-1,0),(0,-1),(0,1),(1,0)];
unit_counter = 0;
PuzzleInput = open("15.in","r");
for y,l in enumerate(PuzzleInput):
	l = l.replace("\n","");
	bgsizeY = max(bgsizeY,y);
	for x, c in enumerate(l):
		bgsizeX = max(bgsizeX,x);
		if c == "#":
			grid[(y,x)] = "#";
		elif c == ".":
			grid[(y,x)] = ".";
		else:
			unitlist.append(((y,x),c,unit_counter));
			unit_counter += 1;
			grid[(y,x)] = ".";
PuzzleInput.close();

AttackValue = 3;
p1 = run(unitlist,AttackValue,False);
print("part 1 =", p1);
p2 = 0;
while p2 == 0:
	AttackValue += 1;
	p2 = run(unitlist,AttackValue,True);
print("part 2 =", p2);