#advent of code 2018 
#day 13
#part 1
import heapq

f = open("input.txt",'r');
Testing = False;
Testing = True; 
if Testing:
	f.close();
	f = open("testinput.txt",'r');
Testing2 = False; 
Testing2 = True; 
if Testing2:
	f.close();
	f = open("testinput2.txt",'r');
Testing3 = False; 
#Testing3 = True; 
if Testing3:
	f.close();
	f = open("testinput3.txt",'r');
Testing4 = False; 
#Testing4 = True; 
if Testing4:
	f.close();
	f = open("testinput4.txt",'r');
Testing5 = False; 
Testing5 = True; 
if Testing5:
	f.close();
	f = open("testinput5.txt",'r');
Testing6 = False; 
Testing6 = True; 
if Testing6:
	f.close();
	f = open("testinput6.txt",'r');
Testing7 = False; 
Testing7 = True; 
if Testing7:
	f.close();
	f = open("testinput7.txt",'r');
NotTesting = False; 
NotTesting = True; 
if NotTesting:
	f.close();
	f = open("input.txt",'r');
	#f = open("shit.txt",'r');

class thing:
	def __init__(self, Pos, sign, currentID):
		self.sign = sign;
		self.PosX = Pos[1];
		self.PosY = Pos[0]; 
		self.IsAlive = False;
		if (sign == "."):
			self.IsPassable = True;
		else:
			self.IsPassable = False;
	def __str__(self):
		return self.sign;
		
	def SquaresInRange(self,bg):
		squares = [];
		p = (self.PosY-1,self.PosX);
		if(bg[p].IsPassable): squares.append(p);
		p = (self.PosY,self.PosX-1);
		if(bg[p].IsPassable): squares.append(p);
		p = (self.PosY,self.PosX+1);
		if(bg[p].IsPassable): squares.append(p);
		p = (self.PosY+1,self.PosX);
		if(bg[p].IsPassable): squares.append(p);
		return squares;

class creature(thing):
	def __init__(self, Pos, sign, currentID):
		thing.__init__(self, Pos, sign, currentID);
		self.ID = currentID;
		self.health = 200;
		self.damage = 3;
		self.side = sign;
		self.IsAlive = True;
		if (self.side == "G"):
			self.enemy = "E";
		if (self.side == "E"):
			self.enemy = "G";
		
	def death(self,bg):
		self.IsPassable = True;
		self.IsAlive = False;
		self.health = 0;
		unitcords[(self.PosY,self.PosX)] = None;
		bg[(self.PosY,self.PosX)].IsPassable = True;
		
		
	def movement(self,bg,PosNow,PosNew):
		self.PosX = PosNew[1];
		self.PosY = PosNew[0];
		bg[PosNow].IsPassable = True;
		bg[PosNew].IsPassable = False;
		unitcords[PosNew] = self.ID;
		unitcords[PosNow] = None;
	

	def ScanProximity(self):
		targets = [];
		p = (self.PosY-1,self.PosX);
		if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0:
			targets.append(p);
		p = (self.PosY,self.PosX-1);
		if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0:
			targets.append(p);
		p = (self.PosY,self.PosX+1);
		if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0:
			targets.append(p);
		p = (self.PosY+1,self.PosX);
		if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0:
			targets.append(p);
		if targets:
			targets.sort(key = lambda x: (units[unitcords[x]].health,units[unitcords[x]].PosY,units[unitcords[x]].PosX));
		return targets;
	
		
	def IdentifyTargets_ALL(self,creaturelist,bg):
		points = [];
		for c in creaturelist:
			if units[c].side == self.side or not units[c].IsAlive: continue;
			points.extend(units[c].SquaresInRange(bg));
		return points;
		
	
	def ShortestPaths(self, pointlist, bg):
		paths = [];
		pathlen = len(bg);
		queue = [];
		heapq.heappush(queue, (0,[(self.PosY,self.PosX)]));
		visited = [];
		while queue:
			d, path = heapq.heappop(queue);
			if d > pathlen:
				return paths;
			if path[-1] in pointlist:
				if pathlen > len(path):
					paths.append(path);
					pathlen = len(path);
					continue;
			if path[-1] in visited:
				continue;
			else: 
				visited.append(path[-1]);
			for a in bg[path[-1]].SquaresInRange(bg):
				if a in visited: continue;
				heapq.heappush(queue, (d+1, path + [a]));
		return paths;
		
	def ChosenPath(self, pointlist, bg):
		paths = self.ShortestPaths(pointlist, bg);
		if len(paths) != 0:
			pathends = min([p[-1] for p in paths]);
			paths2= self.ShortestPaths([pathends], bg);
			if len(paths2) != 0:
				moves = [];
				for p in paths:
					moves.append(p[1]);
				moves = sorted(moves, key = lambda m: (m[0],m[1]));
				m = moves[0];
				self.movement(bg,(self.PosY,self.PosX),m);
			

def PathSearch(bg, Coordinates, Destination):
	pass;

def strike(attacker, target,bg):
	target.health -= attacker.damage;
	if (target.health <= 0):
		target.death(bg);

def armystrength(army):
	strength = 0;
	for soldier in army:
		strength += units[unitcords[soldier]].health;
	return strength;

def armyscores():
	ElfScore = 0;
	GobScore = 0;
	for u in units:
		if units[u].side == "G": GobScore += units[u].health;
		if units[u].side == "E": ElfScore += units[u].health;
	
	return max(ElfScore,GobScore);



def FindEnemies(team):
	Enemies = 0;
	for u in units:
		if units[u].IsAlive and units[u].side != team: Enemies += 1;
	
	return Enemies;
###############################################################################


bgsizex = 0;
bgsizey = 0;
battleground = {};
units = {};
unitcords = {};

identifier = 11;

for y, line in enumerate(f):
	bgsizey += 1;
	bgsizex = 0;
	for x, c in enumerate(line):
		bgsizex += 1;
		if c == "G" or c == "E":
			battleground[(y,x)] = thing((y,x),".",identifier);
			units[identifier] = creature((y,x),c, identifier);
			units[identifier].movement(battleground, (y,x), (y,x));
			identifier += 1;
		else:
			battleground[(y,x)] = thing((y,x),c,identifier);
'''	
for y in range(bgsizey):
	for x in range(bgsizex):
		if (y,x) in unitcords: 
			print("X",end="");
		else: 
			print(battleground[(y,x)],end=""); #'''
	

unitcords = {};
for u in units:
	unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID;


elfs = sum([1 for x in units if units[x].IsAlive and units[x].side=="E"]);
goblins = sum([1 for x in units if units[x].IsAlive and units[x].side=="G"]);

ElapsedRounds = 0;


while goblins and elfs:
	fighters = [];
	for u in units:
		if units[u].IsAlive: 
			fighters.append(units[u].ID);
			
	fighters = sorted(fighters, key = lambda u: (units[u].PosY,units[u].PosX));
	
	for fighter in fighters:
		if not units[fighter].IsAlive: continue;
		if FindEnemies(units[fighter].side) <= 0:
			print("loop broken FIGHTERS");
			break;
		tars = units[fighter].ScanProximity();
		if tars:
			tar = tars[0];
			strike(units[fighter],units[unitcords[tar]],battleground);
		else:
			CurrentPos = (units[fighter].PosY,units[fighter].PosX);
			IdenTars = units[fighter].IdentifyTargets_ALL(fighters,battleground);
			units[fighter].ChosenPath(IdenTars,battleground);
			if CurrentPos == (units[fighter].PosY,units[fighter].PosX):
				continue;
			else:
				tars = units[fighter].ScanProximity();
				if tars:
					tar = tars[0];
					strike(units[fighter],units[unitcords[tar]],battleground);
	
		unitcords = {};
		for u in units:
			unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID;
			
	print("ROUND ", ElapsedRounds);
	unitcords = {};
	for u in units:
		unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID;
	
	ElapsedRounds += 1;
	elfs = sum([1 for x in units if units[x].IsAlive and units[x].side=="E"]);
	goblins = sum([1 for x in units if units[x].IsAlive and units[x].side=="G"]);
	'''
	for y in range(bgsizey):
		for x in range(bgsizex):
			if (y,x) in unitcords and unitcords[(y,x)] in units and units[unitcords[(y,x)]].IsAlive: 
				print(units[unitcords[(y,x)]].side,end="");
			else: 
				print(battleground[(y,x)],end="");	
	print();
	'''
	
	'''
	for y in range(bgsizey):
		for x in range(bgsizex):
			print((y,x), " - ", battleground[(y,x)].IsPassable);
	print();
	print();
	'''
	


unitcords = {};
for u in units:
	unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID;
	print(u, f'({units[u].side} / ({units[u].PosY},{units[u].PosX})) ', units[u].health);
		

for y in range(bgsizey):
	for x in range(bgsizex):
		if (y,x) in unitcords and unitcords[(y,x)] in units and units[unitcords[(y,x)]].IsAlive: 
			print(units[unitcords[(y,x)]].side,end="");
		else: 
			print(battleground[(y,x)],end="");	
print();


print("part 1    =  ", ElapsedRounds, "*",armyscores(), "=",ElapsedRounds*armyscores());
print("lil cheat =  ", (ElapsedRounds-1), "*",armyscores(), "=",(ElapsedRounds-1)*armyscores());
#I cant get the correct answer without implementing any short circuit logics
#thats why I print 2 outputs, for number of rounds and (number of rounds -1)

#190777 p1 correct