Power of Mathematics: 2021 AoC Problem #7, Part 2
Tags: adventofcode, algorithms
Published: 2022-03-09 01:19:52

(The algorithms tag is appropriate, I think)

This post will focus on the 7th problem of AoC 2021, part 2. We first discuss the straightforward method for the original problem, and then discuss the continuous version of the problem.

> This post requires some knowledge of mathematics, or more specifically, quadratic functions and absolute value.

## Problem #7, AoC 2021

### Basic observations

The 7th problem of 2021 Advent of Code is pretty interesting. Mathematically speaking we need to find a real number {% katex inline %}x{% endkatex %} for a certain real sequence {% katex inline %}\\{x_i\\}\_{i=1}^n{% endkatex %}, such that the expression
{% katex %}
S_2=\sum_{i=1}^n\frac{\left(|x_i-x|\right)\left(| x_i-x|+1\right)}{2}
{% endkatex %}
reaches its smallest possible value.

Multiply {% katex inline %}S_2{% endkatex %} by 2 doesn't affect the {% katex inline %}x{% endkatex %} we're looking for. So it suffices to look for the minimum of
{% katex %}
s=\sum_{i=1}^n\left(|x_i-x|\right)\left(|x_i-x|+1\right).
{% endkatex %}

Expanding the expression we easily get
{% katex %}
\begin{align*}
s&=\sum_{i=1}^n\left((x_i-x)^2+| x_i-x|\right)\\\\
 &=\sum_{i=1}^n(x_i-x)^2+\sum_{i=1}^n| x_i-x|\\\\
 &=s_0+S_1+C_2
\end{align*}
{% endkatex %}
where {% katex inline %}S_1=\sum_{i=1}^n|x_i-x|{% endkatex %}and {% katex inline %}s_0=nx^2-2\left(\sum_{i=1}^nx_i\right)x{% endkatex %}. {% katex inline %}C_2{% endkatex %} is just a constant {% katex inline %}\sum_{i=1}^nx_i^2{% endkatex %}, which doesn't affect our {% katex inline %}x{% endkatex %}.

Recall that
{% katex %}
S_1=\left|\sum_{x_i>x}x_i-\sum_{x_i<x}x_i\right|
{% endkatex %}

Let {% katex inline %}S_1{% endkatex %} reaches its minimum when {% katex inline %}x=m_1=\text{the median of }\{x_i\}_{i=1}^n{% endkatex %} and {% katex inline %}s_0{% endkatex %} reaches its minimum when {% katex inline %}x=m_2=\frac{C_1}{n}{% endkatex %}, where {% katex inline %}C_1=\sum\_{i=1}^nx_i{% endkatex %} is a constant. Both value is easy and quick to obtain from the computer. Denote the interval between {% katex inline %}m_0{% endkatex %} and {% katex inline %}m_1{% endkatex %} by {% katex inline %}I{% endkatex %}. Notice that {% katex inline %}S_1{% endkatex %} and {% katex inline %}s_0{% endkatex %}are both concaving up (at least not concaving down) on {% katex inline %}\mathbb{R}{% endkatex %}, therefore the minimum of {% katex inline %}s_0+S_1{% endkatex %} can only be reached on {% katex inline %}I{% endkatex %}. Since for the input provided by AoC {% katex inline %}m_1=309{% endkatex %} and {% katex inline %}m_2\approx462.508{% endkatex %}, which are close enough, and the original problem restricted {% katex inline %}x{% endkatex %} to be on {% katex inline %}\mathbb{Z}{% endkatex %}, the code can be easily written.

```python
# The straightforward method
from math import floor, ceil


def median(list: list[int]):
    leng = len(list)
    list.sort()
    if leng % 2 == 1:
        return list[(leng + 1) // 2]
    else:
        return (list[leng // 2] + list[leng // 2 + 1]) / 2


def method1(data: list[int]):
    med = median(data)
    mean = sum(data) / len(data)
    if med < mean:
        med = floor(med)
        mean = ceil(mean)
    else:
        med = ceil(med)
        mean = floor(mean)

    def calcVal(pos: int):
        nonlocal data
        sum = 0
        for e in data:
            dif = abs(e - pos)
            sum += (dif * (dif + 1)) // 2
        return sum
    answer = calcVal(med)
    position = med
    for i in range(med, mean + 1):
        newans = calcVal(i)
        if (newans < answer):
            answer = newans
            position = i
    print("Minimum is", answer, ", reached when x =", position)


method1([1, 2, 3, 5, 9, 12, 89])
```
```
Minimum is 3118 , reached when x = 17
```

### Further Discussion

But I don't want to stop here. We assume that {% katex inline %}x_1\le x_2\le\dots\le x_n{% endkatex %}. Consider the graph of {% katex inline %}L(x)=S_1{% endkatex %}It is made up with {% katex inline %}n+1{% endkatex %} segments (0 of length by chance), defined on {% katex inline %}I_0=(-\infty,x_1],I_1=[x_1,x_2],\dots,I_{n-1}=[x_{n-1},x_n],I_n=[x_n,+\infty){% endkatex %} respectively, whose slope being {% katex inline %}-n{% endkatex %} at the beginning, increases by 2 per segment, gradually stopping at {% katex inline %}n{% endkatex %}. Therefore the segment on {% katex inline %}I_k{% endkatex %}, denoted by {% katex inline %}\ell_k=\ell_k(x){% endkatex %}, has a slope of {% katex inline %}-n+2k{% endkatex %}. We also let {% katex inline %}x_0=-\infty{% endkatex %} and {% katex inline %}x_{n+1}=+\infty{% endkatex %}.

Consider {% katex inline %}F_k(x)=\ell_k(x)+Q(x){% endkatex %}, where {% katex inline %}Q(x)=s_0=nx^2-2\left(\sum_{i=1}^nx_i\right)x{% endkatex %}. Its axis of symmetry would be {% katex inline %}d_k=m_2+\frac{1}{2}-\frac{k}{n}{% endkatex %}. When {% katex inline %}x_{k+1}\le d_k{% endkatex %}, {% katex inline %}F_k(x){% endkatex %} decreases on its domain. When {% katex inline %}d_k\le x_k{% endkatex %}, {% katex inline %}F_k(x){% endkatex %} increases. Notice that while {% katex inline %}{x_i}{% endkatex %} is increasing while {% katex inline %}{d_i}{% endkatex %} is __decreasing__, there must be a number {% katex inline %}\beta{% endkatex %}, where {% katex inline %}x_\beta\le d_\beta{% endkatex %}, and {% katex inline %}x_{\beta+1}\ge d_{\beta+1}{% endkatex %}. Then on {% katex inline %}(-\infty,x_\beta]{% endkatex %} {% katex inline %}s=s(x){% endkatex %} is decreasing, and on {% katex inline %}[x_{\beta+1},+\infty){% endkatex %} {% katex inline %}s(x){% endkatex %} is increasing. This implies that the minimum of {% katex inline %}s(x){% endkatex %} could only be reached on {% katex inline %}[x_\beta,x_{\beta+1}]{% endkatex %}. It's worth noticing that if {% katex inline %}x_1\ge m_2+\frac{1}{2}{% endkatex %}, then {% katex inline %}s(x){% endkatex %} reaches minimum at {% katex inline %}x=d_0{% endkatex %}; if {% katex inline %}x_n\le m_2-\frac{1}{2}{% endkatex %}, then {% katex inline %}s(x){% endkatex %} reaches minimum at {% katex inline %}x=d_{n+1}{% endkatex %}; because the turning point of {% katex inline %}s(x){% endkatex %} is exactly {% katex inline %}x_1,x_2,\dots,x_n{% endkatex %}, so be only need to check {% katex inline %}s(d_\beta){% endkatex %}, {% katex inline %}s(d_{\beta+1}){% endkatex %}, {% katex inline %}s(d_0){% endkatex %} and {% katex inline %}s(d_{n+1}){% endkatex %}. This method is even worse for computer (has to sort the sequence and find {% katex inline %}\beta{% endkatex %}), but it's better mathematically (in my opinion). Also, this can work for any __real__ {% katex inline %}x{% endkatex %} and {% katex inline %}x_i{% endkatex %}.

```python
def method2(data: list[float]):
    data.sort()
    length = len(data)
    m2 = sum(data) / len(data)
    def s(x: float):
        nonlocal data
        sum = 0
        for e in data:
            dif = abs(e - x)
            sum += (dif * (dif + 1)) / 2
        return sum
    def d(i: int):
        nonlocal m2, length
        return m2 + 1 / 2 - i / length
    def findBeta():
        nonlocal data, m2
        for i in range(1, length):
            if data[i] >= d(i):
                return i - 1
        return length
    beta = findBeta()
    checklist = [beta + 1, 0, length]
    reachmin = 0
    minimum = s(d(beta))
    for i in checklist:
        newval = s(d(i))
        if newval < minimum:
            reachmin = d(i)
            minimum = newval
    print("Minimum is", minimum, ", reached when x =", reachmin)


method2([1, 2, 3, 5, 9, 12, 89])
```
```
Minimum is 3117.9821428571427 , reached when x = 16.928571428571427
```

Beautiful, isn't it?