Today’s puzzle is a simple optimization problem. The objective is to minimize a cost function.

The function to minimize can be written as :

f(x)=∑ i=1 nf i(x)\begin{aligned} f(x) = \sum_{i=1}^{n}f_i(x) \end{aligned}

where f i(x)f_i(x) has the following properties :

We understand easily that the minimum the function is in the interval [x min;x max][x_min; x_max], where x minx_min is the minimum of the numbers x 1,x 2,...,x n{x_1, x_2,..., x_n} and x maxx_max is the maximum.

Demonstration :

∀i∈[1;n]and∀x<x min,f i(x)>f i(x min).Therefore,∀x<x min,f i(x)>f i(x min). Inthesameway,∀i∈[1;n]and∀x>x max,f i(x)>f i(x max),so∀x>x max,f i(x)>f i(x max)\begin{aligned} \forall i \in [1; n] and \forall x \lt x_{min}, f_{i}(x) \gt f_{i}(x_{min}). Therefore, \forall x \lt x_{min}, f_{i}(x) \gt f_{i}(x_{min}).\\ In the same way, \forall i \in [1; n] and \forall x \gt x_{max}, f_{i}(x)\gt f_{i}(x_{max}), so \forall x \gt x_{max}, f_{i}(x) \gt f_{i}(x_{max}) \end{aligned}

Part 1

In this part, the cost function is the absolute value function f i(x)=|x−x i|f_i(x) = \vert x - x_{i}\vert

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let positions = input.iter().map(|x| x.parse().unwrap()).collect::<Vec<i64>>();
    let min_x = positions.iter().cloned().min().unwrap();
    let max_x = positions.iter().cloned().max().unwrap();
    let mut fuel_costs = HashMap::<i64, u64>::new();

    let mut x = min_x;
    while x <= max_x {
        fuel_costs.insert(x, 
            positions.iter()
                .map(|x0| (x - *x0).abs() as u64).sum::<u64>());
        x += 1;
    }

    *fuel_costs.values().min().unwrap()
}

Part 2

In the second part, the function is slightly more complex. It is defined as :

f i(x)=∑ k=0 |x−x i|k\begin{aligned} f_{i}(x) = \sum_{k=0}^{|x-x_{i}|}k \end{aligned}

For example, if x 1=16x_{1} = 16 and x=5x = 5, f 1(x)=∑ k=0 11kf_{1}(x) = \sum_{k=0}^{11}k

It is possible to simplify the calculation of this function, using the technique discovered by Carl Friedrich Gauss at the age of 8. We know that :

∑ k=0n=n*(n+1)/2\begin{aligned} \sum_{k=0}{n} = n * (n+1) / 2 \end{aligned}

Therefore, the function f_{i} becomes :

f i(x)=|x−x i|*(|x−x i|+1)/2\begin{aligned} f_{i}(x) = |x - x_{i}| * (|x - x_{i}| + 1) / 2 \end{aligned}

and its calculation is done in constant time. With the naive formula, it would be done in linear time.

The part 2 main function is only slightly modified, in the while block.

pub fn solve_part2(input: &Vec<String>) -> u64 {
    let positions = input.iter().map(|x| x.parse().unwrap()).collect::<Vec<i64>>();
    let min_x = positions.iter().cloned().min().unwrap();
    let max_x = positions.iter().cloned().max().unwrap();
    let mut fuel_costs = HashMap::<i64, u64>::new();

    let mut x = min_x;
    while x <= max_x {
        fuel_costs.insert(x,
            positions.iter()
                .map(|x0| ((x - *x0).abs() * ((x - *x0).abs()+1)/2) as u64)
                .sum::<u64>());
        x += 1;
    }

    *fuel_costs.values().min().unwrap()
}

Performances

Today, I discovered the --release option of the cargo run (or cargo build) command. This is the normal option used to build and run a Rust program in production, and this the one that should be used to measure program performances.

With the --release option, the part 1 runs in 700 µs, and the part 2 in 1800 µs. Without this option, both parts run in 60000 µs.