AOC Day 7 2021

This is part of a greater series about solving advent of code with spreadsheets.

Part One And Two

As always, read the problem text first. In summary, part one and two are optimization problems.

In part one the goal is to find a number (X) that minimizes the sum of distances to elements in a set (A) ∑|A - X|. The goal of part two is to minimize the square distance⁰ ∑((A - X)^2 + |A - X|)/2.

(0) This exact formula comes from finite arithmetic series.

The final output is the minimized sum.

Solving Part One and Two

The comma separated list of elements goes into A2.

In part one the optimal number is.

GUESS	B2 = MEDIAN(SPLIT(A2,","))

In part two the optimal number is close to this. Adjust in place as necessary.

GUESS	B2 = AVERAGE(SPLIT(A2,","))

Without guesses, write into the value of the GUESS column to binary search for the optimal number¹.

(1) I “prove” why later in this web page.

All of the elements are turned into rows like this.

ELEMENTS²	C2 = TRANSPOSE(SPLIT(A2,","))	← spill	etc

(2) TRANSPOSE makes the spill go into rows.

Distances are then collected like this in part one.

DISTANCE	D2 = ABS(C2 - B$2)	repeat →

And like this in part two.

DISTANCE	D2 = ((C2 - B$2)^2 + ABS(C2 - B$2))/2	repeat →

The sum then is.

OUTPUT	E2 = SUM(D2:D)

How Part One and Part Two Work

This challenge was math heavy. I shied away from that challenge and went with some guesses. Here is some half-baked reasoning.

Part One and the MEDIAN

Someone has proved “the median minimizes the sum of absolute deviations”. That’s good enough for me.

Part Two and the AVERAGE

Someone has proved the average minimizes square number line distance. In the formula ((A - X)^2 + |A - X|)/2 the squared term looks dominant. So I ignored the other term with my guess. This turned out to be good enough since the optimal number was 1 away.

Binary Search

Even without an exact guess, this challenge can be solved with binary search. Both formulas produce a unimodal graph³. This can be traversed quickly to find a maximum or minimum.

(3) Well to be precise it’s unimodal when flipped upside-down.

Total cost versus choice of center has been graphed for the two parts below⁴. This constitutes a “visual proof”⁵ of “unimodality”.

(4) I used a small python script and the leather library to make these.

(5) I’m sure there’s a better proof. The graphs are curvy suggesting a nice formula.

You may be interested in the previous or next day's solution.