1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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);
|
