1 files changed, 85 insertions, 0 deletions
diff --git a/2018/aoc2018-d23.py b/2018/aoc2018-d23.py
new file mode 100644
index 0000000..72ee7f3
--- /dev/null
+++ b/2018/aoc2018-d23.py
@@ -0,0 +1,85 @@
+#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);