Advent of Code 2020: Day 10 using NetworkX, numpy, in Python

#adventofcode #python

Today's challenge is another opportunity to use NetworkX, a graphing library for Python.

Things mentioned in this post: graph theory, directed graph, depth-first search

The Challenge Part 1

Link to challenge on Advent of Code 2020 website

The challenge comes down to finding, in a list of numbers, the differences between consecutive items, and multiplying how many of those differences are 1 with how many of those differences are 3

Numpy again

Let's dispense with the pleasantries, finding the difference between each number using numpy is a case of taking that numpy array, shifting it down by 1, and subtracting one from the other:

First we import the data:

import numpy as np
data = np.loadtxt("input.txt")

Output (for the demo data):

array([28., 33., 18., 42., 31., 14., 46., 20., 48., 47., 24., 23., 49.,
       45., 19., 38., 39., 11.,  1., 32., 25., 35.,  8., 17.,  7.,  9.,
        4.,  2., 34., 10.,  3.])

Then, we need to append a 0 for the supply, and 3 greater than the max value for the device (just a requirement of the challenge):

np.append(data, (0, np.max(data)+3))

Then we sort it:

joltages = np.sort(np.append(data, (0, np.max(data)+3)))

Output (for the demo data):

array([ 0.,  1.,  2.,  3.,  4.,  7.,  8.,  9., 10., 11., 14., 17., 18.,
       19., 20., 23., 24., 25., 28., 31., 32., 33., 34., 35., 38., 39.,
       42., 45., 46., 47., 48., 49., 52.])

Calculate the differences (using slicing to avoid out-of bounds)

diffs = joltages[1:] - joltages[:-1]

Output (for the demo data):

array([1., 1., 1., 1., 3., 1., 1., 1., 1., 3., 3., 1., 1., 1., 3., 1., 1.,
       3., 3., 1., 1., 1., 1., 3., 1., 3., 3., 1., 1., 1., 1., 3.])

Calculate the product of the 1s and the 3s:

np.sum(diffs == 1) * np.sum(diffs == 3)

The full code for part 1:

import numpy as np
data = np.loadtxt("demo.txt")
joltages = np.sort(np.append(data, (0, np.max(data)+3)))
diffs = joltages[1:] - joltages[:-1]
print("result", np.sum(diffs == 1) * np.sum(diffs == 3))

The Challenge Part 2

The 2nd part of the challenge asks to find all possible combinations of those numbers in which the difference between each pair is 3 or less. Here we have two obvious options: brute-force it by calculating every single combination, and checking that none have a difference greater than 3; or do it using some graphs, since for every given adapter, there's only a small number of other adapters that could connect to it. In this way we can build up a graph of possible adapters that could connect to each other, and traverse the graph.

Time to pull out the tool we used in Day 07: networkx. Networkx is an excellent graph solving tool for Python (and other languages) and makes light work of this.

First, we construct the graph, as with Day 07, we have a DiGraph, since adapters can connect only one way. We loop through the different adapters, and then for each adapter, we grab the remaining adapters, and find only the ones that are 3 or less jolts from this one. The loop is simply:

import networkx as nx
for idx, adapter in enumerate(joltages[:-1]):
    others = joltages[idx+1:]
    for other in others[others <= adapter+3]:
        graph.add_edge(adapter, other)

Networx implicitly adds nodes when you reference them in an edge.

Then finally, we just have NetworkX find all the possible paths with nx.all_simple_paths() this returns a generator, which each time you run will produce the next path, it's very efficient as it's doing a depth-first traversal, however we don't want to load all the results into memory, we just need the count, so we use sum(1 for _ in generator) to do it.

count = sum(1 for _ in nx.all_simple_paths(graph, supply, device))
print("paths", count)

Full code for this part:

import numpy as np
import networkx as nx

data = np.loadtxt("demo.txt")
joltages = np.sort(np.append(data, (0, np.max(data)+3)))

graph = nx.DiGraph()
for idx, adapter in enumerate(joltages[:-1]):

    others = joltages[idx+1:]
    for other in others[others <= adapter+3]:
        graph.add_edge(adapter, other, diff=other-adapter)

count = sum(1 for _ in nx.all_simple_paths(graph, supply, device))
print("paths", count)

This takes a while to run, but we get the answer eventually for minimum code work.

We can plot it too, this is what the eventual data looks like (image in header is the demo data graphed)

colors = ["grey"] * len(graph.nodes.keys())
colors[0] = "black"
colors[-1] = "red"

labels = {edge: props["diff"] for edge, props in graph.edges.items()}

pos = nx.nx_agraph.graphviz_layout(graph)
nx.draw(graph, pos=pos, node_color=colors, edge_color="grey", with_labels=True, node_size=15, font_size=3, width=0.1, arrowsize=2)
nx.draw_networkx_edge_labels(graph, pos, edge_labels=labels, font_color='grey', font_size=3)
plt.savefig("test.png", dpi=600)