AoC 2017 Day 12: Gridlock

Source: Digital Plumber

Part 1: A network of nodes is defined by a list of lines formatted as such:

2 <-> 0, 3, 4


Then, write a function that can take a node and recursively expand until it finds all nodes in the same group:

def find_group(node):
    '''Yield all nodes that are connected to the given node.'''

    visited = set()
    q = queue.Queue()

    while not q.empty():
        node = q.get()

        if node in visited:

        yield node

        for neighbor in neighbors[node]:

This is enough to tell how big the group containing 0 is:

print('the group containing 0 has {} nodes'.format(len(list(find_group(0)))))

Part 2: How many groups are there?

This is slightly more interesting since we don’t want to count a group twice if we start from two different nodes in the same group. Mostly though, we will iterate through all the nodes and add 1 to our count if the new node is not one we’ve seen before than record all nodes in that same group:

visited = set()
groups = []

for node in nodes:
    if node in visited:

    group = set(find_group(node))
    visited |= group

print('there are {} groups'.format(len(groups)))

Since we are working with sets, the | operator is a setwise or, it will include nodes in either group. |= will add any nodes in group to visited that aren’t already there. Since we’re only looking for new groups, they will never overlap, but | still works. Plus, it amuses me somewhat to use the pipe operator.

All together:

$ python3 day-12

day-12  python3 input.txt   0.12310385704040527     the group containing 0 has 115 nodes; there are 221 groups

As a fun aside, you could use GraphViz to visualize the graph.

First, generate a graph file with Python:

lib.add_argument('--visualize', default = False, help = 'Filename to write a graphviz file to for visualization')

if lib.param('visualize'):
    with open(lib.param('visualize'), 'w') as fout:
        fout.write('graph {\n')
        for node in nodes:
            for neighbor in neighbors[node]:
                fout.write('  {} -- {}\n'.format(node, neighbor))

Then use one of the layout engines to render it. neato gave me the best results:

$ python3 input.txt --visualize
$ neato -Tpng < > graph.png
$ open graph.png
Click for full size

Click for full size