Day 12

Here we have some set of two direction connections between programs. It's somewhat similar to the problem about balancing towers. We're tasked with finding the total number of programs that can be connected to program zero. This is basically finding the size of a subgraph. My first thought was to write some kind of recursive function to go through the connections that we previously had but this could actually lead to an infinite loop if there is a cycle within the graph. I guess, we could keep some sort of global list of all the nodes visited and then if we can prevent us from going back to a previously visited one.

I think I'll try to challenge myself again to not use any global variables and just keep passing the updated list back and forth.

import pandas as pd
import numpy as np

initial = open('/Users/Sven/py_files/aoc_2017/d12_input.txt').readlines()
initial[:5]

['0 <-> 46, 1376\n',
 '1 <-> 1465, 1889\n',
 '2 <-> 609, 1578\n',
 '3 <-> 3, 1003, 1133, 1887\n',
 '4 <-> 467, 1282\n']

Do some formatting

nodes = [x.split()[0].strip() for x in initial]
conns = [x.split('> ')[1].replace('\n', '').split(', ') for x in initial]
print(nodes[:3])
print(conns[:3])
nodes = dict(zip(nodes, conns))

['0', '1', '2']
[['46', '1376'], ['1465', '1889'], ['609', '1578']]

Okay so the strategy will be:

• Keep a list of nodes visited starting with '0'
• Write a function that takes a node to start from and the list of visited nodes
• It starts by adding the given node to the list
• Then it finds all the connections, checks if they've been visited, and then calls itself on new ones
• Finally it returns the list to the parent environment

def visit(node, visited):
    # append node to list
    visited.append(node)
    
    # find the connected nodes:
    connections = nodes[node]
    
    for new_node in connections:
        if not new_node in visited:
            visited = visit(new_node, visited)
    return(visited)
            

len(visit('0', []))

152

Part 2

Now we're asked to find how many disjoint subgraphs appear in this entire graph. I think this should be relatively easy given the function we just wrote. We should be able to just be able to just make a list of all the nodes visited, subtract that from the list of all nodes, send the first element remaining to the function, and so on...

We'll try out using sets for this as they define unique values and can easily take differences:

subgraphs = 0
remaining_nodes = set(nodes.keys())

while len(remaining_nodes) > 0:
    result = visit(remaining_nodes.pop(), [])
    remaining_nodes -= set(result)
    subgraphs += 1
subgraphs

186

gg ez