DEV Community

Cover image for Advent of Code 2023 - December 25th
Rob van der Leek
Rob van der Leek

Posted on

Advent of Code 2023 - December 25th

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
Enter fullscreen mode Exit fullscreen mode

That's it! See you again tomorrow!

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more