Advent of Code: Question 2

1 minute read


Today was a fairly easy challenge. Part one provides us with a 2d array of integers and asks to find the sum of the differences between the largest and smallest numbers in each row. Super easy to do without loops if you know how to use numpy.

import numpy as np
import pandas as pd

#Part 1
X = pd.read_clipboard(header = None).values #read in my input
checksum = np.apply_along_axis(lambda x: max(x) - min(x),1,X).sum()

Part two asks a similar question. Now we are told that there is one element in each row which evenly divides a different element. For instance, if the row consisted of 5,9,2, and 8, then 2 evenly divides 8. We are asked to find the sum of such quotients.

I had to think about this for a little bit. How can I check the pairwise quotients of an array without using a loop? If you are familiar with linear algebra, you may answer “the outer product!”. Let me explain.

Most people who have taken linear algebra know of the inner product of two vectors. Namely,

\[\mathbf{x}^T \cdot \mathbf{y} = \sum_{i= 1}^N x_i y_i \>.\]

The outer product is slightly different. The result is a matrix with pairwise products as entries. So the $j^{th}$ row is essentially $x_j \mathbf{y}$. From this, it is clear I can use the outer product to find the ratio of those two integers in each row. Shown below is a solution to part two:

def divisor_checksum(x):

    divis = np.ravel(x/x[:,None])  #equivalent to outer produt.  Ravel turns the matrix into a vector

    int_ix = np.equal(np.mod(divis,1),0)

    checksum = divis[int_ix&(divis!=1)] #The diagonal of this matrix consists of 1s (why?).  I've excluded them

    return checksum[0]

np.apply_along_axis(divisor_checksum, 1,X).sum()

Linear algebra, eh? Who would have thought 3 credits in that would come in handy.