#advent of code 2018 
#day 23
#part 1 and part 2

#i have no idea why this works
#i found someone else's solution on github which had a wikipedia link
#the algorithm for cliques is OK but I don't know why we're picking the bot 
#with the largest distance from 0,0,0
#tldr don't ask me shit

def manhattan(pos1, pos2):
	mx = abs(pos1[0] - pos2[0]);
	my = abs(pos1[1] - pos2[1]);
	mz = abs(pos1[2] - pos2[2]);
	return mx + my + mz;
	
def withinRange(b1,b2):
	R1 = b1.radius;
	R2 = b2.radius;
	check = R1 + R2 >= manhattan(b1.pos, b2.pos);
	return check;

def BronKerbosch(R,P,X):
	#https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm#With_pivoting
	cliques = []
	if len(P) == 0 and len(X) == 0: 
		return [R];
	u = max(P.union(X), key = lambda m: len(graph[m]));
	for v in P.difference(graph[u]):
		cliques.extend( BronKerbosch(R.union({v}),P.intersection(graph[v]),X.intersection(graph[v])));
		P.discard(v);
		X.add(v);
	return cliques;

class nanobot:
	def __init__(self, pos, r):
		self.pos = pos;
		self.radius = r;
		self.neighbors = set();
		self.shared = set();
	def __str__(self):
		return f'pos={self.pos}, r={self.radius}';

bots = [];
graph = dict();
f = open("23.in",'r');
for l in f:
	l = l.replace("<","(");
	l = l.replace(">",")");
	l = l.replace("r=","");
	l = l.replace("pos=","");
	p, r = eval(l);
	bots.append(nanobot(p,r));
f.close();

strongest_radius = 0;
strongest_pos = None;
for bot in bots:
	if bot.radius > strongest_radius:
		strongest_radius = bot.radius;
		strongest_pos = bot.pos;

part1 = 0;
candidates = set();
for b_i,bot in enumerate(bots):
	#for part 1
	if (manhattan(strongest_pos, bot.pos) <= strongest_radius): part1 += 1; 
	#for part 2
	graph[b_i] = set();
	candidates.add(b_i);
	for b_j, bot2 in enumerate(bots):
		if b_i==b_j:continue;
		if withinRange(bots[b_i],bots[b_j]):
			graph[b_i].add(b_j);
print("part1 = ", part1);

BotCliques = BronKerbosch(set(),candidates,set());
BiggestClique = max(BotCliques, key=lambda clique: len(clique));
distances = [];
for cliquebot in BiggestClique:
	LowestDistance = max(manhattan(bots[cliquebot].pos,(0,0,0)) - bots[cliquebot].radius,0);
	distances.append(LowestDistance);

p2 = max(distances);
print("part 2 =",p2);