25.md

Day 25

A cool problem, learned about a neat module.

	Part 1	Part 2	Total
Time	1:09:34	00:01	1:09:35

Part 1

I started by trying the bruteforce approach (you can check Part 3 if you want to see it, but you really don't) before spending 45 minutes on it, fixing bugs, etc... and finding out that it would take years to finish.

I was picking all possible combinations of 3 wires to remove, and checking the sizes of the connected sections after their removal. Happy to say it works on the sample!

Then I tried to come up with a way to figure out which three edges were crossed the most when running BFS fully from one node to another node, for each pair of nodes. I figured that the bridges would be travelled on most commonly. In the example, one of the correct wires did show up on top, but the other two were buried a little further down in the ranking. This futile solution has been lost to the sands of time, what a shame.

After realizing that I couldn't come up with a valid algorithm, I figured I'd look into it online. I found the concept of a Bridge in graph theory but all algorithms for finding them seemed to only work on graphs with single bridges - not sure if this is accurate, but that's what I got from my understanding. However, a potential bruteforce that utilizes that fact is instead of C(n, 3) combinations, it would be a much more manageable C(n, 2), then just check if the resulting graph has a bridge. Though I still think my terrible bruteforce code would have taken too long to be reasonable.

So... I decided way too late to check if there was perhaps a Python module or something that figured this out. I looked at one hint, suggesting that NetworkX would be great for this problem, and lo and behold, there it was in their Connectivity section, an aptly named minimum_edge_cut function which literally returns the minimum set of edges to remove from a graph G that would disconnect G - exactly what I was looking for.

I spent a couple of minutes learning the syntax for NX and somehow it is able to compute this problem in a couple of seconds. I first needed to find the edges to remove, then actually remove them, and finally get the size of the remaining partitions of the graph.

Some info about the minimum cut problem. Some more in-depth info.

from helpers.datagetter import aocd_data_in
import networkx as nx

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 1

G = nx.Graph()

for line in din:
    curr, others = line.split(": ")
    others = others.split(" ")
    for other in others:
        G.add_edge(curr, other)

for edge in nx.minimum_edge_cut(G):
    G.remove_edge(edge[0], edge[1])

for x in nx.connected_components(G):
    ans *= len(x)

aocd_submit(ans)

Part 2

I just pushed the big red button, I don't know what else to tell you!

Part 3

Ewww bad ugly slow... but working code that I was working on for Part 1. It bruteforce checks the consequences of removing all combinations of 3 wires. I also learned that .discard() exists for sets, and I totally didn't have try ... catch blocks wrapping all 6 .remove()s beforehand!

# This is the very slow, bad version lol

import itertools
from copy import deepcopy
import tqdm
from helpers.datagetter import aocd_data_in
from collections import defaultdict, deque

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0

conns = defaultdict(set)
connections = []

for line in din:
    curr, others = line.split(": ")
    others = others.split(" ")
    for other in others:
        conns[curr].add(other)
        conns[other].add(curr)
        connections.append([curr, other])


def connects(a, b, c):
    visited = set()
    queue = deque([a])
    while queue:
        curr = queue.popleft()

        if curr == b:
            return True

        if curr in visited:
            continue
        visited.add(curr)

        for next in c[curr]:
            queue.append(next)
    return False


wires = list(conns.copy().keys())
for remove_wires in tqdm.tqdm(itertools.combinations(connections, r=3)):
    a, b, c = remove_wires

    conns_copy = deepcopy(conns)

    conns_copy[a[0]].discard(a[1])
    conns_copy[a[1]].discard(a[0])
    conns_copy[b[0]].discard(b[1])
    conns_copy[b[1]].discard(b[0])
    conns_copy[c[0]].discard(c[1])
    conns_copy[c[1]].discard(c[0])

    groups = [[wires[0]], []]
    bad = False
    for wire in wires[1:]:
        if connects(wires[0], wire, conns_copy):
            groups[0].append(wire)
        elif len(groups[1]) == 0 or connects(groups[1][0], wire, conns_copy):
            groups[1].append(wire)
        else:
            bad = True
            break

    if not bad and len(groups[0]) != 0 and len(groups[1]) != 0:
        ans = len(groups[0]) * len(groups[1])
        break

aocd_submit(ans)