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

BeOnDrag — Wed, 09 Mar 2022 01:19:52 +0000

(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

S1=∑i=1n∣xi−x∣S_1=\sum_{i=1}^n|x_i-x|

and

s0=nx2−2(∑i=1nxi)xs_0=nx^2-2\left(\sum_{i=1}^nx_i\right)x

C_2

is just a constant

∑i=1nxi2\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 $xii=1nx=m_1=\text{the median of }{x_i}_{i=1}^n$ and $s_0$ reaches its minimum when $x=m2=C1nx=m_2=\frac{C_1}{n}$ , where $C1=∑i=1nxiC_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 $R\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 $m2≈462.508m_2\approx462.508$ , which are close enough, and the original problem restricted $x$ to be on $Z\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 $x1≤x2≤⋯≤xnx_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 $I0=(−∞,x1],I1=[x1,x2],…,In−1=[xn−1,xn],In=[xn,+∞)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 $ℓk=ℓk(x)\ell_k=\ell_k(x)$ , has a slope of $- n + 2 k$ . We also let $x0=−∞x_0=-\infty$ and $xn+1=+∞x_{n+1}=+\infty$ .

Consider $Fk(x)=ℓk(x)+Q(x)F_k(x)=\ell_k(x)+Q(x)$ , where $Q(x)=s0=nx2−2(∑i=1nxi)xQ(x)=s_0=nx^2-2\left(\sum_{i=1}^nx_i\right)x$ . Its axis of symmetry would be $dk=m2+12−knd_k=m_2+\frac{1}{2}-\frac{k}{n}$ . When $xk+1≤dkx_{k+1}\le d_k$ , $F_k(x)$ decreases on its domain. When $dk≤xkd_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β≤dβx_\beta\le d_\beta$ , and $xβ+1≥dβ+1x_{\beta+1}\ge d_{\beta+1}$ . Then on $(−∞,xβ](-\infty,x_\beta]$ $s = s (x)$ is decreasing, and on $[xβ+1,+∞)[x_{\beta+1},+\infty)$ $s (x)$ is increasing. This implies that the minimum of $s (x)$ could only be reached on $[xβ,xβ+1][x_\beta,x_{\beta+1}]$ . It's worth noticing that if $x1≥m2+12x_1\ge m_2+\frac{1}{2}$ , then $s (x)$ reaches minimum at $x=d_0$ ; if $xn≤m2−12x_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 $x1,x2,…,xnx_1,x_2,\dots,x_n$ , so be only need to check $s(dβ)s(d_\beta)$ , $s(dβ+1)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?

MathPage: An 11ty Template for Math Problem Lists

BeOnDrag — Sat, 05 Mar 2022 09:01:27 +0000

After (less than) 1 day of easy development, the unflexible, unextensible, unresponsive (okay responsive actually) and fully uncustomizable 11ty template MathPage has come out. See the demo here!

This template uses jQuery and KaTeX. The template suffix is .mpls (MathPage List). The format is like this:

# Page Title

## Category

Problem name
---
Problem
---
Hint
---
Solution
===
Problem name
---
Problem
---
Hint
---
Solution

(Trailing new lines is acceptable.)

It supports Markdown for styling. You will never see a worse template than this one elsewhere!

Okay this template is mainly for myself so I won't make it very good. But if you like it... thank you.

Forem: BeOnDrag

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

Problem #7, AoC 2021

Basic observations

Further Discussion

MathPage: An 11ty Template for Math Problem Lists