AoC 2021 - Day 7

Today’s challenge is here. We have to find the optimal point for all crabs to move to on a single axis. The optimal point is the point where the fuel expenditure to all other points is minimal.

Loading the input data:

def load() -> list[int]:
    with open('../.input/day07') as f:
        return [int(x) for x in f.readline().split(',')]

Task 1

In this task the way to calculate the fuel expenditure is to sum up the fuel expenditure to all other points. The way it’s calculated is linear. Formula for fuel expenditure, where C is the set of all points and x is the point we want to calculate the fuel expenditure for: ∑c∈C∣x−c∣ \sum_{c \in C} |x - c|

We are looking for the point with minimal fuel expenditure: min⁡x∑c∈C∣x−c∣ \min_{x} \sum_{c \in C} |x - c|

The way to find the optimal point is to find the median of all the points where crabs are placed, because the median happens to be the point where the fuel expenditure is minimal. Formula for the median: 12∑c∈Cc \frac{1}{2} \sum_{c \in C} c

I don’t really know how this works myself, but the proof for why it works can be found here.

Here’s the code for the task:

def solve1() -> int:
    numbers = load()
    median = sorted(numbers)[len(numbers) // 2]
    return sum(abs(x - median) for x in numbers)

Task 2

In this task we have to find the optimal point for all crabs to move to on a single axis, similar to task 1. The difference is that the way fuel expenditure is calculated is a sequence: 1, 1+2, 1+2+3, 1+2+3+4, …

The way I solved this is I looked up the formula for the function that calculates the value for the n-th element in the sequence on the Internet. It happens to be:

f(n)=n∗(n+1)2 f(n) = \frac{n * (n + 1)}{2}

I implemented this formula in the code below:

def nth_sum(n: int) -> int:
    return n * (n + 1) // 2

In the solution to the task 2 I used NumPy to create a matrix of the form: [000⋯0111⋯1222⋯2⋮⋮⋮⋱⋮nnn⋯n] \begin{bmatrix} 0 & 0 & 0 & \cdots & 0 \\\\ 1 & 1 & 1 & \cdots & 1 \\\\ 2 & 2 & 2 & \cdots & 2 \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ n & n & n & \cdots & n \end{bmatrix}

Then I subtracted the vector of the crab positions from the matrix. The result is a matrix with the distances from the crab to all other possible points.

[∣0−c1∣∣0−c2∣∣0−c3∣⋯∣0−ci∣∣1−c1∣∣1−c2∣∣1−c3∣⋯∣1−ci∣∣2−c1∣∣2−c2∣∣2−c3∣⋯∣2−ci∣⋮⋮⋮⋱⋮∣n−c1∣∣n−c2∣∣n−c3∣⋯∣n−ci∣] \begin{bmatrix} |0 - c_1| & |0 - c_2| & |0 - c_3| & \cdots & |0 - c_i| \\\\ |1 - c_1| & |1 - c_2| & |1 - c_3| & \cdots & |1 - c_i| \\\\ |2 - c_1| & |2 - c_2| & |2 - c_3| & \cdots & |2 - c_i| \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ |n - c_1| & |n - c_2| & |n - c_3| & \cdots & |n - c_i| \end{bmatrix}

We then apply the formula for the nn-th element in the sequence to the matrix. The result is a matrix with the fuel expenditure to all other points. When we sum the values in rows of the matrix we get the total fuel expenditure to all points for the crabs.

min⁡∑c∈Cf(∣x−c∣) \min \sum_{c \in C} f(|x - c|)

By finding the row with the minimal fuel expenditure we can find the optimal point. Below is the implementation in NumPy:

def solve2() -> int:
    numbers = np.array(load())
    search_vector = np.arange(0, max(numbers) + 1)
    search_matrix = np.tile(search_vector, (len(numbers), 1)).T
    distance = abs(search_matrix - numbers)
    fuel_expended = nth_sum(distance)
    return min(fuel_expended.sum(axis=1))