Power of Mathematics: 2021 AoC Problem #7, Part 2

(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 $x$ for a certain real sequence $\{x_i\}_{i=1}^n$ , such that the expression

$$S_2=\sum_{i=1}^n\frac{\left(|x_i-x|\right)\left(| x_i-x|+1\right)}{2}$$

reaches its smallest possible value.

Multiply $S_2$ by 2 doesn't affect the $x$ we're looking for. So it suffices to look for the minimum of

$$s=\sum_{i=1}^n\left(|x_i-x|\right)\left(|x_i-x|+1\right).$$

Expanding the expression we easily get

$$\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*}$$

where $S_1=\sum_{i=1}^n|x_i-x|$ and $s_0=nx^2-2\left(\sum_{i=1}^nx_i\right)x$ . $C_2$ is just a constant $\sum_{i=1}^nx_i^2$ , which doesn't affect our $x$ .

Recall that

$$S_1=\left|\sum_{x_i>x}x_i-\sum_{x_i<x}x_i\right|$$

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

# 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 $x_1\le x_2\le\dots\le x_n$ . Consider the graph of $L(x)=S_1$ It is made up with $n+1$ segments (0 of length by chance), defined on $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)$ respectively, whose slope being $-n$ at the beginning, increases by 2 per segment, gradually stopping at $n$ . Therefore the segment on $I_k$ , denoted by $\ell_k=\ell_k(x)$ , has a slope of $-n+2k$ . We also let $x_0=-\infty$ and $x_{n+1}=+\infty$ .

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

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?

Comments

[BeOnDrag]

Using the continuous version the best potision to align the crabs (my input data) is 462.40299999999996, where the fuel cost reaches the minimum of 96864153.79550003. A lot less than the "correct answer" 96864235!