For part2 I also checked the degrees of nodes but then I concluded, that I'm fine with brute forcing 2^13 subsets for each node's neighborhood. Then I just intersected all neighbors of those nodes in the subset trying to find the biggest such result. It runs in ~18s, so I'm fine with that.
For part 1 I built all the "triangles", and later filtered the ones where at least one started with 't'. So outer loop - all nodes, inner loop - all nodes connected to first one, compute intersection of neighbors, order alphabetically and add to a set. Fast enough. For part 2 - I didn't even knew about "clique", knew about networkx, but this year didn't use libraries (except re, of course). But, did a dumb bruteforce on top of part 1. So, part 1 gives all the triangles. Then, for each node, check which triangles it is connected to, and build a new set of "squares" and so on, in a loop, build all "cliques" with size N+1 until only 1 remained, and that was the answer. Not very efficient, but again - if it works - it is not dumb.
Weird problem for day 23. Literally 6 lines of code for both parts with networkx. import networkx as nx G = nx.Graph() for line in open('input.txt').read().strip().split(' '): G.add_edge(*line.split('-')) print(sum(1 for c in nx.enumerate_all_cliques(G) if len(c) == 3 and any(n.startswith('t') for n in c))) print(','.join(sorted(max(nx.enumerate_all_cliques(G), key=len))))
I've manually expanded pairs... def solve2(text): E = defaultdict(set) P = [] for line in text.splitlines(): a, b = line.strip().split("-") E[a].add(b) E[b].add(a) P.append({a, b}) groups = P seen = set() while True: new_groups = [] for set_members in groups: possible_candidates = set.intersection(*(E[x] for x in set_members)) for candidate in possible_candidates: new_grp = set_members | {candidate} key = tuple(sorted(new_grp)) if key not in seen: seen.add(key) new_groups.append(new_grp) if not new_groups: break groups = new_groups assert len(groups) == 1 res = ",".join(sorted(groups[0])) return res
For part2 I also checked the degrees of nodes but then I concluded, that I'm fine with brute forcing 2^13 subsets for each node's neighborhood. Then I just intersected all neighbors of those nodes in the subset trying to find the biggest such result. It runs in ~18s, so I'm fine with that.
What keyboard are you using? Sounds great!
for part 2 i checked each n-element subset of each node's adjacency list for each n >= the max clique found so far. runs in under a second.
For part 1 I built all the "triangles", and later filtered the ones where at least one started with 't'.
So outer loop - all nodes, inner loop - all nodes connected to first one, compute intersection of neighbors, order alphabetically and add to a set. Fast enough.
For part 2 - I didn't even knew about "clique", knew about networkx, but this year didn't use libraries (except re, of course).
But, did a dumb bruteforce on top of part 1.
So, part 1 gives all the triangles. Then, for each node, check which triangles it is connected to, and build a new set of "squares"
and so on, in a loop, build all "cliques" with size N+1 until only 1 remained, and that was the answer.
Not very efficient, but again - if it works - it is not dumb.
Not a fan of the graph theory ones, tbh. It always just boils down to “do you remember that one specific algorithm?”
Lovely maximal clique problem
Weird problem for day 23. Literally 6 lines of code for both parts with networkx.
import networkx as nx
G = nx.Graph()
for line in open('input.txt').read().strip().split('
'):
G.add_edge(*line.split('-'))
print(sum(1 for c in nx.enumerate_all_cliques(G) if len(c) == 3 and any(n.startswith('t') for n in c)))
print(','.join(sorted(max(nx.enumerate_all_cliques(G), key=len))))
Having a graph theory library definitely does help when your problem is exclusively graph theory.
for a in E.keys():
for b in E[a]:
for c in E[b]:
if a < b < c and c in E[a] and "t" in [a[0], b[0], c[0]]:
res += 1
That’ll do it
I've manually expanded pairs...
def solve2(text):
E = defaultdict(set)
P = []
for line in text.splitlines():
a, b = line.strip().split("-")
E[a].add(b)
E[b].add(a)
P.append({a, b})
groups = P
seen = set()
while True:
new_groups = []
for set_members in groups:
possible_candidates = set.intersection(*(E[x] for x in set_members))
for candidate in possible_candidates:
new_grp = set_members | {candidate}
key = tuple(sorted(new_grp))
if key not in seen:
seen.add(key)
new_groups.append(new_grp)
if not new_groups:
break
groups = new_groups
assert len(groups) == 1
res = ",".join(sorted(groups[0]))
return res