In this series, I'll share my progress with the 2023 version of Advent of Code.
Check the first post for a short intro to this series.
You can also follow my progress on GitHub.
December 25th
The puzzle of day 25 is straightforward if you know about Karger's algorithm (which I didn't, needed to Google it.)
My pitfall for this puzzle: Solving this puzzle required me to do a few searches on graph theory. It's always less satisfactory if I need to do that instead of coming up with something (horribly bloated and inefficient) myself.
Solution here, do not click if you want to solve the puzzle first yourself
#!/usr/bin/env python3
import random
def parse():
nodes = set()
edges = []
with open('input.txt') as infile:
lines = infile.readlines()
for line in lines:
parts = line.strip().split(': ')
from_node = parts[0]
nodes.add(from_node)
to_nodes = parts[1].split(' ')
for to_node in to_nodes:
nodes.add(to_node)
edges.append((from_node, to_node))
return [nodes, edges]
while True:
nodemap = {}
[nodes, edges] = parse()
while len(nodes) > 2:
e = random.choice(edges)
from_node = e[0]
to_node = e[1]
updated_edges = []
for edge in edges:
if edge[0] == from_node and edge[1] == to_node or \
edge[1] == from_node and edge[0] == to_node:
continue
elif edge[0] == to_node:
updated_edges.append((from_node, edge[1]))
elif edge[1] == to_node:
updated_edges.append((edge[0], from_node))
else:
updated_edges.append(edge)
edges = updated_edges
nodes.remove(to_node)
nodemap[from_node] = nodemap.get(from_node, 1) + nodemap.get(to_node, 1)
nodemap.pop(to_node, None)
if len(edges) == 3 and len(nodemap) == 2:
items = list(nodemap.items())
print(items[0][1] * items[1][1])
break
That's it! See you again tomorrow!
Top comments (0)